Yancheng Wang, Ping Li, Dongfang Sun, Yingzhen Yang
原文摘要
Diffusion models represent a powerful class of generative models known for their solid theoretical foundations and remarkable performance across diverse tasks and domains. Existing node level diffusion methods synthesize nodes and edges within a graph, but are not designed to learn a robust generator from adversarially corrupted graphs. In this study, we introduce the Robust Graph Diffusion Model (RGDM), designed to generate labeled synthetic graph structures consisting of nodes and edges that integrate seamlessly into a given graph. The RGDM consists of a Robust Graph Autoencoder (RGAE) and a Latent Diffusion Model (LDM). Leveraging an edge selection mechanism and an innovative low-rank regularization on the latent feature, the RGDM produces clean and high-quality synthetic graph structures, even when trained on graphs subject to adversarial attacks. Comprehensive experimental evaluations reveal that Graph Neural Networks (GNNs) trained on the augmented graph, which is formed by merging the original attacked graph with the synthetic graph structures, exhibit significantly improved robustness against various graph adversarial attacks in the context of semi-supervised node classification. The code of the RGDM is available at https://github.com/Statistical-Deep-Learning/RGDM.
We study nonparametric regression using an over-parameterized two-layer ReLU neural network with fixed covariance-based channel attention, trained by gradient descent with both layers updated simultaneously. The spherical covariates follow an arbitrary fixed non-atomic distribution, and the target function lies in an interpolation space with spectral bias widely studied in the statistical learning literature. We prove that early-stopped training achieves regression risk $\cO(\eps_n^2)$, where $\eps_n$ is the critical population rate of the attention kernel $\Kattn$. Its positive eigenvalues are $λ_j^{s'}$, where $λ_j$ are those of the ReLU feature covariance kernel $K$ and $s'=2s+3$ for $s\ge1$. Under polynomial eigenvalue decay $λ_j\asymp j^{-2α}$ with $α>1/2$, the regression risk bound $\cO(\eps_n^2)$ specializes to the minimax optimal rate $\cO(n^{-2αs'/(2αs'+1)})$. Our analysis is based on two new technical results on the optimization and generalization of the attention network. First, the neural network function after every gradient descent iteration admits a decomposition into a function with bounded Reproducing Kernel Hilbert Space (RKHS) norm and a uniformly small residual. Second, local Rademacher complexity converts this decomposition into a regression risk bound. Kernel gradient descent on the same ball attains the same rate, while our theorem gives explicit sufficient width and auxiliary-sample conditions for simultaneous network training. Our analysis is further extended to covariates supported on $\RR^d$ through a novel normalization method. Under a sub-Gaussian covariate distribution, the attention network achieves a nearly optimal regression risk $\cO((\log n)n^{-s'(d+3)/(s'(d+3)+d)})$ without a density assumption.
We study nonparametric regression using an over-parameterized two-layer neural network trained with algorithmic guarantees in this paper. We consider the setting where the training features are drawn uniformly from the unit sphere in $\RR^d$, and the target function lies in an interpolation space commonly studied in statistical learning theory. We demonstrate that training the neural network with a novel Preconditioned Gradient Descent (PGD) algorithm, equipped with early stopping, achieves a sharp regression rate of $\cO(n^{-\frac{2αs'}{2αs'+1}})$, where $α$ parametrizes the polynomial eigenvalue decay of the regular Neural Tangent Kernel (NTK), $λ_j\asymp j^{-2α}$, and $2α=d/(d-1)$ under the spherical uniform design considered here. The target function is assumed to belong to the interpolation space $\bth{\cH_K}^{s'}$ with $s'\ge3$. This rate is even sharper than the currently known nearly-optimal rate of $\cO(n^{-\frac{2αs'}{2αs'+1}})\log^2(1/δ)$~\citep{Li2024-edr-general-domain}, where $n$ is the size of the training data and $δ\in (0,1)$ is a small probability. Our analysis is based on two key technical contributions. First, we present a principled decomposition of the network output at each PGD step into a function in the reproducing kernel Hilbert space (RKHS) of a newly induced integral kernel, and a residual function with small $L^{\infty}$-norm. Second, leveraging this decomposition, we apply local Rademacher complexity theory to tightly control the complexity of the function class comprising all the neural network functions obtained in the PGD iterates. Our results show how PGD changes the effective kernel in the reference training dynamics, inducing an integral kernel with lower complexity than the regular NTK arising from vanilla GD.