Research map / Graph learning / Graph self-supervised learning
Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Error Passing Rate (EPR), a theoretical metric for how well a graph fits a GCN, and uses it to derive adaptive edge-adding and edge-dropping augmentations (EPAGCL) for graph contrastive learning.
Problem
Dropping edges is the dominant topology augmentation in graph contrastive learning, while adding edges performs unstably; there is no theoretical explanation of why, and naive edge adding is costly due to the huge number of candidate node pairs.
Approach
Define Error Passing Rate as the fraction of GCN message passing that flows across different-class edges; show that the change in EPR from adding or dropping an edge scales with a degree-based weight 2/sqrt((d_i+1)(d_j+1)), so low-weight node pairs give stable augmentations. Use these weights to sample edges to add and drop, with edge dropping in both views and edge adding in only one view.
Key results
- EPAGCL reaches 86.07% on Cora and 86.77% on PubMed, achieving the best average rank (2.0) among self-supervised methods in the seven-dataset comparison.
- EPAGCL outperforms GCA by an average of 0.61% accuracy under the same contrastive objective.
- In the ablation, 'Drop Only' beats 'Add Only', consistent with the theory that adding edges is the less stable augmentation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use EPAGCL instead of GCA | GCN · Cora | accuracy: 85.59 ± 0.35 -> 86.07 ± 0.32 | Helped |
| use EPAGCL instead of GRACE | GCN · CiteSeer | accuracy: 71.66 ± 0.35 -> 71.94 ± 0.57 | Helped |
| use EPAGCL instead of GRACE | GCN · PubMed | accuracy: 86.74 ± 0.18 -> 86.77 ± 0.14 | Helped |
| use EPAGCL instead of GCA* | GCN · WikiCS | accuracy: 81.45 ± 0.15 -> 81.19 ± 0.11 | Hurt |
| use EPAGCL instead of GREET | GCN · Amazon-Photo | accuracy: 93.56 ± 0.14 -> 93.42 ± 0.12 | Hurt |
| use EPAGCL instead of GREET | GCN · Coauthor-Physics | accuracy: 96.06 ± 0.11 -> 95.87 ± 0.04 | Hurt |
| use EPAGCL instead of GCA* | GCN · ogbn-arxiv | accuracy: 69.26 ± 0.01 -> 69.25 ± 0.01 | Hurt |
| add feature masking (ablation) | EPAGCL without feature mask · Cora, CiteSeer, PubMed, WikiCS, Amazon-Photo, Coauthor-Physics, ogbn-arxiv | accuracy: 85.04 ± 0.33 -> 86.07 ± 0.32; 71.97 ± 0.62 -> 71.94 ± 0.57; 86.72 ± 0.11 -> 86.77 ± 0.14; 81.81 ± 0.18 -> 81.19 ± 0.11; | Mixed |
| adaptively add and drop edges in both views instead of random add and drop (ablation) | GCN contrastive learning without feature mask · benchmark datasets | accuracy | Helped |
| use adaptive edge dropping only instead of adaptive edge adding only (ablation) | GCN contrastive learning without feature mask · benchmark datasets | accuracy | Helped |
| use EPAGCL’s adaptive edge-adding and edge-dropping strategy instead of the tested alternatives (ablation) | GCN contrastive learning without feature mask · benchmark datasets | accuracy | Helped |
Surprising findings
- Edge adding was found to be a poorer augmentation than edge dropping on every dataset tested, even with adaptive weighting in the Add Only variant.
- The paper's theory implies that GCA's preference for dropping low-importance edges (higher alpha) yields less stable results.
Limitations
- The theory relies on Assumption 3.4 (constant error fraction k per node) and on a degree constraint d_max <= 4d_min - 1 in Theorem 3.3.
- Experiments are limited to homophilous node classification; heterogeneous graph results are only on three small datasets in the appendix.
- Memory and preprocessing overhead are higher than GCA.
Experimental setup
Datasets: Cora CiteSeer PubMed WikiCS Amazon-Photo Coauthor-Physics ogbn-arxiv Texas Cornell Wisconsin
Benchmarks: Cora CiteSeer PubMed WikiCS Amazon-Photo Coauthor-Physics ogbn-arxiv Texas Cornell Wisconsin
Metrics: classification accuracy standard deviation pre-processing time training time per epoch FLOPs memory cost Wilcoxon signed-rank p-value
Baselines: GCN GAT DGI GMI MVGRL GRACE GCA BGRL GREET
Builds on: GRACE GCA GCN positive-incentive noise
Closest papers by meaning
- Edge Contrastive Learning: An Augmentation-Free Graph Contrastive Learning Model (AAAI 2025 · similarity 0.89)
- ReGCL: Rethinking Message Passing in Graph Contrastive Learning (AAAI 2024 · similarity 0.88)
- Perfect Alignment May be Poisonous to Graph Contrastive Learning (ICML 2024 · similarity 0.88)
- Does GCL Need a Large Number of Negative Samples? Enhancing Graph Contrastive Learning with Effective and Efficient Negative Sampling (AAAI 2025 · similarity 0.87)
- Graph Contrastive Learning with Joint Spectral Augmentation of Attribute and Topology (AAAI 2025 · similarity 0.86)
- A New Mechanism for Eliminating Implicit Conflict in Graph Contrastive Learning (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.