Bures-Wasserstein Means of Graphs

Isabel Haasler, Pascal Frossard

Abstract

Finding the mean of sampled data is a fundamental task in machine learning and statistics. However, in cases where the data samples are graph objects, defining a mean is an inherently difficult task. We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions, where graph similarity can be measured using the Wasserstein metric. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it. To highlight the potential of our framework as a valuable tool for practical applications in machine learning, it is evaluated on various tasks, including k-means clustering of structured aligned graphs, classification of functional brain networks, and semi-supervised node classification in multi-layer graphs. Our experimental results demonstrate that our approach achieves consistent performance, outperforms existing baseline approaches, and improves the performance of state-of-the-art methods.

Introduction

Averaging a set of data points is a foundational task in statistics, yet defining a mean for graph objects remains a significant challenge. Traditional methods typically average the matrices representing graphs—such as adjacency or Laplacian matrices—using arithmetic, harmonic, or geometric means. However, these approaches suffer from critical limitations. Arithmetic means average edges individually, often failing to capture global structures like communities. Conversely, harmonic and geometric means may better capture global topology but frequently introduce "spurious" edges that were not present in the original sampled data.

Methodology

This paper introduces a framework that bridges Graph Signal Processing and Optimal Transport to define a mathematically rigorous graph mean. The approach involves two primary steps:

  1. Graph Embedding: Rather than averaging matrices directly, each graph is represented by the distribution of "smooth signals" it supports. A smooth graph signal is data on nodes that changes slowly across strongly connected edges. This is modeled as a zero-mean Gaussian distribution parameterized by the pseudo-inverse of the graph's Laplacian matrix.
  2. Bures-Wasserstein Distance: To measure the difference between these signal distributions, the framework utilizes the Wasserstein distance—specifically the Bures-Wasserstein metric, which is the optimal transport distance for Gaussian distributions.

The graph mean is defined as the Fréchet mean (or Wasserstein barycenter) of these signal distributions. The authors prove the existence and uniqueness of this mean and provide a stable iterative algorithm for its computation. Notably, this framework naturally supports signed graphs; a negative edge in the mean graph indicates that nodes consistently exhibit highly dissimilar signals across the input data.

Visual comparison of the proposed Bures-Wasserstein mean ("Ours") against traditional arithmetic, harmonic, and geometric means on synthetic graph data.

Experimental Results

The Bures-Wasserstein mean was evaluated against several benchmarks across synthetic and real-world datasets.

Graph Fusion and Clustering

In synthetic tests involving the fusion of 100 perturbed graphs, the proposed mean successfully captured both local properties (e.g., degree centrality) and global properties (e.g., modularity) without the drawbacks of traditional means. For instance, it reconstructed modularity with an error of just 0.011, matching or exceeding the performance of specialized baselines.

Brain State Classification

The method was applied to the EEG Motor Movement/Imagery Dataset to classify functional brain networks. Centroids computed using the Bures-Wasserstein mean achieved misclassification rates between 12.5% and 13.2%. This significantly outperformed the arithmetic mean (23.7%–25.5%) and the harmonic mean (14.8%–15.3%), demonstrating its utility in capturing physiologically relevant network structures.

Misclassification rates (mean ± std) for EEG motor movement and imagery tasks across different graph mean computation methods.

Multi-layer Node Classification

In semi-supervised node classification tasks on multi-layer networks (e.g., Wikipedia, BBC), the Bures-Wasserstein mean consistently outperformed standard power means. On the Wikipedia dataset with only 5% label availability, it achieved a 49.0% error rate, compared to 59.6% for the arithmetic mean.

Discussion and Conclusion

The Bures-Wasserstein framework provides a powerful tool for graph averaging that respects underlying topology. However, current limitations include the requirement for aligned graphs (pre-defined node correspondences) and a computational complexity of $O(mN^3)$ per iteration. Future work aims to extend this framework to unaligned graphs of varying sizes and to explore its potential in generative modeling for graph populations.

Summary updated

Abstract

Finding the mean of sampled data is a fundamental task in machine learning and statistics. However, in cases where the data samples are graph objects, defining a mean is an inherently difficult task. We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions, where graph similarity can be measured using the Wasserstein metric. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it. To highlight the potential of our framework as a valuable tool for practical applications in machine learning, it is evaluated on various tasks, including k-means clustering of structured aligned graphs, classification of functional brain networks, and semi-supervised node classification in multi-layer graphs. Our experimental results demonstrate that our approach achieves consistent performance, outperforms existing baseline approaches, and improves the performance of state-of-the-art methods.
BibTeX
@inproceedings{haasler2024bures,
  author = {Isabel Haasler and Pascal Frossard},
  title = {{Bures-Wasserstein Means of Graphs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=XNXYoDtWV1},
}
Figure