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

Jun 20, 2026cs.LG

Early-Exit Graph Neural Networks for Link Prediction

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.

Roman Knyazhitskiy, Andrea Giuseppe Di Francesco

University of Cambridge · Sapienza University of Rome

Zero-Shot Link Prediction Graph Neural Networks Network Science Neural Network

Ask PDF

Apr 28, 2026cs.LG

Mini-Batch Class Composition Bias in Link Prediction

Prior work on node classification has shown that Graph Neural Networks (GNNs) can learn representations that transfer across graphs, when underlying graph properties are shared. For a fixed graph, one would then expect GNNs trained for link prediction to learn a representation consistent with that learnt for node classification. We show this intuition does not hold in the general case. Instead, we find popular link prediction models can learn a trivial mini-batch dependent heuristic, enabled by batch-normalisation layers, to solve the edge classification task. When correcting for this, we observe increased alignment of the network representation with node-class relevant features, suggesting the network has learnt a graph representation that better aligns with the underlying graph's properties. Our findings suggest that standard link prediction training may be leading us to overestimate link predictors' ability to learn a generalised representation of a graph that is consistent across tasks.

Kieran Maguire, Srinandan Dasmahapatra

University of Southampton School of Electronics and Computer Science

Graph Neural Networks Network Science Imbalanced Classification

Ask PDF

Sep 1, 2026cs.LG

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

Graph neural networks (GNN) based on message passing are provably no more powerful than the one-dimensional Weisfeiler--Leman colour-refinement test (1-WL): two graphs it cannot tell apart receive identical representations, however deep or wide the network. A common remedy augments node or edge features with precomputed structural descriptors, most often counts of a fixed small subgraph such as triangles or longer cycles, but such counts require committing in advance to the size of the substructure counted, a choice usually made blind to the data. We study a descriptor that avoids this choice. The edge-girth of an edge is the length of a shortest cycle through it, and its multiplicity is the number of such shortest cycles; together they form a per-edge invariant that reports cycles of arbitrary length, computable exactly by a single breadth-first search per edge. Injected into a gated message-passing architecture, EGAGNN, it reaches a test MAE a factor three below the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters; against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary counting cycles up to length eight, using twice as many channels, while a dictionary capped at length four performs no better than no structural information at all. On graph discrimination we prove a matching limitation: on graphs where every edge sees the same number of shortest cycles of the same length, the descriptor becomes constant and any model built on it collapses back to the 1-WL bound. This holds without exception across all 400 pairs of the BREC benchmark: not one of the 90 such pairs is distinguished.

Lilian Marey, Charlotte Laclau

LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

Graph Neural Networks Subgraphs Neural Network Molecular Property Prediction

Ask PDF