Robust Graph Condensation via Classification Complexity Mitigation
Jiayi Luo, Qingyun Sun, Beining Yang, Haonan Yuan, Xingcheng Fu, Yanbiao Ma, Jianxin Li, Philip S. Yu · 2025
Read Robust Graph Condensation via Classification Complexity Mitigation by Jiayi Luo, Qingyun Sun, Beining Yang, Haonan Yuan, Xingcheng Fu, Yanbiao Ma, Jianxin Li, Philip S. Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26451.txt.
Introduction
Jiayi Luo, with seven co-authors, makes graph condensation safer under attack. Graph condensation shrinks a large network into a small fake one that still trains models well. When the source network is poisoned, though, condensed results can fall apart, and standard defences help only a little.
Luo and the team trace the weakness to the process itself: condensation lowers the complexity of sorting nodes into classes, and attacks exploit that. Their framework, MRGC, guides the fake graph to sit on a smooth, low-dimensional surface with little class mix-up. Three learning modules enforce that shape. Across many attack settings, MRGC held up better than prior methods. The work matters for anyone who must shrink network data that may not be clean.
Catalog record
| CREATOR | Jiayi Luo, Qingyun Sun, Beining Yang, Haonan Yuan, Xingcheng Fu, Yanbiao Ma, Jianxin Li, Philip S. Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26451
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust Graph Condensation via Classification Complexity Mitigation Jiayi Luo, Qingyun Sun, Beining Yang, Haonan Yuan, Xingcheng Fu, Yanbiao Ma, Jianxin Li, Philip S. Yu Abstract Graph condensation (GC) has gained significant attention for its ability to synthesize smaller yet informative graphs. However, existing studies often overlook the robustness of GC in scenarios where the original graph is corrupted. In such cases, we observe that the performance of GC deteriorates significantly, while existing robust graph learning technologies offer only limited effectiveness. Through both empirical investigation and theoretical analysis, we reveal that GC is inherently an intrinsic-dimension-reducing process, synthesizing a condensed graph with lower classification complexity. Although this property is critical for effective GC performance, it remains highly vulnerable to adversarial perturbations. To tackle this vulnerability and improve GC robustness, we adopt the geometry perspective of graph data manifold and propose a novel M anifold-constrained R obust G raph C ondensation framework named MRGC . Specifically, we introduce three graph data manifold learning modules that guide the condensed graph to lie within a smooth, low-dimensional manifold with minimal class ambiguity, thereby preserving the classification complexity reduction capability of GC and ensuring robust performance under universal adversarial attacks. Extensive experiments demonstrate the robustness of MRGC across diverse attack scenarios. 1 Introduction Recently, Graph Condensation (GC) gao2024graph ; xu2024survey has emerged as a promising approach to enhance the training efficiency of Graph Neural Networks (GNNs) by condensing large graphs into smaller ones. These smaller yet highly informative synthesized graphs enable GNNs trained on them to achieve performance comparable to models trained on larger original graphs gong2024gc4nc ; liu2024gcondenser ; sun2024gc . This has facilitated the adoption of GC in areas like neural architecture search jin2021graph and graph continual learning liu2024puma . However, the quality of the condensed graph largely depends on the original graph while existing GC methods assume a clean original graph. As shown in Figure 1(a) , when the original graph is attacked, the quality of the condensed graph deteriorates, adversely impacting the applications of GC in real-world scenarios where noise and attackers are prevalent sun2022adversarial . Nevertheless, GC robustness remains largely unexplored. RobGC gao2024robgc is the first attempt to tackle this issue. While RobGC effectively addresses structure attacks, its dependence on structure learning and label propagation limits its defense against feature and label attacks gao2024graph . Benchmark gong2024gc4nc also reveals that GC is vulnerable to feature attacks. Three key questions about GC robustness remain unsolved: ( Q1 ) Can existing robust graph learning techniques improve GC robustness? ( Q2 ) What key property of GC is disrupted by attacks, causing the performance degradation, and can it be theoretically understood? ( Q3 ) How to design a defense strategy to counter universal attacks in GC? Answer to Q1 : Given that most current training-based GC methods utilize GNN as their backbone gong2024gc4nc , one intuitive approach to enhance GC robustness is to leverage existing robust GNN technologies. To investigate this possibility, we conduct two toy cases using GCond jin2021graph as a representative GC method. First, we integrate MedianGCN chen2021understanding (a classic robust GNN dai2024comprehensive ; zhang2021subgraph ) as the GC backbone. Second, we train MedianGCN on the condensed graph synthesized by the standard GCond. As shown in Fig. 1(b) , both strategies fail to work effectively, with even worse performance than the standard GC method. This may be because most existing robust GNNs enhance robustness using attention-like mechanisms dai2024comprehensive , which have been shown to perform poorly even in clean GC scenarios gong2024gc4nc ; sun2024gc ; liu2024gcondenser . (Results with more robust GNNs are in Appendix C ). This result suggests that existing robust GNN techniques may fail to enhance GC robustness, highlighting the need for an innovative solution. (a) GCond under attacks. (b) GC with robust GNN. (c) Classification complexity evaluation. Figure 1: Examples in Cora chen2021understanding dataset (ratio=2.6%): (a) GCond performance under attacks. (b) The robust GNN is adapted for GC under attacks, with (+M) indicating MedianGCN is the GC backbone and (*M) denoting its use in the condensed graph. (c) Classification complexity evaluation, where (*) means the original graph is under attack during GC. Details can be found in Appendix C . Answer to Q2 : Since existing GC research primarily focuses on the classification task gao2024graph , we examine how attacks affect the classification-related properties of GC. Inspired by the classification complexity theory ho2002complexity ; lorena2019complex ; li2008introduction , which investigates classification problems through the geometric properties of classes with the three key factors are intrinsic dimension, boundary complexity, and class ambiguity lorena2019complex , we explore how the GC process influences the classification complexity of graphs and its behavior under attack through the lens of this theory. To evaluate the classification complexity of graphs during the GC process, we employ three widely used metrics lorena2019complex : Intrinsic Dimension, Fisher’s Discriminant Ratio, and the Fraction of Hyperspheres Covering Data (Details are in Appendix C ). As shown in Figure 1(c) , all metrics decrease after GC with an average reduction of 89.25%, indicating that GC will reduce the classification complexity. However, when adversarial attacks occur, we observe an average increase of 547.54% across all metrics in the condensed graph. This reveals an interesting insight: while GC reduces the classification complexity, adversarial perturbations counteract this classification-complexity-reducing property. Answer to Q3 : Based on our analysis, designing a defense strategy to preserve the key property of GC under universal attacks to improve robustness presents three challenges: How to (1) reduce the intrinsic dimension, (2) minimize the complexity of class boundaries, and (3) resolve class ambiguity to mitigate the increasing classification complexity in the condensed graph under attacks? To address these, we explore GC robustness from the geometric perspective of graph data manifolds and propose a novel M anifold-constrained R obust G raph C ondensation framework, named MRGC . To maintain a low intrinsic dimension of the condensed graph (Challenge 1) , we designed an Intrinsic Dimension Manifold Regularization Module to constrain the condensed graph in a low-dimensional manifold. To reduce the complexity of class boundaries (Challenge 2) , we introduce a Curvature-Aware Manifold Smoothing Module to smooth the class manifold in the condensed graph, thereby simplifying the class boundaries. To relieve class ambiguity (Challenge 3) , we develop a Class-Wise Manifold Decoupling Module that mitigates potential class bias by minimizing the overlap between class manifolds. Our main contributions are summarized as follows: • We empirically and theoretically demonstrate that GC inherently reduces the classification complexity of graphs, a property vulnerable to adversarial attacks targeting the original graph and remains unprotected by existing robust graph learning techniques. • We adopt a geometric perspective of graph data manifold and propose MRGC to enhance GC robustness by protecting its classification complexity reduction property. • To the best of our knowledge, we present the first study of the robustness of GC under conditions where features, structure, and labels can all be corrupted. Extensive experiments demonstrate the superior robustness of our proposed MRGC . 2 Related Work Graph Condensation. GC significantly enhances the training efficiency and scalability of GNNs jin2021graph . Existing GC methods can be categorized into four types sun2024gc ; liu2024gcondenser : (1) Gradient Matching: GCond jin2021graph serves as a representative framework for these