Learning the Latent Structure: A Feature-Centric Approach to Graph Data Augmentation

Yu Song; Zhigang Hua; Yan Xie; Bingheng Li; Jingzhe Liu; Bo Long; Jiliang Tang; Hui Liu

cs.LGOct 1, 2026

Learning the Latent Structure: A Feature-Centric Approach to Graph Data Augmentation

Authors: Yu Song, Zhigang Hua, Yan Xie, Bingheng Li, Jingzhe Liu, Bo Long, Jiliang Tang, Hui Liu

Organizations: Michigan State University · Meta

Abstract

Graph-structured data plays a pivotal role in modeling complex relationships. However, real-world graphs are often incomplete due to data collection and observational constraints, severely limiting the effectiveness of modern graph learning pipelines. While existing Graph Data Augmentation (GDA) methods attempt to refine graph structures for improved downstream performance, they are typically label-dependent, computationally expensive, and inherently transductive, limiting their applicability in practical scenarios. In this work, we present a novel feature-centric graph data augmentation framework that bypasses explicit structure modeling by operating directly in the embedding space. Through a self-supervised inverse masking process, our method captures latent ties between observed and complete graphs, enabling recovery of unobserved structural signals through refined node representations. To enhance robustness under noisy and sparse supervision, we introduce a message regularizer and a bootstrap strategy for effective training and generalization. Evaluated on ten graph datasets spanning multiple domains, our approach, SelfAug, consistently outperforms state-of-the-art methods in both accuracy and efficiency across inductive and cold-start settings, highlighting its potential as a scalable and generalizable solution for real-world graph learning scenarios.

Figures & tables

Figure 1: An overview of the proposed framework. Left: the observed graph

G_{\text{obs}}

with missing edges. Right: the complete graph

G_{\text{comp}}

with two inserted edges (red dashed lines). The GNN encoder transforms node features into embeddings that reflect each node’s 1-hop neighborhood. Our augmenter operates in the embedding space by predicting the residual between the observed embeddings

Z_{\text{obs}}

and the complete embeddings

Z_{\text{comp}}

, thereby approximating the effect of a more complete graph structure without explicitly modifying the graph connectivity.

Graph Neural Networks
	Training Data	Cora	Citeseer	Pubmed	DBLP	WikiCS	ogbn- arxiv	Sportsfit	Products	Photo	Computer
GCN	$X_{\text{test}},A_{\text{test}},Y_{\text{test}}$	72.30	65.66	68.41	59.83	58.71	51.95	60.86	39.18	57.78	56.80
GAT	$X_{\text{test}},A_{\text{test}},Y_{\text{test}}$	72.65	65.83	67.75	62.00	60.04	50.60	63.51	36.50	60.09	60.56
APPNP	$X_{\text{test}},A_{\text{test}},Y_{\text{test}}$	72.60	65.23	67.38	61.58	59.51	49.91	61.22	38.66	57.60	58.57
GPRGNN	$X_{\text{test}},A_{\text{test}},Y_{\text{test}}$	73.54	66.21	68.49	62.00	59.33	50.09	62.39	38.51	60.09	62.51
Graph Self-supervised Learning

Table 1: Performance comparison for inductive node classification. Results are reported in terms of classification accuracy (%). Bold numbers indicate the best performance per dataset, and underlined numbers indicate the second-best. OOM denotes out-of-memory errors during training.

Graph Self-supervised Learning
	Training Data	Cora	Citeseer	Pubmed	DBLP	WikiCS	ogbn- arxiv	Sportsfit	Products	Photo	Computer
MLP	$X_{\text{test}},Y_{\text{test}}$	63.70	62.38	68.87	57.17	55.91	47.14	56.31	34.34	51.60	41.47
GraphMAE	$X_{\text{train}},A_{\text{train}}$	68.34	70.64	71.88	65.71	61.73	45.17	61.22	38.03	62.44	58.75
GraphMAE2	$X_{\text{train}},A_{\text{train}}$	71.65	68.12	72.37	67.75	59.91	48.64	57.56	37.36	61.64	51.36
VGAE	$X_{\text{train}},A_{\text{train}}$	69.81	67.40	76.41	63.58	58.89	45.38	62.57	39.47	64.36	58.96
DGI	$X_{\text{train}},A_{\text{train}}$	71.96	65.96	72.16	68.21	55.51	OOM	62.66	37.17	60.36	55.38

Table 2: Performance comparison for cold-start node classification. Results are reported in terms of classification accuracy (%). Bold numbers indicate the best performance per dataset, and underlined numbers indicate the second-best. OOM denotes out-of-memory errors during training.

Panel of Figure 2 — Figure 2: Comparison of embeddings before and after going through the augmentation model, denoted as ‘Encoder’ and ‘Augmenter’, respectively. We report the test accuracy and mutual information between embeddings and labels.

Method	Ave Time (s)	Ave Mem (MB)
GCN	1.46 ‡	15.31 †
GAT	2.05	79.98
GRCN	6.23	78.00
IDGL	6.09	476.50
ProGNN	69.03	78.85
SUBLIME	92.27	133.03

Table 3: Comparison of average runtime till convergence (in seconds) and peak GPU memory usage (in MB) across methods on Cora . † and ‡ denote the best and second-best results, respectively.

Figure 3: Ablation study of Message Regularization (MR) and Bootstrap Augmentation (BA). Experiments conducted under the cold-start setting.

Graph Data Augmentation

See all 9 papers

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization
Jul 8, 2026Adam M. ObermanData Augmentation Graph-Based Semi-Supervised Learning
Department of Mathematics and Statistics, McGill University · Mila, Quebec AI Institute · LawZero
GATTA: Graph Active Learning with Test-Time Augmentation
Aug 15, 2026Zsombor Bánfi, András Gézsi, András FormanekGraph Data Augmentation Active Learning
Department of Artificial Intelligence and Systems Engineering, Budapest University of Technology and Economics, Magyar tudósok krt. 2, Budapest, H-1117, Hungary. · Department of Electrical Engineering (ESAT), STADIUS Center for Dynamical Systems, Signal Processing and Data Analytics, KU Leuven, 3001 Leuven, Belgium.
Graph self-supervised learning based on frequency corruption
Apr 17, 2026Haojie Li, Mengjiao Zhang, Guanfeng Liu +3Graph Neural Networks Graph Representation Learning
School of Data Science, Qingdao University of Science and Technology Qingdao, China · School of Information Science and Technology, Qingdao University of Science and Technology Qingdao, China · School of Computing, Macquarie University Sydney, Australia

Jul 8, 2026J/K move · Enter open · S save

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

Adam M. Oberman

Department of Mathematics and Statistics, McGill University · Mila, Quebec AI Institute · LawZero

Data Augmentation Graph-Based Semi-Supervised Learning Semi-Supervised Learning Statistical Learning Theory

Open paper AskPDF arXiv

Self-supervised learning matches supervised accuracy from a fraction of the labels, but the labeled-sample efficiency behind this has lacked a theoretical explanation. We provide one. Data augmentation induces a similarity graph on the unlabeled data, so downstream learning on that graph is graph-Laplacian-regularized learning. We prove a fast transductive rate,

O(1/n_L)

in the number of labels, in place of the supervised

O(1/\sqrt{n_L})

, by carrying the leave-one-out stability apparatus of Johnson and Zhang (JMLR 2007) over to the augmentation graph, and without the unrealistic assumptions of limit-based analyses (exact kernel, generalizing features). The bound makes augmentation quality explicit: the expected error is at most

C/n_L + R_{\mathrm{DA}}(y)

, where the data-augmentation alignment error

R_{\mathrm{DA}}(y)

is proportional to the graph-cut mass of augmentations that cross a label boundary, so good augmentations let few labels suffice. The analysis uses a streamlined loss that drops the projector, negative-sample, and orthogonality overhead of standard objectives yet still recovers the top-

K

ideal features in the infinite-data limit, the augmentation-kernel eigenspace studied by Zhai et al. The bound gives a mechanistic account of the accuracy-versus-label-count curve through augmentation quality, verified in a controlled model where the constants are known.

Abstract

Graph Data Augmentation

Explore similar work

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

GATTA: Graph Active Learning with Test-Time Augmentation

Graph self-supervised learning based on frequency corruption