Research map / Graph learning / GNN architectures

DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks

NeurIPS 2024 · Graph learning › GNN architectures · approach: Graph structure learning · 2 citations (OpenAlex)

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.

Shows random DropEdge cannot help link sign prediction (with a generalization bound for SGNNs) and proposes SGA, a signed-graph augmentation framework that adds/removes edges via SGCN-based candidates filtered by balance theory plus curriculum learning on edge difficulty scores.

Problem

Signed graphs are sparse and contain many unbalanced triangles, which hurt SGNNs on link sign prediction; existing graph augmentation methods need node features or labels that signed graphs lack, and random DropEdge is shown not to help.

Approach

A structure augmentation module uses an SGCN encoder to propose candidate edges, keeps only candidates that do not create new unbalanced triangles, and trains with a curriculum that orders edges by a local balance-based difficulty score (edges in unbalanced triangles are harder).

Key results

• SGA boosts SGCN AUC by 14.8% on Wiki-RfA and F1-micro by 32.3% on Slashdot, per the paper's reported best improvements.
• Random DropEdge-style perturbations (random add/remove of positive/negative edges, sign flipping) do not stably improve SGCN performance in the experiments.
• Across six datasets and five backbones, SGA improves link sign prediction for most settings, with the balance degree rising on most datasets (e.g., Wiki-RfA 75.54% to 85.38%).

Measured effects reported in the paper

Surprising findings

• Random DropEdge and other random structural perturbations do not improve SGCN, and the theory suggests deleting edges increases the generalization bound.
• SGA slightly reduces the balance degree on Bitcoin-otc (89.04% to 88.60%) and the GAT Wiki-RfA AUC drops.

Limitations

• Assumes balance theory fits the data; the paper acknowledges it may be less effective on datasets that do not conform to balance theory.
• Validated only on link sign prediction; clustering and other signed graph tasks are not tested.
• Some improvements have large standard deviations, and some metrics decline for certain backbones.

Experimental setup

Datasets: Bitcoin-OTC Bitcoin-Alpha Wiki-elec Wiki-RfA Epinions Slashdot

Benchmarks: Bitcoin-OTC Bitcoin-Alpha Wiki-elec Wiki-RfA Epinions Slashdot

Metrics: AUC F1-binary F1-macro F1-micro

Baselines: GCN GAT SGCN SiGAT GS-GNN DropEdge

Builds on: SGCN DropEdge structural balance theory GAUG

Closest papers by meaning

• Self-Explainable Graph Transformer for Link Sign Prediction (AAAI 2025 · similarity 0.91)
• Structure Balance and Gradient Matching-Based Signed Graph Condensation (AAAI 2025 · similarity 0.88)
• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs (ICML 2024 · similarity 0.87)
• A Signed Graph Approach to Understanding and Mitigating Oversmoothing (NeurIPS 2025 · similarity 0.86)
• Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classifications (AAAI 2025 · similarity 0.86)
• Edge Prompt Tuning for Graph Neural Networks (ICLR 2025 · similarity 0.85)