Robust Graph Condensation via Classification Complexity Mitigation

We sincerely thank you for the helpful comments and insightful questions!

---

W1: Theorem 2 lacks a clear definition of attack and the attacker’s goals or capabilities.

A1: Thank you for your insightful review!

We define the “graph under attack” as follows threat model on the original graph:

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.

We will revise the manuscript to explicitly include this definition.

---

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.

A2: Thank you for your insightful review!

We clarify as follows:

• Two probabilities

  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
  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

• State Assumption 4 clearly

  Assumption 4. Adversarial attacks in the original graph will lead to a decrease in the quality of the condensed graph

  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

• Link Assumption 4 to the inequality

  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)$

We will make the notation and expressions more precise in the revision!

---

W3 & W4 & Q3: Application of Corollary 6 from [54] is questionable

A3: Thank you for your insightful review!

We clarify as following:

• Why our theorem can still reflects ID variation in GC?

  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.

• Concerns with Linear GNN Classifiers

  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].

  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:

     Clean Graph	Cora(1.30%)	CiteSeer(0.90%)	PubMed(0.08%)
     GCond	80.8	69.4	75.9
     SGDD	80.2	70.5	75.9
     GCDM	80.2	71.2	72.5
     SFGC	79.5	70.2	73.9
     GEOM	78.5	69.5	73.8
     RobGC	78.9	69.2	75.4
     MRGC	80.4	71.7	76.8

• Why linear GNN like SGC a linear classifier?

  SGC removes activations and collapses multiple weight matrices into one[2]. After $K$propagation steps, resulting $\mathbf{S}^K \mathbf{X}, \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].

• Why is our theorem coverage most GC scenarios?

  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].

• Impact and contributions of our theorem.

  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.

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!

---

W5: Preventing ID reduction in GC is superficial; attackers can design schemes with a lower ID.

A4: Thank you for your insightful review!

• Scope of Existing Attacks

  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.

• Difficulty of ID-Targeted Attacks

  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.

---

W6 & W8 & Q4 & Q5 & Q6: Whether the curvature and class overlap are necessary, and the motivation behind these two modules is unclear.

A5: Thank you for your insightful review!

• Our motivation

  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.

• Why ID doesn’t fix curvature or overlap?

  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.

  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.

• Empirical Analysis

  To further investigate these two modules’ roles, we adopt MRGC with only the ID module, as shown below:

  	Cora(1.30%)		CiteSeer(0.90%)
  	Acc	Gap	Acc	Gap
  MRGC	77.4	/	65.1	/
  MRGC(w/o ID)	72.2	-5.1	60.9	-4.1
  MRGC(w/o Curvature)	76.0	-1.4	64.5	-0.5
  MRGC(w/o Decoupling)	75.7	-1.6	64.7	-0.3
  MRGC(only ID)	74.7	-2.7	63.9	-1.1

  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.

---

W6 & Formatting: Equation 22 & Figure 2 formatting.

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.

---

Q1: Clearer explanation of the assumptions behind Theorem 1.

A7: Thank you for your insightful review

• 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].
• 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.
• Assumption 3 involves modeling with an idealized optimal classifier to enable tractable theoretical derivations.

---

[1] Robustness of graph neural networks at scale, Neurips

[2] Simplifying Graph Convolutional Networks, ICML

[3] The elements of statistical learning: data mining, inference, and prediction, Springer

[4] Graph condensation for graph neural networks, ICLR

[5] Does graph distillation see like vision dataset counterpart, NeurIPS

[6] Structure-free graph condensation: From large-scale graphs to condensed graph-free data, NeurIPS

[7] GC-Bench: An Open and Unified Benchmark for Graph Condensation, NeurIPS

[8] GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights, arXiv

[9] GCondenser: Benchmarking Graph Condensation, arXiv

[10] High Intrinsic Dimensionality Facilitates Adversarial Attack: Theoretical Evidence, TIFS

[11] How complex is your classification problem? a survey on measuring classification complexity, CSUR

[12] Statistical Approaches to Combining Binary Classifiers for Multi-Class Classification, Neurocomputing

[13] Graph neural networks exponentially lose expressive power for node classification

We sincerely appreciate your supportive feedback.

Thank you again for your time, your insightful suggestions, and for recognizing the contributions of our work!

We sincerely thank the reviewer for the detailed comments and insightful questions. Responses are as follows.

---

W1: MRGC does not consistently outperform baseline condensation methods (e.g., GCOND) on unperturbed graphs and occasionally performs worse (Table 1)

A1: Thank you for your insightful review.

This 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.

---

W2 & Q2: The classifier complexity measure is heuristic and lacks a formal connection to theoretical generalization bounds or complexity measures.

A2: Thank you for your insightful review.

The 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.

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].

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.

[1] Complexity measures of supervised classification problems, TPAMI’02

[2] Scaling laws from the data manifold dimension, JMLR’22

[3] The effect of data complexity on classifier performance, Empirical Software Engineering’25

---

W3 & Q1: The paper lacks analysis of why existing robust GNNs (e.g., Pro-GNN, R-GCN) fail under graph condensation settings.

A3: Thank you for your insightful review.

Existing popular robust GNN can be roughly categorized into the following types[1], each with its limitations:

• Adversarial Training: GC training process differs significantly from standard GNN training and lacks a complete training framework, preventing direct application.
• Attention Mechanism: Attention-based GNNs (e.g., GAT) exhibits bad performance even in clean GC settings [2], rendering them ineffective for improving GC robustness.
• Graph Preprocessing: This method can be integrated into the GC, and we has already included them as baselines.

[1] Trustworthy graph neural networks: Aspects, methods, and trends, Proc‘24

[2] GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights, NeurIPS’24

---

Q3: Does the added regularization harm clean accuracy, and how does MRGC compare to baseline condensation methods without perturbation?

A5: Thank you for your insightful review.

The performance on clean GC are shown below:

As shown, our proposed MCGC maintains strong performance even on clean original graphs, achieving best results among all baselines on both CiteSeer and PubMed datasets.

We sincerely thank you for the detailed comments and insightful questions! Responses are as follows.

---

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.

A1: Thank you for your insightful review. We 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.

As 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.

---

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.

A2: Thank you for your insightful review.

• 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.

• 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.

• 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.

• 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:

  	Cora(1.30%)		CiteSeer(0.90%)
  	Acc	Gap	Acc	Gap
  MRGC	77.43	/	65.12	/
  MRGC(w/o Curvature)	76.01	-1.42	64.57	-0.55
  MRGC(w/o Decoupling)	75.77	-1.66	64.78	-0.34

  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.

[1] How complex is your classification problem? a survey on measuring classification complexity. CSUR’19

[2] Complexity measures of supervised classification problems. TPAMI’02

---

W3: A more precise or formal explanation of the manifold would clarify the intuition and theoretical basis.

A3: Thank you for your insightful review.

We clarify its definition as follows:

$\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}\'.

[1] Intrinsic dimension of data representations in deep neural networks, Neurips’19

[2] Low dimensional manifold model for image processing, SIAM Journal on Imaging Sciences’17

---

W4: In Tables 1 and 2, including performance without condensation would help assess GC’s effectiveness under different attacks.

A4: Thank you for your insightful review.

The results corresponding to Tables 1 (Performance comparison under different condensation ratios when the training graph is corrupted) without graph condensation are provided below:

The results corresponding to Tables 2 (Performance comparison under different attack budgets when the training graph is corrupted) without graph condensation are provided below:

As 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).

---

W5 & L1: The limitations discussion is considered insufficient.

A5: Thank you for your insightful review.

Here, 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.

We sincerely thank you for the detailed comments and insightful questions! Responses are as follows.

---

W1 & L1: It's unclear whether MRGC hold under attacks like Nettack.

A1: Thank you for your insightful review.

We 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. To 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:

As shown in the table, MRGC consistently achieves the best robustness across all datasets under MetaAttack, outperforming both standard and robustness-aware baselines.

[1] Adversarial Attacks on Graph Neural Networks via Meta Learning. ICLR’19

---

L2: Tuning three hyperparameters via grid search adds computational overhead.

A2: Thank you for your insightful review.

While 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.