Graph Filters for Signal Processing and Machine Learning on Graphs

Elvin Isufi, Fernando Gama, David I. Shuman, Santiago Segarra

Abstract

Filters are fundamental in extracting information from data. For time series and image data that reside on Euclidean domains, filters are the crux of many signal processing and machine learning techniques, including convolutional neural networks. Increasingly, modern data also reside on networks and other irregular domains whose structure is better captured by a graph. To process and learn from such data, graph filters account for the structure of the underlying data domain. In this article, we provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power; that is, to model a broader variety of signal classes, data patterns, and relationships. We also showcase the fundamental role of graph filters in signal processing and machine learning applications. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding that promotes collaborations at the intersections of signal processing, machine learning, and application domains.

Introduction

In classical signal processing, data typically resides on structured Euclidean domains like time-series lines or image grids. However, real-world data—from social networks and brain regions to sensor arrays and power grids—often exists on irregular domains better represented by graphs. Graph Filters (GFs) provide the necessary framework to process signals on these irregular structures, bridging the gap between traditional signal processing (SP) and modern machine learning (ML).

Foundations of Graph Filtering

The fundamental building block of graph signal processing is the Graph Shift Operator (GSO). Represented by a matrix such as the Adjacency or Laplacian matrix, the GSO captures the graph's topology. "Shifting" a signal involves moving information from a node to its immediate neighbors, effectively performing a local operation.

Graph Convolutional Filters (GCF)

Building on the GSO, Graph Convolutional Filters are defined as polynomials of the shift operator. These filters are linear, shift-invariant, and local. A filter of order $K$ only requires information from a node's $K$-hop neighborhood, making it highly efficient and scalable with a computational complexity of $O(K|E|)$, where $|E|$ is the number of edges.

Graph convolutional filter as a polynomial of the Graph Shift Operator.

Crucially, these filters exhibit permutation equivariance. Much like standard CNNs are translation invariant, GCFs depend only on the underlying connectivity structure, allowing them to be applied to different graphs with similar local properties.

Spectral Analysis and Filter Design

The behavior of graph filters is often best understood through the Graph Fourier Transform (GFT). In the spectral domain, "low frequencies" correspond to signals that vary smoothly across connected nodes, while "high frequencies" represent rapid changes.

The spectral response of a graph filter defined over the graph eigenvalues.

By defining a filter's frequency response $\tilde{h}(\lambda)$ over the graph's eigenvalues, researchers can design filters for specific tasks like denoising (low-pass) or edge detection (high-pass). This spectral perspective reveals that common techniques like Tikhonov and Sobolev regularization are essentially specific instances of rational graph filters.

From Filters to Graph Neural Networks

A key insight of this framework is the direct link between graph filters and Graph Neural Networks (GNNs). GNNs can be viewed as nonlinear graph filter banks—cascaded layers of graph filters separated by point-wise activation functions. This perspective helps explain phenomena like "oversmoothing," where repeated filtering causes node features to become indistinguishable, and provides a principled way to design more robust neural architectures.

Applications and Future Frontiers

Graph filters are already being applied to diverse datasets, from 3D meshes like the Stanford Bunny to physical sensor networks and abstract brain fMRI data. They enable critical tasks such as semi-supervised learning, community detection, and reaching consensus in distributed robotics.

Despite these strengths, several challenges remain:

  • Dynamic Graphs: Extending filters to networks that change over time (e.g., traffic patterns).
  • Web-Scale Scalability: Processing billions of nodes while maintaining signal integrity.
  • Higher-Order Structures: Moving beyond pairwise edges to model complex group relationships via simplicial complexes or hypergraphs.

By providing a unifying framework, this overview aims to foster collaboration across SP and ML, enabling more effective analysis of the networked data that defines our modern world.

Summary updated

Abstract

Filters are fundamental in extracting information from data. For time series and image data that reside on Euclidean domains, filters are the crux of many signal processing and machine learning techniques, including convolutional neural networks. Increasingly, modern data also reside on networks and other irregular domains whose structure is better captured by a graph. To process and learn from such data, graph filters account for the structure of the underlying data domain. In this article, we provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power; that is, to model a broader variety of signal classes, data patterns, and relationships. We also showcase the fundamental role of graph filters in signal processing and machine learning applications. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding that promotes collaborations at the intersections of signal processing, machine learning, and application domains.
BibTeX
@article{isufi2024graph,
  author = {Elvin Isufi and Fernando Gama and David I. Shuman and Santiago Segarra},
  title = {{Graph Filters for Signal Processing and Machine Learning on Graphs}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  url = {https://openreview.net/forum?id=sN6CmihavQ},
}
Figure