Bridging Theory and Practice in Link Representation with Graph Neural Networks

We would like to thank the reviewer for the thoughtful comments and useful suggestions.

W1: The proposed framework only works for GNNs

We agree that many effective link prediction methods go beyond message-passing, including transformer-based models and heuristic methods. However, our focus is intentional: understanding the expressiveness of MP-based link representations is a necessary first step, just as MP models have been the starting point for theoretical analysis in graph-level tasks. These foundational studies have later inspired and supported the development of more powerful models such as graph transformers.

We believe that the same applies to link representation: MP models are still not fully understood in this context, and our framework provides the first steps toward filling that gap. As we state in the paper, in the Limitations section (Section 6), extending the framework to encompass transformer-based architectures is our intention for future work.

W2: The notation should be consistent. For example in Definition 3.1 h does not include the graph structure in equation (7).

For ease of readability, we have omitted the graph $G$ as an explicit argument in message-passing and link-representation functions, assuming it is implicitly defined as the underlying structure on which these functions operate. We have specified it in line 159-161 of the paper. To maintain the consistency, we will follow this notation throughout the paper starting from line 159.

Q1: When defining the neighborhood of a node $N^m(v)$ the paper defines as m-far away from $v$. How is the distance metric defined here?

We thank the reviewer for the question. We would like to clarify that in Definition 2.2 we do not define a distance metric between nodes. Specifically, we do not assign a single distance value (e.g., shortest-path distance) between two nodes.

Instead, we define the $\mathcal{N}^m(v)$ neighborhood of a node $v$ as the set of all nodes that are connected to $v$ by a path of length $m$. Therefore, a node $u$ may appear in multiple neighborhoods $\mathcal{N}^m(v)$ for different values of $m$, whenever there exist multiple paths of different lengths $m$ connecting $u$ and $v$.

We will clarify this point in the paper by expanding the explanation following Definition 2.2.

Q2: When computing the symmetric metrics, is the node feature considered or only the graph structure? If the node feature is considered, how is the WL-test approximation applied to assign the initial colors?

Yes, node features are considered when computing the symmetry metric. We initialize the node colors based on the input features using an injective mapping from the feature space to the color space. In particular, we define each node’s initial color as:

$c_v^0 = {HASH}(x_v)$

where $x_v \in \mathbb{R}^f$ is the feature vector of node $v$, and HASH is an injective function mapping the features to unique colors.

This initialization corresponds to iteration 0 of the WL test. From that point on, standard WL refinement proceeds, updating each node’s color based on its own color and the multiset of its neighbors’ colors. We will make this formalism explicit in the final version of the paper.

We would like to thank the reviewer for the thoughtful comments and useful suggestions.

W1: The framework is only restricted to message-passing designs.

We agree that many effective link prediction methods go beyond message-passing, including transformer-based models and heuristic methods. However, our focus is intentional: understanding the expressiveness of MP-based link representations is a necessary first step, just as MP models have been the starting point for theoretical analysis in graph-level tasks. These foundational studies have later inspired and supported the development of more powerful models such as graph transformers. We believe that the same applies to link representation: MP models are still not fully understood in this context, and our framework provides the first steps toward filling that gap. As we state in the paper, in the Limitations section (Section 6), extending the framework to encompass transformer-based architectures is our intention for future work.

W2: Do training protocol and Reliable Paired Comparison evaluation would remain tractable on larger graphs with rich attributes?

Our training protocol uses a Siamese architecture where both branches share the same weights and apply the link representation model under evaluation. As a result, the computational cost of training is essentially the same as training the base model itself. Our framework does not introduce any additional significant overhead; the scalability depends entirely on the model being tested.

The same applies to the Reliable Paired Comparison evaluation. After training, inference is performed on isomorphic copies of the original graph. These copies are generated with linear complexity in the graph size ($\mathcal{O}(|V| + |E|)$), and the inference time again depends only on the model used.

In short, the scalability of our approach on larger graphs depends solely on the scalability of the link representation models being evaluated, not on the protocol itself.

W3: Missing computational cost of the most expressive models

We agree that computational cost is an important factor when evaluating expressive models. Below, we report the time complexity of the methods considered in our paper, as presented in [1]. The overall time complexity for link prediction is $\mathcal{O}(B + Ct)$, where t is the number of links to be predicted and the terms $B$ (preprocessing) and $C$ (per-link cost) are summarized below:

with:

• $n$: number of nodes in the graph
• $d$: maximum node degree
• $f$: feature dimension
• $h$: complexity of the hash function used in BUDDY
• $\ell$: neighborhood radius

Among these, SEAL is the most expressive but also the most computationally expensive, due to its exponential dependence on the neighborhood radius $\ell$. NCN and BUDDY provide the best trade-off between expressiveness and computational cost. Neo-GNN, while more expensive than NCN, is in fact less expressive. GAE is the least costly, but also the least expressive.

We will include this analysis in the final version of the paper.

[1] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. "Neural Common Neighbor with Completion for Link Prediction." The Twelfth International Conference on Learning Representations.

Q1: the assumption of Thm 3.2 relies on COMB being injective under certain condition. Many practical implementations concatenate and then feed an MLP; is this always injective in training (for instance Neo-GNN), and if not, how sensitive are the conclusions

We would like to clarify that the COMB function referenced in Theorem 3.2 specifically corresponds to the one defined in our Definition 3.1, that is, the function that combines the link endpoints’ representations with the representation of the neighborhood around the two nodes involved in the link. This should not be confused with the more general "combine" operations used inside GNN layers.

As shown in Table 1 of the paper, all existing SOTA models (including Neo-GNN) implement the COMB function of Definition 3.1 as a simple concatenation, without any MLP. Since concatenation is inherently injective, the assumption in Theorem 3.2 holds for these models.

If one implements COMB using both concatenation and an MLP, injectivity is no longer guaranteed. Since injectivity of COMB is an assumption of Theorem 3.2, if that assumption does not hold, the expressiveness guarantees derived from the theorem may no longer apply.

We would like to thank the reviewer for the thoughtful comments and useful suggestions.

W1: Minor typo -- in Table 3 some of the entries use a comma instead of a period.

We apologize for the formatting error, we will correct the table to use consistent notation.

W2: The authors do not make much contact with Srinivasan et al.

We fully agree that Srinivasan et al. provide a foundational result: they show that structural node representations produced by standard GNNs are not sufficient for link prediction, as link-level tasks require joint structural representations. This insight has led to a growing body of work on message-passing models that aim to overcome this limitation, often by incorporating joint structural features into the link representation.
However, despite this growing literature, there is currently no unified framework for systematically analyzing and comparing the expressiveness of these models. This is precisely the gap our work aims to fill.
Our main contribution is to introduce a general framework that subsumes all MP-based link representation models — from standard GNNs to more expressive models that use joint structural information. The framework allows these methods to be described using a common formal scheme, making it possible to compare their expressiveness in a principled way. We will clarify this connection to Srinivasan et al. more explicitly in the revised version of the paper.

W3: Why the symmetry definition given in eq 11 (or 12) would meaningfully impact the real-world expressivity of the models.

The symmetry metric directly reflects the amount of available automorphisms in the graph. When the symmetry is low, the graph structure is irregular, and standard GNNs are unlikely to fail, since structurally different links are more easily distinguishable. In contrast, high symmetry increases the chance of presence of structurally different links with identical representations given by standard GNNs.
This is exactly what we observe in Table 3: on real-world datasets with low symmetry, standard GNNs perform well; on highly symmetric datasets, they fail to rank among the top-performing methods. We will clarify this connection more explicitly in the paper.

W4: The gap between synthetic performance differences and real-world gains could be explored more deeply

The synthetic dataset was intentionally designed to stress-test the expressiveness of the models, by including links that are particularly challenging to be distinguished by standard GNNs. This design amplifies the gap between expressive models (those using joint structural features) and standard GNNs.

In real-world datasets, such extreme cases are less common, and high-symmetry patterns are harder to find. This is precisely what we show in our real-data experiments: expressive models still tend to perform better, but the gap is smaller – reflecting the lower frequency of hard-to-distinguish links in practice.

Overall, our results confirm that expressiveness matters most when symmetry is present, and that the synthetic and real-world results are aligned in that regard.

Q1: Have you given any thought to how this work might extend to the dynamic link representation problem?

Our framework can be extended to the temporal link prediction setting by including the time variable $t$ as an explicit argument of the functions $\phi, \rho, h$ within the framework. This would allow the framework to cover temporal GNNs operating on both snapshot-based and event-based dynamic graphs [1].

A particularly interesting direction would be to extend the analysis in [2] to the temporal link prediction setting and use our framework to investigate the expressiveness of time-then-graph and time-and-graph architectures in the temporal link prediction task. We see this as a promising line of future work.

[1] Longa, Antonio, et al. "Graph Neural Networks for Temporal Graphs: State of the Art, Open Challenges, and Opportunities." Transactions on Machine Learning Research.
[2] Gao, Jianfei, and Bruno Ribeiro. "On the equivalence between temporal and static equivariant graph representations." International Conference on Machine Learning. PMLR, 2022.

Q2: How would you extend this work to directed settings?

Our framework could be quite easily generalized to directed graphs by redefining the functions $h$ and $\psi$ to operate over ordered node pairs $(u, v)$, rather than treating the two nodes separately.

Q3: Could you share more about the intuition behind the loss? I suppose I would have expected to see a margin term

We agree that contrastive loss functions are often defined with an explicit margin term $\gamma$, which controls the degree of dissimilarity enforced between negative pairs. In our case, the goal is to fully minimize similarity between representations of non-automorphic links. Following the approach in [3], we deliberately adopted a zero-margin formulation to push the model toward maximal dissimilarity between such pairs. This choice aligns with our objective of measuring and testing expressiveness, where even small overlaps in representation between structurally different links would be undesirable.

We will clarify this design choice in the revised paper.

[3] Wang, Yanbo, and Muhan Zhang. "An Empirical Study of Realized GNN Expressiveness." Forty-first International Conference on Machine Learning.

Q4-Q5: Expressiveness of SAGE

We thank the reviewer for pointing this out. In our original implementation of GraphSAGE, we did not include neighborhood sampling, rather we used a deterministic aggregation over all neighbors. Following your observation and Remark 2 in Srinivasan et al., we re-ran the experiments using stochastic neighbor sampling. As expected, GraphSAGE now achieves an accuracy of 8.2 ± 3.5, outperforming GCN. We will include this updated result in the paper, along with an explicit reference to the theoretical motivation included in Srinivasan et al.

Q6: How well does the approximation in eq 12 agree with 11?
The approximation in Equation 12 reflects how closely the WL-induced partition (used in Equation 11) matches the true orbit partition. Although there is no complete characterization of WL failures in distinguishing nodes from different orbits, it is said that WL gives different representations to almost all nodes that belong to different orbits [4].

A practical example is presented in [5], where the authors explicitly compare WL partitions and orbit partitions on the Alchemy dataset [6]. Out of 202,579 graphs, only in 4 graphs the partition of the nodes induced by the WL is different wrt the orbits, highlighting that the WL approximation is extremely close in practice.

We will clarify this point further in the final version of the paper.

[4] Babai, László, and Ludik Kucera. "Canonical labelling of graphs in linear average time." 20th annual symposium on foundations of computer science (sfcs 1979). IEEE, 1979.
[5] Morris, Matthew, Bernardo Cuenca Grau, and Ian Horrocks. "Orbit-Equivariant Graph Neural Networks." The Twelfth International Conference on Learning Representations.
[6] Chen, Guangyong, et al. "Alchemy: A quantum chemistry dataset for benchmarking ai models." arXiv preprint arXiv:1906.09427 (2019).

Q7: How sensitive are the results to the choice of α in the reliability check? Characterizing this would be helpful.

We tested the sensitivity of our results to the choice of the significance level in the reliability check. Specifically, we experimented with three commonly used values in statistical testing, i.e., $\{0.1,\ 0.05,\ 0.01\}$. The resulting performance on LR-EXP are reported below.

As expected, all standard GNN models consistently fail to recognize any links, regardless of the significance level. Among the more expressive models, the majority show stable behavior across different values of significance, with fluctuations that remain within the standard deviation. BUDDY and NCN exhibit slightly larger fluctuations in absolute value, but the key point for this experiment is the expressiveness ranking across models. This ranking remains robust across all significance levels, with one minor exception: at significance level 0.1, Neo-GNN slightly surpasses NCN. However, this difference falls within the standard deviation range.

We also note that the lack of a strictly monotonic trend in the number of reliably distinguished links when decreasing the significance level $\alpha$ is due to the two-part structure of our statistical test. Specifically, it combines:

1. The Major Procedure, which tests whether a model can distinguish between two non-automorphic links (i.e., tests if their representations differ significantly);
2. The Reliability Check, which ensures that the same model assigns equal representations to automorphic links (i.e., avoids false positives due to internal fluctuation).

For each pair of non-automorphic links, we compute a threshold $\tau$, and accept the distinction only if the test statistic $T^2_{\text{major}} > \tau$ and the corresponding statistic for automorphic links $T^2_{\text{check}} < \tau$. This means that when $\alpha$ increases, some previously rejected distinctions may now pass the Major Procedure (leading to more links being distinguished), but at the same time, the Reliability Check may fail for others (causing fewer to pass the overall test). These two effects may balance out or interfere with each other, explaining why no simple monotonic pattern emerges in the results.

We would like to thank the reviewer for the thoughtful comments and useful suggestions.

W1: Comparison with Zhang et al., 2021 and Huang et al., 2023

Zhang et al. (2021) propose the labeling trick, a specific method designed to improve the expressiveness of GNNs for link prediction. In our work, we present a general framework that subsumes all message-passing methods for link representation, including the labeling trick (see the last row of Table 1). The role of the framework is to provide a formal lens through which different link representation models can be expressed using the same building blocks, characterized by the functions $\phi$, $\rho$, and the parameters $l$ and $m$. By rewriting each method within the framework, we can precisely understand its expressiveness and compare it to others in a principled way. For instance, thanks to Theorem 3.2, we can conclude that the labeling trick is more expressive than any other existing method based on structural features. We will better explain it in the revised version of the manuscript.

Higher-order GNNs could, in principle, be used to construct expressive link representations. We note, however, that the quadratic complexity of “proper” order-2 GNNs has prevented practitioners from actually following that approach. Thus, the approach by Huang et al. (2023), though inspired by higher-order message passing, effectively still computes node level representations (but relative to a second, fixed reference node). The goal of our paper was to provide a framework that accommodates a large number of current methods that have been applied in practice. Extending the framework to include also (proper) higher-order approaches would be interesting from a purely theoretical point of view, but is outside our current scope.

W2: Usefulness of the framework with respect to WL hierarchy

As noted in our response to W1, while it is true that higher-order GNNs (e.g., 2-WL-based architectures) could, in principle, produce expressive node-pair representations, their quadratic complexity has significantly limited their practical adoption. Many alternative link prediction models have been proposed that rely on other strategies, such as structural features or neighborhood-based heuristics, to achieve higher expressiveness in a more computationally efficient way. The goal of our paper is to provide a unified framework that encompasses all these methods (and potentially also future ones), and to offer theoretical tools to compare their expressiveness in a principled manner.

Q1: Why do the more expressive models perform so much worse in lower symmetry setting?

More expressive models are explicitly designed to distinguish non-automorphic links with automorphic endpoints (i.e., dashed red links in Figure 2). However, in low-symmetry graphs, such ambiguous links are rare. These graphs tend to have highly informative features and irregular structures, making most links trivially distinguishable from their endpoints alone. As a result, standard GNNs are often sufficient to achieve strong performance.
In this context, the added expressiveness of models like SEAL and BUDDY does not yield a clear advantage, but it does not systematically hurt either. For instance, on the four real-world datasets with symmetry below 0.1, BUDDY performs better than GCN in two cases and worse in two; SEAL outperforms GCN in one case. This suggests that in low-symmetry settings, simpler models are often sufficient and the performance gap narrows.

Q2: Do the authors have intuitions on the connection with KGE?

Our framework could be quite easily generalized to directed and multi-relational graphs, including knowledge graphs. We did not go in this direction for the time being, because, on the one hand, this would cause a significant blowup in complexity of notation and the statement of Theorem 3.2. On the other hand, such structurally richer graphs would typically exhibit much lower symmetry levels, thereby alleviating the limitations of node-level representations for link prediction. This is particularly true for knowledge graphs. Indeed, for link prediction in the transductive setting (in particular: knowledge graph completion) it would be admissible to include unique node identifiers as node attributes, in which case our expressivity problem disappears completely. This also is a reason why our synthetic data focuses on inductive link prediction on many small graphs.
As for KGE models, positioning them within our framework is less straightforward, since many do not rely on message passing and operate under fundamentally different assumptions. A detailed investigation of how KGE approaches relate to our framework is an interesting open question, and we consider this a valuable direction for future work.

Q3: Which version of the WL-hierarchy are the authors using?

We thank the reviewer for the opportunity to clarify this important point. We use the oblivious version of the Weisfeiler–Leman test. We will make this explicit in the preliminaries section of the paper to avoid any ambiguity.

We would like to thank the reviewer for the thoughtful comments and useful suggestions.

W1: The paper is more a benchmark paper of a research-track paper

While our paper introduces a new synthetic dataset and evaluates link prediction models on real-world benchmark, its primary contribution is theoretical. We propose a novel framework to formally analyze and compare the expressiveness of GNN-based link representation models. The paper presents new theoretical results (Theorems 3.2 and 3.3), establishes an expressiveness hierarchy of existing methods, and introduces a graph symmetry metric to connect theoretical insights with empirical performance. We believe, as also recognized by the other reviewers, that the strength and originality of these methodological and theoretical contributions make the paper well-suited for the Research track.

W2: The datasets used in this study are limited in size

We would like to clarify that our study includes both small and large-scale datasets. In particular, we evaluate on OGBL-Citation2 (2,927,963 nodes and 30,561,187 edges) and OGBL-PPA (576,289 nodes and 30,326,273 edges), which are among the largest publicly available link prediction benchmarks.

That said, we emphasize that expressiveness is not inherently related to dataset size. Our goal is not to assess scalability, but to understand the expressiveness of different models.

W3: More ablation or empirical studies on design choices like GNN depth vs. neighborhood radius would help.

We thank the reviewer for this suggestion and have conducted additional ablation experiments to further analyze the effect of GNN depth and neighborhood radius on model expressiveness.

In the original experiment reported in the paper, to ensure a fair comparison, we selected for each model the maximum neighborhood radius that makes it as expressive as possible while still respecting its design constraints. For example, in models like NCN, the radius is fixed by design and equal to 1, so it cannot be varied. In others, such as ELPH, the radius is tunable but is constrained to a maximum of 3 by the original authors for computational reasons, and we adopted that upper bound. As for GNN depth, we fixed the number of layers to 3 as commonly done in the literature [1].

To explore this further, we conducted two additional experiments on the LR-EXP dataset:

1. Fixed radius (1), varying the number of layers
2. Fixed number of layers (3), varying the neighborhood radius

The results on the LR-EXP dataset are reported below.

(1) Fixed Radius = 1

(2) Fixed # Layers = 3

Note: For NCN, the radius is fixed by design to 1 and cannot be increased.

These results are fully consistent with Theorem 3.2 (Point 2):

• When fixing the radius, increasing the number of layers improves expressiveness in all the models.
• When fixing the number of layers, increasing the radius also improves expressiveness in all the models.

[1] Oono, Kenta, and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020.

Q1: Can the framework be extended to non-MP models like GNN transformers?

The current version of the framework is specifically designed to model message-passing based link representation methods, and does not extend to non-MP architectures such as GNN transformers.

This focus is intentional: MP models are the foundation of most existing theoretical work in graph learning, and their expressiveness in the context of link representation is still not fully understood. Just as MP GNNs served as the basis for early expressiveness studies in node and graph classification, later extended to more complex architectures like transformers, we believe that starting from MP models is a necessary and meaningful first step.

As stated in the Limitations section (Section 6), extending the framework to account for transformer-based or attention-based architectures is a valuable direction for future research, and we thank the reviewer for highlighting this point.

Q2: What is the best trade-off between the number of GNN layers and neighborhood size?

We would like to clarify that we do not claim the existence of a trade-off between the number of GNN layers and the neighborhood radius. In fact, according to Theorem 3.2, increasing both the number of layers and the neighborhood radius leads to higher expressiveness for message-passing models in link representation.

If a trade-off exists, it is not between these two parameters, but rather between expressiveness and computational cost. Our framework allows us to reason about this trade-off more precisely. Specifically, it suggests that:

1. There is no need to go beyond 1-WL expressivity in the base GNN, as increasing base expressiveness adds cost without increasing expressiveness in pair-wise representation (Theorem 3.2 point 1).
2. It is more efficient to use node representations computed with message passing layers, in a smaller neighborhood, rather than using weaker node features (like simple structural counts) over a larger neighborhood (Theorem 3.2 point 2).

Q3: Can you propose new methods based on the insight in this paper?

Theorem 3.2 provides insights for designing expressive and efficient link prediction models, specifically, by using node representations computed via 1-WL message passing over a limited-radius neighborhood and a suitable number of layers.

Additionally, the symmetry metric helps guide model selection: on datasets with low structural symmetry, simple pure GNNs already suffice, avoiding unnecessary complexity and low generalization ability. On highly symmetric datasets, more expressive models are worth the added computational cost, as they can significantly improve performance.