Scalable Optimal Transport Algorithm for Network Alignment Elaheh Hassani∗
Durga Mandarapu∗
Qi Yu
Texas A&M University TX, USA [email protected]
Lawrence Berkeley National Laboratory CA, USA [email protected]
University of Illinois at Urbana-Champaign IL, USA [email protected]
Hanghang Tong
Ariful Azad
University of Illinois at Urbana-Champaign IL, USA [email protected]
Texas A&M University TX, USA [email protected]
Network alignment identifies node correspondences across different networks and is a fundamental primitive in many data science applications, including social network analysis, fraud detection, and knowledge graph integration. However, state-of-the-art network alignment methods often achieve high accuracy by repeatedly constructing and updating dense matrices, sacrificing scalability in the process. To address this scalability limitation without compromising alignment accuracy, we present FastAlign, a scalable, sparsityaware framework for optimal transport-based network alignment. Rather than introducing a new alignment model, FastAlign preserves the original OT formulation and reinterprets its computation as a set of recurring mixed sparse-dense operations. FastAlign combines sparsity-aware graph computation with domain-specific kernel fusion, including a custom SpMM kernel. Our results show that FastAlign achieves alignment quality comparable to state-ofthe-art OT-based methods while substantially reducing end-to-end runtime up to 3.89×–9.45× on CPU and 2.24×–32.54× on GPU. *
Code Availability: The source code, data, and other artifacts are available at https://github.com/elawh1/FastAlign.
1
INTRODUCTION
The goal of network alignment is to identify node correspondences between two networks. It is a fundamental primitive for integrating graph-structured data across sources in many applications, including social network analysis [1], fraud detection [6], and knowledge graphs [21]. For example, aligning users across social platforms supports cross-platform recommendations; matching entities across transaction networks helps detect suspicious activities; aligning entities across incomplete knowledge graphs enables the construction of unified knowledge bases. As modern networks grow in size and dynamic networks require repeated realignments, it is imperative that alignment algorithms be both accurate and fast. Existing network alignment methods exhibit a tradeoff between scalability and accuracy (Figure 1). Consistency-based methods use a fast linear transformation between two networks, although their accuracy suffers because they do not fully capture global structure [31]. Embedding-based methods improve accuracy by * These authors contributed equally.
0.8
MRR
arXiv:2607.11952v1 [cs.LG] 11 Jul 2026
ABSTRACT
0.6
0.4
FastAlign FINAL BRIGHT NetTrans JOENA PARROT SLOTAlign
104
105 Time (s)
106
Figure 1: MRR (accuracy) vs. runtime across network alignment methods on the ACM-DBLP networks. FINAL is consistency-based, BRIGHT and NetTrans are embeddingbased, while the rest are OT-based methods.
learning node representations, at the cost of higher runtime from deep representation learning [24, 33, 35]. Optimal transport (OT)based methods achieve state-of-the-art (SOTA) empirical accuracy by optimizing a transport objective that combines node similarity, structural consistency, neighborhood consistency, and anchor supervision [20, 28–30]. This accuracy comes with its own scalability limitation as OT-based methods repeatedly construct and update dense cross-network cost and alignment matrices over several iterations, making them expensive in both runtime and memory. To address this scalability bottleneck without sacrificing alignment accuracy, we present FastAlign, a scalable sparsity-aware framework for OT-based network alignment. Rather than introducing a new alignment model, FastAlign preserves the original OT formulation and reinterprets its computation as a set of recurring mixed sparse-dense operations. This reinterpretation exposes where graph sparsity can be exploited and where dense cross-network operations must be optimized for memory efficiency. FastAlign realizes this decomposition using sparsity-aware graph operations and memory-efficient kernel fusion to reduce memory traffic and avoid unnecessary intermediate materialization. As a result, FastAlign accelerates and scales OT-based network alignment, making it practical at large graph sizes. Building on this reinterpretation, FastAlign combines four optimizations. First, it uses sparsity-aware computations to replace all dense matrix computations involving graph structures. Second, it
Elaheh Hassani∗ , Durga Mandarapu∗ , Qi Yu, Hanghang Tong, and Ariful Azad
introduces a custom sparse-dense matrix multiplication (SpMM) algorithm for multiplying a sparse matrix by a wide dense matrix, as arises in OT-based alignment, unlike generic SpMM settings where the dense matrix is tall and skinny. Third, it uses domain-specific kernel fusion to combine chains of memory-bound operations to reduce intermediate materialization and memory traffic. Fourth, its GPU implementation keeps data resident on device and reuses dense matrices across stages to avoid unnecessary data movement and tiles kernels for optimized performance. We implement FastAlign on CPU and GPU and evaluate it on a range of real-world and synthetic network alignment datasets. Our results show that FastAlign achieves comparable alignment quality to SOTA OT-based methods while substantially reducing end-to-end runtime. In summary, this paper makes the following contributions: • We present FastAlign, a scalable sparsity-aware framework for OT-based network alignment that preserves the alignment accuracy while improving runtime and memory efficiency. • We provide a computational reinterpretation of OT-based network alignment using mixed sparse-dense operations. • We develop sparsity-aware graph computation, including a custom SpMM kernel and the fusion of adjacent memory-bound operations, to accelerate OT-based network alignment. • With extensive experiments, we demonstrate that FastAlign achieves 3.89×–9.45× speedup on CPU and 2.24×–32.54× speedup on GPU relative to SOTA network alignment algorithms.
2
BACKGROUND
Let G1 = (V1, E1, A1 ) and G2 = (V2, E2, A2 ) denote two networks, with |V1 | = 𝑛 1 , |V2 | = 𝑛 2 , and adjacency matrices A1 ∈ R𝑛1 ×𝑛1 and A2 ∈ R𝑛2 ×𝑛2 . Nodes optionally carry attributes encoded as X1 ∈R𝑛1 ×𝑑 and X2 ∈ R𝑛2 ×𝑑 . We are further given a set of anchor pairs L ⊆ V1 × V2 , where each pair denotes a known correspondence between the two networks. Network alignment computes a soft alignment matrix S ∈ R𝑛1 ×𝑛2 , where S𝑖 𝑗 scores likelihood of node 𝑖 ∈ V1 corresponding to node 𝑗 ∈ V2 . Figure 2 illustrates network alignment problem. Existing approaches can be categorized as consistency-based, embedding-based, or OT-based [32]. Of these, OT-based approaches consistently achieve SOTA performance [27], our algorithm builds on this paradigm. So, we detail OT-based methods in this section and defer the rest to Section 5.
2.1
Optimal transport for network alignment
Optimal transport (OT) maps one discrete distribution to another by minimizing a total transport cost, known as the Wasserstein distance [16]. OT-based network alignment treats the node sets V1 and V2 as discrete distributions with uniform mass vectors 𝝁 = 1 1 𝑛 1 1𝑛 1 and 𝝂 = 𝑛 2 1𝑛 2 . The soft alignment matrix S corresponds to the OT transport plan, whose entry S𝑖 𝑗 encodes the amount of mass routed from node 𝑖 ∈ V1 to node 𝑗 ∈ V2 and is interpreted as the strength of their correspondence. Given a cost matrix C ∈ R𝑛1 ×𝑛2 that encodes the penalty for aligning each pair of nodes, the optimal alignment is obtained by solving min
S∈Π (𝝁,𝝂 )
⟨S, C⟩ − 𝜀 𝐻 (S),
(1)
a b
c
2
1
b
2
c
3
3
d
4
G₁
G₂
(a) Input Attributed Networks. Node
a 1
4
G₁
G₂
(b) Output Alignment.
Edge
Anchor link
d
Node attr.
Alignment
Figure 2: Network alignment problem. Given two attributed networks G1 and G2 and a set of anchor links, network alignment seeks a correspondence of nodes across networks. where ⟨·⟩ denotes the Frobenius inner product, Π(𝝁, 𝝂) = {S ∈ R𝑛≥01 ×𝑛2 : S1 = 𝝁, S⊤ 1 = 𝝂 } is the set of feasible soft alignments, and 𝜀 > 0 controls the strength of the entropic regularizer 𝐻 (S) that makes the problem strictly convex and efficiently solvable by the Sinkhorn algorithm [5]. The objective in Eq. 1 is shaped by two design choices: how the cost matrix C is constructed and how the resulting optimization is solved. We discuss each in turn.
2.2
Decomposition of the Cost Matrix
The design of the cost matrix C is what most directly shapes alignment quality. A well-designed cost captures three consistency principles together with prior anchor knowledge [30]. Node consistency (Cnode ) requires matched nodes to have similar attributes and similar structural positions within their respective networks. Edge consistency (Cedge ) requires matched node pairs to preserve their connecting edges. Neighborhood consistency (Cnbr ) requires matched nodes to have matched neighborhoods, so that neighbors in one graph map to neighbors in the other. Finally, the cost should reflect prior anchor preferences (Canc ), biasing the alignment toward known correspondences [30]. The overall cost matrix combines these terms additively, where 𝜆𝑒 , 𝜆𝑛 , 𝜆𝑎 ≥ 0 weigh the contribution of each term: C = Cnode + 𝜆𝑒 Cedge + 𝜆𝑛 Cnbr + 𝜆𝑎 Canc
2.3
(2)
The OT solver
Given the current cost matrix C and the predefined marginal vectors 𝝁, 𝝂, the Sinkhorn algorithm computes the alignment matrix S by iteratively rescaling its rows and columns to satisfy the marginal constraints while keeping the alignment cost low. The algorithm maintains two dual vectors a and b and alternately updates them in the log domain (for numerical stability): 𝑎 𝑗 = 𝜀 log 𝜈 𝑗 − 𝜀 LSE 𝑖
𝑏𝑖 −C𝑖 𝑗 𝜀
,
𝑏𝑖 = 𝜀 log 𝜇𝑖 − 𝜀 LSE 𝑗
𝑎 𝑗 −C𝑖 𝑗 𝜀
(3)
where LSE is the log-sum-exp reduction. On convergence, the alignment matrix is recovered as 𝑎 𝑗 + 𝑏𝑖 − C𝑖 𝑗 S𝑖 𝑗 = exp . (4) 𝜀 Eq. 4 yields the optimal alignment for the current C. Because some components of C themselves depend on S, the cost is then updated
Scalable Optimal Transport Algorithm for Network Alignment
using the newly computed alignment and the Sinkhorn solve is repeated. This alternation realizes the constrained proximal point method [22], which solves the problem as a sequence of fixed-cost OT subproblems with guaranteed convergence.
3
SCALING OT-BASED NETWORK ALIGNMENT
In this section, we introduce FastAlign, a scalable and fast network alignment framework. FastAlign achieves its speedups through a deliberate two-stage pipeline. First, it recasts OT-based alignment as a sequence of linear-algebraic operations on matrices with explicit shapes and sparsity. Second, it accelerates these kernels using custom sparse algorithms, kernel fusion, and hardware-mapped parallel implementations across CPUs and GPUs. This two-stage framework is necessary because the initial linear-algebraic decomposition exposes optimization pathways that are usually hidden by conventional OT formulations described in Section 2.
3.1
Foundation of FastAlign: Linear-algebraic Decomposition of Network Alignment
To decompose the OT-based algorithm in linear-algebraic form, we first observe that the computations described in Section 2 can be organized in three phases: (a) Phase 1 normalizes the adjacency matrices and computes the alignment-independent cost components Cnode and Canc ; (b) Phase 2 computes the alignment-dependent components Cedge and Cnbr ; and (c) Phase 3 invokes an OT solver to produce the alignment from the current cost matrix. These three phases of FastAlign are described in Algorithm 1 and Figure 3. Algorithm 1 takes two networks with node features and a set of anchor alignments and returns the alignment matrix S. After normalizing the adjacency matrices into Ā1, Ā2 (Line 1) and representing the anchors as one-hot encodings R1(0) ∈ R𝑛1 × | L | and R2(0) ∈ R𝑛2 × | L | , the algorithm proceeds in three phases: Phase 1: Computing Cnode (line 3-5). The node-consistency cost is built in three steps. First, repeated multiplication (1 − 𝛽) Ā𝑖 R𝑖 + 𝛽 R𝑖(0) produces a personalized-PageRank-style positional encoding of each node with respect to the anchor set; the 𝑙-th column of R𝑖 encodes the position of every node relative to the 𝑙-th anchor (Line 3). Second, Line 4 forms the initial Cnode from these encodings via two matrix multiplications. Finally, the cost is iteratively propagated across networks via the triple product Ā1 Cnode Ā2 , yielding the final Cnode that remains fixed for the rest of the algorithm. Computing Cnode thus reduces to six matrix multiplications of distinct shapes: some involve sparse operands, some are repeated, and some occur in tandem with others. We exploit these patterns in Section 3.4. Phase 1: Computing Canc (line 6). The anchor-preference cost encodes prior supervision directly from the known correspondences. OneHot(L) places a one at each anchor pair (𝑖, 𝑗) ∈ L and zero elsewhere. Each entry of Canc is ≈ 0 on anchor pairs and − log(𝜀) otherwise, biasing transport toward known correspondences. Phase 2: Computing Cedge (line 7 and 10). The edge-consistency cost is built in two steps. First, we form intra-network dissimilarity matrices that capture how neighbors within each network relate to one another with respect to the anchor set: C1 = (R1 R1⊤ ) ⊙ Ā1 and analogously for C2 (Line 7). This triple product, called sampled
Algorithm 1 FastAlign: A Linear Algebraic View of OT-Based Network Alignment Input: Graphs G1, G2 ; attributes X1, X2 ; anchors L Output: Alignment matrix S 1: Ā1 ← Rownormalized(G1 ), Ā2 ← Rownormalized(G2 ) (0) (0) 2: R1 ← OneHot(L [0]), R2 ← OneHot(L [1]) // Phase 1: precompute S-independent quantities (0) 3: Perform 𝑘 iterations: R𝑖 ← (1 − 𝛽) Ā𝑖 R𝑖 + 𝛽 R𝑖 for 𝑖 ∈ {1, 2} ⊤ ⊤ 4: Cnode ← 𝛼 𝑒 −R1 R2 + (1 − 𝛼) 𝑒 −X1 X2 5: Perform 𝑘 iterations: Cnode ← Ā1 Cnode Ā2 6: Canc ← − log(𝜀 + OneHot(L)) 7: C1 ← (R1 R1⊤ ) ⊙ Ā1 , C2 ← (R2 R2⊤ ) ⊙ Ā𝑇2 8: Initialize S 9: repeat // Phase 2: update S-dependent costs 10: Cedge ← C1 SC⊤ 2 11: Cnbr ← − log Ā⊤ 1 SĀ2 12: C ← Cnode + 𝜆𝑒 Cedge + 𝜆𝑛 Cnbr + 𝜆𝑎 Canc // Phase 3: solve for S 13: Repeat 𝑘 times: 14: a ← SoftMin(C, b) 15: b ← SoftMin(C⊤, a) 16: S ← exp (1a⊤ + b1⊤ − C)/𝜖 17: until S converges 18: function SoftMin(C, v) 19: return −𝜖 log (exp(−(C − v1⊤ )/𝜖)) ⊤ 1
dense–dense matrix multiplication (SDDMM), is less expensive than a full dense product because only the entries selected by Ā1 are computed. Since C1 and C2 do not depend on S, they are precomputed in Phase 1. Cedge is computed by transporting C1 and C2 across the networks via the triple product C1 SC⊤ 2 (Line 10). Phase 2: Computing Cnbr (line 11). The neighborhood-consistency cost ensures that for any node pair (𝑖, 𝑗), the alignment score S𝑖 𝑗 is consistent with the alignment scores of 𝑖’s and 𝑗’s neighbors. It is computed by propagating the current alignment across the two networks via the triple product Cnbr = Ā⊤ 1 SĀ2 . Phase 2: Computing C (line 12). After each cost term is computed, we add the matrices to obtain the final cost matrix for the current iteration. We also add the proximal term 𝜆𝑝 log(𝑆), which couples the cost to the current alignment. Phase 3: Computing S (line 13-17). We solve the entropic OT of Section 2.3 by Sinkhorn (Line 13-15). First, the dual vectors a and b are refined by k alternating SoftMin updates. Each SoftMin is a log-sum-exp reduction over the cost matrix: a reduces C over its rows (Line 14), and b reduces C over its columns, equivalently a row reduction over C𝑇 (Line 15). Second, the alignment is updated from the dual vectors a and b (Line 16), where the outer products 1a⊤ and b1⊤ broadcast the dual vectors into 𝑛 1 × 𝑛 2 matrices, combined with C, and exponentiated element-wise to produce S.
3.2
Optimization opportunities
The decomposition in Algorithm 1 exposes the computation as a pattern of recurring dense and sparse linear-algebra operations rather than as isolated steps, which lets us reason about costs and
Elaheh Hassani∗ , Durga Mandarapu∗ , Qi Yu, Hanghang Tong, and Ariful Azad
INPUT
PHASE 1
PHASE 2
PHASE 3
Precompute fixed costs
Build cost matrix
Solve S using Sinkhorn
fixed costs a b
1 c
2
3
d
4
G₁
G₂
Cnode Anchor preference cost
Cedge
a
1
Sinkhorn
b
2
Update Dual vectors
c
3
+
Cross-network dissimilarity
Cost matrix
Cnbr
OUTPUT
Update S
d
4
G₁
G₂
×K
Recompute with S
Canc
Updated S ×T
Figure 3: Overview of OT-based network alignment. Given two attributed networks G1 and G2 and two anchor links (dashed lines). Phase 1 precomputes the fixed cost components, C𝑛𝑜𝑑𝑒 and C𝑎𝑛𝑐 . Phase 2 computes two S-dependent cost terms: C𝑒𝑑𝑔𝑒 and C𝑛𝑏𝑟 , from the current alignment matrix S, then adds them to the fixed costs to form the Cost matrix. Phase 3 runs the Sinkhorn algorithm for 𝐾 iterations to optimize the dual vectors, which then update S. The updated S feeds back into the S-dependent cost terms, and Phase 2-3 repeats up to 𝑇 outer iterations until S converges into the final node alignment. bottlenecks directly. Assuming 𝑛 1 ≈ 𝑛 2 ≈ 𝑛 [28, 30], Phase 1 incurs O (𝑛 3 ) work across multiple matrix multiplications; Phase 2 updates the S-dependent terms in O (𝑛 3 ) and produces a dense O (𝑛 2 ) matrix in each outer iteration; Phase 3 runs Sinkhorn at O (𝑛 2 ) per iteration. Memory traffic is a second bottleneck: the dense O (𝑛 2 ) cost and alignment matrices are streamed repeatedly, rescaled row- and column-wise each Sinkhorn iteration, and re-accessed during every cost update. Profiling PARROT, a representative OT-based method, confirms that runtime is spread across all three phases: fixed-cost computation 40–69%, cost update 15–36%, and Sinkhorn 14–23%. Because the three phases share a small set of recurring primitives, accelerating those primitives accelerates the pipeline endto-end. But the primitives are diverse: the algorithm calls more than ten distinct matrix multiplications differing in operand sparsity, shape, and composition with adjacent operations. Cnode requires dense, sparse, and sparse-dense-sparse triple products; Cedge requires dense-dense-sparse (SDDMM) and sparse-dense-sparse triple products; the OT solver requires matrix–vector products interleaved with elementwise operations. Off-the-shelf libraries such as Intel MKL deliver suboptimal performance across this mix. We identify three opportunities for closing the gap: (a) develop efficient sparse computations to reduce the runtime, (b) fuse a sequence of steps into a combined operation to reduce memory traffic, and (c) develop hardware-mapped parallelization for modern GPUs.
3.3
Sparsity-aware Network Alignment
Since real-world networks are sparse, representing graphs as sparse matrices exposes asymptotically more efficient computations that typically translate into faster runtimes in practice. FastAlign represents the input graphs as sparse matrices and replaces every dense graph computation with a sparse kernel. The positional encoding (Line 3) and C𝑛𝑜𝑑𝑒 propagation (Line 5) multiply a sparse adjacency matrix with a dense matrix, which we cast as an SpMM. Similarly, the sparse-dense-sparse triple product (Line 5) is factored as two successive SpMMs. The same pattern recurs in the S-dependent costs C𝑒𝑑𝑔𝑒 (Line 10) and 𝐶𝑛𝑏𝑟 (Line 11), which are also computed as two SpMMs. We compute the intra-network dissimilarities (Line 7)
using SDDMM that evaluates only the masked entries rather than materializing the full dense product. Computational Efficiency. These sparse substitutions change the asymptotic cost of the dominant operations. In the propagation and transport triple products (Lines 5, 10, 11), replacing GEMM with SpMM reduces computational complexity from O (𝑛 3 ) to O (nnz ·𝑛), where 𝑛 is the number of nodes and nnz is the number of nonzeros (edges) in the sparse matrix. For the intra-network dissimilarity (Line 7), each of the nnz masked entries is an inner product of length |L|, reducing the cost from O (𝑛 2 · |L|) to O (nnz · |L|). Memory Reduction. Utilizing sparse matrix representations scales down graph storage overhead from O (𝑛 2 ) to O (nnz). We further observe that the alignment matrix is often sparse in practice because each node in one network typically has high alignment probability with only a small subset of nodes in the other network. [20, 26] Thus, reducing the numerical precision from double to single precision does not noticeably affect alignment accuracy. This also reduces the memory footprint and enables FastAlign to scale to larger graphs.
3.4
Custom SpMM for wide dense cost matrix
Several of the most expensive steps in Algorithm 1 share a common matrix-product shape. A dense cost matrix is multiplied on both sides by a sparse adjacency-structured matrix. An example is the Cnode propagation Ā1 C Ā⊤ 2 (Line 5), where C is dense matrix of size 𝑛 1 × 𝑛 2 and the outer matrices are sparse matrices Ā1 ∈ R𝑛1 ×𝑛1 and Ā2 ∈ R𝑛2 ×𝑛2 . The same sparse-dense-sparse structure recurs in the edge and neighborhood consistency terms Cedge = C1 SC⊤ 2 (Line 10) and Cnbr = Ā⊤ 1 SĀ2 (Line 11); there the outer factors C1 , C2 are also sparse, with the same sparsity pattern as the adjacency matrix. Computing each term requires two SpMMs that share the same structure, a sparse 𝑛 × 𝑛 matrix multiplied by a dense matrix with Θ(𝑛) columns. We call this primitive SpMM on a wide dense matrix. Here wide means not tall-skinny: the number of columns in the dense matrix is comparable to or larger than its rows. In our algorithm, this column count grows with the graph. Even in the position-aware encoding (Line 3), which is another SpMM, R𝑘 has width ≈ 0.2 𝑛, and it grows without bound as the graphs grow. This is the opposite of the regime that off-the-shelf libraries such
Scalable Optimal Transport Algorithm for Network Alignment
as Intel MKL is optimized for, where the dense matrix has a small, often fixed column dimension 𝑑. To see why that mismatch hurts us, we first review how a generic SpMM is computed and why it is efficient in its intended regime. Why generic SpMM underperforms. A general SpMM [9, 17, 25] computes M = AB where A is the sparse 𝑛 × 𝑛 matrix, and B and M are dense 𝑛 × 𝑑 matrices, where 𝑑 ≪ 𝑛. This kernel computes one Í output row at a time M[𝑖, :] = 𝑘 : 𝐴𝑖𝑘 ≠0 𝐴𝑖𝑘 B[𝑘, :], where 𝑘 runs only over the columns in which row 𝑖 of A has a nonzero, 𝐴𝑖𝑘 is that nonzero value, B[𝑘, :] is the 𝑘-th row of the dense input matrix, and M[𝑖, :] is the output row being accumulated. These kernels are tuned for tall-skinny B (𝑑 ≪ 𝑛) where a row B[𝑘, :] is short, stays cache-resident, and is reused across every nonzero that references column 𝑘 of A. This setting is the most common application of SpMM when used in iterative solvers and graph neural networks. In FastAlign, B is wide, not tall-skinny. A row B[𝑘, :] is now 𝜃 (𝑛), so it may no longer stay cache-resident and cannot be reused across the nonzeros that reference column 𝑘 of A, which limits data reuse in FastAlign. In the worst case, each nonzero from the sparse matrix fetches its corresponding dense row from memory, giving O (nnz · 𝑛) memory traffic. Since SpMM is a memory-bound operation, the standard SpMM libraries (e.g., Intel MKL) hurt the performance of FastAlign. The fix: custom SpMM kernel. We design this kernel with a column blocking model to improve cache residency. We partition dense matrices B and M into 𝑄 = ⌈𝑛 2 /𝑏𝑐 ⌉ narrow blocks of 𝑏𝑐 contiguous columns and process one block at a time. To compute block 𝑞 of output, whose columns start at 𝑗𝑞 = (𝑞 − 1)𝑏𝑐 , we fill it Í one output row at a time: M[𝑖, 𝑗𝑞 : 𝑗𝑞 + 𝑏𝑐 ] = 𝑘 : A𝑖𝑘 ≠0 A𝑖𝑘 B[𝑘, 𝑗𝑞 : 𝑗𝑞 + 𝑏𝑐 ]. Since each memory access within each column block computation is limited to a narrow partition of dense matrix, the B partition needs to reside in cache, reduced to 𝑛 1 × 𝑏𝑐 instead of 𝑛 1 × 𝑛 2 that does not fit into L2/L3. This will increase cache hits when consecutive rows share similar columns of nonzeros. Figure 4 traces one block: To fill the 𝑏𝑐 output block M[𝑘, 𝑗𝑞 : 𝑗𝑞 + 𝑏𝑐 ], the kernel iterates over all rows of A accumulating the A𝑖𝑘 B[𝑘, 𝑗𝑞 : 𝑗𝑞 + 𝑏𝑐 ] for each nonzero. Since each memory access within a column-block computation is limited to a narrow partition of the dense matrix, the resident B partition shrinks to 𝑛 1 × 𝑏𝑐 , which fits into L2/L3, instead of the full 𝑛 1 × 𝑛 2 , which does not. Payoff. Blocking leaves the arithmetic and total access count unchanged at O (nnz · 𝑛). It changes which level of memory is accessed. By keeping each B block cache-resident, it reduces the DRAM traffic for reading B, converting memory-bound stream into a cache-resident reuse pattern. For a SpMM with the structure of our application, this improved cache reuse accelerates the SpMM computations throughout our model.
3.5
Domain-specific Kernel Fusion
According to Algorithm 1, the cost matrix C assembly (Line 12), and Sinkhorn dual vector update (Lines 14,15, Eq. 3) are written as compact algebraic expressions; however, a literal computation allocates and populates a 𝑛 1 ×𝑛 2 intermediate matrix: each log, scale, and add streams a full dense intermediate to memory and back. Since these matrices are large, the memory traffic dominates the computation even though every individual operation is cheap. We
A
B
n1
n1
n1
x n1
M
= bc
n2 Fetch n1 times
DRAM
bc=n2/Q
n2
Q blocks
Cache Read once
Cache-resident block
DRAM read
Output block
Figure 4: Column-blocked SpMM for one output block. To compute one 𝑏𝑐 block of M (blue), the corresponding block of B (green) is read from DRAM into cache once and reused across all rows of A.
merge each algebraic chain into a single path over the output/input matrices. We observed such chains that occur and fused them. Cost matrix C computation. Cost computation (Line 12) combines four dense terms by scaling, log, and addition: C ← Cnode + 𝜆𝑒 Cedge + 𝜆𝑛 Cnbr + 𝜆𝑎 Canc . Naively computing this results in materializing at least 6 separate dense 𝑛 1 × 𝑛 2 matrices. The fused kernel instead visits each entry (𝑖, 𝑗) once, loads the five contributing values, applies the scale/log/add, and writes C𝑖 𝑗 in one pass, without any intermediates. Sinkhorn dual updates. Each dual update is a log-sum-exp reduction over the cost matrix (Eq. 3): the row reduction that updates a and the column reduction that updates b. Evaluated naively, each update shifts, exponentiates, and reduces the cost matrix, then applies a log and a final shift which materializes a full 𝑛 1 × 𝑛 2 intermediate matrix at each step. We instead design a single fused kernel that applies element-wise shift and exponential inside the reduction, in one streaming pass with a max-shift for stability, so the 𝑛 1 ×𝑛 2 intermediate is not materialized. The same kernel serves both updates: applied to C to refresh a and to C𝑇 to refresh b.
3.6
GPU-aware Optimizations
The computational reformulation of FastAlign naturally maps to GPU architectures, as the performance-critical matrix operations reduce to sparse and dense linear algebra kernels. Our GPU implementation builds on the sparsity-aware formulation (Section 3.3) and domain-specific kernel fusion (Section 3.5) using cuSPARSE for sparse matrix operations and cuBLAS for dense linear algebra. Rather than using these libraries out of the box, we tune their performance by selecting memory layouts and SpMM algorithms to match the structure of each operation in the alignment pipeline. Minimizing latency. Unlike the CPU implementation, the GPU implementation must carefully minimize both device-side memory movement and host–device transfers to reduce latency. Cost computation involves sparse–dense–sparse matrix products, which we break down into two SpMM calls with transposing the intermediate dense matrices. As explicitly materializing transposed matrices is expensive, we use transpose views to avoid additional memory allocation. To minimize host–device communication, all graphs, cost matrices, and alignment matrices remain resident in GPU memory, while intermediate buffers are reused throughout the alignment.
Elaheh Hassani∗ , Durga Mandarapu∗ , Qi Yu, Hanghang Tong, and Ariful Azad
GPU-specific kernel fusion. The Sinkhorn dual updates assign one thread block per column and execute two streaming passes: the first reduces the column minimum using warp-level shuffles (__shfl_down_sync), while the second accumulates the shifted exponentials. The same kernel serves the column reduction for updating b by operating on a transpose view of C, produced by a tiled transpose kernel that stages 32 × 32 tiles in shared memory with +1 column padding to eliminate bank conflicts, achieving coalesced reads and writes in a single pass. Parallel streams and reusing SpMM plans. To improve GPU utilization, FastAlign issues independent kernels for separate graphs across parallel, non-blocking CUDA streams. For example, the rownormalization kernels of the two graph intra-distance matrices (Line 7 of Algorithm 1) run concurrently on separate streams rather than sequentially. Furthermore, standard cuSPARSE SpMM calls incur per-invocation overhead for planning, handle setup, and buffer allocation. Because these calls repeat within a loop, FastAlign pre-computes the plan once and reuses it across iterations. This amortizes the initialization overhead, ensuring subsequent calls incur only raw execution costs.
4
EVALUATION
We evaluate FastAlign to answer the following research questions: Q1 How accurate is FastAlign compared to SOTA network alignment algorithms? Q2 How does FastAlign accelerate alignment on real networks? Q3 How does FastAlign scale with increasing network size? Q4 How much does each of our techniques contribute to the overall speedups achieved by FastAlign?
4.1
Experimental Setup
For experiments, we use an AMD EPYC 7763 CPU with 64 cores and 512 GB of memory. For GPU experiments, we use an NVIDIA A100 GPU with 40 GB of memory and CUDA 12.8. All methods are evaluated in a semi-supervised setting, where 20% of the groundtruth node pairs are used as prior knowledge, i.e., anchor links. We report runtime and accuracy metrics averaged over five runs. Runtime measures the end-to-end alignment computation time after the input graphs are read, including all steps required to compute the final alignment matrix. In our experiments, FastAlign exhibits convergence behavior similar to the OT baseline, PARROT. 4.1.1 Metrics. We evaluate the effectiveness of FastAlign compared to the baselines using the following two accuracy metrics. For each test node 𝑥 ∈ 𝐺 1 , let 𝑥 ′ ∈ 𝐺 2 denote its ground-truth match. We rank all candidate nodes in 𝐺 2 by their alignment score with 𝑥. A prediction is counted as a hit at 𝐾 if 𝑥 ′ appears among the top-𝐾 ranked candidates. For a test set with 𝑛 node pairs, Hits@𝐾 = #hits@𝐾 . 𝑛 Mean Reciprocal Rank (MRR) is measured as the average inverse Í 1 rank of the ground-truth match: MRR = 𝑛1 (𝑥,𝑥 ′ ) ∈ Stest rank(𝑥,𝑥 ′) 4.1.2 Baselines. Following the benchmark study [27], we select six top-accuracy baselines that cover the three main categories of network alignment methods. FINAL [31] is consistency-based; BRIGHT [24] and NetTrans [35] are embedding-based; and JOENA [28], PARROT [30], and SLOTAlign [20] are OT-based. PARROT is the closest baseline to FastAlign, since our framework preserves the
Table 1: Dataset Characteristics Networks
nodes
edges
attributes
sparsity (%)
Coral Coral2
2,708 2,708
6,334 4,542
1,433 1,433
99.83 99.88
PPI1 PPI2
3,480 3,480
117,429 90,741
50 50
98.06 98.50
ACM DBLP
9,872 9,916
39,561 44,808
17 17
99.93 99.92
GGI1 GGI2
10,403 10,403
115,755 89,448
0 0
99.88 99.91
ArXiv1 ArXiv2
18,722 18,722
217,921 168,394
0 0
99.6 99.69
DBP15K_FR DBP15K_EN
19,661 19,993
105,997 115,722
300 300
99.84 99.83
same OT-based alignment formulation. We also evaluated NeXtAlign [33], but it timed out on most datasets and is omitted. 4.1.3 Datasets. Table 1 summarizes the real-world datasets we used to evaluate FastAlign against the baselines. For scalability experiments, we generated synthetic graphs using the Erdős–Rényi model with an average node degree of 10 [7].
4.2
Accuracy Results
Table 2 compares the Hits@10 and MRR of FastAlign against all baselines on the real-world datasets. We report GPU results in this table and observe similar accuracy trends on CPU. CPU accuracy results are omitted because several baselines time out on larger datasets, as discussed in the next Subsection. FastAlign and other OT-based methods achieve substantially higher accuracy than consistency-based and embedding-based methods. Compared with state-of-the-art OT-based baselines, FastAlign achieves nearly identical or better accuracy on most datasets, showing that its optimizations do not degrade alignment quality and preserve original OT alignment objective. We attribute the slightly lower accuracy on DBP15K to floating-point roundoff inconsistencies, especially from fused kernels as they change the order of numerical operations.
4.3
Performance Analysis
Figure 5 compares the runtime of FastAlign against all baselines on real-world datasets using CPU and GPU implementations, respectively. On CPU, missing bars indicate that the corresponding baseline timed out on that dataset, whereas on GPU, all baselines completed. FastAlign achieves a 3.89×–9.45× speedup on CPU and a 2.24×–32.54× speedup on GPU compared to PARROT, the fastest baseline. Across all baselines, the speedup ranges from 3.89× to 193.90× on CPU and from 2.24× to 1321.85× on GPU, with the largest speedups achieved over slow baselines. These significantly high speedups demonstrate the effectiveness of FastAlign’s computational reinterpretation and optimizations discussed in Section 3. In general, the speedups increase with dataset size. For datasets of similar size, the speedups follow the sparsity trend: higher sparsity leads to less data movement through memory
Scalable Optimal Transport Algorithm for Network Alignment
Table 2: Accuracy comparison with all baselines for real-world datasets on GPU (bold numbers denote the best accuracies). Dataset Cora PPI ACM-DBLP GGI ArXiv DBP15K Metrics Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR FINAL 0.899 0.832 0.003 0.003 0.798 0.515 0.632 0.338 0.720 0.401 0.001 0.001 BRIGHT 0.674 0.470 0.629 0.511 0.774 0.504 0.588 0.456 0.695 0.492 0.617 0.404 NetTrans 0.716 0.486 0.791 0.634 0.800 0.526 0.677 0.499 0.785 0.551 0.642 0.408 JOENA 1.000 0.997 0.986 0.970 0.871 0.695 0.923 0.849 0.925 0.807 0.984 0.976 PARROT 0.965 0.964 0.998 0.994 0.947 0.776 0.933 0.855 0.918 0.796 0.970 0.886 SLOTAlign 1.000 0.997 0.980 0.965 0.874 0.745 0.803 0.740 0.724 0.607 0.848 0.774 FastAlign 1.000 0.997 0.999 0.996 0.943 0.840 0.941 0.879 0.929 0.811 0.916 0.799
Figure 5: Runtime comparison of network alignment methods on real-world datasets on (a) CPU and (b) GPU architectures. Numbers on PARROT bar indicate speedups of FastAlign over PARROT. and therefore larger speedups. GPU speedups are higher than CPU speedups primarily because kernel fusion and GPU-specific optimizations have a stronger impact on GPU execution. In particular, kernel fusion improves data locality and reuse, reducing memory access latency and contributing to the superior performance of FastAlign on GPU.
4.4
Scalability Analysis
Figure 6a shows the runtime scalability comparison of FastAlign for synthetic datasets against the baselines that did not time out on graphs with 20K nodes. FastAlign scales more efficiently than all baselines, with speedups increasing as graph size grows — from 0.82× at 10K nodes to 9.41× at 110K nodes over the fastest baseline. The overall speedups are in the range 0.82× – 14.49×. FastAlign scales to graphs with up to 110K nodes, while all baselines except BRIGHT run out of memory at smaller graph sizes. The maximum problem size supported by FastAlign is determined by its peak memory usage during Sinkhorn optimization. The peak live state uses nine dense (𝑛 1 × 𝑛 2 ) matrices and two sparse graph matrices. Using single precision (Section 3.3), the dense matrices require (4 · 9 · 𝑛 1𝑛 2 = 36𝑛 1𝑛 2 ) bytes, which bounds the implementation to approximately 110K nodes on a CPU with 512GB memory. As long as they fit in memory, FastAlign aligns the networks. Figure 6b presents the scalability comparison on GPU using an NVIDIA A100 (80GB variant). FastAlign and BRIGHT scale to 50K-node graphs, while FINAL supports up to 35K nodes, PARROT, JOENA, and SLOTAlign up to 30K, and NetTrans only up to 10K. Although the y-axis is shown in log scale to accommodate the wide range of runtimes, the scalability trend on GPU mirrors the CPU results: FastAlign’s speedups increase with graph size. From 10K to 50K nodes, it achieves speedups in the range of 4.16×–86.88×
Figure 6: Scalability comparison of network alignment methods on (a) CPU and (b) GPU architectures as the number of nodes in the synthetic graph increases.
over BRIGHT, the fastest baseline. Across all baselines and graph sizes, the speedups are in the range of 4.16×–2525.88×.
4.5
Ablation studies
Figure 7 shows the runtime contribution of each FastAlign optimization: sparsity-aware computation, kernel fusion, and custom SpMM. The number on each bar reports the speedup of that artifact over PARROT. To isolate algorithmic gains from platform effects, we include a straightforward reimplementation of the baseline,
Elaheh Hassani∗ , Durga Mandarapu∗ , Qi Yu, Hanghang Tong, and Ariful Azad
Figure 7: Performance contribution of FastAlign’s optimizations to its overall runtime on (a) CPU and (b) GPU architectures for real-world networks. Numbers on bars indicate speedups relative to PARROT. PARROT in CPP and CUDA as an intermediate baseline. Both CPP and CUDA baselines are only marginally faster than the original PyTorch implementation of PARROT, with the speedups diminishing as graph size grows, confirming that naive reimplementations with a platform change yield no meaningful performance benefit. On smaller networks, we observe a modest speedup from framework conversion alone. However, on larger datasets with at least 10K nodes, the overhead of PyTorch over CPP/CUDA becomes negligible and the C++/CUDA baselines are no longer faster, confirming that FastAlign’s speedups are driven by its algorithmic optimizations rather than the platform change. On CPU, sparsity alone improves runtime by 0.8×–2.6×, and adding fusion compounds these gains to 2.2×–4.6×, with custom SpMM further increasing speedups to 2.9×–6.6×. On GPU, sparsity contributes 2.6×–4.4× to the speedup, and adding fusion brings the overall speedup to 2.2×–32.5×. Across both CPU and GPU, all optimizations contribute to performance, with fusion consistently compounding the benefits of sparsity.
5
RELATED WORK
In this section, we review the related work, which can be categorized into two groups: network alignment and optimal transport. 5.0.1 Network Alignment. Research on network alignment has largely developed along two directions: consistency-based and embedding-based approaches. The first direction is based on the idea that aligned nodes should have structurally and semantically similar positions, so that the connectivity and attributes of a node’s neighbors carry over from one network to the other. IsoRank [19] propagates pairwise similarities on the product graph, FINAL [31] extends this with attribute and edge consistency for attributed graphs, and BIG-ALIGN [10] recovers a near-permutation between adjacency matrices via a Frobenius objective. Computationally, these methods iterate over an O (𝑛 2 ) product or similarity space that dominates cost at scale, motivating coarsening-based designs like MOANA [34]. In terms of accuracy, however, they capture limited global graph geometry, and the consistency premise weakens when the two networks differ substantially [33]. The second learns node embeddings that encode each network’s topology while pulling anchor pairs together: IONE [11] models directional follower/followee context, REGAL [8] factorizes a crossnetwork similarity matrix, CrossMNA [4] fuses intra-/inter-/global features, and NetTrans [35], BRIGHT [24], and NeXtAlign [33] further improve robustness through learned transformations, restartbased positional features, and consistency-aware sampling, respectively. Computationally, the cost shifts to training: repeated gradient
updates over deep encoders, often with pair sampling, are expensive and lack convergence guarantees. In accuracy, they model crossnetwork relations only indirectly through anchor paths and are sensitive to sampling noise and embedding-space distortion [28, 33]. 5.0.2 Optimal Transport. Optimal transport (OT) has recently been applied to network alignment, representing each graph as a distribution over its nodes and seeking the minimum-cost transport between them [2]. Methods differ mainly in how the transport cost is defined. Early designs transport spectral node embeddings (EMD [13]) or represent graphs through filtered graph signals and Gaussian graph kernels (FGOT [12], GOT [15]), while later costs jointly encode node and edge correspondence via the Wasserstein and Gromov–Wasserstein (GW) distances [2, 23]. A prominent line aligns graphs through Gromov–Wasserstein structural discrepancy (S-GWL [23], GraphOTC [14]), while GOAT [18] accelerates it via the Sinkhorn algorithm. More recent work learns the cost instead of fixing it: SLOTAlign [20] encodes a GW objective with a parameterfree GNN, CombAlign [3] ensembles embedding- and OT-based alignments, and JOENA [28] jointly learns embeddings and transport. PARROT [30] builds random-walk topology and consistency regularization into the OT cost and solves it with a constrained proximal point method. While OT-based methods achieve higher accuracy, they remain the most computationally demanding category. Their cost stems from repeatedly updating dense O (𝑛 2 ) matrices, and while proximal solvers [28] reduce iteration counts, graph sparsity and sparselinear-algebra primitives remain underexploited. As a result, even the most scalable OT aligners are confined to moderate-sized graphs, a gap our work targets by retaining the accuracy of regularized OT while improving runtime and scalability through a computationoptimized algorithm.
6
CONCLUSION
In this paper, we scale OT-based network alignment to large graphs while preserving its accuracy. Instead of designing a new alignment model, we present FastAlign, which keeps the original OT formulation and treats its computation as a small set of recurring sparse-dense operations. FastAlign exploits graph sparsity to skip work over nonexistent edges, fuses memory-bound kernels to cut redundant memory traffic, adds a custom SpMM kernel for the wide dense matrices in OT alignment, and uses GPU-aware optimizations to reuse data on device. Experiments on real and synthetic datasets show that FastAlign matches the accuracy of SOTA OT-based methods while running up to 9.45× faster on CPU and up to 32.54× faster on GPU than the strongest OT baseline.
Scalable Optimal Transport Algorithm for Network Alignment
REFERENCES [1] Xuezhi Cao and Yong Yu. 2016. Joint user modeling across aligned heterogeneous sites. In Proceedings of the 10th ACM Conference on Recommender Systems. 83–90. [2] Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. 2020. Graph optimal transport for cross-domain alignment. In International Conference on Machine Learning. PMLR, 1542–1553. [3] Songyang Chen, Yu Liu, Lei Zou, Zexuan Wang, and Youfang Lin. 2025. CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment. IEEE Transactions on Knowledge and Data Engineering 38, 2 (2025), 956–968. [4] Xiaokai Chu, Xinxin Fan, Di Yao, Zhihua Zhu, Jianhui Huang, and Jingping Bi. 2019. Cross-network embedding for multi-network alignment. In The world wide web conference. 273–284. [5] Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26 (2013). [6] Boxin Du, Si Zhang, Yuchen Yan, and Hanghang Tong. 2021. New frontiers of multi-network mining: Recent developments and future trend. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 4038–4039. [7] Paul Erdős, Alfréd Rényi, et al. 1960. On the evolution of random graphs. Publications of the (1960). [8] Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. 2018. Regal: Representation learning-based graph alignment. In Proceedings of the 27th ACM international conference on information and knowledge management. 117–126. [9] Guyue Huang, Guohao Dai, Yu Wang, and Huazhong Yang. 2020. Ge-spmm: General-purpose sparse matrix-matrix multiplication on gpus for graph neural networks. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1–12. [10] Danai Koutra, Hanghang Tong, and David Lubensky. 2013. Big-align: Fast bipartite graph alignment. In 2013 IEEE 13th international conference on data mining. IEEE, 389–398. [11] Li Liu, William K Cheung, Xin Li, and Lejian Liao. 2016. Aligning users across social networks using network embedding.. In Ijcai, Vol. 16. 1774–80. [12] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. 2022. Fgot: Graph distances based on filters and optimal transport. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 7710–7718. [13] Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017. Matching node embeddings for graph similarity. In Proceedings of the AAAI conference on Artificial Intelligence, Vol. 31. [14] Kevin O’Connor, Bongsoo Yi, Kevin McGoff, and Andrew B Nobel. 2021. Graph optimal transport with transition couplings of random walks. arXiv e-prints (2021), arXiv–2106. [15] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. 2019. Got: an optimal transport framework for graph comparison. Advances in Neural Information Processing Systems 32 (2019). [16] Gabriel Peyré and Marco Cuturi. 2019. Computational optimal transport: With applications to data science. Now Foundations and Trends. [17] Matthew Qian, Yahia Ramadan, Suhita Anubha, and Ariful Azad. 2026. SparsityAware Roofline Models for Sparse Matrix-Matrix Multiplication. arXiv preprint arXiv:2604.06637 (2026). [18] Ali Saad-Eldin, Benjamin D Pedigo, Carey E Priebe, and Joshua T Vogelstein. 2021. Graph matching via optimal transport. arXiv preprint arXiv:2111.05366 (2021). [19] Rohit Singh, Jinbo Xu, and Bonnie Berger. 2008. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences 105, 35 (2008), 12763–12768. [20] Jianheng Tang, Weiqi Zhang, Jiajin Li, Kangfei Zhao, Fugee Tsung, and Jia Li. 2023. Robust attributed graph alignment via joint structure learning and optimal transport. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 1638–1651. [21] Ruijie Wang, Yuchen Yan, Jialu Wang, Yuting Jia, Ye Zhang, Weinan Zhang, and Xinbing Wang. 2018. Acekg: A large-scale knowledge graph for academic data mining. In Proceedings of the 27th ACM international conference on information and knowledge management. 1487–1490. [22] Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. 2020. A fast proximal point method for computing exact wasserstein distance. In Uncertainty in artificial intelligence. PMLR, 433–453. [23] Hongteng Xu, Dixin Luo, and Lawrence Carin. 2019. Scalable GromovWasserstein learning for graph partitioning and matching. Advances in neural information processing systems 32 (2019). [24] Yuchen Yan, Si Zhang, and Hanghang Tong. 2021. Bright: A bridging algorithm for network alignment. In Proceedings of the web conference 2021. 3907–3917. [25] Carl Yang, Aydın Buluç, and John D Owens. 2018. Design principles for sparse matrix multiplication on the gpu. In European Conference on Parallel Processing. Springer, 672–687. [26] Qi Yu, Ruizhong Qiu, Zhichen Zeng, My T Thai, Huan Liu, and Hanghang Tong. 2026. AvAtar: Learning to Align via Active Optimal Transport. arXiv preprint arXiv:2605.24395 (2026).
[27] Qi Yu, Zhichen Zeng, Yuchen Yan, Zhining Liu, Baoyu Jing, Ruizhong Qiu, Ariful Azad, and Hanghang Tong. 2025. PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment. arXiv preprint arXiv:2505.21366 (2025). [28] Qi Yu, Zhichen Zeng, Yuchen Yan, Lei Ying, R Srikant, and Hanghang Tong. 2025. Joint optimal transport and embedding for network alignment. In Proceedings of the ACM on Web Conference 2025. 2064–2075. [29] Zhichen Zeng, Boxin Du, Si Zhang, Yinglong Xia, Zhining Liu, and Hanghang Tong. 2024. Hierarchical multi-marginal optimal transport for network alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 16660– 16668. [30] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. 2023. PARROT: Position-aware regularized optimal transport for network alignment. In Proceedings of the ACM web conference 2023. 372–382. [31] Si Zhang and Hanghang Tong. 2016. Final: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1345–1354. [32] Si Zhang and Hanghang Tong. 2020. Network alignment: Recent advances and future directions. In Proceedings of the 29th ACM international conference on information & knowledge management. 3521–3522. [33] Si Zhang, Hanghang Tong, Long Jin, Yinglong Xia, and Yunsong Guo. 2021. Balancing consistency and disparity in network alignment. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2212–2222. [34] Si Zhang, Hanghang Tong, Ross Maciejewski, and Tina Eliassi-Rad. 2019. Multilevel network alignment. In The World Wide Web Conference. 2344–2354. [35] Si Zhang, Hanghang Tong, Yinglong Xia, Liang Xiong, and Jiejun Xu. 2020. Nettrans: Neural cross-network transformation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 986– 996.