Why not store an edge list on disk and then only call up the edges you are visiting next in your random walk? Can be pretty time efficient if you use a tree to index the nodes. Solutions like SQL databases, parquet files, or hdf5 implement the indexing for you. However, these solutions are not as time efficient as a hashtable in memory but you are already switching away from those.

The challenge with networkx is exactly as you describe, you are storing the graph in memory. There are different backends you can configure for networkx, but they mainly seem to add graph algorithms not memory mapping functionality.