Diffusion-based Negative Sampling on Graphs for Link Prediction

链路预测是图分析的基本任务，具有重要的网络应用，例如社交网络分析和推荐系统等。现代图链路预测方法通常采用对比方法来学习鲁棒的节点表示，其中负采样是关键。典型的负采样方法旨在基于预定义的启发式或自动对抗方法检索困难的例子，这可能是不灵活或难以控制的。此外，在链路预测的背景下，大多数先前的方法从图的现有子结构中对负节点进行采样，错过了潜在的更优采样。为了解决这些问题，我们研究了一种新颖的多级负采样策略，可以从潜在空间中生成具有灵活和可控的“难度”级别的负节点。我们的方法称为基于条件扩散的多级负采样（DMNS），利用扩散模型的马尔可夫链属性，在多个级别的可变难度下生成负节点，并将它们调和以实现有效的图链路预测。我们进一步证明DMNS遵循亚线性正性原则，以实现鲁棒的负采样。在几个基准数据集上的广泛实验证明了DMNS的有效性。

本论文旨在解决图链接预测中负采样方法的限制性问题，即现有方法无法从潜在空间中获取最优的负样本。

本论文提出了一种名为条件扩散多级负采样（DMNS）的方法，利用扩散模型的马尔可夫链属性在多个难度级别上生成负节点，并将它们协调起来以实现有效的图链接预测。

本论文的方法可以在潜在空间中生成具有不同难度级别的负样本，从而提高负采样的灵活性和可控性。DMNS遵循亚线性正性原则，具有鲁棒的负采样性能。实验结果表明，DMNS在多个基准数据集上的表现优于其他现有方法。

与本论文相关的研究包括：《DeepWalk》、《LINE》、《Node2Vec》等基于图嵌入的方法，以及《Adversarial Negative Sampling》、《Unsupervised Inductive Negative Sampling》等负采样方法。