Pith. sign in

REVIEW 3 major objections 4 minor 48 references

GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read SP4LP reads the shortest path between two nodes as a sequence and proves this representation is strictly more expressive than GNNs, NCN, BUDDY, NBFNet, and Neo-GNN, with best MRR on four of five benchmarks.

desk verdict Strong empirical idea, but the central expressiveness theorem is false: a simple circulant graph shows NCN distinguishes links that SP4LP cannot. read the letter →

arxiv 2507.07138 v1 pith:GMBDYTZF submitted 2025-07-09 cs.LG

Francesco Ferrini , Veronica Lachi , Antonio Longa , Bruno Lepri , Andrea Passerini This is my paper
classification cs.LG MSC 68T0768R10
keywords linkpredictiongraphneuralnetworksshortestpathsequencemodelsexpressivenessautomorphicnodeproblemstructuralfeaturesHeaRTbenchmark
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

SP4LP is a link-prediction model that runs a GNN once to embed every node, then reads the shortest path between the two candidate nodes as a sequence of node embeddings and processes that sequence with a Transformer, LSTM, or injective sum. The paper's central claim is that this recipe is strictly more expressive than pure GNNs and four established structural-feature methods — NCN, BUDDY, NBFNet, and Neo-GNN — meaning SP4LP can tell apart structurally different links that those models collapse to one representation, even when the two endpoints are automorphic (interchangeable under a graph symmetry). The paper further claims this expressiveness pays off empirically: under the hard HeaRT evaluation protocol, SP4LP reaches the best MRR on four of five benchmarks, with the largest margin on Citeseer (41.08 versus 28.65 for NCN), while keeping GPU memory nearly flat as batch size grows because message passing happens once and shortest paths are precomputed. Ablations indicate both ingredients matter, since a sequence model on raw node features, and GNN embeddings combined with only path length, both underperform the full model.

What carries the argument

The load-bearing object is the shortest-path sequence: an ordered list of distinct nodes $(u = u_0, u_1, \ldots, u_k = v)$ with consecutive nodes connected by edges and $k = d_G(u,v)$ minimal. SP4LP feeds the GNN embeddings of these nodes into a sequence model $\varphi$ (a Transformer, an LSTM, or an injective summation), aggregates the resulting path representations over the multiset of shortest paths, and merges the summary with the two endpoint embeddings through a combination function $\rho$. Because a single message-passing pass produces every node embedding, the path readout adds only a precomputed breadth-first search, which is what keeps memory flat and avoids the per-link subgraph extraction that heavier structural methods pay for. The sequence model is what makes the design flexible: with $\varphi$ set to the identity and summation as the aggregation, the construction is argued to reproduce NCN, while richer choices of $\varphi$ weight each node along the path and thereby encode multi-hop structure that endpoint-only aggregations cannot see. In the implementation, the shortest path is the first one BFS returns, and pairs in different connected components receive a synthetic one-edge path.

What would settle it

Run the two reduction checks on small graphs. On a triangle, where the two candidate endpoints are joined by an edge and also share a third neighbor, instantiate SP4LP exactly as the proof prescribes, with the identity sequence model and summation aggregation: the shortest path between the adjacent endpoints is just the two-node edge, so the shared neighbor never enters the readout, and the representation differs from NCN's common-neighbor sum, contradicting the claimed exact reduction. Separately, enumerate all connected graphs up to six nodes and compare NBFNet, with injective functions as the proof assumes, against an injective pure GNN: the lemma predicts NBFNet separates no pair of non-automorphic links that the GNN cannot, so a single counterexample would settle the dominance chain.

Watch

Extended reading notes

Core claim

The discovery, on the paper's own terms, is that the shortest path between two nodes is exactly the structural context that node-centric GNNs miss, and that reading it as a sequence makes that context usable. SP4LP computes, for any candidate pair $(u,v)$, the representation $\rho\big(\mathrm{GNN}(u),\, \mathrm{GNN}(v),\, \mathrm{AGG}\{\varphi(\mathrm{GNN}(P)) : P \in P^*_G\{u,v\}\}\big)$, where the GNN embeddings come from one message-passing pass over the whole graph, $P^*_G\{u,v\}$ is the multiset of shortest paths between the endpoints, $\varphi$ is a sequence model over the embeddings of the nodes along a path, AGG aggregates over paths, and $\rho$ combines endpoint and path information. Theorem 3.5 asserts that the class of models defined this way is strictly more expressive than pure GNNs, NCN, BUDDY, NBFNet, and Neo-GNN: every pair of links any of those models can separate is also separable by some SP4LP configuration, and there exist graphs where those five collapse two non-automorphic links that SP4LP separates, because the shortest path is always defined between nodes in the same connected component and carries multi-hop structure, unlike a common-neighbor count. Proposition 3.4 adds that SP4LP does not suffer from the automorphic node problem, and the experiments report the best MRR on four of five HeaRT benchmarks, with the largest gain on Citeseer.

Load-bearing premise

The strict-expressiveness theorem rests on two reduction claims: that SP4LP with the identity sequence model reproduces NCN exactly by reading the endpoints' common neighbors off the shortest path, and that NBFNet is no stronger than an ordinary message-passing GNN; if either reproduction fails on some graph, the dominance result no longer follows from the given proof.

Editorial extensions

If this is right

  • Under the HeaRT evaluation protocol, SP4LP reports the best MRR on Cora, Citeseer, Pubmed, and ogbl-collab and is second on ogbl-ddi; the Citeseer margin is 41.08 versus 28.65 for the runner-up NCN, roughly a 43 percent gain.
  • Proposition 3.4 means the automorphic node problem does not constrain SP4LP: it can assign distinct representations to non-automorphic links whose endpoints are automorphic, a separation no standard GNN can achieve.
  • Theorem 3.5 places pure GNNs, NCN, BUDDY, NBFNet, and Neo-GNN strictly below SP4LP in expressiveness: any link separation those methods achieve is also achievable by some SP4LP configuration, and there are graphs where they collapse a pair that SP4LP separates.
  • Because message passing runs once and shortest paths are a preprocessing step, the model scales to large batches: on ogbl-collab, GPU memory stays between 0.77 and 6.84 GB across batch sizes with no out-of-memory failures, and inference time remains competitive with SEAL.
  • The ablations show the full model beats both a sequence model applied to raw node features and GNN embeddings used with only the path length, indicating that learned node representations and the ordered path readout each contribute to the result.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The recipe generalizes beyond link prediction: any pairwise graph task, from edge classification to knowledge-graph completion, could follow the same 'embed all nodes once, then read the shortest-path trace' pattern, and because reversing a path should not change the link, testing a reversed-path variant would probe how much of the gain comes from sequence order.
  • The paper's definition aggregates over all shortest paths, but the implementation keeps only the first path BFS returns; averaging or sampling over equally short paths is a natural variant that could shift both expressiveness and variance on graphs with many shortest-path ties.
  • The synthetic one-edge path assigned to pairs in different connected components is exactly where the expressiveness guarantee lapses; a quantitative study of accuracy against the fraction of cross-component test pairs would map where the theory stops applying.
  • If the argument that NBFNet is no stronger than a pure GNN is correct, it implies that other Bellman-Ford-style path aggregators inherit the same expressiveness ceiling, a broader consequence than the paper states and one a small-graph search could confirm.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes SP4LP, a link prediction model in the GNN-then-SF paradigm that computes GNN node embeddings, extracts a shortest path between the endpoints of each candidate link, and processes the embeddings along that path with a sequence model such as an LSTM or Transformer. The main theoretical claim, Theorem 3.5, is that SP4LP is strictly more expressive than pure GNNs, NCN, BUDDY, NBFNet, and Neo-GNN. The paper also reports experimental results on five datasets under the HeaRT evaluation protocol, claiming state-of-the-art MRR on four of five datasets, along with ablations and a scalability analysis.

Significance. If Theorem 3.5 were correct, the paper would contribute a useful expressiveness hierarchy for link prediction models and a principled justification for using shortest-path sequences. The empirical protocol is sound in several respects: the code is referenced, results are averaged over five seeds with standard deviations, and the HeaRT protocol is used. However, the central expressiveness theorem is invalid: a concrete counterexample on a vertex-transitive circulant shows that SP4LP cannot distinguish a pair of non-automorphic links that NCN distinguishes, directly refuting the claimed strict expressiveness. Additionally, the NBFNet equivalence proof in Appendix A contains a gap. These problems affect the paper's primary theoretical contribution.

major comments (3)
  1. [Appendix A, Theorem 3.5 (NCN comparison)] The proof step (2) claims that when links have common neighbors, setting phi to the identity, AGG to summation, and rho appropriately makes SP4LP reduce exactly to NCN. This is false for adjacent pairs: if (u,v) is an edge that shares a common neighbor w, the shortest path between u and v has length one and consists only of u and v, so w is not on the path and its embedding is never aggregated by SP4LP, while NCN includes w. Thus the reduction does not hold, and the implication required by Definition 2.10 is not established. The claim fails concretely on the 7-vertex circulant C7(1,2) with identical node features: every permutation-equivariant GNN assigns one constant embedding to all nodes, so SP4LP gives the same representation to edges (0,1) and (0,2), whereas NCN distinguishes them because |N(0) cap N(1)| = 2 and |N(0) cap N(2)| = 1. These links are non-automorphic with automorphic endpoints, contradicting Theorem 3.5.
  2. [Appendix A, Eq. (9) and Eq. (14) (NBFNet comparison)] The induction proving that NBFNet is no more expressive than a pure GNN omits the initial edge representation h^(0)_(u,v) from the AGGREGATE set in the inductive step. Equation (9) defines the NBFNet update as AGGREGATE over the neighboring edge messages union {h^(0)_(u,v)}, but the final equivalence in Eq. (14) only compares the aggregated MESSAGE terms over incident edges. Since h^(0)_(u,v) depends on INDICATOR(x_u^0, x_v^0) and is not captured by the neighboring edge messages, the induction does not establish the claimed equivalence. The strict expressiveness result over NBFNet is therefore unsupported.
  3. [Appendix A, Proposition 3.4 proof] The proof's restatement of Proposition 2.9 inverts the conclusion: it says a model suffers from the automorphic node problem when 'it holds that ... F((u,v),G) != F((u',v'),G)', whereas the correct condition is equality. As printed, the formal statement of what is being disproved is logically wrong, so the proof of Proposition 3.4 is not verifiable in its written form. The intended example in Figure 1 may still illustrate the claim, but the proof needs a corrected formulation.
minor comments (4)
  1. [Equation (8)] The notation for the sequence model phi is ambiguous: the text defines phi : R^(k x d) -> R^d, but the equation writes phi(GNN(ui,G)) inside the multiset, which suggests a per-node function. Please clarify that phi is applied to the entire sequence of k embeddings.
  2. [Section 3 heading] The heading calls SP4LP an 'SF-then-GNN Model', but the paper consistently describes it as GNN-then-SF in the introduction and in the body of Section 3. This inconsistency should be corrected.
  3. [Appendix A, Proposition 3.4 example] The sentence 'u' ≃ u' via the identity, and v ≃ u via an automorphism' should presumably read 'u ≃ u''; as written, the example does not show that both endpoints are automorphic.
  4. [Limitations vs. Appendix D] The Limitations paragraph states that expressiveness depends on the availability of a shortest path, but Appendix D says that when no path exists, SP4LP assigns a synthetic path of length one between the endpoints. These two statements should be reconciled.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the expressiveness theorem is argued by construction and a separating example, and the cited NCN result is external, not self-referential.

full rationale

The paper's central theoretical claim is a relative-expressiveness statement, and its proof follows the standard pattern: show that SP4LP can simulate a pure GNN and NCN by specific choices of rho, AGG and phi, then exhibit a graph and a pair of non-automorphic links that SP4LP separates while NCN/pure GNNs cannot. The 'reduces exactly to NCN' step is not a fitted quantity renamed as a prediction; it is an explicit construction showing that the more expressive class contains the less expressive one, which is exactly what the more-expressive definition requires. The NBFNet comparison relies on an induction that NBFNet is as expressive as a pure GNN, and the BUDDY/Neo-GNN comparison imports Theorem 2 of the NCN paper, whose authors do not overlap with the present paper, so no self-citation chain is load-bearing. The only self-citation is Reference [2] in the related-work survey, used as background for shortest-path graph encodings; it does not support the theorem or the benchmark claims. The empirical MRR/Hits results come from standard validation-set hyperparameter tuning and are not obtained by fitting parameters to the reported test numbers. No specific equation or fitted value reduces by construction to the claimed result, so no circular step can be exhibited; the proof concerns correctness, not circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central mathematical claim has no fitted constants, so the free-parameter ledger is empty. The proof, however, rests on several unproved or fragile premises: injective universal approximators, a reduction of SP4LP to NCN that is only true in special cases, a claimed collapse of NBFNet to pure-GNN expressiveness, an external theorem about NCN versus Neo-GNN and BUDDY, and an implicit connectivity assumption that the limitations section partially acknowledges.

assumptions (5)
  • standard math Injective universal approximators exist for all aggregation, message, and combination functions used in the proofs (g, COMB, AGG, MESSAGE, INDICATOR all injective).
    Appendix A repeatedly invokes injectivity to equate equality of representations with equality of underlying sets. This is standard practice, but the NBFNet proof also assumes the injective regime preserves the claimed equivalence.
  • ad hoc to paper For links with common neighbors, SP4LP with phi as identity and AGG as summation reduces exactly to NCN, meaning common neighbors coincide with shortest-path nodes and endpoint duplication is harmless.
    Appendix A, NCN bullet. This is the load-bearing reduction for the strict-expressiveness theorem; it fails for adjacent pairs and for irrelevant endpoint contributions.
  • ad hoc to paper NBFNet's expressive power is no greater than a pure GNN under injective functions.
    Appendix A, NBFNet bullet. The proof of this equivalence omits the initial h0 term from the aggregation in Equation 9; without this lemma the strict-expressiveness claim over NBFNet collapses.
  • domain assumption Theorem 2 of Wang et al. (the NCN paper) is correct and applies here, i.e., NCN is more expressive than Neo-GNN and BUDDY.
    Appendix A uses this cited theorem to transfer expressiveness; the result is not re-derived in this paper and is not independently checked.
  • domain assumption The graph is connected, or disconnected pairs are handled by a synthetic length-one path, so every pair has a shortest path.
    Definitions 3.1 through 3.3 require a path; Section 6 Limitations states expressiveness depends on shortest-path availability, and Appendix D adds a synthetic length-one path for disconnected pairs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction." pith.science (2026). https://pith.science/paper/GMBDYTZF

@misc{pith2026250707138,
  author       = {Pith},
  title        = {Pith review of: GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GMBDYTZF}},
  note         = {Machine review of arXiv:2507.07138}
}
read the original abstract

Graph Neural Networks (GNNs) often struggle to capture the link-specific structural patterns crucial for accurate link prediction, as their node-centric message-passing schemes overlook the subgraph structures connecting a pair of nodes. Existing methods to inject such structural context either incur high computational cost or rely on simplistic heuristics (e.g., common neighbor counts) that fail to model multi-hop dependencies. We introduce SP4LP (Shortest Path for Link Prediction), a novel framework that combines GNN-based node encodings with sequence modeling over shortest paths. Specifically, SP4LP first applies a GNN to compute representations for all nodes, then extracts the shortest path between each candidate node pair and processes the resulting sequence of node embeddings using a sequence model. This design enables SP4LP to capture expressive multi-hop relational patterns with computational efficiency. Empirically, SP4LP achieves state-of-the-art performance across link prediction benchmarks. Theoretically, we prove that SP4LP is strictly more expressive than standard message-passing GNNs and several state-of-the-art structural features methods, establishing it as a general and principled approach for link prediction in graphs.

Figures

Figures reproduced from arXiv: 2507.07138 by the authors.

Figure 1
Figure 1. Links (v, u) and (v, u′ ) have different structural roles within the graph, yet a GNN assigns them identical representations. In this paper we propose SP4LP, a novel method in the GNN￾then-SF paradigm that combines high expressiveness with computational efficiency. SP4LP constructs a path-aware rep￾resentation by incorporating the embeddings of all nodes along the shortest path connecting the two endpoints. These no… view at source ↗
Figure 2
Figure 2. Overview of the SP4LP framework. First, a GNN is used to compute contextualized embeddings for all nodes in the graph. Then, for each target link, the shortest path connecting the two endpoints is extracted. The embeddings of the nodes along this path are passed to a sequence model (e.g., Transformer or LSTM) to compute a path-aware link representation. This limitation is well-known in the literature [4, 44]. Import… view at source ↗
Figure 3
Figure 3. Inference time and GPU memory usage on ogbl-collab, [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Links (u, v),(u, v′ ) are not distinguished by NCN while are distinguished by SP4LP. Models Cora Citeseer Pubmed Ogbl-ddi Ogbl-collab MRR MRR MRR MRR MRR CN 9.78 8.42 2.28 7.11 4.20 AA 11.91 10.82 2.63 7.37 5.07 RA 11.81 10.84 2.47 9.10 6.29 Shortest Path 5.04 5.83 0.8…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

48 extracted references · 26 canonical work pages

  1. [1]

    Friends and neighbors on the web.Social Networks, 25(3): 211–230, 2003

    Lada A Adamic and Eytan Adar. Friends and neighbors on the web.Social Networks, 25(3): 211–230, 2003. ISSN 0378-8733. doi: https://doi.org/10.1016/S0378-8733(03)00009-1. URL https://www.sciencedirect.com/science/article/pii/S0378873303000091

    doi:10.1016/s0378-8733(03)00009-1 2003

  2. [2]

    Simple Path Structural Encoding for Graph Transformers

    Louis Airale, Antonio Longa, Mattia Rigon, Andrea Passerini, and Roberto Passerone. Simple path structural encoding for graph transformers.arXiv preprint arXiv:2502.09365, 2025

    work page Pith review arXiv 2025

  3. [3]

    An optimal lower bound on the number of variables for graph identification.Combinatorica, 12(4):389–410, 1992

    Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification.Combinatorica, 12(4):389–410, 1992

    1992

  4. [4]

    Bronstein, and Max Hansmire

    Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/forum? id=m1oqEOAozQU

    work page 2023

  5. [5]

    Edge classification on graphs: New directions in topological imbalance

    Xueqi Cheng, Yu Wang, Yunchao Liu, Yuying Zhao, Charu C Aggarwal, and Tyler Derr. Edge classification on graphs: New directions in topological imbalance. InProceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, pages 392–400, 2025

    work page 2025

  6. [6]

    Empirical evaluation of gated recurrent neural networks on sequence modeling.arXiv preprint arXiv:1412.3555, 2014

    Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling.arXiv preprint arXiv:1412.3555, 2014

    arXiv 2014

  7. [7]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms. MIT Press, Cambridge, MA, 3rd edition, 2009

    work page 2009

  8. [8]

    Generalizations of k-dimensional weisfeiler–leman stabiliza- tion

    Anuj Dawar and Danny Vagnozzi. Generalizations of k-dimensional weisfeiler–leman stabiliza- tion. Moscow Journal of Combinatorics and Number Theory, 9(3):229–252, 2020

    work page 2020

Show all 48 references
  1. [9]

    Thelinkregressionproblemingraphstreams

    BowenDong,CharuCAggarwal,andSYuPhilip. Thelinkregressionproblemingraphstreams. In 2019 IEEE International Conference on Big Data (Big Data), pages 1088–1095. IEEE, 2019

    2019

  2. [10]

    node2vec: Scalable feature learning for networks

    Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016

    2016

  3. [11]

    Exploring network structure, dynamics, and function using networkx

    Aric Hagberg, Pieter J Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008

    2008

  4. [12]

    Inductive representation learning on large graphs

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 30. Curran Associ...

    2017

  5. [13]

    Inductive representation learning on large graphs

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017

    2017

  6. [14]

    Long short-term memory.Neural computation, 9(8): 1735–1780, 1997

    Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory.Neural computation, 9(8): 1735–1780, 1997

    1997

  7. [15]

    Open graph benchmark: Datasets for machine learning on graphs

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020. 10

    2020

  8. [16]

    Prediction of protein–protein interaction using graph neural networks.Scientific Reports, 12(1):8360, 2022

    Kanchan Jha, Sriparna Saha, and Hiteshi Singh. Prediction of protein–protein interaction using graph neural networks.Scientific Reports, 12(1):8360, 2022

    2022

  9. [17]

    A new status index derived from sociometric analysis.Psychometrika, 18(1):39–43, 1953

    Leo Katz. A new status index derived from sociometric analysis.Psychometrika, 18(1):39–43, 1953

    1953

  10. [18]

    Semi-supervised classification with graph convolutional networks

    Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016

    2016 arXiv

  11. [19]

    Variational graph auto-encoders

    Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016

    2016 arXiv

  12. [20]

    Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking

    Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. InThirty-seventhConferenceonNeuralInformationProcessingSystemsDatasets and Benchmar...

    2023

  13. [21]

    Distance encoding: Design provably more powerful neural networks for graph representation learning.Advances in Neural Information Processing Systems, 33:4465–4478, 2020

    Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning.Advances in Neural Information Processing Systems, 33:4465–4478, 2020

    2020

  14. [22]

    Line graph neural networks for link weight prediction.Physica A: Statistical Mechanics and its Applications, page 130406, 2025

    Jinbi Liang, Cunlai Pu, Xiangbo Shu, Yongxiang Xia, and Chengyi Xia. Line graph neural networks for link weight prediction.Physica A: Statistical Mechanics and its Applications, page 130406, 2025

    2025

  15. [23]

    The link prediction problem for social net- works

    David Liben-Nowell and Jon Kleinberg. The link prediction problem for social net- works. In Proceedings of the Twelfth International Conference on Information and Knowl- edge Management, CIKM ’03, page 556–559, New York, NY, USA, 2003. Association for Computing Machinery. ISBN...

    2003

  16. [24]

    Computational complexity of the weisfeiler-leman dimension

    Moritz Lichter, Simon Raßmann, and Pascal Schweitzer. Computational complexity of the weisfeiler-leman dimension. In33rd EACSL Annual Conference on Computer Science Logic (CSL 2025), pages 13–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025

    2025

  17. [25]

    Linkpredictionincomplexnetworks: Asurvey

    LinyuanLüandTaoZhou. Linkpredictionincomplexnetworks: Asurvey. PhysicaA:statistical mechanics and its applications, 390(6):1150–1170, 2011

    2011

  18. [26]

    Link prediction via matrix factorization

    Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. InMachine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2011, Athens, Greece, September 5-9, 2011, Proceedings, Part II 22, pages 437–452. Springer, 2011

    2011

  19. [27]

    Weisfeiler and leman go neural: Higher-order graph neural networks

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. InProceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4...

    2019

  20. [28]

    Clusteringandpreferentialattachmentingrowingnetworks

    M.E.J.Newman. Clusteringandpreferentialattachmentingrowingnetworks. Phys.Rev.E ,64: 025102, Jul 2001. doi: 10.1103/PhysRevE.64.025102. URLhttps://link.aps.org/doi/ 10.1103/PhysRevE.64.025102

    2001 doi

  21. [29]

    A review of relational machine learning for knowledge graphs.Proceedings of the IEEE, 104(1):11–33, 2015

    Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs.Proceedings of the IEEE, 104(1):11–33, 2015

    2015

  22. [30]

    Knowledge graph embedding for link prediction: A comparative analysis.ACM Transactions on Knowledge Discovery from Data (TKDD), 15(2):1–49, 2021

    Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. Knowledge graph embedding for link prediction: A comparative analysis.ACM Transactions on Knowledge Discovery from Data (TKDD), 15(2):1–49, 2021

    2021

  23. [31]

    On the equivalence between positional node embeddings and structural graph representations.arXiv preprint arXiv:1910.00452, 2019

    Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations.arXiv preprint arXiv:1910.00452, 2019

    1910 arXiv

  24. [32]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017. 11

    2017

  25. [33]

    Graph attention networks.stat, 1050(20):10–48550, 2017

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks.stat, 1050(20):10–48550, 2017

    2017

  26. [34]

    Graph attention networks

    PetarVeličković,GuillemCucurull,ArantxaCasanova,AdrianaRomero,PietroLiò,andYoshua Bengio. Graph attention networks. InInternational Conference on Learning Representations,

  27. [35]

    Equivariant and stable positional encoding for more powerful graph neural networks

    Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. InInternational Conference on Learning Representations, 2022. URLhttps://openreview.net/forum?id=e95i1IHcWj

    2022

  28. [36]

    Neural common neighbor with completion for link prediction

    Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. InThe Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=sNFLN3itAd

    2024

  29. [37]

    Apan: Asynchronous propagation attention network for real-time temporal graph embedding

    Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, et al. Apan: Asynchronous propagation attention network for real-time temporal graph embedding. InProceedings of the 2021 international conference on management o...

    2021

  30. [38]

    How powerful are graph neural networks?, 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2019

    2019

  31. [39]

    Revisiting semi-supervised learning with graph embeddings

    Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. InInternational conference on machine learning, pages 40–48. PMLR, 2016

    2016

  32. [40]

    Do transformers really perform badly for graph representation?Advances in neural information processing systems, 34:28877–28888, 2021

    Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation?Advances in neural information processing systems, 34:28877–28888, 2021

    2021

  33. [41]

    Graph convolutional neural networks for web-scale recommender systems

    Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedingsofthe24thACMSIGKDDinternationalconferenceonknowledgediscovery&data mining, pages 974–983, 2018

    2018

  34. [42]

    Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction.Advances in Neural Information Processing Systems, 34:13683–13694, 2021

    Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction.Advances in Neural Information Processing Systems, 34:13683–13694, 2021

    2021

  35. [43]

    Link prediction based on graph neural networks.Advances in neural information processing systems, 31, 2018

    Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks.Advances in neural information processing systems, 31, 2018

    2018

  36. [44]

    Labelingtrick: Atheoryofusing graph neural networks for multi-node representation learning.Advances in Neural Information Processing Systems, 34:9061–9073, 2021

    MuhanZhang,PanLi,YinglongXia,KaiWang,andLongJin. Labelingtrick: Atheoryofusing graph neural networks for multi-node representation learning.Advances in Neural Information Processing Systems, 34:9061–9073, 2021

    2021

  37. [45]

    Progresses and challenges in link prediction.Iscience, 24(11), 2021

    Tao Zhou. Progresses and challenges in link prediction.Iscience, 24(11), 2021

    2021

  38. [46]

    Predicting missing links via local information

    Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(4):623–630, October 2009. ISSN 1434-6036. doi: 10.1140/epjb/e2009-00335-8. URL http://dx.doi.org/10.1140/EPJB/E2009-00335-8

    2009 doi

  39. [47]

    Neural bellman-ford networks: A general graph neural network framework for link prediction.Advances in neural information processing systems, 34:29476–29490, 2021

    Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction.Advances in neural information processing systems, 34:29476–29490, 2021. 12 A Proofs Proposition 3.4SP4LP does not suff...

    2021

  40. [2018]

    URL https://openreview.net/forum?id=rJXMpikCZ

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.