Learning over Positive and Negative Edges with Contrastive Message Passing

• URL: http://arxiv.org/abs/2605.17854v1
• Date: Mon, 18 May 2026 04:52:07 GMT
• Title: Learning over Positive and Negative Edges with Contrastive Message Passing
• Abstract summary: We introduce Contrastive Message Passing (CMP) to enable graph neural network layers to reason over positive and negative edges.<n>CMP consistently outperforms baselines in low-label settings when negative edges are informative.
• Score: 45.18818712867722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Adversarial Signed Graph Learning with Differential Privacy [13.459205297125534]
  Signed graphs with positive and negative edges can model complex relationships in social networks.<n>Training on sensitive signed graphs raises significant privacy concerns.<n>We present ASGL, a privacy-preserving adversarial signed graph learning method.
  arXiv  Detail & Related papers  (2025-11-29T04:02:48Z)
• A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
  We present a unified theoretical perspective based on the framework of signed graphs.<n>We show that many existing strategies implicitly introduce negative edges that alter message-passing to resist oversmoothing.<n>We propose Structural Balanced Propagation (SBP), a plug-and-play method that assigns signed edges based on either labels or feature similarity.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  We introduce a new metric, namely Error Passing Rate (EPR), to quantify how a graph fits the network.<n>Inspired by the theoretical conclusions and the idea of positive-incentive noise, we propose a novel GCL algorithm, Error-PAssing-based Graph Contrastive Learning (EPAGCL)<n>We generate views by adding and dropping edges based on the weights derived from EPR.
  arXiv  Detail & Related papers  (2024-12-11T06:31:06Z)
• Negative as Positive: Enhancing Out-of-distribution Generalization for Graph Contrastive Learning [60.61079931266331]
  We propose a novel strategy "Negative as Positive", where the most semantically similar cross-domain negative pairs are treated as positive during Graph contrastive learning (GCL) Our experimental results, spanning a wide array of datasets, confirm that this method substantially improves the OOD generalization performance of GCL.
  arXiv  Detail & Related papers  (2024-05-25T13:29:31Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• Smoothed Graph Contrastive Learning via Seamless Proximity Integration [30.247207861739245]
  Graph contrastive learning (GCL) aligns node representations by classifying node pairs into positives and negatives. We present a Smoothed Graph Contrastive Learning model (SGCL) that injects proximity information associated with positive/negative pairs in the contrastive loss. The proposed SGCL adjusts the penalties associated with node pairs in contrastive loss by incorporating three distinct smoothing techniques.
  arXiv  Detail & Related papers  (2024-02-23T11:32:46Z)
• Balancing Augmentation with Edge-Utility Filter for Signed GNNs [0.20482269513546458]
  Signed graph neural networks (SGNNs) has recently drawn more attention as many real-world networks are signed networks containing two types of edges: positive and negative. The existence of negative edges affects the SGNN robustness on two aspects. One is the semantic imbalance as the negative edges are hard to obtain though they can provide potentially useful information. In this paper, we propose a balancing augmentation method to address the above two aspects for SGNNs. Firstly, the utility of each negative edge is measured by calculating its occurrence in unbalanced structures. Secondly, the original signed graph is selectively augmented with the use of (1) an edge regulator
  arXiv  Detail & Related papers  (2023-10-25T07:15:01Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories.<n>We propose a novel GNN architecture whereby the emphforward pass explicitly depends on emphboth positive (as is typical) and negative (unique to our approach) edges.<n>This is achieved by recasting the embeddings themselves as minimizers of a forward-pass-specific energy function that favors separation of positive and negative samples.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• Pseudo Contrastive Learning for Graph-based Semi-supervised Learning [67.37572762925836]
  Pseudo Labeling is a technique used to improve the performance of Graph Neural Networks (GNNs) We propose a general framework for GNNs, termed Pseudo Contrastive Learning (PCL)
  arXiv  Detail & Related papers  (2023-02-19T10:34:08Z)
• Relation-aware Graph Attention Model With Adaptive Self-adversarial Training [29.240686573485718]
  This paper describes an end-to-end solution for the relationship prediction task in heterogeneous, multi-relational graphs. We particularly address two building blocks in the pipeline, namely heterogeneous graph representation learning and negative sampling. We introduce a parameter-free negative sampling technique -- adaptive self-adversarial (ASA) negative sampling.
  arXiv  Detail & Related papers  (2021-02-14T16:11:56Z)

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.