# Graph Signal Processing -- Part I: Graphs, Graph Spectra, and Spectral Clustering

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

## Key facts

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

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

- [Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networks](https://mlsanity.com/paper/2212.10822/) (2022)
- [Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials](https://mlsanity.com/paper/2305.19872/) (2023)
- [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)
- [Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity](https://mlsanity.com/paper/2203.08027/) (2022)
- [CF-GO-Net: A Universal Distribution Learner via Characteristic Function Networks with Graph Optimizers](https://mlsanity.com/paper/2409.12610/) (2024)
- [Fair and skill-diverse student group formation via constrained k-way graph partitioning](https://mlsanity.com/paper/2301.09984/) (2023)
- [Edgewise outliers of network indexed signals](https://mlsanity.com/paper/2307.11239/) (2023)
- [Rotation-Parameterized Graph Fractional Fourier Transform: Definition, Properties, and Optimal Filtering](https://mlsanity.com/paper/2511.16111/) (2025)

## Abstract (arXiv)

The area of Data Analytics on graphs promises a paradigm shift as we approach information processing of classes of data, which are typically acquired on irregular but structured domains (social networks, various ad-hoc sensor networks). Yet, despite its long history, current approaches mostly focus on the optimization of graphs themselves, rather than on directly inferring learning strategies, such as detection, estimation, statistical and probabilistic inference, clustering and separation from signals and data acquired on graphs. To fill this void, we first revisit graph topologies from a Data Analytics point of view, and establish a taxonomy of graph networks through a linear algebraic formalism of graph topology (vertices, connections, directivity). This serves as a basis for spectral analysis of graphs, whereby the eigenvalues and eigenvectors of graph Laplacian and adjacency matrices are shown to convey physical meaning related to both graph topology and higher-order graph properties, such as cuts, walks, paths, and neighborhoods. Next, to illustrate estimation strategies performed on graph signals, spectral analysis of graphs is introduced through eigenanalysis of mathematical descriptors of graphs and in a generic way. Finally, a framework for vertex clustering and graph segmentation is established based on graph spectral representation (eigenanalysis) which illustrates the power of graphs in various data association tasks. The supporting examples demonstrate the promise of Graph Data Analytics in modeling structural and functional/semantic inferences. At the same time, Part I serves as a basis for Part II and Part III which deal with theory, methods and applications of processing Data on Graphs and Graph Topology Learning from data.