Pith. sign in

REVIEW 3 major objections 6 minor 112 references

Attribute-Enhanced Similarity Ranking for Sparse Link Prediction

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Under unbiased evaluation, GNN link predictors are beaten by a simple heuristic that adds node attributes.

desk verdict A real negative result about GNN link prediction, a sensible method, but shaky theory and a single-run large-graph result. read the letter →

arxiv 2412.00261 v1 pith:76PVJEQG submitted 2024-11-29 cs.LG cs.AIcs.SI

João Mattos , Zexi Huang , Mert Kosan , Ambuj Singh , Arlei Silva This is my paper · ORCID
classification cs.LGcs.AIcs.SI
keywords linkpredictiongraphneuralnetworksunbiasedevaluationAutocovariancenegativesamplingpartitioningclassimbalancenodeattributes
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

Link prediction is usually tested by ranking each true edge against an equal sample of random non-edges, a setting this paper calls biased testing. The paper shows that on sparse attributed graphs this protocol flatters graph neural networks: when every disconnected pair is included in evaluation (unbiased testing), basic topological heuristics such as Autocovariance often beat state-of-the-art GNN methods. To address the sparse regime the authors propose Gelato, which uses a small MLP to fold node attributes into edge weights, scores pairs with Autocovariance, and trains with an N-pair ranking loss over hard negatives selected inside graph partitions. On Cora, CiteSeer, PubMed, and ogbl-collab, Gelato reports higher hits-at-1000 than the GNN baselines it is compared with, and it remains competitive on a dense dataset where attributes are absent. The paper's point is that sparse link prediction is a needle-in-a-haystack ranking problem, not a balanced binary classification problem, and that the field's evaluation should be changed accordingly.

What carries the argument

The load-bearing object is Gelato's pipeline rather than any single layer: an MLP computing edge weights from node attributes, an enhanced adjacency matrix, Autocovariance as the differentiable scoring heuristic, an N-pair ranking loss, and partition-based negative sampling. Autocovariance measures the difference between co-visiting probabilities in a truncated random walk and in a stationary walk, and at $t=1$ it specializes to Modularity, which lets the score separate hard same-community negatives from easy cross-community ones. The N-pair loss contrasts each positive edge against a set of negative pairs, and partition-based sampling restricts negatives to pairs inside the same partition, which the authors justify with stochastic-block-model lemmas showing that intra-block pairs have higher expected Autocovariance.

What would settle it

Take a sparse attributed graph with no community structure, such as a random geometric graph or a planted attribute correlation without modularity, and run Gelato plus the GNN baselines under unbiased testing; if Gelato no longer outperforms either plain Autocovariance or the best GNN baseline, the claim that within-partition sampling suffices would be refuted.

Watch

Extended reading notes

Core claim

The paper's central claim is that reported GNN link-prediction performance in the balanced setting does not transfer to the realistic imbalanced setting. Concretely, with unbiased testing — ranking a held-out positive edge against all disconnected pairs — recent GNN-based methods are often outperformed by Autocovariance, a random-walk heuristic that uses no node attributes and no training. Gelato is the authors' proposed remedy: it modifies the topology by adding attribute-similarity edges and learned MLP edge weights, then applies Autocovariance to the resulting graph, optimizes an N-pair ranking loss, and draws negative pairs from within graph partitions so that training concentrates on hard, same-community negatives. In experiments, Gelato reports the best hits@1000 on Cora, CiteSeer, PubMed, and ogbl-collab, outperforming the best GNN baseline by 138%, 125%, 156%, and 11% respectively, and gains 48%, 39%, 10%, and 139% over its own base Autocovariance heuristic.

Load-bearing premise

Gelato's partitioned negative sampling presupposes that the graph has community structure, so that within-partition node pairs are the hard negatives that matter; if a real graph lacks such structure, training on intra-partition negatives may not transfer to all-pairs evaluation.

Editorial extensions

If this is right

  • Results reported on balanced test sets overstate GNN link prediction, so comparisons should include unsupervised topological baselines under unbiased evaluation.
  • A ranking loss with hard negatives is a better training objective than cross-entropy for sparse link prediction.
  • Node attributes can be injected into the graph structure and scored by a topological heuristic, an alternative to learning node embeddings.
  • Partition-based negative sampling cuts training cost from $O(|V|^2)$ to $O(\sum_i |V_i|^2)$ without losing much accuracy on graphs with community structure.
  • On dense graphs with no attributes, such as ogbl-ddi, Gelato matches rather than beats its base heuristic, indicating that the gains are tied to sparse attributed graphs.

Reading between the lines

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

  • If unbiased evaluation became the default, many published GNN link-prediction rankings would likely change; the paper's stochastic-block-model example shows that a model knowing block structure can look strong under biased testing while being useless in practice.
  • The same design — attribute-enhanced graph plus random-walk scoring — could be applied to knowledge-graph completion or recommendation, where hard negatives also dominate; the partitioning idea would need an analogue of communities, such as item categories.
  • On graphs without community structure, the theoretical justification collapses; a testable prediction is that Gelato's margin over Autocovariance shrinks on non-modular sparse graphs with strong attribute signal.
  • The paper leaves open whether a more powerful differentiable scorer than Autocovariance would push the gains further while keeping unbiased training tractable.
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 / 6 minor

Summary. This paper argues that standard GNN link-prediction evaluation, which balances positive and negative test pairs (termed "biased testing"), overstates performance relative to "unbiased testing," where positive edges are ranked against all disconnected pairs. It proposes Gelato, a similarity-based link-prediction method that learns edge weights from node attributes via an MLP, feeds the attribute-enhanced adjacency matrix into the Autocovariance topological heuristic, trains with an N-pair ranking loss, and uses METIS-partition-based negative sampling for scalability. Experiments on Cora, CiteSeer, PubMed, ogbl-ddi, and ogbl-collab report hits@1000, AP, MRR, and prec@k, showing that Gelato outperforms GNN-based baselines on most datasets while also providing ablations, sensitivity analyses, and training-time comparisons.

Significance. If the results hold, the paper makes a valuable contribution by challenging the dominant evaluation protocol for GNN link prediction and by showing that a simple heuristic-based method can be both accurate and scalable under unbiased testing. The empirical finding that Autocovariance and Gelato outperform strong GNN baselines on several datasets is credible and consistently demonstrated on Cora, CiteSeer, and PubMed. The paper's strengths include a clearly defined unbiased evaluation setting, code release, per-component ablations, hyperparameter sensitivity analyses, and wall-clock training-time comparisons. The main weaknesses are theoretical: Lemmas 3 and 4, which justify the partitioned negative sampling used for ogbl-collab, are not rigorously proven as written, and only one dataset validates the equivalence of partitioned and unbiased training. These issues are repairable but need to be addressed before the paper's central claims are fully supported.

major comments (3)
  1. [Appendix D, Lemma 3] The proof of Lemma 3 contains a demonstrable error. In Eq. (13)-(15), the expected Autocovariance for an inter-cluster pair is written as (1/2m)(1-p - d_i d_j/2m) and then set equal to (1/2m)(q - d_i d_j/2m). This equates 1-p with q, but q is the inter-block edge probability and is not 1-p in general. The lemma's statement is true if Eq. (13) is replaced with the correct expression (1/2m)(q - d_i d_j/2m), so the conclusion is repairable, but the proof as printed is invalid. Because Lemma 3 is the stated justification for discarding inter-partition negative pairs in training, the corrected proof should appear in the revision.
  2. [Appendix E, Lemma 4 and Section 3.4] The proof of Lemma 4 does not establish the claimed monotonicity. The argument defines p as an estimate |E_ik|/|V_ik|^2 and derives the inequality |V_i^k|^2 - |V_i^{k+1}|^2 >= |E_i^k| - |E_i^{k+1}|; this inequality is not sufficient to conclude that the ratio |E_i^{k+1}|/|V_i^{k+1}|^2 is larger than |E_i^k|/|V_i^k|^2, and the notion of "positive pairs we can lose" is not rigorously quantified. Moreover, Lemmas 3 and 4 are stated for Autocovariance on the original graph, whereas Gelato computes Autocovariance on the attribute-enhanced graph eA (Eq. 4-5), so the theoretical justification does not directly transfer. The only empirical check of partitioned-versus-unbiased training is on CiteSeer (Appendix I, Fig. 7). Since ogbl-collab relies on partitioned training, this is a load-bearing gap; the revision should either prove the lemmas for the enhanced graph or provide partitioned-versus-unbiased comparisons on at least one additional dataset, ideally PubMed.
  3. [Table 2 and Section 4.3] The ogbl-collab result, which provides the largest-graph evidence for the headline claim, is reported as a single run (30.92*) without standard deviation, and Section 4.1 states that hyperparameters were not tuned on ogbl-collab. Combined with the unvalidated partitioned-training assumption, the claimed 11% improvement over the best GNN baseline (BUDDY 27.66 +/- 0.24) is not yet established. Please provide multiple seeds with error bars and, if possible, a tuned baseline set for ogbl-collab.
minor comments (6)
  1. [Appendix B] The classifier 2 and 3 tables swap the roles of FP and FN for classifier 2 and set FP=(n-1)p for classifier 3; the final accuracy difference is correct, but the intermediate labels should be fixed to avoid confusion.
  2. [Appendix N] The biased-training results are referenced as 'Table ??' and 'Table ??' but no such tables appear in the manuscript; either include the tables or remove the references.
  3. [Section 4.1 and Eq. (9)] The phrase 'unbiased training without downsampling' is not fully specified: it is unclear how many negative pairs N(u,v) are used per positive pair in the N-pair loss and how the O(V^2) negative set is materialized for Cora, CiteSeer, and PubMed; please clarify the implementation.
  4. [Abstract and Section 4.3] The statement that Gelato 'outperforms existing GNN-based alternatives' is too strong, since Table 2 shows NCNC is better on ogbl-ddi; please qualify by 'most datasets'.
  5. [Appendix I] The last sentence says 'we experimented with different values of p' but the parameter being varied is k (the number of partitions); please correct the notation.
  6. [Tables 7 and 8] The SEAL rows contain stray asterisks and misaligned column entries; please clean the table formatting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the ranking loss, unbiased evaluation, and Gelato's gains are derived in-paper; the only self-citation (Autocovariance) is re-computed and not load-bearing, while the partitioned-sampling proofs have rigor gaps that are correctness issues rather than circularity.

full rationale

The derivation chain is self-contained. The N-pair loss (Eq. 9) is a softmax ranking objective and the evaluation metric (hits@1000) is a ranking metric; optimizing a surrogate for the metric on held-out edges is standard practice, and the test edges are masked during training, so no predicted quantity is an input by construction. Autocovariance is defined in Eqs. 5-8 and its scores are recomputed in Table 2 for every dataset; the self-citation to [30] is background for the heuristic, not the evidence for the performance claims. The partitioned negative-sampling scheme is supported by Lemmas 3-4, whose proofs in Appendices D-E contain a mis-specified inter-block probability (1-p instead of q) and a non-rigorous monotonicity argument; these are correctness/rigor gaps, not circular reductions, because the lemmas do not assume that partitioned training matches unbiased testing. The ogbl-collab result is a single partitioned-training run without error bars and is not verified under all-pairs unbiased testing, which weakens the generalization of the central claim but does not make it circular. No fitted parameter is renamed as a prediction, and no load-bearing claim relies solely on an author self-citation.

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

The paper's theoretical contributions rest on a simplified SBM model, and its method relies on several domain assumptions about community structure, homophily, and the adequacy of Autocovariance. These assumptions are plausible but not proven for real graphs.

free parameters (5)
  • eta = tuned from {0.0, 0.25, 0.5, 0.75, 1.0}
    Controls how many attribute-similar pairs are added to the graph in Eq. 1; tuned separately per dataset.
  • alpha = tuned from {0.0, 0.25, 0.5, 0.75}
    Weight balancing original topology and attribute-enhanced weights in Eq. 4.
  • beta = tuned from {0.25, 0.5, 0.75, 1.0}
    Weight balancing trained MLP weights and raw attribute similarity in Eq. 4.
  • t = 3 (fixed)
    Scaling parameter for the Autocovariance random walk; fixed rather than tuned in the reported experiments.
  • number of METIS partitions k = 10 (Cora, CiteSeer), 100 (PubMed), 20 (ogbl-ddi), 1300 (ogbl-collab)
    Chosen per dataset for partitioned negative sampling; affects the hardness of negatives and training cost.
assumptions (4)
  • domain assumption Graphs are generated by a Stochastic Block Model with intra-block density p and inter-block density q, p > q.
    Used in Theorem 2.1 and Lemmas 1-4 to analyze biased versus unbiased testing and to justify within-partition negative sampling.
  • domain assumption Autocovariance is an effective topological heuristic for sparse link prediction.
    The method is built on Autocovariance; the paper provides empirical evidence but no proof that Autocovariance is optimal or sufficient for real graphs.
  • domain assumption Node attributes are correlated with link existence (homophily).
    The graph learning step assumes that attribute similarity helps predict links; this is stated in the related work section but not established for the datasets.
  • domain assumption METIS partitions correspond to sets of hard negative pairs.
    The negative sampling scheme selects only within-partition negatives, assuming these are more confusable with positives than cross-partition pairs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Attribute-Enhanced Similarity Ranking for Sparse Link Prediction." pith.science (2026). https://pith.science/paper/76PVJEQG

@misc{pith2026241200261,
  author       = {Pith},
  title        = {Pith review of: Attribute-Enhanced Similarity Ranking for Sparse Link Prediction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/76PVJEQG}},
  note         = {Machine review of arXiv:2412.00261}
}
read the original abstract

Link prediction is a fundamental problem in graph data. In its most realistic setting, the problem consists of predicting missing or future links between random pairs of nodes from the set of disconnected pairs. Graph Neural Networks (GNNs) have become the predominant framework for link prediction. GNN-based methods treat link prediction as a binary classification problem and handle the extreme class imbalance -- real graphs are very sparse -- by sampling (uniformly at random) a balanced number of disconnected pairs not only for training but also for evaluation. However, we show that the reported performance of GNNs for link prediction in the balanced setting does not translate to the more realistic imbalanced setting and that simpler topology-based approaches are often better at handling sparsity. These findings motivate Gelato, a similarity-based link-prediction method that applies (1) graph learning based on node attributes to enhance a topological heuristic, (2) a ranking loss for addressing class imbalance, and (3) a negative sampling scheme that efficiently selects hard training pairs via graph partitioning. Experiments show that Gelato outperforms existing GNN-based alternatives.

Figures

Figures reproduced from arXiv: 2412.00261 by the authors.

Figure 1
Figure 1. Gelato applies graph learning to incorporate attribute information into the topology. The learned graph is given [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Scaling up Gelato using batching and sparse tensors. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. We analyze classification-based and similarity-based link prediction approaches through a comparison between the [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Link prediction comparison in terms of ℎ𝑖𝑡𝑠@𝑘 varying 𝑘 using Cora, CiteSeer, OGBL-DDI and OGBL-Collab. All datasets were split using unbiased sampling, except OGBL-Collab, which was split using partitioned sampling. Gelato outperforms the baselines across different va…
Figure 5
Figure 5. Figure 5: Receiver operating characteristic and precision-recall curves for the bad link prediction model that ranks 1M false [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: MPNNs for link prediction cannot distinguish pairs [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Comparison between Gelato trained using unbi￾ased sampling against partitioned sampling on CiteSeer for different values of 𝐾. We verify that even in extreme par￾titioning scenarios (𝑘 = 50, ≈ 66 nodes per partition), there is only a small performance gap between both …
Figure 8
Figure 8. Figure 8: Link prediction comparison in terms of 𝑝𝑟𝑒𝑐@𝑘 using Cora, CiteSeer, OGBL-DDI and OGBL-Collab. All datasets were split using unbiased sampling, except OGBL-Collab, which was split using partitioned sampling. Gelato obtains the best performance on Cora and OGBL-Collab by…
Figure 9
Figure 9. Figure 9: The non-normalized version of the Figure 3. Negative pairs are represented in [PITH_FULL_IMAGE:figures/full_fig_p017_9.png]
Figure 10
Figure 10. Figure 10: Performance comparison (𝑝𝑟𝑒𝑐@𝑘) between Gelato (in blue) against GelatoGIN (in green), which replaces the MLP module by GIN. The dashed line represents the performance on training, while the full line represents the performance on test. We can see that despite eventua…
Figure 11
Figure 11. Figure 11: Sensitivity analysis of 𝛼 and 𝛽 considering 𝐴𝑃 metric [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 12
Figure 12. Figure 12: Results of 𝑝𝑟𝑒𝑐@𝑘 (top) and ℎ𝑖𝑡𝑠@𝑘 (bottom) of Gelato (in blue) against Gelato with 𝛼 and 𝛽 as learning parameters (in green). In both datasets and metrics considered, the learned 𝛼 and 𝛽 obtained worse values than the values found by the grid search hyperparameter tu…
Figure 13
Figure 13. Figure 13: Performance of Gelato with different values of [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

112 extracted references · 55 canonical work pages

  1. [1]

    Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks 25, 3 (2003), 211–230

    2003

  2. [2]

    Ashwin Bahulkar, Boleslaw K Szymanski, N Orkun Baycik, and Thomas C Sharkey. 2018. Community detection with edge augmentation in criminal networks. In ASONAM

    2018

  3. [3]

    Albert-László Barabási. 2016. Network Science. Cambridge University Press

    2016

  4. [4]

    Albert-Laszlo Barabási, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Vicsek. 2002. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications 311, 3-4 (2002), 590–614

    2002

  5. [5]

    Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. 2013. Translating Embeddings for Modeling Multi-relational Data. In NeurIPS

    2013

  6. [6]

    Sebastian Bruch. 2021. An alternative cross entropy loss for learning-to-rank. In WebConf

    2021

  7. [7]

    Jonathon Byrd and Zachary Lipton. 2019. What is the effect of importance weighting in deep learning?. In International conference on machine learning . PMLR, 872–881

    2019

  8. [8]

    Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. 2021. Line graph neural networks for link prediction. IEEE TPAMI (2021)

    2021

Show all 112 references
  1. [9]

    Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. 2019. Deep metric learning to rank. In CVPR

    2019

  2. [10]

    Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. 2023. Graph Neural Networks for Link Prediction with Subgraph Sketching. In ICLR

    2023

  3. [11]

    Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. 2019. Hyperbolic graph convolutional neural networks. In NeurIPS

    2019

  4. [12]

    Wei Chen, Tie-Yan Liu, Yanyan Lan, Zhi-Ming Ma, and Hang Li. 2009. Ranking measures and loss functions in learning to rank. Advances in Neural Information Processing Systems 22 (2009)

    2009

  5. [13]

    Xu Chen, Xiuyuan Cheng, and Stéphane Mallat. 2014. Unsupervised deep haar scattering on graphs. In NeurIPS

    2014

  6. [14]

    Yuzhou Chen, Yulia R Gel, and H Vincent Poor. 2022. BScNets: Block Simplicial Complex Neural Networks. In AAAI

    2022

  7. [15]

    Yu Chen, Lingfei Wu, and Mohammed Zaki. 2020. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In NeurIPS

    2020

  8. [16]

    Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. 2020. Can graph neural networks count substructures? Advances in neural information processing systems 33 (2020), 10383–10395

    2020

  9. [17]

    Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh

  10. [18]

    Arlei Lopes da Silva, Furkan Kocayusufoglu, Saber Jafarpour, Francesco Bullo, Ananthram Swami, and Ambuj Singh. 2020. Combining Physics and Machine Learning for Network Flow Estimation. In ICLR

    2020

  11. [19]

    Jesse Davis and Mark Goadrich. 2006. The relationship between Precision-Recall and ROC curves. In ICML

    2006

  12. [20]

    J-C Delvenne, Sophia N Yaliraki, and Mauricio Barahona. 2010. Stability of graph communities across time scales. PNAS 107, 29 (2010), 12755–12760

    2010

  13. [21]

    Andrea Giuseppe Di Francesco, Francesco Caso, Maria Sofia Bucarelli, and Fabrizio Silvestri. 2024. Link Prediction under Heterophily: A Physics-Inspired Graph Neural Network Approach. arXiv preprint arXiv:2402.14802 (2024)

    2024 arXiv

  14. [22]

    Santo Fortunato. 2010. Community detection in graphs. Physics reports 486, 3-5 (2010), 75–174

    2010

  15. [23]

    Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. 2019. Learning discrete structures for graph neural networks. In ICML

    2019

  16. [24]

    Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. 2003. An efficient boosting algorithm for combining preferences. JMLR 4, Nov (2003), 933–969

    2003

  17. [25]

    Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In SIGKDD

    2016

  18. [26]

    Aditya Grover, Aaron Zweig, and Stefano Ermon. 2019. Graphite: Iterative generative modeling of graphs. In ICML

    2019

  19. [27]

    Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS

    2017

  20. [28]

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS

    2020

  21. [29]

    Yang Hu, Xiyuan Wang, Zhouchen Lin, Pan Li, and Muhan Zhang. 2022. Two- Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction. arXiv preprint arXiv:2206.09567 (2022)

    2022 arXiv

  22. [30]

    Zexi Huang, Arlei Silva, and Ambuj Singh. 2021. A Broader Picture of Random- walk Based Graph Embedding. In SIGKDD

    2021

  23. [31]

    Zexi Huang, Arlei Silva, and Ambuj Singh. 2022. POLE: Polarized Embedding for Signed Networks. In WSDM

    2022

  24. [32]

    Boris Ivanovic and Marco Pavone. 2019. The trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs. In ICCV

    2019

  25. [33]

    Mohsen Jamali and Martin Ester. 2009. Trustwalker: a random walk model for combining trust-based and item-based recommendation. In SIGKDD

    2009

  26. [34]

    Glen Jeh and Jennifer Widom. 2002. Simrank: a measure of structural-context similarity. In SIGKDD

    2002

  27. [35]

    Brian Karrer and Mark EJ Newman. 2011. Stochastic blockmodels and commu- nity structure in networks. PRE 83, 1 (2011), 016107

    2011

  28. [36]

    George Karypis and Vipin Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing ACM KDD 2025, Aug 03–07, 2025, Toronto, ON, Canada Mattos et al. 20, 1 (1998), 359–392

    1998

  29. [37]

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

    1953

  30. [38]

    Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic opti- mization. In ICLR

    2015

  31. [39]

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

    2016 arXiv

  32. [40]

    Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR

    2017

  33. [41]

    Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR

    2018

  34. [42]

    Cheng Li, Jiaqi Ma, Xiaoxiao Guo, and Qiaozhu Mei. 2017. Deepcas: An end-to- end predictor of information cascades. In WebConf

    2017

  35. [43]

    Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. 2024. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. Advances in Neural Information Processing Systems 36 (2024)

    2024

  36. [44]

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

    2020

  37. [45]

    Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. 2018. Learning deep generative models of graphs. In ICML

    2018

  38. [46]

    David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. Journal of the American society for information science and technology 58, 7 (2007), 1019–1031

    2007

  39. [47]

    Zheyi Liu, Darong Lai, Chuanyou Li, and Meng Wang. 2020. Feature Fusion Based Subgraph Classification for Link Prediction. In CIKM

    2020

  40. [48]

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

    2011

  41. [49]

    Haitao Mao, Juanhui Li, Harry Shomer, Bingheng Li, Wenqi Fan, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. 2023. Revisiting link prediction: A data perspective. arXiv preprint arXiv:2310.00793 (2023)

    2023 arXiv

  42. [50]

    Travis Martin, Brian Ball, and Mark EJ Newman. 2016. Structural inference for uncertain networks. Physical Review E 93, 1 (2016), 012306

    2016

  43. [51]

    Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. 2016. A survey of link prediction in complex networks. ACM computing surveys (CSUR) 49, 4 (2016), 1–33

    2016

  44. [52]

    Brian McFee and Gert Lanckriet. 2010. Metric learning to rank. In ICML

    2010

  45. [53]

    Federico Monti, Michael Bronstein, and Xavier Bresson. 2017. Geometric matrix completion with recurrent multi-graph neural networks. In NeurIPS

    2017

  46. [54]

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI

    2019

  47. [55]

    Mark Newman. 2018. Networks. Oxford university press

    2018

  48. [56]

    Mark EJ Newman. 2001. Clustering and preferential attachment in growing networks. Physical review E 64, 2 (2001), 025102

    2001

  49. [57]

    Mark EJ Newman. 2006. Modularity and community structure in networks. PNAS 103, 23 (2006), 8577–8582

    2006

  50. [58]

    Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. 2016. Asym- metric transitivity preserving graph embedding. In SIGKDD

    2016

  51. [59]

    Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab

    1999

  52. [60]

    Liming Pan, Cheng Shi, and Ivan Dokmanić. 2022. Neural Link Prediction with Walk Pooling. In ICLR

    2022

  53. [61]

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gre- gory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al

  54. [62]

    Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In SIGKDD

    2014

  55. [63]

    In NeurIPS

    Pytorch: An imperative style, high-performance deep learning library. In NeurIPS

  56. [64]

    Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM

    2018

  57. [65]

    Yanjun Qi, Ziv Bar-Joseph, and Judith Klein-Seetharaman. 2006. Evaluation of different biological data and computational classification methods for use in protein interaction prediction. Proteins: Structure, Function, and Bioinformatics 63, 3 (2006), 490–500

    2006

  58. [66]

    Jerome Revaud, Jon Almazán, Rafael S Rezende, and Cesar Roberto de Souza

  59. [67]

    Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang

  60. [68]

    Takaya Saito and Marc Rehmsmeier. 2015. The precision-recall plot is more informative than the ROC plot when evaluating binary classifiers on imbalanced datasets. PloS one 10, 3 (2015), e0118432

    2015

  61. [69]

    Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. 2018. Graph networks as learnable physics engines for inference and control. In ICML

    2018

  62. [70]

    Learning with average precision: Training image retrieval with a listwise loss. In ICCV

  63. [71]

    Sunil Kumar Sahu, Fenia Christopoulou, Makoto Miwa, and Sophia Anani- adou. 2019. Inter-sentence Relation Extraction with Document-level Graph Convolutional Neural Network. In ACL

    2019

  64. [72]

    Kihyuk Sohn. 2016. Improved deep metric learning with multi-class n-pair loss objective. In NeurIPS

    2016

  65. [73]

    Balasubramaniam Srinivasan and Bruno Ribeiro. 2020. On the Equivalence between Positional Node Embeddings and Structural Graph Representations. In International Conference on Learning Representations

    2020

  66. [74]

    Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. 2008. Intro- duction to information retrieval. Vol. 39. Cambridge University Press Cambridge

    2008

  67. [75]

    Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, and Austin R Benson. 2021. Edge proposal sets for link prediction. arXiv preprint arXiv:2106.15810 (2021)

    2021 arXiv

  68. [76]

    Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: extraction and mining of academic social networks. In SIGKDD

    2008

  69. [77]

    Yuchun Tang, Yan-Qing Zhang, Nitesh V Chawla, and Sven Krasser. 2008. SVMs modeling for highly imbalanced classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 39, 1 (2008), 281–288

    2008

  70. [78]

    Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen. 2018. Open Domain Question Answer- ing Using Early Fusion of Knowledge Bases and Text. In EMNLP

    2018

  71. [79]

    Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2018. RotatE: Knowl- edge Graph Embedding by Relational Rotation in Complex Space. In ICLR

    2018

  72. [80]

    Xinshao Wang, Yang Hua, Elyor Kodirov, Guosheng Hu, Romain Garnier, and Neil M Robertson. 2019. Ranked list loss for deep metric learning. In ICCV

    2019

  73. [81]

    Xiyuan Wang, Haotong Yang, and Muhan Zhang. 2023. Neural Common Neigh- bor with Completion for Link Prediction.arXiv preprint arXiv:2302.00890 (2023)

    2023 arXiv

  74. [82]

    Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In ICLR

    2018

  75. [83]

    Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. 2019. Kgat: Knowledge graph attention network for recommendation. In SIGKDD

    2019

  76. [84]

    Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. 2008. Listwise approach to learning to rank: theory and algorithm. In ICML

    2008

  77. [85]

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How Powerful are Graph Neural Networks?. In ICLR

    2018

  78. [86]

    Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. 2019. End to end learning and optimization on graphs. NeurIPS (2019)

    2019

  79. [87]

    Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying graph convolutional networks. In ICML

    2019

  80. [88]

    Yonghui Yang, Le Wu, Richang Hong, Kun Zhang, and Meng Wang. 2021. En- hanced graph learning for collaborative filtering via mutual information maxi- mization. In SIGIR

    2021

  81. [89]

    Liang Yao, Chengsheng Mao, and Yuan Luo. 2019. Graph convolutional networks for text classification. In AAAI

    2019

  82. [90]

    Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. 2021. Link prediction with persistent homology: An interactive view. In ICML

    2021

  83. [91]

    Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015. Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In ICLR

    2015

  84. [92]

    Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. 2018. Graphrnn: Generating realistic graphs with deep auto-regressive models. In ICML

    2018

  85. [93]

    Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim

  86. [94]

    Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differen- tiable pooling. In NeurIPS

    2018

  87. [95]

    Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. 2021. Identity-aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence. 10737–10745

    2021

  88. [96]

    Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. 2018. An end-to-end deep learning architecture for graph classification. In AAAI

    2018

  89. [97]

    Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. 2021. Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning. In NeurIPS

    2021

  90. [98]

    Yiding Zhang, Xiao Wang, Chuan Shi, Nian Liu, and Guojie Song. 2021. Lorentzian graph convolutional networks. In WebConf

    2021

  91. [99]

    Muhan Zhang and Yixin Chen. 2017. Weisfeiler-lehman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining . 575–583

    2017

  92. [100]

    Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In NeurIPS

    2018

  93. [101]

    Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. 2021. Data augmentation for graph neural networks. In AAAI

    2021

  94. [102]

    Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. 2020. Robust graph representation learning via neural sparsification. In ICML

    2020

  95. [103]

    Shijie Zhou, Zhimeng Guo, Charu Aggarwal, Xiang Zhang, and Suhang Wang

  96. [104]

    Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu

  97. [105]

    In SIGKDD

    Arbitrary-order proximity preserved network embedding. In SIGKDD. Attribute-Enhanced Similarity Ranking for Sparse Link Prediction ACM KDD 2025, Aug 03–07, 2025, Toronto, ON, Canada

    2025

  98. [106]

    Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. 2022. Graph data augmentation for graph machine learning: A survey. arXiv preprint arXiv:2202.08871 (2022)

    2022 arXiv

  99. [111]

    Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. 2009. Predicting missing links via local information. The European Physical Journal B 71, 4 (2009), 623–630

    2009

  100. [112]

    needles in a haystack

    Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. 2021. Neural bellman-ford networks: A general graph neural network framework for link prediction. In NeurIPS. ACM KDD 2025, Aug 03–07, 2025, Toronto, ON, Canada Mattos et al. A ANALYSIS OF LINK PREDICTION EV AL...

    2021

  101. [2018]

    In SIGKDD

    Deepinf: Social influence prediction with deep learning. In SIGKDD

  102. [2019]

    In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining

    Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining . 257–266

  103. [2021]

    In NeurIPS

    Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction. In NeurIPS

  104. [2022]

    arXiv preprint arXiv:2208.01820 (2022)

    Link prediction on heterophilic graphs via disentangled representation learning. arXiv preprint arXiv:2208.01820 (2022)

    2022 arXiv

Pith tools

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