# Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples

arXiv: https://arxiv.org/abs/2210.00728 · HTML: https://mlsanity.com/paper/2210.00728/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 30 references that are in the map.
- First posted on arXiv 3 Oct 2022.

## Builds on (most cited first, 16 of 16)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Towards Deeper Graph Neural Networks with Differentiable Group Normalization](https://mlsanity.com/paper/2006.06972/) (2020)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Understanding Negative Sampling in Graph Representation Learning](https://mlsanity.com/paper/2005.09863/) (2020)
- [Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework](https://mlsanity.com/paper/2004.02593/) (2020)
- [Learning the Parameters of Determinantal Point Process Kernels](https://mlsanity.com/paper/1402.4862/) (2014)
- [Expectation-Maximization for Learning Determinantal Point Processes](https://mlsanity.com/paper/1411.1088/) (2014)

## Built on by (most cited first, 10 of 10)

- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes](https://mlsanity.com/paper/2212.02055/) (2022)
- [Layer-diverse Negative Sampling for Graph Neural Networks](https://mlsanity.com/paper/2403.11408/) (2024)
- [Inferring Latent Temporal Sparse Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2403.19253/) (2024)
- [Bandwidth-constrained Variational Message Encoding for Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2512.11179/) (2025)
- [Balancing Augmentation with Edge-Utility Filter for Signed GNNs](https://mlsanity.com/paper/2310.16862/) (2023)
- [Heterophilous Distribution Propagation for Graph Neural Networks](https://mlsanity.com/paper/2405.20640/) (2024)
- [RW-NSGCN: A Robust Approach to Structural Attacks via Negative Sampling](https://mlsanity.com/paper/2408.06665/) (2024)
- [Bayesian Neighborhood Adaptation for Graph Neural Networks](https://mlsanity.com/paper/2602.05358/) (2026)
- [Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.17393/) (2026)

## Abstract (arXiv)

Graph Convolutional Neural Networks (GCNs) has been generally accepted to be an effective tool for node representations learning. An interesting way to understand GCNs is to think of them as a message passing mechanism where each node updates its representation by accepting information from its neighbours (also known as positive samples). However, beyond these neighbouring nodes, graphs have a large, dark, all-but forgotten world in which we find the non-neighbouring nodes (negative samples). In this paper, we show that this great dark world holds a substantial amount of information that might be useful for representation learning. Most specifically, it can provide negative information about the node representations. Our overall idea is to select appropriate negative samples for each node and incorporate the negative information contained in these samples into the representation updates. Moreover, we show that the process of selecting the negative samples is not trivial. Our theme therefore begins by describing the criteria for a good negative sample, followed by a determinantal point process algorithm for efficiently obtaining such samples. A GCN, boosted by diverse negative samples, then jointly considers the positive and negative information when passing messages. Experimental evaluations show that this idea not only improves the overall performance of standard representation learning but also significantly alleviates over-smoothing problems.