PaperlayerView exact revision on arXiv

Source-linked AI summary

G-Mixup: Graph Data Augmentation for Graph Classification

Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Xia Hu

arXiv:2202.07179v2cs.LGcs.AI

TL;DR

Graph Mixup is difficult because graph instances are irregular, unaligned, and non-Euclidean. G-Mixup instead interpolates graphons estimated from different graph classes and samples synthetic graphs, with experiments reporting better GNN performance, generalization, and robustness.

  • Problem

    Mixup is difficult to apply directly to graph data because graphs differ in node count, lack natural node alignment, and have divergent topologies.

  • Method

    G-Mixup estimates a graphon for each graph class, linearly mixes graphons and labels, and generates synthetic graphs from the mixed graphon.

  • Results

    G-Mixup improves GNN performance and generalization across datasets, gaining 12 best performances among 15 reported accuracies and performing 2.84% better than the vanilla model.

  • Takeaways & Limitations

    G-Mixup interpolates the topology of different graph classes and improves robustness to noisy labels and corrupted topology.

  • Takeaways & Limitations

    The approach assumes that graphs within one class share the same generator, or graphon, and theoretical analysis assumes each graph has a discriminative motif.

Abstract

from arXiv · show

This work develops \emph{mixup for graph data}. Mixup has shown superiority in improving the generalization and robustness of neural networks by interpolating features and labels between two random samples. Traditionally, Mixup can work on regular, grid-like, and Euclidean data such as image or tabular data. However, it is challenging to directly adopt Mixup to augment graph data because different graphs typically: 1) have different numbers of nodes; 2) are not readily aligned; and 3) have unique typologies in non-Euclidean space. To this end, we propose $\mathcal{G}$-Mixup to augment graphs for graph classification by interpolating the generator (i.e., graphon) of different classes of graphs. Specifically, we first use graphs within the same class to estimate a graphon. Then, instead of directly manipulating graphs, we interpolate graphons of different classes in the Euclidean space to get mixed graphons, where the synthetic graphs are generated through sampling based on the mixed graphons. Extensive experiments show that $\mathcal{G}$-Mixup substantially improves the generalization and robustness of GNNs.

1. Introduction

Graph Mixup is difficult because graphs are irregular, unaligned, and topologically divergent, while existing augmentation mainly modifies individual graphs. G-Mixup addresses this by interpolating class-level graphons and sampling synthetic graphs, with experiments showing improved GNN performance, generalization, and robustness.

  • Existing graph augmentation typically modifies edges or nodes within individual graphs, leaving between-graph augmentation under-explored.
  • Mixup is challenging for graphs because they usually differ in node count, lack natural node alignment, and have divergent class topologies.
  • G-Mixup estimates one graphon per class, interpolates graphons and labels, and samples synthetic graphs from the mixed graphon.
  • Graphons provide regular, aligned, Euclidean-space generators, enabling graph augmentation without directly matching or interpolating graph instances.
  • G-Mixup theoretically targets mixtures of original graphs and experimentally improves GNN generalization and robustness across datasets and architectures.

2. Preliminaries

The preliminaries define graph representations, homomorphisms, graphons, and graph classification with GNNs. Graphons encode edge probabilities, while GNNs aggregate neighborhood information into graph-level representations for class prediction.

  • 2.1. Notations: A graph consists of nodes V(G) and edges E(G), with v(G) and e(G) denoting their respective counts.
  • 2.2. Graph Homomorphism and Graphons: A graph homomorphism is an adjacency-preserving mapping, and homomorphism density measures the relative frequency of one graph appearing in another.
  • 2.2. Graph Homomorphism and Graphons: A graphon is a continuous, bounded, symmetric function on [0,1]^2 whose values represent edge probabilities between latent node positions.
  • 2.2. Graph Homomorphism and Graphons: Graphons also support motif quantities such as edge and triangle density through integrals of their values.
  • 2.3. Graph Classification with Graph Neural Networks: GNN layers aggregate neighboring node representations and combine them with each node’s previous representation.
  • 2.3. Graph Classification with Graph Neural Networks: A readout function summarizes node representations into a graph representation used to predict probabilities over classes.

3. Methodology

G-Mixup estimates class-level graphons, linearly interpolates graphons from different classes, and samples synthetic graphs from the mixed generator. It uses step-function graphons and generates node features from pooled aligned graphon features.

  • G-Mixup: G-Mixup interpolates graph generators from different graph classes and samples synthetic graphs from the resulting mixed graphon.The mixed graphon serves as the generator for synthetic graphs.
  • Graphon Estimation: Step-function graphons approximate unknown real-world graphons as K × K matrices whose entries represent edge probabilities.Estimation methods align nodes using measurements such as degree before estimating the matrix from adjacency matrices.
  • Graphon Estimation: For binary classification, G-Mixup estimates separate graphons for two labeled graph sets; for multiclass classification, it estimates one graphon per class and randomly selects two for mixing.The mixed graphon is WI = λWG + (1 − λ)WH, with λ controlling the source contributions.
  • Synthetic Graph Generation: Synthetic graph generation samples node positions uniformly, draws Bernoulli edges using the step function, and repeats the process to create multiple graphs.The generated graph has K nodes, and node features are obtained by pooling aligned original features into graphon node features.
  • Synthetic Graph Generation: Synthetic graph node features are constructed from aligned original node features and average-pooled into graphon node features.The node features of generated graphs are the same as the graphon features.
  • Computational Complexity: Graph generation costs O(lK) for nodes and O(lK^2) for edges when generating l graphs with K nodes.Graphon estimation is also a major computation cost, with its complexity summarized in Table 1.

4. Theoretical Justification

The theoretical analysis uses discriminative motifs and homomorphism densities to justify graphon interpolation and graph generation. It shows that mixed graphons preserve source motifs and that sampled synthetic graphs approximately preserve the mixed motif densities with high probability.

  • Discriminative Motifs: A discriminative motif is the minimal-node-and-edge subgraph that determines a graph’s class label.The analysis assumes each graph has a discriminative motif and each graph set has finitely many such motifs.
  • Graphon Mixup: Theorem 4.2 bounds the difference between motif homomorphism densities in a mixed graphon and the corresponding original graphons.The bound depends on λ, motif edge counts, and the cut norm between the source graphons.
  • Graphon Mixup: Because λ controls the motif-density difference under dataset-fixed motif and cut-norm terms, the mixed graphon receives the label λyG + (1 − λ)yH.This construction is intended to preserve discriminative motifs from both source graphons.
  • Synthetic Graphs: Theorem 4.3 states that, with sufficiently many sampled graphs, synthetic motif homomorphism density approximates the mixed graphon’s density with high probability.The relation is expressed as t(FI, G) ≈ t(FI, WI) for any specified nonzero margin ε.
  • Empirical Discussion: Figure 2 reports visibly different estimated graphons across graph classes, supporting the class-level divergence used by G-Mixup.The graphons shown are estimated with the LG method.
  • Empirical Discussion: Figure 3 illustrates that mixing REDDIT-BINARY class graphons can combine one high-degree node with a dense subgraph in synthetic graphs.The caption describes this as a mixture of class-specific structures.

5. Experiments

Experiments evaluate G-Mixup across graphons, synthetic graphs, GNN backbones, pooling methods, corruption settings, generated-graph sizes, and deeper GCNs. Results indicate improved classification, generalization, robustness, and training stability, with average original graph size favored for generation.

  • Graphon visualization: Graphons differ across classes, reflecting distinct community density and high-degree-node structures in IMDB-BINARY and REDDIT-BINARY.These differences support generating mixed graphs by interpolating class graphons.
  • Synthetic graph visualization: Synthetic REDDIT-BINARY graphs combine a dense subgraph with high-degree-node patterns from the source classes.The mixed graphon 0.5 *WG + 0.5 *WH generates this topology mixture.
  • Classification performance: G-Mixup achieves 12 best performances among 15 reported accuracies and performs 2.84% better than the vanilla model overall.Comparisons use the same GNN architectures and training hyperparameters for G-Mixup and baselines.
  • Generalization and stability: G-Mixup improves generalization and stabilizes training, with consistently lower test loss and more stable curves than the vanilla model.The comparisons use training, validation, and test curves across four datasets with GCN.
  • Robustness: G-Mixup improves robustness under both label corruption and topology corruption, with better performance than vanilla baselines in general.These results support its use when graph labels or topology are noisy.
  • Sensitivity analyses: Using the average node number of original graphs is a better choice for the generated-graph node-count hyperparameter K.The impact of generated synthetic graph size is evaluated in Figure 5.
  • Sensitivity analyses: Across GCN depths, G-Mixup improves performance for 2–6 layers on IMDB-BINARY and for 2–9 layers on REDDIT-BINARY.At depths 7–9, performance is comparable to baselines in IMDB-BINARY and much lower than for shallower models.

6. Related Works

Related work covers graph data augmentation and graphon estimation. Existing augmentation commonly perturbs individual graphs, whereas G-Mixup uses multiple input graphs and relies on graphon-based mixing.

  • Graph Data Augmentation: Graph data augmentation methods include node perturbation, edge perturbation, and subgraph sampling.These methods improve graph neural network performance but operate on graph data through established single-graph transformations.
  • Graph Data Augmentation: Existing graph augmentation methods primarily use one graph, while G-Mixup leverages multiple input graphs.This distinguishes G-Mixup from the cited node, edge, and subgraph approaches.
  • Graphon Estimation: Graphon estimation research includes step-function methods based on stochastic block models and low-rank matrix decomposition.Examples include SBA, LG, SAS, MC, and USVT.

7. Conclusion

G-Mixup addresses graph irregularity, misalignment, and non-Euclidean structure by mixing class graphons, which are regular, aligned, and Euclidean. Experiments report better GNN performance and generalization, plus improved robustness to noisy labels and corrupted topology.

  • Conclusion: G-Mixup mixes graphons from different graph classes to generate synthetic graphs instead of directly mixing irregular graph data.Graphs within one class are treated as sharing the same graphon generator.
  • Conclusion: GNNs trained with G-Mixup achieve better performance and generalization and are more robust to noisy labels and corrupted topology.These conclusions are stated within the evaluated graph classification setting.

A. Proof of Theorem

The appendix develops the graphon proof using cut-norm structural similarity, counting-lemma bounds, random-graph concentration, and step-function approximation. These tools establish bounds for mixed graphons and motif preservation.

  • Graphon preliminaries: The cut norm measures structural similarity between graphons.Its definition takes a supremum over measurable subsets S and T.
  • Proof tools: A counting-lemma result bounds motif-density differences by the graphons' cut-norm distance.The bound applies to a simple graph F and graphons W and W′.
  • Motif preservation: A random-graph lemma supplies concentration for motif counts generated from a graphon.The proof applies it to the discriminative motif FI and mixed graphon WI.
  • Mixed graphon bounds: The mixed graphon WI = λWG + (1 −λ)WH is compared separately with WG and WH using cut-norm bounds.These comparisons produce upper bounds used in the theorem proof.
  • Step-function approximation: Every graphon can be approximated in cut norm by a step function, whose values are specified over measurable partition blocks.The weak regularity lemma guarantees such an approximation with K steps.

B. Graphons Estimation Methods

The paper surveys graphon estimation methods and positions G-Mixup as graph-level augmentation that mixes estimated graph generators rather than directly mixing irregular graphs. It also discusses why generated-graph identity collisions are unlikely and distinguishes G-Mixup from node-classification augmentation.

  • Graphons Estimation Methods: Graphon estimators approximate graph generators from observed graphs, with methods including SBA, LG, SAS, MC, and USVT.SBA uses stochastic block models; LG improves SBA; SAS sorts and smooths; MC and USVT use low-rank matrix approximations.
  • Graphons Estimation Methods: Two generated graphs are extremely unlikely to be identical when edge-probability factors are below one and the graph has sufficiently many nodes.The relevant probability is expressed as a product of terms involving Wij and 1−Wij.
  • Graphons Estimation Methods: A generated graph is likewise extremely unlikely to be identical to an original graph under the same large-graph condition.The stated probability uses products of Wij and 1−Wij terms for the generated adjacency pattern.
  • Graphons Estimation Methods: Node-classification augmentation methods are not directly applicable because node classification usually uses one graph, whereas graph classification can manipulate multiple graphs.The related-work discussion contrasts node-level augmentation with G-Mixup’s graph-classification setting.

E. Implementation Details

The implementation estimates class-level graphons and node features, then generates synthetic graphs by interpolating these quantities between graph sets with different labels. A batch variant performs the same process within each training batch.

  • E. Implementation Details: The batch implementation repeats graphon estimation, interpolation, and sampling per batch, producing α·|S| synthetic graphs overall.Each batch contributes α·|S|/B synthetic graphs.

F.1. Experimental Setting

Experiments evaluate G-Mixup across GNN architectures, pooling methods, augmentation baselines, datasets, and corruption settings. The GMT experiment reports improvements over all listed baselines across datasets.

  • F.1. Experimental Setting: The training protocol uses Adam, an initial learning rate of 0.01, halving every 100 epochs, batch size 128, and a 7:1:2 train/validation/test split.Test accuracy is reported over ten runs with the best test epoch selected using validation data.
  • F.1. Experimental Setting: Architectural baselines include GCN, GIN, TopKPool, DiffPool, MincutPool, and GMT.The set covers convolutional, isomorphism-based, and graph-pooling architectures.
  • F.1. Experimental Setting: Augmentation baselines include DropEdge, DropNode, Subgraph, and Manifold-Mixup.These methods respectively modify edges, nodes, sampled subgraphs, or graph-level embeddings.
  • F.1. Experimental Setting: The corruption study uses GCN with 10%, 20%, 30%, and 40% label corruption, while topology corruption randomly adds or removes edges on REDDIT-BINARY.The topology corruption ratios are also 10%, 20%, 30%, and 40%.
  • F.1. Experimental Setting: 1.44%, 1.28%, and 2.01% are G-Mixup’s overall improvements over vanilla, DropEdge, and ManifoldMixup, respectively, with GMT across the reported datasets.The paper states that G-Mixup outperforms all baselines on all datasets in this experiment.

G.3. Experiment on Molecular Property Prediction

The molecular property prediction experiment evaluates G-Mixup on three molecular datasets using official GNN backbones and randomly generated edge attributes for synthetic graphs. Reported improvements include statistically significant comparisons.

  • G.3. Experiment on Molecular Property Prediction: The experiment covers ogbg-molhiv, ogbg-molbace, and ogbg-molbbbp, where graphs represent molecules with atoms as nodes and chemical bonds as edges.The backbones are official reference models: gcn, gcn-vitual, gin, and gin-vitual.
  • G.3. Experiment on Molecular Property Prediction: Synthetic molecular graphs receive randomly generated edge attributes during evaluation.Performance is measured using AUROC and its standard deviation.
  • G.3. Experiment on Molecular Property Prediction: The reported improvements in the molecular experiments are statistically significant at p < 0.05.The paper explicitly states statistical significance for three and four improvements in the reported comparisons.
  • G.3. Experiment on Molecular Property Prediction: The mixup-ratio study varies λ in both graphon and label interpolation on ogbg-molbbbp and ogbg-molbace.The analysis compares the best performance against vanilla GCN using p-values.
Loading 2202.07179v2…