How to Traverse Million-Scale Graphs in Python: Scaling BFS with PySpark and GraphFrames

Learn why Python BFS slows on million-scale graphs and how to scale traversal with PySpark GraphFrames. Fix memory bottlenecks and get distributed performance.

Processing million-scale graphs in Python tends to hit two hard walls at once: memory pressure from native structures and slow single-core traversal. Breadth-first search or depth-first search over adjacency lists stored in files becomes a coordination problem the moment you try to parallelize state updates safely. When a dictionary-backed BFS finally runs, it often stalls on random memory access and cache misses. The way out is to shift the traversal onto an engine designed for distributed data, while keeping the developer ergonomics reasonable.

Baseline: the single-process BFS that does not scale

Here is the canonical in-memory BFS, which looks simple but quickly runs into memory and throughput limits on very large graphs:

from collections import deque
def walk_bfs(adj_index, origin):
    seen = set()
    frontier = deque([origin])
    while frontier:
        cur = frontier.popleft()
        if cur not in seen:
            seen.add(cur)
            frontier.extend(adj_index.get(cur, []))
    return seen

The logic is correct, yet the combination of Python dict, set, and deque means a lot of pointer chasing and random memory access. As the graph grows, this creates pressure on DRAM latency and makes multi-core scaling poor. Trying to split this across multiple processes adds contention and coordination costs for shared state, which can outweigh any gains.

Why it slows down at scale

Large-graph traversals are dominated by irregular memory access. With Python dictionaries and sets, lookups and inserts jump around in memory. That pattern puts DRAM throughput and latency on the critical path and limits speedups from additional CPU cores. Expanding BFS frontiers across processes increases synchronization and data-sharing complexity, especially when you need thread-safe updates and deduplicated visitation. BFS in particular is hard to scale well; DFS is typically easier to parallelize. A lower-level native representation and more vectorized code could reduce the memory footprint and help performance, but implementing it is non-trivial.

The practical path forward: pyspark + graphframes

To traverse very large graphs without loading everything into the memory of a single Python process, move the work to a distributed data engine. A combination of pyspark and graphframes lets you express BFS at a high level while leaning on the engine to orchestrate parallel execution and data management. The traversal stays declarative, and you avoid building your own synchronization for shared state. Below is a minimal example that constructs a small graph and runs BFS end-to-end using graphframes.

from pyspark.sql import SparkSession
from graphframes import GraphFrame
# Initialize Spark session
spark_sess = SparkSession.builder \
    .appName("BFS") \
    .config("spark.jars.packages", "graphframes:graphframes:0.8.2-spark3.0-s_2.12") \
    .getOrCreate()
# Create vertex and edge DataFrames
v_df = spark_sess.createDataFrame([
    ("a", "Alice"),
    ("b", "Bob"),
    ("c", "Charlie"),
    ("d", "David"),
    ("e", "Esther")
], ["id", "name"])
e_df = spark_sess.createDataFrame([
    ("a", "b"),
    ("b", "c"),
    ("c", "d"),
    ("d", "e")
], ["src", "dst"])
# Build the GraphFrame
gf = GraphFrame(v_df, e_df)
# Execute BFS query
bfs_out = gf.bfs(fromExpr="id = 'a'", toExpr="id = 'e'")
bfs_out.show(truncate=False)

This approach targets the core issues outlined above. The data is represented as DataFrames, the traversal is executed by graphframes, and you do not need to load a massive adjacency dict into one process or design custom inter-process messaging. If you later want to explore graph databases, Neo4j is also an option to consider.

Why this is worth knowing

At large scale, graph algorithms are constrained less by pure compute and more by memory access patterns and data movement. Recognizing that BFS is particularly tough to parallelize effectively prevents time sinks in ad-hoc multiprocessing experiments that still bounce across DRAM with poor locality. Knowing when to step up to a distributed data engine can save substantial effort and make traversal feasible on graphs that do not fit comfortably into a single machine’s memory. Alternatively, moving to a lower-level representation can pay off, but the engineering cost is significant.

Conclusion

If a Python dict-backed BFS is hitting memory limits and running slowly, shift the computation onto pyspark with graphframes and express traversal at the DataFrame level. This avoids hand-rolled concurrency, reduces the need to keep the entire graph in a single process, and aligns the workload with infrastructure designed to handle it. Keep in mind that BFS is inherently challenging to scale due to random memory access; if you later need different tooling, a graph database like Neo4j is a reasonable next exploration.