Discrete Signal Processing on Graphs

Aliaksei Sandryhaila; Jose M. F. Moura

Source-linked AI summary

Discrete Signal Processing on Graphs

Aliaksei Sandryhaila, Jose M. F. Moura

arXiv:1210.4752v2Oct 17, 2012cs.SIphysics.soc-ph

TL;DR

Graph-indexed datasets lack the regular ordering underlying traditional DSP, motivating a framework that treats data values as signals on arbitrary graphs. The paper extends DSP concepts to these signals and demonstrates the framework in classification, weather-station prediction and compression, and customer-behavior prediction, with reported effectiveness across datasets of different nature.

Problem
Traditional DSP addresses well-ordered time, space, and time-space signals, whereas many datasets consist of data indexed by nodes in social, biological, and physical networks.
Method
The paper proposes DSPG, a linear deterministic framework extending shifts, filters, convolution, transforms, spectral representations, and responses to signals indexed by arbitrary graphs.
Results
The experiments apply DSPG to blog classification, weather-station linear prediction and compression, and mobile-customer behavior prediction, with results described as effective across datasets of different nature.
Takeaways & Limitations
DSPG provides a common signal-processing framework for analyzing and processing data whose similarity or dependency relations are represented by arbitrary graphs.

Abstract

from arXiv · show

In social settings, individuals interact through webs of relationships. Each individual is a node in a complex network (or graph) of interdependencies and generates data, lots of data. We label the data by its source, or formally stated, we index the data by the nodes of the graph. The resulting signals (data indexed by the nodes) are far removed from time or image signals indexed by well ordered time samples or pixels. DSP, discrete signal processing, provides a comprehensive, elegant, and efficient methodology to describe, represent, transform, analyze, process, or synthesize these well ordered time or image signals. This paper extends to signals on graphs DSP and its basic tenets, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, frequency response, and illustrates DSP on graphs by classifying blogs, linear predicting and compressing data from irregularly located weather stations, or predicting behavior of customers of a mobile service provider.

I. INTRODUCTION

The paper develops a linear DSP framework for data indexed by arbitrary graph nodes, extending classical DSP concepts to social, biological, and physical network datasets. It distinguishes this deterministic processing framework from graph-structure analysis and statistical graphical models.

The framework targets rapidly expanding datasets from social, economic, information, biological, infrastructure, and other networked settings.
The framework generalizes and extends algebraic signal processing theory from special line graphs and lattices to signals on arbitrary graphs.
The paper’s goal is to develop a linear DSP framework and tools for datasets arising from social, biological, and physical networks.
DSPG extends shift, filters, convolution, spectral decomposition, Fourier transform, frequency, spectrum, and impulse and frequency responses to graph-indexed data.
Unlike graphical models, DSPG is presented as a deterministic framework for analyzing and processing data indexed by graph nodes.

II. SIGNALS ON GRAPHS

The paper represents relational datasets as weighted graphs and treats data indexed by graph nodes as graph signals. This framework accommodates familiar structures such as time series, spatial lattices, and sensor networks.

Graph representations: Relational data elements can be represented by a graph G = (V, A), where nodes denote elements and A contains weighted connections.Examples include social preferences, coauthorship, and hyperlink relations.
Graph signals: A graph signal maps each node in V to a complex number, so it can be written as an N-element complex-valued vector.The vector notation preserves the fact that each signal value is indexed by a node of the representation graph.
Graph signals: The graph-signal space is identical to C^N, while the indexing of each component retains the relational structure encoded by the graph.Thus, vector representation simplifies discussion without removing node-based indexing.
Examples: A directed cycle represents a finite periodic discrete-time series, with unit-weight directed edges encoding causality and the final-to-first edge encoding periodicity.The cyclic graph extends the sequence structure through its wraparound connection.
Examples: Representation graphs also include two-dimensional rectangular lattices and graphs built from sensor locations under the assumption that nearby sensors have highly correlated temperatures.These examples connect graph representations to spatial and irregularly located measurements.

III. FILTERS ON GRAPHS

The paper defines graph shifts as neighbor-weighted linear operations and develops linear, shift-invariant graph filters as polynomials in the adjacency matrix. It establishes equivalent-filter constructions and algebraic properties governing taps, inverses, and impulse responses.

Graph Shift: Graph shifting replaces each node's signal with a weighted linear combination of signals at its neighbors, extending the classical time shift to arbitrary graphs.The graph itself captures boundary conditions that must be handled explicitly for finite classical signals.
Graph Filters: Linear, shift-invariant graph filters are characterized as polynomials in the graph shift A when the characteristic and minimal polynomials coincide.Such filters have the form H = h(A) = h0 I + h1A + ... + hL A^L, with coefficients called graph filter taps.
Equivalent Filters: When the characteristic and minimal polynomials differ, an equivalent graph and polynomial representation can restore the condition needed for the polynomial characterization.For any matrix A, the paper constructs eA and r(x) such that A = r(eA) and p_eA(x) = m_eA(x).
Filter Representation: Any graph filter has a unique equivalent filter on the same graph with at most NA taps, where NA = deg mA(x).Polynomial division reduces the filter polynomial to a remainder of degree less than NA.
Filter Properties: A graph filter is invertible exactly when its polynomial is nonzero at every distinct eigenvalue of A, and its inverse is another graph filter.The inverse can be constructed through a polynomial rather than by directly inverting the N × N filter matrix.
Impulse Response: Filter taps uniquely determine the impulse response, while the impulse response determines the taps when rank bA = NA.Node relabeling only reorders the impulse response, preserving the filter's response under the corresponding permutation.

IV. ALGEBRAIC MODEL

The algebraic model maps graph filters and signals from matrix-vector form to polynomial and module representations. This graph z-transform preserves filtering through algebraic operations, including multiplication modulo the relevant polynomial.

Algebraic Model: The graph z-transform maps graph filters h(A) to polynomials h(x), forming a polynomial algebra closed under addition and multiplication modulo mA(x).For pA(x) = mA(x), the mapping F → A is an isomorphism of C-algebras.
Graph z-Transform: The graph z-transform generalizes the classical z-transform by representing graph filters and signals as polynomials rather than only matrices and vectors.The representation is defined separately for graph filters and graph signals.
Signal Space: The signal space is an F-module because filtering any signal s by any graph filter h(A) produces another signal in the same space.Theorem 6 states that this signal space is isomorphic to an A-module.
General Case: For non-diagonalizable graphs, the algebraic model uses generalized eigenvectors and polynomial multiplication modulo the characteristic polynomial.The generalized construction follows from replacing the graph by an equivalent graph whose characteristic and minimal polynomials coincide.

V. FOURIER TRANSFORM ON GRAPHS

The graph Fourier transform is constructed from invariant subspaces and generalized eigenvectors of the adjacency matrix, using Jordan decomposition when the matrix is not diagonalizable. In this representation, filtering becomes frequency-domain multiplication, extending classical DSP concepts to arbitrary graphs.

Spectral decomposition: DSPG relates spectral decomposition, signal spectrum, Fourier transform, and frequency response to the Jordan normal form of the adjacency matrix.These concepts are introduced after establishing the structure of graph signal and filter spaces.
Spectral decomposition: A signal decomposes uniquely into invariant subspaces when the subspaces have zero intersections, their dimensions sum to N, and each is irreducible.Each component remains in its invariant subspace under filtering.
Graph Fourier basis: Because graph adjacency matrices may be non-diagonalizable, DSPG uses the Jordan decomposition A = V J V−1 and generalized eigenvector chains to define invariant subspaces.Each subspace generated by a Jordan chain is invariant to graph shifting.
Graph Fourier transform: The generalized eigenvectors form the graph Fourier basis; expanding a signal in this basis defines its graph Fourier transform, while the inverse transform reconstructs the signal from its spectrum.The expansion coefficients are the signal’s spectral coefficients.
Frequency response: Filtering a graph signal is equivalent in the frequency domain to multiplying its spectrum by the filter’s frequency response.The response is represented by h(J), which acts blockwise on invariant subspaces.
Consistency with classical DSP: For diagonalizable adjacency matrices, the frequency response becomes diagonal with entries h(λm), and the inverse graph Fourier transform has the closed form F−1 = V.For periodic time-series graphs, the graph Fourier transform reduces to the classical DFT; the corresponding filtering recovers circular convolution.

VI. APPLICATIONS

DSPG is applied to prediction, compression, classification, and customer-behavior forecasting on graph-indexed data. The applications show how graph structure supports efficient representation and adaptive filtering, while performance depends on graph and filter choices.

Linear Prediction: DSPG extends linear prediction to daily temperature snapshots by modeling 150 geographically located sensors as nodes in a similarity graph.Each sensor connects to K nearest sensors, with edge weights based on normalized inverse squared distances.
Linear Prediction: The graph prediction filter minimizes residual energy, which is quantized and reconstructed through an inverse synthesis filter.For each snapshot, the residual is r = s −h(A)s, and the approximation is reconstructed from the quantized residual.
Linear Prediction: K = 11 and L = 3 produced the lowest LP approximation error, whereas K = 8 and L = 9 produced the highest error.Experiments varied 1 ≤K ≤15 neighbors, 2 ≤L ≤10 filter taps, and 1 ≤B ≤16 residual-quantization bits.
Linear Prediction: Larger graph and filter parameters can increase error, indicating a trade-off between graph connectivity and filter length.Graphs with approximately 3 ≤K ≤7 neighbors performed better with medium-length filters, while larger K and L led to larger errors, possibly from overfitting.
Signal Compression: Graph Fourier representation compresses daily temperature snapshots by retaining a selected number of spectrum coefficients, while its dominant basis vector reflects US temperature distribution.The most frequently energy-capturing basis vector was observed on 217 of 365 days and reflected relative temperature distribution across the United States.
Data Classification and Customer Behavior Prediction: Adaptive graph filters classify blogs and predict mobile-customer behavior, achieving 93% correct classification when labels from 2% of highly hyperlinked blogs are used.Customer prediction used filters with at most L ≤10 taps on a ten-month call log covering approximately 3.5 million customers; accuracy increased with cumulative historical information.

VII. CONCLUSIONS

The paper proposes DSPG for datasets whose similarity or dependency relations are represented by arbitrary graphs, extending core DSP concepts beyond traditional signals. It applies the framework to varied social-science datasets and reports effective results.

DSPG extends shift, filters, signal and filter spaces, spectral decomposition, spectrum, Fourier transform, and frequency response to arbitrary graphs.
The framework treats datasets as signals indexed by graph nodes and generalizes classical time-series DSP through an appropriate graph representation.
The experiments apply DSPG to social-science datasets and report effectiveness across datasets of different nature.The paper also identifies a large mobile-operator Call Detailed Records dataset from one European country as EURMO.

APPENDIX A: MATRIX DECOMPOSITION AND PROPERTIES

The appendix reviews matrix-decomposition properties needed for the paper's treatment of graph signal-processing operators.

The appendix reviews the Jordan normal form and the characteristic and minimal polynomials of a matrix A ∈ C^N×N.
These matrix properties provide the stated background for analyzing the algebraic structure of the paper's operators.
The appendix directs readers to references for a thorough review of these matrix concepts.

Jordan Normal Form

The Jordan normal form organizes a matrix through eigenvalues, eigenvectors, generalized eigenvectors, and associated Jordan blocks.

Each distinct eigenvalue λ_m has D_m linearly independent eigenvectors, with each eigenvector generating a Jordan chain of generalized eigenvectors.
For each eigenvector and its chain, the construction defines a Jordan block whose dimension equals the chain length R_m,d.
Each eigenvalue λ_m is associated with D_m Jordan blocks, one for each independent eigenvector.
The chain matrices V_m,d are concatenated across eigenvalues and eigenvectors into one block matrix.
The resulting block matrix yields the Jordan decomposition of A, with a block-diagonal matrix called A's Jordan normal form.

Minimal and Characteristic Polynomials

The minimal polynomial captures the shortest polynomial annihilating A, while the characteristic polynomial records eigenvalue multiplicities and contains the minimal polynomial as a divisor.

The minimal polynomial m_A(x) is the monic polynomial of smallest degree satisfying m_A(A) = 0_N.
The largest Jordan-chain length R_m for each eigenvalue determines the corresponding factors of the minimal polynomial.
Every polynomial p(x) satisfying p(A) = 0_N is a polynomial multiple of m_A(x), and deg m_A(x) equals the sum of the eigenvalue indices.
The characteristic polynomial is defined by p_A(x) = det(λ I − A) and factors over the distinct eigenvalues.
The algebraic multiplicity A_m sums Jordan-block dimensions, and p_A(x) equals m_A(x) exactly when every eigenvalue has one eigenvector.

APPENDIX B: PROOF OF THEOREM 2

The proof constructs a polynomial that maps specially selected Jordan-block eigenvalues and derivative constraints back to the original Jordan form. Distinct transformed eigenvalues ensure the required interpolation system is uniquely solvable.

Matrix identity: Matrix equality (44) is established by comparing the corresponding expressions in equations (46) and (45).
Jordan-form construction: A polynomial r is chosen so that r(eJ) = J, reducing the construction to value and derivative constraints at transformed eigenvalues.The Jordan blocks of eJ retain the sizes of those in J while using different elements.
Interpolation conditions: The constraints form N linear equations with N unknown polynomial coefficients and have a unique solution through inverse polynomial interpolation.The transformed values eλm,d are selected to be distinct across all Jordan blocks.
Matrix identity: The identity A = r(eA) follows from the Jordan decomposition and the polynomial functional calculus.The proof also uses the fact that the transformed eigenvalues have geometric multiplicity one, yielding equality of the relevant minimal polynomials.

APPENDIX C: PROOF OF THEOREM 4

The proof characterizes when a polynomial inverse of h(A) exists and constructs it by solving interpolation constraints derived from the minimal polynomial. The coefficients are uniquely determined exactly when h does not vanish at any eigenvalue of A.

Inverse-polynomial construction: An inverse polynomial g(x) is constructed so that g(A)h(A) = I_N.This matrix identity supplies the polynomial inverse condition for h(A).
Existence condition: The resulting N_A linear equations have a unique solution if and only if h(λ_m) ≠ 0 for every distinct eigenvalue λ_m of A.The equations use the known values and derivatives of h at the eigenvalues, with R_m determined by the minimal polynomial.
Inverse-polynomial construction: Inverse polynomial coefficients g_0, …, g_{M_A−1} are uniquely determined using inverse polynomial interpolation.The coefficient count matches the interpolation system after incorporating the minimal-polynomial multiplicities.