# Discrete Signal Processing on Graphs: Frequency Analysis

arXiv: https://arxiv.org/abs/1307.0468 · HTML: https://mlsanity.com/paper/1307.0468/

## Key facts

- Cited by 73 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2013.

## Built on by (most cited first, 30 of 73)

- [Benchmarking and Analyzing Point Cloud Classification under Corruptions](https://mlsanity.com/paper/2202.03377/) (2022)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Spectrally Pruned Gaussian Fields with Neural Compensation](https://mlsanity.com/paper/2405.00676/) (2024)
- [An Attentive Inductive Bias for Sequential Recommendation beyond the Self-Attention](https://mlsanity.com/paper/2312.10325/) (2023)
- [Convolutional Learning on Simplicial Complexes](https://mlsanity.com/paper/2301.11163/) (2023)
- [A Survey of Graph-based Deep Learning for Anomaly Detection in Distributed Systems](https://mlsanity.com/paper/2206.04149/) (2022)
- [Simplicial Convolutional Filters](https://mlsanity.com/paper/2201.11720/) (2022)
- [PUFA-GAN: A Frequency-Aware Generative Adversarial Network for 3D Point Cloud Upsampling](https://mlsanity.com/paper/2203.00914/) (2022)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [Finite Impulse Response Filters for Simplicial Complexes](https://mlsanity.com/paper/2103.12587/) (2021)
- [Untrained Graph Neural Networks for Denoising](https://mlsanity.com/paper/2109.11700/) (2021)
- [Wide and Deep Graph Neural Network with Distributed Online Learning](https://mlsanity.com/paper/2107.09203/) (2021)
- [Graph Convolutions Enrich the Self-Attention in Transformers!](https://mlsanity.com/paper/2312.04234/) (2023)
- [Signed Graph Neural Networks: A Frequency Perspective](https://mlsanity.com/paper/2208.07323/) (2022)
- [Unsupervised Learning of Sampling Distributions for Particle Filters](https://mlsanity.com/paper/2302.01174/) (2023)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [Redesigning graph filter-based GNNs to relax the homophily assumption](https://mlsanity.com/paper/2409.08676/) (2024)
- [Node-Variant Graph Filters in Graph Neural Networks](https://mlsanity.com/paper/2106.00089/) (2021)
- [A Computational Framework for Modeling Complex Sensor Network Data Using Graph Signal Processing and Graph Neural Networks in Structural Health Monitoring](https://mlsanity.com/paper/2105.05316/) (2021)
- [Spatiotemporal Analysis Using Riemannian Composition of Diffusion Operators](https://mlsanity.com/paper/2201.08530/) (2022)
- [Robust Graph Representation Learning for Local Corruption Recovery](https://mlsanity.com/paper/2202.04936/) (2022)
- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Attentional Graph Neural Network Is All You Need for Robust Massive Network Localization](https://mlsanity.com/paper/2311.16856/) (2023)
- [Community-based anomaly detection using spectral graph filtering](https://mlsanity.com/paper/2201.09936/) (2022)
- [Graph Signal Processing for Heterogeneous Change Detection Part I: Vertex Domain Filtering](https://mlsanity.com/paper/2208.01881/) (2022)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Topological Schr"odinger Bridge Matching](https://mlsanity.com/paper/2504.04799/) (2025)
- [A Graph Signal Processing Framework for Hallucination Detection in Large Language Models](https://mlsanity.com/paper/2510.19117/) (2025)

## Abstract (arXiv)

Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high-, and band-pass graph filters. In traditional signal processing, there concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.