# Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 5 Dec 2022.

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

- [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)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [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)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [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)
- [Convolutional Recurrent Neural Networks for Music Classification](https://mlsanity.com/paper/1609.04243/) (2016)
- [Interpretable and Efficient Heterogeneous Graph Convolutional Network](https://mlsanity.com/paper/2005.13183/) (2020)
- [Utilizing Neural Networks and Linguistic Metadata for Early Detection of Depression Indications in Text Sequences](https://mlsanity.com/paper/1804.07000/) (2018)
- [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)
- [Improving the Similarity Measure of Determinantal Point Processes for Extractive Multi-Document Summarization](https://mlsanity.com/paper/1906.00072/) (2019)
- [Higher-Order Attribute-Enhancing Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2104.07892/) (2021)
- [Expectation-Maximization for Learning Determinantal Point Processes](https://mlsanity.com/paper/1411.1088/) (2014)
- [Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm](https://mlsanity.com/paper/1703.09307/) (2017)
- [Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples](https://mlsanity.com/paper/2210.00728/) (2022)
- [RAN-GNNs: breaking the capacity limits of graph neural networks](https://mlsanity.com/paper/2103.15565/) (2021)

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

- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [Layer-diverse Negative Sampling for Graph Neural Networks](https://mlsanity.com/paper/2403.11408/) (2024)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Bandwidth-constrained Variational Message Encoding for Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2512.11179/) (2025)
- [RW-NSGCN: A Robust Approach to Structural Attacks via Negative Sampling](https://mlsanity.com/paper/2408.06665/) (2024)
- [Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax](https://mlsanity.com/paper/2508.17531/) (2025)
- [Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.17393/) (2026)

## Abstract (arXiv)

Graph convolutional networks (GCNs) have achieved great success in graph representation learning by extracting high-level features from nodes and their topology. Since GCNs generally follow a message-passing mechanism, each node aggregates information from its first-order neighbour to update its representation. As a result, the representations of nodes with edges between them should be positively correlated and thus can be considered positive samples. However, there are more non-neighbour nodes in the whole graph, which provide diverse and useful information for the representation update. Two non-adjacent nodes usually have different representations, which can be seen as negative samples. Besides the node representations, the structural information of the graph is also crucial for learning. In this paper, we used quality-diversity decomposition in determinant point processes (DPP) to obtain diverse negative samples. When defining a distribution on diverse subsets of all non-neighbouring nodes, we incorporate both graph structure information and node representations. Since the DPP sampling process requires matrix eigenvalue decomposition, we propose a new shortest-path-base method to improve computational efficiency. Finally, we incorporate the obtained negative samples into the graph convolution operation. The ideas are evaluated empirically in experiments on node classification tasks. These experiments show that the newly proposed methods not only improve the overall performance of standard representation learning but also significantly alleviate over-smoothing problems.