Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Marc Lelarge

cs.LGOct 3, 2025

Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Authors: Marc Lelarge

Organizations: INRIA - Ecole Normale Supérieure PSL Research University

Abstract

For the combinatorial graph alignment problem (GAP), finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs, the classical Frank-Wolfe heuristic FAQ remains a strong baseline once it is properly initialized, while existing GNN approaches struggle in the purely structural setting. We introduce a chaining procedure: a sequence of Folklore-type (2-FWL) GNNs in which each network is trained with cross-entropy after decoding the previous network's similarity matrix and ranking nodes by their current alignment quality. This non-differentiable ranking step injects discrete combinatorial feedback at every stage; at inference, we iterate the final network and keep the candidate with highest observed nce. On sparse Erdos-Renyi graphs at noise level 0.25, chained FGNNs used to initialize FAQ reach 85% accuracy versus 13% for FAQ initialized from the convex relaxation, and essentially 0% for prior GNN methods. On correlated regular graphs, where MPNNs with constant features produce identical node embeddings (1-WL fails to refine) and FAQ's convex initialization is degenerate, chaining is the only method among those we evaluate, including Gromov-Wasserstein solvers, that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline. Code and pretrained chains available at: https://github.com/mlelarge/chaining-gnn-graph-alignment.

Figures & tables

type of graphs		sparse	dense	regular
Baselines	${\textbf{Proj}}(D_{\text{cx}})$	17.3	24.4	2.9
(non-neural)	${\textbf{FAQ}}(D_{\text{cx}})$	67.1	53	27
Baselines	FGNN Proj	17.8	23.6	6.7
(neural)	FGNN FAQ	71.1	47	54
chaining	ChFGNN Proj	95.8	44	67.1
chaining	ChFGNN FAQ	98.8	77.4	81.8

Table 1: Normalized alignment quality

\frac{\text{ALG}}{\text{REF}}

(in %) for sparse, dense and regular random graphs. Proj and FAQ are used to produce a permutation from the convex relaxation solution

D_{\text{cx}}

or from the similarity matrix computed by our chained FGNN (ChFGNN).

Panel of Figure 1 — Figure 1: Illustration of Step 2. The permutation $\pi$ maps 1→c, 2→a, 3→b, 4→d. Green edges show matches: edge 1-2 with a-c, and edge 1-3 with b-c. Node 1 has the highest score (2 matched edges), nodes 2 and 3 each have 1 matched edge, and node 4 has no matched edges.

Panel of Figure 2 — Figure 2: Overview of the chaining procedure. Starting from input graphs $G_{A}$ and $G_{B}$ , we first (1) extract features and compute similarities, then iteratively (2) rank nodes by alignment quality, and (3) use rankings to enhance features and similarities.

Sparse Erdős-Rényi, average degree $4$ ( ${\textbf{nce}}_{\max}\!\approx\!1000$ )
$p_{\text{noise}}$	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35
${\textbf{Proj}}(D_{\text{cx}})$	0.98/997	0.97/950	0.90/853	0.59/499	0.23/195	0.09/130	0.04/115	0.02/112
${\textbf{FAQ}}(D_{\text{cx}})$	0.98/997	0.98/950	0.96/898	0.95/847	0.73/723	0.13/504	0.04/487	0.02/485
FGNN Proj	0.98/997	0.94/ 925	0.74/674	0.44/365	0.23/193	0.12/134	0.06/114	0.03/103
FGNN FAQ	0.98/997	0.98/950	0.96/898	0.95/847	0.81/755	0.24/535	0.07/494	0.03/485
ChFGNN Proj	0.98/997	0.98/950	0.96/898	0.94/845	0.91/790	0.82/ 720	0.49/549	0.08/367

Table 2: Accuracy ( acc ) and number of common edges ( nce ) for Erdős-Rényi and regular graphs as a function of the noise

p_{\text{noise}}

. Each cell is

{\textbf{acc}}\,/\,{\textbf{nce}}

. ChFGNN denotes our chained FGNNs; Proj and FAQ are post-processing decoders. The nce metric does not depend on the planted permutation

\pi^{\star}

and is therefore unaffected by label imperfection at high noise.

$p_{\text{noise}}$	0	0.05	0.1	0.15	0.2	0.25
SAGE- FAQ	0.98/997	0.97/946	0.13/497	0.05/477	0.02/474	0.01/473
ChSAGE- FAQ	0.98/997	0.97/951	0.69/756	0.11/494	0.04/476	0.02/475
GIN- FAQ	0.98/997	0.98/951	0.93/ 879	0.25/538	0.04/478	0.02/477
ChGIN- FAQ	0.98/997	0.98/951	0.95/889	0.34/575	0.06/483	0.03/477
GAT- FAQ	0.98/997	0.97/951	0.79/805	0.14/503	0.04/479	0.02/478
ChGAT- FAQ	0.98/997	0.97/951	0.96/893	0.92/ 833	0.24/537	0.05/486

Table 3: Architecture ablation on sparse Erdős-Rényi (

n{=}500

d{=}4

), FAQ decoding. Each cell is

{\textbf{acc}}\,/\,{\textbf{nce}}

. Ch

\cdot

denotes the chained variant of each backbone. Chaining improves every backbone; only ChFGNN survives at

p_{\text{noise}}\geq 0.20

Method	yeast25LC		ca-netscience		inf-euroroad
Noise $q$	5%	10%	10%	20%	10%	20%
${\textbf{FAQ}}(D_{\text{cx}})$	0.50/7660	0.45/7245	0.65/822	0.46/687	0.56/1170	0.11/940
ChFGNN-ER4	0.48/7693	0.42/7297	0.64/818	0.44/688	0.40/1111	0.08/ 970
ChFGNN	0.54/7732	0.51/ 7404	0.65/824	0.57/ 724	0.64/ 1213	0.15/ 963

Table 4: Accuracy ( acc ) and number of common edges ( nce ) on noisy versions of real-world networks; each cell is

{\textbf{acc}}\,/\,{\textbf{nce}}

. ChFGNN-ER4 is the model trained on sparse Erdős–Rényi graphs (

d{=}4

); ChFGNN is trained on the target network and noise level.

Appendix figures & tables27 assets

Supplementary material from the paper’s appendix.

Appendix

name	average	number	used for comparison	sizes of
	degree	of nodes	with	train/val
Bernoulli	70	150	${\textbf{FAQ}}(D_{\text{cx}})$ [ Lyzinski et al., 2015 ]	2000/200
Sparse Erdős-Rényi (ER 4)	4	500	MPNN [ Yu et al., 2023 ]	200/100
Dense Erdős-Rényi (ER 80)	80	500	MPNN [ Yu et al., 2023 ]	200/100
Large Erdős-Rényi	3	1000	Bayesian message passing	200/100
			[ Muratori and Semerjian, 2024 ]

Appendix

Table 5: Statistics of synthetic datasets.

Dataset	# Nodes	# Edges	Avg. Degree	size train/valid
Yeast PPI [ Vijayan and Milenkovic, 2018 ]	1,004	8,323	16.58	20/20
ca-netscience [ Newman, 2006 ]	379	914	4.82	200/20
inf-euroroad [ Šubelj and Bajec, 2011 ]	1,174	1,417	2.41	20/5

Appendix

Table 6: Summary statistics of the real-world graphs.

Dataset	Degree spread	Clustering	Twins	Acc. ceiling	Swap $\leq 2$ edges
	graph / ER	graph / ER
Yeast PPI	1.12 / 0.24	0.65 / 0.02	24%	0.85	57%
ca-netscience	0.81 / 0.45	0.74 / 0.01	48%	0.71	83%
inf-euroroad	0.49 / 0.64	0.02 / 0.002	4%	0.98	77%

Appendix

Table 7: Structure and symmetries of the real-world graphs. Degree spread is the standard deviation of the degrees divided by their mean, and clustering the average clustering coefficient; both are compared with an Erdős–Rényi graph of the same size and average degree. A node has a twin when another node has the same neighbors (or, for two adjacent nodes, the same other neighbors): exchanging twins is an automorphism of the graph, so it leaves nce unchanged for every alignment, and the accuracy ceiling is the expected accuracy of a method that cannot tell twins apart (one correct node per twin class). The last column counts the nodes that can be exchanged with another node at the cost of at most two edges of the graph.

Datasets	FUGAL	${\textbf{FAQ}}(D_{\mathrm{cx}})$	ChFGNN
ER sparse (noise $0.1$ )	560	898	899
ER sparse (noise $0.2$ )	396	723	800
ER dense (noise $0.1$ )	17968	17968	17968
ER dense (noise $0.2$ )	5853	15972	15876
Regular (noise $0.05$ )	131	425	2059

Appendix

Table 10: Number of common edges (NCE) recovered on synthetic graphs.

Sparse Erdős-Rényi, average degree $4$ ( $30$ pairs per cell)
$p_{\text{noise}}$	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35
${\textbf{Proj}}(D_{\text{cx}})$	0.98/994	0.98/944	0.91/849	0.58/482	0.22/195	0.088/131	0.040/117	0.020/117
${\textbf{FAQ}}(D_{\text{cx}})$	0.98/994	0.97/945	0.97/895	0.94/841	0.64/683	0.12/499	0.037/484	0.015/481
BAPG	0.98/994	0.89/893	0.71/772	0.35/624	0.13/548	0.062/528	0.020/520	0.009/520
FGWAlign	0.98/994	0.88/886	0.70/767	0.34/618	0.13/546	0.062/528	0.021/520	0.010/520
ChFGNN Proj	0.98/994	0.98/945	0.97/894	0.95/840	0.91/783	0.85/722	0.40/451	0.035/261

Appendix

Table 11: Accuracy ( acc ) and number of common edges ( nce ) of the Gromov–Wasserstein solvers BAPG and FGWAlign, compared with the convex-relaxation baselines and our chained FGNNs on identical seeded test pairs (

n=500

). Each cell is

{\textbf{acc}}\,/\,{\textbf{nce}}

; best accuracy per column in bold.

Figure 3: Per-pair analysis on the test pairs. (a) Per-pair accuracy of each decoder on sparse Erdős–Rényi graphs as a function of the noise: the transition is bimodal (pairs are either solved or not) and the two Gromov–Wasserstein solvers transition earliest. (b) ChFGNN FAQ against ${\textbf{FAQ}}(D_{\text{cx}})$ on every synthetic pair: the empty lower-right region means that no pair solved by the baseline is missed by the chain. (c) The same paired view against BAPG: a single pair (dense, $p_{\text{noise}}=0.3$ ) is solved by BAPG and missed by the chain.

Sparse, average degree 4
Fraction of Seeds	0%	2%	4%	6%	8%	10%	12%	14%	16%	18%	20%
SeedGNN	0.3	15.1	47.4	82.8	96.0	96.6	97.0	97.6	97.6	97.6	97.6
PGM	0.2	2.3	6.1	16.3	31.6	54.5	73.3	79.2	86.3	88.9	92.7
SGM	0.3	3.6	8.9	13.8	22.3	36.3	54.5	67.3	84.4	89.6	91.6
MGCN	0.1	2.0	4.0	6.7	8.4	11.1	12.4	14.0	16.3	18.9	20.5
Dense, average degree 80

Appendix

Table 12: Accuracy (%) on sparse (average degree 4) and dense (average degree 80) Erdős Rényi random graphs at noise

0.2

, as a function of the seed fraction. Note the different seed scales for the two regimes.

Figure 4: Number of common edges ( nce ) recovered in sparse Erdős–Rényi graphs as a function of wall-clock computation time allocated to each implementation: FUGAL and FAQ variants run on CPU, while ChFGNN runs on GPU. The plot should be read as an implementation-level trade-off, not as a hardware-independent speed comparison.

Method	sparse ( $d{=}4$ )	dense ( $d{=}80$ )	regular ( $d{=}10$ )
BAPG	7	3	$<0.1$
FGWAlign	$\approx 70$	$150$ – $210$	$85$ – $95$
${\textbf{FAQ}}(D_{\text{cx}})$	$20$ – $40$	–	–
ChFGNN FAQ (full chain, CPU only)	$\approx 90$	–	–

Appendix

Table 13: Inference time per graph pair at

n=500

on a single laptop CPU core (seconds). The GPU timings of the chain are given by the Pareto curves of Figure 4 (a few seconds per pair).

ER 4 - noise	0.15	0.2	0.25	0.3	0.35
${\textbf{FAQ}}(D_{\text{cx}})$	15.6	31.4	25.8	24.2	25.6
ChFGNN FAQ	4.1	6.5	8.3	15.1	19.7

Appendix

Table 14: Average number of gradient projections ( Proj ) in the Frank-Wolfe algorithm FAQ , with initialization from either

D_{\text{cx}}

or the similarity matrix produced by the chained FGNNs.

		degree-normalized score		random order
$p_{\text{noise}}$	raw (trained)	at inference	retrained	at inference	retrained
0.15	0.951	0.941	0.952	0.914	0.947
0.20	0.928	0.751	0.924	0.346	0.802
0.25	0.884	0.272	0.840	0.092	0.331
0.30	0.440	0.081	0.465	0.040	0.097
0.35	0.033	0.023	0.033	0.017	0.027

Appendix

Table 15: Ranking ablations on sparse Erdős–Rényi graphs (

n{=}500

d{=}4

): accuracy with FAQ decoding on

30

fixed test pairs per noise level. Raw is the released chain, trained at

p_{\text{noise}}{=}0.22

with the raw score. At inference : the raw-trained chain run with the modified ranking. Retrained : a chain trained from scratch with the modified ranking at every stage, with the same architecture, data and chain length.

stage	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
raw score	.09	.18	.30	.43	.55	.66	.73	.77	.80	.82	.83	.84	.85	.86	.87
degree-normalized	.09	.17	.27	.37	.49	.59	.66	.71	.74	.76	.77	.79	.80	.81	.81
random order	.09	.12	.13	.15	.16	.18	.18	.19	.20	.21	.23	.23	.25	.26	.27

Appendix

Table 16: Per-stage validation accuracy ( Proj decoding, training noise

p_{\text{noise}}=0.22

, sparse Erdős–Rényi graphs) of chains trained with the raw score, the degree-normalized score and a random order. Stage

0

is the network

f

, which receives no ranking.

stage $k\to k{+}1$	acc@ $k$	correction (bottom half, wrong at $k$ )	retention (top half, correct at $k$ )
$0\to 1$	0.12	0.14 (1019/7123)	0.92
$1\to 2$	0.23	0.25 (1698/6937)	0.97
$2\to 3$	0.40	0.33 (2147/6506)	0.99
$3\to 4$	0.58	0.35 (1883/5422)	1.00
$5\to 6$	0.79	0.27 (815/2991)	1.00
$8\to 9$	0.88	0.11 (182/1671)	1.00

Appendix

Table 17: Correction and retention rates per stage of the released sparse chain at test noise

p_{\text{noise}}=0.2

(

30

test pairs). acc@

k

is the Proj accuracy of stage

k

; counts in parentheses are corrected nodes over bottom-half misassigned nodes.

Figure 5: Each line corresponds to chained FGNNs trained at a given level of noise and evaluated across all different level of noises. Performances are acc (in %) for sparse Erdős-Rényi graphs with Proj as post-processing.

Figure 6: Accuracy acc as a function of the noise level for correlated Erdős-Rényi random graphs with size $n=1000$ and average degree $d=3$ . Chained GNNs were trained at noise level $0.25$ and FAQ is used as the last step for the inference. The red curve labeled FAQ corresponds to ${\textbf{FAQ}}(D_{\text{cx}})$ and the blue curve labeled message passing are results from [ Muratori and Semerjian, 2024 ] . The dashed vertical line corresponds to the theoretical $p_{\text{algo}}=1-\sqrt{\alpha}$ above which no efficient algorithm is known to succeed.

Panel of Figure 7 — Figure 7: Left: Training chained GNNs. Each color corresponds to a different training and GNN: the first training (brown) reaches an accuracy below $0.1$ . The second training (magenta) uses as input the output of the first training and get an accuracy $\approx 0.15$ . The remaining trainings using the output of the previous training as input and reach higher and higher accuracy. Right top: acc bottom: nce . First Violin plot ( ${\bf\_faq}$ green) for FAQ , then all other Violin plots correspond to a different number of iterations $N_{\max}=0,1,\dots,9$ of the chaining procedure ( ${\bf\_gnn\_faq\_proj}$ blue with Proj and ${\bf\_gnn\_faq\_faq}$ orange with FAQ ).

	noise	0.4	0.45	0.5	0.55	0.6	0.65	0.7
	acc ${\textbf{Proj}}(D_{\text{cx}})$	0.3428	0.1956	0.1209	0.0815	0.0552	0.0411	0.0309
	acc ${\textbf{FAQ}}(D_{\text{cx}})$	1.0	0.9954	0.9531	0.6910	0.2621	0.0959	0.0225
	nce ${\textbf{Proj}}(D_{\text{cx}})$	3147.7	3000.0	2960.2	2945.8	2942.0	2942.4	2933.6
	nce ${\textbf{FAQ}}(D_{\text{cx}})$	4737.8	4622.8	4462.2	4056.1	3564.9	3408.0	3352.8
training 0.5	acc ChFGNN Proj	0.9994	0.9962	0.9639	0.7842	0.3400	0.1442	0.0737
	acc ChFGNN FAQ	1.0	1.0	1.0	0.9915	0.8949	0.5105	0.1267

Appendix

Table 18: Accuracy acc and number of common edges nce for Bernoulli graphs as a function of the noise

p_{\text{noise}}

Panel of Figure 8 — Figure 8: Bernoulli graphs: acc (top) and nce (bottom) as a function of the noise level. Chained FGNNs were trained at noise level $0.5$ . gnn (resp. gnn_faq ) for chained FGNNs with Proj (resp. FAQ ) as the last step. faq for ${\textbf{FAQ}}(D_{\text{cx}})$ and faq(p) for ${\textbf{FAQ}}(\pi^{\star})$ .

Noise	0.15	0.2	0.25	0.3	0.35
L+1=2	0.28 (+0.02)	0.15 (+0.02)	0.08 (+0.01)	0.04 (+0.01)	0.02 (+0.00)
L+1=6	0.59 (+0.01)	0.43 (+0.06)	0.21 (+0.11)	0.07 (+0.05)	0.03 (+0.01)
L+1=10	0.85 (+0.01)	0.72 (+0.06)	0.43 (+0.13)	0.11 (+0.19)	0.04 (+0.03)
L+1=14	0.91 (+0.00)	0.86 (+0.01)	0.57 (+0.13)	0.16 (+0.21)	0.04 (+0.04)
L+1=16	0.92 (+0.00)	0.88 (+0.01)	0.61 (+0.12)	0.19 (+0.26)	0.04 (+0.04)
#loop	15	23	88	91	73

Appendix

Table 19: Accuracy ( acc ) for sparse Erdős-Rényi graphs as a function of the number (

L+1

) of trained FGNNs. Parentheses report the gain from extending inference to

N_{\text{loop}}=60

loops instead of stopping after the

L+1

trained chain steps. Last line: number of loops for chained FGNNs as a function of the noise

p_{\text{noise}}

to get optimal nce (with a maximal

N_{\text{loop}}=100

Panel of Figure 9 — Figure 9: Sparse Erdős-Rényi graphs: acc (top) and nce (bottom) as a function of the noise level. Chained FGNNs were trained at noise level $0.25$ . gnn (resp. gnn_faq ) for chained FGNNs with Proj (resp. FAQ ) as the last step. faq for ${\textbf{FAQ}}(D_{\text{cx}})$ and faq(p) for ${\textbf{FAQ}}(\pi^{\star})$ .

Panel of Figure 10 — Figure 10: Sparse Erdős-Rényi graphs: acc (top) and nce (bottom) as a function of the number of iterations $L$ at inference.

ER 4 ( acc )	noise	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35
Baselines	${\textbf{Proj}}(D_{\text{cx}})$	98.0	97.3	90.3	59.3	23.3	9.1	4.0	2.0
	${\textbf{FAQ}}(D_{\text{cx}})$	98.0	97.5	96.3	94.6	72.9	13.0	3.7	1.7
training 0.05	ChFGNN Proj	97.9	97.3	94.3	67.1	12.5	6.72	3.70	2.13
	ChFGNN FAQ	97.9	97.5	96.2	72.9	43.5	10.8	4.04	1.69
training 0.10	ChFGNN Proj	97.9	97.5	96.1	91.6	35.4	7.24	4.03	2.36
	ChFGNN FAQ	97.9	97.5	96.4	94.0	38.6	12.3	4.73	1.91

Appendix

Table 20: Accuracy ( acc ) defined in ( 3 ) for sparse Erdős-Rényi graphs as a function of the noise

p_{\text{noise}}

. FGNN refers to the architecture in Section A.6 and ChFGNN to our chained FGNNs. Proj and FAQ are used to produce a permutation (from the similarity matrix computed).

ER 4 ( nce )	noise	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35
Baselines	${\textbf{Proj}}(D_{\text{cx}})$	997	950	853	499	195	130	115	112
	${\textbf{FAQ}}(D_{\text{cx}})$	997	950	898	847	723	504	487	485
training 0.05	ChFGNN Proj	997	950	885	630	116	95	87	83
	ChFGNN FAQ	997	950	898	761	607	495	485	481
training 0.10	ChFGNN Proj	997	950	897	828	370	99	90	86
	ChFGNN FAQ	997	950	899	845	606	501	487	483

Appendix

Table 21: Number of common edges ( nce ) defined in ( 3 ) for sparse Erdős-Rényi graphs as a function of the noise

p_{\text{noise}}

. FGNN refers to the architecture in Section A.6 and ChFGNN to our chained FGNNs. Proj and FAQ are used to produce a permutation (from the similarity matrix computed).

Panel of Figure 11 — Figure 11: Dense Erdős-Rényi graphs: acc (top) and nce (bottom) as a function of the noise level. Chained FGNNs were trained at noise level $0.24$ . gnn (resp. gnn_faq ) for chained FGNNs with Proj (resp. FAQ ) as the last step. faq for ${\textbf{FAQ}}(D_{\text{cx}})$ and faq(p) for ${\textbf{FAQ}}(\pi^{\star})$ .

ER 80 ( acc )	noise	0.1	0.15	0.2	0.25	0.3	0.35
Baselines	${\textbf{Proj}}(D_{\text{cx}})$		60.8	14.3	4.3	1.8	1.1
	${\textbf{FAQ}}(D_{\text{cx}})$				21.2	0.9	0.5
training 0.05	ChFGNN Proj	99.8	16.0	5.95	2.76	1.77	1.01
	ChFGNN FAQ			54.4	1.16	0.72	0.47
training 0.10	ChFGNN Proj		88.9	7.49	3.47	1.99	1.16
	ChFGNN FAQ		89.0	80.0	6.58	0.85	0.52

Appendix

Table 22: Accuracy ( acc ) defined in ( 3 ) for dense Erdős-Rényi graphs as a function of the noise

p_{\text{noise}}

. FGNN refers to the architecture in Section A.6 and ChFGNN to our chained FGNNs. Proj and FAQ are used to produce a permutation (from the similarity matrix computed).

ER 80 ( nce )	noise	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35
Baselines	${\textbf{Proj}}(D_{\text{cx}})$	19964	18987	17966	8700	3888	3646	3633	3624
	${\textbf{FAQ}}(D_{\text{cx}})$	19964	18987	17968	16990	15972	7922	6272	6276
training 0.05	ChFGNN Proj	19964	18987	17941	3794	3457	3421	3429	3411
	ChFGNN FAQ	19964	18987	17968	16990	11408	6244	6252	6253
training 0.10	ChFGNN Proj	19964	18987	17968	15479	3522	3459	3453	3449
	ChFGNN FAQ	19964	18987	17968	15811	13935	6681	6251	6257

Appendix

Table 23: Number of common edges ( nce ) defined in ( 3 ) for dense Erdős-Rényi graphs as a function of the noise

p_{\text{noise}}

. FGNN refers to the architecture in Section A.6 and ChFGNN to our chained FGNNs. Proj and FAQ are used to produce a permutation (from the similarity matrix computed).

Panel of Figure 12 — Figure 12: Regular graphs: acc (top) and nce (bottom) as a function of the noise level. Chained FGNNs were trained at noise level $0.1$ . gnn (resp. gnn_faq ) for chained FGNNs with Proj (resp. FAQ ) as the last step. faq for ${\textbf{FAQ}}(D_{\text{cx}})$ , faq(p) for ${\textbf{FAQ}}(\pi^{\star})$ , and p for ${\textbf{nce}}(\pi^{\star})$ .

Graph Matching

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

See all 38 papers

May 19, 2025

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

We propose a novel benchmarking methodology for graph neural networks (GNNs) based on the graph alignment problem, a combinatorial optimization task that generalizes graph isomorphism by aligning two unlabeled graphs to maximize overlapping edges. We frame this problem as a self-supervised learning task and present several methods to generate graph alignment datasets using synthetic random graphs and real-world graph datasets from multiple domains. For a given graph dataset, we generate a family of graph alignment datasets with increasing difficulty, allowing us to rank the performance of various architectures. Our experiments prove that there is an optimal task difficulty for having a statistically relevant ranking of different models and that, even on a structure-only task, anisotropic models perform better compared to isotropic ones. To further prove that our synthetic task capture meaningful information, we show its effectiveness for self-supervised GNN pre-training: the learned node embeddings can be leveraged as positional encodings by transformers for graph regression or can be used to reconstruct the full structure of the graph with

98\%

accuracy. To support reproducibility and further research, we provide an open-source Python package to generate graph alignment datasets and benchmark new GNN architectures. The source code is available at https://github.com/adrien-lagesse/graph-alignment-benchmark.

Adrien Lagesse, Marc Lelarge

INRIA, École Normale Supérieure - PSL, Paris, France.

Graph Neural Networks Synthetic Benchmark Generation Positional Encoding Graph Matching

Ask PDF

Mar 9, 2026

Towards Effective and Efficient Graph Alignment without Supervision

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.

Songyang Chen, Youfang Lin, Yu Liu +2

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

Graph Matching Graph Representation Learning Optimal Transport

Ask PDF

Jul 11, 2026

Scalable Optimal Transport Algorithm for Network Alignment

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.

Elaheh Hassani, Durga Mandarapu, Qi Yu +2

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

Graph Matching Sparse Matrix Multiplication Optimal Transport

Ask PDF

Abstract

Graph Matching

Explore similar work

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

Towards Effective and Efficient Graph Alignment without Supervision

Scalable Optimal Transport Algorithm for Network Alignment