Graph Reordering for Hardware Aware Memory Locality

46 concepts35 papers1 proposal

Modern hardware is built for arrays, but real-world data is increasingly shaped like a web. When an algorithm processes a graph—whether it is traversing a social network, counting triangles, or aggregating features in a Graph Neural Network (GNN)—it must follow edges from one node to another. On a chip, this translates to following pointers across arbitrary memory addresses.

Because standard graph layouts do not align with physical memory architecture, graph processing is fundamentally bottlenecked by memory latency rather than computational throughput. As argued by Mengzhao Wang et al. in Accelerating Graph Indexing for ANNS on Modern CPUs, performance in these domains is heavily limited by random memory access patterns rather than arithmetic capacity. To overcome this "pointer-chasing" bottleneck, a prominent research direction focuses on hardware-aware spatial locality optimization: restructuring how graphs are stored in memory and how execution is scheduled to match the underlying hardware.

The Core Mechanism: Mapping Topology to Physical Layout

To understand why graph reordering works, we must look at how CPUs and GPUs fetch data. Hardware does not retrieve single bytes from main memory; it fetches data in contiguous chunks called cache lines or via burst transfers. If an algorithm accesses node $A$ and then immediately jumps to a distant memory address to access its neighbor node $B$, the data fetched alongside $A$ is wasted, and the jump to $B$ causes a cache miss.

Graph reordering solves this by relabeling node identifiers so that nodes that are topologically close (i.e., connected by edges or belonging to the same community) are assigned consecutive IDs. Because data arrays are indexed by these IDs, topological proximity directly translates into physical adjacency in memory.

Traditional Layout (Random IDs):
Node 1 -> Memory Address 0x04 (Neighbors: Node 800, Node 45) -> Cache Misses

Reordered Layout (Consecutive IDs for Communities):
Node 1 -> Memory Address 0x04 (Neighbors: Node 2, Node 3)   -> Cache Hits!

The impact of this physical rearrangement is widespread:

Beyond Topology: Priority and Type-First Layouts

While grouping communities optimizes for general traversals, specific workloads exhibit execution patterns that demand more specialized layouts. Spatial locality can be optimized based on execution priority, node attributes, or structural types.

Priority-Based Relabeling

In intensive graph-mining tasks like counting "butterflies" (2x2 bicliques) in bipartite networks, execution is highly non-uniform; a small subset of high-priority or high-degree vertices is accessed repeatedly. To exploit this, Kai Wang et al. in Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks and Accelerated butterfly counting with vertex priority on bipartite graphs introduce priority-based vertex relabeling. By reordering internal graph storage to place high-priority vertices contiguously, they ensure the "hot core" of the graph remains resident in the CPU cache, drastically reducing memory latency overhead.

Type-First and Structural Layouts

For Heterogeneous GNNs (HGNNs), where nodes possess different types and feature dimensions, standard mixed-index layouts destroy GPU memory coalescing. The authors of Accelerating Mini-batch HGNN Training by Reducing CUDA Kernels solve this by implementing a type-first layout that stores features of the same node type contiguously, maximizing memory throughput during feature retrieval.

Similarly, when dealing with multi-attribute graph visualizations or pangenome layouts, Jiajie Li et al. show in Rapid GPU-Based Pangenome Graph Layout that transitioning from a structure-of-arrays to an array-of-structs format ensures that related node attributes (like coordinates and boundaries) are retrieved in a single contiguous memory access, minimizing latency for GPU threads.

Locality-Aware Sampling and Traversal Scheduling

When a graph is too massive to fit entirely into fast memory (such as GPU VRAM), or when the physical layout cannot be altered, systems can achieve spatial locality by inverting the problem: adapting the execution and sampling patterns to match the hardware's current state.

Biasing Samples Toward Caches

In large-scale GNN training, fetching neighbor features from host CPU memory to the GPU over the slow PCIe bus is a notorious bottleneck. Instead of sampling neighborhoods uniformly, modern frameworks intentionally bias their sampling algorithms.

Mingyu Yan et al. introduce this concept in GNNSampler: Bridging the Gap between Sampling Algorithms of GNN and Hardware by prioritizing nodes whose neighbors are already stored contiguously, enabling burst memory transfers. Taking this further, the authors of Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs and Towards Affordable, Adaptive and Automatic GNN Training on CPU-GPU Heterogeneous Platforms design sampling routines that explicitly favor nodes already residing in the GPU cache. This coordination increases local data reuse across mini-batches and cuts down on redundant PCIe traffic.

Cache Blocking and Traversal Alignment

Execution scheduling can also be regularized to enforce locality. In BatchLayout: A Batch-Parallel Force-Directed Graph Layout Algorithm in Shared Memory, the authors employ cache blocking and reformulate graph force calculations as dense matrix operations, ensuring that data remains tightly packed in high-speed CPU caches during intensive iterations.

For graph searches, Rong Zhou 0001 et al. demonstrate in Structured Duplicate Detection in External-Memory Graph Search that expanding nodes in an order that respects an underlying abstract graph structure localizes memory references, allowing slow external memory to perform nearly as efficiently as RAM.

Finally, when executing algorithms across multiple related subgraphs, Runzhen Xue et al. show in HiHGNN: Accelerating HGNNs through Parallelism and Data Reusability Exploitation that scheduling the processing order based on shared data components minimizes external memory traffic by maximizing the utility of data already sitting in local on-chip buffers.

Summary

Whether by physically reordering node IDs on disk, grouping features by type on the GPU, or biasing sampling routines toward cached data, the goal remains identical: transforming unpredictable pointer-chasing into predictable, sequential hardware operations. By aligning the logical structure of graph data with the physical realities of modern memory hierarchies, these techniques unlock order-of-magnitude performance gains without requiring changes to underlying algorithmic complexity.

Key Foundational Work

Structured Duplicate Detection in External-Memory Graph Search (2004) — contributed 1 concept elements to this direction.
A novel page-based data structure for interactive walkthroughs (2009) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_spatial_locality_optimization_653acc91,
  title = {spatial locality optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatial-locality-optimization/rdr_653acc91c01942e2a0713851ed6c8b5b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_spatial_locality_optimization_653acc91_v1,
  title = {spatial locality optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatial-locality-optimization/rdr_653acc91c01942e2a0713851ed6c8b5b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake