Research map / Adversarial robustness and security / Attacks on text and graphs
Robust Graph Condensation via Classification Complexity Mitigation
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 that graph condensation reduces classification complexity (intrinsic dimension) but adversarial attacks on the original graph undo this, and proposes MRGC, a plug-and-play robust GC framework with three manifold regularizers (intrinsic dimension, curvature smoothing, class-wise manifold decoupling) on top of GCond.
Problem
Graph condensation degrades substantially when the original graph is corrupted by structure, feature, or label poisoning attacks, and existing robust GNN and robust GC methods provide limited protection.
Approach
GC acts as an intrinsic-dimension-reducing process that lowers classification complexity; attacks increase it in the condensed graph. MRGC protects this property by regularizing the condensed graph's intrinsic dimension (Laplacian-approximated manifold volume), penalizing curvature-weighted class boundary complexity via Ricci-curvature-reweighted Gaussian curvature, and minimizing overlap between
Key results
- On Cora at 1.30% ratio under structure, feature, and label attacks (1,10,20), MRGC reaches 77.43±0.32 versus 70.69±1.79 for GCond.
- On CiteSeer at 0.90% ratio, MRGC reaches 65.12±0.69 versus 60.77±2.00 for GCond, the runner-up.
- Under varying attack budgets on CiteSeer, MRGC improves over the runner-up by about 3.98% and 4.75% at 30% and 40% label perturbation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply MRGC instead of standard GCond during condensation | GCond graph condensation · Cora, CiteSeer, PubMed, DBLP, and Ogbn-Arxiv under poisoning attacks | accuracy | Mixed |
| Add intrinsic-dimension manifold regularization (ablation) | MRGC on Cora and CiteSeer · Lowest condensation ratio under attack | accuracy | Helped |
| Add curvature-aware manifold smoothing (ablation) | MRGC on Cora and CiteSeer · Lowest condensation ratio under attack | accuracy | Helped |
| Add class-wise manifold decoupling (ablation) | MRGC on Cora and CiteSeer · Lowest condensation ratio under attack | accuracy | Helped |
| Use graph denoising preprocessing before GCond | GCond · Poisoning attacks across five node-classification datasets | accuracy | No clear effect |
Surprising findings
- Plugging MedianGCN, a classic robust GNN, into GC or training on a GCond-condensed graph with MedianGCN performs worse than standard GCond under attack.
- Denoising preprocessing (Jaccard, SVD, kNN) before GCond gives limited gains because it assumes clean features and labels.
Limitations
- Evaluation is limited to node classification; graph classification is left for future work.
- Hyperparameters alpha, beta, gamma are tuned by grid search, and the method adds notable computation (Gaussian curvature is O(n'(d')^6)).
Experimental setup
Datasets: Cora CiteSeer PubMed DBLP Ogbn-arxiv
Benchmarks: Cora CiteSeer PubMed DBLP Ogbn-arxiv
Metrics: node classification accuracy
Baselines: GCond SGDD SFGC GEOM GCDM RobGC GCond(+S) GCond(+J) GCond(+K)
Builds on: GCond MedianGCN PRBCD Ollivier-Ricci curvature
Closest papers by meaning
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.90)
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.88)
- Enhancing Graph Classification Robustness with Singular Pooling (NeurIPS 2025 · similarity 0.88)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.88)
- Robust Graph Neural Networks via Unbiased Aggregation (NeurIPS 2024 · similarity 0.87)
- Refine then Classify: Robust Graph Neural Networks with Reliable Neighborhood Contrastive Refinement (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.