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

In traditional statistics, calculating the average of a set of vectors or scalars is straightforward. However, graphs—complex objects defined by nodes and edges—do not reside in a Euclidean space, making the definition of a "mean graph" a significant challenge. Standard approaches often rely on the arithmetic mean of adjacency or Laplacian matrices. While computationally simple, these methods operate locally on individual edges and frequently fail to capture the global topological properties of the graph set, such as community structures or connectivity patterns. Alternatively, the harmonic mean can introduce spurious edges that distort the underlying geometry of the data.

This paper addresses these limitations by proposing a framework to find a "Fréchet mean"—a point that minimizes the sum of squared distances to all samples—within a mathematically sound manifold tailored for graph objects.

The Bures-Wasserstein Framework

The core of the proposed method lies in bridging graph theory with optimal transport theory through a specific embedding:

  1. Graph Signal Embedding: Each graph is represented by its Laplacian matrix ($L$). The graph is viewed as a distribution of "smooth" signals (values on nodes that vary slowly across edges), modeled as a zero-mean Gaussian distribution $\mathcal{N}(0, L^\dagger)$, where $L^\dagger$ is the Moore-Penrose pseudo-inverse.
  2. Distance Metric: The similarity between two graphs is quantified using the Wasserstein-2 distance between their corresponding Gaussian distributions. For zero-mean Gaussians, this simplifies to the Bures-Wasserstein distance.
  3. The Bures-Wasserstein Mean: The mean graph is defined as the one whose Laplacian corresponds to the barycenter (center of mass) of these distributions in the Wasserstein space.
Visual comparison of graph means on synthetic data, demonstrating the structural preservation of the Bures-Wasserstein mean (labeled "Ours") compared to traditional arithmetic, harmonic, and geometric baselines.

To compute this mean, the authors provide a fixed-point iterative algorithm. A notable extension is the introduction of Filtered Graph Means, which allows for the application of low-pass or high-pass filters to emphasize specific structural features (global vs. local) during the averaging process. Furthermore, unlike many existing methods, this framework naturally accommodates signed graphs, which is essential for applications like neuroscience where negative edge weights represent inhibitory connections.

Experimental Evaluation

The framework was rigorously tested across synthetic and real-world datasets to evaluate its ability to preserve structural information and improve downstream tasks.

Structural Preservation and Clustering

In experiments using Synthetic Stochastic Block Models (SBM), the Bures-Wasserstein (BW) mean demonstrated superior preservation of modularity and community strength compared to baselines. When utilized as a centroid in K-means clustering, the BW mean significantly improved clustering accuracy, measured by Normalized Mutual Information (NMI).

Normalized Mutual Information (NMI) for k-means clustering across varying cluster counts and connectivity levels, showing the performance of the Bures-Wasserstein metric against traditional averaging methods.

Functional Brain Networks

The method was applied to EEG-based brain activity measurements from 109 subjects. The task was to classify brain states during motor execution and imagery. The BW mean achieved a misclassification rate of approximately 12-13%, nearly doubling the performance of the arithmetic mean, which hovered around 24-25%.

Multi-layer Node Classification

On the Wikipedia dataset—a highly heterogeneous multi-layer graph—the BW mean outperformed "power means" in node classification tasks. This suggests that the BW mean is robust even when the underlying graph layers represent highly diverse feature sets.

Discussion and Future Directions

While the Bures-Wasserstein framework offers a powerful tool for graph averaging, it currently requires "aligned" graphs, meaning nodes must correspond across all samples (e.g., the same sensors in an EEG cap). It cannot yet average graphs of different sizes or those with unknown node correspondences.

Future work aims to extend this theory to "unaligned" graphs using Gromov-Wasserstein theory and to optimize the iterative algorithm, which currently carries an $O(N^3)$ complexity, for use with extremely large-scale networks. Despite these current limitations, the Bures-Wasserstein mean represents a significant step forward in treating graphs as geometric objects rather than simple matrices.

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