Enhancing Graph Classification Robustness with Singular Pooling

Conference: NeurIPS 2025 arXiv: 2510.22643 Code: GitHub Area: AI Safety / Graph Neural Network Robustness Keywords: GNN robustness, graph classification, pooling, adversarial attacks, singular value decomposition

TL;DR

This paper presents the first systematic analysis of how flat pooling operators (Sum/Avg/Max) affect adversarial robustness in graph classification. It derives adversarial risk upper bounds for each operator and proposes RS-Pool—a method that constructs graph-level representations from the dominant singular vector of the node embedding matrix—achieving significant robustness improvements without sacrificing clean accuracy.

Background & Motivation

Background: GNNs have demonstrated strong performance in graph representation learning, yet adversarial robustness research has predominantly focused on node classification, leaving graph classification comparatively underexplored. Existing defenses (GNNGuard, Jaccard preprocessing, GCORN, etc.) primarily target the message-passing stage.

Limitations of Prior Work: Graph classification requires aggregating node features into a graph-level representation via pooling, yet the impact of pooling operations on robustness has received virtually no attention. Different pooling strategies (Sum/Avg/Max) exhibit drastically different behavior under adversarial attacks, with performance strongly correlated with graph structure and attack type.

Key Challenge: Graphs in graph classification tasks tend to be small, meaning node-level defenses (e.g., node deletion) risk disrupting information propagation and degrading clean accuracy. A solution is needed that resists perturbations at the pooling stage while preserving expressive power.

Goal: (1) Quantify the effect of different pooling operators on graph classification robustness; (2) Design a pooling method that achieves both robustness and clean accuracy.

Key Insight: Matrix perturbation theory (Davis–Kahan / Wedin theorems) establishes that when the spectral gap is sufficiently large, the dominant singular vector remains stable under bounded perturbations—a property that can be exploited to construct robust graph-level representations.

Core Idea: Use the dominant right singular vector of the node embedding matrix \(H\) as the graph-level representation, which naturally filters out unstable components introduced by adversarial noise.

Method

Overall Architecture

• Input: Graph \(G=(V,E)\) with node features \(X\)
• Intermediate: \(L\) layers of GCN/GIN message passing produce node embedding matrix \(H \in \mathbb{R}^{n \times d}\)
• RS-Pool: Extracts the dominant right singular vector \(v_1\) from \(H\) and uses its scaled version as the graph-level representation
• Output: Classifier prediction on \(\tau v_1\)

Key Designs

1. Theoretical Analysis of Flat Pooling Robustness:

   • Function: Derives adversarial risk upper bounds for Sum/Avg/Max pooling under GCN
   • Mechanism (Theorem 4.2): Given an \(L\)-layer GCN with weight matrices \(W^{(\ell)}\), perturbation budget \(\epsilon\), and \(\hat{w}_u\) denoting the normalized walk sum of length \(L-1\) originating from node \(u\):
     • Sum pooling: \(\gamma = (\prod_\ell \|W^{(\ell)}\|) \sum_{u} \hat{w}_u \epsilon\)
     • Average pooling: \(\gamma = \frac{1}{n}(\prod_\ell \|W^{(\ell)}\|) \sum_{u} \hat{w}_u \epsilon\)
     • Max pooling: \(\gamma = \sqrt{\min\{n,d_L\}}(\prod_\ell \|W^{(\ell)}\|) \max_{u} \hat{w}_u \epsilon\)
   • Design Motivation: The Sum bound grows linearly with graph density (fragile); Average mitigates this by dividing by \(n\); Max depends only on the single highest-weight node (fragile when the attack target is clear, but potentially stronger under random attacks).

2. RS-Pool (Robust Singular Pooling):

   • Function: Generates a graph-level representation \(\tau v_1(H)\) from the dominant right singular vector \(v_1\) of \(H\)
   • Mechanism: Given \(H = U\Sigma V^\top\), RS-Pool maps \(H \mapsto \tau v_1(H)\), where \(\tau > 0\) is a scaling factor
   • Robustness Guarantee (Theorem 5.1):
   \[\gamma = \frac{\tau\sqrt{2}\epsilon}{\sigma_1 - \sigma_2} \left(\prod_{\ell=1}^L \|W^{(\ell)}\|\right) \sum_{u=1}^n (\hat{w}_u)^2\]

   Key insight: A larger spectral gap \(\sigma_1 - \sigma_2\) tightens the bound and strengthens robustness. - Design Motivation: Adversarial perturbations are typically low-rank and localized; the dominant singular direction is the most stable, while minor components are more susceptible to noise corruption.

3. Efficient Implementation via Power Iteration:

   • Function: Approximates the dominant singular vector without computing a full SVD
   • Mechanism: Compute \(S = H^\top H\), initialize \(v\) randomly, and iterate \(v \leftarrow Sv/\|Sv\|_2\) for \(K\) steps, then return \(\tau Hv\)
   • Complexity: \(O(K \times n \times d)\); convergence is typically reached within \(K = 2\)–\(5\) iterations due to the large spectral gap of GNN embeddings
   • Convergence rate is governed by \(\sigma_2/\sigma_1\): a smaller ratio yields faster convergence, creating a dual advantage—a large spectral gap implies both robustness and computational efficiency.

Controlling the Scaling Factor \(\tau\)

• Parameterized as \(\tau = \sigma_1(X)/\alpha\), where \(\alpha\) is tunable
• Corollary 5.2: Even when message-passing weight norms are large, \(\gamma' = \min\{\gamma, 2\tau\}\) yields a finite upper bound
• Increasing \(\alpha\) (decreasing \(\tau\)) reduces attack success rate, but clean accuracy is maximized at an intermediate value.

Key Experimental Results

Main Results: Clean and Attacked Classification Accuracy (GCN, \(\epsilon=0.3\))

Dataset	Attack	Sum	Average	Max	RS-Pool
PROTEINS	Clean	74.2±3.1	70.8±2.2	73.2±2.3	73.5±2.9
PROTEINS	PGD	45.8±2.9	34.2±2.1	28.2±3.5	51.9±3.6
PROTEINS	Random	68.3±3.1	65.7±2.3	42.9±4.1	70.4±3.1
D&D	Clean	75.1±0.6	70.1±0.5	74.1±0.6	74.6±0.7
D&D	PGD	6.7±2.0	12.6±3.6	8.7±5.2	30.4±3.2
D&D	Genetic	60.5±4.2	63.1±2.6	21.4±1.5	67.2±2.9
NCI1	Clean	70.6±0.8	67.9±1.6	68.2±1.2	70.1±1.2
NCI1	PGD	23.4±1.1	14.1±2.1	19.7±1.7	26.3±1.8

Comparison with Advanced Pooling Methods

Dataset	Attack	SAG	TopK-P	PAN-P	Sort-P	RS-Pool
PROTEINS	PGD	45.5±2.1	48.5±1.2	33.3±1.5	31.8±2.9	51.9±3.6
D&D	PGD	9.0±3.8	5.9±2.9	9.6±2.8	16.6±1.9	30.4±3.2
D&D	Genetic	62.5±2.8	57.7±0.6	56.1±3.6	57.7±4.3	67.2±2.9

Key Findings

• RS-Pool consistently outperforms or matches all pooling methods under all attack types, with negligible clean accuracy degradation
• The improvement under PGD attack on D&D is particularly striking: RS-Pool (30.4%) vs. Sum (6.7%) vs. Max (8.7%)
• Max pooling performs worst under Random/Genetic attacks due to its highly localized nature, confirming the theoretical analysis
• Experiments on the \(\alpha\) parameter validate theoretical predictions: increasing \(\alpha\) improves robustness at the cost of clean accuracy, with an optimal trade-off point

Highlights & Insights

• Robustness analysis from a pooling perspective fills an important gap: prior defenses focused exclusively on message-passing, overlooking the critical role of the final aggregation step
• The theory-to-method derivation chain is particularly elegant: deriving the vulnerabilities of each pooling bound → applying matrix perturbation theory → naturally arriving at RS-Pool
• Dual advantage of the spectral gap: a large \(\sigma_1 - \sigma_2\) simultaneously guarantees robustness (denominator in Theorem 5.1) and computational efficiency (faster power iteration convergence)
• RS-Pool is model-agnostic and can serve as a plug-and-play module replacing the pooling layer in any GNN

Limitations & Future Work

• Theoretical analysis is limited to GCN/GIN; attention-based GNNs such as GAT are not covered
• The analysis assumes a non-repeated dominant singular value (\(\sigma_1 \neq \sigma_2\)), which is rare in practice but leaves a theoretical gap
• Only edge perturbations (structural attacks) are considered; in-depth analysis of node feature attacks and joint attacks is absent
• The stability of the dominant SVD component on very small graphs is not thoroughly discussed

Related Work & Insights

• vs. GNNGuard: GNNGuard filters malicious edges during message-passing via attention mechanisms, operating at a different defense layer; RS-Pool complements it at the pooling stage, and the two can be combined
• vs. GCORN: GCORN stabilizes message-passing through orthogonal weight regularization; RS-Pool stabilizes pooling via spectral methods—the two approaches are complementary
• vs. Adversarial Training: Gosch et al. improve robustness by training on perturbed graphs, incurring high computational cost; RS-Pool requires no additional training overhead

Rating

• Novelty: ⭐⭐⭐⭐ First systematic robustness analysis from a pooling perspective in graph classification, with contributions in both theory and methodology
• Experimental Thoroughness: ⭐⭐⭐⭐⭐ Eight datasets, three attack types, and eight pooling variants compared—highly comprehensive
• Writing Quality: ⭐⭐⭐⭐⭐ Theoretical derivations are clear, with motivation, theory, method, and experiments forming a coherent chain
• Value: ⭐⭐⭐⭐ Offers a complementary defensive perspective and a practical plug-and-play solution with high applicability

Related Papers

• [NeurIPS 2025] Bridging Symmetry and Robustness: On the Role of Equivariance in Enhancing Adversarial Robustness
• [NeurIPS 2025] Stealthy Yet Effective: Distribution-Preserving Backdoor Attacks on Graph Classification
• [NeurIPS 2025] Robust Graph Condensation via Classification Complexity Mitigation
• [NeurIPS 2025] Improved Balanced Classification with Theoretically Grounded Loss Functions
• [NeurIPS 2025] Understanding and Improving Adversarial Robustness of Neural Probabilistic Circuits