In machine learning, Mixup is a remarkably effective regularization technique. By taking two data points—such as an image of a cat and an image of a dog—and calculating a simple linear combination of their features and labels, we force a model to learn smooth, robust decision boundaries.
But if you try to apply this directly to graphs, you hit a fundamental mathematical wall. Graphs are discrete, irregular structures. They vary in size, and they lack a natural node ordering. If you blindly average the adjacency matrices of a 10-node molecular graph and a 50-node social network graph, the result is structural nonsense. Even if two graphs have the same number of nodes, node $i$ in the first graph has no inherent correspondence to node $i$ in the second. Without resolving this permutation variance and structural irregularity, direct interpolation yields only destructive noise.
To bring the regularizing power of interpolation to graph neural networks (GNNs), recent research has converged on a powerful paradigm: Continuous Graph Interpolation. Instead of mixing discrete, unaligned graphs in the input space, these techniques map graphs into continuous, mathematically well-behaved spaces where linear combinations become meaningful.
Three primary strategies have emerged to achieve this: interpolating within continuous latent spaces, blending continuous generative blueprints (graphons), and establishing geometric or soft alignments in the input space.
Strategy 1: Interpolating in Continuous Latent Spaces
The most direct way to bypass the discrete irregularity of graphs is to "Euclideanize" them. By training an encoder to map non-Euclidean graph structures into fixed-length, continuous vector representations, we can perform standard vector arithmetic—including linear interpolation—before decoding or classifying the result.
Discrete Graph A ───► [ Encoder ] ───► Latent Vector z_A ──┐
├──► Interpolate ──► Mixed Latent z_mix ──► [ Decoder/Classifier ]
Discrete Graph B ───► [ Encoder ] ───► Latent Vector z_B ──┘
For this to work, the latent space must be smoothly structured and permutation-invariant. Robin Winter et al. address this in Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning by introducing an auxiliary "permuter" model that aligns node orderings during training. This creates a continuous, permutation-invariant latent space that allows for smooth transitions between distinct topologies, making it possible to generate valid intermediate graphs.
Similarly, Abdullah Alchihabi et al. propose GDM: Dual Mixup for Graph Classification with Limited Supervision, which maps structural information into a continuous embedding space via an autoencoder. By interpolating within this latent space and decoding the result back into a synthetic adjacency matrix, they generate diverse, topologically consistent training samples that prevent overfitting when labels are scarce.
Recent architectures scale this concept to large-scale models. Daize Dong et al. (and identically framed by Zhangyang Gao) introduce GraphsGPT in A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer. This framework compresses variable-sized graphs into a fixed-length sequence of continuous vectors ("Graph Words"). Because these vectors reside in a continuous Euclidean space, semantic hybridization and structural interpolation can be performed using pure vector mathematics. The authors of The quest for the GRAph Level autoEncoder (GRALE) leverage a similar philosophy, mapping entire graphs into a single fixed-length vector using an Evoformer-based architecture, which enables property-guided editing and structural manipulation along continuous vector trajectories.
Strategy 2: Interpolating Graphons (Generative Blueprints)
Rather than compressing a specific graph instance into a latent vector, a second school of thought shifts the focus from the sample to the distribution. This approach relies on graphons—continuous, infinite-dimensional functions that act as the limit objects of dense graphs. Think of a graphon as a continuous "recipe" or probability template from which finite graphs can be sampled.
Graph Family A ───► Estimate Graphon W_A ──┐
├──► Linear Interpolation ──► Mixed Graphon W_mix ──► Sample New Synthetic Graphs
Graph Family B ───► Estimate Graphon W_B ──┘
The breakthrough application of this concept to data augmentation is introduced by Xiaotian Han et al. in G-Mixup: Graph Data Augmentation for Graph Classification. Instead of trying to align individual, irregular graphs, the authors estimate a master graphon for each graph class. They then linearly interpolate these class-level graphons to create a hybrid generative template. Because graphons are continuous functions defined on a standard domain, they can be averaged directly without any alignment challenges. Finite synthetic graphs sampled from this mixed graphon naturally blend the discriminative subgraphs and motifs of both parent classes, yielding smoother decision boundaries for downstream classifiers.
Building on this foundation, Ali Azizpour et al. argue in From Moments to Models: Graphon Mixture-Aware Mixup and Contrastive Learning that real-world graph datasets are often mixtures of multiple structural families rather than a single distribution. By disentangling these mixtures, they perform interpolation between the estimated generative models of specific graph clusters, ensuring that augmented graphs remain semantically consistent and avoiding the creation of structurally impossible "chimera" graphs. In Scalable Implicit Graphon Learning, the authors scale this paradigm to massive networks by parameterizing graphons as Implicit Neural Representations (INRs), allowing for continuous structural data augmentation across large graph families.
To bypass the heavy computational cost of explicitly reconstructing graphons, Reza Ramezanpour et al. introduce a statistical shortcut in A Few Moments Please: Scalable Graphon Learning via Moment Matching. They demonstrate that one can linearly interpolate the moment vectors (which represent motif densities like triangles and paths) of different graph classes. Reconstructing a synthetic graphon directly from these mixed moments provides a highly scalable way to generate representative training data without ever manipulating raw adjacency matrices.
Strategy 3: Aligned and Geometric Input-Space Interpolation
If interpolation must happen directly within the input space (on the adjacency matrices themselves), researchers must find a way to force structural alignment between the parent graphs.
One approach is to use optimal transport to find a mathematically principled "shortest path" between two topologies. Zhichen Zeng introduces this in Graph Mixup on Approximate Gromov–Wasserstein Geodesics. By calculating geodesics within the Gromov-Wasserstein space, this method ensures that the structural properties of the synthetic graphs evolve linearly between the parent graphs, preserving strict sample-label consistency. Similarly, Hongyi Ling et al. utilize soft alignments in Graph Mixup with Soft Alignments to compute a convex combination of node features and adjacency matrices across irregular structures.
Alternatively, simpler structural padding can suffice. In Interpolating Graph Pair to Regularize Graph Classification, Hongyu Guo et al. pad graphs with dummy nodes to equalize their sizes and then linearly interpolate their aligned node features and adjacency matrices. This produces hybrid graphs with continuous edge weights between 0 and 1, smoothing the input space.
For node-level tasks, Hoyeop Lee proposes iGraphMix: Input Graph Mixup Method for Node Classification, which avoids explicit node alignment by using a stochastic Bernoulli-based masking process to blend the local neighborhood structures of two source nodes based on a mixing coefficient.
Why It Works: The Intuition of Structural Smoothing
The overarching goal of continuous graph interpolation is to regularize deep graph models by filling the "empty space" of the graph manifold. In a standard graph dataset, models only see discrete, isolated points (e.g., specific molecules). GNNs can easily overfit to these sparse points or develop highly jagged decision boundaries.
By interpolating in a continuous space—whether through latent vectors, graphons, or aligned matrices—we construct a continuous spectrum of topological variations, as systematically analyzed by Alexey Tikhonov et al. in Evaluating Graph Generative Models with Graph Kernels: What Structural Characteristics Are Captured?. This continuous smoothing provides immense practical benefits across several challenging domains:
- Class Imbalance: Wei Ju et al. demonstrate in Cluster-guided Contrastive Class-imbalanced Graph Classification that interpolating representations within minor subclasses enriches semantic diversity, preventing performance collapse on minority classes.
- Out-of-Distribution (OOD) Generalization: Junwei He et al. (HGOE) use graphon interpolation to synthesize statistically plausible outliers, helping models map the fuzzy boundary between known data and unknown anomalies. Lu Lin et al. (CODA) similarly show that navigating low-density regions of the graph manifold via diffusion-based interpolation allows models to generalize across varying graph sizes and covariate shifts.
- Sparsity and Under-Reaching: In node-level tasks where labels are sparse, Weigang Lu et al. (NodeMixup) show that interpolating local topologies between labeled and weakly connected nodes forces the GNN to learn more robust neighborhood representations, overcoming the "under-reaching" problem where distant nodes fail to receive label information.
Ultimately, continuous graph interpolation transforms graph data augmentation from a game of random, destructive perturbations (like dropping random edges) into a mathematically principled framework that preserves structural semantics while regularizing models.
Key Foundational Work
Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning (2021) — contributed 1 concept elements to this direction.
Fast Embedding of Sparse Similarity Graphs (2003) — contributed 1 concept elements to this direction.