Graph Structured Data Viewed Through a Fourier LensGraphstructured data appears in many modern applications like social networks, sensor networks, transportation networks and computer graphics. These applications are defined by an underlying graph (e.g. a social graph) with associated nodal attributes (e.g. number of adclicks by an indi vidual). A simple model for such data is that of a graph signal—a function mapping every node to a scalar real value. Our aim is to develop signal processing tools for analysis of such signals de fined over irregular graphstructured domains, analogous to classical Fourier and Wavelet analysis defined for regular structures like discretetime sequences and twodimensional grids. In this work, we start by reviewing the notion of a Graph Fourier Transform (GFT), which has been defined in the literature for graph signals. We examine the spatial and spectral features of circulant graphs, which accommodate linear shiftinvariant operations. We describe fundamental operations such as shifting, sampling, graphreconnection and linear filtering for signals on circulant graphs and derive associated sampling and graphreconnection theorems. We also develop wavelet filter bank structures for multi resolution analysis of largescale graphs. We present a method to decompose an arbitrary graph into a linear combination of circulant graphs. This helps extend fundamental operations such as sampling, filtering and multi resolution filter banks to general graphs. We present an application in the area of graph semisupervised learning where some of the existing algorithms can be viewed as suitably designed filters defined in the GFT domain. We propose a wavelet regularized learning algorithm and evaluate the performance on some realworld datasets. Publications
