Research map / Graph learning / GNN architectures
Structure Balance and Gradient Matching-Based Signed Graph Condensation
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 SGSGC, a signed graph condensation method combining structure-balanced matching (structural balance theory), gradient matching, feature smoothing and sparsification, optimized bi-level, for sign link prediction.
Problem
Graph condensation for signed graphs with conflicting (negative) links and structural balance, where existing gradient/distribution matching methods only handle simple unsigned link structures, hurting link sign prediction on large graphs.
Approach
Introduces a structure-balanced matching loss, derived from graph homomorphism and structural balance theory, that aligns positive neighbors and separates positive from negative neighbors between original and condensed signed graphs, combined with gradient matching, feature smoothing, and edge sparsification in a bi-level optimization.
Key results
- On Epinions at 0.05% ratio, SGSGC reaches 91.7% AUC versus 86.3% for the best heuristic baseline, about 6.26% improvement over the sub-optimal result.
- On Wiki at 0.35% ratio, SGSGC achieves 82.0% AUC versus 77.9% for SGDD (5.26% improvement).
- Ablation on Wiki shows the sparsification operation adds 3.17% AUC, and full SGSGC is 7.40% above GCond.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SGSGC instead of the strongest listed baseline at the 0.35% condensation ratio | Signed graph link sign prediction · Wiki, 0.35% | AUC: 77.9±3.8 -> 82.0±2.7 | Helped |
| Use SGSGC instead of GDC | Signed graph link sign prediction · Bitcoin-alpha, 1.50% | AUC: 95.2±1.0 -> 96.0±0.3 | Helped |
| Use SGSGC instead of SGDD | Signed graph link sign prediction · Wiki-rfa, 2.00% | AUC: 89.9±2.8 -> 91.5±1.2 | Helped |
| Use SGSGC instead of SGDD | Signed graph link sign prediction · Slashdot, 0.10% | AUC: 83.4±5.9 -> 87.4±1.5 | Helped |
| Use SGSGC instead of GDC | Signed graph link sign prediction · Epinions, 0.05% | AUC: 86.0±0.9 -> 91.7±0.7 | Helped |
| Add structure-balanced matching (ablation) | SGSGC · Wiki and Slashdot | AUC | Helped |
| Add feature smoothing (ablation) | SGSGC · Wiki and Slashdot | AUC: 3.17% | Helped |
| Add structure-balanced matching and feature smoothing (ablation) | SGSGC · Wiki | AUC: 7.40% | Helped |
| Vary α and β across a wide range (ablation) | SGSGC · Wiki and Epinions | AUC | No clear effect |
Surprising findings
- GCDM, a distribution-matching method, performs worse than other condensation methods, suggesting gradient matching better retains label-related information.
Limitations
- Evaluated only on link sign prediction; the authors note it has not been extended to other tasks
- Hyperparameter sensitivity to alpha and beta, with best settings differing by dataset
- Results on Slashdot and Epinions show high variance for some baselines, and the paper gives no compute or runtime measurements
Experimental setup
Datasets: Bitcoin-alpha Wiki Wiki-rfa Slashdot Epinions
Benchmarks: Bitcoin-alpha Wiki Wiki-rfa Slashdot Epinions
Metrics: AUC standard deviation
Baselines: Random Herding K-Center Coarsening GDC GCond GCDM SGDD
Builds on: GCond SGDD SGCN structural balance theory
Closest papers by meaning
- A Signed Graph Approach to Understanding and Mitigating Oversmoothing (NeurIPS 2025 · similarity 0.90)
- Adapting Precomputed Features for Efficient Graph Condensation (ICML 2025 · similarity 0.88)
- DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.88)
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.87)
- Self-Explainable Graph Transformer for Link Sign Prediction (AAAI 2025 · similarity 0.87)
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.