Diffusion-based Negative Sampling on Graphs for Link Prediction
This work addresses a bottleneck in graph link prediction for applications like social networks and recommendation systems, offering a more adaptable negative sampling approach, though it is incremental as it builds on existing contrastive methods.
The paper tackled the problem of generating flexible and controllable hard negative samples for graph link prediction by proposing a diffusion-based method that creates negative nodes at multiple hardness levels from the latent space, achieving improved performance on benchmark datasets.
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.