Robust Graph Condensation via Classification Complexity Mitigation
Authors: Jiayi Luo
Qingyun Sun
Beining Yang
Haonan Yuan
Xingcheng Fu
Yanbiao Ma
Jianxin Li
Philip S. Yu
Venue: NeurIPS 2025 spotlight ()
Keywords: Graph Dataset Condensation
Robust Graph Learning
Primary area: deep_learning

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.

Robust Graph Condensation via Classification Complexity Mitigation
Jiay Luo', Qingyun Sun', Beining Yang?,
Haonan Yuan', Xingcheng Fu', Yanbiao Ma², Jianxin Li"; Philip S. Yu²
SKLCCSE, School of Computer Science and Engineering, Beihang University
21 .Laboratory for Foundations of Computer Science, University of Edinburgh
$ Key Lab of Education Blockchain and Intelligent Technology. Guangxi Normal University *Gaoling School of Artificial Intelligence, Renmin University of China DDeparmeent of Computer Science, University of Illinois, Chicago edu. cn
{luojy sunqy, biiaanmmnijjxeeeee b. yang-320smm 3200mm..mm.mm ed.ac. uk, fuxc@gxnu. edu. cn, yn..bmm199980uu edu. en, ecy.psuuuuc.ed
Abstract
Graph condensation (GC) has gained significant attention for its ability to synthe- size 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 process, synthesizing 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 novel Manifold-coossrrinne Robust Graph Condensation framework named MRGC. Specifically, we introduce three graph data manifold learning modules that guide the condensed graph lie within a smooth, low-dimensional manifold with minimal class ambiguity, thereby pre- serving 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.
Introduction
17 61 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
Recently, Graph Condensation (GC)
performance comparable to models trained on larger original graphs 20 [54]. This has facilitated
the adoption of GC in areas like neural architecture search 33 and graph continual learning 43
However, the quality of the condensed graph largely depends the original graph while existing GC methods assume a clean original graph. As shown in Figure [(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 [53). Nevertheless, GC robustness remains largely unexplored. RobGC [16] is the first attempt 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 [77.. Benchmark [20] also reveals that GC is
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

40-
Original Graph
Cundansed Gruph
Cundanudd Geaple")
044
Asciracy
70-
Accunayy (N)
10-
0.4
1.0
6:23
8.99
Alssck(p=f)
022
3.19
2954
80-
Feorure AT
2.24
Label AToddips
0.00
100p
0.0
0.9
19%
10% 10% 30% 4p% 5p%
GCard Goand
Grand
MRCCC (oum)
Intracio Dimoncion
Ficbork Diceiminate Ratio
Fradtin of Hlyperphere
Persutecion
(0M)
(MM)
Cootring Dats
(a) GCond under attacks.
(b) GC with robust GNN.
(c) Classification complexity evaluation.
Examples in Cora g dataset (ratio=2.6%% (a) GCond performance under attacks. (b) The robust GNN is adapted for GC under attacks, with (+M) indicating MedianGGN is the GC backbone and (*M) denoting its use in the condensed graph. (c) Classification complexity evaluation, where (*)
Figure 1:
means the original graph is under attack during GC. Details can be found in Appendix
vulnerable to feature attacks. Three key questions about GC robustness remain unsolved: (QT) 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 defense strategy to counter universal attacks in GC?
Answer to Q1: Given that most current training- based GC methods utilize GNN their backbone 20 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 (33) as a representative GC method. First, we integrate MedianGCN 8 (a classic robust GNN [O (7)) as the GC backbone. Second, we train MedianGCN on the condensed graph synthesized by the standard GCond. As shown in Fig. [(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 [10], which have been shown to perform poorly even in clean GC scenarios [20] [14 (Results with more robust GNNs are Appendix C.. This result suggests that existing robust GNN techniques may fail to enhance GC robustness, highlighting the need for an innovative solution.
Answer Q2: Since existing GC research primarily focuses on the classification task 117, examine how attacks affect the classification-relteed properties of GC. Inspired by the classification complexity theory (25] 44 33), which investigates classification problems through the geometric properties of classes with the three key factors are intrinsic dimension, boundary complexity, and class ambiguity 44, 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 44 Intrinsic Dimension, Fisher's 's Discriminant Ratio, and the Fraction of Hyperspheres Covering Data (Details are in Appendix C As shown in Figure [(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
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 Manifold-constranned Robust Graph Condensation framework, named MRGC. To maintain a low intrinsic dimension of the condensed graph (Challenge /), we designed an Intrinsic Dimension Manifold Regularization Module to constrain the condensed graph in a oin-dimesiional manifold. To reduce the complexity of class boundaries (Challenge 2), we introduce Curvature-ANwy 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 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 complex- ity 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
33
Existing GC methods can be categorized into four types [54] 41]: (1) Gradient Matching: GCond [3
serves as a representative framework for these methods, optimizing the condensed graph by minimiz- ing gradient discrepancies between GNNs trained the original and condensed graphs [2 65 15
(2) Trajectory Matching: SFGC 774 and GEOM 72 condense graphs by aligning the training trajectories of parameter distributions expert GNNs. (3) Distribution Matching: These methods
minimize the distributional difference between the original and the condensed graphs [39] (3] (4)
Others: Various methods, such as Kernel Ridge Regression (63 64 and Computation Tree 224 23
are also used for GC. However, few studies have explored GC robustness under attack.
Robust Graph Neural Network. Lines of studies have been dedicated enhancing GNN robustness: (I) Preprocessing: These methods leverage certain shared properties of real-world graphs to clean
perturbed ones before training [12 58 30 45). (2) Modeling: New GNN architectures are proposed
to mitigate the impact of attacks dynamically during training [8 31 19 (68) (3) Training: They
don't modify the GNN architecture but training strategies like adversarial training [22 group
training 229 67
to reduce GNN sensitivity.
Robust Graph Condensation. With GC recognized as promising technique [1 61. RobGC [16] is the first to investigate GC robustness and propose a defense against structure attacks. Benchmark 20) reveals that feature noise poses great threats in GC. However, comprehensive understanding of GC robustness and a universal defense against structure, feature, and label attacks remains absent.
3 Method
Problem Formulation. Consider a poisoned graph g-(X; Á,Y) with n nodes, where X denotes node features, A denotes adjacency matrix, and Y denotes node labels. The goal is to synthesize compact graph G' X', A', Y' with n' & n nodes, in a way that resilient to adversarial attacks, so that GNNs trained on g' can still perform well on test nodes in the original graph ğ.
min Eg [ (G'), Pres)),
where g (g') denotes the GNN trained on G', and Lusk denotes the task mesk-specific loss.
Framework. As depicted in Figure mitigate the increase in classification complexity induced by attacks and enhance GC robustness from three complementary perspectives: Reduce the intrinsic dimension (Section 3.7 We estimate and constrain the intrinsic dimension of the condensed graph during the GC process. @ Minimize the complexity of class boundaries (Section 3.2). By regularizing the curvature of class manifolds in the condensed graph, we achieve smoother geometric decision boundaries between classes, @ Resolve class ambiguity (Section 3.3). We minimize the overlapping volume between class manifolds to reduce classification ambiguity and enhance class separability.
3.1 Intrinsic Dimension Manifold Regularization
empirically observe that adversarial attacks will significantly increase the intrinsic dimension of the condensed graph. Here, we first theoretically analyze the relationship between the intrinsic dimension and the graph condensation process and then propose a differentiable method to estimate the intrinsic dimension of the condensed graph. Finally, we impose constraints on the intrinsic dimension throughout the entire condensing process.
From Figure I(c)
Intrinsic dimension is the minimum number of coordinates required to describe the data 2] Fol- lowing the widely adopted manifold assumption which states that high-dimensional data lie

---

Original Gruph (Attacked)
Antakk
Condensed Graph
Feut. & Strw. Label Atuck
Charsificttion Complexity
Graph Condensation
Ciasificaatin Complexity L
intrinsic dimension
class boundary complexity
class ambiguity
[MG
I (
Smuttrr
Dlyh Kingle Soat-wilt
dlick silJl
slobal muaihei
A'
~
Eave
Eop
Sq. Spr(
Repesmakk Kwily
Smunth Loe 1R10)
Intrinsie Dimension Manifold Reg.
CurvatureAAare Manifold Smoothing
Clase-Wise Manifold Decoupling
The framework of MRGC, which introduces three complementary graph manifold learning modules into the GC process: constraining the intrinsic dimension, smoothing classification bound- aries via manifold curvature limits, and encouraging class manifold decoupling. These modules address the increase in classification complexity within the condensed graph induced by attacks.
Figure 2:
lower-dimensional manifold, the intrinsic dimension refers to the dimensionality of this underlying manifold 3 [66. Here, we begin by presenting the following Theorem T
Theorem 1. Given a graph G with nodes, let g' with n' nodes denote the much smaller synthetic graph generated through graph condensation, which is comparable to G in terms of training GNNs. We have the following:
ID(g") ID(G),
where ID(+) denotes the intrinsic dimension of graph data.
Theorem indicates that graph condensation is a graph intrinsic dimension decreasing process, synthesizing a condensed graph that lies in a data manifold with lower dimension. The proof can be found in Appendix A Building on this, we further propose the following Theorem 2
Theorem 2. Building on Theorem 7 let G', denotes the synthetic graph generated through graph condensation, where the original graph G. under attack. Then we have:
ID(G") WDG.)..
Theorem 2 indicates that the adversarial attack poses increasing intrinsic dimension in the con- densed graph. Details the proof are provided Appendix
Through the theoretical analysis in Theorem | and Theorem 2 protecting the key intrinsic dimension decreasing characteristic of GC is important for improving its robustness against attacks. In this work, we propose a novel approach to calculate the dimension of the graph manifold where the condensed graph resides and use as a regularization term to constrain the intrinsic dimension the condensed graph. Specifically, we use the embedding vectors after two rounds of message passing, Z' = (A')2X', as the node representation, which incorporates both feature and structure information. Let MMg") denote the manifold on which the condensed graph g' lies, embedded in TR.... Then,
Iz Ya'n represents the discrete set of observations sampled from M(g'). The intrinsic dimension of g' is defined the dimension of M(g') under the low-dimension manifold assumption [3] denoted as dim(M(g)). According to 49) dim(M(G')) is given by:
dim(M(('))
Σ
2ml M (
Here, V (z') represents the gradient of coordinate function a; on M(G') at point z', where (x(z') = z/. Directly solving Eq. (4) requires constructing the explicit function of MMG'), which is challenging to derive from the discrete observations [Z - In this work, adopt the Laplacian

---

approximation 69 to solve Eq.
4
/ M()))
VV (('))assz'))l | (az);
(5)
where (2,) exp 11 (a. (a, is the graph Laplacian operator with 2ca
hyperparameter e, and [M( is the volume of the manifold. Based on the geometric interpretation of singular values [Ι. the volume |M((')| is proportional to the product of the singular values {ar);== of node representation matrix Z' i.e., [M(g')| I os. The covariance matrix of Z' is defined Σ'2 (Z') Z'. By the relationship between singular values and eigenvalues, the eigenvalues of Σz (denoted by (Ar)(=1) related the singular values of Z X of Thus, the volume [M(g") can be expressed as:
IMM(')) & ddel(Ez: +I)
(6)
where is to ensure that the covariance matrix Σz is positive definite, and det(-) denotes the determinant operation. Finally, the intrinsic dimension manifold regularization loss during graph condensation is defined as:
Ldim /ett(Ez I)-
Σ
Sz (os)-
3.2 Curvature-Aware Manifold Smoothing
The complexity of class boundaries, determined by the geometry of class manifolds, a key factor in classification difficulty [44). Attacks can increase this complexity in condensed graphs, weakening GC robustness. To quantify it, we measure the Gaussian curvature [5I], where larger absolute values indicate more intricate boundaries. Each node's curvature is computed, and the weighted sum of absolute values used as regularization term. Weights reflect each node's influence in message passing and are derived from Ricci curvature [56]
Let M(')) denote the class-c manifold containing nodes with label c, represented by ZZ Y = c). Our goal is to compute the Gaussian curvature of each node on M(G''). We estimate the curvature Oo to its local neighborhood, where + is the surface parameter. The curvature is obtained as the determinant of the Hessian fe ( [47]. Specifically, we project neighbors of node i onto its tangent space, and use these projections inputs fit the hypersurface. The targets are the corresponding projections onto the normal vector at node i, capturing how neighbors deviate from the tangent space and thus reflecting local manifold geometry.
at node by fitting a quadratic hypersurface fo)
We estimate the normal vector u, node i using its k-nearest neighbors in Euclidean space
[Z) -c)-c,,TTo TT)) subject to u, 1,
min
(8)
where Z denotes the node representation of j-th neighborhood and c, = Σイ Z is the center of l neighborhoods. To solve Eq. (8) we define the Lagrangian function:
Llu A) = Σ - X(u, u 1),
(9)
1=1
Define Y Z; - c,1 Solving the Karush- Karush-Kuhn- Tucker conditions for Eq. (9) shows that the normal vector u; corresponds to the eigenvector associated with the smallest eigenvalue of Y Y: details are provided in Appendix A Let (Ai,..., .,,) and (E.....,Ea, Exr be the eigenvalues and corresponding eigenvectors of Y Y, sorted in descending order. Since T Y is symmetric and positive semidefinite, have A dimensional tangent space at node is spanned by
> d 0 and E. 0 for all a b. The (d' 1)-
Ed-1), and the projections of i's k neighbors onto this space form the matrix O (d defined as:
O, [01, 02 ....... oF
(10)
5

---

where each oj E R corresponds to the projection of (Z) -c;) onto the tangent space:
j ZZ) c4) 2 (Z) cc) -Ed-11l
(1I)
Then we propose the following proposition:
Proposition 1. By fitting the quadratic hypersurface [e(o) via mine Ej=(bor Go, - -13),, where 1,-(Z,-Z -.)).u. represents the projection along the normal vector, the Gaussian curvature of the class manifold at node is given by ((())2det(Maa(( (aaat(QQp))))))) (p)). Here QER (1a(d"11""x(""a" xd'-1) is a fourth-order tensor expressed as matrix with entries Qa,becd = Σÿ= Oja0sb0je0jh and p (R((d- is
second-order tensor with entries Pa,s = =E== tj The operator Mat(-) reshapes Q Q into an (d' 1) x (d' - 1) matrix, and det(-) denotes the determinant operation.
Proposition provides a closed-form expression for the Gaussian curvature at node i, with the proof deferred Appendix [ However, averaging curvature across all nodes ignores the varying structural roles of individual nodes. In particular, nodes at community boundaries, which serve as bridges for inter-community message passing, have a greater influence on the geometric complexity of class boundaries. To account for this, we reweight each node's 's Gaussian curvature using Ricci curvature [56], edge-based metric that reflects structural connectivity. Lower Ricci curvature values on edges indicate stronger bridging roles, highlighting the corresponding node's 's importance. We adopt the Ollivier definition [48), where the Ricci curvature between nodes (ž.j) is defined as j) 1 - W(m, m ) (i, where W(:-) is the Wasserstein distance of order 1, D(:,)) denotes the shortest-path distance, and m represents the mass distribution, which is defined as:
a,
if = i, if E N()), otherwise,
()) m
m
=
(1 a)
Ay ()
(12)
0,
where N(i) denotes the neighbors of node i, deg(t) = EjeN() Ag, and a is the smoothing parameter and is typically set to 0.5. The strategy for measuring the Ricci curvature of node is to average the curvatures of its connected edges (9]. expressed as k(i) A. Σjen(s) k(i.j). Finally, the Gaussian curvature regularization term, denoted Leurs is defined as:
deg(e)
Leur
Σ Σ Norm(-x(i)) (K()).
(13)
VEV.
where Norm(.) denotes min-max normalization to [0, 1]. and Ve denotes nodes belonging to class c.
3.3 Wise Manifold Decoupling
Class ambiguity is the third critical factor that contributes to the classification complexity 25 44 To preserve the classification complexity reduction property of GC and improve its robustness, it is essential to avoid class ambiguity in the condensed graph, ensuring that the classes remain well-separated with clear decision boundaries. To avoid the class ambiguity arising condensed graphs under attacks, we propose measuring the overlap between class manifolds by calculating the difference between the sum of the volumes of individual class manifolds and the volume of the entire data manifold. Minimizing this difference defines our class-wise manifold decoupling objective, which can be expressed as follows:
Cxep (IIMIC)-MMO)))
(14)
where IM()) represents the volume of class-c manifold. This approach facilitates sufficient decou- pling between class manifolds to mitigate class ambiguity, thereby effectively reducing classification complexity in the condensed graph.
Training Pipeline. We initialize node features in the condensed graph by randomly selecting non- outlier nodes from the original graph, where outliers are identified based on the Euclidean distances of their features. Other initialization follows [33]. The training loss is as follows:
L Loc + aLam + 3Leur + 7Coop!
(15)

---

where Lae denotes the loss function of GC backbone, as MRGC is a soug-and--lay framework, and a, B, y are hyperparameters. Detailed pipeline are in Appendix [
Complexity Analysis. The Intrinsic Dimension Manifold Regularization Module requires ('''d' (d)))) operations. The Curvature-Aware Manifold Smoothing consists of two parts: Gaussian curva- ture computation, with complexity of ((n'6 + k)), and Ricci curvature computation, which requires ((n))²) operations. The Class-Wise Manifold Decoupling Module has complexity of ((c(d"))) where с denotes the number of classes, It is worth noting that the practical computa- tional cost remains efficient because n', the number of nodes in the condensed graph, small by design. Additionally, we apply PCA [[]] to reduce the feature dimensionality before computing the regularization terms, ensuring that d' stays manageable. Details are provided in Appendix D
4 Experiments
4.1 Experimental Settings
Datasets. We evaluate MRGC und the baselines on five real-world node classification datasets in a transductive setting: Cora (66], CiteSeer [66], PubMed [66], DBLP [6], and Ogbn-arxiv [27]. The data split configuration follows that of (0 for the Cora, CiteSeer, PubMed, and Ogbn-arxiv datasets. For the DBLP dataset, we use the settings from [28], performing random splits with 20 labeled nodes per class for training. 30 per class for validation, and the remaining nodes for testing.
Attacks. For the poisoning attacks, we use the widely adopted PRBCD 18 133 for structure perturbation. For feature perturbation, we randomly select nodes and assign their features by sampling from a normal distribution. For label perturbation, we randomly select a subset of nodes and uniformly flip their labels to other classes. The attack budget is set p percent of the total number of edges for structure perturbation and percent of the number of training nodes for feature and label perturbation.
Baselines. We evaluate MRGC against various baseline approaches, including five state-of-ther the--rt-rrt graph condensation methods: GCond [33, SGDD (65) SFGC 774), GEOM [72 and GCDM (37). We also compare with RobGC [16]. the first robust graph condensation method specifically designed for defending against structure attacks. Furthermore, following (16), enhance our comparison by incorporating three strong graph denoising techniques as preprocessing steps for GCond: GCond(+J), which removes edges based on Jaccard similarity; GCond(+S) which uses Singular Value Decom- position (SVD) for low-rank approximation to mitigate high-rank noise; and GCond(+K), which integrates k-nearest neighbors based on feature similarity into the original graph with k = 3.
Implement Details. In this experiment, we use GCond 33 as the backbone of MRGC, which is a maatiinttmatching based GC method. However, it is important to note that MRGC is compatible with most existing GC methods. The hyperparameters a, 3, and yy are determined through a grid be found in Appendix [ and our
search from 1e-3 to le2 with logarithmic steps of 5. Details code. We repeat all the experiments five times and report the average performance and standard deviation. All the experiments are conducted in single NVIDIA GeForce RTX 3090 24GB GPU.
4.2 Robustness Across Varying Condensation Ratios
In this section, evaluate the impact of different condensation ratios on the robustness of MRGC across the five aforementioned datasets, using three distinct condensation ratios while keeping the attack budgets invariant. The attack budgets for structure, feature, and label attacks set to 1%, 10%, and 20% for the Cora, CiteSeer, and Ogbn-Arxiv datasets, and 0. %, 10%, and 20% for the PubMed and DBLP datasets. The results are presented in Table T
From the results in Table 1 we have the following three observations: (1) Across all the datasets and condensation ratios except for Ogbn-arxiv at ratios of 0.05% and 0.50%, MRGC achieves the best performance under poisoning attacks. This highlights the robustness of our proposed method in mitigating the negative impact of attacks on the graph condensation process. (2) On the Ogbn-arxiv dataset at condensation ratios of 0.25% and 0.50%, GEOM demonstrates superior performance. This is because trajectory- matching GC methods, such as SFGC and GEOM, achieve significantly
majectory-matching
Our code is available at ht/tttts///tthubb www hotps///////ggntStac///cc
7

---

better results on the clean Ogbn-Arxiv dataset than gradient- gradient-matching matching GC methods Consequently, despite performance degradation under attack, they retain a relative advantage due to their initially superior performance on the clean dataset. However, SFGC and GEOM exhibit poor robustness on other datasets. (3) Denoising the graph during the preprocessing stage before GC has limited effectiveness, as these methods assume that the node features and labels are clean.
4 20
54
4.3 Robustness Across Varying Attack Budgets
To evaluate the robustness of MRGC under varying attack budgets, we fix the condensation ratio to the lowest value for each dataset and adjust the attack budgets for structure, feature, and label attacks independently, while ensuring that the other attack budgets remain consistent with the settings outlined in Section 4.2 The experiments are conducted on the Cora, CiteSeer, PubMed, and DBLP datasets, and the results are shown in [
As shown in Table 2 (I) MRGC consistently outperforms all baselines across all datasets and attack budget variations. For example, on the CiteSeer dataset, MRGC achieves improvements of approximately 3.98% and 4.75% over the rumner-up with label perturbation ratios of 30% and 40%, respectively. This highlights the robustness of MR GC against varying attack intensities. (2) The robustness of MRGC remains stable regardless of the type of attack, effectively defending against structure, feature, and label perturbations. In contrast, RobGC performs well under the structure attacks but shows performance degradation the intensity of feature and label attacks increases. (3) Gradient matching- based GC methods generally exhibit better robustness compared to trajectory matching and distribution matching GC methods.
4.4 Ablation Study
To verify the effectiveness of each component, we compare different ablated versions of MRGC on Cora and CiteSeer datasets with the lowest condensation ratio: (1) MRGC (w/o ID), (2) MRGC (wlo C), and (3) MRGC (w/o D), which respectively remove the Intrinsic Dimension Manifold Regular- ization, Curvature-Awart Aware Manifold Smoothing, and Class- Wise Manifold Decoupling modules. As the results are shown in Figure 3 all three modules contribute to the performance of MRGC, with the Intrinsic Dimension Manifold Regularization module providing the greatest improvement.
4.5 Classification Complexity Study
Based on analysis in this work, graph condensation acts as a process that reduces classification complexity, whereas attacks disrupt this property, leading to an increase in the classification complex- ity of the condensed graph. This study aims verify the ability of our proposed MRGC to mitigate this negative impact. As introduced in Section]] [ we measure classification complexity using three
Table 1: Performance comparison under different condensation ratios when the training graph is corrupted. S. F, and I. represent the attack budgets for structure, feature, and label, respectively. The best results are highlighted bold, while the runner-up results are underlined. OOM denotes out-of-memory (24GB), and OOT denotes out-of-time (24 hours)
Dataset
(S.FL)
Ratio
GCond
SGDD
SFGC
GEOM
GCDM
GCond (+S)
GCond (+))
GCond (+K)
RobGC
MRGC
1.30%
70.6921.79
98.2880.9
39.70
40.43a3.10
45,91
68.11
69.29.04s 71.79.0.51
71.6021.64
77.43=9.32
Cora
2.60%
71.39aax2
68.48 68.48a062
50.
10.442
54.00s4.00
49.89.611
68.8221.99
69 99.6621.6
72.00e0.75
72. 19
76.72s0.76
(1.10,20)
5.20%
71.07-1.42
68.63+1.44
68.26-097
70.03+0:4
51,37=222
11.92-2.19
70.43+1.79
71.75-0.0
72.51-1.42
74.40h..29
0.90%
60.77=200
47.136075
36.23-106
36.70s1.95
46.72s4.99
58.49:5.22
60, 11
58.62=0.37
59, 59.
65.12
CiteSeer
1.80%
61.03a1.28
56.
66.12a035
48.6921.44
47.1741.51
46.01a1.74
60.12-3.5
59.8022.5
60.58a1.97
61.77=2.45
63.87=1.04
(1.10,20)
3.60%
61.08e1.70
52.11
67.
60.67=0.15
47.03e1.35
61.15=275
61.88e273
61.91-0.76
665 62.50ml.65
64.44s9.97
0.08%
20.81=074
48.75a001
47.26-274
50.17s2.52
63.81a1.57
70.00=1.01
66.48s2.13
69.27:0.14
74.85
(0.1.10.20)
PubMed
0.30%
0.15%
71.59x1.77
69.02-0.62
49.08-0.0
51.31a3.14
64,58-079
63.18.0.4
64.93e1.12
62.90-1.11
58,90+4477
61.75e1.19
0OM
70.31=2.5
70.33 68.58e0.42
67.28-1.74
71.59+1.62
71.71=077
.62
73.04....26
73.11.0..7
0.11% 62.50aa.441
51.0623.63
41.71a1.27
49.71a1.99
54.78a7.74
$7.13 58.53a1.46
62.66681.46
65.1
(0.1,10,20)
DBLP
0.45%
0.23% 61,37=1.75
62.73e1.20
44.54+1.77
53.45
61.60+0.9
46.95=1.91
60.31.0.65
$3.25e1
93
54.31=236
52.87+1.88
0OM
57.09a2.40 63.58-0.66
56, 76.7841..4 60.05=4.44
62.87e1.36
61. 61.65.0775
65.49
64.6tho..1
0.05%
58. 16-0.7
52.41+1.55
55.32-051
58.38-0.90
43.20+2.10 to
15 58.32-0.0
59.38=0.58
Ogbo-Arxiv
0.25%
59.82s0.99
57.81s077
58.37=2.52
66.49:9.45
52.59e1.47
0OM
60. 60.15=1.20
60.96.0.42
OoT
61.79 72
(1.10,20)
0.50%
60.50+a.11
61.04+066
62.94-1.57
67.56x8.22
54,91=2.54
59.05-043 12-12
63.32+0.34 34
8

---

Table 2: Performance under different attack budgets targeting the original graph. S.F, and L represent the attack budgets for structure, feature, and label, respectively. The best results are highlighted in bold, while the rumner-up results underlined. OOM denotes out-of-memory (24GB).
Dataset (Ratio%)
GCond
GCoad
GCond
Budget
GCond
SGDD
SPGC
GEOM
GCDM
RobGC
MRGC
(+S)
(+)
(+K)
5.5%
60.59
59.1621.59
52.52=3.39
35.03+144
49.51a2.15
60.71a6.1
61.90
61.96a233
62.03
65.57
8.10%
59.09+2.15
53.68+287
37.61+1.22
32.97+1.66
43.95+390
60.72-1.44
60.96+3.05
60,25+4:52
61 11.24-0.68
64.02-0015
Cor
E200%
69. 3613.00
68.5441.3
37.49:2.33
35. 31
49.55x2009
66.52a2.6
25..994
69.82:303
71.13-081
74.79
(1.30%)
F.30%
65 22,0.79
58,3421.25
37.13:2.42
35 50
45.1444.78
57.6922.36
60.06s2.09
69.3845.14
69.15=0.42
72.36:1.02
L.30%
64.9742.25
68.02a027
32.77a5.40
33.57at1
45.61a6.4
67.51
61.5991.81
67.474272
65, 25.99
70.47:1.19
I.40%%
57.49x1.33
61.97+2.19
28.33e0.05
32.63e0.56
37.02a1.77
57.50s0.40
57.29k2.16
62.56x1146
57.81=3.99
63.89si,94
5.5%
48.5142.90
44.24:2.82
35.65:077
35.30s166
42.32a1.58
58
19,28,0.80
49.21
47.92x2.34
48, 48.96-0.76
$2.91
S.10%
45.0611.72
42.90+1.7
33.8322.14
34.67a1.57
40.98s4.25
42.82a0.7
46.69a4.28
47,83
47, 47.2000060
52.72
CiteSeer
F.20%
58.26x1.00
53.5543337
39,56.4.34
43.50g3.31
40.65a4.12
53.03a2.73
59.32s2.57
57.82s4.41
61.0221.51
62.76210.56
(0.90%)
F.30%
54.45+2.85
48.81
37.00-187
42/20+4.21
39.73+2.00
55.50+675
59.49+2.72
55.56+289
56.31=2.50
62.41+1.30
L.30%
51.6943.85
52,42:3.25
45.36=1.89
40.93:0.68
39.424396
51.49.5.81
15
54.94s5.77
49,40=1.41
59.33+2.35
L.40%
49.25x1.20
47.63+1.59
31,91
33.03a1.46
66
51.38a6.66
12.31a
54.45a2.18
48.83a5.45
59.20s1.26
5.0.5%
56.54x1.99
43.18
54,21=3.45
44.47a1.35
46.77a3.23
59.02+1.17
58.55+1.26
57.41-0.22
60.57a0..23
5.1.0%
55.21+3.89
43.55+1.18
46.13-2997
44.07-0:40
48,38+4 46
58.09+0.36
58.28+0-41
58.72-1.23
58.96-0.7
Puh
F.00%
71. 10
50.85.5.29
29
19.112
44 13.33
59, 39.4846667
68. 53.2536.26
67.
72. 37.78.2.59
73.43
(0.08%)
F.30%
67.20 07.2640.74
47.72x1.64
65,70.0.0
60.70at.13
51.20a6.06
00M
63.8811.92
18.2.1
66.62a1.73
68.8620.34
L.30%
68. 68.04a1.83
48.62a4.49
48.6361.22
49.00e1.74
40.70a236
71.76,2.26
66,8343397
65, 65.79:2.77
73.18
1.40%
56. 14x2.64
46.22+1.09
43.14=3.14
45.30=1.00
43.72+471
58.24e1.00
49.96+2.79
58.03-1.93
58.28
5.0.5%
62.31
57.28+184
44.87=5.18
46. 19.199
47.7543.86
55.44s3.06
38.10
62.88=2.79
65.36=188
5.1.0%
61 26..66.
58.21+2.92
45.13-3.62
46.43+0.71
43.45+6 30
54.44+2.06
58.09+5.10
61 19-8111
64.49.0.27
DRLP
F.0%%
60.4142.14
62.0340.53
59.69.1.06
57.69.0:23
29.2884330
56.81a1.49
60.3654.63
60.39_1.37
63.42s1.86
(0.11%)
E.30%
60.45a1.02
55.1245.05
58. 78.166
$6.4924126
45.65:2.55
0OM
$5.1441..4
61.77a149
61.51at.31
63.68
L.30%
70.34
64.52a4.15
48.84=181
50.22s0::4
$3.87+1
61.77s1.50
69.1621.10
69.39.1.69
73.39t
1.40%
68. 30+1.15
63,76+1.29
58.63-2.11
51.58+2.97
37.73-647
60.52+1.65
50.34-185
70.66-260
73.12+0.84
MRGC
MRGC (wlo C)
AAMI
Origin
GCond
GCond (*)
(RGC(*)
(RGC
MRGC (wil
15
0.6
1.2
80
Accuracy (%)
25 2527
12-
1114
8:0
194
8.50
111
0.4
0.8
70
6-
0.2
0.4
64.23
60
0.0
0.0
Cora
CiteSocr
Cora
CiteSeer
Cora
CiteSeer
Cora
CiteSoer
Datasets
ID
FDR
FHC
Figure 3: Ablation study.
Figure 4: Classification complexity "** indicates attack).
80
80
80
24.64
76.76
77.43
76.67
77143
76.79
26
75.49
76/66
76.00
77.43
2201 27.50
75
75:33
71
2412
Accurscy (9
Accuracy (%)
Accuracy
70-
Cora
CiteSeer
70-
- Com
CiteScer
70-
Cora
CiteS
62
64183 62
12 66/22 63.10 6401 63/09
64
5405
62,33
62115
65
23
64
61.11
65
63
5c-1
160
5e0
lel
Sel
1c2
1o-2
5o-2
le-1
Sc-1
160
500
Se-2
le-1 So-1
1c0 Se0 lel
B
y
Figure 5: Hyperparameters study.
widely adopted metrics: Intrinsic Dimension (ID), Fisher's Discriminant Ratio (FDR), and Fraction of Hyperspheres Covering Data (FHC). Details of these metrics can be found in Appendix C The exper- iments are conducted in Cora (2.60%) and CiteSeer (1.80%) and the results are presented in Figure 4 We can see that our proposed MRGC effectively preserves the paassffcttoo-coopplxxiyyeeeideit property of GC, contributing to the achievement of robust graph condensation.

---

4.6 Hyperparameter Sensitivity Study
In this section, we explore the sensitivity of the hyperparameters a, B, and y for MRGC. In the experiments, we vary the values of a, 3, and y on the Cora and CiteSeer datasets with the lowest condensation ratio examine their impact on model performance. The results are shown Figure|4.5) As we can see, MR GC performs better when appropriate values are chosen for all hyperparameters, and wide range of hyperparameters can still yield satisfactory results.
Conclusion
In this work, explore GC's robustness against adversarial attacks on features, structures, and labels. Through empirical and theoretical analysis, we discover that GC functions as an intrinsic- dimension-reducing mechanism that creates graphs with lower classification complexity, while this property is susceptible to adversarial attacks. To protect this critical characteristic and improve the robustness of GC, adopt the geometric perspective of the graph data manifold and propose MRGC, a novel cunifold-constriing modules that constrain the intrinsic dimension, manifold curvature, and class manifold overlap of the property. Experiments
robust graph condensation framework. Specifically, we introduce three
condensed graph, thereby maintaining the wwt.ffaatttonoooopeexeeereeeeeee demonstrate MRGC's effectiveness against universal attacks. One limitation that focus node classification task, with the graph classification task left for our future work.
Acknowledgements
The corresponding author Jianxin Li. The authors of this paper are supported by the National Natural Science Foundation of China through grants No.62225202, and No.62302023. We owe sincere thanks to all authors for their valuable efforts and contributions.
10

---

References
Charu C Aggarwal, Lagerstrom-Fiie Aggarwal, and Lagerstrom-Fite. Linear algebra and optimization for machine learning, volume 156. Springer, 2020.
[2] Laurent Amsaleg, Oussama Chelly, Teddy Furon, Stéphane Girard, Michael E Houle, Ken-ichi Kawarabayashi, and Michael Nett. Estimating local intrinsic dimensionality. KDD, pages 29-38,
2015.
[3] Alessio Ansuini, Alessandro Laio, Jakob Macke, and Davide Zoccolan. Intrinsic dimension data representations in deep neural networks. NeurlPS, 32, 2019.
[4] Yasuhiko Asao and Yuichi Ike. Curvature of point clouds through principal component analysis. ArXiv, 2021.
[5] Robert Bennett. The intrinsic dimensionality of signal collections. IEEE Transactions on Information Theory, 15(5):517-225 1969.
[6] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. ArXiv, 2017.
[7] Paola Campadelli, Elena Casiraghi, Claudio Ceruti, and Alessandro Rozza. Intrinsic dimension estimation: Relevant techniques and benchmark framework. Mathematical Problems in Engineering, 2015(1);759567, 2015.
Liang Chen, Jintang Li, Qibiao Peng, Yang Liu, Zibin Zheng, and Carl Yang. Understanding structural vulnerability graph convolutional networks. ArXiv, 2021.
[9] Corinna Coupette, Sebastian Dalleiger, and Bastian Rieck. Ollivier-ricci curvature hypergraphs: unified framework. ArXiv, 2022.
[10] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjic Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. MIR, pages 1-51, 2024.
[11] George H Dunteman. Principal components analysis, volume 69. Sage, 1989.
[12] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalcxakis. All you need is low (rank) defending against adversarial attacks graphs. In WSDM, pages 169-177, 2020.
[13] Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. JAMS, 29(4):983-104) 2016
[14] Fuli Feng, Xiangnan He, Jie Tang. and Tat-Seng Chua. Graph adversarial training: Dynamically regulariz- ing based on graph structure. TKDE, 336))22493-2044, 2019.
[15] Jian Gao and Jianshe Wu. Multiple sparse graphs condensation. KBS, 278:1 179:4, 2023.
[16] Xinyi Gao, Hongzhi Yin, Tong Chen, Guanhua Ye, Wentao Zhang, and Bin Cui. Robge: Towards robust graph condensation. ArXiv, 2024.
[17] Xinyi Gao, Junliang Yu. Tong Chen, Guanhua Ye, Wentao Zhang, and Hongzhi Yin. Graph condensation: A survey, ArXiv, 2024.
[18] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügnerr, Aleksandar Bojchevski, and Stephan Günne- mann. Robustness of graph neural networks at scale, NeurlPS, 34:7637-7649, 2021.
[19] Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. NewrlPS, 33: 3272--1328, 2020.
[20] Shengbo Gong, Juntong Ni, Noveen Sachdeva, Carl Yang, and Wei Jin. Ge4ne: benchmark framework for graph condensation on node classification with new insights. ArXiv, 2024.
[21] Alexander N Gorban and Ivan Yu Tyukin. Blessing of dimensionality: mathematical foundations of the statistical physics of data. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(21 (7622118)220172233 2018.
[22] Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. NewrIPS, 36. 2024.
11

---

[23] Mridul Gupta, Samyak Jain, Vansh Ramani, Hariprasad Kodamana, and Sayan Ranu. Bonsai: Gradient-free graph distillation for node classification. ICLR, 2025.
[24] Mridul Gupta, Sahil Manchanda, Hariprasad Kodamana, and Sayan Ranu. Mirage: Model-agnostic graph distillation for graph classification, ArXiv, 2023.
[25] Tin Kam Ho and Mitra Basu. Complexity measures of supervised classification problems. TPAMI, 24(3):289-300 2002.
[26] Christian Horvat and Pascal Pfister. Estimating the intrinsic dimensionality using normalizing flows. In NeurlPS, pages 12236, 2022.
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets machine learning on graphs. NeurlPS, 33:221 18- 22133, 2020.
[28] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In KDD, pages 675-684, 2021.
[29] Yeonjun In. Kanghoon Yoon, Kibum Kim, Kijung Shin, and Chanyoung Park. Self- guided robust graph structure refinement. In WWW, pages 697-708 2024.
[30] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In WSDM, pages 148-156, 2021.
[31] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In KDD, pages 66-74, 2020.
[32] Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In KDD, pages 720-730, 2022.
[33] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. ArXiv, 2021.
[34] Elizaveta Levina and Peter Bickel. Maximum likelihood estimation of intrinsic dimension. NeurlPS, 17, 2004.
[35] Jintang Li, Jiaying Peng, Liang Chen, Zäbin Zheng, Tingting Liang, and Qing Ling, Spectral adversarial training for robust graph neural network. TKDE, 35(9):2440-95) -223,,,,--2 2022.
[36] Ming Li, Paul Vitányi, al. An introduction Kolmogorov complexity and its applications, volume 3. Springer, 2008
[37] Mengyang Liu, Shanchuan Li, Xinshi Chen, and Le Song. Graph condensation via receptive field distribution matching, ArXiv, 2022.
[38] Yang Liu, Deyu Bo, and Chuan Shi. Graph condensation via eigenbasis matching. ArXiv, 2023.
[39] Yanqing Liu, Jianyang Gu, Kai Wang, Zheng Zhu, Wei Jiang, and Yang You. Dream: Efficient dataset distillation by representative matching. In CVPR, pages 17314-17324, 2023.
[40] Yilun Liu, Ruihong Qiu, and Zi Huang. Cat: Balanced continual graph learning with graph condensation. In ICDM, pages 1157-1166 162. TEEE, 2023.
[41] Yilun Liu, Ruihong Qiu, and Zi Huang. Geondenser: Benchmarking graph condensation. ArXiv, 2024.
[42] Yilun Liu, Ruihong Qiu, Yanran Tang. Hongzhi Yin, and Zi Huang. Puma: Efficient continual graph learning with graph condensation. Arxiv, 2023.
[43] Yilun Liu, Ruihong Qiu, Yanran Tang. Hongzhi Yin, and Zi Huang. Puma: Efficient continual graph learning for node classification with graph condensation. TKDE, 2024.
[44] Ana C Lorena, Luís PF Garcia, Jens Lehmann, Marcilio CP Souto, and Tin Kam Ho. How complex is your classification problem? survey on measuring classification complexity. ACM Computing Surveys (CSUR), 5-33,, 2019.
[45] Jiayi Luo, Qingyun Sun, Haonan Yuan, Xingcheng Fu, and Jianxin Li. Robust graph learning against adversarial evasion attacks via prior-free diffusion baseed structure purification. In Proceedings of the ACM Web Conference 2025, pages 2110, 2025.
12

---

[46] Yanbiao Ma, Licheng Jiao, Fang Liu, Lingling Li, Wenping Ma. Shuyuan Yang. Xu Liu, and Puhua Chen. Unveiling and mitigating generalized biases of dans through the intrinsic dimensions of perceptual manifolds. Arxiv, 2024.
[47] Yanbiao Ma, Licheng Jiao, Fang Liu, Shuyuan Yang. Xu Liu, and Lingling Li. Curvature-balanced feature manifold learning for long-tailed classification. In CVPR, pages 15824-15835, 2023.
[48] Yann Ollivier. A survey of ricci curvature for metric spaces and markov chains. In Probubilistic approach to geometry, volume 57, pages 343-382. Mathematical Society of Japan, 2010.
[49] Stanley Osher, Zuoqiang Shi, and Wei Zhu. Low dimensional manifold model for image processing. SIIMS, 1069) 2017.
[50] Ian R Porteous. Geometric differentiaionn: for the intelligence of curves and surfaces. Cambridge University Press, 2001.
[51] Lisle Richard. Detection of zones of abnormal strains in structures using gaussian curvature analysis. AAPG bulletin, 78 78(12)1811-1819 1994.
[52] Yuichi Shiraishi and Kenji Fukumizu. Statistical approaches to combining binary classifiers for multi-class classification. Neurocomputing, 74(5)6800688, 2011.
[53] Lichao Sun, Yingtong Dou, Carl Yang. Kai Zhang. Ji Wang. S Yu Philip, Lifang He, and Bo Li. Adversarial attack and defense graph data: A survey. TKDE, 3593)77693-7711, 2022.
[54] Qingyun Sun, Ziying Chen, Beining Yang, Cheng Ji, Xingcheng Fu, Sheng Zhou, Hao Peng, Jianxin Li, and Philip S Yu. Ge-bench: An open and unified benchmark for graph condensation. ArXiv, 2024.
[55] Oliver Sutton, Qinghua Zhou, Alexander N Gorban, and Ivan Y Tyukin. Relative intrinsic dimensionality is intrinsic to learning. In International Conference on Artificial Neural Networks, pages 516-529. Springer. 2023.
[56] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. ArXiv, 2021.
[57] Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma, and Qing Li. Fast graph condensation with structure-based neural tangent kernel. In WWW, pages 4439-4448, 2024.
[58] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. ArXiv, 2019.
[59] Kerui Wu, Ka-Ho Chow, Wenqi Wei, and Lei Yu. Understanding the impact of graph reduction on adversarial robustness in graph neural networks. ArXiv, 2024.
[60] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. NeurIPS, 33:20437- 20448, 2020.
[61] Hongjia Xu, Liangliang Zhang, Yao Ma, Sheng Zhou, Zhuonan Zheng, and Bu Jiajun. A survey on graph condensation. ArXiv, 2024.
[62] Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui- Tsu Weng. Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. ArXiv, 2019.
[63] Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuann Chen, Mahashweta Das, Hao Yang. and Hanghang Tong. Kernel ridge regression-basee graph dataset distillation. In KDD, pages 2850-2861, 2023.
[64] Beining Yang, Qingyun Sun, Cheng Ji, Xingcheng Fu, and Jianxin Li. St-gcond: Self-supervised and transferable graph dataset condensation. 2025.
[65] Beining Yang. Kai Wang. Qingyun Sun, Cheng Ji, Xingcheng Fu, Hao Tang, Yang You, and Jianxin Li. Does graph distillation see like vision dataset counterpart? NeurIPS, 36:53201-53266 2023.
[66] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, pages 40-48. PMLR, 2016.
[67] Haonan Yuan, Qingyun Sun, Xingcheng Fu, Ziwei Zhang, Cheng Ji, Hao Peng, and Jianxin Li. Environment-awwae awar dynamic graph learning for out-of-distributin generalization. NeurIPS, 36, 2023.
13

---

[68] Haonan Yuan, Qingyun Sun, Zhaonan Wang. Xingcheng Fu, Cheng Ji, Yongjian Wang, Bo Jin, and Jianxin Li. DG-Mamba: Robust and efficient dynamic graph structure learning with selective state space models. In AAAI, volume 39, pages 22272-22280, 2025.
[69] Jin Zeng, Gene Cheung, Michael Ng. Jiahao Pang, and Cheng Yang. 3d point cloud denoising using graph laplacian regularization of low dimensional manifold model. IEEE TIP. 29:3474-3455 2019.
[70] Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. NewrIPS, 11666776668,,, 2021.
[71] Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. NeurIPS, 33:9263 9275, 2020.
[72] Yuchen Zhang, Tianle Zhang, Kai Wang, Ziyao Guo, Yuxuan Liang, Xavier Bresson, Wei Jin, and Yang You. Navigating complexity: Toward lossless graph condensation via expanding window matching. ArXiv, 2024.
[73] Kai Zhao, Qiyu Kang, Yang Song, Rui She, Sijie Wang, Wee Peng Tay. Adversarial robustness graph neural networks: A hamiltonian approach. NewrIPS, 36, 2024.
[74] Xin Zheng. Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. NeurIPS, 36, 2024.
[75] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In KDD, pages 1899-1401 2019.
14

---

A Proofs and Derivations
A.1 Proof of Theorem
Here, first restate the theorem:
Theorem 3. Given a graph 9 with nodes, let G' with n' nodes denote the much smaller synthetic graph generated through graph condensation, which is comparable to g in terms of training GNNs. We have the following:
ID(G') (D(
(16)
where (T) denotes the intrinsic dimension of graph data.
Proof. We begin by restating the corollary derived from [55], which provides bounds the probabil- ity of successfully learning a class Y. Specifically:
Corollary 1. With the training sample {xx x) the probability of successfully learning the class X bounded by:
P(g(z)= = 1
(17)
2ID(X)+1*
where k represents the number of the training samples, P(g(z) 1x) denotes the probubility of correctly predicting the label of sample x with the trained classifier g. and ID(X) the intrinsic dimension of class X.
These bounds provide insights into the relationship between the intrinsic dimension of the class and the probability correct classification. Here, we first make the following reasonable assumptions:
(Graph Condensation Equivalence Assumption). The original and the condensed graphs exhibit equivalent capability in training GNNs [17].
Assumption 1.
Assumption 2. (Node Classification Decomposition Assumption). The multi-class classification task for nodes on the gruph can be upproximated as the union of binary clussification tasks for each node type 522
Assumption 3. (Optimal Classification Assumption). Under assumption 2 there exists a GNN with optimized parameters that can achieve optimal classificution performance for each class on the graph, reaching the upper bound specified in Eq. 17
Here, we discuss the probability of classifying the nodes with the label e in the graph G. Under assumption 2 and assumption there exists GNN classifier go with parameter 4b having the following:
((gx(n)) = =
(18)
2ID
where Go denotes the set of nodes belonging to class-c in graph G, ne represents test node belonging to class-c, hi is the number of training nodes in Go, and ID(G.) denotes the intrinsic dimension of G... Similarly, for the condensed graph G', we have the following:
P(ga (nc) le)
2
(19)
We can extract the intrinsic dimension ID(Ge) and ID()') from Eq. (18) and Eq. 19 as follows:
ID(G.) = log(1 */1 P(gæ(n. = 1c)
(20)
ID(G") = 1 log(1 6/1 1 - P(g = 1o)
(21)
The above expressions establish a mathematical link between the intrinsic dimension of a class of nodes and the probability of successful classification, providing a basis for comparing the original and synthetic graphs
15

---

We subtract Eq. 20 and Eq. 21 yielding:
ID(G.) ID( = -(1 [oglo - 'V1 P- P(gx (o)
(22)
+ (1 + log(1
V/1 P(g =l0)
(23)
= - llg
(1 "v1 P(gæ [c)
(24)
+ log
V1 P(gæ (nc) = 1c)
(25)
P(g (ne) 10)
log
(26)
V1 P(ge (ne) lc)
Based on assumption 1
we have + = Ø'. Additionally, according to the definition of graph
condensation, it follows that Ky < ki.. Thus have:
W/1 P(ger (nc) 1e) > 0.
log
(27)
/ 1 P(ga (Te) lc)
This result implies that ID(G') < ID(G)). Similarly, we can prove that the intrinsic dimension the nodes in each class decreases after graph condensation. According to [26 7 "a local ID estimator can be used as a global ID estimator by simply averaging over different samples". Therefore, when the intrinsic dimension of node sets of each class in the graph are reduced after graph condensation. we obtain ID( < ID(
This completes the proof.
A.2 Proof of Theorem
Here, we first restate the theorem:
Theorem 4. Based on theorem let G'. denotes the synthetic graph generated through graph condensation, where the original graph G. is under attack. Then we have:
ID(G") ID(G.).
(28)
Proof. We make the following reasonable assumption:
Assumption 4. Adversarial attacks in the original graph will lead decrease in the quality of the condensed graph.
Based on the proof of theorem [ for the nodes of class in the condensed graph, we have the following equation:
1 $/1 P(g (n.) (c)
ID((G.))) ID('') log
(29)
worh P(g4: (ne) 1c)
Due to (K)). Kg and P(gæ; (no)) < P(ge under assumption 4 can get:
1 - W/T Plg 1o) 0,
log
(30)
us/h1 Plge, (ne) le)
which indicates ID(())))) > ID(G'). Similar the proof of theorem 1 we can get ID( ID(g")
according to 26 7
This completes the proof.
16

---

A.3 Solving Eq. 9
We restate the Eq. 9
&: C(u, A) = ((Z c.)uu)² 2- X(u u, 1),
(31)
]=1
where À is the Lagrange multiplier. Let Y = 2; - c.1 Using this substitution, Eq. 9 can be reformulated as:
L(u;, u. Y, Yu, X(u; u, 1).
(32)
Thus, the original problem can be treated the following optimization problem:
min u Y)u,, subject to u. u, = 1.
(33)
Since Y Y is evidently a symmetric matrix, the Karush-Kuhn-Tucker (KKT) conditions for this optimization problem are expressed as:
{
2Y Yu, - 2Au; =0 u u, 1=
(34)
indicating that u, must satisfy the eigenvalue equation. Therefore, the solution for u, corresponds to the eigenvectors of Y subject to the unit norm constraint u, u, 1. Consequently, the problem described in Eq. ( is equivalent to the following:
C(u, A) = u, Y. Yu, A(u, u
(35)
u T
Au; 0
(36)
A
(37)
This result implies that the solution for u, corresponds to the eigenvectors of Y Y associated with its smallest eigenvalues, normalized to satisfy the unit norm constraint. This completes the derivation.
A.4 Proof of Proposition 1
Here, we first restate the proposition:
Proposition 2. By fitting the quadratic hypersurface fo(o) in the langent space via ming [ 0o, - -t,)2, where t; = -zz - -zi) u, represents the projection along the normal vector u, the Gaussian curvature of the manifold M((G)))) at node is given by Ka(i) [det(Mat(Q- where Q E pmmm=mm xm² is fourth-order tensor expressed trix with entries Qa,beed = Σj=1 Oja0)00f:00jt The vector p E Igm x1 a second-order tensor with entries Pa,b = Σズ= 050- The operator Mat(.) reshapes Q Q into an m X m matrix, and det(-) denotes the determinant.
ma-
Proof. Our goal is to determine the parameter @ that defines the quadratic hypersurface in the tangent space. The Gaussian curvature this hypersurface can then expressed as the determinant of the Hessian matrix associated with the quadratic hypersurface, i.e., det + 47 Our objective function is:
k
1
E(O) min
T 0o, 2 0
-11
(38)
E(O) quantifies the discrepancy between the predicted value and the target (image in a two- dimensional space, the tangent space plane, and the target value be fitted corresponds to the projection of the node onto the normal vector). To simply Eq, 38 we perform equivalent transformation express the objective function in terms of matrix traces:
[ f E()) E(ê) = tr {
T) o T)
(39)
17

---

where tr(-) is the trace operator, T E R&x1 is the target vector:
T [1 fg........................ .... [x],
(40)
Q E [ is defined based on the Kronecker product:
011 O11.
011 -1d-11
01d'-1 011
Old' 01d'-1
021 021
021
028 11
O2d'
021
O2d' 02d'-1
Ok! Okl
OF Okma
O
Okd
Old
(41)
and Ô E -1)² represents the vectorized form of the matrix O Specifically, θ is obtained by concating all rows of θ into single vector, defined as:
= 1 θ O mm
(42)
By calculating Ve (()), we have:
- O T)
V
( = 1tt
(43)
To
2 (o T T T
V
(44)
4
V (0T( 6)
2 V
T
)
(45)
4
1
V (0T(
- V
(46)
4
6 (O)))) -TO
(47)
2
By letting V E(E 0, get:
- T TT= -.
(48)
Solving Eq. (48) we can get the expression of Ô
b 2((00) (00) (O))
(49)
Thus, we can get the Gaussian curvature of the manifold M(())))) at node i given by KG (i) det(@) = 2det(Mat(Q Q ')),, where Q E Imm xm a fourth-order tensor expressed as a matrix with entries Qa,bee,d -ij Ogj The vector mgm* x1 is second-order tensor with entries Pa.b = Σ O5b The operator Mat(-) reshapes Q 'p into an m m matrix, and d.)(.) denotes the determinant. This completes the proof.
B Preliminary
To ensure the completeness and self-contained nature of this paper, we provide an overview of preliminaries relevant our work.
B.1 Intrinsic Dimension
The concept of intrinsic dimension (ID) was originally introduced by (5), where it defined as the number of free parameters required by hypothetical signal generator to produce a close approxi- mation for each signal in a given collection. According to the oww-dimensional manifold hypothesis 21 [3], real-world datasets typically reside (approximately) on low-dimensional manifolds em- bedded within high-dimensional Euclidean spaces. Specifically, let X E Raxd represent a dataset embedded in a dddimensiionl Euclidean space. The data points in X are assumed to be sampled from a manifold M, which is embedded in R where the intrinsic dimension of the manifold satisfies dim(M) < d. Here dim(M) refers to the dimension of the manifold M.
18

---

B.2 Gaussian Curvature
Gaussian curvature is a mathematical concept that quantifies how a surface eurves at a given point. It is an intrinsic property of the surface, meaning it depends only on the distances measured along the surface and not on how the surface is embedded in higher-dimensional space. The Gaussian curvature K of smooth surface in three-dimensional space at a point is the product of the principal curvatures [50], 1i and Kig, at the given point: K = K1 If the surface is represented locally as the graph of a function f via the implicit function theorem, the Gaussian curvature at point p can be computed as the determinant of the Hessian matrix of f. which corresponds to the product of the eigenvalues of the Hessian [50 47 Positive Gaussian curvature indicates that surface curves in the same direction in all tangent directions at a given point, forming a dome-like shape. Negative Gaussian curvature, the other hand, creates saddle-like like shape. The absolute value of the Gaussian curvature measures the degree curvature at a point, regardless of its sign, indicating how strongly the surface bends. A larger absolute value reflects sharper curvature, while smaller value suggests gentler bending.
B.3 Quadratic Hypersurface Fitting Process Explanation (Section 2)
normal vector
langent space
local region of the manifold
(1) Projection onto the tangent plane
(2) Projection onto normal vector
(3) Fitting the quadratic hypersurface
Figure Explanation of the Quadratic Hypersurface Fitting Process in Section 3.2
Here, we provide detailed explanation of the quadratic hypersurface fitting process in Section 3.2 After obtaining the normal vector u, and the tangent space ,, Ex.-1) We first project the neighboring points of node i onto its tangent space, shown on the left side of Figure Next, we fit quadratic hypersurface using the projected points in the tangent space as input. To fit the hypersurface, we also need to know the output function values. We define the target values as the projections of neighboring nodes onto the normal vector at node i. This process is shown in the middle of Figure 6 As illustrated in the figure, the normal vector projections capture the local geometry by quantifying how each neighboring point deviates from the tangent space, ensuring that the fitted hypersurface accurately reflects the manifold's curvature around node i. Finally, we fit the quadratic hypersurface by minimizing mine Σ (fo] Oo,- - 12)2, as introduced in Proposition and this process is illustrated on the right side of Figure
C Additional Experiment Details and Analysis
C.1 Details of the Toy Experiments in Section I
In this section, we detail the toy experiments conducted in section T
(1) For the experiments shown in Figure [(a) we used the Cora dataset with a condensation ratio set to 2.60%. The experiments involved three types of attacks: structure, feature, and label perturbations. For the structure attack, we employed the PRBCD algorithm [18] which introduces structural perturbations to the graph. In the feature attack, we randomly selected nodes from the training set and replaced their features with samples drawn from a normal distribution. For the label attack, we randomly selected a subset of nodes and uniformly flipped their labels to other classes. The attack
19

---

budget was set to p% of the total number of edges for structural perturbations and p% of the number of training nodes for both feature and label perturbations.
(2) For the experiments presented in Figure l(bb), we also utilized the Cora dataset, maintaining a condensation ratio of 2.60%. Our proposed MRGC employed GCond 33 as the backbone for graph condensation. The attack budgets for the feature, structure, and label perturbations were set to 10%, 1%, and 20% of the corresponding components, respectively.
(3) For the experiments presented Figure [(c]
we utilized the same dataset and attack budget settings as those used in the experiments shown in Figure I(b) Here, provide detailed explanation of the three metrics 44 used in our analysis:
Intrinsic DID: We employ the MLE 34 intrinsic dimension (ID) estimator for analysis. Specifically, for a given graph 9 - [X, A, Y with n. nodes, we use the node embeddings derived after rounds of message passing the node representations. These embeddings capture both structural and feature information and are computed as = A The resulting set Z = { represents the node representations of the graph. The intrinsic dimension of 2. which reflects the graph's intrinsic dimension, is then estimated using the MLE approach as follows:
ID(Z) = - Σ
(=(2) Tx(=))
log
(50)
where it a hyperparameter that determines the number of nearest neighbors of considered in the calculation, and we set l = 8. The term rz(z) represents the distance between and its i-th nearest neighbor, while Fx (2) denotes the distance between and its k-th nearest neighbor. For this computation, we employ the Euclidean distance metric to measure the proximity between points.
Fisher's Discriminant Ratio (FDR): It measures the overlap between the values of the features in different classes and is given by:
FL max
(51)
where ry, is the discriminant ratio for each feature ft. Originally, FDR takes the highest value of Tf meaning that at least one feature should separate the classes. This paper the inverse of this original formula, making the FDR values fall between (0, 1), with higher values representing more complex problems where single feature can discriminate the classes. An common formula for ry, in classification task is:
ΣØ= ビ==1 ne.
c: H.s.)
TA
2'
(52)
E/= The i=l x 11
where ney is the number of examples in class cj. and xi is the individual feature value for an example from class Cj- Pe, represents the proportion of examples in class cj. and " is the mean of feature f; for class Cy. with 7 as the standard deviation. In our approach, similar to the estimation of intrinsic dimension, we consider the graph G set Z.
Fraction of Hyperspheres Covering Data (FHC): A topological measure used to assess the coverage of dataset by hyperspheres. This method builds hyperspheres centered each data point and progressively increases their radius until they intersect with a data point from a different class. Smaller hyperspheres that are contained within larger ones are eliminated, and FHC defined as the ratio between the number of remaining hyperspheres and the total number of examples in the dataset. The formula for FHC given by:
FHC Hyperspheres(TT
(53)
where HHyperspheres(()) represents the number of hyperspheres needed to cover the dataset, and n is the total number of examples in the dataset. In this work, we follow the calculation method from Lorena al. (2019). To determine the radius of hypersphere for a given data point v;, we first calculate the distance matrix between all examples in the dataset. Specifically, the "nearest
20

---

Astonay (Kg)
41.91
50.0
1547
GCond
GCood (-M)
Gionnd (MM)
GCond (IGIB)
GCand (MGiB)
GCond (uunn) ("Guard) (Omn))
GCand
MRGC
Figure 7: Additional experiments on robust GNNs as GC backbones. Here, (+) indicates that the robust GNNs serve as the backbone of GCond, while (*) signifies that the robust GNN is applied to the condensed graph, which is obtained using the standard GNNs. "M" denotes the MedianGCN g and "Guard" represents the GNNGuard 71
enemy" of data point refers to the closest point from different class. The radius of the hypersphere centered x; is then calculated as half of the distance to this nearest point from another class. To compute the radius for 24, first measure the distance d, from to another data point Zy, then identify the nearest point from a different class for both z; and Zj. æ4 is the nearest point from different class to Zj. the radius is set to half the distance d, Otherwise, the radius is adjusted based on the distance between the nearest points of the two examples. Once the radii of all hyperspheres are computed, post-processing step is used to identify which hyperspheres can be absorbed: those completely contained within larger hyperspheres. This ensures that only the most relevant hyperspheres considered in the final FHC measure. For the distance computation, we continue to use 2, consistent with the approach used the previous two metrics.
C.2 Additional Experiments on Robust GNNs as GC Backbones
To further investigate whether existing robust GNN technologies can enhance the robustness of graph condensation, we adopt more robust GNNs as the backbones of GCond. Specifically, we select GNNGuard and GIB 660 as the backbone models for GCond. The results are shown Figure
As shown in Figure 7 GNNGuard and GIB do enhance the robustness of GC. Moreover, as mentioned in the Introduction, MedianGCN also fails to improve robustness. This suggests that current robust GNN techniques may not effectively address the robustness of GC, indicating the need for novel solutions to tackle this issue.
C.3 Dataset Details
In our experiments, we use five real-world datasets: (1) Cora: Contains 2,708 publications classified into seven classes, with 5,429 citation links. Each publication is represented by binary word vector indicating the presence or absence of 1,433 dictionary words. (2) CiteSeer: Includes 3,312
publications classified into six classes, connected by 4,732 citation links. Each publication is described by a binary word vector over a dictionary of 3,703 words. (3) PubMed: Comprises 19,717 diabetes-related publications classified into three classes, with 44,338 citation links. Each publication represented by a TF/tDF-weighted word vector from a dictionary of 500 words. (4) DBLP: Contains 17,716 papers, 105,734 citation links, and four labels. (5) Ogbn-arxiv: directed citation network of computer science papers on ArXiv.
The train/val/test split for the Cora, CiteSeer, PubMed, and Ogbn-arxiv datasets follows the same configuration as the benchmark in (20). For the DBLP dataset, we use the settings from (28] performing random splits with 20 labeled nodes per class for training, 30 per class for validation. and the remaining nodes for testing.
In our experiments, we use the transuctive settings. The condensation ratios for the datasets are configured as follows: Cora, the ratios are set 1.30%, 2.60%, and 5.20%. For CiteSeer, they are 0.90%, 1.80%, and 3.60%. In the case of PubMed, the ratios are 0.08%, 0.15%, and 0.30%. Similarly,
21

---

for DBLP, the values are 0.11%, 0.23%, and 0.45%. Lastly, for Ogbn-arxivv arxiv,, the condensation ratios are set to 0.05%, 0.25%, and 0.50%. The condensation ratio refers to the proportion of the number of nodes in the condensed graph to the total number of nodes in the training graph. The statistical information of the datasets is presented in Table
Table 3: The statistics information of datasets.
Dataset
#Nodes
#Edges
#Classes
#Features
Train/Va/Test
Cora
2,708
5429
1.433
140/500/1
CiteSeer
3,327
4732
3,703
120/500/1000
PubMed
19,717
88,648
500
60/500/ 1,000
17,716
105,734
1,639
7,7516
Ogba-arxiv
169.343
1,166,243
40
128
90,941/29,799/488.68
C.4 Baseline Details
To better evaluate the robustness our proposed MRGC, we adopt five types of basclines:
(1) Gradient-matching-bann methods.
The first gradient matching method that aligns model gradients derived from the training and condensed graphs, ensuring the condensed graph effectively preserves the knowledge for GNN training.
GCond B3
SGDD [65] It addresses the issue where GC methods often overlook the impact of structural information from the original graphs. Empirically and theoretically, SGDD demonstrates that synthetic graphs generated by its method are expected to have smaller LED shifts compared to previous works.
(2) Trajectory-matching-be based methods.
A structure-free method that aligns model learning behaviors by aligning the training trajectories of parameter distributions expert GNNs.
SFGC 74
It employs curriculum learning strategy to train expert trajectories with more diverse supervision signals derived from the original graph.
GEOM 772
(3) Claributtio-maachingg based methods.
GCDM [37]: minimizes the discrepancy between node distributions of the training and condensed graphs in feature space.
(4) Distribution-matchinn mawprrtooo--mmaccnnn--aaaeeddd methods. To better highlight the robustness improvement achieved by MRGC, we adopt three state-of-the-arr graph denoising methods before applying GC the same 16]. We choose GCond the GC backbone.
GCond(+S) 31: This method decomposes the noisy graph through Singular Value Decomposition (SVD) and applies low-rank approximation to denoise the graph, reducing the influence of potential high-rank noise.
GCond(+J) B1: This method computes the Jaccard similarity for every pair of connected nodes and discards edges whose similarity is below a specific threshold. our experiments, we set the threshold to 0.01.
GCond(+K) [30]: It identifies the k-nearest neighbors for each node based on their features and incorporates potentially effective edges into the original graph. In our experiments, we set k 3
(5) Robust Graph Condensation method.
The first proposed robust graph condensation method. It is a plug-and-play defense approach that integrates the structure learning process into the GC process, using the condensed graph supervised signal to optimize the original graph structure.
RobGC [6]
22

---

Accuracy (56)
75
74.47
23.92
Accuracy (%)
75
-5:000
75/43
73.67
Accuracy (%6
75
P3.58
73.09
73.79
79169
72.3
pubmed
dblp
70
pubmed
dhlp
70
pubmed
dblp
64.4
80
64,56
65/12
64,0
6512
64,50
64.77
65.75
64.7
69.8
60
60
60
50-1
160
5c0
lel
5el
1c2
le-2
5o-2
le-1
Sc-1
1c0
5c0
5c-2
1o-1
50-1
1c0
5e0
lel
Figure 8: Additional Hyperpa- rameters study.
C.5
Implement Details
Our proposed MRGC is plug-and-play graph condensation method, with GCond 3 selected as the GC backbone our experiments. The hyperparameter settings for each dataset are shown in T
Table 4: Hyperparameters Setting.
Dataset
Ratio
Inteatt Is(adj)
1.30%
le2
le-l
1c0
3
0.01
0.0001
Cora
2.00%
Sel
le-1
le0
0.01
0.0001
5.20%
Sel
le-2
le-1
0.01
0.0001
0.90%
le0
Se-1
Se-2
0.01
0.0001
CiteSeer
1,80%
1c0
5e-2
5e-2
0.01
0.0001
3.60%
le0
Se-2
Se-2
3 0.01
0.0001
0.08%
5e0
Io-1
0.0001
0.0001
PubMed
0.15%
5e0
le-3
1e:3
5
0.0001
0.0001
0.30%
0.0001
0.11%
5e1
Te-1
1c0
0.01
0.0001
DBLP
0.23%
1e0
Se-2
1c0
0.01
0.0001
0.45%
le1
5e-1
1e-1
0.01
0.0001
0.01%
5c-3
Ic-9
Ic-4
0.005
0.005
Oghn-arxiv
5e-3
0.50%
5c-3
1c-9 1e-4
0.005
0.005
C.6 Additional Hyperparameter Sensitivity Study
The sensitivity of additional hyperparameters the PubMed and DBLP datasets, with condensation ratio of 0.90% and 0.11%, %. is shown in Figure g
As observed in the DBLP and PubMed datasets, when the hyperparameters suitable values, our MRGC achieves its best performance. Moreover, wide range hyperparameter settings still results in consistently superior performance.
D Algorithm
D.1 Detailed Complexity Analysis
Here we detailed analysis of the time complexity of our proposed MRGC.
For the Intrinsic Dimension Manifold Regularization Module, solving the Laplacian approximation requires computational complexity of On'd'), where n' denotes the number of nodes in the condensed graph. Evaluating the volume [M((")) involves computing determinant, which has complexity of ((d')s), corresponding to the -dimensioonl covariance matrix. So the total time complexity for this module is O(n'd d' + (d
For the Curvature- normal vector and tangent space for each point. This requires solving the eigenvalue decomposition of the matrix TT dd''d', where Y is constructed from the nearest neighbors. The time complexity for this step is O(k (d)) Next, fit quadratic hypersurface to obtain the
Manifold Smoothing Module, the process begins by computing the
23

---

Gaussian curvature, which involves solving the analytic solution in Proposition 1 Specifically, this step requires computing the matrix inversion of (d' 1 (d' 1)2 matrix Q and the determinant of the matrix Mat(Q, Q "p) E -I) The time complexity for this is O((d' 1) + (d' - -))9). This calculation must be performed for each node, resulting in time complexity of (n''(d' 1) + k + (d')² + (d' - 1)²)). Finally, we compute the Ricci curvature for each node, with time complexity of )() Combining these, the total time complexity is (n' - 1) + +k+ (d' + (d' -1)3 + tn)). After simplification, this aproximates (n'((d')) + k +n)).
For the Class-Wiss Manifolds Decoupling Module, we estimate the volume of the manifold for each class as well as the total graph data manifold. The computational complexity of this module is (()(d"))) where с represents the total number of classes in the graph data, and d' is the dimensionality of the feature space.
The total time complexity of our proposed MRGC is given by: O + (d')3 k + n²) ))) After simplification, the total time complexity of MRGC is approximately to (d') - (n')²). However, due to the definition of GC, the mumber of nodes in the condensed graph, n', significantly smaller than in the original graph, making n' a relatively small number. Furthermore, prior to applying our MRGC, we use PCA [[]] to reduce the dimensionality of the condensed graph, which ensures that d' is also kept small. As a result, the actual execution complexity of our approach remains efficient in practice despite the theoretical time complexity.
1)
D.2 Detailed Training Pipeline
Here, we detail the overall training pipeline of our proposed MRGCThe overall training pipeline of MRGC is outlined in Algorithm The inputs include the attacked training graph G. the hyperpa- rameters a, 3, 7: k, and additional hyperparameters determined by the chosen graph condensation backbone. Initially, the node features of the condensed graph are initialized by randomly selecting non-outlier nodes from the original graph that belong to the same class, Outliers are identified based on the Euclidean distance of their features. Let the average distance be denoted as μud and the variance as oj. Nodes with a distance to other nodes of the same class greater than Pdr + 2 are classified as outliers. The labels and adjacency matrix of the condensed graph are consistent with those used in [33. We obtain the node representations by the node features after two rounds of message passing like Z = x Then we adopt the PCA [i]] to reduce the dimensionality of the node representa- tion to get better performance while significantly reducing the excitation time. Next, we compute the Intrinsic Dimension Manifold Regularization term, calculate the Curvature-Awar Manifold Smoothing Module, and process the Class- Wise Manifold Decoupling Module. These steps yield three manifold regularization terms: Laims Leur, and Lup- It is worth noting that our proposed MRGC can be integrated with any training-based GC methods. Consequently, the Lae is defined by the specific GC backbone it employs. Then, the total training loss is: C = Loc + aL + BLeur + Cyop. Subsequently, the condensed graph is optimized by minimizing L.
E Detailed Related Work
Here, we provide a detailed discussion of the related work, which we briefly summarized in Section 2
Graph Condensation. Graph condensation 33 was proposed to enhance the training efficiency and scalability of Graph Neural Networks by synthesizing much smaller yet highly informative graph. The smaller graph retains the ability to train GNNs effectively, achieving performance comparable to that of GNNs trained on the original, much larger graph. The existing graph condensation studies can be roughly categorized into four lines:
Brachiet-Macchnn-- Based Methods: The saaddien--machiig--baa methods were introduced in GCond (33,, the first graph condensation method. These methods match the gradient information of the same GNN trained on both the original, larger graph and the condensed, smaller graph, with the goal of minimizing the gradient differences at each training step. However, the standard GCond method ignores the structural information linking the original and condensed graphs. To address this issue, SGDD (5] applies optimal transport theory and designs a method to transfer structural information from the original graph to the condensed graph, thereby achieving smaller shifts in Laplacian Energy Distribution (LED).
24

---

Algorithm The overall training pipeline of MRGC.
Require: Attacked training graph G, hyperparameters a, B: 7,
Ensure: Condensed graph G for epoch = 1, E do
Initialize the node features, adjacency matrix, and labels g'.
C= 0
Obtain the standard graph condensation loss Lec
C C + Lee
Calculate the node representation Z' = (A')xx'
Dimensionality reduction of the node representation using PCA: Z' =PCA(Z')
for c = l........ do
/IItrinsiic Dimension Manifold Regularization*/
Compute Laii by Eq. (7)
(CCuraaure-Aware Manifold Smoothing /
Compute Leur by Eq. 11
C+ C (aLddsm + -BLoar)
end for
C*Class- Wiss Manifold Decoupling*/
Compute Seep by Eq. (14
L +
Optimize the condensed graph to minimize C end for
Furthermore, demonstrates both experimentally and theoretically that one-step gradient matching (i.e., not using the inner loop in gradient matching) can still yield excellent results and significantly improve condensation efficiency. Additionally, MSGC (15 also uses pre- defined structures that allow each condensed node to capture distinct neighborhoods, thereby improving the graph condensation process through better graph structure construction.
Prrjectory-Matching Based Methods. arate GNN models on the condensed and original graphs, respectively, and minimize the discrepancy in the training trajectories (i.e.. the variation model parameters) between the final points of these two training trajectories. Unlike rradientmmatching bbasch methods, trajectory-matet www--mmagtttaaaaaaeeee based methods are a multi-step matching approach [17] and often yield SFGC (74 is the first gijjectory-machhing based method in graph condensation. It proposes aligning the long-term GNN learning behaviors between the original and condensed graphs, achieving promising results even when the condensed graph has no structural information, thus enabling structure-free graph condensation. Furthermore, GEOM (72) recognizes the limitations of supervision in trajectory matching and highlights that challenging nodes primarily cause the performance gap in GNNs trained on condensed graphs. To tackle this issue, GEOM assesses these difficult nodes and employs curriculum learning to adjust the matching window size during training dynamically.
Mattttorr--Mtiiiggg-.... Based Methods train two sep-
better results [54] 20 41
Distribution-Mtten Matching -Based Methods. Iestribution-mtcchin -aased methods aim to min- imize the discrepancy in graph statistic distributions between the condensed and original graphs. To be specific 17.. GCDM 37, CaT 40) and PUMA (42 calculate the node distributions in the shared feature space for both the original and condensed graphs, and they optimize by minimizing the maximum mean discrepancy between the corresponding class distributions. Besides this, GDEM (39] works by aligning the eigenbasis as well the node features of both the real and synthetic graphs, which helps in reducing the spectrum bias that is typically caused in the synthetic graph.
Others. There are also many different graph condensation methods. For instance, to reduce the computational burden the inner optimization of gradient-matching -attt-mgttahhheeeeee methods, GCSNTK [57] integrates the Graph Neural Tangent Kernel within the Kernel Ridge Regression framework as an alternative. Additionally, KiDD 63 leverages Kernel Ridge Regression by eliminating the non-linear activation function.
Robust Graph Learning. Although Graph Neural Networks have shown promising results, numerous studies (53 58 31 indicate that they are vulnerable to adversarial attacks, where even small, imperceptible
25

---

perturbations in the graph can significantly degrade their performance. Fortunately, several lines of research have shown promising results in enhancing the robustness of Graph Neural Networks, which can be broadly categorized into three main approaches:
Preprocessing- Baaiged Methods. Preprocessing- methods aim to denoise the graph before training or inference. For example, GCN-Jaccard [58] uses the Jaccard similarity between node feature pairs, removing edges from node pairs whose similarity falls below a predefined threshold. GCN-SVD [2] is based on the widely accepted assumption that real- world graphs often exhibit low-rank properties. leverages Singular Value Decomposition (SVD) to decompose the adjacency matrix and discard the low singular values. GCN- KNN BI connects each node to its k most similar neighbors, adding an edge between them if one does not already exist.
Modeling-Basse Based Methods, Modeling-based methods defend against adversarial attacks by modifying the model architecture. RGCN [75] uses Gaussian distributions as the hidden representations of nodes and mitigates the effects of adversarial changes by absorbing them into the variance of the Gaussian distribution. Pro-GNN [3I. inspired by the well-known properties of low-rank, sparsity, and feature smoothness,, uses structure learning dynamically adjust the graph structure to enhance GNN robustness. GNNGuard [7]] learns how to assign higher weights to edges connecting similar nodes while pruning edges between unrelated nodes. HANG 733 advocates for the use conservative Hamiltonian neural flows in constructing
GNN to improve its robustness.
Training- Baased Methods. Training-based methods do not alter the model architecture the graph; instead, they employ specially designed training strategies to make the model resistant to adversarial attacks. [4
22 35 apply adversarial training to reduce the sensitivity of
Graph Neural Networks to adversarial perturbations. SG-GSR [29] design a novel group- training strategy address the loss of structural information and the issue of imbalanced node degree distribution.
Robust Graph Condensation. Early research work [59] observed that traditional graph reduction methods faced significant difficulties in effectively defending against PGD [62] attacks. As graph condensation has gained recognition 611 and has been seen as a solution to improve GNNs training efficiency, RobGC [16] became the first study to delve into the robustness of GC in the face of adversarial attacks. This work introduced a defense mechanism that was specifically designed to address and counteract structure-bast based attacks. Furthermore, benchmark (20] demonstrated that feature noise, which has been a major challenge in Graph Neural Network models. presents even greater difficulties when applied to GC. This highlighted the importance of considering multiple sources of noise and their impact on the effectiveness of GC.
more effective and promising graph reduction technique (17]
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification:
All the assumptions and complete proof are provided in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the information needed to reproduce the main experimental results are provided in Section 4 and Appendix
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [Yes]
Justification:
Our code is available at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //iipe.cc/pullic/guuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Provided in Section and Appendix Guidelines:
C
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Results are accompanied by error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Provided in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://p...ccpuuotottttcccciiiee
Answer: [Yes]
Justification: This paper follows all the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the abstract and introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
30

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All the owners assets used are properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworeeswthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
31

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
32

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standad components.
Please refer to our LLM policy hattps://neurips... 200ps//ee///0ooeeeeeee////////// for what should or should not be described.
33


Reviews:
[{"review_id": "FUjcg9dPD7", "reviewer": "Reviewer_gMV8", "summary": "This paper introduces Manifold-constrained Robust Graph Condensation (MRGC), a novel framework designed to enhance the robustness of Graph Condensation (GC) against universal adversarial attacks on graph features, structures, and labels. The authors empirically and theoretically demonstrate that GC inherently reduces the classification complexity of graphs, a critical property that is highly vulnerable to adversarial perturbations. To counter this vulnerability, MRGC incorporates three graph data manifold learning modules: Intrinsic Dimension Manifold Regularization, Curvature-Aware Manifold Smoothing, and Class-Wise Manifold Decoupling. These modules guide the condensed graph to reside within a smooth, low-dimensional manifold with minimal class ambiguity, thereby preserving GC's classification complexity reduction capability and ensuring robust performance against diverse attack scenarios. Extensive experiments show that MRGC consistently outperforms existing baselines across various datasets and attack budgets", "questions": "- The experiments evaluate robustness against specific and commonly used poisoning attacks: PRBCD for structure, random feature sampling, and uniform label flipping. I am not confidence on the attack performance of random feature sampling and uniform label flipping. I am curious will the resilience still hold after being attacked by more dedicated attack methods like like Nettack[1]. \n\n[1] Zügner, Daniel, Amir Akbarnejad, and Stephan Günnemann. \"Adversarial attacks on neural networks for graph data.\" Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2018.", "limitations": "**Scope of Adversarial Attacks:** The experiments evaluate robustness against specific and commonly used poisoning attacks: PRBCD for structure, random feature sampling, and uniform label flipping. The study does not investigate the method's resilience against a broader range of more sophisticated or adaptive adversarial attacks.\n\n**Hyperparameter Tuning:** The MRGC framework introduces three new regularization hyperparameters (α,β,γ) which must be tuned. The paper notes that these were determined through a grid search, which can be a computationally intensive process and may pose a practical challenge for applying the method to new datasets.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n- Novelty in Robustness: The paper addresses a largely unexplored area: the robustness of Graph Condensation (GC) against various adversarial attacks (feature, structure, and label perturbations).\n\n- Clear presentation of the designed modules.\n\n- Comprehensive analysis and experimentation: It provides both empirical investigation and theoretical analysis to reveal that GC is an intrinsic-dimension-reducing process, and this property is vulnerable to adversarial attacks.\n\n- Demonstrated Superior Performance: Extensive experiments show that MRGC consistently outperforms state-of-the-art GC methods and robust graph denoising techniques across various datasets and attack budgets.\n\n- It is appreciated that the author conducts the ablation study on the MRGC performance by removing each module.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the detailed comments and insightful questions! Responses are as follows.\n\n---\n\n**W1 & L1: It's unclear whether MRGC hold under attacks like Nettack.**\n\n**A1**: Thank you for your insightful review.\n\nWe agree that robustness under more adversarial attacks is crucial for assessing the reliability of our MRGC. However, Nettack is a **targeted attack** designed to perturb specific individual nodesin the original graph. Since graph condensation produces a compact synthetic graph that does not maintain one-to-one correspondence with original nodes, targeted attacks like Nettack are not directly work in this setting.\nTo address the core of your insightful concern, we further evaluate the robustness of **MRGC** under **MetaAttack** [1], **a global adversarial attack**. The following table presents the test accuracy of GNNs trained on condensed graphs generated by different condensation methods under MetaAttack perturbations:\n\n|  | **Cora(1.30%)** | **CiteSeer(0.90%)** | **PubMed(0.80%)** |\n| --- | --- | --- | --- |\n| GCond | 73.53 | 57.77 | 50.87 |\n| SGDD | 71.27 | 48.62 | 41.63 |\n| GEOM | 45.8 | 35.86 | 44.12 |\n| RobGC | 74.14 | 58.54 | 49.43 |\n| **MRGC** | **77.17(+3.03%)** | **64.23(+5.69%)** | **52.67(+2.19%)** |\n\nAs shown in the table, **MRGC consistently achieves the best robustness across all datasets under MetaAttack**, outperforming both standard and robustness-aware baselines.\n\n*[1] Adversarial Attacks on Graph Neural Networks via Meta Learning. ICLR’19*\n\n---\n\n**L2: Tuning three hyperparameters via grid search adds computational overhead.**\n\n**A2**:  Thank you for your insightful review.\n\nWhile three hyperparameters need to be tuned, **most optimal values remain consistent across datasets**, reducing the need for exhaustive search. Empirically, we also find that **smaller values are generally effective when the condensed graph contains fewer nodes per class**, providing practical guidance to streamline tuning in new settings."}, {"review_id": "yENzvSpamy", "reviewer": "Reviewer_GwSS", "summary": "Current Graph Condensation (GC) algorithms struggle to handle noisy data effectively and lack sufficient robustness studies. This paper aims to address the following three key questions: \\\nQ1: Can existing robust graph learning techniques enhance the robustness of GC methods? \\\nQ2: What key property of GC is disrupted by adversarial attacks, leading to performance degradation, and can this be theoretically explained? \\\nQ3: How can we design an effective defense strategy to counter universal attacks in GC?\n\nThey use three metrics to measure classification complexity, along with the analysis of the relationship between graph condensation (GC) and adversarial attacks.\n\nTo address the robustness issues in current GC methods, the paper proposes three key components: Manifold Regularization, Curvature-Aware Manifold Smoothing, and Class-Wise Manifold Decoupling.", "questions": "See weaknesses", "limitations": "The discussion on limitations is insufficient. As the authors, you likely have a deep understanding of the potential weaknesses of your approach. A more thorough and reasonable analysis of the limitations would help readers better assess the scope and applicability of your work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The use of three metrics to measure classification complexity, along with the analysis of the relationship between graph condensation (GC) and adversarial attacks, makes the motivation of this paper easy to understand. It also provides an intuitive explanation of the limitations of current GC algorithms.\n- The motivation of the paper is clearly presented, and the introduction is easy to follow.\n- The overall writing is logically structured and accessible, allowing readers to understand the contributions even without deep familiarity with the underlying theory.\n- The experimental evaluation is thorough and comprehensive.\n\nWeaknesses:\n1. In Figure 1.C, it would be more informative to show how the three metrics change on the original graph before and after the attack. Comparing only the condensed graph under clean and attacked conditions can demonstrate that the attack degrades accuracy or increases classification difficulty, but it is insufficient to evaluate how well GC performs on the attacked input graph itself.\n2. Section 3.2 aims to produce clearer decision boundaries through Curvature-Aware Manifold Smoothing. In that case, is the additional method in Section 3.3 necessary? The potential redundancy between the two is unclear.\n3. The concept of the manifold M(G′)\\mathcal{M}(G')M(G′) plays a central role in the proposed method. However, its definition and the specific type of manifold used remain unclear. A more precise explanation or formal definition would help clarify the intuition and theoretical foundation of the approach.\n4. In Tables 1 and 2, under different attack strategies and settings, it would be helpful to include the performance without condensation as a reference. This would allow readers to better understand the effectiveness of GC under various conditions. Additionally, I suggest clearly marking the performance on the original graph in the tables for easier comparison.\n5. The discussion on limitations is insufficient. As the authors, you likely have a deep understanding of the potential weaknesses of your approach. A more thorough and reasonable analysis of the limitations would help readers better assess the scope and applicability of your work.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the detailed comments and insightful questions! Responses are as follows.\n\n---\n\n**W1:** In Figure 1.C, consider showing how all three metrics change on the original graph before and after the attack, instead of only on the condensed graph, to better assess GC’s performance under attack.\n\n**A1**: Thank you for your insightful review.\nWe present below the results showing how all three metrics change on the original (including non-condensed) graph, both before and after adversarial attacks. (*) indicates under attack.\n\n|  | Original Graph | Original Graph(*) | Condensed Graph | Condensed Graph(*) |\n| --- | --- | --- | --- | --- |\n| Intrinsic Dimension | 12.14 | 13.61 | 2.24 | 8.57 |\n| Fisher’s Discriminant Ratio | 0.19 | 0.22 | 0.09 | 0.41 |\n| Fraction of Hyperspheres Covering Data | 0.93 | 0.93 | 0.09 | 0.99 |\n\nAs shown, adversarial attacks increase the classification complexity not only in the condensed graph but also in the original graph, especially in Intrinsic Dimension & Fisher’s Discriminant Ratio.\n\n---\n\n**W2:** Section 3.2 aims to produce clearer decision boundaries via Curvature-Aware Manifold Smoothing. Given this, is the method in Section 3.3 necessary? The potential redundancy between the two remains unclear.\n\n**A2**: Thank you for your insightful review.\n\n- **Motivation:** Our framework is designed based on the observation that adversarial attacks increase the **classification complexity** of the condensed graph. According to classification complexity theory [1,2], this complexity arises from three main factors: **(1) higher intrinsic dimensionality, (2) increased class overlap, and (3) complex class boundaries.** Motivated by this, we introduced three targeted modules in our framework to reduce intrinsic dimension, class overlap, and boundary complexity respectively.\n- **Principle**: Curvature-aware smoothing is a **local** second‑order regularizer, it penalizes Gaussian curvature to make each class boundary smoother, **but it does *not* change where or how much different class manifolds overlap in space.** By contrast, class‑wise decoupling is a **global** volume‑based loss that directly minimizes the shared support between classes.\n- **Example:** Imagine class A’s points lie on a unit circle and class B’s on a concentric circle of radius 1.2, creating an annular overlap. Curvature smoothing can round off any zigzag in the decision curve, yet it still must traverse the overlapping band. Only the decoupling module, which effectively shrinks the inner ring or expands the outer ring, can open a gap so that a smooth boundary can pass between the two without crossing.\n- **Empirical:** We conducted an ablation study to evaluate the necessity of each component. Below are results comparing the full model (MRGC) with variants that omit either the curvature (w/o Curvature) or decoupling (w/o Decoupling) modules:\n    \n    \n    |  | **Cora(1.30%)** |  | **CiteSeer(0.90%)** |  |\n    | --- | --- | --- | --- | --- |\n    |  | Acc | Gap | Acc | Gap |\n    | MRGC | 77.43 | / | 65.12 | / |\n    | MRGC(w/o Curvature) | 76.01 | -1.42 | 64.57 | -0.55 |\n    | MRGC(w/o Decoupling) | 75.77 | -1.66 | 64.78 | -0.34 |\n    \n    These results confirm that **both modules contribute meaningfully**, with curvature-aware smoothing providing more gain on **Cora** and decoupling having a greater impact on **CiteSeer**. \n    \n\n*[1] How complex is your classification problem? a survey on measuring classification complexity. CSUR’19*\n\n*[2] Complexity measures of supervised classification problems. TPAMI’02*\n\n---\n\n**W3:** A more precise or formal explanation of the manifold would clarify the intuition and theoretical basis.\n\n**A3**: Thank you for your insightful review.\n\nWe clarify its definition as follows:\n\n$\\mathcal{M}(G\\')$ denotes the underlying data manifold on which the condensed graph $G\\'$ is assumed to lie. This assumption is consistent with standard manifold learning literature[1][2], which suggests that high-dimensional data often reside on a lower-dimensional data manifold. In our context, we consider $\\mathcal{M}(G\\')$ as a smooth, compact submanifold embedded in $\\mathbb{R}^{d'}$, formed by the learned node representations $\\mathbf{Z}\\' = (\\mathbf{A}\\')^2 \\mathbf{X}\\'$.\n\n*[1] Intrinsic dimension of data representations in deep neural networks, Neurips’19*\n\n*[2] Low dimensional manifold model for image processing, SIAM Journal on Imaging Sciences’17*\n\n---\n\n**W4:** In Tables 1 and 2, including performance without condensation would help assess GC’s effectiveness under different attacks.\n\n**A4**: Thank you for your insightful review.\n\nThe results corresponding to Tables 1 (Performance comparison under different condensation ratios when the training graph is corrupted) **without graph condensation** are provided below:\n\n| Dataset | Ratio | GCond | w/o Condensation | **MRGC** |\n| --- | --- | --- | --- | --- |\n| Cora (1,10,20) | 1.30% | 70.69 | 67.25 | **77.43** |\n| CiteSeer (1,10,20) | 0.90% | 60.77 | 59.94 | **65.12** |\n| PubMed (0.1,10,20) | 0.08% | 70.81 | 72.76 | **74.85** |\n| DBLP (0.1,10,20) | 0.11% | 62.50 | 57.74 | **65.11** |\n| Arxiv (0.1,10,20) | 0.05% | 58.16 | **65.86** | 59.38 |\n\nThe results corresponding to Tables 2 (Performance comparison under different attack budgets when the training graph is corrupted) **without graph condensation** are provided below:\n\n| Dataset | Budget | GCond | w/o Condensation | **MRGC** |\n| --- | --- | --- | --- | --- |\n| Cora(1.30%) | S.5% | 60.59 | 59.54 | **65.57** |\n|  | S.10% | 59.09 | 50.89 | **64.02** |\n|  | F.20% | 69.36 | 68.31 | **74.79** |\n|  | F.30% | 65.22 | 65.48 | **72.36** |\n|  | L.30% | 64.97 | 62.80 | **70.47** |\n|  | L.40% | 57.49 | 47.95 | **63.89** |\n| CiteSeer(0.90%) | S.5% | 48.51 | 42.67 | **52.91** |\n|  | S.10% | 45.06 | 39.78 | **52.72** |\n|  | F.20% | 58.28 | 59.25 | **62.76** |\n|  | F.30% | 54.45 | 58.46 | **62.41** |\n|  | L.30% | 51.49 | 43.80 | **59.33** |\n|  | L.40% | 49.25 | 44.78 | **59.20** |\n| PubMed(0.08%) | S.0.5% | 56.54 | 56.74 | **60.57** |\n|  | S.1.0% | 55.21 | 53.70 | **58.96** |\n|  | F.20% | 71.10 | 67.81 | **73.43** |\n|  | F.30% | 67.26 | 62.83 | **68.86** |\n|  | L.30% | 68.04 | 57.59 | **73.38** |\n|  | L.40% | 56.14 | 37.45 | **58.28** |\n| DBLP(0.11%) | S.0.5% | 62.31 | 59.55 | **65.36** |\n|  | S.1.0% | 61.26 | 57.73 | **64.49** |\n|  | F.20% | 60.41 | 60.91 | **63.42** |\n|  | F.30% | 60.45 | 60.13 | **63.68** |\n|  | L.30% | 70.37 | 65.45 | **73.39** |\n|  | L.40% | 68.30 | 68.62 | **73.12** |\n\nAs observed, vanilla graph condensation sometimes offers minor improvements to robustness under adversarial attacks, but can also fail to do so in certain cases. **In contrast, our MRGC consistently enhances robustness across most datasets and attack scenarios** (except on Arxiv).\n\n---\n\n**W5 & L1:** The limitations discussion is considered insufficient.\n\n**A5**: Thank you for your insightful review.\n\nHere, we further discuss our limitations sufficiently: First, we have not yet evaluated the robustness of our method on graph classification tasks. Second, we have not tested its effectiveness under node injection attacks, where the number of nodes may vary."}, {"review_id": "AICIy9KyEl", "reviewer": "Reviewer_EHXr", "summary": "This paper introduces a new framework for Robust Graph Condensation that enhances the resilience of GNNs trained on condensed graphs under adversarial or noisy perturbations. The core idea is to regularize the classification complexity during the condensation process, encouraging the model to favor simple and generalizable decision boundaries. The method shows improved performance and robustness on various datasets compared to existing condensation and defense baselines.", "questions": "1. Most robust GNNs rely on full-graph structures and global supervision, which are absent in the condensed setting. How do these mismatches lead to their ineffectiveness when applied post-condensation?\n2. In what way does constraining the classifier to simpler decision boundaries improve generalization and resistance to perturbations on synthetic graphs?\n3. Does the added regularization introduce any trade-offs in clean accuracy, and how does the method compare to baseline condensation approaches without perturbation?\n4. For other questions, please refer to the Weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n1. The paper identifies a clear limitation in prior condensation methods of overfitting to clean signals, which leads to fragile synthetic graphs.\n2. Instead of modifying the GNN or defenses post hoc, the method improves robustness through simple decision boundary enforcement during condensation.\n3. Empirical results show consistent robustness gains across different noise levels and attacks (random, adversarial, feature corruption).\n\n**Weaknesses:**\n1. On unperturbed graphs, MRGC does not always outperform baseline condensation methods (e.g., GCOND), and occasionally performs worse (Table 1), raising concerns about trade-offs.\n2. Classifier complexity measure is heuristic. While the entropy-margin loss is intuitive, there’s no formal link to generalization bounds or complexity measures from theory (e.g., VC-dim, Rademacher complexity).\n3. No analysis of why existing robust GNNs fail. The paper does not offer empirical or theoretical analysis of why prior defenses (e.g., Pro-GNN, R-GCN) underperform in graph condensation settings.", "was_revised": true, "final_justification": "I appreciate the authors’ rebuttal, which has successfully clarified the points I raised in my initial review.", "rebuttal": "We sincerely thank the reviewer for the detailed comments and insightful questions. Responses are as follows.\n\n---\n\n**W1:** MRGC does not consistently outperform baseline condensation methods (e.g., GCOND) on unperturbed graphs and occasionally performs worse (Table 1)\n\n**A1**: Thank you for your insightful review.\n\nThis is because trajectory-matching GC methods, such as SFGC and GEOM, **achieve significantly better performance on the clean Ogbn-Arxiv dataset compared to gradient-matching GC methods.** Moreover, they often shown bad robustness in other datasets like Cora and CiteSeer.\n\n---\n\n**W2 & Q2:** The classifier complexity measure is heuristic and lacks a formal connection to theoretical generalization bounds or complexity measures.\n\n**A2**: Thank you for your insightful review.\n\nThe ID, FDR, and FHC metrics quantify **data classification complexity**, which we observe to **increase significantly** in the condensed graph **under adversarial attacks on the original graph**.\n\n**Higher classification complexity** reflects **more intricate geometric properties** of the data, characterized by high intrinsic dimensionality and ambiguous class boundaries [1]. These complex geometric properties **indicate poor data quality and impose greater challenges for models to capture underlying data characteristics [2]**, ultimately **leading to performance degradation [3]**.\n\n**To mitigate this negative effect of classification complexity increasing**, we introduce regularization terms to **lower values to  benifits GC robustness**. And the experiments results demonstrate our proposed method.\n\n*[1] Complexity measures of supervised classification problems, TPAMI’02*\n\n*[2] Scaling laws from the data manifold dimension, JMLR’22*\n\n*[3] The effect of data complexity on classifier performance, Empirical Software Engineering’25*\n\n---\n\n**W3 & Q1:** The paper lacks analysis of why existing robust GNNs (e.g., Pro-GNN, R-GCN) fail under graph condensation settings.\n\n**A3**: Thank you for your insightful review.\n\nExisting popular robust GNN can be roughly categorized into the following types[1], each with its limitations:\n\n- Adversarial Training: **GC training process differs significantly from standard GNN training** and lacks a complete training framework, **preventing direct application**.\n- Attention Mechanism: Attention-based GNNs (e.g., GAT) **exhibits bad performance even in clean GC settings** [2], rendering them ineffective for improving GC robustness.\n- Graph Preprocessing: This method can be integrated into the GC, and **we has already included them as baselines.**\n\n*[1] Trustworthy graph neural networks: Aspects, methods, and trends, Proc‘24*\n\n*[2] GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights, NeurIPS’24*\n\n---\n\n**Q3**: Does the added regularization harm clean accuracy, and how does MRGC compare to baseline condensation methods without perturbation?\n\n**A5**: Thank you for your insightful review.\n\nThe performance on clean GC are shown below:\n\n| **Dataset(ratio)** | **Cora(1.30%)** | **CiteSeer(0.90%)** | **PubMed(0.08%)** |\n| --- | --- | --- | --- |\n| GCond | **80.85** | 69.41 | 75.93 |\n| SGDD | 80.29 | 70.52 | 75.91 |\n| GCDM | 80.26 | 71.27 | 72.56 |\n| SFGC | 79.55 | 70.27 | 73.92 |\n| GEOM | 78.52 | 69.53 | 73.83 |\n| RobGC | 78.95 | 69.2 | 75.40 |\n| **MRGC(ours)** | 80.43 | **71.77** | **76.83** |\n\nAs shown, our proposed MCGC **maintains strong performance even on clean original graphs**, achieving best results among all baselines on both CiteSeer and PubMed datasets."}, {"review_id": "FTvp7eIa5s", "reviewer": "Reviewer_6kqs", "summary": "The paper introduces MRGC, a manifold-constrained robust graph-condensation framework. By combining theoretical insights into intrinsic dimension reduction with three complementary manifold learning modules and extensive benchmarking, the study tackles the largely unexplored problem of making graph condensation resilient to attacks.", "questions": "1. I would like to ask for a clearer explanation of the assumptions behind Theorem 1. Could the authors provide empirical or theoretical evidence showing that these assumptions hold in real-world graph condensation scenarios?  \n2. The validity of Theorem 2 relies on both Theorem 1 and Assumption 4. I am not fully convinced by the logical connection in the proof. Could the authors walk through how exactly the conclusion follows from the assumptions, especially in light of the probability inconsistency mentioned in the proof?  \n3. I find it difficult to see how Corollary 6 from [54], which is based on linear classifiers, can be directly extended to general graph learning models. Could the authors clarify why this is justified and whether there are any intermediate theoretical results supporting this leap?  \n4. I appreciate the authors’ effort in connecting graph condensation with intrinsic dimension. However, I wonder whether introducing manifold metrics like curvature and class overlap is truly necessary. Have the authors considered whether simpler alternatives could be similarly effective?  \n5. The full pipeline seems overly complex for practical deployment. Have the authors conducted experiments to isolate the contribution of each module? I would like to know if the curvature and decoupling modules are strictly necessary beyond the ID module.  \n6. The motivation for introducing manifold constraints appears theoretical. Could the authors offer more practical insights or empirical observations to support the decision to use all three manifold metrics?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Pros**\n1. This paper aims to address a cutting-edge problem.\n2. The figures in this paper are visually appealing and well-designed.\n\n**Cons**  \n1. At lines 130 and onwards, Theorem 2 lacks a precise definition of “graph under attack”; both the attacker’s capabilities and objectives remain unspecified, and no threat model is provided.  \n2. In the proof of Theorem 2 (around line 525), the inequality $P(g_{\\Phi_{*}'}(n_c)) < P(g_{\\Phi'}(n_c))$ violates probability axioms and its derivation from Assumption 4 is unclear.  \n3. The use of Corollary 6 from reference [54] (manuscript Eq. 17) is stretched: the corollary is valid only for linear classifiers, yet the manuscript applies it directly to general graph learning models without justification; citing [51] for Assumption 2 does not fix this gap because [51] is unrelated to graph learning.  \n4. Because Theorem 2 rests on Theorem 1, and Theorem 1 depends on assumptions of doubtful realism, the entire theoretical foundation of MRGC may be fragile.  \n5. Even assuming Theorem 2 is correct, the key motivation on lines 133 and 134 “protecting the key ID decreasing characteristic of GC” is insufficiently dialectical; malicious actors could perform adaptive attacks that deliberately seek condensation schemes with lower ID.  \n6. The practical need for full manifold metrics is debatable: intrinsic dimension is helpful, but introducing curvature and class overlap terms makes the pipeline complex; the manuscript gives no evidence that simpler surrogate measures would fail.  \n7. Equation 22 overruns the page margin, violating layout guidelines.  \n8. The proposed pipeline is difficult to deploy in practice; aside from the ID estimation module, the necessity of the curvature and decoupling components is not convincingly motivated.  \n\n**Justification for the rating**\nThe robustness of graph condensation is indeed a highly cutting-edge research topic, and NeurIPS, as one of the most prominent conferences, should actively embrace contributions in this direction. However, this paper presents several critical and unavoidable issues. The theoretical foundation is not sufficiently solid, and the complex pipeline introduced lacks adequate motivation. Among the three core components, only the first one that computes the intrinsic dimension appears necessary, while the other two lack justification. In practice, it would be very difficult to deploy such a complex method. Based on these observations, the overall contribution remains limited.", "was_revised": true, "final_justification": "The authors have clarified my earlier misunderstanding, and I have updated my score to “accept”.", "rebuttal": "We sincerely thank you for the helpful comments and insightful questions! \n\n---\n\n**W1:** Theorem 2 lacks a clear definition of attack and the attacker’s goals or capabilities.\n\n**A1**: Thank you for your insightful review!\n\nWe define the “graph under attack” as follows threat model on the original graph:\n\n**Threat Model: (1) Attack’s goal**: Let $\\mathcal{G}\\_\\* = (\\mathbf{Y}\\_\\*, \\mathcal{E}\\_\\*, \\mathbf{X}\\_\\*)$ denote the attacked version of the original graph  $\\mathcal{G} = (\\mathbf{Y}, \\mathcal{E}, \\mathbf{X})$ , where the attacker may modify the edges $\\mathcal{E}$, the features $\\mathbf{X}$, the training labels $\\mathbf{Y}$. The attacker’s goal is to degrade the performance of GNNs trained on $\\mathcal{G}\\_\\*$ by increasing classification error. **(2) Attacker’s capability**: We adopt the white‑box threat model from prior work (e.g., RPBCD [1]), and the adversary perturbs graphs under a fixed budget.\n\nWe will revise the manuscript to explicitly include this definition.\n\n---\n\n**W2 & Q2:** In Theorem 2, the derivation of the inequality $P(g_{\\Phi^{\\prime}\\_\\*}(n_c)) < P(g_{\\Phi^{\\prime}}(n_c))$ from Assumption 4 is unclear.\n\n**A2**: Thank you for your insightful review!\n\nWe clarify as follows:\n- **Two probabilities**\n    1. $P(g_{\\Phi'}(n_c)=l_c)$ denotes the probability that the classifier $g_{\\Phi^{\\prime}}$ (trained on the **clean condensed graph $G^{\\prime}$**)  correctly assigns label $l_c$ to node $n_c$, when **the clean origin graph $G$ is clean**\n    2. $P(g_{\\Phi_*^{'}}(n_c)=l_c)$ denotes the probability that the classifier $g_{\\Phi^{\\prime}\\_\\*}$ (trained on the **attacked condensed graph $G^{\\prime}_{*}$**)  correctly assigns label $l_c$ to node $n_c$, when **the origin graph $G_{*}$ is attacked**\n- **State Assumption 4 clearly**\n    \n    *Assumption 4. Adversarial attacks in the original graph will lead to a decrease in the quality of the condensed graph*\n    \n    In other words, if you perform condensation on an attacked graph, **the resulting synthetic graph will be of lower quality for node classification** than one generated from the clean graph\n    \n- **Link Assumption 4 to the inequality**\n    \n    Under Assumption 4, the probability of assigning the correct label decreases when the graph is attacked. Formally, $P(g_{\\Phi_*^{\\prime}}(n_c)=l_c)<P(g_{\\Phi'}(n_c)=l_c)$\n    \n\n**We will make the notation and expressions more precise in the revision!** \n\n---\n\n**W3 & W4 & Q3:** Application of Corollary 6 from [54] is questionable\n\n**A3**: Thank you for your insightful review!\n\nWe clarify as following:\n\n- **Why our theorem can still reflects ID variation in GC?**\n    \n    To clarify, **the collary in [54] applies to any linear classifier: as long as attacks cause the linear GNN (e.g., SGC) trained on the condensed graph to have decreased performance, the condensed graph’s ID increases under attacks** (no matter which GNN was used to synthesize the condensed graph). Therefore, our theorem still explains the observed ID variation in the condensed graph.\n    \n- **Concerns with Linear GNN Classifiers**\n    1. **Linear GNNs** without nonlinear activation **are the most widely used and effective setting in GC**. GCond [4], SGDD [5], SFGC [6]  and so on[7-9] adopt the linear GNN backbone,  and linear GNN like SGC is recognized as the top performer in GC[7–9].\n    2. Prior works[13] show that GNNs without nonlinear functions yields comparable performance. In practice, linear GNNs like SGC is more effective in GC. **With linear GNN backbone, our MRGC enhances robustness while maintaining performance on clean graphs**, as shown below:\n        \n        \n        | **Clean Graph** | **Cora(1.30%)** | **CiteSeer(0.90%)** | **PubMed(0.08%)** |\n        | --- | --- | --- | --- |\n        | GCond | **80.8** | 69.4 | 75.9 |\n        | SGDD | 80.2 | 70.5 | 75.9 |\n        | GCDM | 80.2 | 71.2 | 72.5 |\n        | SFGC | 79.5 | 70.2 | 73.9 |\n        | GEOM | 78.5 | 69.5 | 73.8 |\n        | RobGC | 78.9 | 69.2 | 75.4 |\n        | **MRGC** | 80.4 | **71.7** | **76.8** |\n- **Why linear GNN like SGC a linear classifier?**\n    \n    SGC removes activations and collapses multiple weight matrices into one[2]. After $K$propagation steps, resulting  $\\mathbf{S}^K \\mathbf{X},\n    \\mathbf{S} = D^{-\\frac12} A D^{-\\frac12}$. The smoothed features are then passed through a single weight matrix $\\Theta$ and a softmax, $\\hat{\\mathbf{Y}}=\\text{softmax}(\\mathbf{S}^K \\mathbf{X},\\Theta),$ which is a linear step (*Softmax relies solely on an affine transformation of the inputs, so it remains a linear classifier[3]*). **Because both the propagation $\\mathbf{S}^K$and the final weight multiplication $\\Theta$ are linear, SGC is equivalent to a linear classifier[2].** \n    \n- **Why is our theorem coverage most GC scenarios?**\n    \n    **Linear GNN like SGC is the most-widely adopted GNN backbone in GC[4,5,6,7,8,9]**, outperforming GAT or Graphormer due to their efficiency and stable training[7,8,9]. **To our knowledge, these nonlinear attention-based GNNs typically offer bad performance in GC**[7,8,9].\n    \n- **Impact and contributions of our theorem.**\n    \n    **To our knowledge, we are the first to theoretically connect ID to GC.** This insight motivates our empirical investigation, as shown in Figure 1(c), condensation lowers the ID of the condensed graph, while attacks disrupt this reduction.\n    \n\n**We will revise the manuscript to more explicitly state the scope and meaning of our theorem**. Really appreciate the feedback and believe it will help strengthen the paper’s clarity!\n\n---\n\n**W5:** Preventing ID reduction in GC is superficial; attackers can design schemes with a lower ID.\n\n**A4**: Thank you for your insightful review!\n\n- **Scope of Existing Attacks**\n    \n    Our focus is on **existing graph attacks**, to the best of our knowledge, **no existing attacks explicitly target reduced ID** as an attack objective.  As such, our proposed method **offers effective defense against the majority of existing attacks**.\n    \n- **Difficulty of ID-Targeted Attacks**\n    \n    Moreover, we argue that crafting adversarial examples with **lower ID may even degrade attack success**. Recent studies[10] suggest that adversarial examples tend to exhibit high ID. \n    \n\n---\n\n**W6 & W8 & Q4 & Q5 & Q6:** Whether the curvature and class overlap are necessary, and the motivation behind these two modules is unclear.\n\n**A5**: Thank you for your insightful review!\n\n- **Our motivation**\n    \n    In Figure 1(c), we observe that the **classification complexity increases significantly** in the condensed graph **under attacks on the original graph**. **According to classification complexity theory [12],** classification complexity arises from **three main factors: (1) Intrinsic Dimension, (2) Class Overlap, and (3) Class Boundaries.** Based on theory, we introduced three modules to solve three aspects, respectively.\n    \n- **Why ID doesn’t fix curvature or overlap?**\n    \n    Even if the data lie on a low‑dimensional manifold, individual class clusters can still overlap or form highly non‑linear, wiggly boundaries along that manifold. \n    \n    **A specific example:** Imagine two interleaved spiral classes in 2D. You could project them onto a 1D line, yet on that line, the class points still heavily overlap.\n    \n- **Empirical Analysis**\n    \n    To further investigate these two modules’ roles, we adopt MRGC with only the ID module, as shown below:\n    \n    |  | **Cora(1.30%)** |  | **CiteSeer(0.90%)** |  |\n    | --- | --- | --- | --- | --- |\n    |  | Acc | Gap | Acc | Gap |\n    | MRGC | 77.4 | / | 65.1 | / |\n    | MRGC(w/o ID) | 72.2 | -5.1 | 60.9 | -4.1 |\n    | MRGC(w/o Curvature) | 76.0 | -1.4 | 64.5 | -0.5 |\n    | MRGC(w/o Decoupling) | 75.7 | -1.6 | 64.7 | -0.3 |\n    | MRGC(only ID) | 74.7 | -2.7 | 63.9 | -1.1 |\n    \n    As shown, while the ID module contributes primarily, **the other two also play roles in performance.** The MRGC with only ID module has a **performance gap -2.7% in Cora and -1.1% in CiteSeer.**\n    \n\n---\n\n**W6 & Formatting:** Equation 22 & Figure 2 formatting.\n\n**A6**: Thank you for the advice. We will revise Equation 22 to ensure it stays within the margin and make sure the upper part of Figure 2 achieves a balanced layout.\n\n---\n\n**Q1:** Clearer explanation of the assumptions behind Theorem 1.\n\n**A7**: Thank you for your insightful review\n\n- Assumption 1 is grounded in empirical findings and established targets in GC, where condensed graphs consistently preserve performance when used to train GNNs [7,8,9].\n- Assumption 2 adopts a widely used analytical simplification: decomposing multi-class classification into independent binary classification tasks. It’s an analysis method applicable to broad machine learning.\n- Assumption 3 involves modeling with an idealized optimal classifier to enable tractable theoretical derivations.\n\n---\n\n*[1] Robustness of graph neural networks at scale, Neurips*\n\n*[2] Simplifying Graph Convolutional Networks, ICML*\n\n*[3] The elements of statistical learning: data mining, inference, and prediction, Springer*\n\n*[4] Graph condensation for graph neural networks, ICLR*\n\n*[5] Does graph distillation see like vision dataset counterpart, NeurIPS*\n\n*[6] Structure-free graph condensation: From large-scale graphs to condensed graph-free data, NeurIPS*\n\n*[7] GC-Bench: An Open and Unified Benchmark for Graph Condensation, NeurIPS*\n\n*[8] GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights, arXiv*\n\n*[9] GCondenser: Benchmarking Graph Condensation, arXiv*\n\n*[10] High Intrinsic Dimensionality Facilitates Adversarial Attack: Theoretical Evidence, TIFS*\n\n*[11] How complex is your classification problem? a survey on measuring classification complexity, CSUR*\n\n*[12] Statistical Approaches to Combining Binary Classifiers for Multi-Class Classification, Neurocomputing*\n\n*[13] Graph neural networks exponentially lose expressive power for node classification*"}]

Author rebuttal:

Meta-review: The paper introduces a manifold-constrained framework for robust graph condensation that addresses the vulnerability of condensed graphs to adversarial perturbations. All reviewers agree that the work addresses an important and underexplored problem, which offers novel theoretical insights, and extensive experiments demonstrate robustness gains. Initial concerns include the scope of attacks, clarity of the theory, necessity of individual modules, possible trade-offs on clean graphs, etc. The rebuttal provides additional experiments, clearer definitions, and in-depth justifications. Reviewers acknowledge these clarifications in their follow-up. Overall, it is concluded that the paper is technically solid, clearly presented, and makes a valuable contribution.
Decision: Accept (spotlight)