Store graph neighborhoods with explicit CSR and CSC orientation
Connect pointer arrays, edge multiplicity, degree counts and feature access patterns.
On this page
The question for today
What you’ll understand
- Reconstruct adjacency lists from compressed pointers and indices.
- Relate CSR and CSC degrees to an explicitly oriented adjacency matrix.
- Account for stored arcs, index widths and feature-gather locality.
A graph-learning system repeatedly asks which nodes send information to a destination and where their features live. Compressed sparse storage makes one such neighborhood query cheap, but only after its orientation is defined. The pointer array, neighbor indices and edge values must agree about whether a row means a source or a destination. Reversing that convention silently changes both degree accounting and the messages a model receives.
Choose what a matrix row means
For this lesson define A[u,v]=1 for a directed edge u→v, so rows represent sources and columns destinations. Compressed sparse row storage places each source’s outgoing destinations in one contiguous index interval. The row pointer has n+1 entries; row u begins at ptr[u] and ends just before ptr[u+1]. Their difference counts stored outgoing entries. Empty rows repeat a pointer value. The final pointer equals the total stored entry count, which need not equal the number of distinct unordered pairs.
Compressed sparse column storage organizes the same matrix by destination columns, making incoming source lists contiguous. That is often convenient for gathering messages into a destination. If another library defines adjacency with receiving nodes in rows, its CSR instead serves that incoming query directly. Neither convention is inherently wrong. Write the mathematical definition next to the format and test a directed asymmetric graph, because an undirected example can hide an accidental transpose. Keep the format choice separate from the message-passing rule.
Count the representation actually stored
An undirected simple graph is commonly represented using two directed arcs for each non-self edge. A stored self-loop is one entry unless the construction deliberately duplicates it. Parallel edges can remain separate or be coalesced into a value carrying multiplicity; the chosen operation changes the meaning of an unweighted degree. Record the policy before applying normalization. Coalescing is not simply a memory optimization if edge-specific features, timestamps or learned message weights depend on the individual parallel records.
With q-byte pointers, r-byte neighbor indices and v-byte values, one compressed orientation uses (n+1)q plus m(r+v) bytes before alignment and headers. Unweighted graph adjacency can omit values in a custom representation; a general sparse tensor API may still require them. Keeping both CSR and CSC adds another orientation and may require a permutation connecting edge attributes. A 32-bit node index does not imply a 32-bit offset is safe: the total stored arc count can exceed the node count substantially.
Contiguous adjacency does not make every feature access local
Sequentially reading a neighbor-index interval can still gather features scattered across a large node table. Sorting neighbor indices, reordering nodes and batching repeated feature requests can improve locality, but their costs and graph-update implications matter. Verify that reordered node and edge identifiers still align with labels and attributes. For dynamic graphs, maintaining a compact array may require rebuilds or an auxiliary update structure; a static storage byte count does not describe insertion cost or a consistent snapshot during reconstruction.
Use the cache lab to separate index order from feature working set. Reset and set both capacity C=4 and stride s=4: predict four misses and twelve hits among the initial sixteen requests. Separately Reset and set both C=4 and s=3: predict sixteen misses. The stream is address (i·s) mod 16 with N=min(4096,16+floor(2t)); Step adds one request until the cap. These abstract addresses illustrate reuse, not CSR conversion, graph degrees or actual feature-table performance.
Work it through
Decode a directed CSR and its reverse index
Take nodes 0…3 and directed edges 0→1, 0→3, 2→1 and 3→2. Store A[source,destination] in CSR with sorted destinations. Build the pointer and index arrays, then describe CSC and count bytes with four-byte pointers and indices and no stored values.
Outgoing lists are [1,3], [], [1] and [2]. Their lengths are 2,0,1,1, so CSR pointers are [0,2,2,3,4] and destination indices are [1,3,1,2]. The repeated pointer for node 1 correctly represents an empty row.
Incoming lists by destination are [], [0,2], [3] and [0]. CSC column pointers are [0,0,2,3,4] and source indices are [0,2,3,0]. Both orientations contain four stored arcs, while out-degree and in-degree sequences differ.
One orientation uses five pointers times four bytes plus four indices times four bytes: 20+16=36 bytes. Keeping both arrays without sharing uses 72 bytes, excluding attributes, headers and any mapping between their edge orders.
The asymmetric graph exposes orientation: CSR answers outgoing queries here and CSC incoming queries. Both pointer totals equal four even though node 1 has zero outgoing and two incoming edges.
The living notebook
Explore the model
Interactive lab · cache
Feature reuse is separate from adjacency compression
Fresh Reset → set C=4 and s=4 → predict initial misses 4, hits 12. Separate Reset → set C=4 and s=3 → predict misses 16, hits 0. Step adds one request, capped at 4096.
- Hits / requests
- 0 / 16
- Hit rate
- 0%
- Address-stream period
- 16 addresses
A fully associative LRU cache starts empty and requests address (i·s) mod 16. Hits move an address to the newest position; misses evict the oldest when full. Playback starts with 16 requests and adds two per second, capped at 4096 explicitly simulated requests. This toy stream is not a processor-cache benchmark. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forThe fully associative LRU stream has sixteen abstract addresses and starts empty. It does not construct CSR/CSC or benchmark a graph feature gather.
Pause & reason
Check your understanding
Your turn
Try it yourself
For edges 0→2, 1→0 and 1→2 on three nodes, write CSR pointers and indices under the same orientation. Count its bytes with eight-byte pointers, four-byte indices and four-byte edge values.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
The three row lengths are 1,2,0. Values consume storage in addition to neighbor indices.
Compare with the solution
Pointers are [0,1,3,3] and sorted destination indices [2,0,2]. Storage is four pointers×8=32 bytes plus three entries×(4+4)=24 bytes, totaling 56 bytes. The last empty row repeats the final pointer, and the stored in-degrees are 1,0,2 rather than the row-length sequence.
Keep the idea
Take it with you
- Define adjacency orientation before naming CSR or CSC neighborhoods.
- Stored arcs, parallel edges and self-loops determine degree accounting.
- Compressed adjacency locality does not guarantee feature-gather locality.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.