Interpolation Strategies for Graph Data Augmentation

16 concepts16 papers

In computer vision, data augmentation is often as simple as flipping an image or blending two pictures together. This technique, known as "Mixup," creates synthetic training examples by linearly interpolating pixels and labels, forcing models to behave linearly between training samples. However, as noted by Jiajun Zhou et al. in M-Evolve, these geometric transformations fail on graphs.

Graphs are non-Euclidean and irregular. They lack a fixed coordinate system, vary in size, and possess no natural node ordering. If you try to "blend" a molecule with 20 atoms and a social network with 50 users, you immediately face a fundamental obstacle: which node in the first graph corresponds to which node in the second?

The Alignment Challenge

The core difficulty in graph interpolation is the lack of a canonical alignment. In an image, the pixel at $(0,0)$ always corresponds to the top-left corner. In a graph, the first node in an adjacency matrix is arbitrary. Hongyi Ling et al. argue in Graph Mixup with Soft Alignments that determining this correspondence is the primary barrier to effective graph augmentation.

Researchers have proposed several ways to bypass this structural irregularity:

Interpolating in Latent and Generative Spaces

If raw structures cannot be easily aligned, perhaps their underlying representations can. Several recent works shift the interpolation from the discrete graph space to continuous domains.

Xiaotian Han et al. proposed G-Mixup (G-Mixup: Graph Data Augmentation for Graph Classification), which avoids the alignment problem by interpolating "graphons"—non-parametric graph generators. By mixing the generators of different classes rather than the graphs themselves, the authors can sample new synthetic graphs that represent a weighted combination of class properties.

Alternatively, interpolation can happen during the message-passing process. Bo Jiang et al. developed Graph Message Augmentation (GMA) (Unifying Graph Contrastive Learning via Graph Message Augmentation), which performs mixup on the messages passed between nodes. Similarly, Jongwon Jeong et al. introduced iGraphMix (iGraphMix: Input Graph Mixup Method for Node Classification), which interpolates node features and labels while stochastically blending neighborhood structures.

Principled Geometric Paths

A more mathematically rigorous approach involves finding a "path" between two graphs in a metric space. Zhichen Zeng et al. introduced GEOMIX (Graph Mixup on Approximate Gromov–Wasserstein Geodesics), which treats graphs as points in a space governed by the Gromov-Wasserstein (GW) distance. By interpolating along the GW geodesic—the shortest path between two graphs—they generate synthetic samples that maintain strict consistency between the blended structure and the blended label.

In a similar vein, Jaeseung Heo et al. proposed EPIC (EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost), which generates samples along a "graph edit path." By learning the semantic cost of node insertions, deletions, and substitutions, the model can create intermediate graphs that are structurally and semantically plausible.

Why It Works

The success of these methods across unsupervised, semi-supervised, and few-shot tasks suggests that the "graph alignment challenge" is not an insurmountable barrier but a requirement for better inductive biases. As Cheng Yang et al. highlight in their survey (Data-centric Graph Learning: A Survey), shifting focus from model architecture to data-centric strategies like these allows Graph Neural Networks to overcome overfitting and achieve better generalization on limited, irregular data. By finding ways to blend disparate structures, these techniques teach models to recognize the underlying patterns that define a class, regardless of how the specific nodes are ordered or connected.

Key Foundational Work

M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification (2020) — contributed 1 concept elements to this direction.
Corrections to "M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification" (2021) — contributed 1 concept elements to this direction.
Few-Shot Learning on graphs via super-Classes based on Graph spectral Measures (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_alignment_challenge_f30b37ff,
  title = {graph alignment challenge},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-alignment-challenge/rdr_f30b37ffe63c4d2fa221944d5e01977a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_alignment_challenge_f30b37ff_v1,
  title = {graph alignment challenge},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-alignment-challenge/rdr_f30b37ffe63c4d2fa221944d5e01977a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}

See something wrong? Report a mistake