PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.34729v1cs.LGcs.GT

TL;DR

Automorphic nodes can receive indistinguishable GNN representations, while existing expressivity analyses are largely qualitative and misaligned with edge-level link prediction. The paper introduces an edge-orbit framework and EO-GNN, reporting gains of up to 42.36% in high-symmetry settings and 28.44% across real-world benchmarks.

  • Problem

    Existing GNN expressivity analyses are mainly node- or subgraph-level and qualitative, with few synthetic benchmarks that allow automorphism levels to be controlled.

    Source: §1 · p. 2

  • Method

    The paper formalizes WL-induced edge orbits and EAR, then proposes EO-GNN with automorphism-aware dropout and subgraph orbit-based aggregation.

    Source: §1 · p. 2, §3 · p. 3, §3.3 · p. 4

  • Results

    EO-GNN improves over the second-best model by up to 42.36% in high-symmetry settings and gains up to 28.44% across real-world benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The edge-level framework and EO-GNN are presented as better aligning GNN inductive biases with graph symmetries while improving empirical link prediction performance.

    Source: §6 · p. 10

    The theoretical framework assumes identical vertex representations; incorporating semantic embeddings and their interaction with structural signals remains future work.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Permutation-equivariant GNNs can assign identical representations to automorphic nodes, even when their semantic or positional roles differ, limiting link discriminability. The paper addresses gaps in existing expressivity analyses with an edge-level framework, a quantitative measure, and an automorphism-aware GNN design.

1 INTRODUCTION

  • In the encoder-decoder paradigm, permutation-equivariant GNNs produce node embeddings that are decoded into link probabilities, but automorphic nodes can receive identical representations despite distinct roles.The paper identifies this collapse as the Node Automorphism Problem, which degrades link discriminability.Source: §1 · pp. 1–2
  • Existing GNN expressivity analyses are mainly node- or subgraph-level, largely qualitative, and lack synthetic benchmarks with controllable automorphism levels.These limitations leave a gap between theoretical expressivity characterization and edge-centric link prediction.Source: §1 · p. 2
  • The paper introduces WL-induced edge orbits and the Edge Automorphism Ratio (EAR), then proposes EO-GNN with automorphism-aware dropout and subgraph orbit-based aggregation.The framework also uses synthetic benchmarks in which EAR is a tunable generation parameter.Source: §1 · p. 2
  • EO-GNN improves over the second-best model by up to 42.36% in high-symmetry settings and shows gains of up to 28.44% across real-world benchmarks.The paper evaluates on synthetic graphs spanning low to high automorphism levels and on diverse real-world networks.Source: §1 · p. 2

2 RELATED WORK

Related work discusses GNN expressivity through the Weisfeiler–Lehman hierarchy and related methods that incorporate pairwise structure or characterize message-passing link predictors.

2 RELATED WORK

  • Standard MPNNs are bounded by 1-WL for distinguishing non-isomorphic graphs, motivating extensions based on the higher-order k-WL hierarchy.The discussion also notes 2D-WL's use of pairwise structural features for link prediction.Source: §2 · p. 2
  • The related-work discussion includes unrolling distance, which analyzes MPNN generalization through aligned computation trees, and kϕ-kρ-m-WL, which characterizes encoder expressivity and structural neighborhood radius.The latter is described as unifying message-passing link predictors.Source: §2 · pp. 2–3
  • Table 1 is identified as a comparison of graph expressivity frameworks for GNNs.Source: Table 1 · p. 3

3 QUANTIFYING EDGE DISCRIMINABILITY: A THEORETICAL FRAMEWORK

The framework shifts expressiveness analysis to edge discrimination, using model-distinguishable link sets and EAR to characterize GNN link-prediction ambiguity.

3.1 NOTATION AND PRELIMINARIES

  • Graph automorphisms partition nodes into orbits whose members play identical structural roles.An automorphism relabels a graph’s vertices while preserving its edge set.Source: §3.1 · p. 3

3.2 FORMALIZING EDGE DISCRIMINATION

  • A WL-induced edge orbit groups node pairs by the multiset of their endpoints’ subgraph orbits; EM records distinguishable edge pairs and orders models by set inclusion.The endpoint multiset makes the grouping invariant to endpoint order.Source: §3.2 · p. 4

3.3 QUANTIFYING LINK AMBIGUITY: A QUANTITATIVE MEASURE

  • EAR measures the proportion of edges in non-singleton WL-induced edge orbits, optionally power-law-scaled to spread values across [0,1].The paper estimates edge orbits with 1-orbit-WL; its examples report EAR(G1) = 0.8 and EAR(G2) = 1.Source: §3.3 · pp. 4–5

3.4 CONNECTING EAR TO GNN PERFORMANCE

  • Automorphic edges on a Lobster graph show higher link-likelihood variance for a standard GNN, with means below the 0.5 detection threshold.The paper says these edges are therefore likely to be incorrectly predicted as negative links.Source: §3.4 · p. 5
  • At EAR = 0.88, all GNN variants underperform LINKX by up to 15% on synthetic graphs, and MixHop remains 15.3% below LINKX under strong symmetry.Figure 4b shows performance decay as EAR increases.Source: §3.4 · p. 5

4 LEARNING OVER INCREASING AUTOMORPHISM

The section develops orbit-aware dropout and aggregation to reduce automorphism-related indistinguishability, then combines them in EO-GNN’s link-prediction pipeline.

4.1 D1: AUTOMORPHISM-AWARE DROPOUT

  • D1 assigns node and edge dropout probabilities using subgraph-orbit sizes, perturbing structural symmetries; its theorem claims fewer repetitions than single-rate random dropout to distinguish equivalent nodes.The illustration also reports that node dropout preserves EAR while distinguishing half the vertices, and combining node and edge dropout improves expressiveness.Source: §4.1 · p. 6, §4 · p. 6

4.2 D2: SUBGRAPH ORBIT-BIASED AGGREGATION

  • D2 adds Gaussian noise to WL-based role embeddings, concatenates them with node features, and injects them into message passing to increase distance within automorphic neighborhoods while preserving separation from non-automorphic neighbors.The distance increase is expected under a standard deterministic GNN, and remains bounded by separation from non-automorphic neighbors.Source: §4.2 · pp. 6–7

4.3 EO-GNN: A FRAMEWORK FOR RELAXING EQUIVARIANCE IN LINK PREDICTION

  • EO-GNN integrates a standard GCN with D1 and D2 in three stages: orbit-hash precomputation, automorphism-aware message passing, and link prediction.The prediction stage combines pairwise and common-neighbor structure features.Source: §4.3 · p. 7

5 EMPIRICAL EVALUATION

Across synthetic and real-world evaluations, EO-GNN performs strongly, with its gains becoming more pronounced as structural automorphism increases.

5.1 EXPERIMENTAL SETUP

  • Evaluation covers seven real-world link-prediction benchmarks and semi-synthetic datasets with controllable EAR from 0.1 to 0.9, averaging results over five runs.Metrics include MRR, AUC, and Hits@K depending on the benchmark; within each dataset, methods use the same splits and metric.Source: §5.1 · p. 8

5.2 (RQ1) EFFECTIVENESS OF EO-GNN

  • EO-GNN consistently achieves the best AUC and MRR on synthetic benchmarks, reaching up to 99.7% with the lowest variance across automorphism levels.All baselines degrade as EAR rises, especially classical GNNs at EAR ≥0.7; Figure 6a shows mean test AUC over five runs for the top six models.Source: §5.2 · p. 8, Figure 6 · p. 8

5.3 (RQ2) ABLATION STUDY: SIGNIFICANCE OF DESIGN PRINCIPLES

  • At EAR ≥0.5, both D1 and D2 contribute; D1 improves MRR by 42.36% on Syn-Citeseer near EAR = 0.81, while removing D2 reduces average MRR by 26.28% on Syn-Cora and 10.09% on Syn-Citeseer.D1 reaches up to a 22.30% improvement on Syn-Cora at EAR = 0.8.Source: Figure 7 · p. 9

5.4 (RQ3) EVALUATION ON REAL-WORLD GRAPHS

  • EO-GNN achieves the strongest overall performance across Planetoid and OGB benchmarks; on Pubmed, it improves over SEAL by 19.49 MRR points (28.44%), while near-zero-EAR PPA and DDI show smaller gains.Table 2 reports real-data mean accuracy ± standard deviation across data splits.Source: §5.4 · p. 9, Table 2 · p. 9

6 CONCLUSION

The conclusion presents an edge-centric framework and EO-GNN as ways to align GNNs with graph symmetries in link prediction. Its theoretical analysis assumes identical vertex representations, while experiments indicate the findings remain valid with differing node features.

6 CONCLUSION

  • EO-GNN and the edge-centric framework align GNN inductive biases with graph symmetries and improve empirical link prediction performance.The conclusion presents edge orbits as an alternative to node-level symmetry frameworks.Source: §6 · p. 10
  • The theoretical framework assumes identical vertex representations, though experiments indicate its findings remain valid when node features differ.Extending the analysis to semantic embeddings and their interaction with structural signals remains future work.Source: §6 · p. 10

A NOMENCLATURE

B EXTENDED PRELIMINARY

  • A graph quotient partitions vertices into automorphic orbits under the graph’s automorphism group.Source: B EXTENDED PRELIMINARY · p. 17
  • A subgraph orbit captures local structural equivalence through isomorphic GNN-induced enclosing subgraphs, unlike a global orbit based on graph automorphisms.For a 1-layer GNN, nodes b and d share a subgraph orbit when their 1-hop enclosing subgraphs are structurally identical.Source: B EXTENDED PRELIMINARY · p. 17

C EXTENDED RELATED WORK

The related-work discussion distinguishes this paper’s edge-level, model-agnostic analysis from vertex-level expressivity comparisons and prior dropout strategies. The accompanying proofs establish automorphism-equivariant edge-orbit assignments and analyze how dropout parameters affect alteration success.

C EXTENDED RELATED WORK

  • Prior link-prediction methods use node labeling, structural priors, or manually extracted local structures; this work seeks a principled solution within permutation invariance.The passage also describes GCN-based encoders and simple decoders, and notes that vanilla GCNs cannot distinguish automorphic nodes.Source: C EXTENDED RELATED WORK · p. 17
  • Unlike kϕ-kρ-m-WL’s hierarchical comparison of aggregation and update designs, this framework measures indistinguishable edges model-agnostically, targeting real-graph automorphisms and link prediction.The passage identifies vertex-level measures as mismatched to the edge-level problem.Source: C EXTENDED RELATED WORK · p. 17
  • Automorphism-aware Dropout uses the WL automorphism prior to optimize dropout, unlike approaches aimed at other issues such as homophily optimization.The figure reports higher MRR for this method than the compared variants on the two synthetic datasets.Source: C EXTENDED RELATED WORK · pp. 17–18, Figure 9 · p. 18
  • Automorphism-aware Dropout achieves higher MRR than the compared dropout variants on syn-citeseer and syn-cora, with the figure attributing this to pruning automorphic edges.The comparison includes DropEdge, DropNode, DropPath, and AdaEdge.Source: Figure 9 · p. 18

D.1 PROOF FOR EDGE ORBIT EQUIVARIANCE

  • Under graph automorphisms, the WL-induced edge-orbit assignment is invariant; for permutations outside the automorphism group, that equality need not hold.The proof relies on automorphisms preserving subgraph orbits, while other permutations may fail to preserve enclosing subgraphs or map endpoint pairs to edges.Source: §D.1 · p. 18

D.2 DETAILED ANALYSIS OF THEOREM 4.1

  • The detailed analysis defines ϵ-sufficiency and ϵ-completeness and argues that a bounded number of alterations can yield embedding distinction with probability at least 1−σ.The qualitative analysis says increasing p decreases L, and p should increase with graph size at fixed |E| to maintain approximately stable success probability.Source: §D.2 · pp. 19–20

D.3 DETAILED ANALYSIS OF THEOREM 4.2

The analysis examines how standard GNN embeddings separate automorphic and non-automorphic neighbors of an automorphism-dominant node, then considers how D2 reduces that gap. It also outlines the synthetic-dataset generation and reporting setup.

D.3 DETAILED ANALYSIS OF THEOREM 4.2

  • In the stated lobster-graph setting, standard GNNs give an automorphism-dominant node greater average embedding distance to automorphic neighbors than to non-automorphic neighbors.Source: §D.3 · p. 20
  • A GNN equipped with D2 reduces the embedding-distance gap relative to a standard GNN.Source: §D.3 · p. 20
  • Degree gaps account for the average squared embedding distance, and most automorphic vertices have identical degrees except for two tail nodes.The passage specifies N_non-auto = 7 and says automorphic-neighbor degree differences are 3, or 1 for the tail node.Source: §D.3 · p. 21

F SYNTHETIC DATASETS: DETAILS

  • The synthetic-dataset details describe generating graphs from real Cora and Citeseer graphs and report the dataset-generation process, sources, baselines, and hyperparameters.Source: F SYNTHETIC DATASETS: DETAILS · p. 22

F.1 DETAILED RESULTS ON SEMI-SYNTHETIC BENCHMARKS

The semi-synthetic benchmarks are built from duplicated real graphs with added random edges, using generation parameters to control EAR. The supplied table captions identify reported metrics and EAR ranges but provide no result values.

F.1 DETAILED RESULTS ON SEMI-SYNTHETIC BENCHMARKS

  • The construction duplicates a Cora or Citeseer graph and adds uniformly random inter- and intra-copy edges; increasing their probabilities and edge count increases EAR.The parameters include inter-copy probability, intra-copy probability, introduced automorphic nodes, and the number of perturbed edges.Source: §F.1 · p. 22
  • The supplied figure captions identify Syn-Cora and Syn-Citeseer and a construction that changes automorphism in a real-world graph.Source: Figure 10 · p. 22, Figure 11
  • The supplied table captions describe Syn-Cora MRR results and Syn-Citeseer AUC results across datasets with varying EAR.The Syn-Citeseer captions specify EAR ranges [0.10, 0.57] and [0.65, 0.94]; no table values are provided here.Source: Table 5 · p. 23, Table 6 · p. 23, Table 7 · p. 24

G ABLATION STUDY IN DETAILS

The ablation materials compare methods on synthetic Citeseer and Cora across edge automorphism ratios, and report different performance patterns for D1 and D2 as automorphism varies.

H.1 SETUP

  • EO-GNN is trained with contrastive loss between predicted and ground-truth edge connections, while the MLP decoder uses the same loss.Baselines other than MLP use implementations from PyTorch Geometric [10].Source: §H.1 · pp. 25–26

G ABLATION STUDY IN DETAILS

  • Under high automorphism, D1 shows a larger performance gain, while D2 is more robust across varying automorphism levels.The synthetic Citeseer tables report mean MRR and standard deviation across EAR ranges of 0.10–0.57 and 0.65–0.94.Source: Table 9 · p. 25, Table 10 · p. 25, Figure 12 · p. 26

H.1 SETUP

  • The reported results use random edge splits of 80% training, 15% validation, and 5% test, with target links removed during training.Collab permits validation edges as test-time input, but validation edges are not used during training.Source: §H.1 · p. 26

H.2 HYPERPARAMETER TUNING

The appendix describes benchmark-specific hyperparameter tuning, a perfect-hash WL labeling procedure for nodes and edge orbits, and EO-GNN’s computational complexity.

H.2 HYPERPARAMETER TUNING

  • The ablation tables report mean MRR and standard deviation for synthetic Cora and Citeseer across varying EAR values.The supplied captions describe scope but do not provide cell values or identify winning methods.Source: Table 12 · p. 27, Table 13 · p. 27, Table 14 · p. 28
  • Hyperparameters were tuned separately for each method and benchmark; EO-GNN-1 and EO-GNN-2 tested dropout a ∈ {0, 0.5}, with best performance reported for a = 0.The Adam search included learning rates 10^-2, 10^-3, and 10^-4 and dropout rates 0, 0.1, 0.2, and 0.3.Source: §H.2 · pp. 26–27

I WL LABELING SCHEME WITH PERFECT HASH

  • WL labels are updated from each node’s previous label and its neighbors’ label multiset, with perfect hashing making equal labels equivalent to identical inputs.The described pass also hashes edges from the multiset of their endpoint node hashes to assign edge-orbit IDs.Source: I WL LABELING SCHEME WITH PERFECT HASH · p. 29
  • The WL pass preprocesses adjacency, aggregates neighbor information, computes node hashes, and derives edge-orbit hashes from endpoint hashes.Figure 13 illustrates the automorphism test approximated by Algorithm 1.Source: I WL LABELING SCHEME WITH PERFECT HASH · p. 29, Figure 13 · p. 30

J EO-GNN: TIME COMPLEXITY IN DETAIL

  • EO-GNN’s stated total complexity is O(|E| · K + L · (|V| · p^2 + |E| · p)), including WL labeling and L-layer feature encoding and aggregation.The text gives WL precomputation complexity O(|E| · K) and feature dimensionality p.Source: J EO-GNN: TIME COMPLEXITY IN DETAIL · p. 30

K REAL DATASETS: DETAILS

The real-dataset details characterize graphs through size and connectivity, locality, hierarchical structure, and degree-distribution statistics.

K REAL DATASETS: DETAILS

  • Graph size and local connectivity are described using node and edge counts, arithmetic degree, and average degrees of central nodes and their two-hop neighborhoods.Source: K REAL DATASETS: DETAILS · p. 31
  • Locality is characterized by transitivity, the fraction of possible triangles that exist, and the average clustering coefficient across nodes.The clustering coefficient measures the fraction of possible triangles through a node that actually exist.Source: K REAL DATASETS: DETAILS · p. 31
  • Hierarchical structure uses k-core fractions and degree distribution to calculate Gini and Coreness Gini, while scale-free structure is approximated from a power-law degree distribution.The stated power-law range is 2 < γ < 3.Source: K REAL DATASETS: DETAILS · p. 31

Related papers

Loading 2609.34729v1…