# Diffusion-based Negative Sampling on Graphs for Link Prediction

arXiv: https://arxiv.org/abs/2403.17259 · HTML: https://mlsanity.com/paper/2403.17259/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 54 references that are in the map.
- First posted on arXiv 25 Mar 2024.

## Builds on (most cited first, 30 of 37)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [GLIDE: Towards Photorealistic Image Generation and Editing with Text-Guided Diffusion Models](https://mlsanity.com/paper/2112.10741/) (2021)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Imagen Video: High Definition Video Generation with Diffusion Models](https://mlsanity.com/paper/2210.02303/) (2022)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Palette: Image-to-Image Diffusion Models](https://mlsanity.com/paper/2111.05826/) (2021)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Equivariant Diffusion for Molecule Generation in 3D](https://mlsanity.com/paper/2203.17003/) (2022)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017)
- [DiffuSeq: Sequence to Sequence Text Generation with Diffusion Models](https://mlsanity.com/paper/2210.08933/) (2022)
- [Understanding Diffusion Models: A Unified Perspective](https://mlsanity.com/paper/2208.11970/) (2022)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Hard negative examples are hard, but useful](https://mlsanity.com/paper/2007.12749/) (2020)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)

## Built on by (most cited first, 9 of 9)

- [Non-Homophilic Graph Pre-Training and Prompt Learning](https://mlsanity.com/paper/2408.12594/) (2024)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [S-Diff: An Anisotropic Diffusion Model for Collaborative Filtering in Spectral Domain](https://mlsanity.com/paper/2501.00384/) (2024)
- [Diffusion-based Hierarchical Negative Sampling for Multimodal Knowledge Graph Completion](https://mlsanity.com/paper/2501.15393/) (2025)
- [Graph Diffusion Network for Drug-Gene Prediction](https://mlsanity.com/paper/2502.09335/) (2025)
- [Diffusion-augmented Graph Contrastive Learning for Collaborative Filter](https://mlsanity.com/paper/2503.16290/) (2025)
- [Causal Negative Sampling via Diffusion Model for Out-of-Distribution Recommendation](https://mlsanity.com/paper/2508.07243/) (2025)
- [Towards A Tri-View Diffusion Framework for Recommendation](https://mlsanity.com/paper/2511.20122/) (2025)
- [TFPS: A Temporal Filtration-enhanced Positive Sample Set Construction Method for Implicit Collaborative Filtering](https://mlsanity.com/paper/2602.22521/) (2026)

## Abstract (arXiv)

Link prediction is a fundamental task for graph analysis with important applications on the Web, such as social network analysis and recommendation systems, etc. Modern graph link prediction methods often employ a contrastive approach to learn robust node representations, where negative sampling is pivotal. Typical negative sampling methods aim to retrieve hard examples based on either predefined heuristics or automatic adversarial approaches, which might be inflexible or difficult to control. Furthermore, in the context of link prediction, most previous methods sample negative nodes from existing substructures of the graph, missing out on potentially more optimal samples in the latent space. To address these issues, we investigate a novel strategy of multi-level negative sampling that enables negative node generation with flexible and controllable ``hardness'' levels from the latent space. Our method, called Conditional Diffusion-based Multi-level Negative Sampling (DMNS), leverages the Markov chain property of diffusion models to generate negative nodes in multiple levels of variable hardness and reconcile them for effective graph link prediction. We further demonstrate that DMNS follows the sub-linear positivity principle for robust negative sampling. Extensive experiments on several benchmark datasets demonstrate the effectiveness of DMNS.