STRATA

Key Results (Facebook, n=4,039)

• GPU-PerSrc-BFS (BG1): 0.017s — 122× over SciPy, 920× over NetworkX
• DAWN-SOVM (BG2): 0.019s — frontier-driven BFS (DAWN, ICS 2024)
• STRATA-CUDA (TG2): 0.031s — 67× over SciPy (guard+CAS kernel)
• STRATA-SpMM-Cython (TC1): 1.013s — 2.0× over SciPy (CPU best)
• All 12 methods produce identical distance matrices (verified element-wise)

Why STRATA?

Real-world networks are overwhelmingly small-world: Facebook's 721 million users are connected by an average distance of just 4.74 hops. STRATA provides the fastest matrix-algebraic APSP on CPU (2.0× over SciPy C BFS) and competitive GPU methods, while uniquely supporting k-hop constrained queries, dynamic edge insertion/deletion, simultaneous shortest-path count (σ) computation, and matrix-algebraic Betweenness Centrality (Matrix Brandes).

Tier 1  BG1/BG2/TG2  (0.003–0.031s)  GPU per-source BFS / CUDA direct expand
Tier 2  TG1          (0.006–0.267s)  GPU DAWNiBFS bit-compressed STRATA
Tier 3  TC1/BC2      (0.16–2.07s)   CPU SpMM+Cython / C BFS
Tier 4  TC2/TC3      (0.31–3.64s)   CPU dense BLAS / GraphBLAS
Tier 5  BC1–BC5      (0.40–15.9s)   Python BFS / edge-wise / GraphBLAS BFS

Key Findings

• TG2 Memory Cliff: At n=20,000, TG2 explodes to 12.8s. Its dense buffers require 16n² = 6.4GB, exceeding GPU VRAM capacity and causing massive swap overhead.
• TG1 Stable Scaling: Bit-compression reduces memory to 4.25n² (75% reduction). Runs at 0.805s at n=20,000 — stable and predictable.
• BG1/BG2 Dominance: 4n² memory, single kernel launch per source — consistently fastest across all scales.
• TG1 vs BG1: 2.7× gap at n=20K reflects STRATA's structural overhead (per-hop sync, atomicOr, batch management).

STRATA GPU Optimization Path (BA n=20,000)

At Facebook scale (n=4,039), TG2 (0.031s) beats TG1 (0.267s). But at n=20,000, TG2 hits the memory cliff (12.8s) while TG1 remains stable (0.81s). This confirms that STRATA's dense buffers impose a scaling ceiling that bit-compression or framework removal can overcome.

Discovery: Matrix Multiply Encodes σ(s,t)

In STRATA's matrix product A · C^(k-1), the integer values before Heaviside binarization exactly encode the number of shortest paths σ(s,t). This follows from the Brandes (2001) recurrence:

σ(i,j) = ∑ { σ(u,j) : u ∈ N(i) ∧ d(u,j) = d(i,j) - 1 }

STRATA's frontier pruning (F mask) ensures that only newly discovered pairs retain values, which is exactly "count shortest paths only." By simply removing the Heaviside step, STRATA simultaneously computes both D (distances) and σ (shortest-path counts) in a single forward pass.

σ(s,t) Computation: STRATA vs BFS

STRATA σ and BFS σ are exactly identical on all graphs (np.allclose verified). The 8.5–34× speedup comes from replacing n Python loops with d BLAS calls — same O(nm) complexity, better work organization.

Matrix Brandes: Betweenness Centrality

The σ discovery enables Matrix Brandes — expressing both the forward (σ) and backward (δ) phases of Brandes' algorithm as matrix multiplications. This reorganizes n per-source BFS+backpropagation into d hop-level BLAS calls.

Implementations

Betweenness Centrality Performance

TB2 vs igraph C: 2.4–3.6× faster across all graphs. The speedup comes from (1) hop-level fused pruning that skips already-visited pairs, and (2) OpenMP parallelization that hop-level organization naturally enables. Both approaches share O(nm) asymptotic complexity.

Edge Insertion: O(n²) Closed-Form Update

When undirected edge {a,b} is added:

D'[i,j] = min(D[i,j], D[i,a] + 1 + D[b,j], D[i,b] + 1 + D[a,j])

Only 0.008% of pairs are affected per insertion. NumPy vectorization (CPU) runs in ~0.155s, CuPy (GPU) in ~0.035s (4.4× speedup), yielding 22–33× speedup over full recomputation.

Edge Deletion: Level-Based Parent Replacement

Edge deletion is harder — distances can only increase. The proposed algorithm processes levels bottom-up:

1. Phase 1 (Identify): For each affected pair (s,t) at level k, check if an alternative parent exists among neighbors at level k-1.
2. Phase 2 (Propagate): Orphaned nodes cascade upward — their children may also lose shortest paths.
3. Early Termination: In small-world graphs, cascade dies out quickly due to abundant alternative paths.

Deletion Performance (Facebook n=4,039)

CPU DLevel Optimization History

Fully Dynamic Framework

Combining insertion and deletion enables a fully dynamic APSP update framework:

• Insertion: O(n²) closed-form, vectorizable
• Deletion: Level-based parent replacement with early termination
• Method-agnostic: Works with any APSP method that produces D and A

Related work: Even–Shiloach (1981) handles single-source decremental in O(m·n). Ramalingam–Reps (1996) updates affected vertices only. Demetrescu–Italiano (2004) achieves amortized O(n² log³ n) fully dynamic APSP. STRATA's framework is orthogonal to these — it operates on the distance matrix level, independent of the APSP method used.

1. CPU: Fastest Matrix-Algebraic APSP

STRATA-SpMM-Cython (TC1) is the fastest CPU method across all 6 graph topologies, outperforming SciPy's native C BFS by up to 2.0×. The key is Cython fused pruning — collapsing three sparse operations (booleanize → prune → footprint update) into a single C pass over COO entries.

2. GPU: SpMM Elimination via Direct CSR Expansion

STRATA-CUDA (TG2) replaces cuSPARSE SpMM with a custom CUDA kernel that directly traverses CSR neighbors, eliminating three SpMM bottlenecks:

1. Redundant products — SpMM computes all matrix products including already-visited pairs
2. Intermediate matrices — SpMM output requires COO/CSR conversion overhead
3. Separate prune step — footprint check is fused into expansion (1-pass)

The footprint check uses a guard+CAS pattern: non-atomic read guard skips already-visited cells, then atomicCAS ensures race-free 0→1 transitions.

if (F[idx] == 0) {                      // non-atomic guard
    if (atomicCAS(&F[idx], 0, 1) == 0) { // atomic CAS
        int pos = atomicAdd(out_count, 1);
        out_row[pos] = i;
        out_col[pos] = k;
    }
}

3. Structural Insight: Optimization Converges to Per-Source BFS

Progressive removal of STRATA's matrix-algebraic overhead converges to per-source BFS. At small scale (n=4K), TG2 is competitive. At large scale (n=20K), the framework overhead dominates, and BG1 wins by 48.6×. This reveals that for full APSP, matrix-algebraic indirection costs (shared footprint → atomics, per-hop kernel launch) accumulate at scale.

4. STRATA's Unique Capabilities

While BG1 is fastest for full APSP, STRATA provides capabilities that per-source BFS cannot:

• k-hop constrained APSP — exact hop shells at each distance level
• σ(s,t) simultaneous computation — shortest-path counts from the same matrix multiply, 8.5–34× over sequential BFS
• Matrix Brandes — betweenness centrality via hop-level BLAS, TB2 is 2.4–3.6× faster than igraph C
• Dynamic edge insertion — O(n²) incremental update, 22–33× faster than full recomputation
• Dynamic edge deletion — level-based parent replacement with early termination, ~130× optimized
• Algebraic analysis — matrix-based framework for theoretical convergence proofs

Algorithm Selection Guide

Honest Assessment

STRATA's APSP performance on GPU cannot beat per-source BFS at scale. The matrix-algebraic framework introduces structural overhead (per-hop sync, atomics, batch management) that becomes dominant as n grows. TG2's memory cliff at n=20K is a hard scaling limit.

However, STRATA's real value lies in its algebraic generality: the same matrix multiply that computes distances also yields σ(s,t), enabling Matrix Brandes (TB2) to outperform igraph C by 2.4–3.6×. The framework also naturally supports dynamic updates and k-hop queries — capabilities absent from per-source BFS.