RGDM: Robust Graph Diffusion Model
RGDM: Robust Graph Diffusion Model
The authors propose RGDM, which generates labeled synthetic nodes and edges on attacked graphs for enhancement; the authors state that under 25% Metattack, GCN improves by 13.9 percentage points on Cora.
The defender trains the generator on a graph already perturbed by Metattack, Nettack, Topology Attack, without access to a paired clean graph; in the adaptive evaluation the white box attacker knows the generator, edge mask, TNN regularization and downstream SG-GSR, and attacks the final augmented graph under the same absolute edge flip budget.
- Graph neural networks are susceptible to graph adversarial attacks such as Metattack, and existing node-level diffusion generation methods are not designed for learning a robust generator from an attacked graph. The authors aim to solve the problem of generating labeled synthetic nodes and edges on an attacked graph, for augmenting the robustness of semi-supervised node classification.
- RGDM consists of a Robust Graph Autoencoder (with an edge selection mechanism, a sparsification loss and truncated nuclear norm low-rank regularization of latent features, and a SHED sparse hierarchical edge decoder) and a Latent Diffusion Model with Classifier-Free Guidance; it generates labeled synthetic nodes and their edges, which are merged with the original attacked graph before training GCN, Pro-GNN or SG-GSR.
- Evaluated on Cora, Citeseer, Polblogs, and Pubmed with 10 runs: under 25% Metattack, RGDM(GCN) improves by 5.9–13.9 percentage points and RGDM(SG-GSR) improves by 1.0–2.6 percentage points; FND/FED are close to the clean reference; gains remain positive under adaptive attacks and on heterophilous graphs (Chameleon, Actor).
- The authors state that the method applies only to node-level graph data generation; Theorem 3.1 covers only bounded linear probes on fixed latent features, and end-to-end robustness is an empirical conclusion; adaptive attacks are tested with a fixed budget, and the authors state this does not constitute immunity to arbitrary adaptive attacks; joint generalization and robustness theory is listed as future work.
- Evaluated models
- RGDMGCNPro-GNNSG-GSRHANGLHS
- Benchmarks
- CoraCiteseerPubmedPolblogsChameleonActorogbn-arxivReddit
- Metrics
- AccuracyFNDFEDpaired gain ± paired SDp-valuewall clock time
The RGDM graph diffusion model generates clean synthetic node and edge structures on adversarially attacked graphs through an edge selection mechanism and low-rank regularization of latent features. The model consists of two parts, a Robust Graph Autoencoder (RGAE) and a Latent Diffusion Model (LDM), and the synthetic structures can be directly merged into a given graph. In semi-supervised node classification, GNNs trained by combining the original attacked graph with the synthetic structures show significantly improved robustness against multiple graph adversarial attacks. The code has been made public.
Paper analysis
What problem does this paper attempt to solve?
Robustly generate labeled synthetic nodes and edges on an attacked graph to enhance the adversarial robustness of semi-supervised node classification.
Core problem: how to train a robust node-level generator on a graph subjected to graph adversarial attacks, generating labeled synthetic graph structures (SGS) to improve the robustness of node classification.
- Setting and motivation: diffusion models have been used for data augmentation, but the authors state that extensions on graphs mainly target graph-level augmentation; node-level methods are mostly mix-up or GAN-based synthesis, and GAN training is unstable and the generated distribution does not match real data (citing [21]).
- Shortcomings of existing methods: the authors state that node-level diffusion methods DoG [19] and LR-FGDM [20] share the autoencoder + diffusion template, but do not train the generator for adversarial robustness; directly training an ordinary generator on an attacked graph reproduces the noise.
- Core observation: the motivation for low-rank regularization comes from the Low Frequency Property (LFP)—the authors state that in the evaluated latent space, label information is more concentrated in the leading feature directions than adversarial perturbations (Section F.1); Theorem 3.1 provides a conditional supplementary argument via the spectral complexity of bounded linear probes, but the authors explicitly state it is not a guarantee for downstream GNNs.
- Proposed in the paper: Robust Graph Diffusion Model (RGDM), composed of a Robust Graph Autoencoder (RGAE, containing an edge selection mechanism and low-rank regularization of latent features) and a Latent Diffusion Model (LDM); synthetic nodes and edges are generated and merged into the original attacked graph to form an augmented graph, then a GNN is trained.
- Threat model:
- Attacker goal: reduce node classification accuracy via Metattack (untargeted), Nettack (targeted), Topology Attack.
- Attacker knowledge: the main experiments are attack-first-then-defend; in the adaptive evaluation the white box attacker knows the generator, edge mask, TNN regularization and downstream SG-GSR (Section 4.5).
- Attacker capability: perturb edges and features according to a perturbation rate (Metattack/Topology Attack 0–25%) or budget (Nettack 1–5); the adaptive attack perturbs the final augmented graph under the same absolute edge flip budget.
- Victim system: node classifiers such as GCN, Pro-GNN, SG-GSR trained on the attacked graph; the defender does not use a paired clean graph when training RGDM.
What related research exists?
Related work falls into three groups: graph data augmentation, graph diffusion generation, and graph adversarial attack and defense; RGDM shares a template with DoG and LR-FGDM but places the robustness design in the generator.
Graph data augmentation
- Mix-up type (G-Mixup [8], Mixup [9], GraphMix [10], iGraphMix [12], NodeMixup [13], etc.)—augment labeled nodes via mix-up; the authors state such methods can improve GNN performance.
- GAN-based node/edge generation (ImGAGN [42], Graphsmote [43], SNS [45], etc.)—generate synthetic nodes and edges for node and edge imbalance; the authors cite work in the vision domain [21] stating that GAN training is unstable and the generated distribution matches real data poorly.
- Structure/feature/label modification type ([34–41])—modify graph structure, features or node labels for augmentation.
Graph diffusion generation
- Graph-level diffusion models ([3–7])—generate entire graphs; the authors state they mainly target graph-level augmentation.
- DoG [19]—node-level diffusion, using a Bi-Level Neighborhood Decoder (BLND) to reconstruct the observed neighborhood, and applying low-rank regularization to downstream GNNs.
- LR-FGDM [20]—uses a Hierarchical Graph Autoencoder (HGAE) plus prototypical regularization for few-shot node classification, followed by a low-rank transductive classifier.
- The paper points out the difference from these two: RGDM places edge selection, the sparsification objective and low-rank regularization inside the generator, the TNN penalty acts on the latent features used for diffusion, and SHED reconstructs only the selected sparse neighborhood rather than all observed edges.
Graph adversarial attacks and defenses
- Attacks: targeted (Nettack [50]) targets specific nodes, untargeted (Metattack [51], node injection [52]) reduces overall accuracy.
- Three defense categories: adversarial training [53, 54], graph processing/denoising [55–58], model robustification [59–65, 33] (including Pro-GNN [57], SG-GSR [33]).
- Diffusion purification (GDDM [28], DiffSP [29], etc. [28–32])—use diffusion for data/graph purification; the paper points out that purifying an observed graph and generating additional labeled nodes are different tasks, and graph-level purification methods do not provide RGDM's node-level augmentation interface.
Baselines and benchmarks: augmentation comparison baselines are iGraphMix, ImGAGN, Graphsmote, SNS, DoG, LR-FGDM, DDPM; backbone/defense baselines are GCN, GAT, RGCN, GCN-SVD, GraphBel, UAG, GCORNs, GADC, HANG, STABLE, Pro-GNN, SG-GSR; purification comparisons are GDDM, DiffSP. Benchmarks are Cora, Citeseer, Pubmed, Polblogs, plus Chameleon, Actor (heterophilous) and ogbn-arxiv, Reddit (large graphs).
The authors position this paper as: sharing the autoencoder + diffusion architecture with DoG and LR-FGDM, but aimed at adversarially robust learning of the generator, and state that RGDM is the first robust graph diffusion model designed for generating synthetic graph structures for node classification (Conclusions original wording "marking the first robust graph diffusion model").
How does the paper address this problem?
RGAE uses edge selection and low-rank regularization to learn robust latent features, the LDM generates synthetic nodes by class in the latent space, SHED sparsely decodes edges, and after merging, downstream GNNs are trained.
Overall approach: first train a Robust Graph Autoencoder (RGAE) to encode node attributes and edges into latent features robust to perturbations, then in that latent space train a Latent Diffusion Model (LDM) with Classifier-Free Guidance (CFG) to generate synthetic node latent features by class, decode them into node attributes and edges and merge them into the original graph, and finally train GCN, Pro-GNN or SG-GSR on the augmented graph.
RGAE: Encoding and Edge Selection
- Neighborhood encoding: node attributes plus positional embeddings are aggregated through GAT layers, with attention computed only over observed neighbors; concatenating with the MLP output of node attributes gives latent features Zi.
- Edge selection mechanism: learn a binary mask S to select edges, trained with sigmoid relaxation and binary Gumbel Softmax, gradients via a straight-through estimator, τ = 0.5; the mask only changes the generator's training representation, not the original adjacency matrix retained by downstream augmentation.
- SHED decoder: first use balanced K-means to partition nodes into K balanced clusters (cluster capacity M = ⌈N/K⌉), separately reconstruct the inter-cluster neighbor graph C and the intra-cluster neighbor graph M; at generation time only decode activated clusters, drawing on classifier-free guidance's cluster index embedding. The authors state it avoids globally scoring every candidate neighbor, and the reconstructed neighbor graph is sparse.
Optimization Objective and Low-Rank Regularization
- RGAE loss: LRGAE = LC + τS LS + τT |K|r0, where K := ZZ⊤ is the latent feature Gram matrix and |K|r0 is the truncated nuclear norm (TNN, sum of tail eigenvalues). The consistency loss LC constrains attribute and hierarchical edge reconstruction, and the sparsification loss LS suppresses nonzero reconstruction outside the selected sparse neighborhood.
- Motivation for low-rank regularization: the authors state that adversarial perturbations mostly reside in high-rank residual components while clean signals reside in a low-rank subspace; unlike existing approaches that reduce the rank of the adjacency matrix, this penalty acts on the diffusion latent features. Initial rank r0 = ⌈γq⌉, with γ selected by 5-fold cross-validation over {0.1,…,0.9}.
- Theorem 3.1: gives a transductive generalization bound for bounded linear probes on fixed latent features Z, with a smaller complexity term as the spectral tail is smaller; the authors explicitly state that this theorem does not cover class-conditional generation, label-dependent adaptive attacks, or downstream GNNs, and that the latter connection is empirical.
Latent-Space Conditional Generation
- LDM + CFG: train a class-conditional LDM (label dropout) on the labeled node latent features encoded by RGAE, generating N0 synthetic node latent features per class, N′ = CN0 in total.
- Augmented graph construction: synthetic nodes only connect to original graph nodes; no edges are generated between synthetic nodes; the adjacency matrix is block-structured, the original attacked adjacency block A is preserved as-is, and the label set incorporates the synthetic node labels.
Training Procedure and Downstream Training
- Two-stage training (Algorithm 1): first train RGAE (first pretrain with only the consistency loss for 2000 epochs, then optimize the full loss for 1000 epochs, Adam, lr 0.001, weight decay 1e-5; fix the mask for warm-up in the first 100 epochs), then train the LDM for 3000 epochs (Adam, lr 0.0002).
- Generation and training (Algorithm 2): the LDM samples synthetic node latent features, the RGAE decoder decodes them into attributes and edges, forming the augmented graph, then downstream GNNs are trained; the number of synthetic nodes N′ is selected by cross-validation from 1×|VL| to 10×|VL|.
- Complexity: TNN is computed from the singular values of Z, O(N D′²); SHED inference complexity is O(KD′ + di D′ M), which the authors state is lower than the global decoder's O(D′KM).
What experiments did the paper conduct?
Four benchmarks, three attacks, 10 runs: RGDM improves accuracy for all backbones, with the largest gains on GCN and smaller but consistent gains on SG-GSR.
Experimental Setup
- Backbones tested: GCN, Pro-GNN, SG-GSR (main tables), with HANG and LHS (heterophilous) additionally in the appendix; baselines include GAT, RGCN, GCN-SVD, GraphBel, UAG, GCORNs, GADC, STABLE.
- Datasets: Cora, Citeseer, Pubmed, Polblogs (Table 9 gives sizes, e.g., Pubmed 19,717 nodes); heterophilous graphs Chameleon and Actor; large graphs ogbn-arxiv and Reddit.
- Attacks: Metattack (perturbation rate 0–25%, Meta-Self/A-Meta-Self), Nettack (budget 1–5, sampling 10% of target nodes), Topology Attack (0–25%); improved DICE for large graphs.
- Metrics and statistics: mean accuracy ± marginal SD, 10 runs; in paired evaluation, the backbone and the enhanced version share the same perturbed graph under the same attack seed, and the paired gain ± paired SD is reported (Table 26); significance is a two-sided paired t-test (9 degrees of freedom), and Table 27 gives the reported significance levels.
- Fidelity metrics: FND (features extracted by a pretrained GCN) and FED (features extracted by a pretrained NBFNet), averaged over 10 random splits of the clean-graph benchmark split.
- Number of synthetic nodes: selected by cross-validation (Tables 18–20), e.g., under 25% Metattack all Cora backbones use 5×|VL|.
Main Results
According to Table 1 (Metattack, accuracy %, enhancement gain in parentheses):
Swipe horizontally to read the table
Dataset Perturbation rate GCN → RGDM(GCN) Pro-GNN → RGDM(Pro-GNN) SG-GSR → RGDM(SG-GSR) Cora 25% 47.5 → 61.4 (↑13.9) 69.7 → 72.3 (↑2.6) 77.8 → 79.1 (↑1.3±0.3) Citeseer 25% 56.9 → 62.8 (↑5.9) 69.0 → 70.2 (↑1.2) 72.7 → 75.3 (↑2.6±0.4) Polblogs 25% 49.2 → 56.5 (↑7.3) 63.2 → 66.9 (↑3.7) 87.8 → 88.8 (↑1.0±0.3) Pubmed 25% 75.5 → 81.5 (↑6.0) 86.8 → 87.6 (↑0.8) 87.2 → 88.6 (↑1.4±0.3) Cora 15% 65.1 → 69.4 (↑4.3) 76.4 → 78.3 (↑1.9) 78.5 → 80.0 (↑1.5±0.3) Pubmed 0% (clean) 87.2 → 88.1 (↑0.9) 87.3 → 88.4 (↑1.1) 87.7 → 90.3 (↑2.6) - The authors state that under 25% Metattack the paired gains of SG-GSR are 1.3/2.6/1.0/1.4 percentage points (Cora/Citeseer/Polblogs/Pubmed), "modest but consistent" relative to the strong backbone; the large gains over GCN do not represent gains over SG-GSR.
- RGDM also improves on clean graphs (0% perturbation) (GCN improves by 1.7/1.7/0.4/0.9 points), and the authors use this to point out that the enhancement benefit also exists when there are no adversarial edges to filter.
- Nettack (Table 2) and Topology Attack (Table 12) show the same trend; Table 27 reports significance levels at the strongest budget as Metattack 0.006–0.008, Nettack 0.005–0.006, Topology Attack 0.006–0.007.
Comparison with Other Enhancement Methods and DoG
- Enhancement method comparison (Table 4, 25% Metattack, GCN fixed): RGDM(GCN) is 61.42/62.84/56.47/81.52 (Cora/Citeseer/Polblogs/Pubmed), higher than iGraphMix, ImGAGN, Graphsmote, SNS, DoG (59.40/60.10/54.70/79.20), and LR-FGDM (58.90/59.60/54.20/78.90); the authors state it is 2.02/2.74/1.77/2.32 points higher than DoG.
- Component-by-component comparison (Table 5, SG-GSR + 25% Metattack fixed): starting from DoG(BLND), adding edge selection gives +1.0/1.1/1.0/0.8 points, adding the latent-feature TNN gives a further +0.8/1.0/0.9/0.7 points, and switching to SHED gives a further +1.7/2.2/1.6/2.0 points; the authors note these are conditional increments along this sequence, not independent additive effects.
- Purification method comparison (Table 29, 25% Metattack, SG-GSR backbone): RGDM(SG-GSR) 79.1/75.3/88.8/88.6, higher than GDDM and DiffSP, with t-test p-values 0.0004–0.0022.
Fidelity, Heterophily, and Adaptive Attacks
- FND/FED (Tables 13–14, 25% Metattack): RGDM's FND is 8.16/4.44/4.35/3.95, with clean references 7.90/4.28/4.16/3.79; FED is 8.34/5.28/6.61/5.34, with clean references 8.03/5.10/6.31/5.15; all lower than DDPM and the enhancement baselines. The authors describe this as an empirical fidelity measure, and clean graphs are used only for evaluation, not training.
- Heterophilous graphs (Table 6, LHS backbone): under 25% perturbation, Chameleon 70.03 → 72.41 (+2.38), Actor 35.37 → 37.90 (+2.53); the authors state this supports the chosen soft penalty and does not mean that stronger rank reduction is always beneficial.
- Adaptive attacks (Table 7/34/35, white box, fixed absolute budget): when attacking the final enhanced graph, SG-GSR → RGDM(SG-GSR) is 74.8→77.8, 69.5→73.4, 84.7→87.6, 84.9→87.2; the variant with a differentiable edge-selection mask gains 2.4/3.2/2.2/1.7 points (SD and p-values not reported). The authors state that these fixed-budget tests do not establish immunity to arbitrary adaptive attacks.
Other Ablations and Analyses
- Sparsification loss and low-rank regularization ablation (Table 3, 25% Metattack, GCN): removing the sparsification loss lowers accuracy by 4.70/3.87/3.23/3.60 points; full RGDM is higher than the two comparison regularizers, weight orthogonality and low-rank adjacency.
- Large graphs (Table 21, improved DICE, GCN): ogbn-arxiv under 20% perturbation 54.95 → 56.17 (+1.22), Reddit 74.53 → 75.99 (+1.46); Table 22 shows that removing edge selection leaves gains of only 0.35/0.47 points.
- Number of synthetic nodes (Table 30, Pro-GNN, Cora 25%): best at 5×|VL| with 72.3, dropping to 71.2 at 10×|VL|.
- DDPM enhancement control (Table 31, Cora 25%): DDPM(Pro-GNN) 68.2 is lower than 69.7 without enhancement, and RGDM(Pro-GNN) is 72.3.
- Label ratio (Table 32, Cora 25%): RGDM(Pro-GNN) is higher than Pro-GNN at every level from 2.5% to 60%.
- Efficiency (Table 8/15, single A100): SHED makes RGAE training 153 vs 480 minutes on Pubmed (3.14×) and 452 vs 2511 minutes on ogbn-arxiv (5.56×); per-node generation is sped up 1.10×/3.27×, and the authors note this is not end-to-end generation or downstream inference speedup.
- Purification variants (Table 28, Cora 25%): RGDM(Purification) 71.0, RGDM(GDA) 72.3, the two combined 72.9 (Pro-GNN 69.7).
What are some points that can be further explored?
The authors state that the method is limited to node-level generation, that the theorem does not cover end-to-end robustness, and list joint generalization and robustness theory as future work.
Limitations and future directions noted by the authors
- Scope of applicability: the authors state that the proposed method applies only to node-level data generation on graph datasets (NeurIPS Checklist item 2 Limitations, pointing to the Introduction).
- Scope of the theorem: Theorem 3.1 addresses bounded linear probes on fixed latent features and independent random splits, and does not cover class-conditional generation, label-dependent adaptive attacks, or downstream GNNs; the authors state that the end-to-end connection is empirical (Section 3.2, Appendix B).
- LFP is an empirical property: the concentration of label information in the leading feature directions is an empirical observation on the evaluated latent kernel, not a universal property of attacked graphs, nor a theorem assumption (Section F.1).
- Scope of adaptive attacks: the fixed-budget adaptive test does not establish immunity to arbitrary white box attacks; the differentiable variant for edge selection is a gradient approximation, not a proof of globally optimal perturbation (Section 4.5, Appendix F.18).
- Future work: establish a joint generalization and robustness theory for data-dependent representation learning, class-conditional generation and downstream GNNs (last paragraph of Appendix B).
- Nature of the fidelity evidence: FND/FED being close to the clean reference is empirical fidelity evidence and does not guarantee that the generated structures are error-free (Section F.3).
Scope of experimental coverage
- The backbones tested are GCN, Pro-GNN, SG-GSR (main tables), with HANG and LHS additionally in the appendix; the datasets are Cora, Citeseer, Pubmed, Polblogs, plus Chameleon, Actor, ogbn-arxiv, Reddit, 8 in total.
- Attacks cover Metattack (0–25%), Nettack (budget 1–5), Topology Attack (0–25%), improved DICE (large graphs) and two adaptive Metattack variants; main results are mean ± SD over 10 runs.
- Significance testing is a paired t-test; paired SD is reported only for some rows of Metattack (Table 26), paired SD is not provided for Nettack and Topology Attack, and their significance retains the reported values (Section F.11).
- In the adaptive evaluation, the "differentiable with respect to edge selection" variant reports only mean accuracy, without standard deviation or p-values (Table 35).
- The paper does not report downstream GNN inference time; the timings in Table 15 cover only RGAE training and per-node generation.
Summarize the main content of the paper
RGDM trains a robust node-level diffusion generator on an attacked graph and augments downstream GNNs with synthetic graph structures, improving accuracy on all backbones.
A defense paper in the direction of graph adversarial robustness: using robust generative data augmentation to improve the accuracy of semi-supervised node classification under graph adversarial attacks.
- Problem: node-level diffusion generation methods (DoG, LR-FGDM) are not designed for learning a robust generator from an attacked graph; an ordinary generator will reproduce attack noise into the synthetic structure.
- Method: RGDM = RGAE (GAT encoding + learnable edge selection mask + truncated nuclear norm low-rank regularization of the Gram matrix of hidden features + SHED sparse hierarchical edge decoder) + class-conditional LDM with CFG; generates labeled synthetic nodes and their connecting edges and merges them into the original attacked graph (the original adjacency block is preserved), then trains GCN, Pro-GNN, or SG-GSR.
- Main results: under 25% Metattack, RGDM(GCN) improves by 5.9–13.9 percentage points on four datasets, and RGDM(SG-GSR) improves by 1.0–2.6 percentage points (paired gain ± paired SD, Table 1); on clean graphs there is also a 0.2–2.6 point improvement.
- Fidelity: under 25% Metattack, FND/FED on Pubmed are 3.95/5.34, close to the clean reference 3.79/5.15, and lower than DDPM and the various augmentation baselines (Tables 13–14).
- Other evidence: on the heterophilous graphs Chameleon/Actor the gains are 2.38/2.53 points (Table 6); under white box adaptive attacks the gains remain positive (Table 7); SHED speeds up RGAE training on Pubmed by 3.14× (Table 8).
- Authors' conclusions: the authors state that RGDM is the first robust graph diffusion model for synthetic graph structure generation for node classification, and that the augmentation consistently improves the accuracy of each backbone under three attacks; at the same time, the authors explicitly state that the gain magnitude on strong backbones is not large, that the theorem does not provide an end-to-end guarantee, and that the fixed-budget adaptive test does not constitute immunity to arbitrary attacks.