Pith. sign in

REVIEW 5 major objections 5 minor 1 cited by

Bridging Theory and Practice in Link Representation with Graph Neural Networks

T0 review · 5 major / 5 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 A three-parameter framework (endpoint encoder power, neighborhood encoder power, radius) orders link-prediction GNNs into a provable hierarchy, and a symmetry score shows when the extra power pays off.

desk verdict Worth reading for the framework and benchmark, but the central hierarchy theorem is false as stated; the paper needs a corrected theorem and a real proof. read the letter →

arxiv 2506.24018 v1 pith:FYNPQOGP submitted 2025-06-30 cs.LG cs.AI

Veronica Lachi , Francesco Ferrini , Antonio Longa , Bruno Lepri , Andrea Passerini , Manfred Jaeger This is my paper
classification cs.LGcs.AI
keywords linkpredictiongraphneuralnetworksexpressivepowerWeisfeiler-Lehmanrepresentationmessagepassingsymmetrysyntheticbenchmark
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

This paper argues that the expressive power of message-passing GNNs for link representation — how well they tell structurally different node pairs apart — can be summarized by three parameters: the power of the function encoding the two endpoints, the power of the function encoding the neighborhood, and the radius of that neighborhood. The authors package this as the $k_\phi$-$k_\rho$-$m$ framework and prove that any model relying only on endpoint encodings cannot tell links with automorphic endpoints apart, no matter how strong its encoder is. Within the framework, expressiveness grows with radius plus message-passing depth and with the Weisfeiler-Lehman strength of the neighborhood encoder, which places SEAL strictly above NCN, Neo-GNN, and ELPH, and all of them above pure GNNs. They also build the first synthetic benchmark for link-level expressiveness and a graph symmetry score, and use both to show that on highly symmetric graphs the expressive models clearly outperform the simple ones, while on low-symmetry graphs simple models suffice. If the account is right, model choice for link prediction can be grounded in a few computable quantities instead of trial and error.

What carries the argument

The load-bearing object is the $k_\phi$-$k_\rho$-$m$ framework, a template into which a message-passing link model fits if its link function can be written as $\mathrm{COMB}\!\left(g(\phi(u),\phi(v)),\, \mathrm{AGG}\{\psi(\rho(i,h(u,v)),u,v) \mid i \in \bigcup_{j=0}^{m} \mathcal{N}^{j}(u,v)\}\right)$. In this template, $\phi$ and $\rho$ are message-passing functions whose Weisfeiler-Lehman dimensions are $k_\phi$ and $k_\rho$ ($k$-WL being the standard hierarchy of graph-isomorphism tests, and $k_\rho$ the smallest $k$ such that $\rho$ is as powerful as $k$-WL); $m$ is the radius of the node sets around the link that are aggregated; $h$ rewrites node features using pairwise link information; $\psi$ scales passing representations by coefficients extracted from the graph; and $g$, $\mathrm{AGG}$, $\mathrm{COMB}$ are fixed aggregation and combination functions. Every model the paper studies — pure GNNs, NCN, Neo-GNN, ELPH, BUDDY, SEAL — is a special case, so expressiveness comparisons reduce to comparing parameters, which Theorems 3.2 and 3.3 convert into a hierarchy. The second device is the symmetry score $\widehat{r}_G = 1 - (|\mathrm{WL}_G|-1)/(|V_G|-1)$, which approximates the orbit-based symmetry of a graph using the number of colors $1$-WL converges to, and which the paper uses to test whether theoretical expressiveness pays off on real datasets.

What would settle it

Run an exhaustive search over small graphs for two non-automorphic links $(u,v)$ and $(u',v')$ that a $1$-WL link model with radius $m_1$ and $l_1$ layers separates, while no $1$-WL model with radius $m_2 < m_1$ and $l_2 \ge l_1 + m_1 - m_2$ layers separates them; one such pair would refute the depth-for-radius compensation step in Theorem 3.2(2) and with it the NCN-versus-Neo-GNN and Neo-GNN-versus-ELPH comparisons. A second check targets the practice claim: re-running the LR-EXP protocol on any new graph family should reproduce the precision ordering SEAL first, then NCN and Neo-GNN, then ELPH, then BUDDY, with pure GNNs at zero, and any single pair that a provably less expressive model separates while SEAL cannot would break the hierarchy.

Watch

Extended reading notes

Core claim

The paper's central claim is that link-level expressiveness in message-passing GNNs is governed by the triplet $(k_\phi, k_\rho, m)$: the Weisfeiler-Lehman dimension of the endpoint message-passing function, the Weisfeiler-Lehman dimension of the neighborhood message-passing function, and the radius of the joint neighborhood around the link that gets aggregated. Theorem 3.2 establishes three monotonicity results. First, models with radius zero see a link only through its endpoints, so they assign identical representations to links whose endpoints are automorphic, regardless of how powerful the endpoint encoder is. Second, among models whose neighborhood encoder matches $1$-WL, expressiveness is monotone in $m + l$, the sum of neighborhood radius and number of message-passing layers. Third, at equal radius, expressiveness is monotone in the Weisfeiler-Lehman dimension of the neighborhood encoder. From these, Theorem 3.3 orders existing methods: pure GNNs sit at the bottom; NCN, Neo-GNN, and ELPH occupy the middle under stated conditions on radius and layers; and SEAL, whose link-aware positional encodings simulate a higher-order $1$-$|\mathcal{N}^m(u,v)|$-WL test, sits strictly above all of them. The paper further claims that this ordering shows up in practice: on the new LR-EXP benchmark, test precision rises exactly along the hierarchy (pure GNNs score 0%, BUDDY 45%, ELPH 62%, NCN and Neo-GNN 75%, SEAL 97%), and on real datasets the most expressive model becomes necessary precisely as the graph symmetry score $\widehat{r}_G$ increases.

Load-bearing premise

The hierarchy among the mid-tier models rests on a compensation step in the appendix proof of Theorem 3.2(2) — that a model with a smaller neighborhood radius can reach the same information by stacking more message-passing layers, so that expressiveness is decided by radius plus layers ($m+l$) — which is asserted rather than formally derived and is not obviously true, because the two models aggregate nodes from different distance shells around the link.

Editorial extensions

If this is right

  • Every pure GNN link model, however powerful its node encoder, assigns the same representation to links whose endpoints are automorphic, and any model that injectively combines an $m>0$ neighborhood aggregation with the endpoint representations is strictly more expressive.
  • Among $1$-WL-based link models, depth substitutes for radius: a small-radius deep model matches a large-radius shallow model whenever $m+l$ is at least as large, so expressiveness can be tuned with layers instead of wider neighborhoods.
  • At fixed radius, raising the Weisfeiler-Lehman power of the neighborhood encoder strictly increases link expressiveness, which is why SEAL's link-aware positional encodings, simulating $1$-$|\mathcal{N}^m(u,v)|$-WL, place it above every other studied model.
  • The practical value of expressiveness is dataset-dependent: on the twelve real benchmarks the simple models lead only in the low-symmetry regimes, while on the six most symmetric datasets the most expressive model SEAL ranks first on all of them.
  • LR-EXP provides the first synthetic benchmark dedicated to link-level expressiveness, and precision on it rises along the hierarchy: pure GNNs 0%, BUDDY 45%, ELPH 62%, NCN and Neo-GNN 75%, SEAL 97%.

Reading between the lines

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

  • If the depth-for-radius compensation is later made rigorous, the framework implies a concrete design rule the authors only gesture at: for a fixed compute budget, a deeper model with a smaller neighborhood radius would be preferable to a wider but shallower one, because the same $m+l$ is reached with a smaller aggregation set.
  • The symmetry score $\widehat{r}_G$ is cheap to compute before training, since it only needs converged $1$-WL color counts, so it could serve as a model-selection heuristic: compute it once and reserve SEAL-style architectures for datasets where it exceeds some threshold, spending simpler models elsewhere — a threshold the paper does not provide.
  • A testable prediction of this account is that the LR-EXP construction can be tuned to interpolate symmetry, and that increasing graph duplication and inter-block edge probability should widen the precision gap between SEAL and the simpler models monotonically.
  • Extending the same three parameters to transformer-based and spectral link encoders, which the paper lists as future work, would let the same hierarchy questions be asked of the architectures that currently dominate large-scale link prediction.
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

5 major / 5 minor

Summary. This paper introduces the kφ-kρ-m framework, which expresses message-passing link representation models as a combination of endpoint encodings φ, a node encoder ρ over the m-hop joint neighborhood, an aggregation function AGG, and a combination function COMB. The paper states Theorem 3.2 giving expressiveness comparison criteria and uses it in Theorem 3.3 to rank Pure GNNs, NCN, Neo-GNN, ELPH, and SEAL. It also introduces LR-EXP, a synthetic benchmark for link-level expressiveness, and a graph symmetry measure r̂G, reporting experiments on synthetic and real-world link prediction datasets.

Significance. If the theory were correct, this would be a useful unifying perspective: the paper provides the first systematic formal comparison of link-level message-passing models, ships a synthetic benchmark and code, and proposes a practical symmetry heuristic whose empirical trend is suggestive. The framework is a clean definitional contribution, and the LR-EXP protocol is a valuable resource for the community. However, the central hierarchy currently rests on a false theorem statement and a proof sketch with a load-bearing unproven step; the empirical trend, while interesting, is confounded by per-dataset tuning and OOM exclusions. These issues must be resolved before the hierarchy can be accepted.

major comments (5)
  1. [Section 3.2, Theorem 3.2(2)] Theorem 3.2(2) is false as stated when m2 = 0. For example, take M2 with m2 = 0, l2 = 1 and M1 with m1 = 1, l1 = 0. Then m1 + l1 = 1 ≤ 1 = m2 + l2, so the theorem asserts M1 ≤ M2. But item (1) of the same theorem states that any m = 0 model cannot distinguish links whose endpoints are automorphic, while an m = 1 model can, e.g., by counting common neighbors. Hence M1 ≤ M2 fails. The statement needs at least an m2 > 0 qualification, and as written the two clauses of Theorem 3.2 contradict each other.
  2. [Appendix A, proof of Theorem 3.2(2)] The proof contains the asserted step that a smaller neighborhood radius m2 can be compensated by using more layers to reach the same depth of information as F1. This step is not derived. The aggregation in Eq. (6) is over the union_{j=0}^{m2} N^j(u,v), not the larger union_{j=0}^{m1} N^j(u,v). Additional layers enrich the representations of nodes in the smaller set, but they do not by themselves place the missing outer-ring nodes into the aggregated multiset. A formal argument is required to show that whenever the ρ1-multiset over the larger neighborhood differs, the ρ2-multiset over the smaller neighborhood differs as well; the current proof does not provide it, and the conclusion does not follow from the displayed equations.
  3. [Appendix A, proof of Theorem 3.2(2) and (3)] The proof reduces distinguishability to a difference of the multiset of ρ-values over the neighborhood, ignoring the pairwise term ψ(i,u,v,X0) and the modified feature matrix h(u,v,X0) in Eq. (7). Since these components can make F distinguish two links even when the ρ-multisets coincide, the implication used in the proof is not valid for the general framework of Definition 3.1. The theorem either needs to restrict ψ and h or to carry them through the argument explicitly.
  4. [Section 3.2, Theorem 3.3 items 2–4] The hierarchy comparisons NCN vs Neo-GNN, Neo-GNN vs ELPH, and NCN vs ELPH are derived directly from Theorem 3.2(2) via Table 1. Since Theorem 3.2(2) is contradictory in the m2 = 0 case and unproven in the relevant m2 > 0 case, these hierarchy claims are not established. In addition, the proof of Theorem 3.3(2) does not explicitly verify the condition m_Neo-GNN + l_Neo-GNN ≤ m_NCN + l_NCN from Theorem 3.2(2); it only states the condition l_NCN ≥ m_Neo-GNN. The connection between the two conditions should be made precise.
  5. [Section 5, Table 3] The practical claim that more expressive models significantly outperform simpler ones as symmetry increases is based on a small set of datasets with per-dataset hyperparameter tuning, OOM exclusions, and no significance testing. For example, GAT is OOM on three datasets and SAGE is OOM on two, and the paper reports no statistical test for the monotonic relationship between r̂G and model ranking. The pattern is suggestive, but the wording in the abstract and Section 5.2 overstates the strength of the evidence.
minor comments (5)
  1. [Section 2, Definition 2.7 vs Theorem 3.2(1)] Definition 2.7 defines automorphic links using a single automorphism mapping the unordered pair {u,v}, while Theorem 3.2(1) uses two separate automorphisms σ1, σ2 mapping the endpoints independently. These are different equivalence relations, and the paper should align them or explicitly state which notion is used in each result.
  2. [Section 2, after Definition 2.4] The notation kρ is informal: it is described as the smallest k such that ρ is as powerful as k-WL, but Table 1 later uses expressions like 1-|N^m(u,v)|-WL, which is not a standard k-WL dimension. The paper should define kρ precisely enough to cover the values appearing in Table 1.
  3. [Section 5.1, Eq. (12)] The symmetry measure r̂G uses the number of distinct WL colors at convergence as a proxy for the number of orbits, but the paper does not justify why |WL_G| approximates |O_G|. This approximation is attributed to reference [28], a self-citation, without a derivation or discussion of its accuracy.
  4. [Tables 3 and 8] In Table 3, ELPH is represented by BUDDY, its more scalable version, but Appendix D reports results for ELPH on the high-symmetry datasets. The relationship between the two is not explained in the main text, and the reader cannot tell whether the reported scores are directly comparable.
  5. [Throughout] There are several minor typographical and formatting issues: 'more expressive then' should be 'more expressive than' in Theorem 3.3; the edge count for edit-tsw in Table 5 reads '2.756' and should presumably be '2,756'; and Eq. (3) uses Al_G with summation index l but the upper limit is written L rather than consistent with the index.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the kφ-kρ-m framework is a definitional organizing device, the hierarchy claims rest on Table 1 instantiations and WL theory, and the empirical claims are tested against external benchmarks; the only self-citation is minor and non-load-bearing.

full rationale

The framework in Definition 3.1 is a definitional template; Theorem 3.2(1) and (3) follow from standard WL/automorphism facts, and Theorem 3.3's hierarchy is derived from the explicit m, l, and kρ values in Table 1, which are taken from the original model definitions rather than fitted to the conclusions. The real-world experiment is self-contained against external benchmarks (OGB, Cora, Citeseer, etc.), and the symmetry metric in Section 5.1 is an approximation attributed to both the authors' prior work [28] and an external source [36], so the self-citation is not load-bearing: the same orbit-count estimate is independently available and could be checked by exact orbit computation. The theoretical argument does contain a significant correctness gap, flagged explicitly: in Appendix A, proof of Theorem 3.2(2), the line 'Since F2 uses a number of layers lM2 ≥ lM1 + mM1 − mM2, it can compensate for the smaller neighborhood radius m2 by using more layers to reach the same depth of information as F1' is asserted without derivation, and the statement as written conflicts with Theorem 3.2(1) when m2 = 0. This is a soundness gap in the hierarchy proof, not a reduction of the conclusion to the inputs, so it does not constitute circularity under the criteria. No 'prediction' is a fitted parameter renamed; LR-EXP precision values and MRR results are measured outputs. Score 2 reflects the presence of a minor self-citation only.

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

The framework itself introduces no free parameters. The central claim rests on the WL hierarchy, on the exactness of the Table 1 model formalizations, and on the WL-color approximation of the symmetry metric. No invented entities are postulated.

assumptions (6)
  • standard math The 1-WL test and k-WL hierarchy are sound characterizations of GNN expressiveness; k-WL preserves automorphisms for all k.
    Used throughout: Definition 2.4 and Theorem 3.2 proof in Appendix A relies on WL color refinement properties.
  • domain assumption Each model can be exactly expressed in the kφ-kρ-m framework with the parameter assignments in Table 1.
    Table 1 maps NCN, Neo-GNN, ELPH, SEAL, and pure GNNs to (kφ, kρ, m); the hierarchy proofs depend on these assignments being exact.
  • domain assumption kρ, defined as the smallest k such that ρ is as powerful as k-WL, is well-defined for the models considered.
    Section 2 introduces kρ without proof that such a minimal k exists for arbitrary message-passing architectures.
  • domain assumption SEAL's Double-Radius Node Labeling achieves expressiveness equivalent to 1-|N^m(u,v)|-WL, which is strictly stronger than 1-WL.
    Used in Theorem 3.3(5), citing Zhou et al. [55].
  • domain assumption The number of distinct WL colors at termination approximates the number of node orbits well enough for the symmetry metric r̂G.
    Equation (12) defines r̂G = 1 - (|WL|-1)/(|V|-1); the paper uses this as a proxy for orbit-based rG without analyzing the approximation bias.
  • standard math Message-passing GNNs are permutation equivariant, so automorphic nodes receive identical representations.
    Fundamental property used implicitly in Theorem 3.2(1) and in the discussion of automorphic links.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bridging Theory and Practice in Link Representation with Graph Neural Networks." pith.science (2026). https://pith.science/paper/FYNPQOGP

@misc{pith2026250624018,
  author       = {Pith},
  title        = {Pith review of: Bridging Theory and Practice in Link Representation with Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FYNPQOGP}},
  note         = {Machine review of arXiv:2506.24018}
}
abstract

Graph Neural Networks (GNNs) are widely used to compute representations of node pairs for downstream tasks such as link prediction. Yet, theoretical understanding of their expressive power has focused almost entirely on graph-level representations. In this work, we shift the focus to links and provide the first comprehensive study of GNN expressiveness in link representation. We introduce a unifying framework, the $k_\phi$-$k_\rho$-$m$ framework, that subsumes existing message-passing link models and enables formal expressiveness comparisons. Using this framework, we derive a hierarchy of state-of-the-art methods and offer theoretical tools to analyze future architectures. To complement our analysis, we propose a synthetic evaluation protocol comprising the first benchmark specifically designed to assess link-level expressiveness. Finally, we ask: does expressiveness matter in practice? We use a graph symmetry metric that quantifies the difficulty of distinguishing links and show that while expressive models may underperform on standard benchmarks, they significantly outperform simpler ones as symmetry increases, highlighting the need for dataset-aware model selection.

Figures

Figures reproduced from arXiv: 2506.24018 by the authors.

Figure 1
Figure 1. kϕ-kρ-m framework: nodes representations in the m-order neighborhood of target link are calculated using a MP function ρ with possibly modified node features; these representations are aggregated and combined with representations of endpoints of target link obtained through MP function ϕ. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Examples of LR-EXP graphs. Node colors show WL col￾ors; dashed lines mark test links that are non-automorphic but indis￾tinguishable for standard GNNs. Each graph is generated in two steps: (1) sample an Erdos–Rényi ˝ graph with n ∈ {5, . . . , 17} nodes and edge probability p ∼ U(0, 1); (2) duplicate the graph and add inter-block edges with probability p ′ ∼ U(0, 1). This construction introduces rich symmetries and… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Plain Transformers are Surprisingly Powerful Link Predictors

    cs.LG 2026-02 conditional novelty 6.0 of 10

    A plain-style Transformer over sampled local subgraphs, with a multiplicative adjacency residual, reaches state-of-the-art link prediction on several benchmarks without node IDs or hand-crafted heuristics.

Reference graph

Works this paper leans on

64 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    The sur- prising power of graph neural networks with random node initialization

    Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020

    arXiv 2010

  2. [2]

    Breaking the limits of message passing graph neural networks

    Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599–608. PMLR, 2021

    work page 2021

  3. [3]

    How symmetric are real-world graphs? a large-scale study

    Fabian Ball and Andreas Geyer-Schulz. How symmetric are real-world graphs? a large-scale study. Symmetry, 10(1):29, 2018

    work page 2018

  4. [4]

    Position: Graph learning will lose relevance due to poor benchmarks

    Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M Bronstein, Mathias Niepert, Bryan Perozzi, et al. Position: Graph learning will lose relevance due to poor benchmarks. arXiv preprint arXiv:2502.14546, 2025

    arXiv 2025

  5. [5]

    Bronstein, and Haggai Maron

    Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=dFbKQaRk15w

    work page 2022

  6. [6]

    The expressive power of pooling in graph neural networks

    Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. Advances in neural information processing systems, 36:71603–71618, 2023

    work page 2023

  7. [7]

    Improving graph neural network expressivity via subgraph isomorphism counting

    Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022

    2022

  8. [8]

    siamese

    Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6, 1993

    work page 1993

Show all 64 references
  1. [9]

    A note on over-smoothing for graph neural networks

    Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318, 2020

    2006 arXiv

  2. [10]

    An optimal lower bound on the number of variables for graph identification

    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

  3. [11]

    Line graph neural networks for link prediction

    Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5103–5113, 2021

    2021

  4. [12]

    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. In The Eleventh International Conference on Learni...

    2023

  5. [13]

    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. In Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, pages 392–400, 2025

    2025

  6. [14]

    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

    2020

  7. [15]

    The link regression problem in graph streams

    Bowen Dong, Charu C Aggarwal, and S Yu Philip. The link regression problem in graph streams. In 2019 IEEE International Conference on Big Data (Big Data), pages 1088–1095. IEEE, 2019

    2019

  8. [16]

    A fair comparison of graph neural networks for graph classification

    Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.09893, 2019. 11

    1912 arXiv

  9. [17]

    Meta-path learning for multi-relational graph neural networks

    Francesco Ferrini, Antonio Longa, Andrea Passerini, and Manfred Jaeger. Meta-path learning for multi-relational graph neural networks. In Learning on Graphs Conference, pages 2–1. PMLR, 2024

    2024

  10. [18]

    R. A. Fisher. Contributions to Mathematical Statistics. Wiley, 1950

    1950

  11. [19]

    The iteration number of the weisfeiler-leman algorithm

    Martin Grohe, Moritz Lichter, and Daniel Neuen. The iteration number of the weisfeiler-leman algorithm. ACM Transactions on Computational Logic, 26(1):1–31, 2025

    2025

  12. [20]

    Inductive representation learning on large graphs

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

    2017

  13. [21]

    The generalization of student’s ratio

    Harold Hotelling. The generalization of student’s ratio. The Annals of Mathematical Statistics, 2(3):360–378, 1931. doi: 10.1214/aoms/1177732979. URL https://projecteuclid.org/ euclid.aoms/1177732979

    1931

  14. [22]

    The k-dimensional weisfeiler-leman algorithm

    Neil Immerman and Rik Sengupta. The k-dimensional weisfeiler-leman algorithm. arXiv preprint arXiv:1907.09582, 2019

    1907 arXiv

  15. [23]

    Prediction of protein–protein interaction using graph neural networks

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

    2022

  16. [24]

    Is expressivity essential for the predictive perfor- mance of graph neural networks? In NeurIPS 2024 Workshop on Scientific Methods for Under- standing Deep Learning, 2024

    Fabian Jogl, Pascal Welke, and Thomas Gärtner. Is expressivity essential for the predictive perfor- mance of graph neural networks? In NeurIPS 2024 Workshop on Scientific Methods for Under- standing Deep Learning, 2024. URL https://openreview.net/forum?id=5v7hpSy3Ir

    2024

  17. [25]

    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

  18. [26]

    Variational graph auto-encoders

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

    2016 arXiv

  19. [27]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017. URL https: //openreview.net/forum?id=SJU4ayYgl

    2017

  20. [28]

    A simple and expressive graph neural network based method for structural link representation

    Veronica Lachi, Francesco Ferrini, Antonio Longa, Bruno Lepri, and Andrea Passerini. A simple and expressive graph neural network based method for structural link representation. In Geometry-grounded Representation Learning and Generative Modeling Workshop (GRaM) at ICML 2024,...

    2024

  21. [29]

    Evaluating graph neural networks for link prediction: Current pitfalls and new bench- marking

    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 bench- marking. In Thirty-seventh Conference on Neural Information Processing Systems Datasets an...

    2023

  22. [30]

    Line graph neural networks for link weight prediction

    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

  23. [31]

    Computational complexity of the weisfeiler-leman dimension

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

    2025

  24. [32]

    Link prediction in complex networks: A survey

    Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6):1150–1170, 2011

    2011

  25. [33]

    Simplifying approach to node classifica- tion in graph neural networks

    Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classifica- tion in graph neural networks. Journal of Computational Science, 62:101695, 2022. 12

    2022

  26. [34]

    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. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–...

    2019

  27. [35]

    Position: Future directions in the theory of graph machine learning

    Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In Forty-first International Conference on Mac...

    2024

  28. [36]

    Orbit-equivariant graph neural networks

    Matthew Morris, Bernardo Cuenca Grau, and Ian Horrocks. Orbit-equivariant graph neural networks. In The Twelfth International Conference on Learning Representations, 2023

    2023

  29. [37]

    Relational pooling for graph representations

    Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663–4673. PMLR, 2019

    2019

  30. [38]

    A review of relational machine learning for knowledge graphs

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

    2015

  31. [39]

    Knowledge graph embedding for link prediction: A comparative analysis

    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

  32. [40]

    On the equivalence between positional node embeddings and structural graph representations

    Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=SJxzFySKwH

    2020

  33. [41]

    Graph attention networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations,

  34. [42]

    Neural common neighbor with completion for link prediction

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

    2024

  35. [43]

    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. In Proceedings of the 2021 international conference on management ...

    2021

  36. [44]

    An empirical study of realized gnn expressiveness

    Yanbo Wang and Muhan Zhang. An empirical study of realized gnn expressiveness. arXiv preprint arXiv:2304.07702, 2023

    2023 arXiv

  37. [45]

    An empirical study of realized GNN expressiveness

    Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview. net/forum?id=WIaZFk02fI

    2024

  38. [46]

    The reduction of a graph to canonical form and the algebra which appears therein

    Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12–16, 1968

    1968

  39. [47]

    Graph neural networks in node classification: survey and evaluation

    Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33(1):4, 2022

    2022

  40. [48]

    Active and semi-supervised graph neural networks for graph classification

    Yu Xie, Shengze Lv, Yuhua Qian, Chao Wen, and Jiye Liang. Active and semi-supervised graph neural networks for graph classification. IEEE Transactions on Big Data, 8(4):920–932, 2022

    2022

  41. [49]

    How powerful are graph neural networks? In International Conference on Learning Representations , 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations , 2019. URL https: //openreview.net/forum?id=ryGs6iA5Km

    2019

  42. [50]

    How powerful are graph neural networks?, 2019

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

    2019

  43. [51]

    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 Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974–983, 2018

    2018

  44. [52]

    Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction

    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

  45. [53]

    Link prediction based on graph neural networks

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

    2018

  46. [54]

    Labeling trick: A theory of using graph neural networks for multi-node representation learning

    Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061–9073, 2021

    2021

  47. [55]

    From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks

    Cai Zhou, Xiyuan Wang, and Muhan Zhang. From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks. In International Conference on Machine Learning, pages 42742–42768. PMLR, 2023

    2023

  48. [56]

    Progresses and challenges in link prediction

    Tao Zhou. Progresses and challenges in link prediction. Iscience, 24(11), 2021. 14 A Proofs Proof of Theorem 3.2 . We prove theorem by addressing each of its three components individually

    2021

  49. [58]

    If mM = 0, then, regardless of kM ϕ , M is not able to distinguish between links whose endpoints are automorphic, i.e., ∀F ∈ M, ∀(u, v), (u′, v′) s.t

    Let M ∈ M. If mM = 0, then, regardless of kM ϕ , M is not able to distinguish between links whose endpoints are automorphic, i.e., ∀F ∈ M, ∀(u, v), (u′, v′) s.t. ∃σ1, σ2 ∈ ΣG n with σ1(u) = u′ ∧ σ2(v) = v′ (13) F ((u′, v′), X0) = F ((u, v), X0) (14) therefore, automorphic link...

  50. [59]

    If mM1 + lM1 ≤ mM2 + lM2, then M1 ≤ M2

    Let M1, M2 ∈ Mwith kM1 ρ = kM2 ρ = 1-WL and let lM1 , lM2 be the number of layers used respectively by M1, M2. If mM1 + lM1 ≤ mM2 + lM2, then M1 ≤ M2. Proof Let F1 ∈ M1, F2 ∈ M2. Assume lM2 ≥ lM1 + mM1 − mM2 and lM1 ≤ lM2 and mM1 > mM2. Let (u, v), (u′, v′) ∈ VG × VG such that...

  51. [60]

    If kM1 ρ ≤ kM2 ρ , then M1 ≤ M2

    Let M1, M2 ∈ Mwith mM1 = mM2. If kM1 ρ ≤ kM2 ρ , then M1 ≤ M2. Proof Let mM1 = mM2 = m and kM1 ρ ≤ kM2 ρ . Let F1 ∈ M1 and F2 ∈ M2 and (u, v), (u′, v′) ∈ VG × VG such that F1((u, v), G,X0) ̸= F1((u′, v′), G,X0). Assume that cℓ u = cℓ u′ and cℓ v = cℓ v′, i.e., u and u′, as wel...

  52. [61]

    According to Table 1, Neo-GNN uses a fixed number of message-passing layers lNeo-GNN = 1, while NCN allows lNCN to be freely chosen. Since both models operate with the same type of base function ρ (e.g., 1-WL), Theorem 3.2 implies that if lNCN ≥ mNeo-GNN, then NCN can simulate...

  53. [62]

    By design, ELPH does not use any message-passing layers (lELPH = 0, see Table 1), and instead aggregates counts over the m-hop neighborhood. If Neo-GNN uses a neighborhood of size at least mELPH − 1, then Theorem 3.2 ensures it can access all the information available to ELPH ...

  54. [63]

    NCN uses a fixed radius mNCN = 1 (Table 1), but allows a configurable number of layers

    ELPH relies only on aggregated neighborhood counts and uses lELPH = 0 layers. NCN uses a fixed radius mNCN = 1 (Table 1), but allows a configurable number of layers. If lNCN ≥ mELPH − 1, then by Theorem 3.2 NCN can effectively capture structural signals that ELPH computes with...

  55. [64]

    SEAL is more expressive due to both its flexible architecture and enhanced message-passing capabilities. Specifically, SEAL builds a subgraph around the link and augments the adjacency matrix with positional encodings that are link-aware, effectively allowing a learned structu...

  56. [2018]

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

Pith tools

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