Technical Summary: FastAlign - A Scalable Optimal Transport Algorithm for Network Alignment

Problem Statement

Network alignment aims to identify node correspondences across different networks, a critical task for applications such as social network analysis, fraud detection, and knowledge graph integration. While Optimal Transport (OT)-based methods currently achieve state-of-the-art (SOTA) accuracy by optimizing a transport objective that combines node similarity, structural consistency, and anchor supervision, they suffer from severe scalability limitations. Existing OT approaches repeatedly construct and update dense cross-network cost and alignment matrices over multiple iterations. This process results in high computational complexity ($O(n^3)$) and memory traffic ($O(n^2)$), making them impractical for large-scale or dynamic networks. Conversely, faster consistency-based or embedding-based methods often sacrifice accuracy by failing to capture global graph structures or incurring high runtime costs from deep representation learning.

Methodology: FastAlign

The authors present FastAlign, a scalable, sparsity-aware framework designed to accelerate OT-based network alignment without altering the underlying alignment model or compromising accuracy. Instead of proposing a new objective function, FastAlign reinterprets the standard OT formulation as a sequence of recurring mixed sparse-dense linear algebra operations. This reinterpretation allows the framework to exploit graph sparsity and optimize memory efficiency through four key technical strategies:

1. Linear-Algebraic Decomposition

FastAlign decomposes the OT alignment process into three distinct phases:

• Phase 1 (Precomputation): Computes alignment-independent cost components ($C_{node}$ and $C_{anc}$) and precomputes intra-network dissimilarity matrices. This involves normalizing adjacency matrices and generating positional encodings relative to anchor pairs.
• Phase 2 (Cost Update): Computes alignment-dependent cost components ($C_{edge}$ and $C_{nbr}$) based on the current soft alignment matrix $S$. These are calculated via triple products involving sparse adjacency matrices and the dense alignment matrix.
• Phase 3 (Solver): Solves for the updated alignment matrix $S$ using the Sinkhorn algorithm on the assembled cost matrix.

2. Sparsity-Aware Computations

Recognizing that real-world networks are sparse, FastAlign replaces all dense matrix computations involving graph structures with sparse kernels.

• Complexity Reduction: Operations such as positional encoding propagation and cost term updates are cast as Sparse Matrix-Dense Matrix Multiplications (SpMM). This reduces the asymptotic complexity of dominant operations from $O(n^3)$ to $O(nnz \cdot n)$, where $nnz$ is the number of non-zero edges.
• Memory Efficiency: The framework utilizes sparse matrix representations to scale graph storage from $O(n^2)$ to $O(nnz)$. Additionally, it reduces numerical precision from double to single precision where accuracy is not compromised, further lowering memory footprint.

3. Custom SpMM for Wide Dense Matrices

A critical bottleneck identified in OT alignment is the multiplication of a sparse adjacency matrix by a "wide" dense matrix (where the number of columns is comparable to or larger than the number of rows). Standard SpMM libraries (e.g., Intel MKL) are optimized for "tall-skinny" dense matrices and perform poorly here due to poor cache residency.

• Solution: FastAlign introduces a custom SpMM kernel using a column-blocking model. It partitions the wide dense matrix into narrow blocks that fit into the L2/L3 cache. This ensures that dense rows are reused across multiple non-zero entries of the sparse matrix, converting a memory-bound stream into a cache-resident reuse pattern.

4. Domain-Specific Kernel Fusion

To mitigate memory traffic caused by materializing large intermediate matrices ($n_1 \times n_2$), FastAlign fuses chains of memory-bound operations:

• Cost Assembly: The assembly of the total cost matrix (combining $C_{node}$, $C_{edge}$, $C_{nbr}$, and $C_{anc}$) is fused into a single pass that loads, scales, and writes values without creating intermediate dense matrices.
• Sinkhorn Updates: The log-sum-exp reductions required for updating dual vectors in the Sinkhorn algorithm are fused. Element-wise shifts, exponentials, and reductions are performed in a single streaming pass, eliminating the need to materialize full intermediate matrices.

5. GPU-Aware Optimizations

The GPU implementation leverages the above optimizations with specific hardware considerations:

• Data Residency: All graphs, cost matrices, and alignment matrices remain resident on the GPU device to minimize host-device transfers.
• Parallelism: Independent kernels for separate graphs are executed on parallel CUDA streams.
• Plan Reuse: SpMM plans are pre-computed once and reused across iterations to amortize initialization overhead.
• Tiled Transpose: A tiled transpose kernel with shared memory staging is used to facilitate efficient column reductions for the Sinkhorn solver.

Key Contributions

1. FastAlign Framework: A scalable, sparsity-aware framework for OT-based network alignment that preserves the original OT formulation while significantly improving runtime and memory efficiency.
2. Computational Reinterpretation: A novel decomposition of OT-based alignment into mixed sparse-dense operations, exposing optimization pathways hidden in standard formulations.
3. Algorithmic Innovations: Development of sparsity-aware graph computations, including a custom SpMM kernel for wide dense matrices and the fusion of adjacent memory-bound operations.
4. Empirical Validation: Extensive experiments demonstrating that FastAlign achieves SOTA alignment quality while substantially reducing end-to-end runtime.

Results

The authors evaluated FastAlign on a range of real-world (e.g., ACM-DBLP, PPI, DBP15K) and synthetic datasets against six SOTA baselines (including FINAL, BRIGHT, NetTrans, JOENA, PARROT, and SLOTAlign).

• Accuracy: FastAlign achieves alignment quality (measured by Hits@10 and Mean Reciprocal Rank) comparable to or better than SOTA OT-based methods, confirming that the optimizations do not degrade the alignment objective.
• Runtime Speedup:
  • CPU: FastAlign achieves a 3.89×–9.45× speedup over the fastest OT baseline (PARROT) and up to 193.90× over slower baselines.
  • GPU: FastAlign achieves a 2.24×–32.54× speedup over PARROT and up to 1321.85× over other baselines.
• Scalability: FastAlign scales efficiently to graphs with up to 110,000 nodes on CPU and 50,000 nodes on GPU. In contrast, most baselines run out of memory or time out on significantly smaller graphs (e.g., 30,000 nodes).
• Ablation Studies: The study confirms that all components contribute to performance. On GPU, sparsity-aware computation contributes 2.6×–4.4× speedup, while kernel fusion compounds these gains to reach the full 32.5× speedup.

Significance

The paper claims that FastAlign bridges the gap between accuracy and scalability in network alignment. By retaining the high-accuracy OT formulation but re-engineering its computational execution, FastAlign makes optimal transport-based alignment practical for large-scale graphs. The work demonstrates that significant performance gains can be achieved not by changing the mathematical model, but by optimizing the underlying linear algebra primitives (specifically SpMM and kernel fusion) to match the structural properties of network data (sparsity) and hardware constraints (memory bandwidth and cache). This approach allows for the deployment of high-precision alignment algorithms in scenarios previously limited by computational cost.