# Learning over Positive and Negative Edges with Contrastive Message Passing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 18 May 2026.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [Understanding Dimensional Collapse in Contrastive Self-supervised Learning](https://mlsanity.com/paper/2110.09348/) (2021)
- [Debiased Contrastive Learning](https://mlsanity.com/paper/2007.00224/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [InfoGCL: Information-Aware Graph Contrastive Learning](https://mlsanity.com/paper/2110.15438/) (2021)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks](https://mlsanity.com/paper/1905.08865/) (2019)
- [Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification](https://mlsanity.com/paper/1905.04579/) (2019)
- [SIGformer: Sign-aware Graph Transformer for Recommendation](https://mlsanity.com/paper/2404.11982/) (2024)
- [PANE-GNN: Unifying Positive and Negative Edges in Graph Neural Networks for Recommendation](https://mlsanity.com/paper/2306.04095/) (2023)
- [Evaluating Performance and Bias of Negative Sampling in Large-Scale Sequential Recommendation Models](https://mlsanity.com/paper/2410.17276/) (2024)
- [TeX-Graph: Coupled tensor-matrix knowledge-graph embedding for COVID-19 drug repurposing](https://mlsanity.com/paper/2010.11367/) (2020)

## Abstract (arXiv)

Conventional approaches to learning on graphs involve message passing along existing (i.e., positive) edges to update node features. However, these approaches often disregard the potentially valuable information contained in the absence (i.e., negative) of edges. Here, we theoretically analyze the value of negative edges in graph representations and prove that in settings of low label rates, high homophily, and high edge density, access to negative edges provides significant information gain over using only positive edges. Motivated by this insight, we introduce Contrastive Message Passing (CMP), a general message passing architecture that enable graph neural network layers to reason over positive and negative edges. By imposing soft positive semidefinite constraints on the learnable weights, our approach differentially applies similarity-preserving transformations to positively connected nodes and dissimilarity-inducing transformations to negatively connected nodes. Over simulated and real datasets in varying data regimes, CMP consistently outperforms baselines in low-label settings when negative edges are informative.