Learning over Positive and Negative Edges with Contrastive Message Passing
For graph neural network practitioners, this work provides a principled way to exploit negative edges, improving performance in label-scarce scenarios.
The paper proves that negative edges provide significant information gain in low-label, high-homophily, high-density settings, and introduces Contrastive Message Passing (CMP), a GNN architecture that leverages both positive and negative edges, outperforming baselines in low-label regimes.
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.