Graph Fourier MMD for Signals on Graphs

Sam Leone, Aarthi Venkat, Guillaume Huguet, Alexander Tong, Guy Wolf, Smita Krishnaswamy

Introduction

In many modern scientific domains, particularly biomedicine, data is rarely distributed in flat Euclidean space. Instead, it often resides on complex structures such as protein-protein interaction networks or cellular state manifolds modeled as graphs. Comparing signals or probability distributions across these structures is a fundamental task, yet traditional metrics often struggle to balance geometric awareness with computational efficiency.

This paper introduces Graph Fourier MMD (GFMMD), a novel distance metric designed specifically for signals on graphs. By leveraging the spectral properties of the graph Laplacian, GFMMD provides a geometry-aware, analytically tractable, and highly scalable alternative to existing methods like Maximum Mean Discrepancy (MMD) and Earth Mover’s Distance (EMD).

The Challenge of Graph-Based Distributions

Standard tools for comparing distributions face significant hurdles when applied to graph-structured data:

  1. MMD typically ignores the underlying connectivity of the graph, treating nodes as independent entities unless a specific kernel is manually engineered.
  2. EMD (Wasserstein distance) is geometrically sensitive but suffers from an $O(n^3)$ computational bottleneck, making it impractical for large-scale datasets like single-cell RNA sequencing (scRNA-seq).

GFMMD addresses these limitations by defining a distance that respects the "smoothness" of the graph while maintaining a computational complexity of $O(n \log n)$.

Methodology: Smoothness and the Graph Laplacian

The core of GFMMD lies in its formulation as an Integral Probability Metric (IPM). To compare two distributions $P$ and $Q$, the method seeks a "witness function" $f$ that maximizes the difference in expectation between the two distributions. Crucially, GFMMD constrains $f$ to be smooth relative to the graph's topology.

The Smoothness Constraint

Smoothness is defined using the Graph Laplacian $L$. The constraint $f^T L f \leq 1$ ensures that the witness function does not change abruptly between nodes that are closely connected. This penalizes "jumps" across the graph, forcing the metric to account for the graph's intrinsic geometry.

Analytical Solution and Feature Maps

One of the paper's primary contributions is the derivation of an analytical solution. For distributions with equal mass on connected components, the authors prove that the distance can be calculated as: $$GFMMD(P, Q) = \|L^{-1/2}(P - Q)\|_2$$ This result transforms a complex optimization problem into a simple Euclidean distance calculation in a transformed feature space. The operator $L^{-1/2}$ acts as a feature map, embedding signals into a space where the graph's geometry is implicitly encoded.

Computational Scalability

Calculating the matrix square root $L^{-1/2}$ is traditionally expensive ($O(n^3)$). To circumvent this, the authors employ Chebyshev polynomial approximations. By approximating the spectral filter, GFMMD can be computed in $O(n \log n)$ time for sparse graphs, representing a massive speedup over exact methods and optimal transport.

Empirical Evaluation

The authors validated GFMMD across synthetic and real-world biological datasets, demonstrating both accuracy and speed.

Synthetic Manifolds and Benchmarks

On a "Swiss Roll" point cloud, GFMMD was tested for its ability to recover ground-truth geodesic distances. It achieved a Spearman correlation of 0.613, significantly outperforming Diffusion EMD (0.584) and Sinkhorn-based EMD (0.250). Furthermore, using Chebyshev approximations (order 8), the computation time for all-pairs distances was reduced from ~139 seconds to just ~0.64 seconds with negligible loss in accuracy.

Single-Cell RNA Sequencing

The method was applied to a dataset of 9,167 CD8+ T cells. By treating each gene's expression as a signal over the cell-cell k-nearest neighbor graph, GFMMD enabled:

  • Gene Localization Scores: A score $s(P) = \|L^{-1/2} P\|_2$ was used to identify genes expressed in specific cellular niches versus "housekeeping" genes expressed globally.
  • Functional Clustering: Using the $L^{-1/2}$ feature map, genes were embedded into a low-dimensional space where they clustered into distinct functional modules (e.g., naive vs. effector T cell signatures), outperforming standard differential expression analysis in identifying trajectory-specific markers.

Key Insights and Limitations

GFMMD provides an intuitive "infinite effort" interpretation: if two distributions reside on disconnected components of a graph, the distance between them is infinite, reflecting the impossibility of moving mass across a gap. Furthermore, it generalizes the concept of "effective resistance" from electrical circuit theory; if $P$ and $Q$ are point masses, their GFMMD relates to the resistance between those nodes.

However, the method is not without limitations:

  • Graph Dependency: The metric's accuracy is strictly tied to how well the graph represents the underlying data manifold. If the graph construction (e.g., KNN) is flawed, the distance will be skewed.
  • Mass Constraints: The requirement for equal mass on connected components makes the metric sensitive to how the graph is partitioned.

Conclusion

Graph Fourier MMD represents a significant step forward in signal processing on graphs. By providing a closed-form solution that is both geometrically grounded and computationally efficient, it opens new avenues for analyzing high-dimensional biological data and other complex networked systems. Future work may explore alternative spectral filters to further refine the metric's sensitivity to multi-scale graph features.

Summary updated

Abstract

While numerous methods have been proposed for computing distances between probability distributions in Euclidean space, relatively little attention has been given to computing such distances for distributions on graphs. However, there has been a marked increase in data that either lies on graph (such as protein interaction networks) or can be modeled as a graph single cell data, particularly in the biomedical sciences. Thus, it becomes important to find ways to compare signals defined on such graphs. Here, we propose Graph Fourier MMD (GFMMD), a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation between the pair of distributions on the graph. We find an analytical solution to this optimization problem as well as an embedding of distributions that results from this method. We also prove several properties of this method including scale invariance and applicability to disconnected graphs. We showcase it on graph benchmark datasets as well on single cell RNA-sequencing data analysis. In the latter, we use the GFMMD-based gene embeddings to find meaningful gene clusters. We also propose a novel type of score for gene selection called gene localization score which helps select genes for cellular state space characterization.
BibTeX
@misc{leone2023graph,
  author = {Sam Leone and Aarthi Venkat and Guillaume Huguet and Alexander Tong and Guy Wolf and Smita Krishnaswamy},
  title = {{Graph Fourier MMD for Signals on Graphs}},
  year = {2023},
  eprint = {2306.02508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.02508},
}
Figure