acceptodds
Under review as a conference paper at ICLR 2027

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

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 non-automorphic problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterizing 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 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 19.49%, respectively, in predicting links in scenarios with high automorphism.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Link Prediction, Network Science, Representation Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FfHNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper utilized the extended concept of edge-level automorphism to improve both theoretical analyses (with WL-induced edge orbit) and algorithmic techniques (with D1: automorphism-aware dropout and D2: subgraph orbit-biased aggregation) in GNNs. Experiments showed the relatedness between the edge automorphism ratio and GNN performence, and validated the effectiveness of D1 and D2.

Critical strengths
  1. Technical soundness. The theoretical concepts are well rooted and rigorously developed. For example, on how node-level autoporphism is adapted to edge-level automorphism. Besides, the techniques are effective with improvements on main-stream GNN baselines and datasets.
  2. Presentation Clarity. The clarity can further improved if the calculation process of WL-induced edge orbit are showcased by specific examples. For example, it can be explained in detail how the left picture in Figure 3 is plotted using the definition. Besides, the concept of WL test should be explained considering readers not familiar in this field.
Critical weaknesses
  1. No broader significance. This paper is more suited to domain-specific conference such as LoG (Learning on Graph Conference) with its current demonstration.
  2. No deeper insight. The developed contributions are solid but well expected and too normal for the top AI conference of ICLR.
Questions for authors
  1. On broader significance. Why is edge-level automorphism significant ? The significance does not naturally comes from its mathematical analogy to node-level automorphism. Instead, it should be thoroughly investigated on what specific real-world network types exhibit these properties and sharply analyzed on how it relates to the link prediction problem.
  2. On deeper insight. Is edge-level automorphism complementary to node-level automorphism ? If so, this conclusion should not stay at the shallow surface of definition similarity. Instead, it can be theoretically analyzed on how the combination of edge-level automorphism and node-level automorphism contributes to some complete expressiveness. Besides, the exclusivity between these two automorphisms may also inspire deeper theretical conclusions.

I will consider raising my score only when the above points are addressed satisfactorily.

1 comment

We thank the reviewer for the constructive feedback and for acknowledging the soundness of our theory. We address each point below.

Significance of edge-level: The fundamental importance of edge-level automorphism lies in its ability to detect failures that node-level analysis cannot detect. For instance, all nodes of the triangular prism are equivalent from the node perspective; however, from the edge perspective, the triangle edges and the rung edges are structurally entirely different. Any analysis derived from the node level cannot preserve edge-level problems. From the task perspective, there is likewise no proven strong correlation between node classification and link prediction. We consider this to be the core reason why edge-level research requires an independent theoretical framework and measure to move forward.

Relationship with node-level: We believe node- and edge-level automorphisms are complementary and logically independent, i.e., neither level of symmetry can be derived from the other. We use two simple counterexamples to show this.

The first is the triangular prism discussed above. So all vertices being structurally identical at the node level does not imply that everything is the same at the edge level.

The second example goes in the opposite direction. In the complete bipartite graph K2,3K_{2,3}, all edges are equivalent (the graph is edge-transitive), but the nodes on the two sides are not, as they do not even have the same degree. Here, the edges are indistinguishable while the nodes are not.

Taken together, we argue that vertex-transitivity and edge-transitivity are independent properties. We believe this further supports the need to study edge-level tasks in their own right.

We thank the reviewer for raising this important question again.

Reviewer_wB84OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper showed that GNNs assign identical embeddings to automorphic nodes, which limits their expressive power in link prediction. To quantify this, the authors proposed the Edge Automorphism Ratio (EAR), the fraction of edges indistinguishable under WL-induced edge orbits. They then introduced EO-GNN, which adds automorphism-aware dropout and orbit-biased aggregation to a standard GCN. Each module was supported by a theorem, and the method was validated on synthetic graphs with controlled EAR and on seven real-world benchmarks, with ablation studies.

Critical strengths
  1. A principled edge-level metric for expressivity: By introducing WL-induced edge orbits and EAR, the paper moved expressivity analysis from the node to the edge level and from qualitative to quantitative. This yielded a model-agnostic measure that quantifies a graph's automorphism before training.

  2. Empirical validation with controllable EAR: Synthetic benchmarks with tunable EAR showed that several GNNs (e.g., GCN, SAGE) degrade as EAR rises (Fig. 4b), while EO-GNN stays robust (Fig. 6). This directly links the metric to performance.

Critical weaknesses
  1. Insufficient justification and empirical characterization of EAR: Although EAR provides a useful quantitative measure of edge-level structural ambiguity, its relationship with GNN expressivity and link prediction performance was not sufficiently clarified. First, EAR was computed using WL initialized with constant node features (X=1), even for attributed graphs. Since node features can distinguish structurally equivalent nodes, it remains unclear to what extent EAR captures the expressivity limitations of feature-aware GNNs. Second, Fig. 4b showed that ChebGCN and GAT exhibit relatively robust performance as EAR increases, unlike GCN and SAGE. In particular, the behavior of GAT, which is also bounded by 1-WL, deserves further explanation. Moreover, the real-world results in Table 2 indicated that a lower EAR does not necessarily correspond to better link prediction performance (e.g., Cora vs. Citation2). These observations warrant a more careful discussion of what EAR measures and how reliably it reflects the practical difficulty of link prediction.

  2. Limited direct evidence of improved edge discrimination and comparison with more expressive baselines: Although EO-GNN achieves promising link prediction performance, the experiments provided limited direct evidence that the improvements stem from its ability to distinguish edges within the same WL-induced edge orbit. In particular, it remains unclear whether EO-GNN can effectively discriminate between positive and negative links that share the same edge-orbit signature, which is central to the paper's motivation. Furthermore, the empirical comparisons did not appear to include higher-order WL-based models, such as PPGN or 2-WL-based link predictors, which can potentially overcome some limitations of 1-WL expressivity. Without such comparisons or a more direct analysis of edge discrimination, it is difficult to fully assess the extent to which EO-GNN addresses the proposed automorphism problem beyond improving overall prediction accuracy.

Questions for authors
  1. EAR computation and node features: EAR was computed using WL initialized with (X=1), even for attributed graphs. Could the authors clarify the rationale for excluding node features and discuss how feature-aware WL initialization might affect EAR and its relationship with GNN expressivity?

  2. Performance trends under increasing EAR: In Fig. 4b, ChebGCN and GAT appear relatively robust as EAR increases, whereas GCN and SAGE exhibited substantial degradation. Since GAT was also bounded by 1-WL, could the authors explain these different performance trends? Additionally, Table 2 showed that Cora (EAR = 0.139) generally achieves lower MRR than Citation2 (EAR = 0.311). How should EAR be interpreted in relation to prediction difficulty across different datasets?

  3. Direct evidence of edge discrimination: Could the authors provide an analysis similar to Fig. 4a for EO-GNN, focusing on whether the proposed method can distinguish positive and negative links within the same WL-induced edge orbit? Such an analysis would help establish whether the performance improvements directly result from enhanced edge discrimination.

  4. Comparison with higher-order WL-based models: Since the paper was motivated by the expressivity limitations of 1-WL, could the authors compare EO-GNN with more expressive models, such as PPGN (Maron et al., NeurIPS 2019) or the 2-WL link prediction model [15], at least on small synthetic graphs with varying EAR? This would help clarify the advantages of EO-GNN relative to existing approaches for overcoming 1-WL limitations.

  5. Prediction decoder: In Eq. (6), why is ReLU used rather than Sigmoid for link prediction? Is an additional prediction layer applied to produce the final link probability or score? Clarify the decoder architecture.

  6. Architectural overview (suggestion): An overview figure illustrating how D1, D2, and the prediction decoder are integrated into EO-GNN would improve the clarity of the proposed framework, even if included in the appendix.

  7. Minor presentation issues: Provide explicit references to the Appendix D proofs of Theorems 4.1 and 4.2 in the main text. Also, the unresolved references ("Appendix ??") for the vertex-level and edge-level automorphism measures on page 16 should be corrected.

4 comments
AuthorsOpenReview ↗

Response 1: Position of EAR measure

We thanks for reviewer for the detailed feedback.

Relationship between EAR and empirical performance. We would like to clarify the motivation behind EAR: it characterizes the level of automorphism inherent in the graph itself, rather than imposing a hard expressivity bound on link prediction. Specifically, EAR measures the fraction of existing edges that share the same WL-induced edge-orbit signature with other edges; such edges receive and pass identical messages during message passing. In this sense, EAR can be viewed as an edge-level quantification of the automorphic node problem identified in SEAL and BUDDY. We therefore do not claim that EAR is equivalent to empirical prediction difficulty. In link prediction, difficulty also depends on the data split, the negative sampling strategy, and the evaluation metric, none of which are properties of the graph structure itself.

Different trends of ChebGCN/GAT and GCN/SAGE in Fig. 4b. We would like to clarify that the 1-WL upper bound and performance degradation are not the same thing, and that the robustness of GAT and ChebGCN does not contradict the 1-WL bound. We use the same constant node features (X=1) for all models in order to isolate architectural effects. All GNNs in Fig. 4b share the same 1-WL upper bound, but how much their performance degrades below this bound depends on their aggregation mechanisms. GCN and SAGE use fixed-weight or mean aggregation, which makes them sensitive to neighbor multiplicity. In contrast, GAT can adaptively reweight neighbors based on their representations, potentially reducing the dominance of redundant messages. ChebGCN uses polynomial filters of order K=3, so each layer aggregates information from a 3-hop neighborhood. An L-layer ChebGCN therefore covers 3L hops, while GCN and SAGE cover only L hops. This brings ChebGCN closer to the stable WL coloring, which separates more edges. This is in line with our argument about D2 in our response to Reviewer SNen.

Cora vs. Citation2 (Table 2). We agree that a lower EAR does not necessarily correspond to better link prediction performance, and this is consistent with our positioning of EAR. EAR measures the structural ambiguity in the graph itself; in practice, a low EAR does not mean that the task is easy. Cora and Citation2 illustrate this well. Citation2 ranks each positive pair against 1,000 fixed negatives and provides a training graph that is several orders of magnitude larger, whereas Cora uses a random split with an equal number of positive and negative links. Differences in MRR between the two datasets therefore mainly reflect these factors, not structural ambiguity.

  • SEAL: Zhang & Chen. Link Prediction Based on Graph Neural Networks. NeurIPS 2018.
  • BUDDY: Chamberlain et al. Graph Neural Networks for Link Prediction with Subgraph Sketching. ICLR 2023.
Reviewer_wB84OpenReview ↗

Further comments

Thank you for the response. The authors' explanations partially addressed some concerns, amd most questions remain unanswered.

Q1. The central concern is how EAR, computed solely from graph structure, reflects the expressivity limitations of GNNs utilizing node features. This fundamental question remains unanswered.

Q2. The explanation regarding GAT's adaptive attention is reasonable. However, for ChebGCN, a larger receptive field does not necessarily imply closer approximation to stable WL coloring; its spectral filtering capability may provide a more appropriate explanation. Moreover, differences in evaluation protocols do not sufficiently explain the inconsistent relationship between EAR and prediction performance.

Q3. An analysis similar to Fig. 4a was requested to verify whether the trained EO-GNN actually mitigates the edge indistinguishability problem. Neither the requested analysis nor even a basic explanation for its absence was provided.

Q4. The request for comparisons with higher-order WL-based models remains unanswered, without even a basic explanation.

Q5. The question regarding the ReLU-based prediction decoder remains unanswered, despite requiring only a brief clarification.

Q6-Q7. The architectural overview suggestion and minor presentation issues were also left unanswered.

As most concerns remain unresolved despite the authors' response, the original rating is maintained.

AuthorsOpenReview ↗

Response 2: Evidence of improved edge discrimination

Comparison with more expressive baselines. Following the reviewer's suggestion, we compare EO-GNN with PPGN (Maron et al., 2019), whose expressive power is equivalent to 3-WL.

ModelCoraCiteseerPubmed
GCN34.19 ± 6.2344.37 ± 6.0614.55 ± 2.41
PPGN (3-WL)43.15 ± 6.2341.96 ± 2.09OOM
EO-GNN (ours)50.02 ± 5.8362.88 ± 1.4568.51 ± 0.74

MRR, mean ± std over 5 seeds. OOM: out of memory on an H100 with 93.6 GB.

PPGN improves over GCN on Cora but falls behind it on Citeseer, and it already runs out of memory on Pubmed, which has only 19.7k nodes. Because PPGN maintains a representation for every node pair, which requires O(n²) memory and O(n³) time per layer, so it cannot be applied to the OGB datasets at all. EO-GNN outperforms PPGN on both datasets where PPGN can run.

More broadly, our paper compares EO-GNN with a wide range of models on both synthetic and real-world benchmarks (Sec. 5, Fig. 6). On the synthetic benchmarks, GCN combined with expressive positional encodings and methods using structural features are the most expressive models; on real-world datasets, GCN with structural features remains a strong baseline. We aim to show in this work, EO-GNN with two lightweight modules, D1 and D2, designed specifically for edge automorphism, to a standard GCN yields consistently more robust performance, and our real-world results confirm this.

Evidence of edge discrimination. We thank the reviewer for this question. Our main evidence comes from the semi-synthetic benchmark in Sec. 5, where we control the level of automorphism directly. There, EO-GNN maintains its performance as automorphism increases, and the same trend holds on real-world graphs. We provide this evidence for each module separately below.

D1. Theorem 4.1 shows that dropout helps distinguish automorphic edges, and that our automorphism-aware dropout does so in fewer iterations. Empirically, Fig. 9 compares D1 with all previous dropout modules: dropout in general helps distinguish automorphic edges, and D1 performs best because it targets automorphic edges specifically.

D2. Following the same methodology, we analyze D2 both theoretically and empirically in terms of how well it distinguishes automorphic neighborhoods.

In addition, Reviewer SNen asked for more direct evidence of D2's contribution, and we share that analysis here. D2 has two complementary components. Emb(o_u) encodes each node's global structural role in the graph. ε_u breaks the remaining symmetry within an orbit and provides discriminative power beyond WL, but carries no structural information by itself. The following ablation, which combines results from the paper with new experiments, shows that both components are necessary:

VariantEmb(o_u)ε_uCiteseer (MRR)Pubmed (MRR)
w/o D2✗✗40.28 ± 2.6236.25 ± 6.56
Random Only✗✓32.75 ± 4.8738.25 ± 8.20
Orbit Only✓✗50.42 ± 1.8752.51 ± 1.28
Full D2 (EO-GNN)✓✓62.88 ± 1.4568.51 ± 0.74

Setting: 85/5/10 split with split seed 2025; results averaged over 10 random seeds.

Observations. (1) Random features alone do not help link prediction, although they are effective for node and graph classification (Sato et al., 2021; Abboud et al., 2021): Random Only performs on par with w/o D2 on Pubmed and falls about 7 points below it on Citeseer, with substantially higher variance. (2) The orbit embedding is the main source of improvement: Orbit Only improves over w/o D2 by about 10 points on Citeseer and 16 points on Pubmed, while also reducing variance. (3) The two components are complementary: adding ϵu\epsilon_u on top of the orbit embedding brings a further gain of about 12 points on Citeseer and 16 points on Pubmed, even though ϵu\epsilon_u alone does not help. This confirms that ϵu\epsilon_u is useful precisely for breaking symmetry within orbits, once the orbit embedding has supplied the structural role.

  • Maron, Ben-Hamu, Serviansky & Lipman. Provably Powerful Graph Networks. NeurIPS 2019.
  • Sato, Yamada & Kashima. Random Features Strengthen Graph Neural Networks. SDM 2021.
  • Abboud, Ceylan, Grohe & Lukasiewicz. The Surprising Power of Graph Neural Networks with Random Node Initialization. IJCAI 2021.
AuthorsOpenReview ↗

Response 3: Minor clarifications

Prediction decoder Thank you for pointing this out. The ReLU in Eq. (6) is the hidden activation of a two-layer MLP decoder, not the output activation. Concretely, the decoder computes suv=W2 ReLU(W1(hu⊙hv)+b1)+b2s_{uv} = W_2 \, \mathrm{ReLU}(W_1 (h_u \odot h_v) + b_1) + b_2 where ⊙\odot denotes the element-wise product, and the final linear layer outputs a scalar logit σ(suv)\sigma(s_{uv}). During training, we apply the sigmoid inside the binary cross-entropy loss (i.e., BCE with logits), so the link probability is σ(suv)\sigma(s_{uv}). At evaluation time, we rank candidate pairs directly by σ(suv)\sigma(s_{uv}), which is equivalent since the sigmoid is monotonic. We will state the full decoder explicitly in the revised version.

Architectural overview (Q6). We agree and will add an overview figure to the appendix of the camera-ready version showing how D1, D2, and the prediction decoder are integrated into EO-GNN.

Minor presentation issues (Q7). Thank you for the careful reading. In the revised version, we will add explicit references to the proofs of Theorems 4.1 and 4.2 in Appendix D in the main text.

Reviewer_SNenOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the expressiveness limitations of Graph Neural Networks (GNNs) in link prediction, focusing on edge-level structural automorphism and its quantitative characterization. The authors introduce WL-induced Edge Orbit to characterize edge-level structural equivalence based on node-level WL equivalence classes, and further propose the Edge Automorphism Ratio (EAR) to quantify the proportion of theoretically indistinguishable edges in a graph. Building on this framework, the authors develop EO-GNN, which incorporates Automorphism-aware Dropout (D1) and Subgraph Orbit-Biased Aggregation (D2) to mitigate representational indistinguishability caused by structural symmetry.

Critical strengths
  1. The paper explores GNN expressiveness for link prediction from an edge-level perspective, providing a valuable connection between structural symmetry and link prediction.

  2. The proposed EAR offers an intuitive and efficient metric for quantifying edge-level structural ambiguity.

  3. EO-GNN combines orbit-aware dropout and orbit-biased aggregation to address structural symmetry, offering a well-motivated design.

Critical weaknesses
  1. The relationship between EAR and link prediction difficulty is not sufficiently justified.In Definition 3.4, the WL-induced Edge Orbit is defined for arbitrary node pairs, including both existing edges and non-edges. However, in Measure 3.1, EAR is computed only over the existing edge set E\mathcal E, measuring the proportion of edges that share the same WL-induced edge-orbit signature with other edges. This raises a concern about its alignment with the link prediction task. Link prediction requires distinguishing positive edges from negative node pairs, rather than distinguishing different existing edges from one another. Multiple existing edges sharing the same structural signature do not necessarily make link prediction more difficult, whereas positive and negative node pairs sharing the same signature can directly cause prediction ambiguity. Therefore, it is unclear why measuring structural ambiguity only among existing edges is sufficient to characterize link prediction difficulty. The authors should clarify this connection and investigate whether considering WL-induced structural equivalence between positive and negative candidate pairs would provide a more task-aligned measure.

  2. The independent contribution of the orbit-aware design in D2 is not sufficiently validated. D2 combines learnable structural role embeddings derived from WL-based orbit labels with independent Gaussian noise, formulated as h_u^{(0)}= Emb(o_u)+\epsilon_u. However, the current ablation studies only compare the full EO-GNN with variants that remove either D1 or D2, without disentangling the individual contributions of orbit embeddings and random noise. Since independent random node features may already break the representational symmetry among structurally equivalent nodes, it remains unclear whether the performance gains of D2 primarily stem from the proposed orbit-aware structural prior or from generic random feature augmentation. I suggest conducting additional ablation studies: (1) Orbit Embedding Only, using WL-based orbit embeddings without Gaussian noise; (2) Random Feature Only, using independent Gaussian random node features without orbit embeddings; and (3) Orbit Embedding + Random Noise, corresponding to the complete D2 module. These comparisons would help determine whether the orbit-aware structural information provides additional benefits beyond standard random feature augmentation.

Questions for authors
  1. Given that Definition 3.4 defines the WL-induced Edge Orbit for arbitrary node pairs, why does Measure 3.1 compute EAR only over existing edges, rather than considering structural equivalence between positive and negative candidate pairs? How does this choice affect EAR's ability to characterize link prediction difficulty?

  2. What is the specific benefit of incorporating WL-based orbit embeddings in D2? Could independent Gaussian random node features achieve similar performance? Can the authors provide additional ablations comparing*Random Feature Only, Orbit Embedding Only, and the complete D2 module to isolate the contribution of the orbit-aware design?

2 comments
AuthorsOpenReview ↗

Response 1: EAR and Link Prediction Difficulty

We thank the reviewer for the insightful review and we address each point as below.

Relationship Between EAR and Prediction Difficulty: We acknowledge that the evidence supporting EAR as a measure of prediction difficulty is not sufficiently direct, in the sense that it is not based on empirical evaluation. The motivation behind EAR is to characterize the structural ambiguity inherent in the graph itself, which is defined as the automorphic node problem in SEAL and BUDDY [1, 2]. We argue that EAR provides a well-defined, data-based measure that aligns with the limitations of GNNs, i.e., edges that share the same WL-induced orbit signature receive identical messages under message passing, so a high EAR means that the GNN encoder faces substantial structural redundancy when learning edge representations. This is also the motivation behind the design of D1 and D2.

We deliberately chose not to adopt an evaluation-based characterization for the following reasons:

1: Sampling Strategy: The degree of ambiguity between positive and negative samples depends highly on the sampling strategy and metrics used. On the same graph, random negative sampling, the fixed negatives provided by OGB, and hard negatives such as those of HeaRT yield very different ambiguity measures. If the measure were tied to the negative samples, it would reflect the evaluation protocol rather than the graph itself.

2: Metrics: Beyond the choice of negatives, different metrics capture different aspects of difficulty: MRR is sensitive to the exact rank of the positive and is closer to recommendation scenarios, whereas Hits@100 is a more lenient criterion that only requires the positive to rank above the 100th negative. On the same graph and split, the two metrics can therefore lead to different conclusions about difficulty.

We also agree that a task-specific measure is potentially valuable, and we computed it following the reviewer’s suggestion. We define EAR_emp as the fraction of positive test pairs whose WL signature coincides with that of at least one negative pair under the standard evaluation protocol. As shown below, EAR_emp, while more task-aligned in principle, rarely detects exact positive–negative collisions and therefore offers little additional explanatory power.

DatasetPPAPubmedCollabDDICoraCiteseerCitation2
EAR0.0010.2160.5050.0020.1390.3260.311
EAR_emp00.00490.0002400.00720.08840.000311
Observations: Exact positive–negative collisions are rare. EAR_emp is below 1% on six of the seven datasets and exactly zero on PPA and DDI. Under standard protocols, almost no positive test pair is WL-indistinguishable from a negative pair, so EAR_emp has little dynamic range across datasets.
Conclusions: These results suggest that the structural ambiguity relevant to performance does not mainly arise from exact collisions between positive and negative pairs.

In future work, we plan to theoretically analyze structural ambiguity between positive and negative samples, for instance by bounding the Hits@K and MRR achievable by signature-based models, which may provide more direct and stable evidence for the relationship between structural ambiguity and link prediction difficulty. We thank the reviewer again for this constructive suggestion, which has helped us clarify the scope of EAR.

  • Zhang, Muhan and Yi-Xin Chen. “Link Prediction Based on Graph Neural Networks.” Neural Information Processing Systems (2018).
  • Chamberlain, Benjamin Paul et al. “Graph Neural Networks for Link Prediction with Subgraph Sketching.” ArXiv abs/2209.15486 (2022): n. pag.
AuthorsOpenReview ↗

Response 2: Contribution of Orbit Embeddings in D2

We thank the reviewer for this question.

Conceptually, Emb$(o_u)$ and ϵu\epsilon_u play two distinct but complementary roles in D2: Emb$(o_u)$ encodes each node’s global structural role, i.e., its structural role in the graph; ϵu\epsilon_u is designed to break the remaining symmetry within an orbit, providing discriminative power beyond WL, but carries no structural information by itself. The two components are complementary, and both are indispensable. We verify this conclusion below by reorganizing the results reported in the paper and adding new ablation results:

VariantEmb(o_u)ε_uCiteseer (MRR)Pubmed (MRR)
w/o D2✗✗40.28 ± 2.6236.25 ± 6.56
Random Only✗✓32.75 ± 4.8738.25 ± 8.20
Orbit Only✓✗50.42 ± 1.8752.51 ± 1.28
Full D2 (EO-GNN)✓✓62.88 ± 1.4568.51 ± 0.74

Experimental setting: for Citeseer and Pubmed we use an 85/5/10 split ratio with split seed 2025. All results are averaged over 10 random seeds.

Observations: Random Only performs on par with w/o D2 on Pubmed and falls about 7 points below it on Citeseer, with substantially higher variance. (2) The orbit embedding is the main source of improvement: Orbit Only improves over w/o D2 by about 10 points on Citeseer and 16 points on Pubmed, while also reducing variance. (3) The two components are complementary: adding ϵu\epsilon_u on top of the orbit embedding brings a further gain of about 12 points on Citeseer and 16 points on Pubmed, even though ϵu\epsilon_u alone does not help.

We believe EO-GNN is practically useful and a meaningful step towards mitigating automorphism in link prediction.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the AC and all reviewers for their time and constructive feedback. We were glad to see that the reviewers found our theory rigorous (FfHN), EAR an intuitive and principled edge-level metric (SNen, wB84), and EO-GNN well-motivated (SNen).

The main concerns and our responses are summarized below.

1. What EAR measures (SNen, wB84). We clarify that EAR characterizes the structural ambiguity inherent in the graph itself, as an edge-level quantification of the automorphic node problem identified in SEAL and BUDDY. It is neither an evaluation-based expressivity bound nor a direct measure of prediction difficulty. We agree that ambiguity between positive and negative pairs is a valuable perspective, and following SNen's suggestion, we computed an evaluation-based variant, EAR_emp. Under standard protocols, exact positive–negative collisions are rare (below 1% on six of seven datasets), so EAR_emp has little discriminative power across datasets. We fully recognize the long-term value of this suggestion, but based on the current evidence, EAR remains the more practical measure.

DatasetPPAPubmedCollabDDICoraCiteseerCitation2
EAR0.0010.2160.5050.0020.1390.3260.311
EAR_emp00.00490.0002400.00720.08840.000311

EAR_emp is defined *(as suggested) as the fraction of positive test pairs whose WL signature coincides with that of at least one negative pair under the standard evaluation protocol.

2. Evidence for edge discrimination (SNen, wB84). Our main evidence in this work comes from the semi-synthetic benchmark in Sec. 5, where we control the level of automorphism directly: EO-GNN maintains its performance as automorphism increases, and the same trend holds on real-world graphs. Each module is also supported theoretically and empirically. For D1, Theorem 4.1 shows that automorphism-aware dropout distinguishes automorphic edges in fewer iterations, and Fig. 9 shows that it outperforms all previous dropout modules.

For D2, we analyze how well it distinguishes automorphic neighborhoods, and add a new ablation that separates the orbit embedding from the random noise:

VariantEmb(o_u)ε_uCiteseer (MRR)Pubmed (MRR)
w/o D2✗✗40.28 ± 2.6236.25 ± 6.56
Random Only✗✓32.75 ± 4.8738.25 ± 8.20
Orbit Only✓✗50.42 ± 1.8752.51 ± 1.28
Full D2 (EO-GNN)✓✓62.88 ± 1.4568.51 ± 0.74

Our conclusion is that random features alone do not help link prediction, the orbit embedding is the main source of improvement, and the noise brings a further gain only on top of the orbit embedding. This repositions the role of random features with respect to edge automorphism: the expressive power of random features has mainly been established for node and graph classification (Sato et al., 2021; Abboud et al., 2021), and evidence for link prediction remains limited. Our results suggest that for link prediction, breaking symmetry alone is not sufficient; it becomes effective only when it is anchored to the structural roles provided by the orbit embedding.

  • Sato, Yamada & Kashima. Random Features Strengthen Graph Neural Networks. SDM 2021.
  • Abboud, Ceylan, Grohe & Lukasiewicz. The Surprising Power of Graph Neural Networks with Random Node Initialization. IJCAI 2021.

3. Comparison with higher-order models (wB84). We added PPGN (3-WL) and confirmed that it is more powerful than GCN, and EO-GNN outperforms PPGN on Cora and Citeseer.

ModelCoraCiteseerPubmed
GCN34.19 ± 6.2344.37 ± 6.0614.55 ± 2.41
PPGN (3-WL)43.15 ± 6.2341.96 ± 2.09OOM
EO-GNN (ours)50.02 ± 5.8362.88 ± 1.4568.51 ± 0.74

4. Significance of edge-level automorphism (FfHN). We show with two counterexamples (the triangular prism and K2,3K_{2,3}) that node-level and edge-level symmetry are logically independent. The importance of edge-level automorphism therefore lies in the failures that node-level analysis cannot detect. From the task perspective, there is likewise no established correspondence between node-level and link-level expressivity, since link prediction depends on the joint representation of node pairs. This is the core reason why edge-level analysis requires its own theoretical framework and measure.

We hope these clarifications and new results address the reviewers' concerns, and we are happy to discuss any remaining questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.