  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.
