Source-linked AI summary
Understanding Negative Sampling in Graph Representation Learning
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, Jie Tang
TL;DR
Graph representation learning has underexplored negative sampling even though sampling affects representation learning at scale. The paper analyzes its objective and risk, proposes MCNS using self-contrast approximation and Metropolis-Hastings, and reports robust improvements across tasks and datasets.
Problem
Negative-sampling strategy in graph representation learning is insufficiently explored, while its distribution can substantially affect performance across datasets.
Method
MCNS approximates the positive distribution using current embeddings and accelerates negative sampling with Metropolis-Hastings.
Results
MCNS stably outperforms eight negative-sampling strategies regardless of the underlying graph representation method.
Takeaways & Limitations
The negative-sampling distribution should be positively but sub-linearly correlated with the positive sampling distribution.
Takeaways & Limitations
The paper notes an O(n)-time sampling formulation that is impractical for middle- or large-scale graphs, motivating MCNS's adapted Metropolis-Hastings algorithm.
Abstract
from arXiv · showhide
Graph representation learning has been extensively studied in recent years. Despite its potential in generating continuous embeddings for various networks, both the effectiveness and efficiency to infer high-quality representations toward large corpus of nodes are still challenging. Sampling is a critical point to achieve the performance goals. Prior arts usually focus on sampling positive node pairs, while the strategy for negative sampling is left insufficiently explored. To bridge the gap, we systematically analyze the role of negative sampling from the perspectives of both objective and risk, theoretically demonstrating that negative sampling is as important as positive sampling in determining the optimization objective and the resulted variance. To the best of our knowledge, we are the first to derive the theory and quantify that the negative sampling distribution should be positively but sub-linearly correlated to their positive sampling distribution. With the guidance of the theory, we propose MCNS, approximating the positive distribution with self-contrast approximation and accelerating negative sampling by Metropolis-Hastings. We evaluate our method on 5 datasets that cover extensive downstream graph learning tasks, including link prediction, node classification and personalized recommendation, on a total of 19 experimental settings. These relatively comprehensive experimental results demonstrate its robustness and superiorities.
1 INTRODUCTION
Graph representation learning commonly uses sampled positive and negative node pairs, but negative-sampling strategy remains underexplored despite its influence on training. The paper analyzes this role theoretically and proposes MCNS, which improves performance across tasks and datasets.
- Graph representation methods transform nodes into low-dimensional vectors for tasks including node classification, link prediction, and recommendation.
- Most methods can be unified as SampledNCE systems with an encoder, positive sampler, and negative sampler trained to distinguish pairs using embedding inner products.
- Negative-sampling strategy is relatively unexplored, whereas prior work has extensively studied positive-pair criteria such as random walks, proximity, and community structure.
- The negative-sampling distribution strongly affects performance, and the best choice varies substantially across datasets.
- Negative sampling should be positively but sub-linearly correlated with positive sampling, helping determine the objective and reduce estimation variance.
- MCNS approximates the positive distribution with current embeddings and accelerates negative sampling using Metropolis-Hastings.
- MCNS significantly improves results across link prediction, node classification, and recommendation, and stably outperforms other strategies on five datasets.
2 FRAMEWORK
The framework unifies network embedding and GNN methods through sampled positive and negative pairs, an encoder, and contrastive optimization. Different methods primarily vary in how they model positive distributions and encode nodes.
- The preliminaries unify network embedding and GNN approaches within a SampledNCE framework for analyzing negative sampling.
- Algorithm 1 samples nodes by degree, one positive per node, and k negative nodes from specified distributions before optimizing cross-entropy over embedding inner products.
- Many network embedding methods use separate central and contextual embeddings, and a bipartite transformation makes their analysis equivalent to unique-embedding graphs.
- The encoder may be an embedding lookup table or a GNN variant that generates node embeddings.
- Network embedding methods define positive distributions through adjacency, random walks, or homophily and structural-equivalence assumptions.
- GNNs implicitly regularize positive distributions through encoder mechanisms such as graph Laplacian smoothing and local smoothness.
3 UNDERSTANDING NEGATIVE SAMPLING
Negative sampling influences both the optimization objective and estimation risk, so its distribution should be chosen alongside the positive sampling distribution. The analysis yields a positively but sub-linearly correlated negative distribution and motivates MCNS as an efficient implementation.
- Objective: The optimal embedding objective is governed jointly by the positive distribution pd and negative distribution pn.The theorem derives the optimum for each node pair from the sampled positive and negative distributions.
- Objective: Negative sampling is as important as positive sampling for determining the optimization objective.The framework explicitly includes both positive and negative distributions in the sampled contrastive objective.
- Risk: With limited positive samples, negative sampling also determines the expected squared deviation, or risk, of learned inner products.The risk analysis characterizes asymptotic estimation error and its dependence on sampling distributions.
- MCNS: MCNS approximates the positive distribution from current embeddings and uses Metropolis-Hastings sampling to reduce negative-sampling cost.Neighbor-based continuation can skip burn-in when adjacent nodes have similar positive distributions.
4 METHOD
MCNS addresses the unknown positive sampling distribution through self-contrast approximation and uses adapted Metropolis-Hastings sampling to make negative sampling practical at scale. It also exploits graph locality and a modified loss to improve sampling efficiency and training.
- 4.1 The Self-contrast Approximation: The unknown positive distribution is approximated using inner products from the current encoder for self-contrast negative sampling.This substitutes an implicitly defined approximation for the unavailable real distribution.
- 4.1 The Self-contrast Approximation: The resulting sampling method has O(n) time per sample, motivating MCNS's adapted Metropolis-Hastings algorithm for middle- and large-scale graphs.The adapted algorithm is introduced specifically to reduce this time cost.
- 4.3 Markov chain Negative Sampling: MCNS applies Metropolis-Hastings to sample from an unnormalized distribution based on encoder inner products raised to α.The chain targets the self-contrast approximated distribution, although standard Metropolis-Hastings can require a long burn-in period.
- 4.3 Markov chain Negative Sampling: Graph traversal reduces burn-in costs because nearby nodes tend to share similar target negative sampling distributions.MCNS uses Depth First Search to continue a Markov chain across neighboring nodes.
- 4.3 Markov chain Negative Sampling: The proposal distribution mixes uniform sampling with sampling from the nearest k nodes, while a γ-skewed hinge loss separates positive and negative pairs by a margin.The hinge loss pulls positive pairs closer and pushes negative pairs away until they exceed the predefined margin.
5 EXPERIMENTS
Experiments evaluate MCNS across three graph-learning tasks, multiple encoders, five datasets, and 19 settings. MCNS consistently improves performance over negative-sampling baselines and also shows favorable efficiency and robustness patterns.
- Experimental Setup: MCNS is evaluated on three representative tasks, three graph representation algorithms, and five datasets across 19 experimental settings.The study compares MCNS with eight negative-sampling baselines.
- Overall Results: Ten-fold cross-validation and paired t-tests show statistically significant improvements, with a maximum p-value of 0.0005 across the 19 settings.The reported maximum p-value is below 0.01.
- Link Prediction: On Arxiv link prediction, MCNS outperforms all baselines across the evaluated graph representation methods.Degree-based strategies outperform uniform RNS on Arxiv, unlike the recommendation datasets.
- Node Classification: On BlogCatalog node classification, MCNS consistently outperforms all baselines across training-set ratios for Micro-F1, with similar Macro-F1 trends.Macro-F1 results are omitted but described as following the same trend.
- Analysis and Efficiency: MCNS adapts beyond degree-based distributions, reaches optimum performance near γ ≈0.1, and completes ten-epoch MovieLens training in 17 minutes while KBGAN is at least 2× slower.Embedding dimension 512 is selected as a trade-off between performance and time consumption.
6 RELATED WORK
Related work spans negative-sampling strategies from word embeddings, recommendation, information retrieval, and knowledge-graph embeddings. Existing approaches include frequency-based, uniform, score-based, hard-negative, rejection-based, GAN-based, and sampled-softmax methods.
- Word2vec-inspired methods sample negatives proportional to word frequency raised to the 3/4 power, a setting followed by later network-embedding work.
- Recommendation methods use uniform, dynamically score-based, hard-negative, or rejection-based negative sampling strategies.
- GAN-based negative sampling has been applied to information retrieval, recommendation, word embeddings, and knowledge-graph embeddings.
- Other research studies sampled softmax and debiasing variants for extremely large-scale settings.
7 CONCLUSION
The paper studies negative sampling theoretically and proposes MCNS from those results. Experiments report that MCNS outperforms eight negative-sampling strategies across graph representation learning methods.
- The paper concludes that negative sampling distributions should be positively but sub-linearly correlated with positive sampling distributions.
- MCNS approximates the ideal negative-sampling distribution through self-contrast and accelerates sampling with Metropolis-Hastings.
- MCNS outperforms 8 negative sampling strategies regardless of the underlying graph representation learning method.
A APPENDIX
The appendix documents the experimental implementation and supporting algorithmic details. It covers the environment, encoders, baselines, datasets, evaluation metrics, and DFS sampling procedure.
- The appendix begins with MCNS implementation notes covering the running environment and implementation details.
- It then presents the encoder algorithms used in the experiments.
- The appendix describes each baseline and concludes with datasets, evaluation metrics, and the DFS algorithm.
A.1 Implementation Notes
Implementation details isolate negative sampling within a three-part training pipeline and specify task-specific validation, graph paths, dimensions, margins, and optimization procedures.
- The implementation separates negative sampling, positive sampling, and embedding learning, with the study focusing on negative sampling strategy.
- Recommendation experiments use ten-fold cross validation plus a validation set, with user-item paths U −I −U and I −U −I for GraphSAGE and GCN.
- Link prediction uses five-fold cross validation, 256-dimensional embeddings, margin γ=0.1, and Adam-optimized stochastic gradient descent.
A.2 Encoders
The experiments use three graph representation algorithms: DeepWalk, GCN, and a third algorithm introduced in the surrounding experimental setup. DeepWalk forms positives from random-walk co-occurrences, while GCN forms them from direct graph edges.
- The experiments evaluate three graph representation algorithms.
- DeepWalk samples nodes co-occurring within random-walk windows as positive pairs.This sampling acts as data augmentation and corresponds to sampling from ˆpd in the SampledNCE view.
- GCN samples positive pairs from direct edges in the graph.
A.3 Baselines
The evaluation compares several negative-sampling strategies across graph representation and recommendation settings, using task-specific datasets, metrics, and experimental protocols. It also describes DFS-based sequence generation for traversal-based representation learning.
- Negative-sampling baselines: The study keeps encoder hyperparameters fixed across negative-sampling strategies.The compared strategies include Power of Degree, RNS, WRMF, DNS, PinSAGE, WARP, IRGAN, and KBGAN.
- Negative-sampling baselines: Power of Degree samples negatives with probability proportional to degree^β, using Deд0.75 as the widely used setting.
- Negative-sampling baselines: RNS samples negative nodes uniformly at random and serves as a recommendation baseline.
- Evaluation: Recommendation performance is evaluated with Hits@k and MRR, with k set to 10 and 30 and M set to 500 for Alibaba and Amazon.MovieLens uses all unconnected items for each user as evaluation items.
- Evaluation: For link prediction, 30% of true edges are removed, 30% false edges are sampled, and AUC is computed from inner-product edge probabilities.Each model is trained on the connected residual graph before test-edge probabilities are scored.
- Sequence generation: DFS generates a traversal sequence whose adjacent nodes are also adjacent in the graph by recursively visiting unvisited neighbors.