Maximizing Cohesion and Separation in Graph Representation Learning: A Distance-aware Negative Sampling Approach

• URL: http://arxiv.org/abs/2007.01423v2
• Date: Thu, 21 Jan 2021 08:27:06 GMT
• Title: Maximizing Cohesion and Separation in Graph Representation Learning: A Distance-aware Negative Sampling Approach
• Authors: M. Maruf and Anuj Karpatne
• Abstract summary: Unsupervised graph representation learning (GRL) is to learn a low-dimensional space of node embeddings that reflect the structure of a given unlabeled graph. Existing algorithms for this task rely on negative sampling objectives that maximize the similarity in node embeddings at nearby nodes. We present a novel Distance-aware Negative Sampling (DNS) which maximizes the separation of distant node-pairs.
• Score: 9.278968846447215
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The objective of unsupervised graph representation learning (GRL) is to learn a low-dimensional space of node embeddings that reflect the structure of a given unlabeled graph. Existing algorithms for this task rely on negative sampling objectives that maximize the similarity in node embeddings at nearby nodes (referred to as "cohesion") by maintaining positive and negative corpus of node pairs. While positive samples are drawn from node pairs that co-occur in short random walks, conventional approaches construct negative corpus by uniformly sampling random pairs, thus ignoring valuable information about structural dissimilarity among distant node pairs (referred to as "separation"). In this paper, we present a novel Distance-aware Negative Sampling (DNS) which maximizes the separation of distant node-pairs while maximizing cohesion at nearby node-pairs by setting the negative sampling probability proportional to the pair-wise shortest distances. Our approach can be used in conjunction with any GRL algorithm and we demonstrate the efficacy of our approach over baseline negative sampling methods over downstream node classification tasks on a number of benchmark datasets and GRL algorithms. All our codes and datasets are available at https://github.com/Distance-awareNS/DNS/.

Related papers

• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  We propose an approach to reduce the number of nodes that are included during aggregation. We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features. We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup.
  arXiv  Detail & Related papers  (2024-10-25T17:52:16Z)
• Bootstrap Latents of Nodes and Neighbors for Graph Self-Supervised Learning [27.278097015083343]
  Contrastive learning requires negative samples to prevent model collapse and learn discriminative representations. We introduce a cross-attention module to predict the supportiveness score of a neighbor with respect to the anchor node. Our method mitigates class collision from negative and noisy positive samples, concurrently enhancing intra-class compactness.
  arXiv  Detail & Related papers  (2024-08-09T14:17:52Z)
• Reliable Node Similarity Matrix Guided Contrastive Graph Clustering [51.23437296378319]
  We introduce a new framework, Reliable Node Similarity Matrix Guided Contrastive Graph Clustering (NS4GC) Our method introduces node-neighbor alignment and semantic-aware sparsification, ensuring the node similarity matrix is both accurate and efficiently sparse.
  arXiv  Detail & Related papers  (2024-08-07T13:36:03Z)
• Re-visiting Skip-Gram Negative Sampling: Dimension Regularization for More Efficient Dissimilarity Preservation in Graph Embeddings [8.858596502294471]
  We show that node-wise repulsion is, in aggregate, an approximate re-centering of the node embedding dimensions. We propose an algorithm augmentation framework that speeds up any existing algorithm, supervised or unsupervised.
  arXiv  Detail & Related papers  (2024-04-30T19:43:01Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. First, emphnode-wise architectures pre-compute individual embeddings for each node that are later combined by a simple decoder to make predictions. Second, emphedge-wise methods rely on the formation of edge-specific subgraph embeddings to enrich the representation of pair-wise relationships.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• STERLING: Synergistic Representation Learning on Bipartite Graphs [78.86064828220613]
  A fundamental challenge of bipartite graph representation learning is how to extract node embeddings. Most recent bipartite graph SSL methods are based on contrastive learning which learns embeddings by discriminating positive and negative node pairs. We introduce a novel synergistic representation learning model (STERLING) to learn node embeddings without negative node pairs.
  arXiv  Detail & Related papers  (2023-01-25T03:21:42Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN) In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries. By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Node Representation Learning in Graph via Node-to-Neighbourhood Mutual Information Maximization [27.701736055800314]
  Key towards learning informative node representations in graphs lies in how to gain contextual information from the neighbourhood. We present a self-supervised node representation learning strategy via directly maximizing the mutual information between the hidden representations of nodes and their neighbourhood. Our framework is optimized via a surrogate contrastive loss, where the positive selection underpins the quality and efficiency of representation learning.
  arXiv  Detail & Related papers  (2022-03-23T08:21:10Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  We propose a novel pool-based Active Learning framework constructed on a sequential Graph Convolution Network (GCN) With a small number of randomly sampled images as seed labelled examples, we learn the parameters of the graph to distinguish labelled vs unlabelled nodes. We exploit these characteristics of GCN to select the unlabelled examples which are sufficiently different from labelled ones.
  arXiv  Detail & Related papers  (2020-06-18T00:55:10Z)
• Investigating Extensions to Random Walk Based Graph Embedding [0.3867052484157571]
  We propose a novel extension to random walk based graph embedding, which removes a percentage of least frequent nodes from the walks at different levels. By this removal, we simulate farther distant nodes to reside in the close neighborhood of a node and hence explicitly represent their connection. The results indicate, that extensions to random walk based methods (including our own) improve the predictive performance only slightly - if at all.
  arXiv  Detail & Related papers  (2020-02-17T21:14:02Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.