SC-MAD: Mixtures of Higher-Order Networks for Data Augmentation

Madeline Navarro, Santiago Segarra

TL;DR

SC-MAD (Simplicial Complex Mixup for Augmenting Data) is a novel framework that brings the power of "mixup" data augmentation to higher-order networks. By mapping discrete simplicial complexes into a continuous latent space of "complexons," the authors can generate synthetic, topologically sound training samples that significantly boost the performance of simplicial neural networks on classification tasks.

What Problem Does This Paper Address?

While standard graphs are great for modeling pairwise relationships (A connects to B), many real-world systems involve multi-way interactions (A, B, and C interact as a group). Simplicial complexes are the mathematical tool used to model these higher-order structures—think of them as graphs that include not just edges, but also triangles, tetrahedra, and so on.

However, training deep learning models on these complexes (like Simplicial Convolutional Networks) is hampered by a lack of labeled data. Data augmentation techniques like Mixup—which creates new training samples by interpolating between existing ones—have revolutionized image and graph processing. But applying Mixup to simplicial complexes is non-trivial because they are irregular, non-Euclidean objects. You can't simply "average" two different network topologies in their discrete form.

Methods

The authors propose a three-step pipeline called SC-MAD:

  1. Complexon Estimation: To move from discrete to continuous, they map simplicial complexes to complexons. A complexon is a limit object that represents a family of simplicial complexes in a continuous space, much like a graphon does for graphs. They adapt a "Sorting-and-Smoothing" (SAS) approach to estimate these complexons from data.
  2. Complexon Mixup: Once in this continuous Euclidean space, they perform interpolation. They explore two flavors:
  3. Linear Mixup: A simple weighted average of two complexons.
  4. Convex Clustering Mixup: A more sophisticated, data-driven approach that solves an optimization problem to fuse multiple samples, better preserving discriminative class features.
  5. Simplicial Complex Sampling: Finally, they sample new, discrete simplicial complexes from the mixed complexon. This ensures the resulting synthetic data obeys the rules of simplicial complexes (e.g., if a triangle exists, its edges must also exist).
A visualization of the "clusterpath" showing how complexons from two different shapes (circle and figure-eight) fuse as the mixup parameter λ increases.

Datasets

The authors evaluated SC-MAD on two types of data:

  • Synthetic Vietoris-Rips Complexes: Generated from points sampled from two distinct 2D shapes: a circle and a figure-eight.
  • MNIST Superpixel Complexes: The classic handwritten digit dataset was transformed into higher-order networks. Each image becomes a graph of "superpixels," and triangles are added to represent cliques of three adjacent regions, capturing richer visual information than a standard graph.

Key Insights and Ideas

  • The Continuous Bridge: The "aha moment" is using complexons as a bridge. By moving to a continuous limit space, the authors turn a combinatorial topology problem into a standard interpolation problem.
  • Structural Interpolation: Unlike simple pixel averaging, SC-MAD interpolates the connectivity and topology. As shown in the MNIST example below, the mixed complex (c) isn't just a blurry overlay; it's a new network structure that blends the structural characteristics of a '0' and a '3'.
  • Theoretical Guarantee: The authors prove that their mixup method preserves "homomorphism densities"—essentially ensuring that the synthetic samples contain the same fundamental building blocks (sub-complexes) as the original classes.
Simplicial complex representations of MNIST digits: (b) a '0', (d) a '3', and (c) a synthetic mixture sampled from a complexon interpolated between the two.

Key Results

SC-MAD consistently improved classification accuracy across all tests:

  • Vietoris-Rips: Accuracy rose from 0.631 (no augmentation) to 0.738 using convex clustering mixup for both data and labels.
  • MNIST: Accuracy improved from 0.782 to 0.856.
  • Convex Clustering vs. Linear: The data-driven convex clustering approach generally outperformed standard linear mixup, suggesting that multi-sample fusion is more effective for capturing the nuances of higher-order data.

Limitations and Future Work

The current work focuses on dense simplicial complexes, as complexons are limit objects specifically designed for dense sequences. Extending this to sparse networks remains an open challenge. Additionally, while the authors explored several label-mixing strategies (Linear, Sigmoid, Logit), they note that finding the optimal way to pair mixed data with mixed labels is a promising direction for future research. Finally, applying this framework to other domains like social network analysis or protein interaction networks could yield significant benefits.

Summary updated

Abstract

The myriad complex systems with multiway interactions motivate the extension of graph-based pairwise connections to higher-order relations. In particular, the simplicial complex has inspired generalizations of graph neural networks (GNNs) to simplicial complex-based models. Learning on such systems requires large amounts of data, which can be expensive or impossible to obtain. We propose data augmentation of simplicial complexes through both linear and nonlinear mixup mechanisms that return mixtures of existing labeled samples. In addition to traditional pairwise mixup, we present a convex clustering mixup approach for a data-driven relationship among several simplicial complexes. We theoretically demonstrate that the resultant synthetic simplicial complexes interpolate among existing data with respect to homomorphism densities. Our method is demonstrated on both synthetic and real-world datasets for simplicial complex classification.
BibTeX
@inproceedings{navarro2024sc,
  author = {Madeline Navarro and Santiago Segarra},
  title = {{SC-MAD: Mixtures of Higher-Order Networks for Data Augmentation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  doi = {10.1109/icassp48485.2024.10447519},
}
Figure