Pure Message Passing Can Estimate Common Neighbor for Link Prediction

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-05 18:37:16

Abstract: Message Passing Neural Networks (MPNNs) have emerged as the {\em de facto} standard in graph representation learning. However, when it comes to link prediction, they are not always superior to simple heuristics such as Common Neighbor (CN). This discrepancy stems from a fundamental limitation: while MPNNs excel in node-level representation, they stumble with encoding the joint structural features essential to link prediction, like CN. To bridge this gap, we posit that, by harnessing the orthogonality of input vectors, pure message-passing can indeed capture joint structural features. Specifically, we study the proficiency of MPNNs in approximating CN heuristics. Based on our findings, we introduce the Message Passing Link Predictor (MPLP), a novel link prediction model. MPLP taps into quasi-orthogonal vectors to estimate link-level structural features, all while preserving the node-level complexities. We conduct experiments on benchmark datasets from various domains, where our method consistently outperforms the baseline methods, establishing new state-of-the-arts.

Main paper: 
 introduction: 
 Link prediction is a cornerstone task in the field of graph machine learning, with broad-ranging implications across numerous industrial applications. From identifying potential new acquaintances on social networks (Liben-Nowell & Kleinberg, 2003) to predicting protein interactions (Szklarczyk et al., 2019) , from enhancing recommendation systems (Koren et al., 2009) to completing knowledge graphs (Zhu et al., 2021) , the impact of link prediction is felt across diverse domains. Recently, with the advent of Graph Neural Networks (GNNs) (Kipf & Welling, 2017) and more specifically, Message-Passing Neural Networks (MPNNs) (Gilmer et al., 2017) , these models have become the primary tools for tackling link prediction tasks. Despite the resounding success of MPNNs in the realm of node and graph classification tasks (Kipf & Welling, 2017; Hamilton et al., 2018; Veličković et al., 2018; Xu et al., 2018) , it is intriguing to note that their performance in link prediction does not always surpass that of simpler heuristic methods (Hu et al., 2021) . Zhang et al. (2021) highlights the limitations of GNNs/MPNNs for link prediction tasks arising from its intrinsic property of permutation invariance. Owing to this property, isomorphic nodes invariably receive identical representations. This poses a challenge when attempting to distinguish links whose endpoints are isomorphic nodes. As illustrated in Figure 1a , nodes v 1 and v 3 share a Common Neighbor v 2 , while nodes v 1 and v 5 do not. Ideally, due to their disparate local structures, these two links (v 1 , v 3 ) and (v 1 , v 5 ) should receive distinct predictions. However, the permutation invariance of MPNNs results in identical representations for nodes v 3 and v 5 , leading to identical predictions for the two links. As Zhang et al. (2021) asserts, such node-level representation, even with the most expressive MPNNs, cannot capture structural link representation such as Common Neighbors (CN), a critical aspect of link prediction.In this work, we posit that the pure Message Passing paradigm (Gilmer et al., 2017) can indeed capture structural link representation by exploiting orthogonality within the vector space. We begin by presenting a motivating example, considering a non-attributed graph as depicted in Figure 1a . In order to fulfill the Message Passing's requirement for node vectors as input, we assign a one-hot vector to each node v i , such that the i-th dimension has a value of one, with the rest set to zero. These vectors, viewed as signatures rather than mere permutation-invariant node representations, can illuminate pairwise relationships. Subsequently, we execute a single iteration of message passing as shown in Figure 1b , updating each node's vector by summing the vector of its neighbors. This process enables us to compute CN for any node pair by taking the inner product of the vectors of the two target nodes.At its core, this naive method employs an orthonormal basis as the node signatures, thereby ensuring that the inner product of distinct nodes' signatures is consistently zero. While this approach effectively computes CN, its scalability poses a significant challenge, given that its space complexity is quadratically proportional to the size of the graph. To overcome this, we draw inspiration from DotHash (Nunes et al., 2023) and capitalize on the premise that the family of vectors almost orthogonal to each other swells exponentially, even with just linearly scaled dimensions Kainen & Kůrková (1993) . Instead of relying on the orthogonal basis, we can propagate these quasi-orthogonal (QO) vectors and utilize the inner product to estimate the joint structural information of any node pair. Furthermore, by strategically selecting which pair of node signatures to compute the inner product, we can boost the expressiveness of MPNNs to estimate substructures-a feat previously deemed impossible in the literature (Chen et al., 2020) .In sum, our paper presents several pioneering advances in the realm of GNNs for link prediction:• We are the first, both empirically and theoretically, to delve into the proficiency of GNNs in approximating heuristic predictors like CN for link prediction. This uncovers a previously uncharted territory in GNN research. • Drawing upon the insights gleaned from GNNs' capabilities in counting CN, we introduce MPLP, a novel link prediction model. Uniquely, MPLP discerns joint structures of links and their associated substructures within a graph, setting a new paradigm in the field. • Our empirical investigations provide compelling evidence of MPLP's dominance. Benchmark tests reveal that MPLP not only holds its own but outstrips state-of-the-art models in link prediction performance. 
preliminaries and related work: 
 Notations. Consider an undirected graph G = (V, E, X), where V represents the set of nodes with cardinality n, indexed as {1, . . . , n}, E ⊆ V × V denotes the observed set of edges, and X i,: ∈ R Fx encapsulates the attributes associated with node i. Additionally, let N v signify the neighborhood of a node v, that is N v = {u|SPD(u, v) = 1} where the function SPD(•, •) measures the shortest path distance between two nodes. Furthermore, the node degree of v is given byd v = |N v |.To generalize, we introduce the shortest path neighborhood N s v , representing the set of nodes that are s hops away from node v, defined asN s v = {u|SPD(u, v) = s}.Link predictions. Alongside the observed set of edges E, there exists an unobserved set of edges, which we denote as E c ⊆ V × V \ E. This unobserved set encompasses edges that are either absent from the original observation or are anticipated to materialize in the future within the graph G. Consequently, we can formulate the link prediction task as discerning the unobserved set of edges E c . Heuristics link predictors include Common Neighbor (CN) (Liben-Nowell & Kleinberg, 2003) , Adamic-Adar index (AA) (Adamic & Adar, 2003) , and Resource Allocation (RA) (Zhou et al., 2009) . CN is simply counting the cardinality of the common neighbors, while AA and RA count them weighted to reflect their relative importance as a common neighbor.EQUATIONThough heuristic link predictors are effective across various graph domains, their growing computational demands clash with the need for low latency. To mitigate this, approaches like ELPH (Chamberlain et al., 2022) and DotHash (Nunes et al., 2023) propose using estimations rather than exact calculations for these predictors. Our study, inspired by these works, seeks to further refine techniques for efficient link predictions. A detailed comparison with related works and our method is available in Appendix A.GNNs for link prediction. The advent of graphs incorporating node attributes has caused a significant shift in research focus toward methods grounded in GNNs. Most practical GNNs follow the paradigm of the Message Passing (Gilmer et al., 2017) . It can be formulated as:EQUATIONwhere h(l)v represents the vector of node v at layer l and h(0) v = X v,:. For simplicity, we use h v to represent the node vector at the last layer. The specific choice of the neighborhood aggregation function, AGGREGATE(•), and the updating function, UPDATE(•), dictates the instantiation of the GNN model, with different choices leading to variations of model architectures. In the context of link prediction tasks, the GAE model (Kipf & Welling, 2016) derives link representation, h(i, j), as a Hadamard product of the target node pair representations, h (i,j) = h i ⊙ h j . Despite its seminal approach, the SEAL model (Zhang & Chen, 2018) , which labels nodes based on proximity to target links and then performs message-passing for each target link, is hindered by computational expense, limiting its scalability. Efficient alternatives like ELPH (Chamberlain et al., 2022) estimate node labels, while NCNC (Wang et al., 2023) directly learns edgewise features by aggregating node representations of common neighbors. 
can message passing count common neighbor?: 
 In this section, we delve deep into the potential of MPNNs for heuristic link predictor estimation. We commence with an empirical evaluation to recognize the proficiency of MPNNs in approximating link predictors. Following this, we unravel the intrinsic characteristics of 1-layer MPNNs, shedding light on their propensity to act as biased estimators for heuristic link predictors and proposing an unbiased alternative. Ultimately, we cast light on how successive rounds of message passing can estimate the number of walks connecting a target node pair with other nodes in the graph. All proofs related to the theorem are provided in Appendix E.To explore the capacity of MPNNs in capturing the overlap information inherent in heuristic link predictors, such as CN, AA and RA, we conduct an empirical investigation, adopting the GAE framework (Kipf & Welling, 2016) with GCN (Kipf & Welling, 2017) and SAGE (Hamilton et al., 2018) as representative encoders. SEAL (Zhang & Chen, 2018) , known for its proven proficiency in capturing heuristic link predictors, serves as a benchmark in our comparison. Additionally, we select a non-informative baseline estimation, simply using the mean of the heuristic link predictors on the training sets. The datasets comprise eight non-attributed graphs (more details in Section 5). Given that GNN encoders require node features for initial representation, we have to generate such features for our non-attributed graphs. We achieved this by sampling from a high-dimensional Gaussian distribution with a mean of 0 and standard deviation of 1. Although one-hot encoding is frequently employed for feature initialization on non-attributed graphs, we choose to forgo this approach due to the associated time and space complexity.To evaluate the ability of GNNs to estimate CN information, we adopt a training procedure analogous to a conventional link prediction task. However, we reframe the task as a regression problem aimed at predicting heuristic link predictors, rather than a binary classification problem predicting link existence. This shift requires changing the objective function from cross-entropy to Mean Squared Error (MSE). Such an approach allows us to directly observe GNNs' capacity to approximate heuristic link predictors.Our experimental findings, depicted in Figure 2 , reveal that GCN and SAGE both display an ability to estimate heuristic link predictors, albeit to varying degrees, in contrast to the non-informative baseline estimation. More specifically, GCN demonstrates a pronounced aptitude for estimating RA and nearly matches the performance of SEAL on datasets such as C.ele, Yeast, and PB. Nonetheless, both GCN and SAGE substantially lag behind SEAL in approximating CN and AA. In the subsequent section, we delve deeper into the elements within the GNN models that facilitate this approximation of link predictors while also identifying factors that impede their accuracy.GNNs exhibit the capability of estimating link predictors. In this section, we aim to uncover the mechanisms behind these estimations, hoping to offer insights that could guide the development of more precise and efficient methods for link prediction. We commence with the following theorem: Theorem 1. Let G = (V, E) be a non-attributed graph and consider a 1-layer GCN/SAGE. Define the input vectors X ∈ R N ×F initialized randomly from a zero-mean distribution with standard deviation σ node . Additionally, let the weight matrix W ∈ R F ′ ×F be initialized from a zero-mean distribution with standard deviation σ weight . After performing message passing, for any pair of nodes {(u, v)|(u, v) ∈ V × V \ E}, the expected value of their inner product is given by:GCN: E(h u • h v ) = C du dv k∈Nu Nv 1 dk ; SAGE: E(h u • h v ) = C √ d u d v k∈Nu Nv 1,where dv = d v + 1 and the constant C is defined as C = σ 2 node σ 2 weight F F ′ . The theorem suggests that given proper initialization of input vectors and weight matrices, MPNNbased models, such as GCN and SAGE, can adeptly approximate heuristic link predictors. This makes them apt for encapsulating joint structural features of any node pair. Interestingly, SAGE predominantly functions as a CN estimator, whereas the aggregation function in GCN grants it the ability to weigh the count of common neighbors in a way similar to RA. This particular trait of GCN is evidenced by its enhanced approximation of RA, as depicted in Figure 2 .Quasi-orthogonal vectors. The GNN's capability to approximate heuristic link predictors is primarily grounded in the properties of their input vectors in a linear space. When vectors are sampled from a high-dimensional linear space, they tend to be quasi-orthogonal, implying that their inner product is nearly 0 w.h.p. With message-passing, these QO vectors propagate through the graph, yielding in a linear combination of QO vectors at each node. The inner product between pairs of QO vector sets essentially echoes the norms of shared vectors while nullifying the rest. Such a trait enables GNNs to estimate CN through message-passing. A key advantage of QO vectors, especially when compared with orthonormal basis, is their computational efficiency. For a modest linear increment in space dimensions, the number of QO vectors can grow exponentially, given an acceptable margin of error (Kainen & Kůrková, 1993 ). An intriguing observation is that the orthogonality of QO vectors remains intact even after GNNs undergo linear transformations post message-passing, attributed to the randomized weight matrix initialization. This mirrors the dimension reduction observed in random projection (Johnson & Lindenstrauss, 1984) .Limitations. While GNNs manifest a marked ability in estimating heuristic link predictors, they are not unbiased estimators and can be influenced by factors such as node pair degrees, thereby compromising their accuracy. Another challenge when employing such MPNNs is their limited generalization to unseen nodes. The neural networks, exposed to randomly generated vectors, may struggle to transform newly added nodes in the graph with novel random vectors. This practice also violates the permutation-invariance principle of GNNs when utilizing random vectors as node representation. It could strengthen generalizability if we regard these randomly generated vectors as signatures of the nodes, instead of their node features, and circumvent the use of MLPs for them.Unbiased estimator. Addressing the biased element in Theorem 1, we propose the subsequent instantiation for the message-passing functions:h (l+1) v = u∈Nv h (l)u .(3)Such an implementation aligns with the SAGE model that employs sum aggregation devoid of selfnode propagation. This methodology also finds mention in DotHash (Nunes et al., 2023) , serving as a cornerstone for our research. With this kind of message-passing design, the inner product of any node pair signatures can estimate CN impartially: Theorem 2. Let G = (V, E) be a graph, and let the vector dimension be given by F ∈ N + . Define the input vectors X = (X i,j ), which are initialized from a random variable x having a mean of 0 and a standard deviation of 1 √ F . Using the 1-layer message-passing in Equation 3, for any pair of nodes {(u, v)|(u, v) ∈ V × V }, the expected value and variance of their inner product are:E(h u • h v ) = CN(u, v), Var(h u • h v ) = 1 F d u d v + CN(u, v) 2 -2CN(u, v) + F Var x 2 CN(u, v).Though this estimator provides an unbiased estimate for CN, its accuracy can be affected by its variance. Specifically, DotHash recommends selecting a distribution for input vector sampling from vertices of a hypercube with unit length, which curtails variance given that Var x 2 = 0. However, the variance influenced by the graph structure isn't adequately addressed, and this issue will be delved into in Section 4.Orthogonal node attributes. Both Theorem 1 and Theorem 2 underscore the significance of quasi orthogonality in input vectors, enabling message-passing to efficiently count CN. Intriguingly, in most attributed graphs, node attributes, often represented as bag-of-words (Purchase et al., 2022) , exhibit inherent orthogonality. This brings forth a critical question: In the context of link prediction, do GNNs primarily approximate neighborhood overlap, sidelining the intrinsic value of node attributes? We earmark this pivotal question for in-depth empirical exploration in Appendix C, where we find that random vectors as input to GNNs can catch up with or even outperform node attributes.Theorem 2 elucidates the estimation of CN based on a single iteration of message passing. This section explores the implications of multiple message-passing iterations and the properties inherent to the iteratively updated node signatures. We begin with a theorem delineating the expected value of the inner product for two nodes' signatures derived from any iteration of message passing:Theorem 3. Under the conditions defined in Theorem 2, let h (l)u denote the vector for node u after the l-th message-passing iteration. We have:E h (p) u • h (q) v = k∈V |walks (p) (k, u)||walks (q) (k, v)|,where |walks (l) (u, v)| counts the number of length-l walks between nodes u and v.This theorem posits that the message-passing procedure computes the number of walks between the target node pair and all other nodes. In essence, each message-passing trajectory mirrors the path of the corresponding walk. As such, hu aggregates the initial QO vectors originating from nodes reachable by length-l walks from node u. In instances where multiple length-l walks connect node k to u, the associated QO vector X k,: is incorporated into the sum |walks (l) (k, u)| times.One might surmise a paradox, given that message-passing calculates the number of walks, not nodes. However, in a simple graph devoid of self-loops, where at most one edge can connect any two nodes, it is guaranteed that |walks(1) (u, v)| = 1 iff SPD(u, v) = 1.Consequently, the quantity of length-1 walks to a target node pair equates to CN, a first-order heuristic. It's essential to recognize, however, that |walks (l) (u, v)| ≥ 1 only implies SPD(u, v) ≤ l. This understanding becomes vital when employing message-passing for estimating the local structure of a target node pair in Section 4. 
method: 
 In this section, we introduce our novel link prediction model, denoted as MPLP. Distinctively designed, MPLP leverages the pure essence of the message-passing mechanism to adeptly learn structural information. Not only does MPLP encapsulate the local structure of the target node pair by assessing node counts based on varying shortest-path distances, but it also pioneers in estimating the count of triangles linked to any of the target node pair-an ability traditionally deemed unattainable for GNNs (Chen et al., 2020) . Node representation. While MPLP is specifically designed for its exceptional structural capture, it also embraces the inherent attribute associations of graphs that speak volumes about individual node characteristics. To fuse the attributes (if they exist in the graph) and structures, MPLP begins with a GNN, utilized to encode node u's representation: GNN(u) ∈ R Fx . This node representation will be integrated into the structural features when constructing the QO vectors. Importantly, this encoding remains flexible, permitting the choice of any nodelevel GNN.Probabilistic hypercube sampling. Though deterministic avenues for QO vector construction are documented (Kainen, 1992; Kainen & Kurkova, 2020) , our preference leans toward probabilistic techniques for their inherent simplicity. We inherit the sampling paradigm from DotHash (Nunes et al., 2023) , where each node k is assigned with a node signature h (0) k , acquired via random sampling from the vertices of an F -dimensional hypercube with unit vector norms. Consequently, the sampling space for h (0)k becomes {-1/ √ F , 1/ √ F } F .Harnessing One-hot hubs for variance reduction. The stochastic nature of our estimator brings along an inevitable accompaniment: variance. Theorem 2 elucidates that a graph's topology can augment estimator variance, irrespective of the chosen QO vector distribution. At the heart of this issue is the imperfectness of quasi-orthogonality. While a pair of vectors might approach orthogonality, the same cannot be confidently said for the subspaces spanned by larger sets of QO vectors.Capitalizing on the empirical observation that real-world graphs predominantly obey the powerlaw distribution (Barabási & Albert, 1999) , we discerned a strategy to control variance. Leveraging the prevalence of high-degree nodes-or hubs-we designate unique one-hot vectors for the foremost hubs. Consider the graph's top-b hubs; while other nodes draw their QO vectors froma hypercube {-1/ √ F -b, 1/ √ F -b} F -b × {0} b ,these hubs are assigned one-hot vectors from {0} F -b × {0, 1} b , reserving a distinct subspace of the linear space to safeguard orthogonality. Note that when new nodes are added to the graph, their QO vectors are sampled the same way as the non-hub nodes, which can ensure a tractable computation complexity.Norm rescaling to facilitate weighted counts. Theorem 1 alludes to an intriguing proposition: the estimator's potential to encapsulate not just CN, but also RA. Essentially, RA and AA are nuanced heuristics translating to weighted enumerations of shared neighbors, based on their node degrees. In Theorem 2, such counts are anchored by vector norms during dot products. MPLP enhances this count methodology by rescaling node vector norms, drawing inspiration from previous works (Nunes et al., 2023; Yun et al., 2021) . This rescaling is determined by the node's representation, GNN(u), and its degree d u . The rescaled vector is formally expressed as:EQUATIONwhere f : R Fx+1 → R is an MLP mapping the node representation and degree to a scalar, enabling the flexible weighted count paradigm.Node label estimation. The estimator in Theorem 2 can effectively quantify CN. Nonetheless, solely relying on CN fails to encompass diverse topological structures embedded within the local neighborhood. To offer a richer representation, we turn to Distance Encoding (DE) (Li et al., 2020) . DE acts as an adept labeling tool (Zhang et al., 2021) , demarcating nodes based on their shortestpath distances relative to a target node pair. For a given pair (u, v), a node k belongs to DE(p, q) iff SPD(u, k) = p and SPD(v, k) = q. Unlike its usage as node labels, we opt to enumerate these labels, producing a link feature defined by #(p, q) = |DE(p, q)|. Our model adopts a philosophy akin to ELPH (Chamberlain et al., 2022) , albeit with a distinct node-estimation mechanism.Returning to Theorem 3, we recall that message-passing as in Equation 3 essentially corresponds to walks. Our ambition to enumerate nodes necessitates a single-layer message-passing alteration, reformulating Equation 3 to:EQUATIONHere, N s v pinpoints v's shortest-path neighborhoods distanced by the shortest-path s. This method sidesteps the duplication dilemma highlighted in Theorem 3, ensuring that η s v aggregates at most one QO vector per node. Similar strategies are explored in (Abboud et al., 2022; Feng et al., 2022) .For a tractable computation, we limit the largest shortest-path distance as r ≥ max(p, q). Consequently, to capture the varied proximities of nodes to the target pair (u, v), we can deduce:#(p, q) =              E(η p u • η q v ), r ≥ p, q ≥ 1 |N q v | - 1≤s≤r #(s, q), p = 0 |N p u | - 1≤s≤r #(p, s), q = 0 (6)Concatenating the resulting estimates yields the expressive structural features of MPLP.Shortcut removal. The intricately designed structural features improve the expressiveness of MPLP. However, this augmented expressiveness introduces susceptibility to distribution shifts during link prediction tasks (Dong et al., 2022) . Consider a scenario wherein the neighborhood of a target node pair contains a node k. Node k resides a single hop away from one of the target nodes but requires multiple steps to connect with the other. When such a target node pair embodies a positive instance in the training data (indicative of an existing link), node k can exploit both the closer target node and the link between the target nodes as a shortcut to the farther one. This dynamic ensures that for training-set positive instances, the maximum shortest-path distance from any neighboring node to the target pair is constrained to the smaller distance increased by one. This can engender a discrepancy in distributions between training and testing phases, potentially diminishing the model's generalization capability.To circumvent this pitfall, we adopt an approach similar to preceding works (Zhang & Chen, 2018; Yin et al., 2022; Wang et al., 2023; Jin et al., 2022) . Specifically, we exclude target links from the original graph during each training batch, as shown by the dash line in Figure 3 . This maneuver ensures these links are not utilized as shortcuts, thereby preserving the fidelity of link feature construction. 2020) discusses the challenge of counting such a substructure with a pure message-passing framework. We next give an implementation of messagepassing to approximate triangle counts linked to a target node pair-equivalent in complexity to conventional MPNNs.For a triangle to form, two nodes must connect with each other and the target node. Key to our methodology is recognizing the obligatory presence of length-1 and length-2 walks to the target node. Thus, according to Theorem 3, our estimation can formalize as:EQUATIONAugmenting the node label counts with triangle estimates gives rise to a more expressive structural feature set of MPLP.Feature integration for link prediction. Having procured the structural features, we proceed to formulate the encompassing link representation for a target node pair (u, v) as:EQUATIONwhich can be fed into a classifier for a link prediction between nodes (u, v). 
experiments: 
 Datasets, baselines and experimental setup We evaluate our approach on a diverse set of 8 nonattributed and 5 attributed graph benchmarks. In the absence of predefined train/test splits, links are partitioned into train, validation, and test splits following a 70-10-20 percentage distribution. Our comparison spans three categories of link prediction models: (1) heuristic-based methods encompassing CN, AA, and RA; (2) node-level models like GCN and SAGE; and (3) link-level models, including SEAL, Neo-GNN (Yun et al., 2021) , ELPH (Chamberlain et al., 2022) , and NCNC (Wang et al., 2023) . Each experiment is conducted 10 times, with the average score and standard deviations reported using the Hits@50 metric, a well-accepted standard for the link prediction task (Hu et al., 2021) . We limit the number of hops r = 2, which results in a good balance of performance and efficiency. A comprehensive description of the experimental setup is available in Appendix B.Results Performance metrics are presented in Table 1 and Table 2 . MPLP outperforms other models on 12 of the 13 benchmarks. In the context of non-attributed graphs, MPLP takes the lead on 7 out of the 8 datasets, followed by SEAL and ELPH. For attributed graphs, MPLP reigns supreme on all 5 datasets. Notably, MPLP consistently demonstrates superior results across a wide range of graph domains, with a performance advantage ranging from 2% to 10% in Hits@50 over the closest competitors. More ablation study can be found in Appendix D. We investigate the precision of MPLP in estimating #(p, q), which denotes the count of node labels, using the Collab dataset. The outcomes of this examination are illustrated in Figure 5 . Although ELPH possesses the capability to approximate these counts utilizing techniques like MinHash and Hyperloglog, our method exhibits superior accuracy. Moreover, ELPH runs out of memory when the dimension is larger than 3000. Remarkably, deploying a one-hot encoding strategy for the hubs further bolsters the accuracy of MPLP, concurrently diminishing the variance introduced by inherent graph structures. An exhaustive analysis, including time efficiency considerations, is provided in Appendix D.1.Link prediction Link prediction, inherent to graph data analysis, has witnessed a paradigm shift from its conventional heuristic-based methods to the contemporary, more sophisticated GNNs approaches. Initial explorations in this domain primarily revolve around heuristic methods such as CN, AA, RA, alongside seminal heuristics like the Katz Index (Katz, 1953) , Jaccard Index (Salton & McGill, 1986) , Page Rank (Brin & Page, 1998) , and Preferential Attachment (Barabási & Albert, 1999) . However, the emergence of graphs associated with node attributes has shifted the research landscape towards GNN-based methods. Specifically, these GNN-centric techniques bifurcate into node-level and link-level paradigms. Pioneers like Kipf & Welling introduce the Graph Auto-Encoder (GAE) to ascertain node pair similarity through GNN-generated node representation.On the other hand, link-level models, represented by SEAL (Zhang & Chen, 2018) , opt for subgraph extractions centered on node pairs, even though this can present scalability challenges.Amplifying GNN Expressiveness with Randomness The expressiveness of GNNs, particularly those of the MPNNs, has been the subject of rigorous exploration (Xu et al., 2018) . A known limitation of MPNNs, their equivalence to the 1-Weisfeiler-Lehman test, often results in indistinguishable representation for non-isomorphic graphs. A suite of contributions has surfaced to boost GNN expressiveness, of which (Morris et al., 2021; Maron et al., 2020; Zhang & Li, 2021; Frasca et al., 2022) stand out. An elegant, yet effective paradigm involves symmetry-breaking through stochasticity injection (Sato et al., 2021; Abboud et al., 2021; Papp et al., 2021) . Although enhancing expressiveness, such random perturbations can occasionally undermine generalizability. Diverging from these approaches, our methodology exploits probabilistic orthogonality within random vectors, culminating in a robust structural feature estimator that introduces minimal estimator variance.Link-Level Link Prediction While node-level models like GAE offer enviable efficiency, they occasionally fall short in performance when compared with rudimentary heuristics (Chamberlain et al., 2022) . Efforts to build scalable link-level alternatives have culminated in innovative methods such as Neo-GNN (Yun et al., 2021) , which distills structural features from adjacency matrices for link prediction. Elsewhere, ELPH (Chamberlain et al., 2022) harnesses hashing mechanisms for structural feature representation, while NCNC (Wang et al., 2023) adeptly aggregates common neighbors' node representation. Notably, DotHash (Nunes et al., 2023) , which profoundly influenced our approach, employs quasi-orthogonal random vectors for set similarity computations, applying these in link prediction tasks.Distinctively, our proposition builds upon, yet diversifies from, the frameworks of ELPH and DotHash. While resonating with ELPH's architectural spirit, we utilize a streamlined, efficacious hashing technique over MinHash for set similarity computations. Moreover, we resolve ELPH's limitations through strategic implementations like shortcut removal and norm rescaling. When paralleled with DotHash, our approach magnifies its potential, integrating it with GNNs for link predictions and extrapolating its applicability to multi-hop scenarios. It also judiciously optimizes variance induced by the structural feature estimator in sync with graph data. We further explore the potential of achieving higher expressiveness with linear computational complexity by estimating the substructure counting (Chen et al., 2020) .The statistics of each benchmark dataset are shown in Table 3 . The benchmarks without attributes are:• USAir (Batagelj & Mrvar, 2006 ): a graph of US airlines;• NS (Newman, 2006): a collaboration network of network science researchers;• PB (Ackland & others, 2005) : a graph of links between web pages on US political topics;• Yeast (Von Mering et al., 2002) : a protein-protein interaction network in yeast;• C.ele (Watts & Strogatz, 1998) : the neural network of Caenorhabditis elegans; • Power (Watts & Strogatz, 1998) : the network of the western US's electric grid;• Router (Spring et al., 2002) : the Internet connection at the router-level;• E.coli (Zhang et al., 2018) : the reaction network of metabolites in Escherichia coli.4 out of 5 benchmarks with node attributes come from (Shchur et al., 2019) , while Collab is from Open Graph Benchmark (Hu et al., 2021 ):• CS: co-authorship graphs in the field of computer science, where nodes represent authors, edges represent that two authors collaborated on a paper, and node features indicate the keywords for each author's papers;• Physics: co-authorship graphs in the field of physics with the same node/edge/feature definition as of CS;• Computers: a segment of the Amazon co-purchase graph for computer-related equipment, where nodes represent goods, edges represent that two goods are frequently purchased together together, and node features represent the product reviews;• Physics: a segment of the Amazon co-purchase graph for photo-related equipment with the same node/edge/feature definition as of Computers;• Collab: a large-scale collaboration network, showcasing a wide array of interdisciplinary partnerships.Since Collab has a fixed split, no train test split is needed for it. For the other benchmarks, we randomly split the edges into 70-10-20 as train, validation, and test sets. The validation and test sets are not observed in the graph during the entire cycle of training and testing. They are only used for evaluation purposes. For Collab, it is allowed to use the validation set in the graph when evaluating on the test set.We run the experiments 10 times on each dataset with different splits. For each run, we cache the split edges and evaluate every model on the same split to ensure a fair comparison. The average score and standard deviation are reported for Hits@50.In our experiments, we explore advanced variants of the baseline models ELPH and NCNC. Specifically, for ELPH, Chamberlain et al. (2022) propose BUDDY, an enhanced link prediction method that preprocesses node representations for efficiency. NCNC (Wang et al., 2023) builds upon its predecessor, NCN, by first estimating the complete graph structure and then performing inference.We incorporate these latest and most accurate versions of both models to establish robust baselines in our study.In Figure 4 , we assess the inference time across different models on the Collab dataset for a single epoch of test links. Specifically, we clock the wall time taken by models to score the complete test set. This encompasses preprocessing, message-passing, and the actual prediction. For the SEAL model, we employ a dynamic subgraph generator during the preprocessing phase, which dynamically computes the subgraph. Meanwhile, for both ELPH and our proposed method, MPLP, we initially propagate the node features and signatures just once at the onset of inference. These are then cached for subsequent scoring sessions.We implement MPLP in Pytorch Geometric framework (Fey & Lenssen, 2019) . We run our experiments on a Linux system equipped with an NVIDIA V100 GPU with 32GB of memory.The efficiency of MPLP stands out when it comes to link prediction inference. Let's denote t as the number of target links, d as the maximum node degree, r as the number of hops to compute, and F as the dimension count of node signatures.For preprocessing node signatures, MPLP involves two primary steps:1. Initially, the algorithm computes all-pairs unweighted shortest paths across the input graph to acquire the shortest-path neighborhood N s v for each node. This can be achieved using a BFS approach for each node, with a time complexity of O(|V ||E|). 2. Following this, MPLP propagates the QO vectors through the shortest-path neighborhood, which has a complexity of O(td r F ), and then caches these vectors in memory.During online scoring, MPLP performs the inner product operation with a complexity of O(tF ), enabling the extraction of structural feature estimations.However, during training, the graph's structure might vary depending on the batch of target links due to the shortcut removal operation. As such, MPLP proceeds in three primary steps:1. Firstly, the algorithm extracts the r-hop induced subgraph corresponding to these t target links. In essence, we deploy a BFS starting at each node of the target links to determine their receptive fields. This process, conceptually similar to message-passing but in a reversed message flow, has a time complexity of O(tdr). Note that, different from SEAL, we extract one r-hop subgraph induced from a batch of target links. 2. To identify the shortest-path neighborhood N s v , we simply apply sparse-sparse matrix multiplications of the adjacency matrix to get the s-power adjacency matrix, where s = 1, 2, . . . , r. Due to the sparsity, this takes O(|V |d r ). 3. Finally, the algorithm engages in message-passing to propagate the QO vectors along the shortest-path neighborhoods, with a complexity of O(td r F ), followed by performing the inner product at O(tF ).Summing up, the overall time complexity for the training phase stands at O(tdr + |V |d r + td r F ).We determine the optimal hyperparameters for our model through systematic exploration. The setting with the best performance on the validation set is selected. The chosen hyperparameters are as follows:• Number of Hops (r): We set the maximum number of hops to r = 2. Empirical evaluation suggests this provides an optimal trade-off between accuracy and computational efficiency. • Node Signature Dimension (F ): The dimension of node signatures, F , is fixed at 1024, except for Collab with 2048. This configuration ensures that MPLP is both efficient and accurate across all benchmark datasets.• The minimum degree of nodes to be considered as hubs (b): This parameter indicates the minimum degree of the nodes which are considered as hubs to one-hot encode in the node signatures. We experiment with values in the set [50, 100, 150] .• Batch Size (B): We vary the batch size depending on the graph type: For the 8 nonattributed graphs, we explore batch sizes within [512, 1024] . For the 5 attributed graphs, we extend our search to [2048, 4096] .More ablation study can be found in Appendix D.4.In Section 3, we delved into the capability of GNNs to discern joint structural features, particularly when presented with Quasi-Orthogonal (QO) vectors. Notably, many graph benchmarks utilize text data to construct node attributes, representing them as Bag-Of-Words (BOW). BOW is a method that counts word occurrences, assigning these counts as dimensional values. With a large dictionary, these BOW node attribute vectors often lean towards QO due to the sparse nature of word representations. Consequently, many node attributes in graph benchmarks inherently possess the QO trait. Acknowledging GNNs' proficiency with QO vector input, we propose the question: Is it the QO property or the information embedded within these attributes that significantly impacts link prediction in benchmarks? This section is an empirical exploration of this inquiry. For our analysis, we sample 10000 nodes (7650 for Photo) and compute the inner product of their attributes. The results are visualized in Figure 6 . Our findings confirm that with a larger BOW dimension, CS node attributes closely follow QO. However, this orthogonality isn't as pronounced in Photo and Collab-especially Collab, where word embeddings replace BOW. Given that increased node signature dimensions can mitigate estimation variance (as elaborated in Theorem 2), one could posit GNNs might offer enhanced performance on CS, due to its extensive BOW dimensions. Empirical evidence from Table 2 supports this claim.Further, in Figure 7 , we showcase the inner product of node attributes in CS and Photo, but this time, nodes are sequenced by class labels. This order reveals that nodes sharing labels tend to have diminished orthogonality compared to random pairs-a potential variance amplifier in structural feature estimation using node attributes.To discern the role of embedded information within node attributes, we replace the original attributes in CS, Photo, and Collab with random vectors-denoted as random feat. These vectors maintain the original attribute dimensions, though each dimension gets randomly assigned values from {-1, 1}.The subsequent findings are summarized in Table 4 . Intriguingly, even with this "noise" as input, performance remains largely unaltered. CS attributes appear to convey valuable insights for link predictions, but the same isn't evident for the other datasets. In fact, introducing random vectors to Computers and Photo resulted in enhanced outcomes, perhaps due to their original attribute's insufficient orthogonality hampering effective structural feature capture. Collab shows a performance drop with random vectors, implying that the original word embedding can contribute more to the link prediction than structural feature estimation with merely 128 QO vectors. Lastly, we substitute node attributes with QO vectors of varied dimensions, utilizing GCN as the encoder. The outcomes of this experiment are cataloged in Table 4 . What's striking is that GCNs, when furnished with lengthier random vectors, often amplify link prediction results across datasets, with the exception of CS. On Computers and Photo, a GCN even rivals our proposed model (Figure 2 ), potentially attributed to the enlarged vector dimensions. This suggests that when computational resources permit, expanding our main experiment's node signature dimensions (currently set at 1024) could elevate our model's performance. On Collab. the performance increases significantly compared to the experiments which are input with 128-dimensional vectors, indicating that the structural features are more critical for Collab than the word embedding.In Figure 5 , we assess the accuracy of node label count estimation. For ELPH, the node signature dimension corresponds to the number of MinHash permutations. We employ a default hyperparameter setting for Hyperloglog, with p = 8, a configuration that has demonstrated its adequacy in (Chamberlain et al., 2022) . For time efficiency evaluation, we initially propagate and cache node signatures, followed by performing the estimation.Furthermore, we evaluate the node label count estimation for #(2, 2) and #(2, 0). The outcomes are detailed in Figure 8 . While MPLP consistently surpasses ELPH in estimation accuracy, the gains achieved via one-hot hubs diminish for #(2, 2) and #(2, 0) relative to node counts at a shortestpath distance of 1. This diminishing performance gain can be attributed to our selection criteria for one-hot encoding, which prioritizes nodes that function as hubs within a one-hop radius. However, one-hop hubs don't necessarily serve as two-hop hubs. While we haven't identified a performance drop for these two-hop node label counts, an intriguing avenue for future research would be to refine variance reduction strategies for both one-hop and two-hop estimations simultaneously.Regarding the efficiency of estimation, MPLP consistently demonstrates superior computational efficiency in contrast to ELPH. When we increase the node signature dimension to minimize estimation variance, ELPH's time complexity grows exponentially and becomes impractical. In contrast, MPLP displays a sublinear surge in estimation duration.It's also worth noting that ELPH exhausts available memory when the node signature dimension surpasses 3000. This constraint arises as ELPH, while estimating structural features, has to cache node signatures for both MinHash and Hyperloglog. Conversely, MPLP maintains efficiency by caching only one type of node signatures. We investigate the individual performance contributions of three primary components in MPLP: Shortcut removal, One-hot hubs, and Norm rescaling. To ensure a fair comparison, we maintain consistent hyperparameters across benchmark datasets, modifying only the specific component under evaluation. Moreover, node attributes are excluded from the model's input for this analysis. The outcomes of this investigation are detailed in Table 5 and Table 6 .Among the three components, Shortcut removal emerges as the most pivotal for MPLP. This highlights the essential role of ensuring the structural distribution of positive links is aligned between the training and testing datasets (Dong et al., 2022) .Regarding One-hot hubs, while they exhibited strong results in the estimation accuracy evaluations presented in Figure 5 and Figure 8 , their impact on the overall performance is relatively subdued. We hypothesize that, in the context of these sparse benchmark graphs, the estimation variance may not be sufficiently influential on the model's outcomes.Finally, Norm rescaling stands out as a significant enhancement in MPLP. This is particularly evident in its positive impact on datasets like Yeast, Physics, Photo, and Collab.We further examine the contribution of various structural features to the link prediction task. These features include: #(1, 1), #(1, 2), #(1, 0), #(2, 2), #(2, 0), and #(△). To ensure fair comparison, we utilize only the structural features for link representation, excluding the node representations derived from GNN(•). Given the combinatorial nature of these features, they are grouped into four categories:• #(1, 1);• #(1, 2), #(1, 0); • #(2, 2), #(2, 0); • #(△).The configuration of these structural features and their corresponding results are detailed in Table 7 and Table 8 .Our analysis reveals that distinct benchmark datasets have varied preferences for structural features, reflecting their unique underlying distributions. For example, datasets PB and Power exhibit superior performance with 2-hop structural features, whereas others predominantly favor 1-hop features. Although #(1, 1), which counts Common Neighbors, is often considered pivotal for link prediction, the two other 1-hop structural features, #(1, 2) and #(1, 0), demonstrate a more pronounced impact preserving the local structures of other links. However, this approach is computationally inefficient. Although shortcut removal can markedly enhance performance and address the distribution shift issue (as elaborated in Appendix D.2), it can also inadvertently modify the graph structure. Thus, striking a balance between computational efficiency and minimal graph structure alteration is essential.Our findings are delineated in Table 9 , Table 10 , Table 11 , and Table 12 . Concerning the batch size, our results indicate that opting for a smaller batch size typically benefits performance. However, if this size is increased past a certain benchmark threshold, there can be a noticeable performance drop. This underscores the importance of pinpointing an optimal batch size for MPLP. Regarding the node signature dimension, our data suggests that utilizing longer QO vectors consistently improves accuracy by reducing variance. This implies that, where resources allow, selecting a more substantial node signature dimension is consistently advantageous.We extend our model evaluation to include additional metrics such as Hits@20 and Hits@100, with the results detailed in Table 13 , Table 14 , Table 15 , and Table 16 . In the Hits@20 metric, MPLP maintains its lead, ranking as the top model in 6 out of 8 non-attributed datasets and excelling in 3 attributed datasets. For Hits@100, MPLP consistently ranks among the top two models across all non-attributed datasets and achieves the best performance in 3 attributed benchmarks, securing second place in the Physics and Collab dataset. 13 : Link prediction results on non-attributed benchmarks evaluated by Hits@20. The format is average score ± standard deviation. The top three models are colored by First, Second, Third. We begin by restating Theorem 1 and then proceed with its proof:Let G = (V, E) be a non-attributed graph and consider a 1-layer GCN/SAGE. Define the input vectors X ∈ R N ×F initialized randomly from a zero-mean distribution with standard deviation σ node . Additionally, let the weight matrix W ∈ R F ′ ×F be initialized from a zero-mean distribution with standard deviation σ weight . After performing message passing, for any pair of nodes {(u, v)|(u, v) ∈ V × V \ E}, the expected value of their inner product is given by: For GCN:E(h u • h v ) = C du dv k∈Nu Nv 1 dk ,For SAGE:E(h u • h v ) = C √ d u d v k∈Nu Nv 1,where dv = d v + 1 and the constant C is defined as C = σ 2 node σ 2 weight F F ′ .Proof. Define X as X ⊤ 1 , . . . , X ⊤ N ⊤ and W as (W 1 , W 2 , . . . , W F ).Using GCN as the MPNN, the node representation is updated by:h u = W k∈N (u)∪{u} 1 dk du X k ,where dv = d v + 1.For any two nodes (u, v) from {(u, v)|(u, v) ∈ V × V \ E}, we compute:h u • h v = h ⊤ u h v =   W a∈N (u)∪{u} 1 da du X a   ⊤   W b∈N (v)∪{v} 1 db dv X b   = a∈N (u)∪{u} 1 da du X ⊤ a W ⊤ W b∈N (v)∪{v} 1 db dv X b = a∈N (u)∪{u} 1 da du X ⊤ a    W ⊤ 1 W 1 • • • W ⊤ 1 W F . . . . . . . . . W ⊤ F W 1 • • • W ⊤ F W F    b∈N (v)∪{v} 1 db dv X b .Given that 1. E W ⊤ i W j = σ 2 weight F ′ when i = j, 2. E W ⊤ i W j = 0 when i ̸ = j, we obtain:E(h u • h v ) = σ 2 weight F ′ a∈N (u)∪{u} 1 da du X ⊤ a b∈N (v)∪{v} 1 db dv X b .Also the orthogonal of the random vectors guarantee that E X ⊤ a X b = 0 when a ̸ = b. Then, we have:E(h u • h v ) = C du dv k∈Nu Nv 1 dkwhere C = σ 2 node σ 2 weight F F ′ . This completes the proof for the GCN variant. A similar approach, utilizing the probabilistic orthogonality of the input vectors and weight matrix, can be employed to derive the expected value for SAGE as the MPNN.We begin by restating Theorem 2 and then proceed with its proof: Let G = (V, E) be a graph, and let the vector dimension be given by F ∈ N + . Define the input vectors X = (X i,j ), which are initialized from a random variable x having a mean of 0 and a standard deviation of 1 √ F . Using the message-passing as described by Equation 3, for any pair of nodes {(u, v)|(u, v) ∈ V × V }, the expected value and variance of their inner product are:E(h u • h v ) = CN(u, v), Var(h u • h v ) = 1 F d u d v + CN(u, v) 2 -2CN(u, v) + F Var x 2 CN(u, v).Proof. We follow the proof of the theorem in Nunes et al. (2023) . Based on the message-passing defined in Equation 3:E(h u • h v ) = E ku∈Nu X ku,: • kv∈Nv X kv,: = E ku∈Nu kv∈NvX ku,: X kv,:ku∈Nu kv∈Nv E(X ku,: X kv,: ).CONCLUSIONIn this work, we delved into the potential of message-passing GNNs to encapsulate joint structural features of graphs. Stemming from this investigation, we introduced a novel link prediction paradigm that consistently outperforms state-of-the-art baselines across a varied suite of graph benchmarks. The inherent capability to adeptly capture structures enhances the expressivity of GNNs, all while maintaining their computational efficiency. Our findings hint at a promising avenue for elevating the expressiveness of GNNs through probabilistic approaches. 
 
 Appendix:  


Decision: The reviewers all lean towards accepting the paper with one reviewer scoring the paper to be of very high quality and impact. Reasons to accept the paper are 

(i) both theoretical and practical results that should be relevant to the graph learning community
(ii) strong and extensive experimental evaluation with competitive results
(ii) extensive ablation studies
(iv) a clearly and well-written paper with a strong motivation of the proposed approach

There was one reviewer who was not satisfied with the reasons the authors provided for why their methods works. Indeed, some explanations where inconsistent and the authors should take this feedback into account in the final version of their paper.

Reviews: review: paper_summary: paper_summary: This paper first shows that pure message passing can count common neighbor. Based on the proposed theory, this paper develops MPLP  for link prediction, where the common neighbor is an important heuristic feature. Experiments on link prediction demonstrate the performance gains of MPLP over baselines.
strength_weakness: strength_weakness: 1. If MILP aims to count the common neighbor exactly, why not directly use the pre-computed common neighbor? If MILP aims to develop a neural network to approximate common neighbor heuristics, what is the novelty of MILP compared with [1]?
2. To capture structural link representation such as Common Neighbors (CN),  Zhang et al. [2] propose labeling trick, which is a position encoding in my opinion. Indeed, the Quasi-orthogonal vector is also a position encoding. I suggest discussing the relationship between Quasi-orthogonal vectors and existing position encodings such as random walk position encodings (RWPE), relative random walk probabilities (RRWP) [3], Resistance Distance encodings [4], and Laplace position encodings (LapPE). Notably, Laplace position encodings are also orthogonal.
3. Is MILP scalable to large-scale graphs? If MILP assigns each node with a unique orthogonal vector, then the orthogonality requires the dimension of the orthogonal vector to be larger than the number of nodes, as the orthogonal vectors are linearly independent.



[1] Neural Common Neighbor with Completion for Link Prediction.

[2] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.

[3] Graph Inductive Biases in Transformers without Message Passing.

[4] Rethinking the Expressive Power of GNNs via Graph Biconnectivity.
questions: questions: See Weaknesses.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_summary: The authors of this work introduce the Message Passing Link Predictor (MPLP), a link prediction model that uses pure message passing - as originally proposed by Gilmer et al. - to estimate structural similarities between nodes. The method is motivated by the fact that a single round of message passing using one-hot-encodings of nodes in un-attributed graphs can be used to estimate the common neighbors between node pairs. This idea is used to develop MPLP, a novel link prediction model that uses message passing to construct quasi-orthogonal vectors, whose inner product can be used to efficiently estimate structural similarities. Combining those vectors with node features and shortest path neighborhoods, MPLP obtains node representations that can be used by a classifier to predict links. Moreover, an advanced model MPLP+ is proposed with a simplified estimation of shortest path neighborhoods based on multiple rounds of message passing using one-hop information only. The two resulting models are evaluated in eight unattributed and seven attributed graphs, showing excellent performance compared to nine baseline methods.
strength_weakness: strength_weakness: [W1] I could not follow the role of the weight matrix W, which is assumed to be randomly initialized from a zero-mean distribution, in theorem 3.1, see Q1.

[W2] The experimental evaluation does not include results on the training time of the different models. 

[W3] The evaluation is solely based on HITS@50, see Q3.
questions: questions: [Q1] Referring to W1, what would happen if we assume that the weight matrix is absent, i.e. if we remove the weight parameters in the aggregation function?

[Q2] Related to W2, how does the training time of the proposed models compare to those of the baseline methods?

[Q3] I understand that the authors followed the evaluation metrics of OGB. Nevertheless, it would be good to include additional evaluation metrics such as accuracy, AUC-ROC or AUPR, see e.g. [arXiv 1505.04094].
limitations: limitations: The paper includes a detailed discussion of limitations in section H of the appendix, which I consider sufficient for this work.
paper_summary: paper_summary: This paper studies the problem of encoding pairwise structural features to enhance link prediction (LP). They note that previous literature has shown that standard MPNNs cannot encode the necessary pairwise information needed for LP. The authors argue that with careful design, MPNNs can in fact estimate pairwise structural features (e.g., common neighbors). This is done by equipping each node with quasi-orthogonal vector, which is used to estimate the counts of various structural features between two nodes. The authors then benchmark their method(s) on a number of datasets and compare against prominent benchmarks. They further highlight the efficiency of their method against other methods.
strength_weakness: strength_weakness: Weakness 1:
----------------
My main concern is that I'm unsure why the performance of this method is this good. Let me explain. MPLP estimates the structural counts via the use of quasi-orthogonal vectors. The predictor (i.e., score function), then takes as input (a) the elementwise product of both node representations (outputted by a MPNN) and (b) the estimated structural counts which are of the form #(p, q) such that (1, 1) is CNs. I'm just restating the Eq. at the end of 4.2.  

However, **how is this appreciatively different from BUDDY [16]?**. In the score function, they also include the elementwise product of both nodes in the target link. They then concatenate the same kind of structural counts considered by MPLP. They differ only in their method of estimating those counts. BUDDY (and ELPH) use subgraph sketching instead of orthogonal vectors. As such, **I can't seem to understand why MPLP/MPLP+ do so much better than BUDDY** (I know you report ELPH in your tables but it only does marginaly better than BUDDY). If the performance difference was small I wouldn't be as confused, by the gap on some datasets is enormous. For example BUDDY has a 49.85 Hits@100 on ogbl-PPA while MPLP+ is 65.24. A smaller, but still noticeable, gap is present on ogbl-Citation2 with BUDDY at 87.56 and MPLP+ at 90.72. My point is, the different in performance is non-trivial. The authors clearly report that their method can outperform BUDDY.

But as I noted, there doesn't seem to be anything specific reason why this is occurs, as they are estimating the same information. Is the approximation used by the authors better? If so, then why? The authors seems to argue that in Appendix F.1, where they compare the MSE of the label counts by ELPH/BUDDY and theirs. However, I have a few issues with the results: **(a)** The results aren't very clear to me. For example, is it on all test samples? Positive and negative? **(b)** Also the authors don't specify the # of hops used when estimating the counts for ELPH/BUDDY. From personal experience using their code, I find setting hops=3 can help improve the counts while still being fairly efficient. **(c)** **Most importantly, the authors only compare to MPLP and not MPLP+**. To me, this is a very important point as MPLP+ is itself a comprimise between efficiency and estimation quality. As shown in Table 2, MPLP is impractical on larger datasets as it's OOM. So why not compare the estimation quality of MPLP+, the model which still performs well but can scale to larger graphs? In my opinion it is very important that the authors include MPLP+ in the experiments in Appendix F.1.

I apologize for the wall of text, but the magnitude of increase over BUDDY seems very strange to me. To summarize, I suggest the authors: (a) Giving more explanation as to why the large discrepancy in performance may exist and (b) Include MPLP+ in Figures 8 and 9. I think if the authors can show that MPLP+ still does a much better job at estimating the structural features, that may be the answer. Otherwise, I very strongly recommend the authors try to give any difference that exist between the two methods that can explain it.

Weakness 2:
----------------
I find it odd that MPLP+ is more efficienct than BUDDY. MPLP+ and BUDDY both use L layers of message passings. Furthermore, as noted before, the scoring function is similar. The only difference is in estimating the structural counts.  However, BUDDY pre-computes and caches the subgraph counts, so it is qctually quite efficiency as they don't need to be recomputed. This is as opposed to MPLP+ which does have to recompute them each time. Because of this I don't really see how BUDDY can be slower except for various differences in implementation. Because from the theoretical complexity I shouldn't expect BUDDY to be slower. Again, I recommend the authors try to explain why this might be the case.

Weakness 3:
----------------
I should have noticed this earlier, but the similarity between MPLP and BUDDY hurts the novelty of the paper. As far as I can see, the authors are proposing a new method that can potentially estimate the structural counts a little better and faster. While noteworthy, this is a small contribution. However, I personally only find this to be a minor weakness of the paper.


Weakness 4:
----------------
Some benchmark datasets are missing. Including Cora, Citeseer, and Pubmed (see [33]). I recommend including them. Also, for HeaRT, I recommend reporting the results on all datasets and not just ogbl-ppa/collab/citation2. To be clear, this is a very minor weakness.
questions: questions: 1. Can you reproduce Figures 8 and 9 with MPLP+ against BUDDY/ELPH?
2. Can you better explain why MPLP+ is more efficienct than BUDDY?
3. Are there any other contributing factors that may lead to MPLP/MPLP+ doing better than a similar method like

Other:
--------

1. I recommend including the results of BUDDY in the main tables. I know you include ELPH and it typically does better, but it gets confusing when the results are for ELPH but the efficiency for BUDDY. I think it'll just make the experiments section easier to read.
limitations: limitations: yes

Comments: title: Round 3
Round 3
Round 2
Round 2 [2/2]: Proof Sketch for MPLP's Expressiveness over NCN
Round 2 [1/2]
Please read and respond to the rebuttal
comment: Thanks for your rebuttal which has answered some of my concerns. Due to Weaknesses 3 (Pairwise Orthogonality), I still have concerns about the correctness of the proof in this paper. Therefore, I would like to lower my confidence level in my assessment to 1.
We sincerely appreciate the reviewer's time and effort in reviewing our work. We address the following points in your feedback:

## GPU memory:
We measure the GPU memory peak consumption of MPLP+ on both PPA and Citation2 datasets during training and testing. As a comparison, we also measure the memory consumption of a typical 2-layer GCN model on the same datasets **with the same batch size**.

| GPU Mem(GB) | PPA | Citation2 |
|---|---|---|
| GCN | 18.73 | 68.59 |
| MPLP+ | 29.53 | 84.7 |

The results show that MPLP+ consumes more memory than GCN. This is because MPLP+ needs to store the node signatures for all nodes in the graph, which requires more memory than the GCN model. Even though the GPU memory cost is high for MPLP+ during training, its cost will be much lower during testing. During inference, MPLP+ only needs to retrieve the node embedding/signature of the two nodes in the link prediction task, and does not need to store the graph structure at all. Therefore, the time/space complexity of MPLP+ during inference is the same as the GCN/BUDDY model (linear to the number of edges to predict), and more efficient than the NCN (requiring finding CN nodes(NCN)/neighboring nodes(NCNC) by using graph structure).

In our current implementation, we just throw everything into the GPU memory and maximize the batch size to make the training process faster. Depending on the practical needs, we can probably further optimize the memory consumption of MPLP+ by using a more memory-efficient implementation, such as storing the node signatures on the CPU memory and loading them into the GPU memory when needed (using DataLoader).

## Why MPLP+ can outperform BUDDY:
We sincerely appreciate the reviewer's in-depth discussions with us, which really encourage us to rethink the theoretical and empirical aspects of our work compared to BUDDY/NCN. In fact, both works are our favorite papers and we are glad to see that they are compared with our work. In general, we still think that it may be too difficult to rigorously compare components (RA) across methods beyond the performance results. However, we also believe such discussions are valuable for the community. Below are some other thoughts we have that may help explain but not mean to thoroughly convince the reviewer on why weighted count can be important:

1. **Why NCN works**: As the reviewer pointed out, NCN may also implicitly capture the node degree with bias. Even though we show that NCN cannot encode the node degree in the strongly regular graph, its GCN-style message passing, **normalized by node degree**, can capture the node degree information in the CN nodes' representation in a biased way. We do not have a proof for this, but it may relate to the proof of Theorem 3.1 in our paper.

2. **Why BUDDY fails on PPA**: The hyperparameter matters. NCN uses a heavily tuned hyperparameter setting compared to BUDDY. It is possible that BUDDY can also achieve comparable performance with a more sophisticated hyperparameter search. MPLP+ has a comparable set of hyperparameters to BUDDY, but we indeed have a hyperparameter search until we landed a good enough result.

3. **BUDDY has some training difficulty**: The slightly performance drop from RA to BUDDY+RA in [5] may indicate that there is something suboptimal in the training process of BUDDY. Ideally, adding RA should improve the performance, if not degrade it. However, there is certainly some noise confusing BUDDY during training.


4. Response to "if we consider Katz":

    Katz is different from MPLP+ because Katz is weighted by number of hops. However, MPLP+ is weighted by the node degree. Therefore, performance of Katz may not indicate MPLP+'s.

4. **Seemingly high variance could be probably okay**: BUDDY can somehow perform well with large variance. Besides that the reviewer observed BUDDY can perform better beyond 3-hop, we also observe that MPLP+ can perform better with 2-hop neighbors ((1,2),(2,1)) even with relatively large variance. Therefore, it is possible that MPLP+ is better than BUDDY because of the path estimation with an acceptable variance (sounding not acceptable though by a factor of $10^3$). And in turn MPLP+ provides (1) lower estimation variance (2) weighted counting beyond (1,1).

## If all above are not correct:
Then we also wonder why BUDDY, with high variance estimation, can still perform well. We agree with the reviewer that the CN counts with relatively low variance might be the essential factor for BUDDY to perform well behind the scene.

------
Again, we sincerely appreciate the reviewer's time and effort in reviewing our work. The discussion with the reviewer has been very insightful and valuable, especially in understanding the performance advantage of MPLP+. We want to thank the reviewer again for the engaging discussion and the constructive feedback, which helps build a healthy ML research community.
I'll start off my comment by saying that I'll raise my score to a 5. However, I'm really just doing it out of respect for the authors and their patience with me. To be honest, I'm still not convinced that my concerns have been properly addressed. 

I tried to respond to most points below. However, one last question I have is if you can give more details as to how much GPU memory is needed to run MPLP+? I only ask because I noticed in D.4 that you guys used a 80Gb GPU which seems like a lot. Was that much memory necessary? I know this is the last day of rebuttals so if you don't answer it's fine. I'm just curious.

> In general, our contribution is (1) theoretical perspective ... (2) practical implementation

Thanks for the clarification, I agree that these are the main contributions of the paper. Apologies for any mixup. Regardless, my main problem is not with either of these but rather with my lack of understanding as to why MPLP+ does so well.

> Our claim is that MPLP+ can outperform BUDDY on PPA and Citation2 due to (1) lower estimation variance (Appendix F.1) (2) Norm Scaling and (3) Shortcut Removal.

This really gets at the heart of my problem. As you mentioned, (2) and (3) aren't contributions of the work. Also, F.1 **does not** show that MPLP has a lower estimation variance, rather that MPLP does. As you mentioned earlier, MPLP+ and BUDDY can't be compared. 

> We appreciate the reviewer reminding us that BUDDY also uses RA in its implementation. To have a more fair comparison, we remove the RA feature from BUDDY

I appreciate it but that wasn't really my point. My logic is the following:
1. The authors argue that weighting matters, however BUDDY uses RA and still performs much worse.
2. While on can argue that this is because RA ignores walks beyond (1, 1), I don't find this compelling as (a) NCN can do quite well just considering only CNs and (b) the walk estimation of MPLP+ seems to steeply decline beyond (1, 1). Even if we consider Katz, which does compute the \# of walks exactly and weights them, the performance is still the same or worse than just RA (see [5]). 

So let's consider ogbl-ppa: (a) With Katz, considering walks > 2 hurts performance and (b) BUDDY includes the weighted counts of CNs. MPLP doesn't do better due to the shortcut removal, as the authors show in their ablation study that it has limited effect on ogbl-ppa. This again brings me to my why question - why can MPLP+ outperform BUDDY by such a large margin? 

Maybe this is just going completely over my head (and apologies if so), but it doesn't make sense to me.

> We respectfully disagree that the walk estimation with relatively high variance will be useless in practice

I did not call it useless, just that estimation doesn't look great.

> Firstly, we do not have baselines for walk estimation to compare against. It is difficult to tell if the estimation is good or bad. 

I understand and sympathize with the authors. However, I don't think the lack of a baseline means we shouldn't question the estimation quality. I think it's fair to say that we'd prefer not be off by a factor of 10^3 when estimating the number of walks. To be clear, this isn't meant as a criticism.

> In fact, BUDDY, with such high variance esitmation, can still achieve the good performance considered as sota at its publication. 

Yes, and I think this is a problem! If it can do well with high variance are the counts themselves really important? If not, then why does it achieve SOTA (at the time)? This again goes with my general point about the need to understand why methods can perform well when they do.

As an aside, my hunch as to why BUDDY can still do well is that the vast majority of the impact is gained by the inclusion of CNs, of which the variance is low (but just a guess).
Thank you for the responses to my questions. In light of those responses as well as the responses to the other reviewers, I am happy to retain my positive evaluation.
We really appreciate the reviewer's careful investigation about our work, especially the time and efforts. Actually, we want to understand better what the reviewer is concerned about so that we can provide a more detailed explanation. We address the following points in your feedback:

1. We apologize for the confusion. We do not claim that these individual components are the core contribution of our work. We highlighted them in the rebuttal-discussion because we tried to address the reviewer's concern about why MPLP+ can outperform BUDDY. In general, our contribution is (1) **theoretical perspective**: pure node-level MPNN can estimate the common neighbors/walks between two nodes; (2) **practical implementation**: the proposed MPLP(+), built based on the node-level MPNN and previous studies, can achieve state-of-the-art performance on various datasets while maintaining node-level MPNN's efficiency.

The following discussions are to provide a more detailed explanation about why MPLP+ can outperform BUDDY:

2. Our claim is that MPLP+ can outperform BUDDY on PPA and Citation2 due to (1) lower estimation variance (Appendix F.1) (2) Norm Scaling and (3) Shortcut Removal.

3. We appreciate the reviewer reminding us that BUDDY also uses RA in its implementation. To have a more fair comparison, we remove the RA feature from BUDDY and re-run the ablation study of BUDDY. The results show that BUDDY, without RA as link feature, will drop to $30.19$ in Hits@100. This suggests that the RA feature is an important factor for BUDDY to perform well on PPA. Since MinHash/HyperLogLog of BUDDY cannot perform weighted counting, it explicitly adds RA as a feature to improve the performance on PPA. This is also why we believe that the weighted counting mechanism of MPLP+ can be crucial for its performance advantage over BUDDY.

|  | PPA(Hits@100) | Citation2(MRR) |
|---|---|---|
| BUDDY | 49.85 | 87.56 |
| BUDDY w/o RA | 30.19 | - |
| MPLP+ | 65.24 | 90.72 |
| MPLP+ w/o Shortcut Removal | 64.53 | 87.76 |
| MPLP+ w/o Norm Scaling | 53.94 | 90.25 |

4. Regarding the importance of the weighted counting on PPA, the ablation study above can clearly show that MPLP+ with Norm Scaling can perform significantly better. We respectfully disagree that the walk estimation with **relatively high variance** will be useless in practice. Firstly, we do not have baselines for walk estimation to compare against. It is difficult to tell if the estimation is good or bad. Moreover, even if we look at the node estimation of MPLP/BUDDY in Appendix F.1, the estimation variance is also as high as the walk estimation of MPLP+ (in the range of $10^2$ to $10^3$). In fact, BUDDY, with such high variance esitmation, can still achieve the good performance considered as sota at its publication. 

5. We appreciate the reviewer's suggestion about digging deeper into why MPLP(+) performs better than BUDDY. However, we respectfully disagree that bringing in other methods like NCN into discussion can help resolve the concern. NCN has a much different way to represent link. It is too difficult to make a rigorous ablation study across NCN and MPLP(+). In fact, the ablation study above when comparing components within MPLP(+) may also only tell part of the story, just like any ML paper. This is because there can be joint effects between the components in the system. At last, we can only conclude that the entire MPLP(+), with all components proven to be effective in both theoretical and empirical aspects within its own, can achieve sota performance over both BUDDY and NCN(C).

6. Another evidence that it is difficult to ablate between two methods happens to be shown on BUDDY itself. In Table 2 of [5], the benchmarking results show that BUDDY, with precomputed RA, can actually perform slightly worse than RA itself (BUDDY+RA's $47.33$ vs RA's $49.33$). This observation cannot conclude that RA is good or bad for BUDDY. However, by ablating RA within BUDDY, our results show that RA is crucial for BUDDY to achieve good performance on PPA.

--------
We apologize for the extensive response and appreciate the reviewer's careful investigation. We really do hope that our responses have addressed your concerns.

[5] Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking
I really do appreciate the author's continued indulgence of my comments and I don't mean to come off as overly critical. However, I spent a day thinking about it and my concerns still stand.

> Norm Scaling + Shortcut Removal

As I mentioned, I'm not discounting that they can help. But:

1. I don't see why I should see these as the authors contributions, as the authors themselves state in the paper that they are taken from prior work. As such, they are not core contributions of the authors. 
2. Furthermore, I'm quite quite confused by the norm scaling ablation study. The authors show that for ogbl-ppa, performance massively decreases when ablating norm scaling on ogbl-ppa. However, earlier, they also mention that BUDDY uses a pre-computed RA score for ogbl-ppa. In that case, if weighted counting is so important, why does BUDDY still lag behind MPLP+ so much on ogbl-ppa? You can argue that it's because RA only considers CNs (i,e,, walks of length (1, 1)) while MPLP+ considers higher-order walks. But (a) as the authors show in their earlier comment, the walk estimation outside of (1, 1) isn't very good and (b) regardless of the estimation quality, why can NCN (which only considers CN node representations) do so well? I don't see how to reconcile the authors findings with these points.
We really appreciate the reviewer's active engagement and insightful questions during the rebuttal-discussion process. Since the reviewer still has a major concern about the performance advantage of MPLP+ over BUDDY, we want to summarize the key points discussed so far:

## Summary of why MPLP+ can outperform BUDDY on PPA and Citation2:

1. **From the theoretical perspective**: MPLP+ has two key components, Norm Scaling and Shortcut Removal, which can boost the performance of MPLP+ over BUDDY. The Norm Scaling improves the expressiveness of MPLP+ by enabling weighted counting, while the Shortcut Removal avoids the distribution shift problem during training.

2. **From the empirical ablation study**: We conduct an additional ablation study to show that Norm Scaling and Shortcut Removal are crucial for the performance improvement of MPLP+ on PPA and Citation2. The empirical results demonstrate that Norm Scaling and Shortcut Removal are effective techniques for improving the performance of MPLP+ over BUDDY.

3. **From the experimental results**: In Table 2, we show that MPLP+, with distinct components like Norm Scaling and Shortcut Removal, can achieve better performance than BUDDY on both PPA and Citation2. In fact, MPLP+ not only outperforms BUDDY but also achieves state-of-the-art performance on PPA and Citation2 on the OGBL leaderboard.

We believe that the theoretical and empirical evidence provided above can explain how and why MPLP+ can outperform BUDDY on PPA and Citation2. We are eager to know what remains unclear or unsatisfactory to the reviewer and will be happy to provide further clarification. This can greatly help us improve the clarity of the paper and the presentation of the results.
We thank the reviewer for the feedback. We address the following points in your feedback:

## Q1: Can the position encodings estimate common neighbors?
We thank the reviewer for the insightful question. Theoretically, the positional encodings like RRWP/Resistance Distance/LapPE can estimate the number of common neighbors between two nodes. We first show that RRWP can estimate the Resource Allocation (RA) score between two nodes with a bias term.

> Consider a graph with two nodes $i$ and $j$ and ajacency matrix $A$. The RA score between node $i$ and node $j$ is defined as $RA(i,j) = (AD^{-1}A)_{ij}$, where $D$ is the degree matrix. For RRWP in [3], the relative positional encoding between node $i$ and node $j$ is $P\_{i,j} \in \mathbb{R}^{K}$. Then, the 3rd element of $P\_{i,j}$ is $P\_{i,j}^{(3)} = (D^{-1}A)^2\_{ij}=(D^{-1}AD^{-1}A)\_{ij}$. Therefore, RRWP can estimate the RA score between node $i$ and node $j$, biased by the degree of node $i$ and node $j$.

Compared to MPLP(+)'s unbiased estimation, RRWP's estimation of RA is biased. Moreover, the computation of RRWP involves adjacency matrix $A$'s power operation, which is much more computationally expensive than MPLP(+)'s pairwise structural estimation. Therefore, MPLP(+) provides a more efficient and unbiased estimation of the number of common neighbors between two nodes.

Similar to RRWP, Resistance Distance and LapPE can also estimate the number of common neighbors between two nodes. Resistance Distance Encoding can estimate the common neighbor between two nodes because of its equivalence to the random walk's ($D^{-1}A$ in RRWP) commute time [4]. LapPE can estimate the number of common neighbors between two nodes because it is derived from the eigenvectors of the Laplacian, which can tell the relative distance information between two nodes [5]. Rigorous investigation for Resistance Distance and LapPE estimation of common neighbors can be an interesting direction for future work.

[3] Graph Inductive Biases in Transformers without Message Passing.

[4] Rethinking the Expressive Power of GNNs via Graph Biconnectivity.

[7] Rethinking graph transformers with spectral attention.

## Q2: Pairwise Orthogonality
We apologize for the confusion. Since the quasi-orthogonal vectors are independently sampled from a standard normal distribution, their expectation is actually zero vector, orthogonal to each other. For $E[v_1^Tv_2] = E[v_1]^TE[v_2] = 0$, the independence of the vectors ensures that we can split the expectation into the product of the expectations. We will clarify this in the revised version.

------
Thanks for the feedback. If there are any other concerns, please let us know, and we will be happy to respond.
> As shown in the table, the performance of MPLP+ drops significantly when removing Norm Scaling on PPA

I appreciate the experiments but by argument isn't that these strategies can necessarily help, but (a) the impact is limited and (b) this isn't a technique introduced by the authors of this paper (i.e., not novel contributions). These are true as shortcut removal has a marginal impact on ogbl-ppa and norm scaling has the same on ogbl-citation2. I'll admit, I'm also surprised that shortcut removal has such a big effect on MPLP+ on citation2. As shown in the NCN paper (linked in my last response), shortcut removal actual hurts performance of NCN on ogbl-citation2. 

> we include the experimental results for the walk estimation quality of MPLP+ on Collab below

Thanks a lot. I agree there's no way to really judge these w/o a baseline (not your fault). However, at first glance the MSE seems high. Compared to the node estimations shown in Fig 8, it's a lot higher. Though I guess part of that is because is because there are just many more walks. Regardless this does suggest the estimation isn't great.

I really do appreciate all the discussion and additional experiments but my main concerns haven't been addressed. So I will keep my score.
Thanks for your response. The response has addressed Concern 1. Unfortunately, my concerns about Concerns 2,3,4 remain unaddressed. The suggestions and questions are as follows.

1. The authors may want to discuss the theoretical properties of the above-mentioned position encodings. For example, can the position encodings estimate common neighbors which is the key topic of this paper?
2. Let $h\_i=E[v\_i]$. As the rank of the matrix $(h\_1,h\_2,\dots,h\_N) \in \mathbb{R}^{N \times d}$ is less than $d$, the $N$ vectors $\\{h\_i\\}_{1}^N$ in the $d$-dimensional vector space can not be pairwise orthogonal.
We thank the reviewer for the feedback on our rebuttal. We address the following points in your feedback:

## Concern 1
We show that MPLP is more expressive and powerful than NCN:

**Expressiveness**: We present a proof sketch to show that MPLP is more expressive than NCN, specifically because MPLP can enable weighted node counting by Norm Scaling technique (Sec 4.1). Consider a $n_1 \times n_1$ rook's graph and a $n_2 \times n_2$ rook's graph, where $n_1 \neq n_2$. These two graphs are strongly regular graphs, but with different node degrees. Also any non-adjacent nodes in rook's graph will have two common neighbors. We investigate if NCN/MPLP can encode the non-adjacent node pair in $n_1 \times n_1$ rook's graph **differently** from the non-adjacent node pair in $n_2 \times n_2$ rook's graph. 

For NCN, (1) the GNN encoder (GCN/SAGE) will generate the same representation for all nodes due to regular graphs; (2) all the non-adjacent node pairs will have two common neighbors, leading to the same NCN score. 

For MPLP, because $n_1 \neq n_2$, the Norm Scaling technique will assign different norms to the quasi-orthogonal vectors of nodes in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs. Therefore, the non-adjacent node pairs in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs will have different MPLP representation due to the weighted node counting. This shows that MPLP is more expressive than NCN.

**powerful**: In Table 1/2, we empirically show that MPLP(+) can achieve better performance than NCN on various datasets, which demonstrates the effectiveness of MPLP for link prediction tasks.

We thank the reviewer for pointing this out. We will include the proof in the revised version.


## Concern 2
We thank the reviewer for the suggestion. RRWP, Resistance Distance encodings, and LapPE can all provide a pairwise structural representation, especially the distance information. Even though they are used for graph classification tasks, we also believe that there can be a connection between these encodings and link prediction tasks. This can be an interesting direction for future work. We will add a discussion on the connection between RRWP/Resistance Distance/LapPE and MPLP in the revised version, detailing how these positional encodings can also be decoded to provide pairwise structural representation, similar to MPLP, and potentially be used for link prediction tasks. For LapPE, we will also cover that it is derived from the orthogonal eigenvecotrs of the Laplacian matrix, while MPLP's quasi-orthogonal vectors are randomly initialized.

## Concern 3
We apologize for any confusion regarding the inductive ability of positional encodings. Previously, we referred the positional encodings specifically to the one formally defined in [5]. However, the positional encodings, like RRWP/Resistance Distance/LapPE, contains both the positional information and the structural information (this is also discussed in Sec 2 of [3]). We will clarify this when discussing the connection between RRWP/Resistance Distance/LapPE and MPLP in the revised version.

[5] On the Equivalence between Positional Node Embeddings and Structural Graph Representations.

## Concern 4
We apologize for the confusion regarding the orthogonality of the vectors. Consider two vectors $v_1$ and $v_2$ **independently** sampled from a standard normal distribution. The inner product of these two vectors $v_1^Tv_2$ is likely to be zero but **not always**. However, the expected value of the inner product is $E[v_1^Tv_2] = E[v_1]^TE[v_2] = 0$, which means that the vectors are orthogonal in expectation due to the independence of the vectors. This is why we refer to the vectors as quasi-orthogonal such that they are orthogonal from the probabilistic perspective. We will clarify this in the revised version.

-----
We hope that we have addressed your concerns. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.
Proof Sketch for MPLP's Expressiveness over NCN:

We present a proof sketch to show that MPLP is more expressive than NCN, specifically because MPLP can enable weighted node counting by Norm Scaling technique (Sec 4.1). Consider a $n_1 \times n_1$ rook's graph and a $n_2 \times n_2$ rook's graph, where $n_1 \neq n_2$. These two graphs are strongly regular graphs, but with different node degrees. Also any non-adjacent nodes in rook's graph will have two common neighbors. We investigate if NCN/MPLP can encode the non-adjacent node pair in $n_1 \times n_1$ rook's graph **differently** from the non-adjacent node pair in $n_2 \times n_2$ rook's graph. 

For NCN, (1) the GNN encoder (GCN/SAGE) will generate the same representation for all nodes due to regular graphs; (2) all the non-adjacent node pairs will have two common neighbors, leading to the same NCN score. 

For MPLP, because $n_1 \neq n_2$, the Norm Scaling technique will assign different norms to the quasi-orthogonal vectors of nodes in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs. Therefore, the non-adjacent node pairs in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs will have different MPLP representation due to the weighted node counting. This shows that MPLP is more expressive than NCN.
We appreciate the reviewer's feedback. We address the following points in your feedback:

## Empirical advantages of MPLP+'s Norm Scaling and Shortcut Removal. Q2
We thank the reviewer for the insightful comments. In our previous response, we have discussed the theoretical advantages of Norm Scaling and Shortcut Removal. The ablation study in Table 7/8 shows that these two techniques can effectively boost the MPLP's performance, depending on the dataset. We also show in Appendix F.1 that MPLP(+) has better estimation accuracy compared to ELPH/BUDDY.

Here, we further investigate the empirical advantages of Norm Scaling and Shortcut Removal in MPLP+ especially on PPA and Citation2 dataset. We keep all the other hyperparameters the same as the main experiments, and only remove Norm Scaling for PPA and Shortcut Removal for Citation2. The results are shown in the table below:

|  | PPA(Hits@100) | Citation2(MRR) |
|---|---|---|
| BUDDY | 49.85 | 87.56 |
| MPLP+ | 65.24 | 90.72 |
| MPLP+ w/o Shortcut Removal | 64.53 | 87.76 |
| MPLP+ w/o Norm Scaling | 53.94 | 90.25 |

As shown in the table, the performance of MPLP+ drops significantly when removing Norm Scaling on PPA. This indicates that Norm Scaling is crucial for capturing the nuanced structural information in the PPA dataset and the driving factor boosting the performance of MPLP+. On the other hand, the performance of MPLP+ decreases when removing Shortcut Removal on Citation2. This suggests that Shortcut Removal is essential for avoiding the distribution shift problem in the Citation2 dataset. Interestingly, the degenerated performance of MPLP+ is close to BUDDY when removing Norm Scaling on PPA and Shortcut Removal on Citation2. This empirically demonstrates that Norm Scaling and Shortcut Removal are effective techniques for improving the performance of MPLP+ over BUDDY.

Since NCN uses the common neighbors' node representation as link representation, it is not directly comparable to MPLP(+). Therefore, it is difficult to conclude that Norm Scaling and Shortcut Removal are not effective for MPLP(+) because NCN cannot exploit the node degree information and shortcut removal technique. We will include this empirical analysis in the revised version.

In fact, MPLP+ with Norm Scaling can be more expressive than NCN. We include a proof sketch in the end of the response.

The more expressive MPLP can face more severe distribution shift problems than NCN (Sec 5.3.2 in [2]). Therefore, the Shortcut Removal technique is more crucial for MPLP to avoid the distribution shift problem compared to NCN.

[2] FakeEdge: Alleviate Dataset Shift in Link Prediction

## Other concerns
We greatly appreciate the reviewer's suggestions. We will revise the paper to more explicitly indicate the walk-based counting mechanism of MPLP+ and the reference of the proposed techniques of MPLP(+). We will also include a discussion when comparing the efficiency results between BUDDY and MPLP.

## Q1: Estimation quality of MPLP+
We thank the reviewer for the suggestion. Similar to experiments in Appendix F.1, we include the experimental results for the walk estimation quality of MPLP+ on Collab below:

| Signature Dimension F | #(1,1) | #(1,2) | #(1,0) | #(2,2) |
|---|---|---|---|---|
| 1000 | 2.0 | 4.4*10^3 | 3.7*10^3 | 1.0*10^11 |
| 1500 | 0.49 | 1.0*10^3 | 2.1*10^3 | 1.3*10^11 |
| 2000 | 0.55 | 5.2*10^2 | 1.5*10^3 | 1.1*10^11 |
| 2500 | 0.23 | 4.3*10^2 | 1.9*10^3 | 1.2*10^11 |

Since there is no other baseline counting walk on graph, we can only investigate the results by itself. As shown in the table, the walk estimation quality of MPLP+ becomes worse when hops increase. This is because with longer hops, the number of walks between two nodes increases exponentially, leading to a higher estimation variance. When it comes to the #(2,2), the estimation variance becomes too high to be useful. Therefore, we observe that the performance gain from 3-hop above neighbors of MPLP(+) is marginal. In the meantime, increasing the signature dimension $F$ can help reduce the estimation variance. We will include this analysis in the revised version.

-----
We hope that we have addressed your concerns. Please let us know if there are any other concerns. We will be happy to respond.
Thanks for the detailed response. I list my further comments below.

| However, BUDDY cannot perform a weighted counting due to the mechanism of MinHash and HyperLogLog. 

I agree with this in relation to BUDDY. But I'm skeptical that this is actually important. Of course RA/AA do better than just CN, but let's consider NCN. It doesn't consider the degree of the CNs and does very well. Of course one can argue that maybe the degree information get's encoded in the node representations in NCN but we don't really know since it's not explicit in any way. So I'm technically not disagreeing with your claim, but I'm unsure if the proof really exists to claim that this matters.

| ELPH/BUDDY can cause a distribution shift problem, while MPLP will not

I agree in theory, but in practice recent work has shown that the effect of this distribution shift is quite minimal. NCN/NCNC also removes the link during training. On the OGB datasets, their studies show the effect is minimal, at best (Note: The results are only in an older version of the paper [here](https://arxiv.org/pdf/2302.00890v2) in Table 3 under NoTLR). Also [1] below studies the problem and conclude that it really only effects nodes of lower degree. They show that the overall performance on ogbl-collab and ogbl-citation2 is barely changed when removing target links. 

So again, I'm not disagreeing with you and I agree that this is a plus for MPLP/MPLP+. I'm just skeptical that it matters a lot in practice. 

[1] Zhu, Jing, et al. "Pitfalls in link prediction with graph neural networks: Understanding the impact of target-link inclusion & better practices." Proceedings of the 17th ACM International Conference on Web Search and Data Mining. 2024.

| In our experiments, the performance gain from 3-hop neighbors of MPLP(+) is marginal.

Interesting. It's likely dataset dependent. 

| While theoretically, MPLP+ and BUDDY should have similar efficiency. However, the implementation of two methods causes the efficiency discrepancy.

Ok, that makes sense. Please include a discussion of this when showing the efficiency results in the paper. As the current results are misleading. 

|  We do not include the Cora/Citeseer/Pubmed in our main experiment because recent studies[4,5] and we find that these three datasets overwhelmingly rely on the node attributes for link prediction tasks.

Ok, that's fair.

| However, beyond ELPH/BUDDY, MPLP(+) proposes several distinct components (Shortcut Removal, Norm Scaling, One-hot hubs, walk-based counting)

I thank the reviewers for the clarification.

However, I'm not disagreeing that the mechanism for estimating nodes/walk counts is different. That is a notable achievement. My point was regarding, as you mentioned, the "spirit" of the method being quite similar. That is still true. Furthermore, some of the components mentioned such as shortcut removal aren't proposed by this paper. In fact, it's used by multiple link prediction methods. This is also true for norm scaling where the authors explicitly refer to [12, 25] in their paper (line 246). To be clear, this isn't a bad thing, but I think the authors should be clear in their paper about what specifically they propose that's novel.

|  MPLP+ estimates the number of walks between two nodes

Thanks for the clarification. I recommend the authors make this a little more explicit in their paper, as when introducing MPLP+ it's only mentioned briefly on line 294.

Furthermore, in my opinion, the fact that MPLP+ uses walk-based features raises 2 more questions:

Q1: How well does it estimate walk of disparate lengths? I recommend the authors try to incorporate this into future versions of their paper. Because as of now, we really don't know how well it actually estimates the walks. This matters because it will give us some understanding on whether estimating these counts is actually important and driving the performance gain.

Q2: It doesn't explain to me why MPLP+ can perform so well. In general, MPLP+ tends to do slightly worse than MPLP across almost all datasets. Naively, this would suggest that if it were computationally feasible to run on ogbl-ppa, it would also do very well ~65 Hits@100. But this would still be much much higher than the performance of BUDDY on ogbl-ppa which is ~49. A similar observation stands for ogbl-citation2. I know this is hypothetical as the results don't exist, but I would find it hard to believe that estimating the node counts slightly better would lead to such a huge increase. Also, we don't really have any reason to expect that using walks in MPLP+ would help on the OGBs. In [33] they show that Katz (which just weights these walks) always does same/worse than RA/AA. So that likely can't explain it either for just MPLP+.

Basically, as I mentioned in my original review, I don't really understand why MPLP/MPLP+ does so well, especially compared to BUDDY. Because of that I'll keep my score.
Thanks for your response. Unfortunately, my concerns about Weaknesses 1,2,3 remain unaddressed. The questions are as follows.

1. The authors claim that MPLP is more expressive and powerful than NCN, but I can not find the corresponding theoretical analysis.
2. The shortest path distance is a pairwise structural representation (heuristic metrics), as shown in NBFNet [6]. [3] shows that relative random walk probabilities (RRWP) can express the shortest path distance. Moreover, Resistance Distance encodings [4] are similar in my opinion. Moreover, the discussion with Laplace position encodings (LapPE) [7]---which are also orthogonal---is missing.
3. The graph-level classification is inductive. They first train GNNs on the training set of graphs and then infer on the test set of **unseen** graphs. Why are the position encodings limited to transductive settings?
4. If the random quasi-orthogonal vectors have dimension $F<<N$, then their expectations also have dimension $F<<N$. So why are they orthogonal in expectation? Can you provide the theoretical analysis or reference to prove that "these vectors do not need to be strictly orthogonal but should be orthogonal in expectation"?



[6] Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction.
[7] Rethinking graph transformers with spectral attention.
Dear reviewers,

First of all, thank you for your service to the ML community. Writing high-quality reviews and engaging with authors' responses is essential to a healthy ML research community. 

It is essential that you read the rebuttals and provide a response and/or follow-up questions within the next few days. This will allow the authors sufficient time to react. While a detailed response addressing all points is not necessary, at a minimum, you should indicate you have read and considered the review and whether you will maintain or revise your score. Please also take the time to read the other reviews. Understanding your fellow reviewers' key arguments can help converge towards more similar ratings in cases of diverging scores.

I want to thank you again, and I look forward to following the discussions here.