Scalable Optimal Transport Algorithm for Network Alignment

# Scalable Optimal Transport Algorithm for Network Alignment
Source: [https://arxiv.org/html/2607.11952](https://arxiv.org/html/2607.11952)
,Durga Mandarapu∗Lawrence Berkeley National LaboratoryCAUSA[durga@lbl\.gov](https://arxiv.org/html/2607.11952v1/mailto:[email protected]),Qi YuUniversity of Illinois at Urbana\-ChampaignILUSA[qiyu6@illinois\.edu](https://arxiv.org/html/2607.11952v1/mailto:[email protected]),Hanghang TongUniversity of Illinois at Urbana\-ChampaignILUSA[htong@illinois\.edu](https://arxiv.org/html/2607.11952v1/mailto:[email protected])andAriful AzadTexas A&M UniversityTXUSA[ariful@tamu\.edu](https://arxiv.org/html/2607.11952v1/mailto:[email protected])

###### Abstract\.

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 presentFastAlign, a scalable, sparsity\-aware framework for optimal transport\-based network alignment\. Rather than introducing a new alignment model,FastAlignpreserves the original OT formulation and reinterprets its computation as a set of recurring mixed sparse\-dense operations\.FastAligncombines sparsity\-aware graph computation with domain\-specific kernel fusion, including a custom SpMM kernel\. Our results show thatFastAlignachieves alignment quality comparable to state\-of\-the\-art OT\-based methods while substantially reducing end\-to\-end runtime up to3\.89×3\.89\\times–9\.45×9\.45\\timeson CPU and2\.24×2\.24\\times–32\.54×32\.54\\timeson GPU\.

\*\*\*These authors contributed equally\.## 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\(Cao and Yu,[2016](https://arxiv.org/html/2607.11952#bib.bib11)\), fraud detection\(Duet al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib10)\), and knowledge graphs\(Wanget al\.,[2018](https://arxiv.org/html/2607.11952#bib.bib12)\)\. 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](https://arxiv.org/html/2607.11952#S1.F1)\)\. Consistency\-based methods use a fast linear transformation between two networks, although their accuracy suffers because they do not fully capture global structure\(Zhang and Tong,[2016](https://arxiv.org/html/2607.11952#bib.bib4)\)\. Embedding\-based methods improve accuracy by learning node representations, at the cost of higher runtime from deep representation learning\(Yanet al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib3); Zhanget al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib5),[2021](https://arxiv.org/html/2607.11952#bib.bib6)\)\. 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\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8); Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7); Zenget al\.,[2024](https://arxiv.org/html/2607.11952#bib.bib2); Tanget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib9)\)\. 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\.

10410^\{4\}10510^\{5\}10610^\{6\}0\.40\.40\.60\.60\.80\.8Time \(s\)MRRFastAlignFINALBRIGHTNetTransJOENAPARROTSLOTAlign

Figure 1\.MRR \(accuracy\) vs\. runtime across network alignment methods on the ACM\-DBLP networks\. FINAL is consistency\-based, BRIGHT and NetTrans are embedding\-based, while the rest are OT\-based methods\.To address this scalability bottleneck without sacrificing alignment accuracy, we presentFastAlign, a scalable sparsity\-aware framework for OT\-based network alignment\. Rather than introducing a new alignment model,FastAlignpreserves 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\.FastAlignrealizes this decomposition using sparsity\-aware graph operations and memory\-efficient kernel fusion to reduce memory traffic and avoid unnecessary intermediate materialization\. As a result,FastAlignaccelerates and scales OT\-based network alignment, making it practical at large graph sizes\.

Building on this reinterpretation,FastAligncombines four optimizations\. First, it uses sparsity\-aware computations to replace all dense matrix computations involving graph structures\. Second, it 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 implementFastAlignon CPU and GPU and evaluate it on a range of real\-world and synthetic network alignment datasets\. Our results show thatFastAlignachieves comparable alignment quality to SOTA OT\-based methods while substantially reducing end\-to\-end runtime\.

In summary, this paper makes the following contributions:

- •We presentFastAlign, 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 thatFastAlignachieves3\.89×3\.89\\times–9\.45×9\.45\\timesspeedup on CPU and2\.24×2\.24\\times–32\.54×32\.54\\timesspeedup on GPU relative to SOTA network alignment algorithms\.

## 2\.Background

Let𝐆1=\(𝐕1,𝐄1,𝐀1\)\\mathbf\{G\}\_\{1\}=\(\\mathbf\{V\}\_\{1\},\\mathbf\{E\}\_\{1\},\\mathbf\{A\}\_\{1\}\)and𝐆2=\(𝐕2,𝐄2,𝐀2\)\\mathbf\{G\}\_\{2\}=\(\\mathbf\{V\}\_\{2\},\\mathbf\{E\}\_\{2\},\\mathbf\{A\}\_\{2\}\)denote two networks, with\|𝐕1\|=n1\|\\mathbf\{V\}\_\{1\}\|=n\_\{1\},\|𝐕2\|=n2\|\\mathbf\{V\}\_\{2\}\|=n\_\{2\}, and adjacency matrices𝐀1∈ℝn1×n1\\mathbf\{A\}\_\{1\}\\in\\mathbb\{R\}^\{n\_\{1\}\\times n\_\{1\}\}and𝐀2∈ℝn2×n2\\mathbf\{A\}\_\{2\}\\in\\mathbb\{R\}^\{n\_\{2\}\\times n\_\{2\}\}\. Nodes optionally carry attributes encoded as𝐗1∈ℝn1×d\\mathbf\{X\}\_\{1\}\{\\in\}\\mathbb\{R\}^\{n\_\{1\}\\times d\}and𝐗2∈ℝn2×d\\mathbf\{X\}\_\{2\}\\in\\mathbb\{R\}^\{n\_\{2\}\\times d\}\. We are further given a set of anchor pairsℒ⊆𝐕1×𝐕2\\mathcal\{L\}\\subseteq\\mathbf\{V\}\_\{1\}\\times\\mathbf\{V\}\_\{2\}, where each pair denotes a known correspondence between the two networks\. Network alignment computes a soft alignment matrix𝐒∈ℝn1×n2\\mathbf\{S\}\\in\\mathbb\{R\}^\{n\_\{1\}\\times n\_\{2\}\}, where𝐒i​j\\mathbf\{S\}\_\{ij\}scores likelihood of nodei∈𝐕1i\\in\\mathbf\{V\}\_\{1\}corresponding to nodej∈𝐕2j\\in\\mathbf\{V\}\_\{2\}\. Figure[2](https://arxiv.org/html/2607.11952#S2.F2)illustrates network alignment problem\. Existing approaches can be categorized as consistency\-based, embedding\-based, or OT\-based\(Zhang and Tong,[2020](https://arxiv.org/html/2607.11952#bib.bib21)\)\. Of these, OT\-based approaches consistently achieve SOTA performance\(Yuet al\.,[2025a](https://arxiv.org/html/2607.11952#bib.bib1)\), our algorithm builds on this paradigm\. So, we detail OT\-based methods in this section and defer the rest to Section[5](https://arxiv.org/html/2607.11952#S5)\.

### 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\(Peyré and Cuturi,[2019](https://arxiv.org/html/2607.11952#bib.bib13)\)\. OT\-based network alignment treats the node sets𝐕1\\mathbf\{V\}\_\{1\}and𝐕2\\mathbf\{V\}\_\{2\}as discrete distributions with uniform mass vectors𝝁=1n1​𝟏n1\\bm\{\\mu\}=\\tfrac\{1\}\{n\_\{1\}\}\\mathbf\{1\}\_\{n\_\{1\}\}and𝝂=1n2​𝟏n2\\bm\{\\nu\}=\\tfrac\{1\}\{n\_\{2\}\}\\mathbf\{1\}\_\{n\_\{2\}\}\. The soft alignment matrix𝐒\\mathbf\{S\}corresponds to the OT transport plan, whose entry𝐒i​j\\mathbf\{S\}\_\{ij\}encodes the amount of mass routed from nodei∈𝐕1i\\in\\mathbf\{V\}\_\{1\}to nodej∈𝐕2j\\in\\mathbf\{V\}\_\{2\}and is interpreted as the strength of their correspondence\. Given a cost matrix𝐂∈ℝn1×n2\\mathbf\{C\}\\in\\mathbb\{R\}^\{n\_\{1\}\\times n\_\{2\}\}that encodes the penalty for aligning each pair of nodes, the optimal alignment is obtained by solving

\(1\)min𝐒∈Π​\(𝝁,𝝂\)⁡⟨𝐒,𝐂⟩−ε​H​\(𝐒\),\\min\_\{\\mathbf\{S\}\\in\\Pi\(\\bm\{\\mu\},\\bm\{\\nu\}\)\}\\;\\langle\\mathbf\{S\},\\mathbf\{C\}\\rangle\-\\varepsilon\\,H\(\\mathbf\{S\}\),where⟨⋅⟩\\langle\\cdot\\rangledenotes the Frobenius inner product,Π​\(𝝁,𝝂\)=\{𝐒∈ℝ≥0n1×n2:𝐒𝟏=𝝁,𝐒⊤​𝟏=𝝂\}\\Pi\(\\bm\{\\mu\},\\bm\{\\nu\}\)=\\\{\\mathbf\{S\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{n\_\{1\}\\times n\_\{2\}\}:\\mathbf\{S\}\\mathbf\{1\}=\\bm\{\\mu\},\\;\\mathbf\{S\}^\{\\top\}\\mathbf\{1\}=\\bm\{\\nu\}\\\}is the set of feasible soft alignments, andε\>0\\varepsilon\>0controls the strength of the entropic regularizerH​\(𝐒\)H\(\\mathbf\{S\}\)that makes the problem strictly convex and efficiently solvable by the Sinkhorn algorithm\(Cuturi,[2013](https://arxiv.org/html/2607.11952#bib.bib15)\)\. The objective in Eq\.[1](https://arxiv.org/html/2607.11952#S2.E1)is shaped by two design choices: how the cost matrix𝐂\\mathbf\{C\}is constructed and how the resulting optimization is solved\. We discuss each in turn\.

![Refer to caption](https://arxiv.org/html/2607.11952v1/x1.png)Figure 2\.Network alignment problem\. Given two attributed networks𝐆1\\mathbf\{G\}\_\{1\}and𝐆2\\mathbf\{G\}\_\{2\}and a set of anchor links, network alignment seeks a correspondence of nodes across networks\.
### 2\.2\.Decomposition of the Cost Matrix

The design of the cost matrix𝐂\\mathbf\{C\}is what most directly shapes alignment quality\. A well\-designed cost captures three consistency principles together with prior anchor knowledge\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8)\)\.*Node consistency*\(𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}\) requires matched nodes to have similar attributes and similar structural positions within their respective networks\.*Edge consistency*\(𝐂edge\\mathbf\{C\}\_\{\\text\{edge\}\}\) requires matched node pairs to preserve their connecting edges\.*Neighborhood consistency*\(𝐂nbr\\mathbf\{C\}\_\{\\text\{nbr\}\}\) 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 \(𝐂anc\\mathbf\{C\}\_\{\\text\{anc\}\}\), biasing the alignment toward known correspondences\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8)\)\. The overall cost matrix combines these terms additively, whereλe,λn,λa≥0\\lambda\_\{e\},\\lambda\_\{n\},\\lambda\_\{a\}\\geq 0weigh the contribution of each term:

\(2\)𝐂=𝐂node\+λe​𝐂edge\+λn​𝐂nbr\+λa​𝐂anc\\mathbf\{C\}=\\mathbf\{C\}\_\{\\text\{node\}\}\\;\+\\;\\lambda\_\{e\}\\,\\mathbf\{C\}\_\{\\text\{edge\}\}\\;\+\\;\\lambda\_\{n\}\\,\\mathbf\{C\}\_\{\\text\{nbr\}\}\\;\+\\;\\lambda\_\{a\}\\,\\mathbf\{C\}\_\{\\text\{anc\}\}

### 2\.3\.The OT solver

Given the current cost matrix𝐂\\mathbf\{C\}and the predefined marginal vectors𝝁,𝝂\\bm\{\\mu\},\\bm\{\\nu\}, the Sinkhorn algorithm computes the alignment matrix𝐒\\mathbf\{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𝐚\\mathbf\{a\}and𝐛\\mathbf\{b\}and alternately updates them in the log domain \(for numerical stability\):

\(3\)aj=ε​log⁡νj−ε​LSEi\(bi−𝐂i​jε\),bi=ε​log⁡μi−ε​LSEj\(aj−𝐂i​jε\)a\_\{j\}=\\varepsilon\\log\\nu\_\{j\}\-\\varepsilon\\operatorname\*\{LSE\}\_\{i\}\\\!\\left\(\\tfrac\{b\_\{i\}\-\\mathbf\{C\}\_\{ij\}\}\{\\varepsilon\}\\right\),\\quad b\_\{i\}=\\varepsilon\\log\\mu\_\{i\}\-\\varepsilon\\operatorname\*\{LSE\}\_\{j\}\\\!\\left\(\\tfrac\{a\_\{j\}\-\\mathbf\{C\}\_\{ij\}\}\{\\varepsilon\}\\right\)
where LSE is the log\-sum\-exp reduction\. On convergence, the alignment matrix is recovered as

\(4\)𝐒i​j=exp⁡\(aj\+bi−𝐂i​jε\)\.\\mathbf\{S\}\_\{ij\}=\\exp\\\!\\left\(\\frac\{a\_\{j\}\+b\_\{i\}\-\\mathbf\{C\}\_\{ij\}\}\{\\varepsilon\}\\right\)\.Eq\.[4](https://arxiv.org/html/2607.11952#S2.E4)yields the optimal alignment for the current𝐂\\mathbf\{C\}\. Because some components of𝐂\\mathbf\{C\}themselves depend on𝐒\\mathbf\{S\}, the cost is then updated using the newly computed alignment and the Sinkhorn solve is repeated\. This alternation realizes the constrained proximal point method\(Xieet al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib16)\), 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 introduceFastAlign, a scalable and fast network alignment framework\.FastAlignachieves 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](https://arxiv.org/html/2607.11952#S2)\.

### 3\.1\.Foundation ofFastAlign: 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](https://arxiv.org/html/2607.11952#S2)can be organized in three phases: \(a\) Phase 1 normalizes the adjacency matrices and computes the alignment\-independent cost components𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}and𝐂anc\\mathbf\{C\}\_\{\\text\{anc\}\}; \(b\) Phase 2 computes the alignment\-dependent components𝐂edge\\mathbf\{C\}\_\{\\text\{edge\}\}and𝐂nbr\\mathbf\{C\}\_\{\\text\{nbr\}\}; and \(c\) Phase 3 invokes an OT solver to produce the alignment from the current cost matrix\. These three phases ofFastAlignare described in Algorithm[1](https://arxiv.org/html/2607.11952#alg1)and Figure[3](https://arxiv.org/html/2607.11952#S3.F3)\.

Algorithm 1FastAlign: A Linear Algebraic View of OT\-Based Network Alignment1:Graphs

𝐆1,𝐆2\\mathbf\{G\}\_\{1\},\\mathbf\{G\}\_\{2\}; attributes

𝐗1,𝐗2\\mathbf\{X\}\_\{1\},\\mathbf\{X\}\_\{2\}; anchors

ℒ\\mathcal\{L\}
2:Alignment matrix

𝐒\\mathbf\{S\}
3:

𝐀¯1←\\bar\{\\mathbf\{A\}\}\_\{1\}\\leftarrowRownormalized\(

𝐆1\\mathbf\{G\}\_\{1\}\),

𝐀¯2←\\bar\{\\mathbf\{A\}\}\_\{2\}\\leftarrowRownormalized\(

𝐆2\\mathbf\{G\}\_\{2\}\)

4:

𝐑1\(0\)←OneHot​\(ℒ​\[0\]\)\\mathbf\{R\}\_\{1\}^\{\(0\)\}\\leftarrow\\textsc\{OneHot\}\(\\mathcal\{L\}\[0\]\),

𝐑2\(0\)←OneHot​\(ℒ​\[1\]\)\\mathbf\{R\}\_\{2\}^\{\(0\)\}\\leftarrow\\textsc\{OneHot\}\(\\mathcal\{L\}\[1\]\)
5:// Phase 1: precompute𝐒\\mathbf\{S\}\-independent quantities

6:Perform

kkiterations:

𝐑i←\(1−β\)​𝐀¯i​𝐑i\+β​𝐑i\(0\)\\mathbf\{R\}\_\{i\}\\leftarrow\(1\-\\beta\)\\,\\bar\{\\mathbf\{A\}\}\_\{i\}\\mathbf\{R\}\_\{i\}\+\\beta\\,\\mathbf\{R\}\_\{i\}^\{\(0\)\}for

i∈\{1,2\}i\\in\\\{1,2\\\}
7:

𝐂node←α​e−𝐑1​𝐑2⊤\+\(1−α\)​e−𝐗1​𝐗2⊤\\mathbf\{C\}\_\{\\text\{node\}\}\\leftarrow\\alpha\\,e^\{\-\\mathbf\{R\}\_\{1\}\\mathbf\{R\}\_\{2\}^\{\\top\}\}\+\(1\-\\alpha\)\\,e^\{\-\\mathbf\{X\}\_\{1\}\\mathbf\{X\}\_\{2\}^\{\\top\}\}
8:Perform

kkiterations:

𝐂node←𝐀¯1​𝐂node​𝐀¯2\\mathbf\{C\}\_\{\\text\{node\}\}\\leftarrow\\bar\{\\mathbf\{A\}\}\_\{1\}\\mathbf\{C\}\_\{\\text\{node\}\}\\ \\bar\{\\mathbf\{A\}\}\_\{2\}
9:

𝐂anc←−log⁡\(ε\+OneHot​\(ℒ\)\)\\mathbf\{C\}\_\{\\text\{anc\}\}\\leftarrow\-\\log\\\!\\left\(\\varepsilon\+\\textsc\{OneHot\}\(\\mathcal\{L\}\)\\right\)
10:

𝐂1←\(𝐑1​𝐑1⊤\)⊙𝐀¯1,𝐂2←\(𝐑2​𝐑2⊤\)⊙𝐀¯2T\\mathbf\{C\}\_\{1\}\\leftarrow\(\\mathbf\{R\}\_\{1\}\\mathbf\{R\}\_\{1\}^\{\\top\}\)\\odot\\bar\{\\mathbf\{A\}\}\_\{1\},\\ \\mathbf\{C\}\_\{2\}\\leftarrow\(\\mathbf\{R\}\_\{2\}\\mathbf\{R\}\_\{2\}^\{\\top\}\)\\odot\\bar\{\\mathbf\{A\}\}\_\{2\}^\{T\}
11:Initialize

𝐒\\mathbf\{S\}
12:repeat

13:// Phase 2: update𝐒\\mathbf\{S\}\-dependent costs

14:

𝐂edge←𝐂1​𝐒𝐂2⊤\\mathbf\{C\}\_\{\\text\{edge\}\}\\leftarrow\\mathbf\{C\}\_\{1\}\\mathbf\{S\}\\mathbf\{C\}\_\{2\}^\{\\top\}
15:

𝐂nbr←−log⁡\(𝐀¯1⊤​𝐒​𝐀¯2\)\\mathbf\{C\}\_\{\\text\{nbr\}\}\\leftarrow\-\\log\\\!\\left\(\\bar\{\\mathbf\{A\}\}\_\{1\}^\{\\top\}\\mathbf\{S\}\\bar\{\\mathbf\{A\}\}\_\{2\}\\right\)
16:

𝐂←𝐂node\+λe​𝐂edge\+λn​𝐂nbr\+λa​𝐂anc\\mathbf\{C\}\\leftarrow\\mathbf\{C\}\_\{\\text\{node\}\}\+\\lambda\_\{e\}\\mathbf\{C\}\_\{\\text\{edge\}\}\+\\lambda\_\{n\}\\mathbf\{C\}\_\{\\text\{nbr\}\}\+\\lambda\_\{a\}\\mathbf\{C\}\_\{\\text\{anc\}\}
17:// Phase 3: solve for𝐒\\mathbf\{S\}

18:Repeat

kktimes:

19:

𝐚←SoftMin​\(𝐂,𝐛\)\\mathbf\{a\}\\leftarrow\\textsc\{SoftMin\}\(\\mathbf\{C\},\\mathbf\{b\}\)
20:

𝐛←SoftMin​\(𝐂⊤,𝐚\)\\mathbf\{b\}\\leftarrow\\textsc\{SoftMin\}\(\\mathbf\{C\}^\{\\top\},\\mathbf\{a\}\)
21:

𝐒←exp⁡\(\(𝟏​𝐚⊤\+𝐛𝟏⊤−𝐂\)/ϵ\)\\mathbf\{S\}\\leftarrow\\exp\\\!\\big\(\(\\mathbf\{1\}\\mathbf\{a\}^\{\\top\}\+\\mathbf\{b\}\\mathbf\{1\}^\{\\top\}\-\\mathbf\{C\}\)/\\epsilon\\big\)
22:until

𝐒\\mathbf\{S\}converges

23:functionSoftMin\(

𝐂,𝐯\\mathbf\{C\},\\mathbf\{v\}\)

24:return

−ϵ​log⁡\(\(exp⁡\(−\(𝐂−𝐯𝟏⊤\)/ϵ\)\)⊤​𝟏\)\-\\epsilon\\log\\\!\\big\(\(\\exp\(\-\(\\mathbf\{C\}\-\\mathbf\{v\}\\mathbf\{1\}^\{\\top\}\)/\\epsilon\)\)^\{\\top\}\\mathbf\{1\}\\big\)

Algorithm[1](https://arxiv.org/html/2607.11952#alg1)takes two networks with node features and a set of anchor alignments and returns the alignment matrix𝐒\\mathbf\{S\}\. After normalizing the adjacency matrices into𝐀¯1,𝐀¯2\\bar\{\\mathbf\{A\}\}\_\{1\},\\bar\{\\mathbf\{A\}\}\_\{2\}\(Line[3](https://arxiv.org/html/2607.11952#alg1.l3)\) and representing the anchors as one\-hot encodings𝐑1\(0\)∈ℝn1×\|ℒ\|\\mathbf\{R\}\_\{1\}^\{\(0\)\}\\in\\mathbb\{R\}^\{n\_\{1\}\\times\|\\mathcal\{L\}\|\}and𝐑2\(0\)∈ℝn2×\|ℒ\|\\mathbf\{R\}\_\{2\}^\{\(0\)\}\\in\\mathbb\{R\}^\{n\_\{2\}\\times\|\\mathcal\{L\}\|\}, the algorithm proceeds in three phases:

Phase 1: Computing𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}\(line 3\-5\)\.The node\-consistency cost is built in three steps\. First, repeated multiplication\(1−β\)​𝐀¯i​𝐑i\+β​𝐑i\(0\)\(1\-\\beta\)\\,\\bar\{\\mathbf\{A\}\}\_\{i\}\\mathbf\{R\}\_\{i\}\+\\beta\\,\\mathbf\{R\}\_\{i\}^\{\(0\)\}produces a personalized\-PageRank\-style positional encoding of each node with respect to the anchor set; thell\-th column of𝐑i\\mathbf\{R\}\_\{i\}encodes the position of every node relative to thell\-th anchor \(Line[6](https://arxiv.org/html/2607.11952#alg1.l6)\)\. Second, Line[7](https://arxiv.org/html/2607.11952#alg1.l7)forms the initial𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}from these encodings via two matrix multiplications\. Finally, the cost is iteratively propagated across networks via the triple product𝐀¯1​𝐂node​𝐀¯2\\bar\{\\mathbf\{A\}\}\_\{1\}\\mathbf\{C\}\_\{\\text\{node\}\}\\bar\{\\mathbf\{A\}\}\_\{2\}, yielding the final𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}that remains fixed for the rest of the algorithm\. Computing𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}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](https://arxiv.org/html/2607.11952#S3.SS4)\.

Phase 1: Computing𝐂anc\\mathbf\{C\}\_\{\\text\{anc\}\}\(line[9](https://arxiv.org/html/2607.11952#alg1.l9)\)\.The anchor\-preference cost encodes prior supervision directly from the known correspondences\.OneHot​\(ℒ\)\\textsc\{OneHot\}\(\\mathcal\{L\}\)places a one at each anchor pair\(i,j\)∈ℒ\(i,j\)\\in\\mathcal\{L\}and zero elsewhere\. Each entry of𝐂anc\\mathbf\{C\}\_\{\\text\{anc\}\}is≈0\\approx 0on anchor pairs and−log⁡\(ε\)\-\\log\(\\varepsilon\)otherwise, biasing transport toward known correspondences\.

Phase 2: Computing𝐂edge\\mathbf\{C\}\_\{\\text\{edge\}\}\(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:𝐂1=\(𝐑1​𝐑1⊤\)⊙𝐀¯1\\mathbf\{C\}\_\{1\}=\(\\mathbf\{R\}\_\{1\}\\mathbf\{R\}\_\{1\}^\{\\top\}\)\\odot\\bar\{\\mathbf\{A\}\}\_\{1\}and analogously for𝐂2\\mathbf\{C\}\_\{2\}\(Line[10](https://arxiv.org/html/2607.11952#alg1.l10)\)\. This triple product, called*sampled dense–dense matrix multiplication*\(SDDMM\), is less expensive than a full dense product because only the entries selected by𝐀¯1\\bar\{\\mathbf\{A\}\}\_\{1\}are computed\. Since𝐂1\\mathbf\{C\}\_\{1\}and𝐂2\\mathbf\{C\}\_\{2\}do not depend on𝐒\\mathbf\{S\}, they are precomputed in Phase 1\.𝐂edge\\mathbf\{C\}\_\{\\text\{edge\}\}is computed by transporting𝐂1\\mathbf\{C\}\_\{1\}and𝐂2\\mathbf\{C\}\_\{2\}across the networks via the triple product𝐂1​𝐒𝐂2⊤\\mathbf\{C\}\_\{1\}\\mathbf\{S\}\\mathbf\{C\}\_\{2\}^\{\\top\}\(Line[14](https://arxiv.org/html/2607.11952#alg1.l14)\)\.

Phase 2: Computing𝐂nbr\\mathbf\{C\}\_\{\\text\{nbr\}\}\(line[15](https://arxiv.org/html/2607.11952#alg1.l15)\)\.The neighborhood\-consistency cost ensures that for any node pair\(i,j\)\(i,j\), the alignment score𝐒i​j\\mathbf\{S\}\_\{ij\}is consistent with the alignment scores ofii’s andjj’s neighbors\. It is computed by propagating the current alignment across the two networks via the triple product𝐂nbr=𝐀¯1⊤​𝐒​𝐀¯2\\mathbf\{C\}\_\{\\text\{nbr\}\}=\\bar\{\\mathbf\{A\}\}\_\{1\}^\{\\top\}\\mathbf\{S\}\\bar\{\\mathbf\{A\}\}\_\{2\}\.

Phase 2: Computing𝐂\\mathbf\{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λp​log⁡\(S\)\\lambda\_\{p\}\\log\(S\), which couples the cost to the current alignment\.

![Refer to caption](https://arxiv.org/html/2607.11952v1/x2.png)Figure 3\.Overview of OT\-based network alignment\. Given two attributed networks𝐆1\\mathbf\{G\}\_\{1\}and𝐆2\\mathbf\{G\}\_\{2\}and two anchor links \(dashed lines\)\.Phase 1precomputes the fixed cost components,𝐂n​o​d​e\\mathbf\{C\}\_\{node\}and𝐂a​n​c\\mathbf\{C\}\_\{anc\}\.Phase 2computes two𝐒\\mathbf\{S\}\-dependent cost terms:𝐂e​d​g​e\\mathbf\{C\}\_\{edge\}and𝐂n​b​r\\mathbf\{C\}\_\{nbr\}, from the current alignment matrix𝐒\\mathbf\{S\}, then adds them to the fixed costs to form the Cost matrix\.Phase 3runs the Sinkhorn algorithm forKKiterations to optimize the dual vectors, which then update𝐒\\mathbf\{S\}\. The updated𝐒\\mathbf\{S\}feeds back into the𝐒\\mathbf\{S\}\-dependent cost terms, and Phase 2\-3 repeats up toTTouter iterations until𝐒\\mathbf\{S\}converges into the final node alignment\.Phase 3: Computing𝐒\\mathbf\{S\}\(line 13\-17\)\.We solve the entropic OT of Section[2\.3](https://arxiv.org/html/2607.11952#S2.SS3)by Sinkhorn \(Line[18](https://arxiv.org/html/2607.11952#alg1.l18)\-15\)\. First, the dual vectors𝐚\\mathbf\{a\}and𝐛\\mathbf\{b\}are refined by k alternating SoftMin updates\. Each SoftMin is a log\-sum\-exp reduction over the cost matrix:𝐚\\mathbf\{a\}reduces𝐂\\mathbf\{C\}over its rows \(Line 14\), and𝐛\\mathbf\{b\}reduces𝐂\\mathbf\{C\}over its columns, equivalently a row reduction over𝐂T\\mathbf\{C\}^\{T\}\(Line 15\)\. Second, the alignment is updated from the dual vectors𝐚\\mathbf\{a\}and𝐛\\mathbf\{b\}\(Line[21](https://arxiv.org/html/2607.11952#alg1.l21)\), where the outer products𝟏​𝐚⊤\\mathbf\{1\}\\mathbf\{a\}^\{\\top\}and𝐛𝟏⊤\\mathbf\{b\}\\mathbf\{1\}^\{\\top\}broadcast the dual vectors inton1×n2n\_\{1\}\\times n\_\{2\}matrices, combined with𝐂\\mathbf\{C\}, and exponentiated element\-wise to produce𝐒\\mathbf\{S\}\.

### 3\.2\.Optimization opportunities

The decomposition in Algorithm[1](https://arxiv.org/html/2607.11952#alg1)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 bottlenecks directly\. Assumingn1≈n2≈nn\_\{1\}\\approx n\_\{2\}\\approx n\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8); Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7)\), Phase 1 incurs𝒪​\(n3\)\\mathcal\{O\}\(n^\{3\}\)work across multiple matrix multiplications; Phase 2 updates the𝐒\\mathbf\{S\}\-dependent terms in𝒪​\(n3\)\\mathcal\{O\}\(n^\{3\}\)and produces a dense𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)matrix in each outer iteration; Phase 3 runs Sinkhorn at𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)per iteration\. Memory traffic is a second bottleneck: the dense𝒪​\(n2\)\\mathcal\{O\}\(n^\{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 computation40​–​69%40\\text\{\-\-\}69\\%, cost update15​–​36%15\\text\{\-\-\}36\\%, and Sinkhorn14​–​23%14\\text\{\-\-\}23\\%\.

Because the three phases share a small set of recurring primitives, accelerating those primitives accelerates the pipeline end\-to\-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\.𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}requires dense, sparse, and sparse\-dense\-sparse triple products;𝐂edge\\mathbf\{C\}\_\{\\text\{edge\}\}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\.FastAlignrepresents the input graphs as sparse matrices and replaces every dense graph computation with a sparse kernel\. The positional encoding \(Line 3\) and𝐂n​o​d​e\\mathbf\{C\}\_\{node\}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𝐂e​d​g​e\\mathbf\{C\}\_\{edge\}\(Line 10\) andCn​b​rC\_\{nbr\}\(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𝒪​\(n3\)\\mathcal\{O\}\(n^\{3\}\)to𝒪​\(nnz⋅n\)\\mathcal\{O\}\(\\textit\{nnz\}\\cdot n\), wherennis the number of nodes andnnzis the number of nonzeros \(edges\) in the sparse matrix\. For the intra\-network dissimilarity \(Line 7\), each of thennzmasked entries is an inner product of length\|ℒ\|\|\\mathcal\{L\}\|, reducing the cost from𝒪​\(n2⋅\|ℒ\|\)\\mathcal\{O\}\(n^\{2\}\\cdot\|\\mathcal\{L\}\|\)to𝒪​\(nnz⋅\|ℒ\|\)\\mathcal\{O\}\(\\textit\{nnz\}\\cdot\|\\mathcal\{L\}\|\)\.

Memory Reduction\.Utilizing sparse matrix representations scales down graph storage overhead from𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)to𝒪​\(nnz\)\\mathcal\{O\}\(\\textit\{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\.\(Tanget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib9); Yuet al\.,[2026](https://arxiv.org/html/2607.11952#bib.bib37)\)Thus, reducing the numerical precision from double to single precision does not noticeably affect alignment accuracy\. This also reduces the memory footprint and enablesFastAlignto scale to larger graphs\.

### 3\.4\.Custom SpMM for wide dense cost matrix

Several of the most expensive steps in Algorithm[1](https://arxiv.org/html/2607.11952#alg1)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𝐂node\\mathbf\{C\}\_\{\\text\{node\}\}propagation𝐀¯1​𝐂​𝐀¯2⊤\\bar\{\\mathbf\{A\}\}\_\{1\}\\mathbf\{C\}\\,\\bar\{\\mathbf\{A\}\}\_\{2\}^\{\\top\}\(Line[8](https://arxiv.org/html/2607.11952#alg1.l8)\), where𝐂\\mathbf\{C\}is dense matrix of sizen1×n2n\_\{1\}\\times n\_\{2\}and the outer matrices are sparse matrices𝐀¯1∈ℝn1×n1\\bar\{\\mathbf\{A\}\}\_\{1\}\\in\\mathbb\{R\}^\{n\_\{1\}\\times n\_\{1\}\}and𝐀¯2∈ℝn2×n2\\bar\{\\mathbf\{A\}\}\_\{2\}\\in\\mathbb\{R\}^\{n\_\{2\}\\times n\_\{2\}\}\. The same sparse\-dense\-sparse structure recurs in the edge and neighborhood consistency terms𝐂edge=𝐂1​𝐒𝐂2⊤\\mathbf\{C\}\_\{\\text\{edge\}\}=\\mathbf\{C\}\_\{1\}\\mathbf\{S\}\\mathbf\{C\}\_\{2\}^\{\\top\}\(Line[14](https://arxiv.org/html/2607.11952#alg1.l14)\) and𝐂nbr=𝐀¯1⊤​𝐒​𝐀¯2\\mathbf\{C\}\_\{\\text\{nbr\}\}=\\bar\{\\mathbf\{A\}\}\_\{1\}^\{\\top\}\\mathbf\{S\}\\bar\{\\mathbf\{A\}\}\_\{2\}\(Line[15](https://arxiv.org/html/2607.11952#alg1.l15)\); there the outer factors𝐂1,𝐂2\\mathbf\{C\}\_\{1\},\\mathbf\{C\}\_\{2\}are also sparse, with the same sparsity pattern as the adjacency matrix\. Computing each term requires two SpMMs that share the same structure, a sparsen×nn\\times nmatrix multiplied by a dense matrix withΘ​\(n\)\\Theta\(n\)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[6](https://arxiv.org/html/2607.11952#alg1.l6)\), which is another SpMM,𝐑k\\mathbf\{R\}\_\{k\}has width≈0\.2​n\\approx 0\.2\\,n, and it grows without bound as the graphs grow\. This is the opposite of the regime that off\-the\-shelf libraries such as Intel MKL is optimized for, where the dense matrix has a small, often*fixed*column dimensiondd\. 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\(Yanget al\.,[2018](https://arxiv.org/html/2607.11952#bib.bib35); Qianet al\.,[2026](https://arxiv.org/html/2607.11952#bib.bib36); Huanget al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib33)\)computes𝐌=𝐀𝐁\\mathbf\{M\}=\\mathbf\{A\}\\mathbf\{B\}where𝐀\\mathbf\{A\}is the sparsen×nn\\times nmatrix, and B and M are densen×dn\\times dmatrices, whered≪nd\\ll n\. This kernel computes one output row at a time𝐌​\[i,:\]=∑k:Ai​k≠0Ai​k​𝐁​\[k,:\]\\mathbf\{M\}\[i,:\]=\\sum\_\{k\\,:\\,A\_\{ik\}\\neq 0\}A\_\{ik\}\\mathbf\{B\}\[k,:\], wherekkruns only over the columns in which rowiiof𝐀\\mathbf\{A\}has a nonzero,Ai​kA\_\{ik\}is that nonzero value,𝐁​\[k,:\]\\mathbf\{B\}\[k,:\]is thekk\-th row of the dense input matrix, and𝐌​\[i,:\]\\mathbf\{M\}\[i,:\]is the output row being accumulated\. These kernels are tuned for tall\-skinny𝐁\\mathbf\{B\}\(d≪n\)\(d\\ll n\)where a row𝐁​\[k,:\]\\mathbf\{B\}\[k,:\]is short, stays cache\-resident, and is reused across every nonzero that references columnkkof𝐀\\mathbf\{A\}\. This setting is the most common application of SpMM when used in iterative solvers and graph neural networks\.

InFastAlign,𝐁\\mathbf\{\\mathbf\{B\}\}is wide, not tall\-skinny\. A row𝐁​\[k,:\]\\mathbf\{B\}\[k,:\]is nowθ​\(n\)\\theta\(n\), so it may no longer stay cache\-resident and cannot be reused across the nonzeros that reference columnkkof𝐀\\mathbf\{A\}, which limits data reuse inFastAlign\. In the worst case, each nonzero from the sparse matrix fetches its corresponding dense row from memory, giving𝒪​\(nnz⋅n\)\\mathcal\{O\}\(\\textit\{nnz\}\\cdot n\)memory traffic\. Since SpMM is a memory\-bound operation, the standard SpMM libraries \(e\.g\., Intel MKL\) hurt the performance ofFastAlign\.

The fix: custom SpMM kernel\.We design this kernel with a column blocking model to improve cache residency\. We partition dense matrices𝐁\\mathbf\{B\}and𝐌\\mathbf\{M\}intoQ=⌈n2/bc⌉Q=\\lceil n\_\{2\}/b\_\{c\}\\rceilnarrow blocks ofbcb\_\{c\}contiguous columns and process one block at a time\. To compute blockqqof output, whose columns start atjq=\(q−1\)​bcj\_\{q\}=\(q\-1\)b\_\{c\}, we fill it one output row at a time:𝐌\[i,jq:jq\+bc\]=∑k:𝐀i​k≠0𝐀i​k𝐁\[k,jq:jq\+bc\]\\mathbf\{M\}\[i,j\_\{q\}:j\_\{q\}\+b\_\{c\}\]=\\sum\_\{k\\,:\\,\\mathbf\{A\}\_\{ik\}\\neq 0\}\\mathbf\{A\}\_\{ik\}\\mathbf\{B\}\[k,j\_\{q\}:j\_\{q\}\+b\_\{c\}\]\. 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 ton1×bcn\_\{1\}\\times b\_\{c\}instead ofn1×n2n\_\{1\}\\times n\_\{2\}that does not fit into L2/L3\. This will increase cache hits when consecutive rows share similar columns of nonzeros\.

Figure[4](https://arxiv.org/html/2607.11952#S3.F4)traces one block: To fill thebcb\_\{c\}output block𝐌\[k,jq:jq\+bc\]\\mathbf\{M\}\[k,j\_\{q\}:j\_\{q\}\+b\_\{c\}\], the kernel iterates over all rows of𝐀\\mathbf\{A\}accumulating the𝐀i​k𝐁\[k,jq:jq\+bc\]\\mathbf\{A\}\_\{ik\}\\mathbf\{B\}\[k,j\_\{q\}:j\_\{q\}\+b\_\{c\}\]for each nonzero\. Since each memory access within a column\-block computation is limited to a narrow partition of the dense matrix, the resident𝐁\\mathbf\{B\}partition shrinks ton1×bcn\_\{1\}\\times b\_\{c\}, which fits into L2/L3, instead of the fulln1×n2n\_\{1\}\\times n\_\{2\}, which does not\.

Payoff\.Blocking leaves the arithmetic and total access count unchanged at𝒪​\(nnz⋅n\)\\mathcal\{O\}\(\\textit\{nnz\}\\cdot n\)\. It changes which level of memory is accessed\. By keeping each𝐁\\mathbf\{B\}block cache\-resident, it reduces the DRAM traffic for reading𝐁\\mathbf\{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\.

![Refer to caption](https://arxiv.org/html/2607.11952v1/x3.png)Figure 4\.Column\-blocked SpMM for one output block\. To compute onebcb\_\{c\}block of𝐌\\mathbf\{M\}\(blue\), the corresponding block of𝐁\\mathbf\{B\}\(green\) is read from DRAM into cache once and reused across all rows of𝐀\\mathbf\{A\}\.
### 3\.5\.Domain\-specific Kernel Fusion

According to Algorithm[1](https://arxiv.org/html/2607.11952#alg1), the cost matrix𝐂\\mathbf\{C\}assembly \(Line 12\), and Sinkhorn dual vector update \(Lines 14,15, Eq\.[3](https://arxiv.org/html/2607.11952#S2.E3)\) are written as compact algebraic expressions; however, a literal computation allocates and populates an1×n2n\_\{1\}\\times n\_\{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 merge each algebraic chain into a single path over the output/input matrices\. We observed such chains that occur and fused them\.

Cost matrix𝐂\\mathbf\{C\}computation\.Cost computation \(Line 12\) combines four dense terms by scaling, log, and addition:𝐂←𝐂node\+λe​𝐂edge\+λn​𝐂nbr\+λa​𝐂anc\\mathbf\{C\}\\leftarrow\\mathbf\{C\}\_\{\\text\{node\}\}\+\\lambda\_\{e\}\\mathbf\{C\}\_\{\\text\{edge\}\}\+\\lambda\_\{n\}\\mathbf\{C\}\_\{\\text\{nbr\}\}\+\\lambda\_\{a\}\\mathbf\{C\}\_\{\\text\{anc\}\}\. Naively computing this results in materializing at least 6 separate densen1×n2n\_\{1\}\\times n\_\{2\}matrices\. The fused kernel instead visits each entry\(i,j\)\(i,j\)once, loads the five contributing values, applies the scale/log/add, and writes𝐂i​j\\mathbf\{C\}\_\{ij\}in one pass, without any intermediates\.

Sinkhorn dual updates\.Each dual update is a log\-sum\-exp reduction over the cost matrix \(Eq\.[3](https://arxiv.org/html/2607.11952#S2.E3)\): 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 fulln1×n2n\_\{1\}\\times n\_\{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 then1×n2n\_\{1\}\\times n\_\{2\}intermediate is not materialized\. The same kernel serves both updates: applied to𝐂\\mathbf\{C\}to refresh𝐚\\mathbf\{a\}and to𝐂T\\mathbf\{C\}^\{T\}to refresh𝐛\\mathbf\{b\}\.

### 3\.6\.GPU\-aware Optimizations

The computational reformulation ofFastAlignnaturally 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](https://arxiv.org/html/2607.11952#S3.SS3)\) and domain\-specific kernel fusion \(Section[3\.5](https://arxiv.org/html/2607.11952#S3.SS5)\) 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\.

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𝐛\\mathbf\{b\}by operating on a transpose view of𝐂\\mathbf\{C\}, produced by a tiled transpose kernel that stages32×3232\\times 32tiles in shared memory with\+1\+1column padding to eliminate bank conflicts, achieving coalesced reads and writes in a single pass\.

Parallel streams and reusing SpMM plans\.To improve GPU utilization,FastAlignissues independent kernels for separate graphs across parallel, non\-blocking CUDA streams\. For example, the row\-normalization kernels of the two graph intra\-distance matrices \(Line[10](https://arxiv.org/html/2607.11952#alg1.l10)of Algorithm[1](https://arxiv.org/html/2607.11952#alg1)\) 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,FastAlignpre\-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 evaluateFastAlignto answer the following research questions:

- Q1How accurate isFastAligncompared to SOTA network alignment algorithms?
- Q2How doesFastAlignaccelerate alignment on real networks?
- Q3How doesFastAlignscale with increasing network size?
- Q4How much does each of our techniques contribute to the overall speedups achieved byFastAlign?

### 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 ground\-truth 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,FastAlignexhibits convergence behavior similar to the OT baseline, PARROT\.

#### 4\.1\.1\.Metrics

We evaluate the effectiveness ofFastAligncompared to the baselines using the following two accuracy metrics\. For each test nodex∈G1x\\in G\_\{1\}, letx′∈G2x^\{\\prime\}\\in G\_\{2\}denote its ground\-truth match\. We rank all candidate nodes inG2G\_\{2\}by their alignment score withxx\. A prediction is counted as a hit atKKifx′x^\{\\prime\}appears among the top\-KKranked candidates\. For a test set withnnnode pairs,Hits​@​K=\#​hits​@​Kn\\mathrm\{Hits@\}K=\\frac\{\\\#\\mathrm\{hits@\}K\}\{n\}\. Mean Reciprocal Rank \(MRR\) is measured as the average inverse rank of the ground\-truth match:MRR=1n​∑\(x,x′\)∈𝒮test1rank⁡\(x,x′\)\\mathrm\{MRR\}=\\frac\{1\}\{n\}\\sum\_\{\(x,x^\{\\prime\}\)\\in\\mathcal\{S\}\_\{\\mathrm\{test\}\}\}\\frac\{1\}\{\\operatorname\{rank\}\(x,x^\{\\prime\}\)\}

#### 4\.1\.2\.Baselines

Following the benchmark study\(Yuet al\.,[2025a](https://arxiv.org/html/2607.11952#bib.bib1)\), we select six top\-accuracy baselines that cover the three main categories of network alignment methods\. FINAL\(Zhang and Tong,[2016](https://arxiv.org/html/2607.11952#bib.bib4)\)is consistency\-based; BRIGHT\(Yanet al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib3)\)and NetTrans\(Zhanget al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib5)\)are embedding\-based; and JOENA\(Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7)\), PARROT\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8)\), and SLOTAlign\(Tanget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib9)\)are OT\-based\. PARROT is the closest baseline toFastAlign, since our framework preserves the same OT\-based alignment formulation\. We also evaluated NeXtAlign\(Zhanget al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib6)\), but it timed out on most datasets and is omitted\.

#### 4\.1\.3\.Datasets

Table[1](https://arxiv.org/html/2607.11952#S4.T1)summarizes the real\-world datasets we used to evaluateFastAlignagainst the baselines\. For scalability experiments, we generated synthetic graphs using the Erdős–Rényi model with an average node degree of1010\(Erdőset al\.,[1960](https://arxiv.org/html/2607.11952#bib.bib14)\)\.

Table 1\.Dataset CharacteristicsTable 2\.Accuracy comparison with all baselines for real\-world datasets on GPU \(bold numbers denote the best accuracies\)\.![Refer to caption](https://arxiv.org/html/2607.11952v1/images/cpu_real_runtime_inside.png)

![Refer to caption](https://arxiv.org/html/2607.11952v1/images/gpu_real_runtime_inside.png)

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 ofFastAlignover PARROT\.

### 4\.2\.Accuracy Results

Table[2](https://arxiv.org/html/2607.11952#S4.T2)compares the Hits@1010and MRR ofFastAlignagainst 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\.FastAlignand other OT\-based methods achieve substantially higher accuracy than consistency\-based and embedding\-based methods\. Compared with state\-of\-the\-art OT\-based baselines,FastAlignachieves 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 DBP1515K to floating\-point roundoff inconsistencies, especially from fused kernels as they change the order of numerical operations\.

### 4\.3\.Performance Analysis

Figure[5](https://arxiv.org/html/2607.11952#S4.F5)compares the runtime ofFastAlignagainst 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\.FastAlignachieves a3\.89×3\.89\\times–9\.45×9\.45\\timesspeedup on CPU and a2\.24×2\.24\\times–32\.54×32\.54\\timesspeedup on GPU compared to PARROT, the fastest baseline\. Across all baselines, the speedup ranges from3\.89×3\.89\\timesto193\.90×193\.90\\timeson CPU and from2\.24×2\.24\\timesto1321\.85×1321\.85\\timeson GPU, with the largest speedups achieved over slow baselines\.

These significantly high speedups demonstrate the effectiveness ofFastAlign’s computational reinterpretation and optimizations discussed in Section[3](https://arxiv.org/html/2607.11952#S3)\. 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 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 ofFastAlignon GPU\.

### 4\.4\.Scalability Analysis

Figure[6](https://arxiv.org/html/2607.11952#S4.F6)a shows the runtime scalability comparison ofFastAlignfor synthetic datasets against the baselines that did not time out on graphs with2020K nodes\.FastAlignscales more efficiently than all baselines, with speedups increasing as graph size grows — from0\.82×0\.82\\timesat 10K nodes to9\.41×9\.41\\timesat 110K nodes over the fastest baseline\. The overall speedups are in the range0\.82×0\.82\\times–14\.49×14\.49\\times\.

![Refer to caption](https://arxiv.org/html/2607.11952v1/images/cpu_er_runtime_inside.png)

![Refer to caption](https://arxiv.org/html/2607.11952v1/images/gpu_er_runtime_inside.png)

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\.FastAlignscales to graphs with up to110110K nodes, while all baselines exceptBRIGHTrun out of memory at smaller graph sizes\. The maximum problem size supported byFastAlignis determined by its peak memory usage during Sinkhorn optimization\. The peak live state uses nine dense\(n1×n2\)\(n\_\{1\}\\times n\_\{2\}\)matrices and two sparse graph matrices\. Using single precision \(Section[3\.3](https://arxiv.org/html/2607.11952#S3.SS3)\), the dense matrices require\(4⋅9⋅n1​n2=36​n1​n2\)\(4\\cdot 9\\cdot n\_\{1\}n\_\{2\}=36n\_\{1\}n\_\{2\}\)bytes, which bounds the implementation to approximately110110K nodes on a CPU with512512GB memory\. As long as they fit in memory,FastAlignaligns the networks\.

![Refer to caption](https://arxiv.org/html/2607.11952v1/images/cpu_ablation1.png)

![Refer to caption](https://arxiv.org/html/2607.11952v1/images/gpu_ablation1.png)

Figure 7\.Performance contribution ofFastAlign’s optimizations to its overall runtime on \(a\) CPU and \(b\) GPU architectures for real\-world networks\. Numbers on bars indicate speedups relative toPARROT\.Figure[6](https://arxiv.org/html/2607.11952#S4.F6)b presents the scalability comparison on GPU using an NVIDIA A100 \(80GB variant\)\.FastAlignandBRIGHTscale to 50K\-node graphs, whileFINALsupports up to 35K nodes,PARROT,JOENA, andSLOTAlignup to 30K, andNetTransonly 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 of4\.16×4\.16\\times–86\.88×86\.88\\timesoverBRIGHT, the fastest baseline\. Across all baselines and graph sizes, the speedups are in the range of4\.16×4\.16\\times–2525\.88×2525\.88\\times\.

### 4\.5\.Ablation studies

Figure[7](https://arxiv.org/html/2607.11952#S4.F7)shows the runtime contribution of eachFastAlignoptimization: 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, 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 least1010K nodes, the overhead of PyTorch over CPP/CUDA becomes negligible and the C\+\+/CUDA baselines are no longer faster, confirming thatFastAlign’s speedups are driven by its algorithmic optimizations rather than the platform change\.

On CPU, sparsity alone improves runtime by0\.8×0\.8\\times–2\.6×2\.6\\times, and adding fusion compounds these gains to2\.2×2\.2\\times–4\.6×4\.6\\times, with custom SpMM further increasing speedups to2\.9×2\.9\\times–6\.6×6\.6\\times\. On GPU, sparsity contributes2\.6×2\.6\\times–4\.4×4\.4\\timesto the speedup, and adding fusion brings the overall speedup to2\.2×2\.2\\times–32\.5×32\.5\\times\. 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\(Singhet al\.,[2008](https://arxiv.org/html/2607.11952#bib.bib18)\)propagates pairwise similarities on the product graph, FINAL\(Zhang and Tong,[2016](https://arxiv.org/html/2607.11952#bib.bib4)\)extends this with attribute and edge consistency for attributed graphs, and BIG\-ALIGN\(Koutraet al\.,[2013](https://arxiv.org/html/2607.11952#bib.bib19)\)recovers a near\-permutation between adjacency matrices via a Frobenius objective\. Computationally, these methods iterate over an𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)product or similarity space that dominates cost at scale, motivating coarsening\-based designs like MOANA\(Zhanget al\.,[2019](https://arxiv.org/html/2607.11952#bib.bib20)\)\. In terms of accuracy, however, they capture limited global graph geometry, and the consistency premise weakens when the two networks differ substantially\(Zhanget al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib6)\)\.

The second learns node embeddings that encode each network’s topology while pulling anchor pairs together: IONE\(Liuet al\.,[2016](https://arxiv.org/html/2607.11952#bib.bib22)\)models directional follower/followee context, REGAL\(Heimannet al\.,[2018](https://arxiv.org/html/2607.11952#bib.bib23)\)factorizes a cross\-network similarity matrix, CrossMNA\(Chuet al\.,[2019](https://arxiv.org/html/2607.11952#bib.bib24)\)fuses intra\-/inter\-/global features, and NetTrans\(Zhanget al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib5)\), BRIGHT\(Yanet al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib3)\), and NeXtAlign\(Zhanget al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib6)\)further improve robustness through learned transformations, restart\-based 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 cross\-network relations only indirectly through anchor paths and are sensitive to sampling noise and embedding\-space distortion\(Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7); Zhanget al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib6)\)\.

#### 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\(Chenet al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib25)\)\. Methods differ mainly in how the transport cost is defined\. Early designs transport spectral node embeddings \(EMD\(Nikolentzoset al\.,[2017](https://arxiv.org/html/2607.11952#bib.bib26)\)\) or represent graphs through filtered graph signals and Gaussian graph kernels \(FGOT\(Mareticet al\.,[2022](https://arxiv.org/html/2607.11952#bib.bib27)\), GOT\(Petric Mareticet al\.,[2019](https://arxiv.org/html/2607.11952#bib.bib28)\)\), while later costs jointly encode node and edge correspondence via the Wasserstein and Gromov–Wasserstein \(GW\) distances\(Xuet al\.,[2019](https://arxiv.org/html/2607.11952#bib.bib29); Chenet al\.,[2020](https://arxiv.org/html/2607.11952#bib.bib25)\)\. A prominent line aligns graphs through Gromov–Wasserstein structural discrepancy \(S\-GWL\(Xuet al\.,[2019](https://arxiv.org/html/2607.11952#bib.bib29)\), GraphOTC\(O’Connoret al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib30)\)\), while GOAT\(Saad\-Eldinet al\.,[2021](https://arxiv.org/html/2607.11952#bib.bib31)\)accelerates it via the Sinkhorn algorithm\. More recent work learns the cost instead of fixing it: SLOTAlign\(Tanget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib9)\)encodes a GW objective with a parameter\-free GNN, CombAlign\(Chenet al\.,[2025](https://arxiv.org/html/2607.11952#bib.bib32)\)ensembles embedding\- and OT\-based alignments, and JOENA\(Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7)\)jointly learns embeddings and transport\. PARROT\(Zenget al\.,[2023](https://arxiv.org/html/2607.11952#bib.bib8)\)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𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)matrices, and while proximal solvers\(Yuet al\.,[2025b](https://arxiv.org/html/2607.11952#bib.bib7)\)reduce iteration counts, graph sparsity and sparse\-linear\-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 computation\-optimized 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 presentFastAlign, which keeps the original OT formulation and treats its computation as a small set of recurring sparse\-dense operations\.FastAlignexploits 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 thatFastAlignmatches the accuracy of SOTA OT\-based methods while running up to9\.45×9\.45\\timesfaster on CPU and up to32\.54×32\.54\\timesfaster on GPU than the strongest OT baseline\.

## References

- X\. Cao and Y\. Yu \(2016\)Joint user modeling across aligned heterogeneous sites\.InProceedings of the 10th ACM Conference on Recommender Systems,pp\. 83–90\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p1.1)\.
- L\. Chen, Z\. Gan, Y\. Cheng, L\. Li, L\. Carin, and J\. Liu \(2020\)Graph optimal transport for cross\-domain alignment\.InInternational Conference on Machine Learning,pp\. 1542–1553\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- S\. Chen, Y\. Liu, L\. Zou, Z\. Wang, and Y\. Lin \(2025\)CombAlign: enhancing model expressiveness in unsupervised graph alignment\.IEEE Transactions on Knowledge and Data Engineering38\(2\),pp\. 956–968\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- X\. Chu, X\. Fan, D\. Yao, Z\. Zhu, J\. Huang, and J\. Bi \(2019\)Cross\-network embedding for multi\-network alignment\.InThe world wide web conference,pp\. 273–284\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- M\. Cuturi \(2013\)Sinkhorn distances: lightspeed computation of optimal transport\.Advances in neural information processing systems26\.Cited by:[§2\.1](https://arxiv.org/html/2607.11952#S2.SS1.p1.14)\.
- B\. Du, S\. Zhang, Y\. Yan, and H\. Tong \(2021\)New frontiers of multi\-network mining: recent developments and future trend\.InProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining,pp\. 4038–4039\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p1.1)\.
- P\. Erdős, A\. Rényi,et al\.\(1960\)On the evolution of random graphs\.Publications of the\.Cited by:[§4\.1\.3](https://arxiv.org/html/2607.11952#S4.SS1.SSS3.p1.1)\.
- M\. Heimann, H\. Shen, T\. Safavi, and D\. Koutra \(2018\)Regal: representation learning\-based graph alignment\.InProceedings of the 27th ACM international conference on information and knowledge management,pp\. 117–126\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- G\. Huang, G\. Dai, Y\. Wang, and H\. Yang \(2020\)Ge\-spmm: general\-purpose sparse matrix\-matrix multiplication on gpus for graph neural networks\.InSC20: International Conference for High Performance Computing, Networking, Storage and Analysis,pp\. 1–12\.Cited by:[§3\.4](https://arxiv.org/html/2607.11952#S3.SS4.p2.18)\.
- D\. Koutra, H\. Tong, and D\. Lubensky \(2013\)Big\-align: fast bipartite graph alignment\.In2013 IEEE 13th international conference on data mining,pp\. 389–398\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p1.1)\.
- L\. Liu, W\. K\. Cheung, X\. Li, and L\. Liao \(2016\)Aligning users across social networks using network embedding\.\.InIjcai,Vol\.16,pp\. 1774–80\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- H\. P\. Maretic, M\. El Gheche, G\. Chierchia, and P\. Frossard \(2022\)Fgot: graph distances based on filters and optimal transport\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 7710–7718\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- G\. Nikolentzos, P\. Meladianos, and M\. Vazirgiannis \(2017\)Matching node embeddings for graph similarity\.InProceedings of the AAAI conference on Artificial Intelligence,Vol\.31\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- K\. O’Connor, B\. Yi, K\. McGoff, and A\. B\. Nobel \(2021\)Graph optimal transport with transition couplings of random walks\.arXiv e\-prints,pp\. arXiv–2106\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- H\. Petric Maretic, M\. El Gheche, G\. Chierchia, and P\. Frossard \(2019\)Got: an optimal transport framework for graph comparison\.Advances in Neural Information Processing Systems32\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- G\. Peyré and M\. Cuturi \(2019\)Computational optimal transport: with applications to data science\.Now Foundations and Trends\.Cited by:[§2\.1](https://arxiv.org/html/2607.11952#S2.SS1.p1.9)\.
- M\. Qian, Y\. Ramadan, S\. Anubha, and A\. Azad \(2026\)Sparsity\-aware roofline models for sparse matrix\-matrix multiplication\.arXiv preprint arXiv:2604\.06637\.Cited by:[§3\.4](https://arxiv.org/html/2607.11952#S3.SS4.p2.18)\.
- A\. Saad\-Eldin, B\. D\. Pedigo, C\. E\. Priebe, and J\. T\. Vogelstein \(2021\)Graph matching via optimal transport\.arXiv preprint arXiv:2111\.05366\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- R\. Singh, J\. Xu, and B\. Berger \(2008\)Global alignment of multiple protein interaction networks with application to functional orthology detection\.Proceedings of the National Academy of Sciences105\(35\),pp\. 12763–12768\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p1.1)\.
- J\. Tang, W\. Zhang, J\. Li, K\. Zhao, F\. Tsung, and J\. Li \(2023\)Robust attributed graph alignment via joint structure learning and optimal transport\.In2023 IEEE 39th International Conference on Data Engineering \(ICDE\),pp\. 1638–1651\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§3\.3](https://arxiv.org/html/2607.11952#S3.SS3.p3.2),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- R\. Wang, Y\. Yan, J\. Wang, Y\. Jia, Y\. Zhang, W\. Zhang, and X\. Wang \(2018\)Acekg: a large\-scale knowledge graph for academic data mining\.InProceedings of the 27th ACM international conference on information and knowledge management,pp\. 1487–1490\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p1.1)\.
- Y\. Xie, X\. Wang, R\. Wang, and H\. Zha \(2020\)A fast proximal point method for computing exact wasserstein distance\.InUncertainty in artificial intelligence,pp\. 433–453\.Cited by:[§2\.3](https://arxiv.org/html/2607.11952#S2.SS3.p3.3)\.
- H\. Xu, D\. Luo, and L\. Carin \(2019\)Scalable gromov\-wasserstein learning for graph partitioning and matching\.Advances in neural information processing systems32\.Cited by:[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- Y\. Yan, S\. Zhang, and H\. Tong \(2021\)Bright: a bridging algorithm for network alignment\.InProceedings of the web conference 2021,pp\. 3907–3917\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- C\. Yang, A\. Buluç, and J\. D\. Owens \(2018\)Design principles for sparse matrix multiplication on the gpu\.InEuropean Conference on Parallel Processing,pp\. 672–687\.Cited by:[§3\.4](https://arxiv.org/html/2607.11952#S3.SS4.p2.18)\.
- Q\. Yu, R\. Qiu, Z\. Zeng, M\. T\. Thai, H\. Liu, and H\. Tong \(2026\)AvAtar: learning to align via active optimal transport\.arXiv preprint arXiv:2605\.24395\.Cited by:[§3\.3](https://arxiv.org/html/2607.11952#S3.SS3.p3.2)\.
- Q\. Yu, Z\. Zeng, Y\. Yan, Z\. Liu, B\. Jing, R\. Qiu, A\. Azad, and H\. Tong \(2025a\)PLANETALIGN: a comprehensive python library for benchmarking network alignment\.arXiv preprint arXiv:2505\.21366\.Cited by:[§2](https://arxiv.org/html/2607.11952#S2.p1.13),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1)\.
- Q\. Yu, Z\. Zeng, Y\. Yan, L\. Ying, R\. Srikant, and H\. Tong \(2025b\)Joint optimal transport and embedding for network alignment\.InProceedings of the ACM on Web Conference 2025,pp\. 2064–2075\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§3\.2](https://arxiv.org/html/2607.11952#S3.SS2.p1.10),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1),[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1),[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p2.1)\.
- Z\. Zeng, B\. Du, S\. Zhang, Y\. Xia, Z\. Liu, and H\. Tong \(2024\)Hierarchical multi\-marginal optimal transport for network alignment\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 16660–16668\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1)\.
- Z\. Zeng, S\. Zhang, Y\. Xia, and H\. Tong \(2023\)PARROT: position\-aware regularized optimal transport for network alignment\.InProceedings of the ACM web conference 2023,pp\. 372–382\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.11952#S2.SS2.p1.6),[§3\.2](https://arxiv.org/html/2607.11952#S3.SS2.p1.10),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.2](https://arxiv.org/html/2607.11952#S5.SS0.SSS2.p1.1)\.
- S\. Zhang, H\. Tong, L\. Jin, Y\. Xia, and Y\. Guo \(2021\)Balancing consistency and disparity in network alignment\.InProceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining,pp\. 2212–2222\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- S\. Zhang, H\. Tong, R\. Maciejewski, and T\. Eliassi\-Rad \(2019\)Multilevel network alignment\.InThe World Wide Web Conference,pp\. 2344–2354\.Cited by:[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p1.1)\.
- S\. Zhang, H\. Tong, Y\. Xia, L\. Xiong, and J\. Xu \(2020\)Nettrans: neural cross\-network transformation\.InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,pp\. 986–996\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p2.1)\.
- S\. Zhang and H\. Tong \(2016\)Final: fast attributed network alignment\.InProceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,pp\. 1345–1354\.Cited by:[§1](https://arxiv.org/html/2607.11952#S1.p2.1),[§4\.1\.2](https://arxiv.org/html/2607.11952#S4.SS1.SSS2.p1.1),[§5\.0\.1](https://arxiv.org/html/2607.11952#S5.SS0.SSS1.p1.1)\.
- S\. Zhang and H\. Tong \(2020\)Network alignment: recent advances and future directions\.InProceedings of the 29th ACM international conference on information & knowledge management,pp\. 3521–3522\.Cited by:[§2](https://arxiv.org/html/2607.11952#S2.p1.13)\.