AdaNS: Adaptive negative sampling for unsupervised graph representation learning. (April 2023)

• Record Type: Journal Article
• Authors: Wang, Yu; Hu, Liang; Gao, Wanfu; Cao, Xiaofeng; Chang, Yi
• Is Part Of: Pattern recognition. Volume 136(2023)
• Publication Date: 2023-04
• Subjects: Graph representation learning -- Negative sampling -- Noise contrastive estimation; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.109266
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Hard negatives can relieve the vanishing gradient problem Mixing distribution can alleviate the computational consumption Hard negatives can bring performance improvement An adaptive negative sampling strategy named AdaNS is proposed Abstract: Recently, unsupervised graph representation learning has attracted considerable attention through effectively encoding graph-structured data without semantic annotations. To accelerate its training, noise contrastive estimation (NCE) samples uniformly negative examples to fit an unnormalized graph model. However, this uniform sampling strategy may easily lead to slow convergence, even the vanishing gradient problem. In this paper, we theoretically show that sampling those hard negatives close to the current anchor can relieve the above difficulties. With this finding, we then propose an Ada ptive N egative S ampling strategy, namely AdaNS, which efficiently samples the hard negatives from the mixing distribution regarding the dimensional elements of the current node representation. Experiments show that our AdaNS sampling strategy applied on top of representative unsupervised models, e.g., DeepWalk, GraphSAGE, can outperform the existing negative sampling strategies in the tasks of node classification and visualization. This also further demonstrates that sampling those hard negatives can bring performance improvements for learning the node representations.