PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.02517v1cs.LG

TL;DR

Real-world graphs are often incomplete, while existing graph data augmentation methods commonly depend on labels, generalize poorly beyond specific graphs, and face efficiency bottlenecks. SelfAug instead augments node embeddings through a self-supervised, feature-centric framework, and the paper reports state-of-the-art accuracy and efficiency across benchmarks, including inductive and cold-start settings.

  • Problem

    Real-world graphs are often incomplete, while existing graph data augmentation methods commonly depend on labels, generalize poorly beyond specific graphs, and face efficiency bottlenecks.

    Source: Introduction · p. 1

  • Method

    SelfAug enhances node embeddings with a self-supervised objective that models differences between masked and observed graphs to compensate for missing structural information.

    Source: General Framework · p. 3, Conclusion · p. 7

  • Results

    Across benchmarks, SelfAug achieves state-of-the-art accuracy and efficiency, with strong performance in inductive and cold-start settings and reduced inference cost versus existing GDA baselines.

    Source: Introduction · p. 2, Conclusion · p. 7

  • Takeaways & Limitations

    The authors identify SelfAug as a potential scalable and generalizable solution for real-world graph learning tasks.

    Source: Conclusion · p. 7

    The evaluation is limited to within-domain settings where training and test graphs share similar structural and feature distributions.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

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.

Introduction

Real-world graphs are often incomplete, while existing augmentation methods can depend on labels, generalize poorly to unseen graphs, and incur high computational costs. SelfAug instead enriches node representations in embedding space through self-supervised learning and is reported to perform strongly in inductive and cold-start settings with reduced inference cost.

  • Incomplete graph structures leave important connections unobserved and can degrade graph learning, including in cold-start settings where relational information may be unavailable.Sparse topologies may inadequately represent the underlying system, and advanced GNNs can deteriorate to MLP-like performance in severely sparse situations.Source: Introduction · p. 1
  • Existing GDA methods often require labels, learn structures transductively for specific graphs, and incur high computational costs that limit practical deployment.Some approaches use resource-intensive optimization, while pairwise node relationship assessment scales quadratically with graph size.Source: Introduction · p. 1
  • SelfAug shifts augmentation from explicit graph-structure modeling to direct enhancement of node representations in embedding space.This feature-centric perspective is intended to simplify augmentation and support a more flexible, generalizable learning paradigm.Source: Introduction · pp. 1–2
  • SelfAug uses self-supervised inverse masking to learn latent ties between observed and underlying structure, reconstructing complete representations without task-specific labels.At test time, it produces enriched node embeddings in a single forward pass without dataset-specific optimization.Source: Introduction · p. 2
  • SelfAug demonstrates strong performance in inductive and cold-start settings, with significantly reduced inference cost compared with existing GDA baselines.Source: Introduction · p. 2

Related Works

Related work covers graph data augmentation methods and graph self-supervised learning, noting limitations in scalability and generalization for prior approaches. SelfAug is distinguished by its augmentation-focused design and emphasis on generalization.

Graph Data Augmentation

  • Graph structure learning jointly optimizes graph structure and a task-specific solver, while test-time adaptation modifies graphs for pretrained GNNs; both can rely on supervision and complex optimization.The cited test-time methods aim to reuse infrastructure without expensive retraining, but the passage says these approaches are often less scalable and poorly suited to unseen graphs.Source: Related Works · p. 2

Graph Self-supervised Learning

  • Graph self-supervised learning addresses label scarcity through graph contrastive learning and generative modeling, typically producing embeddings useful for downstream tasks.Source: Related Works · p. 2
  • Unlike existing graph SSL methods, SelfAug is motivated by data augmentation, uses tailored architectures and objectives to address observed-graph imperfections, and targets improved generalization.Source: Related Works · p. 2

Method

SelfAug learns embedding-space corrections instead of explicitly reconstructing graph structure. Its self-supervised masking objective is supplemented by message regularization and bootstrap target refinement to improve learning under noisy or sparse graph conditions.

Preliminaries

  • SelfAug replaces adjacency reconstruction with parameter-shared node-embedding residuals, reducing structure-learning complexity from O(n^2) to O(n) and enabling inductive reuse.Unlike prior approaches that often require complex optimization and access to the full test graph, the learned augmenter can be applied to graphs from similar distributions without retraining.Source: Preliminaries · pp. 2–3

General Framework

  • Random edge masking trains the augmenter without task labels to restore unmasked-graph embeddings from masked-view embeddings.The reconstruction distance combines cosine distance and mean squared error; training treats the observed graph as a proxy for the ideal structure, assuming it is relatively clean and dense.Source: General Framework · pp. 3–4

Capturing Reliable Relationships

  • A message regularizer encourages similar nodes to share stable neighborhood information, helping the encoder discount noisy or idiosyncratic signals.It is designed to emphasize reliable message representations between sufficiently similar nodes.Source: Capturing Reliable Relationships · p. 4

Bootstrap Augmentation

  • Bootstrap training dynamically refines the target embeddings with augmenter predictions, gradually shifting from the observed-graph target using a linearly increasing schedule.This strategy addresses sparse training graphs by allowing learned structural patterns to improve the initially fixed target.Source: Bootstrap Augmentation · pp. 4–5

Experiments

Experiments evaluate SelfAug on inductive and cold-start graph classification, alongside analyses of embedding quality, efficiency, and module contributions. The reported results show strong performance and generalization, with both proposed components contributing to accuracy.

Experiment Settings

  • The evaluation spans ten benchmarks and disjoint inductive train, validation, and test graphs; SelfAug trains on Gtrain and transfers without retraining or fine-tuning.Cold-start removes validation and test edges; test accuracy is averaged over five random splits.Source: Experiment Settings · p. 5

Performance Comparison

  • SelfAug achieves the highest inductive accuracy across all datasets, beating the runner-up by 5.24% on DBLP and 5.73% on PHOTO without test-graph or label access.The paper also reports that GDA methods perform unstably and struggle to surpass base GNNs.Source: Performance Comparison · pp. 5–6, Table 1 · p. 6

Augmenter Analysis

  • The augmenter consistently improves both test accuracy and normalized mutual information, with MI gains often larger than accuracy gains.MI is computed as NMI between k-means clusters and ground-truth labels; accuracy uses a linear classifier.Source: Figure 2 · p. 6, Augmenter Analysis · p. 6

Performance Comparison

Efficiency Analysis

  • SelfAug achieves the best overall runtime and memory usage, comparable to a simple two-layer GCN.Its inference requires only a forward pass on the test graph and a linear classifier, whereas structure-learning methods require dataset-specific optimization and incur greater computational overhead.Source: Efficiency Analysis · pp. 6–7, Table 3 · p. 7

Ablation Study

  • Removing either Message Regularization or Bootstrap Augmentation lowers accuracy in most cases; removing Message Regularization causes the larger drop.The results indicate complementary contributions, with bootstrap augmentation providing smaller but consistent gains under sparse supervision.Source: Ablation Study · p. 7

Conclusion

SelfAug enhances node embeddings to compensate for missing structural information and achieves state-of-the-art accuracy and efficiency across benchmarks. Its evaluation is limited to within-domain scenarios, motivating future work on cross-domain transfer and adaptive augmentation.

Conclusion

  • SelfAug bypasses explicit structure editing by enhancing node embeddings through a generative, self-supervised objective.It models embedding differences between masked and observed graphs to compensate for missing structural information.Source: Conclusion · p. 7
  • Across multiple benchmarks, SelfAug achieves state-of-the-art performance in accuracy and efficiency for inductive and cold-start settings.The conclusion describes the framework as a scalable and generalizable solution for real-world graph learning tasks.Source: Conclusion · p. 7
  • The evaluation is limited to within-domain scenarios, and future work should explore cross-domain transfer and adaptive augmentation for distribution shifts.Graphs across domains can differ in sparsity, scale, and connection patterns.Source: Conclusion · p. 7
Loading 2610.02517v1…