Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications

Anton Savostianov, Michael T. Schaub, Benjamin StammarXiv 2025 · DOI · arXiv

Abstract

Low-pass graph filters are fundamental tools in Graph Signal Processing (GSP), typically requiring the projection of signals onto the subspace spanned by the smallest eigenvalues of the graph Laplacian. However, for dynamic or parametric graphs, recomputing these eigenspaces is computationally expensive. This paper introduces a method to interpolate these subspaces on the Grassmann manifold. By mapping subspaces to a flat tangent space via a logarithmic map, performing linear interpolation, and mapping back via an exponential map, the approach avoids the "eigenvalue bottleneck." We provide theoretical error bounds and demonstrate an order-of-magnitude speedup on synthetic and real-world datasets.

Introduction

In many real-world applications, such as transportation networks or sensor grids, the underlying graph structure is not static but evolves over time or varies with external parameters. Applying standard GSP techniques like denoising or node classification requires low-pass filtering, which depends on the "low-frequency" subspace of the graph Laplacian. For large-scale dynamic graphs, the repeated computation of these subspaces becomes a significant bottleneck. Standard interpolation techniques fail because they do not preserve the orthonormality or validity of the basis matrices.

Methodology

The proposed solution treats subspaces as points on the Grassmann manifold $Gr(n, k)$, the set of all $k$-dimensional subspaces in $\mathbb{R}^n$. The core of the method involves Riemannian interpolation in normal coordinates.

Geometric visualization of Riemannian interpolation on the Grassmann manifold.

As illustrated in Figure 1, the process follows three main steps:

  1. Logarithmic Mapping: Subspaces (represented by Stiefel matrices $V_i$) are mapped from the curved manifold to a flat tangent space $T_{[V_\bullet]} Gr(n, k)$ centered at a base point $[V_\bullet]$. This is achieved using a "Procrustes Logarithm" to ensure basis alignment.
  2. Tangent Space Interpolation: In the flat tangent space, standard interpolation methods like Lagrange or Chebyshev polynomials are applied to the tangent vectors $\Delta_i$.
  3. Exponential Mapping: The interpolated tangent vector $\tilde{\Delta}$ is mapped back to the manifold using the exponential map to obtain the interpolated subspace $\tilde{V}$.
Algorithm for Grassmannian interpolation of graph filters.

The complete procedure is detailed in Algorithm 1 (Figure 2). To handle the filter's dependence on eigenvalues, the authors approximate the spectrum by solving a reduced $k \times k$ eigenvalue problem using the interpolated subspace, further reducing computational overhead.

Experimental Evaluation

The authors establish a rigorous error bound (Theorem 3.1), showing that interpolation error in the tangent space propagates linearly to the manifold. This theoretical stability was validated across several datasets, including the Contextual Stochastic Block Model (CSBM), the KarateClub social network, and an MNIST similarity graph.

Key Results

  • Computational Efficiency: For a system of size $n=600$, the interpolation method was roughly an order of magnitude faster than exact eigenvalue computation while maintaining high accuracy.
  • Error Convergence: The theoretical error bounds were confirmed numerically; the interpolation error decreases exponentially as the number of anchor points increases, following the behavior of Chebyshev interpolation.
  • Improved Accuracy: On the MNIST and KarateClub datasets, searching through the interpolated "Dot Product Graph" family allowed the authors to find graph structures that outperformed the original static graph in node classification tasks.

Conclusion and Future Work

By focusing on subspaces rather than individual eigenvectors—which can be unstable under small perturbations—this Grassmannian approach provides a robust and efficient framework for dynamic GSP. While the current framework assumes a fixed subspace dimension $k$, it offers a scalable path for filtering on evolving networks. Future work includes extending the method to higher-order Laplacians for simplicial complexes and integrating these interpolation layers directly into Graph Neural Networks (GNNs) to handle dynamic spectral filtering more efficiently.

Summary updated

BibTeX
@misc{savostianov2025grassmanian,
  author = {Anton Savostianov and Michael T. Schaub and Benjamin Stamm},
  title = {{Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications}},
  year = {2025},
  eprint = {2510.23235},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.23235},
}
Figure