CSR: How Graphs Are Stored in Flat Arrays

Click a node to see which sections of the arrays correspond to its neighbors. Try clicking node 2 to see what an empty range looks like.

The Problem: Nested Maps Are Expensive

A graph with $N$ nodes and $E$ edges is typically stored as a nested map — graph[node_i][node_j] = weight. Every time you ask “who are node 0’s neighbors?”, the runtime hashes the key, walks hash buckets, checks equality, returns an inner map (another hash-based structure on the heap), and iterates over it — with hash + equality on every neighbor. Each weight is a separate heap-allocated object.

Data is scattered across memory. The CPU cache prefetcher can’t help — every access is a random pointer chase.

For algorithms like PageRank or PPR that iterate over all neighbors millions of times, this overhead dominates. In one real profile, FragmentId.__hash__ alone accounted for 295 million calls and 14.4 seconds of CPU time — and that’s just the hashing, not the dict lookups themselves.

How about a full matrix?

For a graph with 10,000 nodes and average degree 5, you have ~50,000 edges. A full adjacency matrix would be $10{,}000 \times 10{,}000 = 10^8$ cells. Only $50{,}000 / 10^8 = 0.05\%$ are nonzero — 99.95% wasted space, ~400 MB of zeros. And iterating a row still touches all $N$ cells even if only 5 are nonzero.

The CSR Solution

Give each node an integer index $0 \ldots N{-}1$ and store everything in three flat arrays:

• indptr (length $N{+}1$): bookmarks — indptr[i] says where node $i$‘s neighbors start
• indices (length $E$): all destination nodes packed sequentially, section by section
• weights (length $E$): edge weights, parallel to indices — weights[k] is the weight of the edge to indices[k]

To find neighbors of node $i$:

$\text{neighbors}(i) = \texttt{indices}[\,\texttt{indptr}[i] \;:\; \texttt{indptr}[i{+}1]\,]$

The indptr trick

Think of it like a family shopping list. Everyone’s items are written on one long list, and a separate slip of paper says “lines 1-5 are for mom, lines 6-7 for dad, lines 8-12 for grandma”. The list is indices. The slip with line ranges is indptr.

When indptr[i] == indptr[i+1], the range is empty — that node has no outgoing edges. Node 2 demonstrates this: indptr[2] = 3 and indptr[3] = 3, so indices[3:3] is an empty slice.

Why “Compressed Sparse Row”

• Compressed — zeros are not stored
• Sparse — designed for data where most entries are zero
• Row — traversal is by row (source node); for column-major access there’s CSC (Compressed Sparse Column)

Performance: Same Big-O, Different Constants

Both hash maps and CSR give $O(1)$ neighbor access asymptotically. The speedup comes from constants:

The constant factor difference is typically 10-30x for graph traversal workloads. This comes from three sources:

1. Zero hashing — 295M hash calls become zero
2. Cache locality — contiguous arrays fit L1/L2 cache, no pointer chasing
3. Vectorization — numpy operations on flat arrays use SIMD instructions

When NOT to Use CSR

CSR is optimized for read-heavy, write-once graphs:

• Dynamic graphs — inserting or removing an edge requires rebuilding the arrays. If your graph changes frequently, an adjacency list or edge list is better.
• Column access — finding all nodes that point to node $i$ (reverse lookup) is $O(E)$ in CSR. Use CSC for that, or store both.
• Very dense graphs — if most cells are nonzero, a plain matrix is simpler and has less overhead from indptr bookkeeping.

The typical pattern: build your graph using whatever is convenient (dict-of-dict, edge list), then convert to CSR once before the compute-heavy phase. Conversion costs $O(N + E)$ time and pays for itself on the first full traversal.