Towards Effective and Efficient Graph Alignment without Supervision

Songyang Chen; Youfang Lin; Yu Liu; Shuai Zheng; Lei Zou

cs.LGMar 9, 2026

Towards Effective and Efficient Graph Alignment without Supervision

Authors: Songyang Chen, Youfang Lin, Yu Liu, Shuai Zheng, Lei Zou

Organizations: Beijing Jiaotong University, Beijing, 100044, P.R. China. · Peking University, Beijing, 100871, P.R. China.

Abstract

Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the local representation, global alignment'' paradigm, and present a new global representation and alignment'' paradigm to resolve the mismatch between the two phases in the alignment process. We then propose Global representation and optimal transport-based Alignment (GlobAlign), and its variant, GlobAlign-E, for better Efficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, GlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT's cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, GlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.

Figures & tables

Panel of Figure 1 — Figure 1: Running time (s) vs. accuracy (Hits@1) on three widely-adopted datasets Tang et al. (2023a) ; Xu et al. (2019b) ; Gao et al. (2021) ; Wang et al. (2023) ; Cheng et al. (2023) . Existing embedding and OT-based methods show similar performance in terms of efficiency-accuracy tradeoff. Our GlobAlign model significantly surpasses existing solutions in accuracy, while our GlobAlign-E model achieves up to one order of magnitude speedup with comparable performance

Notation	Description
$\mathcal{G}_{s},\mathcal{G}_{t}$	The source and target graph
$\mathbf{A}_{p},\mathbf{X}_{p}$	Adjacency matrix and node feature matrix ( $p=s,t$ )
$u_{i},u_{j},v_{k},v_{l}$	Nodes with $u_{i},u_{j}\in\mathcal{G}_{s}$ and $v_{k},v_{l}\in\mathcal{G}_{t}$
$\mathbf{D}_{s},\mathbf{D}_{t}$	The relation matrices of source graph and target graph
$\mathbf{T}$	The alignment matrix
$\mathbf{Cost}_{gwd},\mathbf{Cost}_{wd}$	The cross-graph transport cost

Table 1: Table of notations.

Method	Alignment Paradigm	Time Complexity
GAlign Trung et al. (2020)	Local Representation, Global Comparison	$O(n^{2}d)$
WAlign Gao et al. (2021)		$O(n^{2}d)$
GTCAlign Wang et al. (2023)		$O(n^{2}d)$
GWD Xu et al. (2019b)	Local Propagation, Global Transport	$O(n^{3})$
SLOTAlign Tang et al. (2023a)		$O(n^{3})$
UHOT-GM Cheng et al. (2023)		$O(n^{3})$

Table 2: Comparison of GlobAlign against state of the art: alignment paradigms and time complexity. Note that all methods share a space complexity of

O(n^{2})

, which is dominated by the output size.

Figure 2: A toy example to show the limitation of local representation for graph alignment

Figure 3: Illustration of node alignment from OT perspective

Dataset	$\|\mathcal{V}_{s}\|,\|\mathcal{V}_{t}\|$	$\|\mathcal{E}_{s}\|,\|\mathcal{E}_{t}\|$	Features	Anchors
Douban	1,118	3,022	538	1,118
Douban	3,906	16,328	538	1,118
Allmv-Imdb	5,713	119,073	14	5,174
Allmv-Imdb	6,011	124,709	14	5,174
ACM-DBLP	9,872	39,561	17	6,325
ACM-DBLP	9,916	44,808	17	6,325

Table 3: Datasets and their statistics.

Datasets	Metrics	kNN	GAlign	WAlign	GTCAlign	GWD	SLOTAlign	UHOT-GM	GlobAlign	GlobAlign-E
Douban	Hits@1	27.65 $\pm_{0.23}$	45.33 $\pm_{0.26}$	39.45 $\pm_{0.37}$	60.89 $\pm_{0.36}$	3.31 $\pm_{0.27}$	51.41 $\pm_{0.12}$	59.91 $\pm_{0.35}$	77.10 $\pm_{0.18}$	75.62 $\pm_{0.16}$
	Hits@5	42.33 $\pm_{0.25}$	67.74 $\pm_{0.17}$	62.41 $\pm_{0.43}$	76.82 $\pm_{0.21}$	8.35 $\pm_{0.35}$	73.48 $\pm_{0.23}$	71.50 $\pm_{0.36}$	93.67 $\pm_{0.21}$	91.88 $\pm_{0.27}$
	Hits@10	49.30 $\pm_{0.21}$	78.07 $\pm_{0.23}$	71.52 $\pm_{0.39}$	82.34 $\pm_{0.25}$	9.98 $\pm_{0.31}$	77.71 $\pm_{0.19}$	77.33 $\pm_{0.27}$	96.21 $\pm_{0.25}$	94.34 $\pm_{0.22}$
	Hits@30	63.23 $\pm_{0.31}$	84.77 $\pm_{0.29}$	83.21 $\pm_{0.59}$	89.86 $\pm_{0.23}$	12.91 $\pm_{0.34}$	82.96 $\pm_{0.21}$	84.74 $\pm_{0.26}$	97.83 $\pm_{0.23}$	95.19 $\pm_{0.19}$
	MRR	35.04 $\pm_{0.31}$	56.39 $\pm_{0.23}$	46.23 $\pm_{0.43}$	69.80 $\pm_{0.13}$	5.81 $\pm_{0.18}$	61.33 $\pm_{0.21}$	67.42 $\pm_{0.15}$	84.31 $\pm_{0.17}$	81.52 $\pm_{0.13}$
Allmv-Imdb	Hits@1	30.41 $\pm_{0.15}$	82.13 $\pm_{0.19}$	52.69 $\pm_{0.23}$	84.73 $\pm_{0.16}$	87.82 $\pm_{0.33}$	90.61 $\pm_{0.11}$	91.63 $\pm_{0.14}$	96.30 $\pm_{0.13}$	94.82 $\pm_{0.39}$

Table 4: Comparison of model performance against seven baselines on five datasets.

Figure 5: Running time comparison. Vertical bars with diagonal lines represent methods that exceed the 3-hour time limit

Figure 6: Impact of hyperparameters

Figure 7: Accuracy (Hits@1) vs. noise level

Figure 8: Ablation study

Panel of Figure 9 — Figure 9: The attention matrices for the Douban dataset

Graph Matching

Graph matching finds correspondences between nodes and edges to compare, align, or locate related structures in graphs.

See all 35 papers

Scalable Optimal Transport Algorithm for Network Alignment
Jul 11, 2026Elaheh Hassani, Durga Mandarapu, Qi Yu +2Graph Matching Sparse Matrix Multiplication
Lawrence Berkeley National Laboratory CA, USA · University of Illinois at Urbana-Champaign IL, USA
Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment
Aug 30, 2026Lutz Oettershagen, Honglian Wang, Aristides GionisGraph Matching Hypergraph Learning
University of Liverpool · Liverpool, UK · KTH Royal Institute of Technology +2
Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings
May 19, 2025Adrien Lagesse, Marc LelargeGraph Neural Networks Synthetic Benchmark Generation
INRIA, École Normale Supérieure - PSL, Paris, France.

Jul 11, 2026J/K move · Enter open · S save

Scalable Optimal Transport Algorithm for Network Alignment

Elaheh Hassani, Durga Mandarapu, Qi Yu, Hanghang Tong+1

Lawrence Berkeley National Laboratory CA, USA · University of Illinois at Urbana-Champaign IL, USA

Graph Matching Sparse Matrix Multiplication Optimal Transport

Open paper AskPDF arXiv

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, sparsity-aware 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-of-the-art OT-based methods while substantially reducing end-to-end runtime up to 3.89x-9.45x on CPU and 2.24x-32.54x on GPU.

Abstract

Graph Matching

Explore similar work

Scalable Optimal Transport Algorithm for Network Alignment

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings