Lecture 22: Graph Optimization

What this lecture covers

Professor Julian Shun covers how to represent large graphs efficiently and how to make breadth-first search (BFS) fast, both serially and in parallel. The lecture follows on from earlier material on sparse matrices and the compressed sparse row (CSR) format, and builds toward general lessons about memory-bound, irregular algorithms that recur throughout the second half of the course. It answers a practical question: given that real-world graphs are large, sparse, and unevenly connected, what representation and traversal strategy actually performs well on real hardware?

After watching, you should be able to compare adjacency matrix, edge list, adjacency list, and CSR representations by their space and time trade-offs; implement a cache-conscious serial BFS; reason about races and determinism in a parallel BFS implementation; and explain why switching between top-down and bottom-up traversal strategies, or compressing edge lists, can significantly speed up graph algorithms.

Key ideas

• Graph representations: adjacency matrix (O(N^2) space, O(1) edge queries), edge list (O(M) space, slow neighbor lookup), adjacency list (O(N + M), easy updates), and compressed sparse row, or CSR (O(N + M), best for static, memory-efficient scans).
• Power law degree distribution: many real-world graphs have highly skewed degree distributions, where the number of vertices with degree D is proportional to D^-P; this causes load-imbalance issues when parallelizing across vertices.
• Cache-conscious BFS: the dominant cost in a naive serial BFS is random access into the parent array; replacing repeated parent checks with a compact bit vector for "has this vertex been visited" cuts cache misses substantially.
• Parallel BFS with frontiers: each BFS level (frontier) can be explored in parallel using a prefix sum to assign disjoint write locations for the next frontier, avoiding races when multiple vertices try to write to the same array region.
• Compare-and-swap and determinism: naive parallel updates to the parent array race and produce a non-deterministic BFS tree; using an atomic "write-min" operation in two phases makes the output tree deterministic at a small (5-20%) performance cost.
• Direction optimization: switching between a top-down traversal (good for small frontiers) and a bottom-up traversal that scans unexplored vertices' incoming edges (good for large frontiers) reduces wasted edge traversals, especially on power-law graphs.
• Graph compression: storing edge differences instead of raw targets, and encoding them with variable-length byte codes, shrinks memory use; because these algorithms are memory-bound, compression can make parallel runs faster, not just smaller.

Walkthrough

What a graph is and its applications (1:18)

The lecture opens with the basic vertex/edge model, noting that edges can be directed, weighted, and carry metadata (illustrated with social networks, protein networks, flight-cost graphs, and the Google Knowledge Graph). It then surveys applications: social network queries, clustering, connectomics, and image segmentation in computer vision, establishing why efficient graph algorithms matter broadly.

Comparing graph representations and their trade-offs (15:38)

Shun walks through the space cost and the cost of adding an edge, deleting an edge, and finding neighbors for four representations: adjacency matrix, edge list, adjacency list, and CSR. The section reinforces why CSR is preferred for the static algorithms covered in the rest of the lecture — scanning a vertex's neighbors is O(degree(v)) with good locality, at the cost of expensive updates.

Properties of real-world graphs (22:22)

Using examples like the Twitter network (41 million vertices, 1.5 billion edges, about 6.3 GB) and the Common Crawl web graph (3.5 billion vertices, 128 billion edges, over half a terabyte), the lecture shows that real-world graphs, while large, generally fit on large-memory machines. It highlights sparsity (M much less than N^2) and power-law degree distributions as properties that shape algorithm design.

Serial breadth-first search and its cache behavior (25:46)

After defining BFS outputs (visit order, distances, and a BFS tree), Shun presents CSR-based pseudocode and code for serial BFS, then does a back-of-the-envelope cache-miss analysis. The random accesses into the parent array dominate the miss count, which motivates replacing per-edge parent checks with a compact bit vector that only needs to be consulted once per vertex, cutting cache misses roughly from O(M) to O(N).

Parallel BFS with frontiers and prefix sums (25:46 continued / 42:04)

The parallel version processes one frontier at a time, using a Cilk for loop over frontier vertices and a prefix sum over vertex degrees to give each vertex a disjoint block of the next frontier's array, avoiding write conflicts. The work-span analysis shows Θ(D log M) span (where D is the graph diameter) and Θ(N + M) work, matching the serial algorithm's work while parallelizing across frontiers. Measured speedups reach about 32x on 40 hyperthreaded cores.

Determinism, direction optimization, and compression (57:16, 1:02:17, 1:10:31)

Shun identifies the compare-and-swap on the parent array as the source of non-determinism, then shows a two-phase write-min approach that makes the output BFS tree deterministic for a modest slowdown. He then introduces direction optimization, alternating between top-down traversal (good for small frontiers) and bottom-up traversal over unexplored vertices' incoming edges (good for large frontiers), which can be almost three times faster on power-law graphs. Finally, the lecture covers compressing CSR edge lists using delta encoding and variable-length byte codes, chunked to preserve parallel decoding, noting that because graph algorithms are memory-bound, compression can improve rather than hurt parallel performance.

Before you watch

• Review the compressed sparse row (CSR) format from the earlier lecture on sparse matrices, since this lecture reuses it directly for graphs.
• Be familiar with prefix sum, work-span analysis, and Cilk's parallel for loop, all covered in prior lectures on parallel programming.
• Understanding of compare-and-swap as an atomic primitive will help with the parallel BFS and determinism sections.

Check your understanding

1. Why does the compressed sparse row format make edge insertion expensive but neighbor iteration fast?
2. In the serial BFS cache analysis, why does accessing the parent array dominate the total cache misses, and how does a bit vector reduce this?
3. How does the prefix sum over frontier degrees let multiple threads write to frontier_next in parallel without races?
4. What specifically causes the non-determinism in the naive parallel BFS, and how does the write-min approach fix it?
5. Why is the bottom-up traversal strategy effective when the frontier is large, and why does it not help on graphs like road networks?