Diffusion on Graph: Augmentation of Graph Structure for Node Classification
Authors: Yancheng Wang
Changyu Liu
Yingzhen Yang
Venue: Accepted by TMLR ()

Abstract: Graph diffusion models have recently been proposed to synthesize entire graphs, such as molecule graphs. Although existing methods have shown great performance in generating entire graphs for graph-level learning tasks, no graph diffusion models have been developed to generate synthetic graph structures, that is, synthetic nodes and associated edges within a given graph, for node-level learning tasks. Inspired by the research in the computer vision literature using synthetic data for enhanced performance, we propose Diffusion on Graph (DoG), which generates synthetic graph structures to boost the performance of GNNs. The synthetic graph structures generated by DoG are combined with the original graph to form an augmented graph for the training of node-level learning tasks, such as node classification and graph contrastive learning (GCL). To improve the efficiency of the generation process, a Bi-Level Neighbor Map Decoder (BLND) is introduced in DoG. To mitigate the adverse effect of the noise introduced by the synthetic graph structures, a low-rank regularization method is proposed for the training of graph neural networks (GNNs) on the augmented graphs. Extensive experiments on various graph datasets for semi-supervised node classification and graph contrastive learning have been conducted to demonstrate the effectiveness of DoG with low-rank regularization. The code of DoG is available at \url{https://github.com/Statistical-Deep-Learning/DoG}.

Published in Transactions on Machine Learning Research (02/2025)
Diffusion on Graph: Augmentation of Graph Structure for Node Classification
Yancheng Wang
yancheng. Soncheng-wonggaase edu changyu2 Gasu. edu yingzhen yong Banggaasu Basu. edu
Changyu Liu
Yingzhen Yang
School of Computing and Augmented Intelligence Arizona State University
Reviewed on OpenReview: https: // openreview. net/ forun? id- taW948kU6m
Abstract
Graph diffusion models have recently been proposed to synthesize entire graphs, such as molecule graphs. Although existing methods have shown great performance in generating entire graphs for graph-level learning tasks, no graph diffusion models have been devel- oped to generate synthotic graph structures, that is, synthetic nodes and associated edges within given graph, for node-level learning tasks. Inspired by the research in the com- puter vision literature using synthetic data for enhanced performance, on Graph (DoG), which generates synthetic graph structures to boost the performance of GNNs. The synthetic graph structures generated by DoG are combined with the origi- nal graph to form an augmented graph for the training of node-level learning tasks, such as node classification and graph contrastive learning (GCL). To improve the efficiency of the generation process, a Bi-Level Neighbor Map Decoder (BLND) introduced in DoG. To mitigate the adverse effect of the noise introduced by the synthetic graph structures, low-rank regularization method is proposed for the training of graph neural networks (GNNs) the augmented graphs. Extensive experiments various graph datasets for semi-supervised node classification and graph contrastive learning have been conducted to demonstrate the effectiveness of DoG with low-rank regularization. The code of DoG is available at http////aaat/ttttttaooo//aaaaaaa happra/sttttta-------e-eaaaannno
propose Diffusion
1 Introduction
Diffusion models (Song al., 2021c; Song & Ermon, 2019a; Ho et al., 2020) have gained prominence class of generative models capable of producing high-quality synthetic data (Gao et al., 2023; Rombach et al., 2022; Baranchuk et. al., 2022). Building upon the success of diffuusin models, conditional diffussin models (Rombach et al., 2022; Ho & Salimans, 2022) utilize external information such as text descriptions, class labels, or images in the noising and denoising phases, steering the generation process towards con- textually relevant outcomes. Building on these advancements, recent studies (Trabucco et al., 2023; Azizi et al., 2023) employ class-conditional diffusion models to produce labeled synthetic data, which then in- corporated into the training datasets of classification tasks as form of data. augmentation. Following the success of diffusion models in the visual and textual fields, graph diffusion models (Niu et al., 2020; Jo al., 2022; Haefeli et al., 2022; Vignac et al., 2023a; Limnios al., 2023) have recently been studied to tailor diffusion models to tackle the specific challenges of synthesizing graph-structured data. This adaptation has broadened the scope of synthetic graph generation, allowing for the creation of complex, realistic graphs that preserve the fundamental characteristics of real-world datasets. Although current models are predomi- nantly aimod at generating complete graphs (Niu et al., 2020; Jo al., 2022; Hacfeli et al., 2022) or small graphs (Vignac et al., 2023a; Limnios al., 2023) resembling the graphs in the given graph datasets for graph-level learning tasks, there remains unexplored potential in generating synthetic graph structures

---

Published in Transactions on Machine Learning Research (02/2025)
Augmented Gruph
Orignal Graph
85.0
75.0
Original Nodes
82.5
72.5
Orignal Edges
80.0
70.0
Synthetic Graph Structures
77.5
67.5
GCN
OCN
Synthetic Nodes
75.0
GCN with Low-rank Regudarization
65.0
OCN with Low-rank Regalarisation
Synthetic Edges
72.5
0
3 4
6
7 8 9
10
62.5
0
2 3 4 7 8 9 10
N'
Figure 1: Illustration of the aug- mented graph after adding the syn- thetic graph structures to the original graph.
(a) Cora
(b) Citeseer
Figure 2: Node classification accuracy of GCN on Cora and Citeseer trained with different numbers (N') of synthetic nodes added. VL is the set of labeled training nodes in the original graph.
for node-level classification tasks within a single graph. The synthetic graph structure refers to both the synthetic nodes and the edges connecting them within the same graph as illustrated in Figure
In this work, we focus on node-level generation, aiming synthesize graph structures within a given graph. Limited training data is a common issue in graph datasets. For example, only 140 of 3327 nodes in Cite- seer (Sen et al., 2008b) are in the training set. Inspired by the synthetic data augmentation methods from the computer vision literature (Azizi et al., 2023; Hc et al., 2022), we proposc new rescarch direction of using synthetic graph structures to increase the nunber of training nodes and thereby improve the node classification performance. Figure illustrates that the performance of GCN trained on augmented graphs increases with suitably more synthetic structures added to the training set.
We propose a novel Diffusion Model on Graph (DoG), which, to the best of our knowledge, is the first graph diffusion model to generate synthetic graph structures comprising both synthetic nodes and the synthetic edges associated with the synthetic nodes within a single given graph. DoG comprises novel Graph Autoencoder (GAE) and a Latent Diffusion Model (LDM). The encoder of the GAE encodes node attributes and edges connecting to the nodes into a continuous latent space, and the decoder of the GAF decodes latent features to node attributes and edges connecting to the nodes. The LDM aims at synthesizing the latent features of the synthetic graph structures. When trained with Classifier-fres free Guidance (CFG) (Ho & Salimans, 2022), the LDM can generate the latent features of the synthetic graph structures where the node belongs to specific class. The motivation for leveraging the LDM in processing the latent representations primarily stems from its ability to enhance the generative capabilities of the diffusion model while ensuring computational efficiency. The LDM trains the diffusion model in the compressed latent features generated by the GAE rather than directly in the high-dimensional input data space. This approach significantly reduces the dimensionality of the data being processed, which decreases the computational resources required for the training and the inference of the diffusion model. Moreover, the LDM has shown remarkable performance generating high-quality synthetic data across various domains (Rombach et al., 2022; Lovelace et al., 2023). Moreover, decoding the neighbors of a node from the latent space in the entire graph can be computationally expensive, considering that node can potentially connect to any other nodes within the graph its neighbors. To overcome this issue, our DoG features Bi-Level Neighborhood Decoder (BLND), which reconstructs the edges connecting to a node in a hierarchical manner. The nodes in the graph are first divided into several clusters using a balanced clustering method. For each synthetic node, instead of finding the neighbors among all the nodes the original graph, BLND first finds the clusters containing the original nodes to which the synthetic node should connect through an inter-cluster dccoder. Then, BLND identifies the individual nodes within each of the identified clusters by generating an intra-cluster neighbor map for that specific cluster with an intra-cluster decoder. Combining the synthetic graph structures generated by DoG with the original graph, we obtain an augmented graph, illustrated in Figure 1, for the downstream node-level learning tasks.
Due to the inherent randomness in the forward process of diffusion models (Ho et al., 2020) and the difficulty in accurately conditioning the LDM with class signals (Fu et al., 2024), the synthetic graph structures inevitably contain noise. Consequently, training node classifiers directly on these augmented graphs may result in degraded performance (Azizi et al., 2023). Let V, denote the set of labeled training nodes in the
2

---

Published in Transactions on Machine Learning Research (02/2025)
original graph. Let N' denote the number of synthetic nodes generated by our DoG, which measures the amount of synthetic graph structures added to the augmented graph. As illustrated in Figure 2, while the performance of GCN trained on augmented graph increases with more synthetic graph structures added when N' < 3/VL,, more syuthetic graph structures addod to the augmented graph hurts the performance of the vanilla GCN severely when N' > 3/V2/- As a result, it remains an important and interesting problem to effectively train GNNs on the augmented graph, which can be very noisy due to the noise in synthetic graph structures. To this end, we propose a low-rank learning method inspired by the low frequency property illustrated in Figure 5 in Section C of the appendix. The low frequeney property suggests that the low-rank part of features learned by GNN cover the majority of the information of the training labels. Motivated by this observation, we add low-rank regularization term in the training loss of a GNN for node-level learning lasks, such as node classification and graph contrastive learning, on the augmented graph. The low-rank regularization term encourages that only the low-rank part of the features learned by a GNN is used for classification, so that the noise in the synthetic graph structures in the high-rank part of the features would mostly not affect the performance of the GNN. We evaluate the semi-superviser node classification accuracy of GCN trained with low-rank regularization and regular GCN with different amounts of synthetic graph structures added to the augmented graph. As illustrated in Figure 2, the GCN trained with the low-rank regularization constantly outperforms the vanilla GCN and exhibits more stable performance than the vanilla GCN with different amount, of synthetic nodes added to the augmented graph. Such results suggest that our low-rank learning method significantly reduces the adverse effect of the noise in the augmented graph when more synthetic structures are introduced.
1.1 Contributions
First, we propose diffusion model on graph-structured data, termed Diffusion on Graph (DoG). To the best of our knowledge, DoG is the first node-level graph diffusion model that synthesizes nodes and associated edges in a single given graph. In contrast, previous graph diffusion models focused on generating entire graphs by learning diffusion models from graph-level learning datasets. Our DoG model also features a novel Bi-Level Neighborhood Decoder (BLND), which efficiently reconstructs the edges connecting to a node in a bi-level hierarchical manner.
Second, we propose a low-rank learning method that trains GNNs or GCL models on the augmented graph with low-rank regularization, which largely mitigates the adverse effect of the noise from the synthetic graph structures. The low-rank learning method uses a low-rank regularization term in the usual training loss by cross-cntropy, which is inspired by the low frequency property illustrated in Figure 5 in Section C of the appendix. Our low-rank learning method enjoys both strong theoretical guarantee in terms of the error bound for the test loss presented in Section A of the appendix, and compelling empirical results. Extensive experiment results Table 1 and Table 2 of training GNNs and GCL models on augmented graphs with low-rank regularization suggest that the low-rank learning method effectively reduces the adverse effect of noise in the synthetic graph structures. In addition, results in Table 3 show that the low-rank regularization method significantly outperforms existing data selection methods for learning with noisy data.
Different from existing node-level graph augmentation methods reviewed in Section 2.2, DoG is among the first to generate synthetic graph structures which improve the prediction accuracy of GNNs for node classi- fication by enlarging the size of the training set. The augmentation method of DoG is orthogonal to existing node-level data augmentation methods. For example, existing node-level augmentation methods, such as GraphMix (Verma al., 2021), FLAG (Kong et al., 2022), and NODEDUP (Guo et al., 2024), can be directly applied to the training of GNNs on the graphs augmented by DoG with enhanced performance. Results in Table 4 show that DoG can significantly improve the performance of models trained with GraphMix, FLAG, and NODEDUP. As a result, DoG is expected to generate broad impact in the graph learning literature as a new graph augmentation method.
2
Related Works
2.1
Diffusion Models
Score-based diffusion models, which smoothly transform data to noise using a diffusion process and synthesize samples by learning and simulating the time reversal of this diffusion (Song et al., 2021c), have demonstrated
3

---

Published in Transactions on Machine Learning Research (02/2025)
superior performance across wide range of generation tasks (Ho et al., 2020; Song & Ermon, 2019a; Gao et al., 2023; Rombach et al., 2022; Baranchuk et. al., 2022). As DDPM suffers from large computational overhead in the sampling process, many recent works (Song et al., 2021d;b; Song & Ermon, 2020) focus on accelcrating DDPM. For instance, LDM (Rombach et al., 2022) significantly improves the computational efficiency and the quality of generated images by training DDPM on the latent features of the training data encoded by pre-trained autoencoders. Recently, graph diffusion models have also been widely studied to generate synthetic graphs (Niu et al., 2020; Jo et al., 2022; Haefeli et al., 2022; Jo et al., 2022; Zhou et al., 2024). Early works (Jo et al., 2022; Haefeli et al., 2022; Vignac et al., 2023a) on graph diffusion seek to design discrete diffusion models tailored to the discrete nature of the adjacency matrix of graph data. Inspired by LDM (Rombach et al., 2022), SaGess (Limnios et al., 2023) embeds the graph structures and features of entire graphs into latent. features and trains a DDPM on the latent feature space. Albeit the above efforts have been made to adopt diffusion models to generate synthetic graphs, all existing graph diffusion models are designed for graph-level synthotic data generation, which cannot be generalized to node-level generation within single graph. In contrast, our work aims to generate synthetic graph structures, that are, synthetic nodes and the associated edges at the same time for node-level learning tasks.
2.2 Generative Data Augmentation and Data Selection
Node-level Graph Data Augmentation. Node-level graph data augmentation methods enhance the training of GNNs on graphs by modifying the structure, features, or labels of nodes in the graph (Zhao et al., 2023). Structure augmentation methods (Gasteiger et al., 2019; Zhao et al., 2021; Rong et al., 2020; Feng et al., 2022) modify the connectivity of nodes in the graph by either adding or removing edges. TADA (Lai et al., 2024) employs the attribute-aware graph structure sparsification to augment the graph structure for the training of the GNNs. Feature augmentation methods (You et al., 2020; Kong et al., 2022) randomly alter the node features during the training process. For instance, FLAG (Kong el al., 2022) iteratively augments node features with gradient- based adversarial perturbations during training to improve the performance of GNNs at the test time. LGGD (Azad & Fang, 2024) proposes to generate new features for the training nodes in the given graph based on the generalized geodesic distance as data augmentation for the node classification task. Label augmentation methods adjust the labels of nodes in the training set. For example, Mixup- Mixup-based methods (Han et al., 2022; Wang et al., 2021; Verma et al., 2021) such as GraphMix (Verma et al., 2021) create interpolations of existing labeled nodes for the training of GNNs. GeoMix (Zhao et al., 2024) introduces a novel Mixup approach based on the in-place graph editing to augment the training set in the given graph for the node classification task. NODEDUP (Guo et al., 2024) is the first work that enlarges the training set of the graph by duplicating the nodes in it.
We remark that the node-level data augmentation methods, which modify the structure, features, or labels of nodes in the graph surveyed above, are orthogonal to DoG. As evidenced in Table 4 in Scction 5.3, combining the DoG with the existing node-level data augmentation methods further boosts the performance of the existing node-level data augmentation methods and the DoG.
Generative Data Augmentation. Synthesizing informative training data as data augmentation for im- proving the performance of deep neural networks remains a vital yet challenging research area. Existing works predominantly focus on synthesizing training data through pre-trained deep generative models, such as Generative Adversarial Networks (GANs) (Zhang et al., 2021; Li et al., 2022) and diffusion models (He et al., 2022; Tian et al., 2023; Yuan et al., 2022; Bansal & Grover, 2023; Vendrow et al., 2023). For instance, recent works(Saryyldde et al., 2023; Lei et al., 2023; Azizi et al., 2023) leverage conditional latent diffusson models, such as Stable Diffusion et al., 2022) to create class-conditioned samples for training image classification models.
Training on Noisy Synthetic Data. Despite the promising results of introducing synthetic data into the training of classification models, it is well-known that synthetic data generated by diffusson contain noise (Azizi et al., 2023; Trabucco et al., 2023; Na el al., 2024), which attributed to the randonness of the forward process (Ho et al., 2020) and the difficulty in accurately conditioning the LDM with class signals (Fu et al., 2024). To mitigate this issuc, recent works (Saryyilız et al., 2023; Lei et al., 2023; Zhou et al., 2023) data selection methods, TopoFilter (Wu et al., 2020) and NGC (Wu et al., 2021) employ prompt engineering to generate synthetic data with improved quality for training downstream (Sans(Sa et al., 2023; Lei
4

---

Published in Transactions on Machine Learning Research (02/2025)
et al., 2023; Zhou et al., 2023). However, these methods are sensitive to the design of prompts and are limited to multi-modal generative models. Beyond directly improving the quality of generated synthetic data, methods such as data selection (Han et al., 2018; Yu et al., 2019; Song et al., 2021a; Nguyen et al., 2020; Song et al., 2023), which selects a high-quality subset from the noisy training data to improve the performance of deep learning models, can also be used to select high-quality synthetic data for the training of downstream tasks. To this end, we also survey data selection methods for learning with noisy data, To demonstrate the superiority of our method in learning with noisy synthetic graph structures, we adapt data selection methods, TopoFilter (Wu et al, 2020) and NGC (Wu et al., 2021) to the settings of graph learning and establish baselines that use them to select high-quality subset of the synthetic nodes. We then train GNNs on the original graph combined with the synthetic graph structures selected by these data selection methods.
2.3 Low-Rank Learning
Low-rank learning methods (Candès et al., 2011) have emerged as pivotal tools to mitigate noise, and enhance representation learning- For instance, (Yang & Cohen, 2015) introduced the technique of singular value pruning, which applics low-rank constraints within neural network layers to improve both performance and computational efficiency. Following that, (Hu et al., 2013) adopts Truncated Nuclear Norm Regularization (TNNR) to perform selective minimization of singular values to precisely recover the low-rank matrices under noisy conditions. The integration of TNNR in tensor completion tasks has also seen notable improvements, particularly through the application of tensor singular value decomposition (I-SVD) (Liu et al., 2017; Zhang et al., 2020). Following that, a recent. study (Indyk et al., 2019) further improved the low-rank approximation methods for better practical efficacy. In the graph domain, low-rank learning methods have also been widely studied to improve the robustness of GNNs against noise and adversarial attacks (Savas & Dhillon, 2011; Entezari et al., 2020; Jin et al., 2020; Alchihabi el al., 2023; Xu el al., 2021).
2.4 Graph Neural Networks
Graph Neural Networks (GNNs) emerged a powerful tool for learning expressive node representations for graph data. Most prevailing GNNs are built to learn the representations of nodes in neighborhood aggregation manner, usually referred to as Mcssage Passing Neural Networks (MPNNs). The represcntation of a node is learned by transforming and aggregating node features from its neighbors. Following this scheme, different GNN architectures have been proposed, including graph convolutional networks (GCNs) (Kipf & Welling, 2017), attention- based GNNs (Veličković et al., 2018; Wang et al., 2019; lyer et al., 2021), and the others (Wu al., 2019; Hamilton et al., 2017; Xu et al., 2019; Wu et al., 2019; Chen et al., 2020). Following the success of Transformers in natural language processing (Vaswani et al., 2017), transformer architectures have also been adapted to design GNNs to capture nodo-wise correlations (Wu et al., 2022; 2023b;a). Recently, GNNs, such as Graph Variational Autoencoders (GVAEs), have been adopted for graph- level synthetic graph generation, aiming to generate set of synthetic graphs resembling the graphs in the given graph datasets (Mitton et al., 2020; Bongini et al., 2021; Zhu et al., 2022; Vignac et al., 2023b; Cai et al., 2024). Since graph-level synthetic graph generation methods cannot generate synthetic nodes within a given graph; they cannot be applied to generate synthetic labeled nodes lo enlarge the I training set of a graph for node classification, In contrast, our work focuses on node-level synthetic graph structure generation, which aims to generate synthetic nodes and synthetic edges connecting the synthetic nodes to the original nodes in given graph.
3 Preliminaries
We first establish the notations for the attributed graph in Section 3.1. Furthermore, a comprehensive overview of Diffusion Models (DMs), Latent Diffusion Models (LDMs), and Classifier-free Guidance (CFG) is provided in Scction B of the appendix.
3.1 Attributed Graph and Notations
An attributed graph with N nodes is denoted by G (V,E,). Here, V= (0i, U2,..., uND represents the nodes, and & > V represents the edges. Node attributes are given by X E RNDD where each row
5

---

Published in Transactions on Machine Learning Research (02/2025)
Graph Autoencoder
Latent Diffusion
Encoder
X
A
ML
Forward Diftusion
X+
MLP
BLND
MLP
2T-1 2T
M
Reverse Diftusion
Decoder
Latent Space
Node Attributes X;
Mode Index
Positional Embeddings pos(1)
X
Neighhor Attributes
X
NT Neighbor Indices
Positional Embeddings pos(j)
Figure 3: The overall framework of synthetic node generation process.
The structure the Bi-level Neighbor
Map Decoder (BLND) illustrated Figure 4.
X, E RD corresponds the attributes of node U,. The adjacency matrix A E [0, of graph defines connections such that Ai if (v,, 0y) E. Each row A, represents the connections of node u. An augmented adjacency matrix, = A + includes self-loops. The diagonal degree matrix of this augmented matrix is D. The neighborhood (iii)= = -i Aij }} includes node eú itself and all nodes connected to uy The notation [N] denotes all natural numbers from 1 to N inclusive. [A], stands for the i-th row of a matrix A. ||-llp denotes the p-norm of a vector or a matrix.
4 Methods
4.1
Diffusion Graphs (DoG)
Graph Autoencoder (GAE). To encode node vs into latent feature with the encoder of the Graph Autoencoder (GAE), we first generate latent feature of the node attribute X, as f(X,), where f() is Multi-Layer Perceptron (MI.)) layer, which consists of a linear layer followed by an activation function ReLU. To incorporate the information from the edges connected to U, we add positional embeddings to the node attributes of U3 neighbors. Positional embedding methods (Ma et al., 2021; You et al., 2019) have been used GNNs to encode the global positional information of the nodes a graph. In our work, the positional indexes are used encode the positions of neighboring nodes of nodes in the graph into the latent space. For each neighbor j E Ni)), we modify the node attributes as X = X; + pos(j), where pos(-) is a function converting the position index into embedding vector (Vaswani et al., 2017). We apply two Graph Attention Network (GAT) (Veličković et al., 2018) layers to aggregate the information in (X, 1 (i))) into a single latent feature Z, Next, we concatenate Zí with f(X.) to obtain the latent feature of node o by Z, = (Xx)),)(()), where f' is another MLP layer encoding the concatenated features to the latent space of LDM with lower dimension D'. After encoding a node e; the graph to latent feature Z,, the decoder of the GAF, reconstructs the node attribute X, and its associated edges A, The node attributes X, are roconstructed by three consecutive MLP layers. The edges connected the node are reconstructed by the Bi-Level Neighborhood Decoder (BLND) introduced below. The overall framework of DoG is illustrated in Figure 3.
Bi-Level Neighborhood Decoder (BLND). Decoding the node attribute from the latent space can be achieved following existing designs of autoencoders (Zhai et. al., 2018). However, decoding the edges connected to a node from the latent space the entire graph can be computationally expensive, considering that node can potentially connoct to any other nodes within the graph as neighbors. To address this challenge, we propose a Bi-Level Neighborhood Decoder (BLND), which decodes each latent feature into an inter-cluster neighbor map and intra-cluster neighbor map defined below.

---

Published in Transactions on Machine Learning Research (02/2025)
Inter-Cluster Neighbor Map
C
Z 2- Latent Feature
Embedding Layer
Z
ML.P
Concal
M.
M
Concill
M.
Intra-Cluste Neighbor Map
The structure of the Bi-Level Neighborhood Decoder (BLND); which generales an inter-cluster neighbor map and an intra-cluster neighbor map for each node.
Figure 4:
Preparing Inter-Cluster Neighbor Map and Intra- Cluster Neighbor Map. We first divide the nodes in the graph into several clusters of similar size by applying balanced K-means clustering (Malinen & Fränti, 2014) on the node attributes. The number of clusters, denoted by K, is decided by cross-validation on each dataset. We set the maximal capacity of each cluster to M = x 1. After clustering the nodes into K clusters, we assign an index each node within its respective cluster by ordering them according to their indices in the entire graph. For each node Ui, the BLND first reconstructs which is denoted by a matrix C E {0, 1j where Ca = 1 if and only if there exists at least some node Uj in cluster k which is connected to node ug Our BLND then reconstructs the intra-cluster neighbor map between each node and each cluster, and the intra-cluster neighbor map is denoted by a chree-dimensional tensor M E {0, 1} x M = 1 if and only the node U; is connected to the m-th node in cluster k. The detailed reconstruction processes for C and M are described in the following paragraph.
inter-cluster neighbor map
Training the GAE with Bi-Level Neighborhood Decoder. As illustrated in Figure 4, BLND recon- structs the inter-cluster neighbor map and intra-cluster neighbor map with two branches of MLP decoding layers. For each node 14, BLND first reconstructs its inter-cluster neighbor map C2 with one MLP layer. After that, the predicted cluster indices C(i) {k E [ = =} are separately fed to an embedding layer to generate a set of class-conditional ures (t) = [({) E TR Ik E c(i) using the class-conditional em- bedding method in Classifier- free Guidance (Ho & Salimans, 2022), where g contains one text embedding layer followed by an MLP layer. Next, each of the class-conditional features g(k) 2(i) concatenated with the latent feature of the other branch for decoding the intra-cluster neighbor map by M. = g'Z (k)(,)) where g' is another MLP layer. The class-conditional embedding enables the parameter-sharing of the de- coder layers for reconstructing intra-cluster neighbor maps of different clusters and thus largely reduces the computation cost for reconstructing the edges connected to node in large graph.
In our work, we train the GAE with BLND by minimizing the node reconstruction loss and the bi-level edge reconstruction loss
2
LGAE
X
X
M
M
Node Reconstruction Loss
Bi-Level Edge Reconstruction Loss
where |1-1|, denotes the Euclidean norm. The node reconstruction loss aims to reconstruct the node attribute. The bi-level edge reconstruction loss aims to reconstruct the inter-cluster neighbor map and the intra-cluster neighbor map. With the reconstructed inter-cluster neighbor map and the intra-cluster neighbor map, we can easily obtain the edges connected to the nodes in the graph.
4.2 Conditional Generation of Synthetic Graph Structures in Latent Space
After finishing the training of GAE, the node attributes and the edges connected to the nodes in the graph can be encoded into a continuous low-dirensionall latent space. To generate synthetic graph structures, which are synthetic nodes and associated edges, we train a conditional Latent Diffusion Model (LDM) (Rombach et al., 2022) with Classifier-Free Guidance (CFG) (Ho & Salimans, 2022) on the latent features. The labels of synthetic nodes and Gaussian noises are fed to the LDM model to sample latent features of synthetic graph structures by Equation (17) in Section B of the appendix. With the conditional LDM trained on the
7

---

Published in Transactions on Machine Learning Research (02/2025)
latent space, we generate latent features of the synthetic graph structures. Next, reconstruct the generated latent features into the node attributes and the edges associated with the nodes. Let Vz. S V denote the set of labeled nodes in the original graph G, and Vayn denotes the set of generated synthetic nodes by DoG. Let the node attributes of Veyu generated by DoG be Xsyu. Let C' be the number of classes, and No be the number of synthetic nodes for each class. N' = CN,- = DVyaal is the number of the synthetic N'
nodes. Let syn = 1 denote the set of the labels of the synthetic nodes. Let Z - (
{ denote the
latent features of the synthetic graph structures. Let Asyn R'N' denote the edges of the synthetic nodes generated by our DoG. Then the augmented synthetic graph structure is (Vayn: Xayn Aayn). The adjacency matrix of the augmented graph is Aaug- = [A Asyn; Asyn A] R(N=N") and the node attributes of the augmented graph is Xaug = [X; Xayn] E IR(++*)xx, The augmented graph, which is the combination of the original graph 9 and the synthetic graph structure, is then denoted by Gaus = (VU Vayn: Xaug, Aaug). The set of labeled nodes in Gaug is Vz U Vayn their labels are YL U sya- Algorithm 1 and Algorithm 2 in Section D of the appendix describe the training algorithm of the DoG and the generation process of the augmented graph Gang in details.
4.3 Low-Rank Regularization
After obtaining the augmented graph Gaug = UVUV Vayn: X Xaug: Asug) with Ñ N N' nodes, we can train Graph Neural Networks (GNNs) for node classification it. However, due to the randomness of the forward process in diffusion models (Ho et al., 2020) and the difficulty in accurately conditioning the LDM with class signals (Fu et al., 2024), the synthetic graph structures in the augmented graph inevitably contain noise, which can degrade the performance of GNNs trained on it. To address this issue, we propose a low-rank learning method with a low-rank regularization in the training of the GNNs on the augmented graph to enforce the learned feature kernel to be low-rank, whose motivation is discussed below.
Motivation of Learning Low-Rank Features. Let Y = (y1:y2i...:: E 10.13Nxc be the ground truth label matrix of all the nodes in the augmented graph, where C' is the number of classes. Let K be the gram matrix of the node representations H E R.xx which is calculated by K = H E RNN H can be the input to the last linear layer of the GNN trained for node classification or the output of the graph encoder in graph contrastive learning (GCL). By the low frequency property on the augmented graph illustrated in Figure 5 of Section C of the appendix, the projection of Y on the top eigenvectors of K with small rank r, such as r 0.2N, covers the majority of the information in Y. This observation motivates using the low-rank part of the features H, or equivalently the low-rank part of the gramn matrix K, for node classification. This is because the low-rank part of the features H covers the dominant information in the ground truth label matrix Y. Through mostly using only the low-rank part of H for node classification, the negative affect of the noise introduced by the synthetic graph structures in the high-rank part of the features H on a trained GNN reduced.
i= with X1 2 72. min N. 2 X [in((N. (N,4++1 = ...,=0 be the eigenvalues of K. In order to encourage the features H or the gram matrix be low-rank, we explicitly add the truncated nuclear norm |H = Ex d to the training loss function of semi- supervised node classification. The starting rank ro < min((, d) is the rank of the features H we aim to keep in the node representation, that is, if [H]]., = 0, then rank(H)- = ro- To enforce the features H or the gram matrix K to be low-rank in the training of the GNNs, regularize the training by adding a low-rank regularization term, which is the truncated nuclear norm [[H]],, to the usual cross-cntropy loss:
Learning with Low-Rank Regularization. Let {
{
{
) N
1 Σ KL (y:, [softmax (HW)), + +T||H]) m LEVL
min L(W)- W
=
(2)
Here KL is the KL divergence between the label y, and the softmax of the classifier output node us- >> O is the weighting parameter for the truncated nuclear norm ||H]], We use regular gradient descent to optimize (2) with a learning rate 17 E 2). The low-rank regularization can also be adapted to graph contrastive learning (GCL) methods by adding the truncated nuclear norm |H]], to the training loss of
x
the GCL methods. GCL methods usually optimize contrastive loss, such the InfoNCE loss (Hassani &
8

---

Published in Transactions on Machine Learning Research (02/2025)
Ahmadi, 2020), to train graph encoder that generates discriminative node representations H. By jointly optimizing the truncated nuclear norm ||H]],, with the contrastive loss of GCL. methods, the learned node representations H can also be enforced to be low-rank. The rank To is tuned by the standard cross-validatte described in Section 5.1. DoG enhances the training of GNNs with a selected mumber of synthotic nodes, which is also decided by cross- voss-valiiation as described in Section 5.1.
Theoretical Justification for Low-Rank Regularization on the Augmented Graph. The classifier in the optimization problem (2) is in fact linear classifier with output HW, and the predicted class scores are the softmax of such output. In Section A.1 of the appendix, present the upper bound for the test loss of the linear classifier HW trained on the augmented graph under the standard setting for transductive learning. The test loss is the Euclidean distance between the output of the linear classifier, HW, on the test nodes and the ground truth class label on the test nodes.
The upper bound for the test loss of the lincar classifier formally described in (4) of Section A.1 of the appendix. Such upper bound (4) theoretically justifies the usage of the low-rank regularization term [ I in the regularized training loss (2) for the linear classifier the augmented graph, because smaller |H l
renders a lower upper bound for the test loss, benefiting the prediction accuracy for node classification using such linear classifier.
4.4 Complexity Analysis
In our work, we proposed novel decoder, BLND, to reconstruct the edges connected to a node in the graph. To show its efficiency, we analyze the inference time complexity and the parameter size of the GAE with BLND, For comparison, we also analyze the inference time complexity and the parameter size of GAE, where BLND replaced by a regular edge decoder that directly reconstructs the adjacency matrix A. For ease of comparison, we denote the number of parameters and inference cost of all the MLP and GAT layers except BLND as SMLP and CMLP respectively. For node U; in the graph, let d; Σ C. be the number of clusters predicted to be connected to U,. Let D' be the dimension of the input feature for BLND. The inference time complexity of GAE with BLND is O(KD' + d complexity for computing the inter-cluster neighbor map and encoding the cluster indices. (dd M) is the computation cost for computing the intra-cluster neighbor map. In contrast, the inference time complexity of GAE with regular edge decoder is O KM + CMIP). We note that, d; is upper bounded by the degree of the node Uy In most graph datasets, the average degree of nodes is usually very small. For instance, on Pubmed, where the average node degree is 2.25, we have d, S 2.25. As result, D'(K + d,M) < D'KM. For example, setting K 100 and M 198 on Pubmed, we find that the inference time complexity of GAF with BLND is (5445.5D' + CMLP), which is much more efficient than the regular edge decoder whose inference time complexity is (19800D + CMLP). In general, the inference time complexity of GAE with BLND is much lower than that of GAE with a regular edge decoder.
where O'KD') is the additional
In addition, the parameter size of GAE with BLND is D2 D'K + D'M + SMLP, where D2 is the number of parameters in the layer for encoding cluster indices. D'K is the number of parameters in the layer for predicting the inter-cluster neighbor map. D'M is the number of parameters in the layer for reconng the intra-cluster neighbor map. It is noted that the reconstruction of the intra-cluster neighbor map of different clusters shares the same MLP decoder, as illustrated in Figure 4. In contrast, the parameter size of GAE with a regular edge decoder is D'KM + SMIPP. Because K + M & KM, the parameter size of GAE with BLND is much smaller than that of GAE with a regular edge decoder. For example, KM = N = 19717 on Pubmed with M- = 198 and K- = 100.
To thoroughly study the complexity of GAE with BLND, we also analyze its training time complexity. Let Ierain be the number of training epochs. The training time complexity of GAE with BLND should be O((KD'+ K DM + (CMMP)NNtraai of DoG, which replaces BLND with an MLP decoder reconstructing the entire neighbor map, is shown in Table 9 in Section F.4 of the appendix. DOG trains the GAF with BLND to encode node features and edges into low-dimensional latent features, which improves the efficiency of the diffusson process by reducing the dimension of input features. We remark that existing works on accelerating LDMs (Castells et al., 2024; Yang et al., 2023) can also be adapted to accelerate the diffusion process of DoG.
K
The time of training and data generation for both DoG and the variant
9

---

Published in Transactions on Machine Learning Research (02/2025)
5 Experiments
In this section, we perform empirical evaluations of DoG on public graph benchmarks. In Section 5.1, we discuss the experimental setup and implementation details. In Section 5.2, we present the evaluation results of DoG for semi-supervised node classification and graph contrastive learning. Comprehensive ablation studies on DoG are performed in Section 5.3. Although the experiments are mostly conducted on homophilic graph datasets in this section, we also demonstrate the effectiveness of DoG on heterophilic graph datasets in Table 7 in Section E.2 of the appendix. More additional experiment results are deferred to Section E of the appendix. In Section E.3 of the appendix, we evaluate the quality of the generated synthetic graph structures. In Section E.4, we evaluate the training time and synthetic data generation time of DoG. In Section E.5, we list the cross-validation results of the dyper-parameters on different graph datasets. In Section E.6 of the appendix, we perform an ablation study on the synthetic graph structures generated by DoG. In Section E.7 of the appendix, we evaluate the performance of DoG on the large-scale graph.
5.1 Experimental Settings
Implementation Details. We conduct experiments on five public benchmarks that are widely used for node classification on attributed graphs, namely Cora, Citeseer, Pubmed (Sen al., 2008a), Coauthor CS, and ogbn-arxiv (Hu et al., 2020). Details on the statistics of the dataset are deferred to Table 6 in Section E.1 of the appendix. To generate synthetic nodes, we first train the GAE on the input graph. The training of the GAE in DoG is divided into two phases. In the first phase, we only optimize the node reconstruction loss in LGAE for 1000 epochs. In the second phase, we optimize both the node reconstruction loss and the bi-level edge reconstruction loss in LGAE for another 1000 epochs. We use Adam optimizer with a learning rate of 0.001 for the training of the GAE. The weight docay is set to 10-5, We keep track of the exponential moving average (EMA) of the model during the training with a decay factor of 0.995. We set the number of clusters, K, in BLND to 100 in our experiments.
We use the AdamW optimizer to optimize the LDM with a learning rate of 0.0002 and a weight decay factor of 0.0001. The same embedding layer as in Classifier-Free Guidance (CFG) (Ho & Salimans, 2022) is used to encode the class information, which is described in Section B of the appendix. The guidance strength of CFG is set to 0.5 in our experiments. A three-layer Multilayer Perceptron (MLP) is used as the denoising model in the LDM, whose hidden dimension is set to 512. We train LDM for 3000 epochs and keep track of the exponential moving average (EMA) of the model during the training with decay factor of 0.995. We perform all the experiments in our paper on one NVIDIA Tesla A100 GPU. In Table in Scction E.4 of the appendix, we present the training time and data generation time of DoG.
Tuning To,T, and N' by Cross Validation. We tune the rank to, the weight for the truncated nuclear loss t, and the mumber of synthetic nodes N' by standard cross-valie validation on cach datasct with different models. Let rn = [7 min [N,d}] where 7 is the rank ratio. Let N' = B|Vr. where B characterizes the amount of synthetic nodes. We select the values of 7, т, and B by performing 5-fold cross-validation on 20% of the training data in each datasct. In addition, the models are trained for only 40% of the total epoch numbers in the cross-validation process. These strategies ensure the efficiency of the process. The value of y is selected from (0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9). The value of r is selected from {0.05, 0.1, 0.15,.1.0000 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5). The value of 8 is selected from {1, 2, 3, 4, 5, 6, 7, 8, 9, 10). The selected values of ru.T, and N' on each dataset for different models are shown in Table 10 in Section E.5 of the appendix. As shown in Table on different datascts is acceptable and does not largely increase the computation cost of the training process.
validaaiiot
Section E.5 of the appendix, the time for the cross-vall validation process
Compared Methods. In our experiments, first compare our method with eight semi-supervised node classification methods, namely GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), APPNP (Klicpera et al., 2019), S²GC (Zhu & Koniusz, 2020), SGFormer (Wu et al., 2023b), and EXPHORMER (Shirzad et al., 2023). In addition to semi-supervised node classification methods, we also apply DoG to graph contrastive learning (GCL) methods and compare them with eight state-of the GCL methods, including DGI (Veličkovié et al., 2019), GMI (Peng et al., 2020), GCA (Zhu et al., 2021), MVGRL (Hassani & Ahmadi, 2020), GraphMAE (Hou al., 2022), BGRL (Thakoor al., 2022). SGCL (Sun al., 2024), and GGD (Zheng al., 2022).
10

---

Published in Transactions on Machine Learning Research (02/2025)
5.2 Experimental Results
Semi-supervised Node Classification. To validate the effectiveness of Degree of Graph (DoG) in enhane- ing the performance of Graph Neural Networks (GNNs) for semi-supervised node classification, we applied DoG to augment the graph data in the training process of three distinct GNN architectures, including the vanilla GCN (Kipl' & Welling, 2017) and EXPHORMER (Shirzad et al., 2023). We train each model on the augmented graphs following their corresponding original implementation details. We use the standard split following the baseline methods (Kipf Welling, 2017; Shirzad et al., 2023) for all the nodes from the original graph. The syuthesized nodes are added to the training set. We run all experiments times and report the mean and standard deviation of the accuracy. Results in Table show that models incorporating DoG significantly outperform their corresponding baseline models, achieving state-of-the-a performance across all datasets. In addition, the results in Table 1 show that the data augmentation with synthetic graph structures alone, which are denoted as DoG w/o low-rank, also brings significant performance improvements over the base models. For example, DoG w/o low-rank improves the performance of EXPHORMER by 1.4% on Citeseer. Combined with low-rank regularization, the improvement. is further enhanced to 1.9%.
Table 1: Semi-supervieed node classification performance benchmark datasets. The best result is high- lighted in bold, and the sccond-best result is underlined. This convention is followed by all the tables in this paper. The number of synthetic nodes added into different datasets is deferred to Table 10 in Section E.5 of the appendix.
Methods
Cora
Citeseer
Pubmed
Coauthor CS
ogbu-arxiv
GCN (Kipf Welling, 2017)
81.7
70.5 +
79.4
92.9 0.1
71.7 0.3
GAT (Velifkovié et ol., 2018)
83.0 0.7
72.5 +: 0.7
79.0 =
93.6 0.7
73.2 th 0.2
APPNP (Kliepera al., 2019)
0.5
80.1 0.2
94.0 - 0.3
70.3 0.3
SPGC (Ziu & Kuniusz, 2020)
0.2
73.6 0.5
80.2 0.5
93.8 + 0.1
71.2 1 0.3
SGFormer (Wu et al., 2023b)
01.5
72.6
80.3
93.7 03.7
72.6 0.1
EXPHORMER (Shirzad et al., 2023)
81.1
72.9
83.2
95.7 + 0.2
72.4 0.3
DoG w/o low-rank (GCN)
83.0 0.3 1.3)
72.4::.33 1.9)
81.6 (.2)
94.0 1.1)
72.7 02770000
1.0)
DoG (GCN)
2.3)
73.6
3.1
0.3 3.4)
94.5
1.6)
1.4)
DoG w/o low-rank (EXPHORMER)
85.1
74.3
14)
813 0.3 1.1)
96.7 1.0)
73.4 0.6
1.)
DoG (EXPHORMER)
85.7 0.4 1.6)
74.8
0.2
1.9)
84.6 1 0.4
(1 1.4)
96.9 0.3 1.2)
73.4 0.3
Table 2: Node classification performance with features learned from graph contrastive learning on benchmark datasets. The best results on each dataset are highlighted in bold.
Methods
Cora
Citeseer
Pubmed
Conuthor CS
ogbu ogbu-arxiv arxiv
DGI (Velickovié al., 2019)
81.7 0.6
71.5 0.7
77.3 0.6
92.2 + 0.6
65.1 + 0.4
GMI (Peng al., 2020)
82.7 : 0.2
73.0 0.3
80.1 0.2
91.0 + 0.0
69.6 1: 0.3
GCA (Zhu et al., 2021)
82.7 + 0.2
73.0 +
80.1 + 0.2
91.0 + (10
69.6 + 0..
MVGRL (Hassaal & Almadi, 2020)
12.9.0.77
7.76
7.3
02.1
68.1 0.1
BGRL (Thakoor et al., 2022)
80.5
7..0
79.5
93.3
71.6 0.2
SGCL (Sun et al,, 2021)
82.5
7.
8..
93.3 0.2
71.0 0.1
GraphMAF (Hou
2022)
73.0
81.9
GGD (Zheng al, 2022)
83.9
73.0
8.88
02.7 0.4
71.6 1 0.5
DoG (MVGRL)
0.4 1.2)
(t 1.4)
81.8
(1 2.4)
93.5
1.4)
1.8)
DoG (GraphMA1s)
84.7 + 0.5 1.3)
74.3 0.9
(1 1.3)
83.2
0.5
1.3)
94.2
1.2)
72.8 + 0.2 1.0)
DoG (GGD)
85.2 + 0.5 1.3)
74.4 1
0.5
1.4
82.8
0.6
(1 1.5)
93.9 0.3
1.2)
73.0 0.3
1.4)
Graph Contrastive Learning. To demonstrate the power of DoG in augmenting the graph data for node-level learning tasks, also perform experiments for using DoG to perform data augmentation in the training of graph contrastive learning (GCL) methods. We adhere to the experimental settings described in previous works (Hassani & Ahmadi, 2020; Thakoor et al., 2022: Sun et al., 2024) on GCL. After finishing the GCL pre-training, the encoders of the GCL methods are used lo extract the node representations of all the nodes. Next, we evaluate the quality the node representations by training a logistic regression model on the training data of each datasct for node classification. We run all experiments 10 times and report the mean and standard deviation of the accuracy. Results in Table demonstrate that DoG significantly improves the performance of GCL methods. For instance, DoG (MVGRT.) improves the performance of
11

---

Published in Transactions on Machine Learning Research (02/2025)
MVGRL by 2.4% on Pubmed. In addition, DoG (MVGRL) improves the performance of MVGRL by an average of 1.64% across the five benchmarks.
5.3 Ablation Study
Ablation Study on the Low-Rank Regularization. In this section, we study the effectiveness of low- rank regularization in DoG for node classification. Since low-rank regularization is applied to mitigate the noise in the synthetic graph structures generated by the diffusson models, we compare low-rank regularization with two other data selection methods, namely TopoFilter (Wu et al., 2020) and NGC (Wu et al., 2021), that are proposed for learning with noisy data. Although the data selection methods are not specifically designed for learning with graph data, they can be easily adapted to perform data selection on the synthetic nodes added to the training set in the training process. GCN is used as the base model for this ablation study. It is observed from the results in Table 3 that low-rank regularization significantly improves the performance of node classification on the augmented graphs generated by DoG. DoG outperforms its counterpart with- out low-rank regularization by an average of 1.44% in classification accuracy on the five graph datasets. Furthermore, DoG outperforms the best results of the two data selection methods by an average of 1.02% in classification accuracy on the five graph datasets, highlighting its advantages in mitigating the adverse effects of noise in synthetic graph structures over existing methods.
Table 3: Ablation Study on the Low-Rank Regularization in DoG and Comparison with Data Selection Methods. The best results on each dataset are highlighted in bold.
Methodl
Syuthettc Graph
Sceucturrs
Cors
Citeseer
Pelmnd
Coauthor CS
oghn-araiv
GCN (Kigf& & Welling, 2017)
Na
81.7 + 0.4
+0.5++03
70.4
52.9 0.1
71.7+003
GCN with limmmok
No
82. 0.5 (19.9)
02 (1 (1))
810 it 1.6)
030 (1
72.4 (107))
wyo
(GUN)
You
12.1
DoG w/o low rank (GCN) Topafilbee (Wa es al., 2020)
Yos
53.0 0.5 (1 1.3)
72.
(1 L.8)
013100 (.)
03.6 0.220.2 (1 0.7
02.1103 (10.4)
DeG w/o low-rank (GCN) NGC (Wi et nl., 2021)
You
52.9 0.2 (1 1.3)
72.1=04 (1 L.)
812+
(1)))
032 (1 0.66
72.1206
DoG (GCN)
You
84.0 + 0.3
(1 23)
78.0- 0.4 (.3)
82.8 0.3 (144)
94.5+02. 1.6)
T&.1+08 (144)
In addition to studying the performance of low-rank regularization in mit miligating noise in synthetic graph structures. We also perform an ablation study by applying low-rank regularization to vanilla GCN trained on the original graph. The results in Table 3 show that applying low-rank regularization vanilla GCN can boost the performance by an average of 1.44% in classification accuracy on the five graph datasets. This improvement can be further boosted to 2.24% after combining augmentation with synthetic graph structures and low-rank regularization, demonstrating the effectiveness of augmentation with synthetic graph structures in DoG.
Comparison with Existing Node-Level Data Augmentation Methods. DoG is among the first to generate synthetic graph structures that improve the prediction accuracy of the GNNs for node classification by enlarging the size of the training set. The augmentation method of DoG is orthogonal to existing node- level data augmentation methods, which modifies the graph structure, node features, or training labels of nodos in the graph. In this section, we compare DoG with existing node-level data augmentation methods, NODEDUP (Guo et al., 2024), FLAG (Kong al., 2022),, GraphMix (Verma al., 2021), TADA (Lai et al., 2024), LGGD (Azad & Fang, 2024), and GeoMix (Zhao et al., 2024), which are surveyed in Section 2.2. In addition, we evaluate the performance of combining the DoG with the competing node-level data aug- mentation methods, where the node-level data augmentation methods are applied to the augmented graph generated by DoG. It is observed from Table that DoG performs better than all the competing node-level data augmentation methods. In addition, combining DoG with these nodc-level data augmentation methods further improves their performance on all the datasets. For instance, combining GeoMix with DoG improves the performance of GeoMix by 1.1% in node classification accuracy Pubmed.
A Ablation Study on the Balanced K-means Clustering in BLND. To verify the effectiveness of the balanced K-means clustering algorithm used in BLND, we perform an ablation study by replacing the balanced K-means clustering algorithm with random partitioning in the Bi-Level Neighborhood Decoder (BLND). Instead of splitting the nodes into 100 clusters with K-means, the nodes are randomly split into 100 groups, where each group has less than N nodes and N is the number of nodes in the graph. We also conducted a sensitivity analysis the value of K in the balanced K-means clustering Cora with
12

---

Published in Transactions on Machine Learning Research (02/2025)
Table 4: Comparisons between DoG and existing node-level data augmentation methods. The values in the parentheses are the improvements over the bascline model EXPHORMER (Shirzad et al., 2023).
Methods
Cora
Citeseer
Pubmed
Couuthor CS
ogbn-arxiv
EXPHORMER (Shirzud et ol., 2023)
72.9
83.2 +
95.7
72.4 0.3
DoG (EXPHORMER)
85.7 0.4 (6)
74.8 0.2 (19)
04.6 (t 1-4
9.9 (f 1.2)
+34 (f 1-0)
NODEDUP (EXPHORMER) (Gao es al, 202))
0. (.66
73.7
(T
0.6
(T
9. (T
72.72022 (T
NODEDUP DoG (EXPHORMER)
85.8 (1
7.
(1
84 (77
97.0
7..5
FLAG (EXPHORMER)) (Kong 2012)
0.3 1.2)
1..3 (3)
13.
(1 0.6)
96.0
(1 0.3)
72.7 (1
FLAG + DoG (EXPHORMER)
83.8 (17
7..1
(1
8..0 (t))
9..0 (t))
T..7 (t))
GraphMix (EXPHORMER) (Verma es al. 2021)
0.3 1.1
74.2
0.3
(1
0.5
(f
96.1 (f0.4)
02 (f..4)
GraphMix DoG (EXPHORMER)
0.5 2.0)
75.2.000
0.5
2.3)
85.0
0.4 L8)
97.1 (144)
73.6
(.2)
TADA (EXPHORMER) (Lai et al., 20141)
8.34 (3)
74.4 (T
84. (.8)
963
(T (T
7.6
(T
TADA + DoG (EXPHORMER)
86.5
(f 244
75.5
(f 2.)
85.1 (9
97.0 (.
13.5 (t
LGGD (EXPHORMER) (Avad Fang 2024)
85.5 0.4
1.4
74.2
1.3)
83.9 0.3 (.7)
96.2 (1))
72.7
0-74000 0.3 (.))
LGGD + DoG (EXPHORMET))
86.2 2 0.5
(1)
75.1 0.5
2.2)
84.8 1 0.4 (6)
96.8
(1)
73.7
0.5
(1)
GeoMix (EXPHORMER) (Zlaao et al. 202)
85.0 0.3
(T9.
0. (T13)
81.1 (F
9..1 (T
72.7 (T
GeoMix + DoG (EXPHORMER)
86.3 0.5
2.2)
75.3 0.5 (144
86.2
(.0)
97.2
(1 1.5)
73.8 0.3
1.4)
GCN as the base model. The results in Table 5 demonstrate that balancod K-means clustering significantly outperforms random partitioning, Furthermore, the performance of DoG with BLND is not sensitive to K.
Table 5: Ablation Study on Balanced K-means Clustering in Bi-Level Neighborhood Decoder (BLND).
Cluster Number K
10
25
50
100
150
200
100 (Random Partition)
Cora ACC
84.1
83.9
84.0
84.0
83.9
83.8
82.8
In addition, we present the evaluation results of DoG on heterophilic graph datasets in Table 7 in Section E.2 of the appendix. We evaluate the quality of the generated synthetic graph structures on different graph datasets in Table 8 in Section E.3 of the appendix. The training time and synthetic data generation time of DoG are presented in Table 9 in Section F.4 of the appendix. The ablation study in Table 12 in Section F.6 of the appendix demonstrates the effectiveness of the synthetic graph structures by comparing with ablation models, which also increase the number of nodes in the graph. Table 13 in Section E.7 of the appendix shows that DoG is also evfective in augmenting large-scale graphs for semi-supervised node classification.
6 Conclusions
In this work, we propose novel graph diffusion model termed Diffussio on Graph (DoG). DoG is designed to generate synthetic graph structures, which consist of the syuthetic nodes and the synthetic edges connecting to the synthetic nodes. The synthetic graph structures generated by DoG can then be combined with the original graph to form an augmented graph for the training of node-level learning tasks, including node classification and graph contrastive learning. In addition, a Bi-Level Neighbor Map Decoder (BLND) is introduced in DoG to improve the efficiency of the generation process. To mitigate the adverse effect of the noise roduced by the synthetic graph structures, a provable low-rank regularization method is proposed. Extensive experiments on various graph datasets for both node classification and graph contrastive learning have been performed to demonstrate the effectiveness of DoG.
Acknowledgments
This material is based upon work supported by the U.S. Department of Homcland Security under Grant Award Number 17900AAC0001-00-000 The views and conclusions contained in this docunent are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security. This work is also partially supported by the 2023 Mayo Clinic and Arizona State University Alliance for Health Care Collaborative Research Seed Grant Program.
13

---

Published in Transactions on Machine Learning Research (02/2025)
References
Abdullah Alchihabi, Qing En, and Yuhong Guo. Efficient low-rank gnn defense against structural attacks. In 2023 IEEE International Conference on Knowledge Graph (ICKG), pp. 8. IEEE, 2023.
Amitoz Azad and Yuan Fang. A learned generalized geodesic distance function-basee approach for node feature augmentation on graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp. 49 58, 2024.
Shekoofeh Azizi, Simon Kornblith, Chitwan Saharia, Mohammad Norouzi, and David J Fleet. Synthetic data from diffusion models improves imagenet classification. Transactions on Machine Learning Research, 2023.
Hritik Bansal and Aditya Grover. Leaving reality to imagination: Robust classification via generated datasets. arXiv preprint 2xxi::2302.02500 2023.
Dmitry Baranchuk, Andrey Voynov, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Label-efficient semantic segmentation with diffusion models. In The Tenth International Conference on Learning Repre- sentations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
P. Bongini, M. Bianchini, and F. Scarselli. Molecular graph generation with graph neural networks. Stat, 2021.
Zhou Cai, Xiyuan Wang, and Muhan Zhang. Latent graph diffusion: A unified framework for generation and prediction on graphs. Xrxiv preprint arXiv:2402.0055 2024.
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Thibault Castells, Hyoung-Ky Kyu Song, Bo-Kyeong Kim, and Shinkook Choi. Ld-pruner: Efficient pruning of latent diffusion models using lask-agnostic insights. CoRR, abs/ abs/2404.119938 2024. doi: 10.48550/ARB ARXIV. 2404.11936, URL https: //doi. org/10. httgg/..8850//////
arxiv 2404. 11936.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. Tn International Conference on Machine Learning, 2020.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177, 2020.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092-22108 2020.
Wenzheng Feng, Yuxiao Dong, Tinglin Huang, Ziqi Yin, Xu Cheng, Evgeny Kharlamov, and Jic Tang. GRAND+: scalable graph random neural networks. In WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pp. 3248 3258. ACM, 2022.
Hengyu Fu, Zhuoran Yang, Mengdi Wang, and Minshuo Chen. Unveil conditional diffusion models with classifier-free guidance: A sharp statistical theory. arXiv preprint or 1 19968, 2024.
Sicheng Gao, Xuhui Liu, Bohan Zeng, Sheng Xu, Yanjing Li, Xiaoyan Luo, Jianzhuang Liu, Xiantong Zhen, and Baochang Zhang. Implicit diffusion models for continuous super-resolution. In IEEE/CVE Conference Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023, pp. 10021-10030. IEEF, 2023.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
Zhichun Guo, Tong Zhao, Yozen Liu, Kaiwen Dong, William Shiao, Neil Shah and Nitesh V Chawla. Node duplication improves cold-start link prediction. Xixie preprint arXim:2422.09711 2024.
14

---

Published in Transactions on Machine Learning Research (02/2025)
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. CoRR, abs/2210.015499, 2022. doi: 10.48550/ARXI ARXIV. 2210.01549. URL attps://doi.orgg htrg//..8850//// arXiv wwt..2220.... 01549.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Newral Information Processing Systems, 2017.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Tvor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8536 8546, 2018.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pp. 8230-8248. PMLR, 2022.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In Proceedings of the 37th International Conference on Machine Learning, TCML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 4116 4126. PMLR, 2020.
Ruifei He, Shuyang Sun, Xin Yu, Chuhui Xue, Wenqing Zhang, Philip Torr, Song Bai, and Xiaojuan Qi. Is synthetic data from generative models ready for image recognition? arXiv preprint arXiv:2210.07514 2022.
Jonathan Ho and Tim Salimans. Classifier-free diffusion guidance. arXiv preprint arXic:2207.1259. 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffuusio probabilistic models. In Advances Neural Information Processing Systems 33: Annual Conference on Newral Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020. URL https: attps://proceedings wttpeeediinnnnuuusss.comm neurips.cc/pappr/ Abstract..taat htmll
2020/hash/
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjic Wang, and Jie Tang. Graphmae: Self-supervised masked graph auloencoders. In Aidong Zhang and Huzefa Rangwala (eds.), KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14- 18, 2022, pp. 594 604. ACM, 2022.
Qingsong Hu, Deyu Zhang, Wei Zhang, and Xuelong Li. Truncated nuclear norm regularization for tensor completion. Xixiv preprint arXiv: 1777007777 2013.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datascts for machine learning on graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. In Advances in Neural Information Processing Systems, 2019.
Roshni G Iyer, Wei Wang, and Yizhou Sun. Bi-level atlention graph neural networks. In 2021 IEEE IEEE, 2021.
International Conference on Data Mining (ICDM), pp.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery E data mining, pp. 66 74, 2020.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, ICML 2022 17- 23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 10362 10383. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Regresentations, TCLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.nel, 2019. URL https: http:///epeeeeeeeeetteee
Forum?id-HigL- 249Ym.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Robust optimization data augmentation for large-scale graphs. In IEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pp. 60-69. IEEE, 2022. doi: 10. 10.119/CVVPR5268.20222 202.8 000116. URL https://doi. org/ 10. 1109/CVPP526688 2022.00015.
Yurui Lai, Xiaoyang Lin, Renchi Yang, and Hongtao Wang- Efficient topology-aware data. augmentation for high-degree graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1463-1473, 2024.
Shiye Lei, Hao Chen, Sen Zhang, Bo Zhao, and Dacheng Tao. Image captions are natural prompts for text-to-image models. arXiv preprinl ar xrx:::207..00 08526, 2023.
Daiqing Li, Huan Ling, Seung Wook Kim, Karsten Kreis, Sanja Fidler, and Antonio Torralba. Bigdataset- gan: Synthesizing imagenet with pixel-wise annotations. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognátion, pp. 21330-22 21330-21340, 2022.
Stratis Limnios, Praveen Selvaraj, Mihai Cucuringu, Carsten Maple, Gesine Reinert, and Andrew Elliott. Sagess: Sampling graph denoising diffusion model for scalable graph generation. CoRR, abs/2306.1668/) 2023. doi: N0.48550/ARXI www.AAII............. 1600..68877 URL https://doo http:/doooorree. org/10. atgg/1..4550000 48550/arXiv.. 230..168222
Jinyu Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Low-rank tensor completion by truncated muclear norm regularization. arXiv preprint arXic:1712.00704, 2017.
Justin Lovelace, Varsha Kishore, Chao Wan, Eliot Shekhtman, and Kilian Q. Weinberger. Latent diffusion for language generation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in newral information processing systems, 35:1362-115 1375, 2022.
Liheng Ma, Reihaneh Rabbany, and Adriana Romero-Soriano. Graph attention networks with positional embeddings. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 514-527. Springer, 2021.
Mikko I Malinen and Pasi Fränti. Balancod k-mcans for clustcring. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, St SSPR 2014, Joensuu, Finland, August 20-22, 2014. Proceedings, pp. 32-41. Springer, 2014.
Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia-basee based benchmark for graph neural networks. arXiv preprint orXi:22007.000) 2020.
Joshua Mitton et al. A graph vae and graph transformer approach to generating molecular graphs. Tn Proceedings of the International Conference Machine Learning (ICML), 2020.
Byconghu Na, Ycongmin Kim, HeeSun Bac, Jung Hyun Lee, Se Jung Kwon, Wanmo Kang, and II chul Moon. Label-noise robust diffusion models. In The Twelfth International Conference on Learning Representations, 2024. URL https: ttttps://operrweeee http///wppeeeeeeee//////ee/o.eep wttpe/iiiiineneeeeeeeeeeeeee
16

---

Published in Transactions on Machine Learning Research (02/2025)
Duc Tam Nguyen, Chaithanya Kumar Mummadi, Thi-Phuone Thi-Phhoogg-Nhung Ngo, Thi Hoai Phuong Nguyen, Laura Beggel, and Thomas Brox. SELF: learning to filter noisy labels with self-ensembling. In 8th International Conference on Learning Representations, 1CLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- view.nct, 2020.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistie models. In International Conference on Machine Learning, pp. 8162-8171. PMLR, 2021.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation
invariant graph generation via score-based generative modeling. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pp. 4474-4484. PMLR, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview nct, 2020.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW, 2020.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In IEEE/CVF Conference on Computer Vision and Pattern Recognilion, CVPR 2022, New Orlenns, LA, USA, June 18-24, 2022, pp. 10674 10685. IEEE, 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropodge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httt:s:://ppenrviieee wtwpeenrwviee.eeefffrreeeeeeeeee net/forum? id=HkxiqqrKPr.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily I. Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text- to-image diffusion models with deep language understanding. Advances in Newral Information Processing Systems, 35:36479-880 04644496-6444,,, 2022.
Mert Bülent Saryildız, Karteek Alahari, Diane Larlus, and Yannis Kalantidis. Fake it till you make it: Learning transferable representations from synthetic imagenet clones. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8011-8021, June 2023.
Berkant Savas and Inderjit S Dhillon. Clustered low rank approximation of graphs in information science applications. In Proceedings of the 2011 SIAM International Conference on Data Mining, pp. 164-175.
SIAM, 2011.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Col- lective classification in network data. AI Mag., 29(3):93- 2008a.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- tive classification in network data. Al magazine, 29(3):93-93) 93, 2008b.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Xrxiv preprinl Xrxiv:1811.0055 1.85668, 2018.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 31613-31632. PMLR, 2023.
Jascha
Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis R. Bach and David M. Blei (ods.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 2256 2265. JMLR.org, 2015.
17

---

Published in Transactions on Machine Learning Research (02/2025)
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jac-Gil Lee. Robust learning by self-transition for handling noisy labels. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao (eds.), KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 1490-1500. ACM, 2021a.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Trans. Neural Networks Learn. Syst., 34(11):8135 8153, 2023. doi: 3152227. URL attpp://doi. //tp//iio/////////////ooo/////// 1109/TNNLS. 2022. 3152527.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenRe- netw 2021b.
Yang Song and Stelano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Newral Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11895 11907, 2019a.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In 2019b.
Advances in Newral Information Processing Systems, pp.
Yang Song and Stefano Ermon. Improved techniques for training score- based generative models. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Sys- tems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training of score-basek diffusion models. In Advances in Newral Information Processing Systems 34: Anauaa Conference on Newral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 1415-1428, 2021c
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Scoro-based generative modcling through stochastic differential equations. 9th International Conference on Learning Represeniations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.ned 2021d.
Wangbin Sun, Jintang Li, Liang Chen, Bingzhe Wu, Yatao Bian, and Zibin Zheng. Rethinking and simplifying bootstrapped graph latents. In Laz Angelica Caudillo-Mata, Silvio Lattanzi, Andrés Muñoz Medina, Leman Akoglu, Aristides Gionis, and Sergei Vassilvitskii (eds.), Proceedings of the 17th ACM International Conference on Web Search and Data Minning, WSDM 2024, Merida, Merico, March 4-8, 2024, pp. 665 673.
ACM, 2024.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Velickovic, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In The Tenth International Conference on Learning Representatiinns, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview net, 2022. URL http:p/:/gggaooooooo.oo//////oss
Yonglong Tian, Lijie Fan, Phillip Isola, Huiwen Chang, and Dilip Krishnan. Stablerep: Synthetic images from text-to-image models make strong visual representation learners. arXiv preprint ar arXiv:2306.0090 009884 2023.
Brandon Trabucco, Kyle Dohorty, Max Gurinas, and Ruslan Salakhutdinov. Effective data augmentation with diffusson models. arXiv preprint arXiv:2302.079) 079444 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL https:
/ //openrevies wtt://orum/iddrrriieet
18

---

Published in Transactions on Machine Learning Research (02/2025)
Petar Veličkovié, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In International Conference on Learning Regresentations, ICLR, 2019.
Joshua Vendrow, Saachi Jain, Logan Engstrom, and Aleksander Madry. Dataset interfaces: Diagnosing model failures using controllable counterfactual generation. arXiv preprint wxXiu2292.008666 2023.
Vikas Verma, Meng Qu, Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10024 10032, 2021.
Clément Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview 2023a.
Clement Vignac et al. Digress: Discrete denoising diffusion for graph generation. In Proceedings of the International Conference on Learning Representations (TCI.R) 2023b.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The world wide web conference, pp. 2022-2002 2032, 2019.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujum Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663-3674, 2021.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (cds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019. URL http://proceedinge mlr. www..presssvvv.. http//9//uuuu wwlee. html.
Pengxiang Wu, Songzhu Zheng, Mayank Goswami, Dimitris N. Metaxas, and Chao Chen. A topological filter for learning with label noisc. In Advances in Newral Information Processing Systems 39: Annual Conference on Newral Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Qitian Wu, Wentao Zhao, Zenan Li, David P. Wipf, and Junchi Yan. Nodelormer: A scalable graph structure learning transformer for node classification. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28-
December 9, 2022. 2022.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixian He, David Wipf, and Junchi Yan. Difformer: Scalable (graph) transformers induced by energy constrained diffusion. In The Fleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net net, 2023a. URL
https://openrevieet wtdp:/ttttaadddd///eaaaaa
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large- graph representations. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Arnual Conference on Neural Information Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023b.
Zhi-Fan Wu, Tong Wei, Jianwen Jiang, Chaojie Mao, Mingqian Tang, and Yu-Feng Li. NGC: A unified framework for learning with open-world noisy data. In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pp. 62 71. IEEE, 2021. doi: URL sttps://doi..e
10. CTt.//CCCV9992.201.....
1109/ICCV48922 2021.000111
Hui Xu, Liyao Xiang, Jiahao Yu, Anqi Cao, and Xinbing Wang. Specdup robust graph structure learning with low- oorrannk information. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2241 2241-2250, 2250, 2021.
19

---

Published in Transactions on Machine Learning Research (02/2025)
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Represenlations, 2019.
Yiming Yang and William W Cohen. Singular value pruning of deep neural networks with application dialogue response selection. arXiv preprint arXin: 08865, 2015.
Yingzhen Yang. Sharp generalization of transductive learning: A transductive local rademacher complexity approach. arXiv preprint orXiv:2309.66855 2023.
Yuewei Yang, Xiaoliang Dai, Jialiang Wang. Peizhao Zhang, and Hongbo Zhang. Efficient quantization strategics for latent diffusion models. CoRR, (bs/2312.05443) 2023.
Jiaxuan You, Rex Ying, and Jure Leskovee. Position-aware graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Mochine Learning Research, pp. 7134-7143. PMLR, 2019. URL http:::/ppocceednggee mlr. pte.rr.rss///eee. /tpass/v//// you/ly html.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advonces in Newral Information Processing Systems 39: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL
cheurips.cccppper//200
24220446012223312448fffffaaa Abstract. html.
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor W. Tsang, and Masashi Sugiyama. How does disagroe- ment help generalization against label corruption? In Proceedings of the 36th International Conference Machine Learning, 1CML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7164-7173. PMLR, 2019.
Jianhao Yuan, Francesco Pinto, Adam Davics, Aarushi Gupta, and Philip Torr. Not just pretty pictures: Text-to-image generators enable interpretable interventions for robust representations. arXie preprinl arXiv:2912.11291 2022.
Junhai Zhai, Sufang Zhang, Junfen Chen, and Qiang He. Autoencoder and its various variants. In 2018 IEFE international conference on systems, man, and cybernetics (SMC), pp. 415-419. IEFE, 2018.
Xinyu Zhang, Guanghui Wang, Xiangzhao Li, Xuelin Liu, and Wei Liu. An efficient tensor completion method via truncated nuclear norm. ScienceDirect, 2020.
Yuxuan Zhang, Huan Ling, Jun Gao, Kangxue Yin, Jean-Francois Lafleche, Adela Barriuso, Antonio Tor- ralba, and Sanja Fidler. Datasetgan: Efficient labeled data factory with minimal human effort. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 10145-10155, 2021.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11015-11023, 2021.
Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. IEEE Dala Eng. Bull., 46(2); 140-165, 2023. URL http://sites.comg/
org/ debull/A23jjaaaaee Aaaia//23jnn//ppp0e pdf.
Wentao Zhao, Qitian Wu, Chenxiao Yang, and Junchi Yan. Geomix: Towards geometry-awane data augmen- tation. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4500 4511, 2024.
Yizhen Zheng, Shirui Pan, Vincent C. S. Loe, Yu Zheng, and Philip S. Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information
20

---

Published in Transactions on Machine Learning Research (02/2025)
Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Cai Zhou, Xiyuan Wang, and Muhan Zhang. Latent graph diffusion: A unified framework for generation and prediction on graphs. CoRR, abs 2222222222221122 2024. doi: 10. 10.48550/ AAA/V.22TT2.22221111 URL https: //doi.oor/100 200.0.48500//.ii../ 240..22222000 2402.02518. 02518.
Yongchao Zhou, Hshmat Sahak, and Jimmy Ba. Training thin air: Improve image classification with generated data. Xrviv preprint orXi:22305155110 2023.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International conference on learning representations, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Jure Leskovec, Marko Grobelník, Marc Najork, Jie Tang, and Leila Zia (eds.), WWW '21 The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pp. 2069 2080. ACM/ / IW3C2, 2021. doi: 0.1145/3442231 3349880. URL https://doi. org/10 /0 1114444444228111 3449802.
Yanqiao Zhu et al. A survey on deep graph generation: Methods and applications. In Proceedings of the Learning on Graphs Conference. PMLR, 2022.
A Theoretical Results
Our low-rank regularization is thooretically inspired by Theorem A.1 in this section. We consider the semi- supervised or transductive node classification task on the original graph formulated in Section 3.1. The results can be straightforwardly applied to the augmented graph with the original graph replaced by the augmented graph.
Following the standard setting transductive learning, we suppose that a set VL with V2l m is sampled uniformly without replacement from V as the labeled training nodes, and the remaining nodes Vo V/. are the test nodes. Let. Y = [yı;y;; ... vy {0, 1] N be the ground truth label malrix of all the nodes in the original graph. Using the features H I Nxd the original graph generated by the methods describe in Section 4.3, the optimization problem of semi-supervised or transductive node classification is
1 min I(W) We
Σ KL (y,, [softmax (HW)).) #EVV
m
For a matrix with rows, we use [A] to denote the submatrix of A formed by rows of A corresponding the test nodes, that is, all the rows A; with v; Vo form the submatrix [A]ys [A]y, defined in the same way. For the gram matrix K = НA with eigenvalues Xι 2 Xe... 2 ÅN, denote by the submatrix of K formed by rows and columns of K corresponding to nodes in
Rv = [H] H Vz Vz.
We define F(W,t) == (W the output of the classifier after the t-th itcration of gradient descent L(W) for 2 1. We have the following theoretical result on the loss of the unlabeled test nodes Va measured by the gap between F( F(W,t) and Y.
Thcorem A.1. Let m 2 cN for a constant (0, 1), and To E [N]. Assume that V, with V2 m sampled uniformly without replacement from V as the labeled training nodes, and the remaining nodes Vo V Vz. the test nodes. Then for every >> O, with probability least. exp(-r), after
21

---

Published in Transactions on Machine Learning Research (02/2025)
the t-th iteration of gradient descent on the training loss L(W) for all t 2 we have
Urest (t) = - F(W,t) -1] 10ull
m (Ix (IN vv [ + c1t
1 u
mm
H
C2
+
+
(3)
m
m
u
where ||
En Erero di 01.01 are positive numbers depending on {di)iem and to with o8
r0 K
maX4e[N]
2 It noted that Usett (1) = 1/u. [F( () &l FF Fuclidean distance between the classifier output F(W.4 t) and the training label matrix Y. We remark that the truncated nuclear norm H appears on the RHS of the upper bound (2).
the test loss of the unlabeled nodes measured by the
A.1 Upper Bound for the Test Loss of GNN trained the Augmented Graph
We now consider the bound for the test loss of a GNN trained the augmented graph. Suppose that the labeled training nodes in the augmented graph V/, are sampled uniformly without replacement from all the nodes of the augmented graph, V V and the remaining nodes Vy = [N] VE are the test nodes. By applying Theorem A.1 to the augmented graph and using fcatures in Section 4.3 to replace the features H in Theorem A.1, we conchude that the test loss of a GNN trained on the augmented graph is bounded by
Usest (t) = [F(W 11voll
[IN K v2. M1
|| + ciro
(++ u m = H 4
+
H
C2
m
u
where |H], is the truncated nuclear norm defined in Section 4.3, co, C1, C2 positive numbers depending on {1
je[ja and to with T max Kü;- KyL.e. = H) H v. the submatrix of K defined
Scction 4.3 formed by rows and columns of K corresponding nodes VL-
(4) icelretically justifies the usage of the truncated nuclear norm |H] in the regularized training loss (2) for GNNs on the augmented graph, as smaller ||]] leads to tighter bound for the test loss. Moreover, when the low frequency property holds, which is usually the case demonstrated by Figure 5 in Section C of the appendix,
(IN - r.. [y,, would be very small with enough itcration number
A.2 Proof of Theorem A.1
We present the proof of Theorem A.1 below.
Proof. It can be verified that at the t-th iteration of gradient descent for t 2 1, we have
w w - [
1w Y T),
(5)
Tt follows by (5) that
H
((()_ H vs. (t-
H vi
H Vr.
(w -
V.
V2.
H V/ (t--1) nT Dr....
Hw _ Y
(6)
v..
22

---

Published in Transactions on Machine Learning Research (02/2025)
With F(W.t) Hw it follows by (6) that
()(,()- 4) (Im vyKve. [F(W1 ([W,t-1) -1) -1 -Y
It follows from the above equality that
F(W,0) 1) - 1ly = (IN - mR (F(W.0) (FV..)))((((W))) -81y = (IN - nkvvo "
(7)
so that As a result. of (7); we have
F(W,t)- - YY --11 - (INN-nkuLna)) [ [8]v
(8)
We apply [Corollary 3.7] (Yang, 2023) to obtain the following bound for the Lest loss FI
Yl l
F(W, (1) -Y]
cu -ec F(W, 1) Y
Vz 1
G
min r(u, m. Q)
(9)
m
05Q5n
with
Σ
X
Σ
X
r(u, Q) = Q
@==++ -
+
9=Q+1
+
q=Q+1
m
m
where co, C2 are positive numbers depending on (dolee(N) and To with r = maxie[N] K It follows by (7) and (9) with Q = ro that
1 F(W. t) 17c, c l
X
Σ
0
[ (IN kk kv..v
[
2 vr.
+ taro
+ 1 +
g
7=70+ +1
+
C2
(10)
which completes the proof using the notation | rr = Em do.
B Preliminaries of Diffusion Models
Diffusion models (DMs) (Sohl-Dickstein et al., 2015; Ho et al., 2020) are latent variable models that model the data Xo as Markov chains Xy Xo, with intermediate variables sharing the same dimension. DMs can be described with two Markovian processes: a forward diffusion process q(x1:7 Xn) = I g(x; xx-1) and reverse denoising process (x(xoT)) p(xx) IT (x Gaussian noise to data x;:
xx). The forward process gradually adds
q(x: xx-1) = N(xx; /1 1,1).,
(11)
where the hyperparameter S1T controls the amount of noise added at each timestop The 3ur are chosen such that samples Xy can approximately converge standard Gaussians, i.c., q(xr) WO I). Typically, this forward process q is predefined without trainable parameters.
23

---

Published in Transactions on Machine Learning Research (02/2025)
The generation process of DMs is defined as learning a parameterized reverse denoising process, which aims to incrementally denoise the noisy variables xr.1 to approximate clean data X in the target data distribution:
Po (x x,) = M4 t). t). P²T).
(12)
where the initial distribution p(xT) is defined as (0, The means 14 typically are neural networks such as U-Nets for images or Transformers for text, and the variances P: typically are also predefined.
As latent variable models, the forward process (x (x)) can be viewed as a fixed posterior, to which the reverse process Pe (Xo.T) is trained to maximize the variational lower bound of the likelihood of the data. However, directly optimizing the likelihood known to suffer serious training instability (Nichol & Dhariwal, 2021). Instead, (Song & Ermon, 2019b; Ho et al., 2020) suggest simple surrogate objective:
LDM = N0.,--l ex(x))))1 1
(13)
Intuitively, the model is trained to predict the noise vector to denoise diffused samples X, at every step t towards a cleaner one X,-1. After training, we can draw samples with Eo by the iterative ancestral sampling:
Be
X
3 X
Eo (x,,,)))) t)) + PLE,
(14)
v1
VI-
with E ~ (O,, I). a and 3, are constants with regard to the time t. The sampling chain is initialized from Gaussian prior Xy ~ p(X+) = (Xxr;;;;0 I)
Latent Diffusion Models (LDMs) (Rombach et al., 2022) extend the capabilities of standard Diffusion Models (DMs) by introducing latent space representation that reduces the dimension of the data involved in the diffusion process. In LDMs, data X, is first mapped to lower-dimensional latent representation Zo: which undergoes the diffusion process instead of the high-dimensional original data. This mapping is defined by an encoder network ge() = Zo. The forward process in LDMs involves gradually adding Gaussian noise to the latent representations Z.
(Z, Z,-1) = N(Z v1 3,2.-1,881
(15)
where Bur are hyperparameters controlling the noise addition, similar to DMs. The reverse process in LDMs aims to reconstruct the clean latent representation Zo from the noisy representation Zr by:
po (Z Z.) = 1:
IT),
(16)
with the reconstructed latent data Zo subsequently transformed back to the original data space using a decoder network ga(Z)) = Xo. This lover-dimensional approach enhances computational efficiency and often improves the quality of the generated samples.
Classifier-Free Guidance (CFG) (Ho & Salimans, 2022) combines conditional noise predictor Ex(,,, C, and unconditional noise predictor e cx(X,, in the sampling process improve sample quality and enforce class guidance. CFG can be easily incorporated into LDMs with the sampling process formulated as follows:
B.
X -1-B
X,
E)) + PLE,
(17)
VI-ap
where Z ~ ~O. a, 3r and P are constants with regard to the time é, (1+w)e,(X, -eo) and w is the guidance factor.
C Low Frequency Property
In this section, we propose the low frequency property, which suggests that the low-rank projection of the ground truth clean labels possesses the majority of the information of the clean labels, and projection of the label noise mostly uniform over all the eigenvectors of kernel matrix used classification. The cigen-projection and the signal concentration ratio on five graph datasets, including Cora, Citescer, Pubmed, Coauthor-CS, and ogbn-arxiv, illustrated in Figure 5.
24

---

Published in Transactions on Machine Learning Research (02/2025)
0.5
0.5
Brolection Valti
0.55
Projection Value
1.44
Projemtio Value
6.4
0.3
Projection
6:3
0.33
8.3
0.2
0.11
0.0
0.0
0.D
6.00
0
500
1000
1500 2000 2500
1000
2000
3030
5000
15000
15000
20000
0
5000
10000 Rank
15000
20000
540041
1000000 150000
Rank
Zank
Rank
Rank
Concerattion
1.0:
Energy Concentation
1.3
Cowcertation
1.0:
Energy Concestation
1.0
Lineego Concenzation
8.0
0.8
0.8
8.c
a.-
%
n.6
n6.
0.4
0.4
0.4
302-
2:
0.0
o.
30'0
5000
10000
15000
20000
50000 200000 150000 Rank
Ronk
Rank
(a) Cora
(b) Citeseer
(c) Pubmod
(d) Coauthor-CS
(c) ogbn-arxiv
Figure 5: Eigen-projecteo projection (first row) and signal concentration ratio (second row) the augmented graph for Cora, Citeseer, Pubmed, Coauthor-CS, and ogbn-arxiv. To compule the eigen-projection, we first calculate the eigenvectors U of the kernel gram matrix K RNNN computed by feature matrix F E R-vxd, then the projection value is computed by p= - EE Y / E IR", where C is the number of classes, and E {0, 11 is the one-hot labels of all the training data in the augmented graph, Y(e)) is the e-th column of Y. The eigen-projection eigenvector of K, and the signal concentration ratio of a rank r reflects the proportion of signal projected onto the top r cigenvectors of K. The signal concentration ratio for rank r is computed by ||p()>>)]/ 1|2 where p (lir) contains the first r elements of p. For example, by the rank ratio of Y for Cora, Citeseer, and Pubmed are 0.844, 0.809, 0.784, 0.779, and 0.787, respectively. We refer to such property as the low frequency property, which suggests that we can learn a low-rank portion of the observed label Y, which covers most information in the ground truth clean label while only learning a small portion of the label noise.
for E [min(N, d)] reflects the amount of the signal projected onto the r-th
0.2 min {N.d}, d]. the signal concentration
D Algorithms for the Training of DoG and the Generation of the Augmented Graph
The training process of the DoG consists of two steps, which are detailed in Algorithm 1. The first step, which is from Line 1 to Line 5 in Algorithm 1, describes the training of the GAE on the original graph. For each of the nodes in the original graph, the encoder of the GAE encodes the node attributes of the given node, the node attributes of its neighbors, and the binary neighbor maps of edges connecting to that node into the latent representations. The positional embeddings of the given node and its neighbors are added their node attributes to encode global positional information. The decoder of the GAE then reconstructs the node attributes of the given node and the binary neighbor maps of edges from the latent representations. The training of the GAE is supervised by the MSE loss. The second step, which is from Line 7 to Line 13, describes the training of the LDM the latent representations of the nodes in the original graph following the standard training process as in (Rombach et al., 2022).
Algorithm& 2 describes the generation process for the augmented graph Gung, which also consists of two steps. In the first step, the conditional diffussin model generates a synthetic latent representation from a randomly sampled Gaussian noise given a node label. In the second step, the decoder of the GAE uses the senthetic latent representation to reconstruct the node attributes and the binary neighbor maps of edges connecting the synthetic node to authentic nodes in the original graph.
E
Additional Experiments
E.1
Datasets
In our experiment, we evaluate our method on five public benchmarks that are widely used for node repre- sentation learning, namely Cora, Citeseer, Pubmed (Sen et al., 2008a), Coauthor CS, and ogbn-arxiv (Hu
25

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 1 Training DoG (Training the GAE and the LDM)
Algorithm Generation the Augmented Graph Saug
Imput:
The iaput attribute matrix X, adjacency matrix A, the train- epochs of the GAE fOAR, the labels Y,, of the labeled nodes
Imput:
The imput attribute matrix X, adjacency matrix A. the training epechs of the GNN faNN, the number of
VL. and the training epochs of the LDM (LDM
added nodes M, and the labels of the synthetic data
Output: The parameters of the GAE and the parameters of the
LDM 0
Output: The augmented graph
Saug
= (V
Obtain inter-cluster neighbor map and the intra-cluster neighbor map M by spplying balanced K-Meamms clustering
Deyn. Xang. Aang).
1: for i to M do
X
2: Sample Gaussian noise ()
2: Initialize the parameter of the GAE
3: Set the class label of the i-th synthetic node to gi
3: for I ++1 1 to ÉCAE do
Update w by 5: end for Initialize the parameter 8 LDM.
LLLLE with LOAR from (q.(1)
Generate H; from & with the LDM for class yi
end for
6: Derode 2 = {2.),-² to Xayn and Aayn with the decoder
7: Map the node attributes X and the adjacency matrix A to the latent space using the encoder de of the GAE as H = (X. FLDM da
of the GAE as Sayn = ge(lZ)
7: Get Asug = [A Asyn A) and Xang = X: Xayal
8: for 1
return Sloug (VU Vayur Xaug- Anms)
9: Sample Gaussian noise ~ N(O.1)
10: Get latent feature Zu [Z.|e: E V2) V2
11: Update 0 by 0 +- 0 Ve (Zz. YL) 2|1
12: end for
13: return The parameters of the GAB and the parameters of the
LDM 0
et al., 2020). Cora, Citesoer, and Pubmed are the three most widely used citation networks, where nodes are documents and edges are citation links. Coauthor CS is a co-authorship graph based on the Microsoft Academic Graph from the KDD Cup 2016 challenge. Nodes in Coauthor CS are authors that are connected by an edge if they co-authored paper. Node features represent paper keywords for each author's papers, and class labels indicate the most active fields of study for each author. Nodes in the ogbn-arxiv dataset are publications from the arXiv with comprehensive node features derived from paper abstracts, which are used to predict the subject area of cach paper. Edges in the ogbn-arxiv datasct represent citation relationships between papers. For all our experiments, we follow the default separation (Shchur al., 2018; Mernyei & Cangea, 2020; Hu et al., 2020) of training, validation, and test sets on each benchmark.
Table 6: The statistics of the datasets.
Dataset
Nodes
Edges
Features
Classes
2,708
5,429
1,433
CiteSeer
3,327
4,732
3.703
6
Pubmed
19,717
44,338
500
3
Counthor CS
18.133
81,894
6,805
15
ogbn-arxiv
169,345
1,166,243
128
40
It is worthwhile to mention that this work focuses on augmenting attributed graphs for node-level learning lasks. DoG generates synthelic node altributes and synthetic edges. DoG consists of a Graph Autoencoder (GAE) that encodes node attributes into latent node foatures. Subsequently, the latent diffusion model within DoG is trained on these latent features. Consequently, node attributes are essential for both the training and generation processes of the DoG model, so that DoG cannot be applied non-attributed graphs.
E.2 Evaluation on Heterophilic Graphs
In this section, study the effectiveness of DoG for semi-supervised node classification four widely used heterophilic graph datasets, namely Texas, Film, Chamelcon, and Squirrel (Pei et al., 2020). We apply DoG to ACM-GCN (Luan et al., 2022), which is a widely used GNN for semi-supervised node classification on heterophilic graphs. Results in Table 7 show that DoG can also largely enhance the performance of GNN for semi-supervised node classification on heterophilic graph datascts. In addition, the results show that the data augmentation with synthetic graph structures alone, which are denoted as DoG w/o low-rank, also brings significant performance improvements over the base model. For example, DoG w/o low-rank
26

---

Published in Transactions on Machine Learning Research (02/2025)
improves the performance of ACM-GCN by 1.4% Squirrel. Combined with low-rank regularization, the improvement. by DoG is further enhanced to 2.0%.
Table 7: Evaluation results of DoG on heterophilic graphs
Methods
Texas
Film
Chameleon
Squirzel
ACM-GCN (Pei et al., 2020)
3.2 96.2 2. (1))
116+11
69.0 L7
58.0
DoG w/o low rank (ACM-GON GCN)
42.8 02881. (+
70.0 1.6 (1 1.0)
1.
DoG (ACM-GCN)
96.6 1.5)
1. ( 166
70.6 14 (1
60.0 (f
E.3 Study on the Quality of the Generated Synthetic Graph Structures
In this section, study the quality of the generated synthetic graph structures by comparing two heuristic metrics on graph characteristics, which are the homophily ratio and the average node degree, between the original graph and generated synthetic graph structures. The homophily ratio, defined as the proportion of edges that connect nodes of the same class among all edges, verifies the structural integrity of synthetic edges in the generated synthetic graph structures compared to the edges in the original graph. The average node degree measures the connectivity pattern of nodes within a graph. By comparing the average node degree of the original graph with that of the synthetic graph structures, we can evaluate how well the connectivity patterns of the original graph are maintained in the synthetic graph structures. The results in Table 8 show that both the average node degree and homophily ratio of the generated synthetic graph structures closely match those of the original graph.
Table 8: The statistics of the datasets.
Homophily Ratio
Average Node Degree
Dataset
Original Graph
Synthetic Graph Structures
Original Graph
Synthetic Graph Structures
Cora
0.81
0.82
4.0
3.8
CiteSeer
0.71
0.75
2.9
2.8
Pubined
0.80
4.5
Coauthor CS
0.80
0.78
8.9
8.6
ogbn-arxiv
0.66
0.66
13.8
13.6
E.4 Training Time and Synthetic Data Generation Time
To study the efficiency of BLND, compare the training time between GAE with BLND and GAE without BLND. In addition, we also compare the time for generation of our DoG and DoG without BLND in its GAE. All evaluations are conducted using a single Nvidia A100 GPU. It is observed from the results in Table 9 that BLND siguificantly reduces the computation cost of the training and synthetic graph structure generation. For instance, the training of GAE without BLND takes over five times the training time of our GAE with BLND on ogbn-arxiv. In addition, BLND also significantly reduces the time for synthetic graph structure generation. For instance, the data generation without BLND takes over four times the data generation time of our DoG with BLND on ogbn-arxiv.
Table Time for the training of GAE and LDM in DoG and data generation with DoG on different datasets.
Training Time (minutes)
Generation Time (s/sample)
Datascts
GAB
GAE without BLND
LDM
DoG
DoG without BLND
Cora
39
0.049
0.066
Citeseer
14
18
41
0.052
0.067
Pubuned
41
129
154
0.067
0.073
Coauthor CS
52
145
179
0.074
0.088
ogbı-arxiv
301
1690
315
0.130
0.426
27

---

Published in Transactions on Machine Learning Research (02/2025)
E.5 Cross- Validation Results
Tuning TosT, and N' by Cross- Validation. The selected values of To.T, and N on each dataset for different models are shown in Table 10. Since we set ly min (N, d and N' = s in Section 5.1, we show the optimal values of y,,, and 3 in Table 10. Since we train different models for 40% of the total number of epochs on 20% of the training data, the cross-validation process does not largely increase the computation overhead for using DoG to augment the training of models for node classification and GCL.
Table 10: Selected rank ratio y and truncated muclear loss's weight À for each dataset.
Methods
Hy Hyperparanelees
Cura
Cileseer
Pulmed
Coauthor CS
ogbu-arxxiv
0.10
0.15
0.20
0.10
0.10
DoG (GCN)
0.2
0.2
0.2
0.2
0.2
3
3
2
0.10
0.10
0.20
0.10
0.15
DoG (EXPHORMER)
7
0.2
0.2
0.2
0.2
2
0.15
0.15
0.20
0.10
0.10
DoG (MVGRL)
0.2
0.2
0.2
0.2
2
2
2
1
0,10
0.10
0.25
0.10
0,10
DoG (GraphMAB)
0.2
0.2
0.2
0.2
0.2
2
3
1
1
0.15
0.10
0.25
0.10
0.05
DoG (GGD)
0.2
0.2
0.2
0.2
0.2
3
2
Table 11: Time for selecting optimal number synthetic nodes N' with cross-validatiin.
Cross-validation Time (minutes)
Datasets
DoG (GCN)
DoG (EXPHORMER)
DoG (MVGRL)
DoG (GraphMAE)
DoG (GGD)
Cora
2.5
10.5
13.5
16.5
1.5
Citesver
2.0
11.4
15.4
18.4
1.4
Pubmed
12.4
39.5
52.5
58.5
10.5
Coauthor CS
14.7
12.5
57.5
63.5
11.5
ogbn-arxiv
37.1
90.5
101.5
117.5
33.5
E.6 Ablation Study on the Synthetic Graph Structures
To evaluate the effectiveness of the synthetic graph structures generated by the DoG in improving the performance GNNs for node classification, we compare the DoG with two categories of ablation models of the DoG, which do not incorporate the synthetic graph structures generated by the DoG. The first category of the ablation models, which is referred DoG to the training set of the original graph without connecting them to the real nodes in the original graph. The second category of ablation models, which is referred to as DoG-KNN, connects the synthetic nodes generated by the DoG to the real nodes in the original graph using the K-Nearest Neighbor (KNN) algorithm on the node attributes. The value of K in the KNN algorithm is set to K E {1, [dovg/4) /4], (davg/21 [dngl, [2x da [4 x davgl}, where daeg is the average node degree of the original real graph. EXPHORMER (Shirzad et al., 2023) employed as the base model for semi-supervised node classification. The results are shown Table 12. It observed that although increasing the number of nodes can boost the performance of the base GNN model, DoG with the connectivity of the new nodes, the synthetic nodes, significantly outperforms the ablation model, DoG-Duplicate, which does not have connectivity of the new nodes. For example, DoG outperforms DoG-Duplicate by 1.4% in the node classification accuracy on the Citesecr datasct. Furthermore, DoG exhibits much better performance than DoG-KNN with different K values. For instance, the best- performing DoG-KNN model with K = daeg improves the classification accuracy of the base model from 72.9% to 73.8% on the Citescer datasot, whereas the DoG model further clevates the classification accuracy 74.8%. In addition, we compare DoG with NODEDUP (Guo et al., 2024), which enlarges the training set by duplicating real nodes with low degrees in the original graph. Following the settings in (Guo et al.,
DoG-Duplicate, only adds the synthetic nodes generated by
28

---

Published in Transactions on Machine Learning Research (02/2025)
2024), only the nodes with degrees not exceeding 2 are duplicated. Edges connecting the low-degree nodes and their own duplicates are created. It is observed that DoG also significantly outperforms NODEDUP. For instance, DoG outperforms NODEDUP by 1.1% in the node classification accuracy on the Citeseer dataset. The ablation study results underline the efficacy of the synthetic graph structures generated by DoG in boosting classification performance.
Table 12: Ablation study on the effectiveness of the synthetic graph structures generated by DoG.
Methods
Cora
Citeseer
Pubmed
CoauthorCS
ogbn-arxiv
EXPHORMER
84.1
72.9
83,2
95.7
72.4
NODEDUP
84.7 (t 0.6)
73.7
(t 0.8)
83.6 (1 0.4)
95.8 (f 0.1)
72.7 (1 0.3)
DoG-Duplicate
84.3 (1 0.2)
73.4
(1 0.5)
83.5 (1 0.3)
96.9 (f 0.2)
72.4
(1 0.0)
DoG-KNN [K 1)
84.8 (1 0.7)
73.7
(1 0.8)
83.6
(1 0.4) 0.4)
96.2 (f 0.5)
72.8 0.4)
DoG-KNN (K- [davg/4 /4]
84.8 (t 0.7)
73.6
0.7)
83.8
(1 0.6)
96.2 (f 0.5)
72.7 0.3)
DoG-KNN [K-
[dug!?2)
84.7 0.6
73.7
0.8)
83.9 (1 0.7)
96.3 0.6)
(1 0.4)
DoG-KNN (K- davyy 1)
84.9 0.8)
73.8
0.9)
83.9 0.77
96.1 (f 0.4)
(1 0.2)
DoG-KNN (K x dany)
0.4)
73.6
0.7)
84.0 (1 0.8)
96.4 96.4 (t7)
T2.6 (1 0.2)
DoG-KN KNN (K- x davg)
84.4 (1 0.3)
73.6
(1 0.7)
83.8 (1 0.6)
96.3 0.6)
72.7 (1 0.3)
DoG (EXPHORMER)
85.7 (T 1.6)
74.8 (T 1.9)
84.6 (1 1.4)
96.9 (1 1.2)
73.4 (1 1.0)
E.7 Performance on Parge-Scale Graph
To evaluate the performance of DoG on large-scale graphs, we conduct an experiment for semi-supervised node classification on AMiner-CS (Feng al., 2020), which consists of more than half million nodes (593,486 nodes) and 6,217,004 edges. We employ DoG to augment the original graph for the training of GRAND+ (Feng et al., 2022). The experiment is performed following the settings in Section 5.1. The results are shown in Table 13. It is observed that DoG significantly improves the performance of GRAND+ by 1.4% on AMiner-CS, demonstrating the scalability of DoG for synthetic graph structure generation on large-scale graphs.
Table 13: Node classification performance on AMiner-CS.
Methods GRAND + DoG (GRAND+)
Accuracy
54.2%
55.6%
29


Reviews:
[{"review_id": "vYwsOpwRcP", "reviewer": "Reviewer_su2i", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points：\n•\tThe authors propose a graph augmentation method by generating synthetic nodes and edges to enlarge the training set and improve the performance of node classification models in the experiment.\n•\tThe authors’ theoretical analysis and experiments prove the effectiveness of the proposed Bi-Level Neighborhood Decoder and Low-Rank regularization.\n\nWeak points：\n•\tAdding a node or an edge can influence many other nodes, so it was once considered difficult to conduct data augmentation by adding nodes to the original graph [1,2]. In this paper, it is still unclear how the proposed method overcomes the challenges in labeling and imputing features and connectivity of new nodes when adding nodes to the original graph.\n•\tSince it has been shown that simply duplicating nodes with low degrees can improve the model performance [3], and the latent space method may have difficulty representing the real global graph structure [4], the improvement of the proposed method may come from the larger number of node features rather than the synthetic graph structure.\n\n[1] Zhao T, Liu Y, Neves L, et al. Data augmentation for graph neural networks[C]//Proceedings of the aaai conference on artificial intelligence. 2021, 35(12): 11015-11023.\n[2] Wang Y, Wang W, Liang Y, et al. Nodeaug: Semi-supervised node classification with data augmentation[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020: 207-217.\n[3] Guo Z, Zhao T, Liu Y, et al. Node duplication improves cold-start link prediction[J]. arXiv preprint arXiv:2402.09711, 2024.\n[4] Vignac C, Krawczuk I, Siraudin A, et al. DiGress: Discrete Denoising diffusion for graph generation[C]//Proceedings of the 11th International Conference on Learning Representations. 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a new node-level graph augmentation method outperforming current methods, by synthesizing new nodes and linking them to the original graph. They use latent diffusion to generate nodes and design a Bi-Level Neighborhood Decoder to reduce the time complexity when generating the adjacency matrix. The authors also add Low-Rank regularization during training to minimize the noise in the synthetic graph.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "•\tThe authors may analyze how the proposed method overcomes the challenges in labeling and imputing features and connectivity of new nodes when adding nodes to the original graph. (strengthen the work)\n•\tThe authors could better justify whether the improvement in the proposed method comes from the increase in the number of nodes or the synthetic graph structures. (strengthen the work)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wWeJjMYNnR", "reviewer": "Reviewer_qCN5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper proposes the first diffusion-based method to augment a given graph.\n\n2. The proposed method obtains consistent performance improvement on different datasets.\n\nWeakness:\n\n1. Most baselines are not new.\n\n2. Some parts are not explained clearly enough, as detailed below in the requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigate the graph generation problem within the context of network data, and aim to augment the original network with synthetic sub-graphs and boost the performance of GNNs. \n\nThe proposed method is based on diffusion, which was explored in the context of whole graph generation but has not been explored for generation of sub-graph structures in networks. Different from whole graph generation that generates one connected graph, the generation process described in this paper will generate multiple sub-structures distributed across different regions of the original graph.\n\nThe proposed model contains a Graph Autoencoder and a Latent Diffusion module. The encoder encodes a given node, as well as the connected edges, into latent space. The diffusion model then generates latent features of the synthetic graph structures. Then the decoder decodes the latent representations back into the data space. To match the generated structure to proper nodes in the graph, a bi-level neighborhood decoder is designed to reconstruct the edges connected to a node hierarchically. By training the model to reconstruct the given graph, the model learns the distribution of the graph, and can be used to generate new structures.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please further clarify the motivation of leveraging latent diffusion for processing the latent representations. \n\n2. One thing is unclear. The generated graph structure is generated based on a given node within the graph. Then it seems that the generated graph should be placed at the position of this node. Why do we have to find a position within the entire graph?\n\n3. When feeding a given node with its edges into the model, which edges are included? Do the authors only consider the edges directly connected to the given node? If this is the case, it seems that the model can only process the information in a very local manner.\n\n4. The high level introduction of the bi-level neighborhood decoder in the Introduction section should be improved. The current version cannot clearly explain how are the generated nodes and edges connected to the original graph.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IN1vsZmEDs", "reviewer": "Reviewer_6C6o", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While graph neural network (GNN) models are briefly mentioned in the Introduction section, they should be more comprehensively mentioned in the Related Work section as a subsection, since there are many recent GNNs that effectively operate on node classification and link generation tasks on both the transductive and inductive settings. The authors should reference the following works in their writing for relevance and recency: \n\n[WWW 2019] Heterogeneous Graph Attention Network. In The World Wide Web Conference (WWW '19). Association for Computing Machinery, New York, NY, USA, 2022–2032. https://doi.org/10.1145/3308558.3313562\n\n[IEEE ICDM 2021] \"Bi-Level Attention Graph Neural Networks,\" in 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021 pp. 1126-1131.\ndoi: 10.1109/ICDM51629.2021.00133\n\nThe authors also need to more clearly motivate why they are considering a graph diffusion model based approach instead other successful methods like GNNs, and graph variational autoencoder approaches and are also used to synthesize graphs. \n\nModel architecture is well described and seems to be technically correct. Complexity analysis is also described in detail, which is helpful for evaluation. Model hyperparameters are provided and the experiment setup is described in sufficient detail. \n\nWhile experiment results achieve good performance against recent baselines, there are some concerns that the authors should help address: It would help if the authors provided experiment dataset statistics like number of nodes, number of edges, type of links,  and also conduct experiments on other graph settings like attributed vs. non-attributed graphs, and a combination of small and large-scale graphs (million node/billion edge graphs).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes Diffusion on Graph (DoG), which generates synthetic graph structures to boost the performance of GNNs. The synthetic graph structures generated by DoG are combined with the original graph to form an augmented graph for the training of node-level learning tasks, such as node classification and graph contrastive learning (GCL). To improve the efficiency of the generation process, a Bi-Level Neighbor Map Decoder (BLND) is introduced in DoG. To mitigate the adverse effect of the noise introduced by the synthetic graph structures, a low-rank regularization method is proposed for the training of graph neural networks (GNNs) on the augmented graphs. Source code of DoG is also released for reproducibility.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above section for requested changes on improving the motivation of the writing, references, and experiments/datasets.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was initially reviewed by three reviewers. The reviewers found the proposed method technically novel and showing good performance against baselines. However, they raised several important concerns on the initial version :
- Lack of recent related work, including recent GNNs for node classification and other discussions on graph data augmentation.  
- Unclear motivation/justification for subgraph generation and adopting latent diffusion model design.  
- Insufficient experimental settings and missing recent baselines in experiments. 

The author rebuttal addressed most of these concerns satisfactorily by incorporating missing references, clarifying the motivation and technical design, and adding more ablation study and comparisons with recent baselines, including larger-scale graphs. As a result, two reviewers responded favorably on the revised draft (1 accept and 1 weak accept). Although the third reviewer did not decide on a final rating, the AE found the author's detailed response sufficiently addressed initial concerns, especially regarding missing recent baselines and lack of clarity. 

Overall, while the empirical study in this work is limited to certain types of graph data, the efficacy of the proposed new augmentation strategy for node-level task learning is validated across a range of benchmarks. Therefore, the AE agrees with the majority of the reviewers and recommends acceptance for a revised version of this submission. The authors should incorporate the requested changes into the final version, including additional experimental comparisons and clarifications provided during the rebuttal.
Decision: Accept (poster)