# A Directed Graph Fourier Transform with Spread Frequency Components

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2018.

## Built on by (most cited first, 6 of 6)

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Causal Fourier Analysis on Directed Acyclic Graphs and Posets](https://mlsanity.com/paper/2209.07970/) (2022)
- [Haar-Laplacian for directed graphs](https://mlsanity.com/paper/2411.15527/) (2024)
- [Statistical Testing on Directed Graphs by Surrogate Data Generation](https://mlsanity.com/paper/2606.00758/) (2026)
- [Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast](https://mlsanity.com/paper/2505.13102/) (2025)
- [Rotation-Parameterized Graph Fractional Fourier Transform: Definition, Properties, and Optimal Filtering](https://mlsanity.com/paper/2511.16111/) (2025)

## Abstract (arXiv)

We study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, to capture low, medium and high frequencies we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain. To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain; and (ii) minimize a smooth spectral dispersion function over the achievable frequency range to obtain the desired spread DGFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are efficiently tackled via a provably convergent, feasible optimization method on the Stiefel manifold. We also propose a heuristic to construct the DGFT basis from Laplacian eigen-vectors of an undirected version of the digraph. We show that the spectral-dispersion minimization problem can be cast as supermodular optimization over the set of candidate frequency components, whose orthonormality can be enforced via a matroid basis constraint. This motivates adopting a scalable greedy algorithm to obtain an approximate solution with quantifiable worst-case spectral dispersion. We illustrate the effectiveness of our DGFT algorithms through numerical tests on synthetic and real-world networks. We also carry out a graph-signal denoising task, whereby the DGFT basis is used to decompose and then low-pass filter temperatures recorded across the United States.