Reordering Algorithms

Graph Reordering Algorithms

GraphBrew implements 18 different vertex reordering algorithms (IDs 0-17), each with unique characteristics suited for different graph topologies. This page explains each algorithm in detail.

Note: Algorithm ID 13 (MAP) is reserved for external label mapping files, not a standalone reordering algorithm.

Why Reorder Graphs?

Graph algorithms spend significant time accessing memory. When vertices are ordered randomly, memory access patterns are unpredictable, causing cache misses. Reordering places frequently co-accessed vertices together in memory, dramatically improving cache utilization.

Before Reordering:           After Reordering:
Vertex 1 → 5, 99, 2000       Vertex 1 → 2, 3, 4
Vertex 2 → 8, 1500, 3        Vertex 2 → 1, 3, 5
(scattered neighbors)         (nearby neighbors)

Algorithm Categories

Category	Algorithms	Best For
Basic	ORIGINAL, RANDOM, SORT	Baseline comparisons
Hub-Based	HUBSORT, HUBCLUSTER	Power-law graphs
DBG-Based	DBG, HUBSORTDBG, HUBCLUSTERDBG	Cache locality
Community	RABBITORDER	Hierarchical communities
Classic	GORDER, CORDER, RCM	Bandwidth reduction
Leiden-Based	LeidenOrder (15, baseline), ~~LeidenDendrogram (16)~~, LeidenCSR (17)	Strong community structure
Hybrid	GraphBrewOrder (12), MAP (13), AdaptiveOrder (14)	External/Adaptive selection

Basic Algorithms (0-2)

0. ORIGINAL

Keep original vertex ordering

./bench/bin/pr -f graph.el -s -o 0 -n 3

Description: Uses vertices in their original order from the input file
Complexity: O(1) - no reordering
Best for: Baseline comparison, already well-ordered graphs
When to use: Always run this first to establish baseline performance

1. RANDOM

Random vertex permutation

./bench/bin/pr -f graph.el -s -o 1 -n 3

Description: Randomly shuffles all vertices
Complexity: O(n) where n = number of vertices
Best for: Testing, worst-case scenarios
When to use: Debugging, establishing worst-case baseline

2. SORT

Sort vertices by ID

./bench/bin/pr -f graph.el -s -o 2 -n 3

Description: Sorts vertices in ascending order by original ID
Complexity: O(n log n)
Best for: Graphs where IDs have locality meaning
When to use: When input has meaningful vertex numbering

Hub-Based Algorithms (3-4)

These algorithms prioritize high-degree vertices (hubs) which are accessed frequently.

3. HUBSORT

Sort by degree (hubs first)

./bench/bin/pr -f graph.el -s -o 3 -n 3

Description: Places high-degree vertices (hubs) at the beginning
Complexity: O(n log n)
Rationale: Hubs are accessed most frequently; placing them together improves cache reuse
Best for: Power-law graphs (social networks, web graphs)

How it works:

Original:  v1(deg=5), v2(deg=100), v3(deg=2), v4(deg=50)
After:     v2(deg=100), v4(deg=50), v1(deg=5), v3(deg=2)

4. HUBCLUSTER

Cluster hubs with their neighbors

./bench/bin/pr -f graph.el -s -o 4 -n 3

Description: Places each hub followed by its neighbors
Complexity: O(n + m) where m = number of edges
Rationale: When accessing a hub, its neighbors are likely accessed next
Best for: Graphs with hub-and-spoke patterns

How it works:

Hub v2 has neighbors: v1, v5, v8
Ordering: v2, v1, v5, v8, [next hub], ...

DBG-Based Algorithms (5-7)

Degree-Based Grouping (DBG) creates "frequency zones" based on access patterns.

5. DBG

Degree-Based Grouping

./bench/bin/pr -f graph.el -s -o 5 -n 3

Description: Groups vertices by degree into logarithmic buckets
Complexity: O(n)
Rationale: Vertices with similar degrees have similar access frequencies
Best for: General-purpose, works well on most graphs

Bucket structure:

Bucket 0: degree 1
Bucket 1: degree 2-3
Bucket 2: degree 4-7
Bucket 3: degree 8-15
...

6. HUBSORTDBG

HUBSORT within DBG buckets

./bench/bin/pr -f graph.el -s -o 6 -n 3

Description: First groups by DBG, then sorts each bucket by degree
Complexity: O(n log n)
Best for: Combines benefits of both approaches

7. HUBCLUSTERDBG ⭐ (Recommended for power-law)

HUBCLUSTER within DBG buckets

./bench/bin/pr -f graph.el -s -o 7 -n 3

Description: First groups by DBG, then clusters hubs with neighbors in each bucket
Complexity: O(n + m)
Best for: Power-law graphs with clear hub structure

Edge Case Handling (Hub-Based Algorithms)

All hub-based algorithms (HUBSORT, HUBCLUSTER, DBG, HUBSORTDBG, HUBCLUSTERDBG) include guards for empty subgraphs:

// Guard against empty graphs (prevents division by zero)
if (num_nodes == 0) {
    return;  // Nothing to reorder
}
const int64_t avgDegree = num_edges / num_nodes;

This is important when these algorithms are used as the final algorithm in GraphBrewOrder, where community subgraphs may have no internal edges on graphs with extreme structure (e.g., Kronecker graphs).

Community & Classic Algorithms (8-11)

These algorithms use different approaches: RabbitOrder detects communities, while GORDER, CORDER, and RCM focus on bandwidth reduction and cache optimization.

8. RABBITORDER

Rabbit Order (community + incremental aggregation using Louvain)

# Format: -o 8[:variant] where variant = csr (default) or boost
./bench/bin/pr -f graph.el -s -o 8 -n 3         # Default: CSR variant (native, fast)
./bench/bin/pr -f graph.el -s -o 8:csr -n 3     # Explicit CSR variant
./bench/bin/pr -f graph.el -s -o 8:boost -n 3   # Original Boost-based variant

Description: Hierarchical community detection with incremental aggregation (Louvain-based)
Complexity: O(n log n) average
Variants:
- csr (default): Native CSR implementation - faster, no external dependencies
- boost: Original Boost-based implementation - requires Boost library
Note: RabbitOrder is enabled by default (RABBIT_ENABLE=1 in Makefile)
Best for: Large graphs with hierarchical community structure
Limitation: Uses Louvain (no refinement), can over-merge communities

Isolated Vertex Handling: Both variants group isolated (degree-0) vertices at the end of the permutation, matching Boost's original behavior and improving cache locality for non-isolated vertices.

Key insight: Uses a "rabbit" metaphor where vertices "hop" to form communities.

Comparison with GVE-Leiden (Algorithm 17):

Metric	RabbitOrder	GVE-Leiden
Algorithm	Louvain (no refinement)	Leiden (with refinement)
Community Quality	Good	Better
Speed	Faster	Slightly slower
Over-merging	Can occur	Prevented by refinement

9. GORDER

Graph Ordering (dynamic programming + BFS)

./bench/bin/pr -f graph.el -s -o 9 -n 3

Description: Uses dynamic programming with sliding window optimization
Complexity: O(n × w) where w = window size
Best for: Graphs where local structure matters

Window optimization:

Window size determines how far ahead to look when placing vertices
Larger window = better quality, slower computation

10. CORDER

Cache-aware Ordering

./bench/bin/pr -f graph.el -s -o 10 -n 3

Description: Explicitly optimizes for CPU cache hierarchy
Complexity: O(n + m)
Best for: Cache-sensitive applications

11. RCM

Reverse Cuthill-McKee

./bench/bin/pr -f graph.el -s -o 11 -n 3

Description: Classic bandwidth-reduction algorithm (BFS-based)
Complexity: O(n + m)
Best for: Sparse matrices, scientific computing graphs
Note: Originally designed for sparse matrix solvers

How it works:

Start from a peripheral vertex (far from center)
BFS traversal, ordering by increasing degree
Reverse the final ordering

Advanced Hybrid Algorithms (12-14)

12. GraphBrewOrder

Per-community reordering with variant support

# Format: -o 12[:variant[:frequency[:intra_algo[:resolution[:maxIterations[:maxPasses]]]]]]
./bench/bin/pr -f graph.el -s -o 12 -n 3                   # Use defaults (leiden variant)
./bench/bin/pr -f graph.el -s -o 12:leiden -n 3            # Explicit leiden variant
./bench/bin/pr -f graph.el -s -o 12:gve -n 3               # GVE-Leiden variant (faster)
./bench/bin/pr -f graph.el -s -o 12:gveopt -n 3            # Cache-optimized GVE
./bench/bin/pr -f graph.el -s -o 12:gve:10:8 -n 3          # gve variant, freq=10, intra=RabbitOrder

Description: Runs community detection, then applies per-community reordering
Variants:
- leiden: Original GVE-Leiden library - default
- gve: GVE-Leiden CSR-native implementation
- gveopt: Cache-optimized GVE with prefetching
- gvefast: Single-pass GVE (faster, less refinement)
- gveoptfast: Cache-optimized single-pass GVE
- rabbit: RabbitOrder-based community detection
- hubcluster: Hub-clustering based approach
Parameters:
- frequency: Hub frequency threshold (default: 10) - controls how edges are categorized
- intra_algo: Algorithm ID to use within communities (default: 8 = RabbitOrder)
- resolution: Leiden resolution parameter (default: dynamic for best PR performance)
- maxIterations: Maximum Leiden iterations (default: 30)
- maxPasses: Maximum Leiden passes (default: 30)
Dynamic thresholds: Community size thresholds are computed dynamically based on avg_community_size/4 and sqrt(N)
Best for: Fine-grained control over per-community ordering

13. MAP

Load mapping from file

./bench/bin/pr -f graph.el -s -o 13:mapping.lo -n 3

Description: Loads a pre-computed vertex ordering from file
File formats: .lo (list order) or .so (source order)
Best for: Using externally computed orderings

14. AdaptiveOrder ⭐ (ML-powered)

Perceptron-based algorithm selection

./bench/bin/pr -f graph.el -s -o 14 -n 3           # Default: per-community
./bench/bin/pr -f graph.el -s -o 14:2 -n 3          # Multi-level (depth=2)
./bench/bin/pr -f graph.el -s -o 14:0:0.75:50000:1 -n 3  # Full-graph mode

Description: Uses ML to select the best algorithm for each community
Features: 15 linear + 3 quadratic cross-terms + convergence bonus
Safety: OOD guardrail, ORIGINAL margin fallback
Parameters: max_depth (0), resolution (auto), min_recurse_size (50000), mode (0=per-community, 1=full-graph)

See AdaptiveOrder-ML for the full ML model details.

Leiden Variants (15-17)

GraphBrew consolidates Leiden algorithms into three main IDs with parameter-based variant selection for cleaner script sweeping.

15. LeidenOrder (Baseline Reference)

Leiden community detection via GVE-Leiden library

# Format: -o 15:resolution
./bench/bin/pr -f graph.el -s -o 15 -n 3                    # Default (auto-resolution)
./bench/bin/pr -f graph.el -s -o 15:0.75 -n 3               # Lower resolution
./bench/bin/pr -f graph.el -s -o 15:1.5 -n 3                # Higher resolution

Description: Leiden community detection using the external GVE-Leiden library (requires CSR→DiGraph conversion)
Complexity: O(n log n) average
Best for: Baseline comparison — measures how much LeidenCSR (17) improved over the reference implementation
Default resolution: Auto-detected via continuous formula (0.5-1.2) with CV guardrail for power-law graphs
Note: LeidenCSR (17) reimplements this natively on CSR and is 28–95× faster to reorder with equivalent kernel quality. Use LeidenCSR for production workloads.

Key features:

Uses GVE-Leiden C++ library by Subhajit Sahu (external/leiden/)
Requires CSR → DiGraph format conversion (adds overhead)
Produces high-quality modularity scores (reference quality)

16. LeidenDendrogram ⚠️ (Deprecated)

Leiden community detection with dendrogram traversal

⚠️ Deprecated: LeidenDendrogram is functionally superseded by LeidenCSR (17) variants (gvedendo, dfs, bfs, hubsort) which produce equivalent kernel quality but reorder 28–95× faster. This algorithm is kept only for historical comparison. Use LeidenCSR (17) instead.

# Format: -o 16:variant:resolution
./bench/bin/pr -f graph.el -s -o 16 -n 3                    # Default (auto-resolution, hybrid)
./bench/bin/pr -f graph.el -s -o 16:dfs:1.0 -n 3            # DFS traversal
./bench/bin/pr -f graph.el -s -o 16:dfshub:1.0 -n 3         # DFS hub-first
./bench/bin/pr -f graph.el -s -o 16:dfssize:1.0 -n 3        # DFS size-first
./bench/bin/pr -f graph.el -s -o 16:bfs:1.0 -n 3            # BFS traversal
./bench/bin/pr -f graph.el -s -o 16:hybrid:1.0 -n 3         # Hybrid (recommended)

Variants:

Variant	Description	Best For
`dfs`	Standard DFS traversal	General hierarchical
`dfshub`	DFS with hub-first ordering	Power-law graphs
`dfssize`	DFS with size-first ordering	Uneven community sizes
`bfs`	BFS level-order traversal	Wide hierarchies
`hybrid`	Sort by (community, degree)	Default - best overall

17. LeidenCSR ⭐ (Fastest, Best Quality)

GVE-Leiden: Fast CSR-native Leiden with proper refinement

Implements the full Leiden algorithm from: "Fast Leiden Algorithm for Community Detection in Shared Memory Setting" (ACM DOI 10.1145/3673038.3673146)

# Format: -o 17[:variant:resolution:iterations:passes]
./bench/bin/pr -f graph.el -s -o 17 -n 3                    # Default: gveopt2 (fastest + best quality)
./bench/bin/pr -f graph.el -s -o 17:gve:1.0:20:5 -n 3       # GVE-Leiden explicit params
./bench/bin/pr -f graph.el -s -o 17:gveopt:auto -n 3        # Cache-optimized GVE, auto resolution
./bench/bin/pr -f graph.el -s -o 17:gveopt2:2.0:20:10 -n 3  # CSR-based aggregation (fastest)
./bench/bin/pr -f graph.el -s -o 17:gveadaptive:dynamic -n 3 # Dynamic resolution adjustment
./bench/bin/pr -f graph.el -s -o 17:gvedendo:1.0:20:5 -n 3  # GVE with incremental dendrogram
./bench/bin/pr -f graph.el -s -o 17:gveoptsort:auto -n 3    # Multi-level sort ordering
./bench/bin/pr -f graph.el -s -o 17:gveturbo:1.0:5:10 -n 3  # Speed-optimized (skip refinement)
./bench/bin/pr -f graph.el -s -o 17:gverabbit:1.0:5 -n 3    # GVE-Rabbit hybrid (fast)
./bench/bin/pr -f graph.el -s -o 17:hubsort:1.0:10:3 -n 3   # Hub-sorted variant
./bench/bin/pr -f graph.el -s -o 17:fast:1.0:10:2 -n 3      # Union-Find + Label Prop
./bench/bin/pr -f graph.el -s -o 17:dfs:1.0:10:1 -n 3       # DFS ordering
./bench/bin/pr -f graph.el -s -o 17:bfs:1.0:10:1 -n 3       # BFS ordering

Resolution Parameter Modes:

Mode	Syntax	Description
Fixed	`1.5`	Use specified resolution value
Auto	`auto` or `0`	Compute from graph density and CV
Dynamic	`dynamic`	Auto initial, adjust per-pass (gveadaptive only)
Dynamic+Initial	`dynamic_2.0`	Start at 2.0, adjust per-pass

# Resolution modes examples
./bench/bin/pr -f graph.el -s -o 17:gveopt2:1.5 -n 3       # Fixed resolution
./bench/bin/pr -f graph.el -s -o 17:gveopt2:auto -n 3      # Auto-computed resolution
./bench/bin/pr -f graph.el -s -o 17:gveopt2:0 -n 3         # Same as auto
./bench/bin/pr -f graph.el -s -o 17:gveadaptive:dynamic -n 3      # Dynamic adjustment
./bench/bin/pr -f graph.el -s -o 17:gveadaptive:dynamic_2.0 -n 3  # Dynamic, start at 2.0

Variants:

Variant	Description	Speed	Quality	Best For
`gve`	GVE-Leiden with refinement	Fast	Best	Modularity quality
`gveopt`	Cache-optimized GVE with prefetching	Faster	Best	Large graphs
`gveopt2`	CSR-based aggregation (DEFAULT)	Fastest	Best	Best overall ⭐
`gveadaptive`	Dynamic resolution adjustment	Fast	Best	Unknown graphs ⭐
`gveoptsort`	Multi-level sort ordering (LeidenOrder-style)	Fast	Best	Hierarchical
`gveturbo`	Speed-optimized (optional refinement skip)	Fastest	Good	Speed priority
`gvedendo`	GVE with incremental dendrogram	Fast	Best	Dendrogram needs
`gveoptdendo`	GVEopt with incremental dendrogram	Faster	Best	Dendrogram needs
`gvefast`	CSR buffer reuse (leiden.hxx style)	Fastest	Best	Large graphs
`gverabbit`	GVE-Rabbit hybrid (limited iterations)	Fastest	Good	Very large graphs
`dfs`	Hierarchical DFS	Fast	Good	Tree structures
`bfs`	Level-first BFS	Fast	Good	Wide hierarchies
`hubsort`	Community + degree sort	Fast	Good	Power-law graphs
`fast`	Union-Find + Label Propagation	Very Fast	Moderate	Speed priority
`modularity`	Modularity optimization	Fast	Good	Quality focus

Key Recommendations:

Best overall: gveopt2 — CSR-based aggregation, fastest + best quality
Unknown graphs: gveadaptive:dynamic — adjusts resolution per-pass
Speed priority: gveturbo — optional refinement skip
High resolution (1.0-2.0) creates more communities that fit better in cache — optimizing for locality, not sociological accuracy

See Command-Line-Reference#leidencsr-17 for resolution mode syntax.

VIBE: Unified Reordering Framework

VIBE (Vertex Indexing for Better Efficiency) provides a unified interface for graph reordering with two main algorithms (vibe Leiden-based, vibe:rabbit RabbitOrder-based) and configurable ordering strategies.

# Format: -o 17:vibe[:algorithm][:ordering][:aggregation][:resolution_mode]
./bench/bin/pr -f graph.mtx -s -o 17:vibe -n 3         # Leiden-based (default)
./bench/bin/pr -f graph.mtx -s -o 17:vibe:conn -n 3    # Connectivity BFS ordering (default strategy)
./bench/bin/pr -f graph.mtx -s -o 17:vibe:hrab -n 3    # Hybrid Leiden+RabbitOrder (best locality)
./bench/bin/pr -f graph.mtx -s -o 17:vibe:rabbit -n 3  # RabbitOrder-based (single-pass)
./bench/bin/pr -f graph.mtx -s -o 17:vibe:dynamic -n 3 # Dynamic resolution (adjusted per-pass)
./bench/bin/pr -f graph.mtx -s -o 17:vibe:0.75 -n 3    # Fixed resolution

Key ordering strategies: vibe (hierarchical), vibe:dfs/bfs (dendrogram traversal), vibe:dbg/corder (within communities), vibe:conn (connectivity BFS, default), vibe:hrab (hybrid Leiden+RabbitOrder — best for web/geometric graphs).

See Command-Line-Reference#leidencsr-17 for full option reference and Community-Detection for algorithm details.

Algorithm Selection Guide

By Graph Type

Graph Type	Recommended	Alternatives
Social Networks	LeidenCSR (17:gveopt2)	LeidenCSR (17:gveadaptive)
Web Graphs	VIBE (17:vibe:hrab)	LeidenCSR (17:gveopt2)
Road Networks	ORIGINAL (0), RCM (11)	LeidenCSR (17:gveadaptive)
Citation Networks	LeidenCSR (17:gve)	LeidenOrder (15)
Random Geometric	VIBE (17:vibe:hrab)	LeidenCSR (17:gveopt2)
Unknown	LeidenCSR (17:gveadaptive)	AdaptiveOrder (14)

By Graph Size

Size	Nodes	Recommended
Small	< 100K	Any (try several)
Medium	100K - 1M	LeidenCSR (17:gveopt2)
Large	1M - 100M	LeidenCSR (17:gveopt2), LeidenCSR (17:gveturbo)
Very Large	> 100M	LeidenCSR (17:gveturbo), HUBCLUSTERDBG (7)

Quick Decision Tree

Is your graph modular (has communities)?
├── Yes → Is it very large (>10M vertices)?
│         ├── Yes → LeidenCSR (17:fast) for speed
│         │         LeidenCSR (17:gve) for quality
│         └── No → LeidenCSR (17) or (17:gve) - best quality
└── No/Unknown → Is it a power-law graph?
              ├── Yes → HUBCLUSTERDBG (7)
              └── No → Try AdaptiveOrder (14)

Performance Comparison Example

Running PageRank on a social network (1M vertices, 10M edges):

Algorithm	Time	Speedup
ORIGINAL (0)	1.00s	1.00x
RANDOM (1)	1.45s	0.69x
HUBSORT (3)	0.85s	1.18x
DBG (5)	0.80s	1.25x
HUBCLUSTERDBG (7)	0.72s	1.39x
RabbitOrder (8)	0.68s	1.47x
LeidenOrder (15)	0.65s	1.54x
LeidenCSR (17:gve)	0.55s	1.82x

Next Steps

Running-Benchmarks - How to run experiments
AdaptiveOrder-ML - Deep dive into ML-based selection
Adding-New-Algorithms - Implement your own algorithm

← Back to Home

Uh oh!

Reordering Algorithms

Graph Reordering Algorithms

Why Reorder Graphs?

Algorithm Categories

Basic Algorithms (0-2)

0. ORIGINAL

1. RANDOM

2. SORT

Hub-Based Algorithms (3-4)

3. HUBSORT

4. HUBCLUSTER

DBG-Based Algorithms (5-7)

5. DBG

6. HUBSORTDBG

7. HUBCLUSTERDBG ⭐ (Recommended for power-law)

Edge Case Handling (Hub-Based Algorithms)

Community & Classic Algorithms (8-11)

8. RABBITORDER

9. GORDER

10. CORDER

11. RCM

Advanced Hybrid Algorithms (12-14)

12. GraphBrewOrder

13. MAP

14. AdaptiveOrder ⭐ (ML-powered)

Leiden Variants (15-17)

15. LeidenOrder (Baseline Reference)

16. LeidenDendrogram ⚠️ (Deprecated)

17. LeidenCSR ⭐ (Fastest, Best Quality)

VIBE: Unified Reordering Framework

Algorithm Selection Guide

By Graph Type

By Graph Size

Quick Decision Tree

Performance Comparison Example

Next Steps

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally