Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

Chen Shao; Donald Loveland; Tobias Käfer; Danai Koutra

cs.LGSep 28, 2026

Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

Authors: Chen Shao, Donald Loveland, Tobias Käfer, Danai Koutra

Organizations: Karlsruhe Institute of Technology Karlsruhe, Germany · Department of Computer Science University of Michigan Ann Arbor, MI, USA · Computer Science & Engineering University of Michigan Ann Arbor, MI, USA

Abstract

Graph Neural Networks (GNNs) are effective for learning node and link embeddings through permutation-equivariant aggregation. However, standard GNNs collapse automorphic nodes, i.e., those with identical structural roles (or orbits) into indistinguishable representations, leading to the node automorphism problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterize GNN expressiveness rely primarily on Weisfeiler-Lehman (WL) analyses, but these methods are typically qualitative and often misaligned with empirical results. To address this gap, we begin by introducing a novel quantitative framework to assess GNN expressiveness for link prediction. We first formalize edge-level automorphism through edge orbits, which capture the set of structural role pairs for nodes that share a link. Then, we introduce the edge automorphism ratio (EAR), a scalar metric that quantifies a GNN's ability to distinguish links in a given graph. We empirically demonstrate that EAR correlates strongly with performance, validating its practical benefit. Building on this insight, we design EDGE-ORBIT EQUIVARIANT GRAPH NEURAL NETWORK (EO-GNN), a GNN architecture that addresses automorphism collapse while preserving equivariance and incurring minimal computational overhead. EO-GNN accomplishes this through two core designs combined with WL-based node hashes: (i) automorphism-aware dropouts and (ii) subgraph orbit-biased aggregation. Empirical evaluations on synthetic and real graphs show improvements of up to 42.36% and 28.44%, respectively, in predicting links in scenarios with high automorphism.

Figures & tables

Method	Level	M-Agnostic	Invariance.	Quantification.	Alignment.
$1$ -WL [ 43 ]	node	✓	✓	✗	✗
$k$ -WL [ 5 ]	node	✓	✓	✗	✗
2D-WL [ 15 ]	edge	✗	✓	✗	✓
$k_{\phi}$ - $k_{\rho}$ - $m$ -WL [ 20 ]	edge	✗	✗	✓	✗
Homomorphism. [ 47 ]	subgraph	✓	✓	✓	✗
Unrolling Distance. [ 37 ]	node	✓	✓	✗	✗

Table 1: Graph Expressivity Frameworks for GNNs.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Symbols	Definitions
$\mathcal{H}=(\mathcal{V},\mathcal{E})$	graph $\mathcal{H}$ with nodeset $\mathcal{V}$ , edgeset $\mathcal{E}$
$\mathbf{A}$	$n\times n$ adjacency matrix of $\mathcal{H}$
$\mathbf{X}$	$n\times F$ node feature matrix of $\mathcal{H}$
$\mathbf{x}_{v}$	$F$ -dimensional feature vector for node $v$
$\mathbf{L}$	unnormalized graph Laplacian matrix
$\mathcal{G}/\text{Aut}(\mathcal{G})$	the quotient of the automorphism when it acts on the graph $\mathcal{G}$

Appendix

Table 3: Major symbols and definitions.

Benchmark Name	syn-cora	syn-citeseer
# Nodes	5416	6654
# Edges	10556 to 17549	9104 to 23098
automorphism $EAR$	[0, 0.1, $\ldots$ , 0.9]	[0, 0.1, $\ldots$ , 0.9]
Degree Range	1 to 168	1 to 107
Average Degree	3.89 to 6.48	2.73 to 6.94
Inter Prob.	0.1	0.1

Appendix

Table 4: Statistics for Synthetic Datasets

Method	0.19	0.30	0.37	0.51	0.60	0.71	0.81	0.83	0.90
GCN	$99.41{\scriptstyle\pm.23}$	$99.39{\scriptstyle\pm.09}$	$99.06{\scriptstyle\pm.22}$	$98.51{\scriptstyle\pm.35}$	$98.01{\scriptstyle\pm.45}$	$97.27{\scriptstyle\pm.42}$	$96.45{\scriptstyle\pm.57}$	$96.29{\scriptstyle\pm.67}$	$94.07{\scriptstyle\pm.86}$
GAT	$99.28{\scriptstyle\pm.16}$	$98.97{\scriptstyle\pm.23}$	$98.99{\scriptstyle\pm.13}$	$98.75{\scriptstyle\pm.20}$	$98.48{\scriptstyle\pm.25}$	$97.98{\scriptstyle\pm.22}$	$97.72{\scriptstyle\pm.50}$	$97.51{\scriptstyle\pm.50}$	$96.42{\scriptstyle\pm.39}$
GIN	$91.83{\scriptstyle\pm.70}$	$95.76{\scriptstyle\pm.78}$	$95.53{\scriptstyle\pm.59}$	$94.91{\scriptstyle\pm.90}$	$84.81{\scriptstyle\pm.14}$	$82.49{\scriptstyle\pm.14}$	$70.24{\scriptstyle\pm.78}$	$72.01{\scriptstyle\pm.96}$	$65.24{\scriptstyle\pm.38}$
GraphSAGE	$97.91{\scriptstyle\pm.62}$	$97.96{\scriptstyle\pm.57}$	$97.96{\scriptstyle\pm.60}$	$97.05{\scriptstyle\pm.85}$	$95.93{\scriptstyle\pm.93}$	$93.38{\scriptstyle\pm.99}$	$90.27{\scriptstyle\pm 1.93}$	$90.37{\scriptstyle\pm 2.24}$	$85.82{\scriptstyle\pm 2.03}$
MixHopGCN	$99.55{\scriptstyle\pm.17}$	$99.28{\scriptstyle\pm.09}$	$98.99{\scriptstyle\pm.13}$	$98.75{\scriptstyle\pm.20}$	$98.48{\scriptstyle\pm.25}$	$97.98{\scriptstyle\pm.22}$	$97.72{\scriptstyle\pm.50}$	$97.51{\scriptstyle\pm.50}$	$96.42{\scriptstyle\pm.39}$
ChebGCN	$98.41{\scriptstyle\pm.13}$	$98.19{\scriptstyle\pm.22}$	$97.82{\scriptstyle\pm.21}$	$96.56{\scriptstyle\pm.79}$	$96.76{\scriptstyle\pm.32}$	$94.09{\scriptstyle\pm.56}$	$91.18{\scriptstyle\pm 1.02}$	$86.24{\scriptstyle\pm 1.77}$	$84.88{\scriptstyle\pm 1.42}$

Appendix

Table 5: syn-cora : Mean metrics (MRR) and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

Method	0.19	0.30	0.37	0.51	0.60	0.71	0.81	0.83	0.90
GCN	$42.28{\scriptstyle\pm 11.15}$	$34.09{\scriptstyle\pm 8.75}$	$27.06{\scriptstyle\pm 5.83}$	$21.29{\scriptstyle\pm 6.17}$	$20.83{\scriptstyle\pm 3.29}$	$18.37{\scriptstyle\pm 3.90}$	$16.50{\scriptstyle\pm 3.50}$	$14.78{\scriptstyle\pm 4.48}$	$12.82{\scriptstyle\pm 3.91}$
GAT	$30.45{\scriptstyle\pm 6.74}$	$25.24{\scriptstyle\pm 7.63}$	$21.77{\scriptstyle\pm 7.00}$	$20.28{\scriptstyle\pm 5.60}$	$19.74{\scriptstyle\pm 9.83}$	$17.06{\scriptstyle\pm 6.54}$	$15.60{\scriptstyle\pm 3.41}$	$14.80{\scriptstyle\pm 4.85}$	$13.28{\scriptstyle\pm 3.10}$
GIN	$15.80{\scriptstyle\pm 2.59}$	$15.57{\scriptstyle\pm 5.25}$	$14.43{\scriptstyle\pm 3.99}$	$10.88{\scriptstyle\pm 4.81}$	$9.19{\scriptstyle\pm 3.93}$	$6.87{\scriptstyle\pm 4.00}$	$4.42{\scriptstyle\pm 3.89}$	$4.06{\scriptstyle\pm 3.72}$	$3.07{\scriptstyle\pm 3.30}$
GraphSAGE	$24.79{\scriptstyle\pm 8.27}$	$24.20{\scriptstyle\pm 4.74}$	$17.53{\scriptstyle\pm 5.70}$	$16.30{\scriptstyle\pm 5.24}$	$15.45{\scriptstyle\pm 3.57}$	$13.66{\scriptstyle\pm 4.13}$	$12.26{\scriptstyle\pm 5.25}$	$11.01{\scriptstyle\pm 3.77}$	$8.94{\scriptstyle\pm 2.54}$
MixHopGCN	$65.87{\scriptstyle\pm 14.64}$	$58.62{\scriptstyle\pm 11.24}$	$17.65{\scriptstyle\pm 29.31}$	$0.12{\scriptstyle\pm 0.00}$	$0.12{\scriptstyle\pm 0.00}$	$0.12{\scriptstyle\pm 0.00}$	$0.12{\scriptstyle\pm 0.00}$	$0.12{\scriptstyle\pm 0.00}$	$0.12{\scriptstyle\pm 0.00}$
ChebGCN	$28.71{\scriptstyle\pm 4.29}$	$24.71{\scriptstyle\pm 5.39}$	$21.38{\scriptstyle\pm 5.21}$	$21.01{\scriptstyle\pm 4.68}$	$19.82{\scriptstyle\pm 5.16}$	$16.75{\scriptstyle\pm 4.98}$	$15.35{\scriptstyle\pm 3.71}$	$10.26{\scriptstyle\pm 2.32}$	$9.77{\scriptstyle\pm 2.48}$

Appendix

Table 6: syn-cora : Mean Metrics (MRR) and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

$EAR$	0.10	0.18	0.28	0.38	0.48	0.57
GCN	$99.65{\scriptstyle\pm 0.08}$	$99.50{\scriptstyle\pm 0.14}$	$99.42{\scriptstyle\pm 0.16}$	$98.92{\scriptstyle\pm 0.24}$	$98.61{\scriptstyle\pm 0.33}$	$98.03{\scriptstyle\pm 0.22}$
GAT	$99.42{\scriptstyle\pm 0.14}$	$98.94{\scriptstyle\pm 0.32}$	$99.17{\scriptstyle\pm 0.14}$	$98.28{\scriptstyle\pm 0.71}$	$98.31{\scriptstyle\pm 0.74}$	$97.89{\scriptstyle\pm 1.07}$
GIN	$95.43{\scriptstyle\pm 1.10}$	$95.40{\scriptstyle\pm 0.71}$	$94.69{\scriptstyle\pm 1.14}$	$92.73{\scriptstyle\pm 0.79}$	$90.53{\scriptstyle\pm 1.34}$	$89.78{\scriptstyle\pm 1.16}$
GraphSAGE	$96.19{\scriptstyle\pm 2.00}$	$95.99{\scriptstyle\pm 1.77}$	$94.18{\scriptstyle\pm 1.73}$	$93.26{\scriptstyle\pm 3.49}$	$91.69{\scriptstyle\pm 2.63}$	$91.81{\scriptstyle\pm 2.91}$
MixHopGCN	$99.69{\scriptstyle\pm 0.06}$	$94.41{\scriptstyle\pm 1.60}$	$99.03{\scriptstyle\pm 0.25}$	$98.77{\scriptstyle\pm 0.07}$	$98.22{\scriptstyle\pm 0.27}$	$97.99{\scriptstyle\pm 0.23}$
ChebGCN	$97.59{\scriptstyle\pm 0.46}$	$97.76{\scriptstyle\pm 0.41}$	$97.20{\scriptstyle\pm 0.44}$	$94.90{\scriptstyle\pm 0.58}$	$92.50{\scriptstyle\pm 1.31}$	$88.75{\scriptstyle\pm 1.86}$

Appendix

Table 7: syn-citeseer : Mean metrics (AUC) and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

(1/2,

EAR\in[0.10,0.57]

). The best method per column is bolded.

$EAR$	0.65	0.77	0.81	0.88	0.94
GCN	$97.65{\scriptstyle\pm 0.47}$	$96.32{\scriptstyle\pm 0.56}$	$96.49{\scriptstyle\pm 0.74}$	$95.03{\scriptstyle\pm 1.60}$	$91.81{\scriptstyle\pm 2.05}$
GAT	$97.81{\scriptstyle\pm 0.41}$	$96.56{\scriptstyle\pm 1.26}$	$95.87{\scriptstyle\pm 1.41}$	$93.11{\scriptstyle\pm 4.54}$	$91.93{\scriptstyle\pm 2.09}$
GIN	$86.46{\scriptstyle\pm 2.00}$	$78.42{\scriptstyle\pm 1.10}$	$82.29{\scriptstyle\pm 1.19}$	$75.34{\scriptstyle\pm 1.54}$	$61.25{\scriptstyle\pm 1.04}$
GraphSAGE	$86.72{\scriptstyle\pm 4.49}$	$85.62{\scriptstyle\pm 5.20}$	$82.41{\scriptstyle\pm 6.02}$	$77.59{\scriptstyle\pm 3.97}$	$74.68{\scriptstyle\pm 5.96}$
MixHopGCN	$96.28{\scriptstyle\pm 0.44}$	$93.72{\scriptstyle\pm 0.76}$	$94.55{\scriptstyle\pm 0.52}$	$91.21{\scriptstyle\pm 1.95}$	$88.35{\scriptstyle\pm 3.18}$
ChebGCN	$84.72{\scriptstyle\pm 1.89}$	$79.21{\scriptstyle\pm 1.42}$	$76.92{\scriptstyle\pm 1.49}$	$72.16{\scriptstyle\pm 2.07}$	$68.81{\scriptstyle\pm 2.76}$

Appendix

Table 8: syn-citeseer : Mean metrics (AUC) and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

(2/2,

EAR\in[0.65,0.94]

). The best method per column is bolded.

$EAR$	0.10	0.18	0.28	0.38	0.48	0.57
GCN	$49.84{\scriptstyle\pm 4.78}$	$48.61{\scriptstyle\pm 13.29}$	$48.34{\scriptstyle\pm 10.77}$	$43.70{\scriptstyle\pm 10.66}$	$39.74{\scriptstyle\pm 9.66}$	$27.99{\scriptstyle\pm 7.70}$
GAT	$31.93{\scriptstyle\pm 8.23}$	$27.72{\scriptstyle\pm 7.61}$	$25.82{\scriptstyle\pm 4.77}$	$24.61{\scriptstyle\pm 6.22}$	$23.06{\scriptstyle\pm 3.30}$	$21.82{\scriptstyle\pm 8.21}$
GIN	$20.37{\scriptstyle\pm 3.99}$	$18.09{\scriptstyle\pm 4.48}$	$15.77{\scriptstyle\pm 2.23}$	$14.17{\scriptstyle\pm 3.56}$	$11.37{\scriptstyle\pm 2.29}$	$10.79{\scriptstyle\pm 2.36}$
GraphSAGE	$24.01{\scriptstyle\pm 15.47}$	$20.28{\scriptstyle\pm 12.22}$	$20.13{\scriptstyle\pm 10.96}$	$16.45{\scriptstyle\pm 4.91}$	$15.82{\scriptstyle\pm 5.18}$	$12.57{\scriptstyle\pm 5.13}$
MixHopGCN	$70.99{\scriptstyle\pm 27.71}$	$52.17{\scriptstyle\pm 4.79}$	$51.84{\scriptstyle\pm 9.30}$	$43.61{\scriptstyle\pm 6.49}$	$39.02{\scriptstyle\pm 2.52}$	$36.87{\scriptstyle\pm 10.14}$
ChebGCN	$28.40{\scriptstyle\pm 6.49}$	$27.45{\scriptstyle\pm 5.14}$	$27.07{\scriptstyle\pm 10.19}$	$23.05{\scriptstyle\pm 3.27}$	$22.76{\scriptstyle\pm 4.13}$	$15.23{\scriptstyle\pm 4.23}$

Appendix

Table 9: syn-citeseer : Mean MRR and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

(1/2,

EAR\in[0.10,0.57]

). The best method per column is bolded.

$EAR$	0.65	0.77	0.81	0.88	0.94
GCN	$21.32{\scriptstyle\pm 4.65}$	$20.78{\scriptstyle\pm 3.08}$	$18.08{\scriptstyle\pm 3.87}$	$13.18{\scriptstyle\pm 2.00}$	$10.56{\scriptstyle\pm 2.93}$
GAT	$21.16{\scriptstyle\pm 4.89}$	$19.10{\scriptstyle\pm 4.48}$	$14.75{\scriptstyle\pm 2.74}$	$13.61{\scriptstyle\pm 5.15}$	$10.22{\scriptstyle\pm 1.75}$
GIN	$10.45{\scriptstyle\pm 1.82}$	$9.61{\scriptstyle\pm 3.08}$	$7.51{\scriptstyle\pm 3.36}$	$5.91{\scriptstyle\pm 2.72}$	$2.82{\scriptstyle\pm 2.89}$
GraphSAGE	$10.61{\scriptstyle\pm 5.20}$	$10.56{\scriptstyle\pm 5.06}$	$10.34{\scriptstyle\pm 3.02}$	$6.89{\scriptstyle\pm 2.12}$	$5.16{\scriptstyle\pm 2.18}$
MixHopGCN	$36.12{\scriptstyle\pm 4.80}$	$35.69{\scriptstyle\pm 9.47}$	$34.84{\scriptstyle\pm 6.12}$	$25.08{\scriptstyle\pm 11.08}$	$14.32{\scriptstyle\pm 2.42}$
ChebGCN	$12.33{\scriptstyle\pm 3.00}$	$8.83{\scriptstyle\pm 2.23}$	$7.57{\scriptstyle\pm 2.49}$	$7.09{\scriptstyle\pm 0.94}$	$4.81{\scriptstyle\pm 0.62}$

Appendix

Table 10: syn-citeseer : Mean MRR and standard deviation for each method on synthetic datasets with varying automorphism ratios

EAR

(2/2,

EAR\in[0.65,0.94]

). The best method per column is bolded.

Method	0.19	0.30	0.37	0.51	0.60	0.71	0.81	0.83	0.90
Proposed w.o. D1	$99.89{\scriptstyle\pm 0.08}$	$99.83{\scriptstyle\pm 0.10}$	$99.77{\scriptstyle\pm 0.11}$	$99.76{\scriptstyle\pm 0.07}$	$99.76{\scriptstyle\pm 0.05}$	$99.74{\scriptstyle\pm 0.07}$	$99.67{\scriptstyle\pm 0.12}$	$99.63{\scriptstyle\pm 0.07}$	$99.62{\scriptstyle\pm 0.22}$
Proposed w.o D2	$99.90{\scriptstyle\pm 0.05}$	$99.80{\scriptstyle\pm 0.05}$	$99.79{\scriptstyle\pm 0.07}$	$99.78{\scriptstyle\pm 0.12}$	$99.75{\scriptstyle\pm 0.03}$	$99.74{\scriptstyle\pm 0.07}$	$99.73{\scriptstyle\pm 0.04}$	$99.71{\scriptstyle\pm 0.03}$	$99.90{\scriptstyle\pm 0.05}$
Proposed	$99.94{\scriptstyle\pm 0.03}$	$99.86{\scriptstyle\pm 0.03}$	$99.83{\scriptstyle\pm 0.07}$	$99.81{\scriptstyle\pm 0.00}$	$99.80{\scriptstyle\pm 0.05}$	$99.78{\scriptstyle\pm 0.04}$	$99.76{\scriptstyle\pm 0.03}$	$99.74{\scriptstyle\pm 0.07}$	$99.93{\scriptstyle\pm 0.08}$

Appendix

Table 11: Ablation study showing the effect of different components. Mean metrics (MRR) and standard deviation for each method on synthetic Cora with varying automorphism ratios

EAR

Method	0.19	0.30	0.37	0.51	0.60	0.71	0.81	0.83	0.90
Proposed w.o. D1	$85.53{\scriptstyle\pm 14.99}$	$80.43{\scriptstyle\pm 12.34}$	$65.46{\scriptstyle\pm 4.98}$	$62.64{\scriptstyle\pm 20.27}$	$60.10{\scriptstyle\pm 10.21}$	$49.77{\scriptstyle\pm 12.52}$	$41.64{\scriptstyle\pm 3.52}$	$38.49{\scriptstyle\pm 12.70}$	$34.89{\scriptstyle\pm 5.32}$
Proposed w.o D2	$97.42{\scriptstyle\pm 1.74}$	$58.13{\scriptstyle\pm 11.50}$	$54.20{\scriptstyle\pm 17.44}$	$49.86{\scriptstyle\pm 7.44}$	$49.43{\scriptstyle\pm 10.93}$	$45.12{\scriptstyle\pm 5.11}$	$38.35{\scriptstyle\pm 4.47}$	$35.64{\scriptstyle\pm 4.88}$	$32.47{\scriptstyle\pm 7.89}$
Proposed	$90.78{\scriptstyle\pm 7.34}$	$84.41{\scriptstyle\pm 1.87}$	$66.53{\scriptstyle\pm 14.99}$	$64.51{\scriptstyle\pm 20.85}$	$62.30{\scriptstyle\pm 10.83}$	$57.83{\scriptstyle\pm 2.04}$	$52.14{\scriptstyle\pm 13.77}$	$47.36{\scriptstyle\pm 6.13}$	$45.83{\scriptstyle\pm 3.30}$

Appendix

Table 12: Ablation study showing the effect of different components. Mean metrics (MRR) and standard deviation for each method on synthetic Cora with varying automorphism ratios

EAR

$EAR$	0.10	0.18	0.28	0.38	0.48	0.57
Proposed w.o. D1	$99.89{\scriptstyle\pm 0.08}$	$99.83{\scriptstyle\pm 0.10}$	$99.77{\scriptstyle\pm 0.11}$	$99.76{\scriptstyle\pm 0.07}$	$99.76{\scriptstyle\pm 0.05}$	$99.74{\scriptstyle\pm 0.07}$
Proposed w.o D2	$99.90{\scriptstyle\pm 0.05}$	$99.80{\scriptstyle\pm 0.05}$	$99.79{\scriptstyle\pm 0.07}$	$99.78{\scriptstyle\pm 0.12}$	$99.75{\scriptstyle\pm 0.03}$	$99.74{\scriptstyle\pm 0.07}$
Proposed	$99.94{\scriptstyle\pm 0.03}$	$99.86{\scriptstyle\pm 0.03}$	$99.83{\scriptstyle\pm 0.07}$	$99.81{\scriptstyle\pm 0.00}$	$99.80{\scriptstyle\pm 0.05}$	$99.78{\scriptstyle\pm 0.04}$

Appendix

Table 13: Ablation study showing the effect of different components. Mean metrics (MRR) and standard deviation for each method on synthetic Citeseer with varying automorphism ratios

EAR

$EAR$	0.10	0.18	0.28	0.38	0.48	0.57
Proposed w.o. D1	$83.40{\scriptstyle\pm 11.40}$	$71.65{\scriptstyle\pm 12.54}$	$69.35{\scriptstyle\pm 12.85}$	$67.94{\scriptstyle\pm 12.46}$	$64.67{\scriptstyle\pm 8.23}$	$64.18{\scriptstyle\pm 7.58}$
Proposed w.o D2	$79.99{\scriptstyle\pm 12.23}$	$76.28{\scriptstyle\pm 7.76}$	$72.20{\scriptstyle\pm 16.27}$	$66.62{\scriptstyle\pm 12.13}$	$66.62{\scriptstyle\pm 12.13}$	$66.62{\scriptstyle\pm 12.13}$
Proposed	$85.72{\scriptstyle\pm 5.57}$	$83.02{\scriptstyle\pm 6.87}$	$74.85{\scriptstyle\pm 7.60}$	$72.06{\scriptstyle\pm 5.95}$	$68.64{\scriptstyle\pm 4.59}$	$67.42{\scriptstyle\pm 10.02}$

Appendix

Table 14: Ablation study showing the effect of different components. Mean MRR and standard deviation for each method on synthetic Citeseer with varying automorphism ratios

EAR

Explore similar work

Early-Exit Graph Neural Networks for Link Prediction
Jun 20, 2026Roman Knyazhitskiy, Andrea Giuseppe Di FrancescoEfficient Neural Network Inference Graph Neural Networks
University of Cambridge · Sapienza University of Rome
Mini-Batch Class Composition Bias in Link Prediction
Apr 28, 2026Kieran Maguire, Srinandan DasmahapatraGraph Representation Learning Link Prediction
University of Southampton School of Electronics and Computer Science
Edge-Girth as a Structural Edge Feature for Graph Neural Networks
Sep 1, 2026Lilian Marey, Charlotte LaclauGraph Neural Networks Graph Representation Learning
LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

Jun 20, 2026, cs.LGJ/K move · Enter open · S save

Early-Exit Graph Neural Networks for Link Prediction

Roman Knyazhitskiy, Andrea Giuseppe Di Francesco

University of Cambridge · Sapienza University of Rome

Efficient Neural Network Inference Graph Neural Networks Link Prediction Early-Exit Neural Networks

Open paper AskPDF arXiv

Graph Neural Networks are great for link prediction in various network-like structures; however, the question of their speed/quality tradeoff has been barely studied. While in practice the time it takes to do inference matters little for small benchmarks, the latency does limit applicability in large-scale domains. In this work, we explore early-exiting strategies that can be applied to Graph Neural Networks to solve the problem of link-prediction faster. We use no auxiliary losses to enforce early exiting, allowing it to emerge as an implicit property of the architecture. We show that our method enables early exiting in several setups, moving the Pareto frontier on the HeaRT benchmark for GCN and SAS-GNN backbones. Our findings show that inference speed of GNNs on many link-prediction problems can be improved, while losing little, or even winning in terms of prediction quality. The code is available in our repository: https://github.com/knyazer/link_prediction.

Abstract

Explore similar work

Early-Exit Graph Neural Networks for Link Prediction

Mini-Batch Class Composition Bias in Link Prediction

Edge-Girth as a Structural Edge Feature for Graph Neural Networks