1) Definition and Measurement of Consistency and Diversity

The definitions of consistency and diversity [3], along with how to measure them, have already been provided in Supplementary Section B.8.3; however, we will revise the main paper to explicitly reference this section for clarity. Specifically, Consistency is measured as the test accuracy of the model trained on augmented data, reflecting how well the augmentation preserves task-relevant semantics, and Diversity is measured as the Frobenius norm of the difference between the prediction logits of the original and augmented models, capturing how much variation the augmentation introduces in the model’s outputs. For more details, please refer to Supplementary Section B.8.3.

2) Importance of Consistency and Diversity

Consistency and diversity [3, R5, R6] are used as key indicators for measuring augmentation quality. Consistency ensures that augmentations preserve task-relevant semantics, leading to stable predictions. Diversity encourages variations that expose the model to different structural or feature-level perturbations, promoting better generalization. While these objectives can indeed conflict (i.e., excessive diversity may harm consistency), an effective augmentation strategy must balance both to avoid overfitting to trivial perturbations or being too invariant to informative changes. In our work, we demonstrate that existing methods tend to lean towards one of these at the expense of the other (Figure 1b). In contrast, D-GDA is able to strike a good balance between both.

[R5] Juan, Xin, et al. "Multi-strategy adaptive data augmentation for Graph Neural Networks." Expert Systems with Applications 258 (2024): 125076.

[R6] Chen, Nan, et al. "Consistency training with learnable data augmentation for graph anomaly detection with limited supervision." The twelfth international conference on learning representations. 2024.

3) Ablation on different Choices of Target Sample Selection (TSS) Backbones

In D-GDA, TSS identifies difficult samples based on prediction entropy. To maintain consistency, we use the same backbone architecture in TSS as in the downstream model being evaluated. For example, when comparing D-GDA performance with a GCN backbone, we also use GCN within TSS; similarly, for GAT or GraphSAGE, the corresponding backbone is used in both components. The rationale behind this design is that each GNN backbone employs a different message passing mechanism, and as a result, a node that may appear difficult for one model may not be difficult for another architecture. Table 9 summarizes the results of using GCN, GAT, and GraphSAGE within the TSS module across multiple experiments. The findings show that the best performance is consistently achieved when the same backbone is used in both TSS and the downstream classifier, confirming the importance of the proposed choice of architecture in TSS.

Table 9: Ablation on different choices of TSS backbones.

4) Diffusion Model and Latent Diffusion Model (LDM) Computational Cost Comparison

Rombach et al. [R7] demonstrated that training a state-of-the-art diffusion model requires approximately 1000 V100 GPU-days, whereas training a Latent Diffusion Model (LDM) reduces this cost to just 271 V100 GPU-days, reflecting a 3.6× improvement in training time. This computational advantage of LDMs has been consistently highlighted in prior works such as [5, 20, 66]. We outline our rationale for adopting latent diffusion in Section 3.1.3 of the main paper. Specifically, Latent Diffusion Models (LDMs) offer a significantly more efficient and tractable alternative to applying diffusion directly in the raw feature space. Especially for graph data, training diffusion models in the raw feature space presents two key challenges: 1) **High-dimensional sparsity: ** Many graph datasets, such as Cora and Citeseer, contain sparse and high-dimensional feature vectors. Modeling directly in this space makes diffusion model training unstable and computationally expensive. 2) Structural complexity: Preserving both topological and semantic information during diffusion model training in the raw space demands more complex architectures and heavier training models, further increasing the resource burden.

To overcome these issues, our method applies diffusion in a compact latent space learned via our Graph Variational Autoencoder (GVAE). This latent representation captures the essential structural and feature-level information while significantly reducing dimensionality and sparsity. As a result, latent diffusion not only lowers computational cost but also enhances training stability and scalability. We will revise the manuscript to more clearly communicate this motivation to further strengthen the theoretical grounding of our design choice. In Table 14 main paper, removal of LDM resulted in reduced performance on three datasets.

[R7] Rombach, Robin, et al. "High-resolution image synthesis with latent diffusion models." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022.

5) Clarification between VGAE and GVAE

We cited VGAE [29] as it introduced the foundational concept of applying variational autoencoders to graph-structured data. However, our use of the term GVAE (Graph Variational Autoencoder) reflects a generalized and modified architecture beyond what VGAE originally proposed. Specifically, VGAE was designed for link prediction and employs a dot-product decoder that only reconstructs edge presence. In contrast, our GVAE includes two distinct decoders: a feature decoder that reconstructs node features, and an edge decoder that reconstructs edge connectivity. Please see Section 3.1.2 for more details.

We thank the respected reviewer for encouraging comments. To incorporate the suggestion of the respected reviewer, the third sentence in Section 3.1.2, is modified as : “Variational graph autoencoders learn expressive latent representations of graph data, capturing both node features and local structure [28,33,45]. Therefore, we employ a variant of this architecture for compact latent representation learning, resulting in reduced computational complexity and improved performance. Our GVAE consists of a GCN-based encoder and two decoders for node feature and edge reconstruction.”

1) Section 3 Revision

We have thoroughly revised the theoretical descriptions of TSS, GVAE, and LDM in the methodology section (Section 3) to improve the structure and understanding of the proposed D-GDA framework.

2a) LDM Convergence Proof

We provide a theoretical justification for the convergence of LDM in the D-GDA framework setting, which operates in label-free settings. Despite the inherent challenges of sparse graph supervision, we show that the denoising network in D-GDA converges to the true conditional score function, enabling it to sample augmentations from a neighborhood-aware latent distribution. Our analysis follows the foundational results from score-based generative modeling [20, R3, R4], adapted to the graph setting with local structural conditioning. Let $v_{i}$ denote a node in graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, with latent representation $z_{i}^{0} \in \mathcal(R)^{d}$ obtained from a Graph Variational Autoencoder (GVAE). We assume a standard DDPM-style forward process [20] that gradually corrupts $z_{i}^{0}$ with Gaussian noise. The reverse process aims to estimate the noise via a denoising network $\epsilon_{\theta}(z_{i}^{t}, t, c_{i}^{0})$, conditioned on a neighborhood-aware vector $c_{i}^{0}$. The model is trained with a score-matching loss ($\mathcal{L_{diff}}$). For details See Section 3.1.3. Our goal is to show that under mild assumptions, the denoising model $ε_{\theta}$ converges to the true conditional score function of the local latent distribution, enabling realistic and diverse augmentations without reliance on class labels. We begin by stating the following assumptions:

Assumption 1 (Locality Assumption): The latent variable $z_{i}^{0}$ is drawn from a smooth conditional distribution $p(z_{i}^{0} \mid \mathcal{N}(v_{i}))$, supported on a low-dimensional manifold.

Assumption 2 (Model Capacity): The denoising network $ε_{\theta}$ is a universal approximator i.e. has enough expressive power to learn any function within a given function class (For D-GDA the score function of the noisy latent distribution).

Assumption 3 (Diffusion Schedule): The noise schedule $\\{\alpha_{t}\\}$, where $t$ varies from $1 \to T$, is chosen such that $\bar{\alpha}_{T} \to 0$ as $T \to \infty$, ensuring near-total corruption at the final step.

Theorem 1: Let $ε_{\theta}(z_{i}^{t}, t,c_{i}^{0})$ be trained using the denoising score matching objective. Then, as $T \to \infty$ and model capacity increases, $ε_{\theta}$ converges to the conditional score function: $ε_{\theta}(z_{i}^{t}, t,c_{i}^{0}) \rightarrow \nabla_{z_{i}^{t}} \log p_{t}(z_{i}^{t} \mid c_{i}^{0})$, where $p_{t}(z_{i}^{t} \mid c_{i}^{0})$ is the marginal distribution of the noisy latent variable at time $t$, conditioned on the local structure of node $v_{i}$.

Sketch of Proof: This result follows from established results in score-based generative modeling [R3]. Minimizing the denoising score-matching loss recovers the true score function of the noisy data distribution. In D-GDA, the conditioning vector $c_i^0$ restricts generation to a node's local neighborhood, simplifying the modeling of $p(z_i^0 \mid N(v_i))$ as a smooth, low-dimensional conditional distribution. Assumption A1 ensures the score function is well-defined and smooth, while Assumption A2 guarantees that $\epsilon_\theta$ can approximate this function arbitrarily well. The noise schedule in A3 ensures that the diffusion process sufficiently corrupts the latent code, enabling meaningful denoising learning. Together, these yield convergence to the true conditional score function. This theoretical justification shows that D-GDA's latent diffusion process, when conditioned on local neighborhood structure, can provably learn a neighborhood-aware augmentation distribution, without requiring access to class labels.

Empirical Validation: We evaluate D-GDA’s LDM under increasingly limited training data. Specifically, we reduce the amount of training data from 100% to 60% and 40%, and track LDM behavior across four graph datasets: Cora, Citeseer, Pubmed, and Ogbn-Arxiv. Early stopping is applied based on validation loss with a patience of 10 epochs. In Table 7, we report the training loss, validation loss, early stopping epoch, and D-GDA test accuracy. We observe that, as the training data decreases, training loss consistently decreases (e.g., Cora: 0.069 to 0.029), due to easier overfitting on fewer samples. Validation loss increases (e.g., Pubmed: 0.249 $\to$ 0.319), indicating reduced generalization from limited training data. LDM trained with less data tend to converge earlier (e.g., Ogbn-Arxiv: 672 $\to$ 172), suggesting faster overfitting. Test accuracy drops across datasets (e.g., Citeseer: 81.5% $\to$ 75.6%), as the model struggles to generate diverse augmentations.

Table 7: Impact of reducing training data for LDM on training loss, validation loss, early stopping epoch, and node classification accuracy

[R3] Song, Yang, et al. "Score-based generative modeling through stochastic differential equations." arXiv preprint arXiv:2011.13456 (2020).

[R4] Song, Yang, and Stefano Ermon. "Generative modeling by estimating gradients of the data distribution." Advances in neural information processing systems 32 (2019).

2b) D-GDA Training and Inference Cost Breakdown

Table 8 provides a component-wise breakdown of the D-GDA training time, covering TSS, GVAE, and LDM, along with its inference time with Test-Time Augmentation (TTA). For comparison of computational time with compared methods please see Table in rebuttal.

Table 8: Breakdown of training time (in seconds) and per sample inference time (in seconds) for D-GDA across ten datasets of varying scales

3) Description of Technical Innovation

Our technical innovation lies in the utilization of GVAE and LDM for the task of graph data augmentation. Specifically, how these components are adapted, extended, and algorithmically integrated for the graph data augmentation is novel. D-GDA is a cohesive, task-adaptive framework with novel mechanisms and substantial empirical gains. The technical contributions of D-GDA include:

Target Sample Selector (TSS): A novel component that selects samples that would benefit the most from the augmentation based on prediction entropy. TSS utilization results in improved (See Table 14 in main paper)

Neighborhood-aware Latent Diffusion Model (LDM): We propose to adapt LDM to the graph domain by applying the diffusion process in the latent space learned by GVAE, while explicitly modeling local graph structure. This design allows for generating high-quality node representations that preserve both feature and topological context. Removal of LDM results in reduced performance, as shown in Table 14.

Multi-task Compatibility: Unlike prior works that target a single setting, D-GDA is versatile and effective across node classification, link prediction, and graph classification, as well as in semi-supervised, supervised, and long-tailed settings.

ML Safety Measures: D-GDA is shown to improve critical safety measures such as calibration, robustness to adversarial attacks, and improved performance under feature corruption. These evaluations go beyond traditional accuracy benchmarks and highlight the practical utility and robustness of our proposed D-GDA framework.

We sincerely thank the reviewer for their thoughtful feedback and for acknowledging our efforts in addressing earlier concerns. We greatly appreciate the reviewer’s interest in the convergence behavior of our Latent Diffusion Model (LDM), particularly under constrained data settings.

We fully agree that conventional LDMs, such as Stable Diffusion, used in high-dimensional image generation tasks typically require large-scale datasets (LAION-5B). Specifically, Stable Diffusion v1.4 employs a U-Net architecture with approximately 865M parameters and operates in a latent space of size 64×64×4 (16384-d) for the generation of 512×512 images.

In contrast, our LDM is lightweight, task-specific, and operates in a much lower-dimensional latent space (256-d) obtained from the graph variational autoencoder. The architecture of our LDM is a compact 1D-UNet style model, comprising only ~165K trainable parameters, three orders of magnitude smaller than standard image-based diffusion models. For reference, the architecture and parameter breakdown are presented in Table 10.

Table 10: Layer-wise breakdown of learnable parameters in the LDM architecture.

Additional Empirical Results for LDM Convergence

As the respected reviewer observed, the overall performance degradation remains under 10% even when the LDM training data is reduced to 40%, as shown in rebuttal Table 7. This result empirically demonstrates the robustness and generalization capability of our LDM in low-resource settings. Additionally, we provide further evidence of convergence in the form of LDM train and validation losses. Table 11 shows epoch-wise LDM training and validation loss on the Cora dataset for different LDM training data percentages.

Table 11: Epoch-wise training and validation loss of the LDM across different training data percentages. A “–” indicates that training was stopped early based on the early stopping criterion.

D-GDA Robustness to Homophily

The node homophily is defined as the average fraction of a node’s neighbors that share the same label [R1]. Table 1 compares these node homophily scores with GCN and D-GDA performance, as well as the resulting performance gain across six node classification and three link prediction datasets. Pearson’s correlation coefficient between node homophily and these performances is computed. We observe a positive correlation of 0.63 between homophily and GCN performance, however, a reduced correlation of 0.45 with D-GDA performance. It suggests that D-GDA performance is not strongly correlated with homophily compared to GCN. More interestingly, we observe a negative correlation of -0.37 between homophily and performance gain of D-GDA, indicating that D-GDA performance gain is robust to homophily. On the remaining datasets, node labels are not available, so homophily can not be computed.

Table 1: Node Homophily Vs GCN and D-GDA performance: The D-GDA performance gain is robust to homophily.

[R1] Platonov, Oleg, et al. "Characterizing graph datasets for node classification: Homophily-heterophily dichotomy and beyond." Advances in Neural Information Processing Systems 36 (2023): 523-548.

Test Time Augmentation Effectiveness and Computational Cost Analysis

We have shown the effectiveness of Test Time Augmentation (TTA) in Table 11 of the main paper. Now we present an extended evaluation by expanding the analysis to 10 datasets to provide a more comprehensive view. Table 2 summarizes the results for GCN and D-GDA, both with and without TTA, along with the per-sample TTA cost. Across all datasets and tasks, we observe consistent performance improvements when employing TTA, highlighting its generalizability and effectiveness.

Table 2: Performance comparison of GCN and D-GDA with and without test time augmentation (TTA). Per-sample inference time (sec) with TTA is also reported.

Ablation on Node Importance Selection Strategies for Graph Classification

To evaluate the effectiveness of the proposed degree-based node selection method, we compared it against two alternative strategies including random selection and PageRank-based selection as suggested. Table 3 summarizes the results for graph classification across these strategies. Following [R2], we compute PageRank with a damping factor of 0.85 and a convergence tolerance of $1 \times 10^{-6}$. We observe that the proposed degree-based selection consistently outperforms both alternatives. This supports the intuition that high-degree nodes are indeed more structurally influential, reinforcing the effectiveness of degree-based selection as the optimal strategy in our setting.

Table 3: D-GDA performance comparison on graph classification datasets using the proposed degree-based node selection strategy, compared against random and PageRank-based selection methods.

[R2] Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), 11–15.

D-GDA Computational Comparison with Baselines

Table 4 provides a component-wise breakdown of the D-GDA training time, covering TSS, GVAE, and LDM, along with its inference time with Test-Time Augmentation (TTA). Table 5 compares the overall training and inference times (in seconds) of D-GDA with and w/o TTA against baseline methods including GCN, DropEdge, and FLAG, across three datasets of varying sizes: Cora, Flickr, and Ogbn-Arxiv (large-scale dataset). Among these methods, DropEdge consistently demonstrates the lowest training and inference costs, making it the most efficient overall. D-GDA shows better efficiency than FLAG on the larger datasets, Flickr and Ogbn-Arxiv, highlighting its scalability. Additionally, the D-GDA variant without TTA achieves inference times comparable to FLAG.

Table 4: Breakdown of training time (in seconds) and per sample inference time (in seconds) for D-GDA across ten datasets of varying scales.

Table 5: Training time (sec) and inference time per sample (sec) comparison of D-GDA with baselines.

D-GDA Scalability and Efficiency Analysis

Table 6 compares the scalability of D-GDA across datasets of varying numbers of nodes and number of graphs. Specifically, performance gain, training time, and per-sample inference time of D-GDA are compared with the dataset size. For datasets containing multiple graphs, we report the average number of nodes per graph. The results demonstrate that D-GDA scales efficiently with increasing dataset size. The training time increases sublinearly as the dataset size increases, while still delivering significant performance improvements over GCN.

Table 6: Scalability of D-GDA with varying graph sizes. D-GDA training time increases sublinearly with increasing dataset size.

Thanks for the additional results in the rebuttal! I think they help a lot on the understanding of the proposal's efficiency, and would recommend the authors to add them in the paper.