PaperlayerView exact revision on arXiv

Source-linked AI summary

Discrete Signal Processing on Graphs: Frequency Analysis

Aliaksei Sandryhaila, Jose M. F. Moura

arXiv:1307.0468v2cs.SImath.SP

TL;DR

Graph signals lack the natural frequency ordering available for time and image signals, making low-, high-, and band-pass concepts nontrivial on arbitrary graphs. The paper defines graph total variation to order frequencies, develops corresponding filters and their design, and demonstrates applications to sensor malfunction detection and data classification.

  • Problem

    Arbitrary graph signals lack an obvious frequency ordering with the physical interpretation of oscillation rates available in traditional signal processing.

  • Method

    The paper defines graph total variation, uses it to order graph frequencies, defines graph pass filters, and designs specified responses through least-squares approximations.

  • Results

    The framework is applied to detecting sensor anomalies with high-pass filters and recovering unknown graph-signal values with regularization.

  • Takeaways & Limitations

    The proposed frequency and filter concepts support graph-signal analysis in sensor networks and data classification.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Graph signal processing extends classical DSP to data indexed by arbitrary graphs, where conventional frequency ordering is not directly intuitive. This paper uses graph shifts and total variation to define graph frequencies and filters for applications including sensor analysis and classification.

  • Graph shift framework: The adjacency matrix serves as the graph shift in this framework, producing at each node a weighted combination of neighboring signal values.This contrasts with Laplacian-based approaches, which use the graph Laplacian as their basic building block.
  • Frequency-ordering problem: Unlike time and image signals, graph signals lack an obvious frequency ordering tied to physically interpretable oscillation rates.Traditional low and high frequencies correspond to slower and faster oscillations, respectively.
  • Proposed frequency ordering: The paper orders graph frequencies by how much their spectral components change between neighboring nodes, using a graph total variation function.This extends the classical use of total variation to quantify oscillations in time and image signals.
  • Graph filters: The resulting framework defines low-, high-, and band-pass graph signals and filters, with filter design based on the graph-processing framework.The paper organizes these developments through graph-signal notation, variation measures, frequency ordering, and filter design.
  • Applications: Experiments apply the concepts to sensor-network analysis and classification using graph signals from physical measurements and political-blog labels.The paper also reviews graph DSP foundations and applies regularization to recover unknown signal values.
  • Signal processing on graphs: Graph signal processing analyzes datasets whose elements are connected by relational graphs and treats each dataset as a signal indexed by graph vertices.The graph is represented as G = (V, A), with weighted adjacency relationships between nodes.

C. Graph Fourier Transform

The graph Fourier transform expands graph signals in a basis derived from the adjacency matrix. Its transform coefficients represent frequency content, and the inverse transform reconstructs the original signal from those components.

  • Graph Fourier basis: Graph frequencies are the distinct eigenvalues of the adjacency matrix, while the corresponding Jordan eigenvectors form the graph Fourier basis.The basis vectors are organized through the Jordan decomposition of the adjacency matrix.
  • Transform: The graph Fourier transform expands a graph signal in the adjacency matrix’s Jordan basis using the transform matrix F = V^-1.Here, V contains the Jordan basis vectors.
  • Frequency content: The transform coefficients characterize the frequency content of the graph signal.Each coefficient records the signal’s contribution in the corresponding graph-frequency component.
  • Inverse transform: The inverse graph Fourier transform reconstructs the original signal as a linear combination of frequency components weighted by the transform coefficients.This provides the synthesis counterpart to the graph Fourier expansion.

D. Frequency Response

Graph filtering acts in the graph-Fourier domain through a frequency response, extending the classical convolution theorem to arbitrary graphs. The paper defines graph total variation by comparing a signal with its normalized shifted version, connecting variation to neighboring-node changes.

  • Frequency response: Filtering a graph signal multiplies its graph-Fourier content by the filter’s graph frequency response.This is the graph analogue of the classical convolution theorem.
  • Classical DSP connection: For finite periodic time series, total variation compares each sample with its neighbor on the cycle graph.The periodicity condition produces the cyclic graph representation used for traditional discrete signals.
  • Classical DSP connection: The graph total-variation definition generalizes classical signal variation from lines and regular lattices to arbitrary graphs.Classical variation compares consecutive samples or shifted versions of a signal.
  • Total variation: Graph total variation measures the difference between a signal and its shifted version using the normalized adjacency matrix.Normalization ensures the shifted signal is properly scaled for comparison with the original.
  • Total variation: The graph-signal gradient is defined through the normalized graph shift, and total variation sums the magnitudes of local variations across vertices.This extends the discrete derivative and total-variation concepts from finite time signals to arbitrary graphs.

IV. LOW AND HIGH FREQUENCIES ON GRAPHS

The paper evaluates frequency-component variation using the graph Fourier basis, including generalized eigenvectors of the adjacency matrix. Proper eigenvectors have variation determined by their eigenvalues, while generalized eigenvectors require the extended variation expression.

  • Frequency variation: Frequency ordering is built by evaluating total variation on the graph Fourier basis.Components with smaller or larger variation can then be treated as lower- or higher-frequency components.
  • Generalized eigenvectors: Generalized eigenvectors are handled using the extended variation expression rather than the proper-eigenvector simplification.The graph Fourier basis is represented by Jordan chains of the adjacency matrix.
  • Proper eigenvectors: For a proper adjacency-matrix eigenvector, total variation is determined by its eigenvalue when eigenvectors share the same ℓ1-norm.All proper eigenvectors associated with one eigenvalue have the same total variation.
  • Proper eigenvectors: Normalized proper-eigenvector variation is a real number between 0 and 2.

B. Frequency Ordering

Ordering graph frequencies by increasing total variation yields low-to-high frequency orderings, with distinct behavior for real and complex spectra. Real spectra have a unique ordering, whereas complex spectra can contain tied variations.

  • Frequency ordering: Smaller total variation defines low frequencies, while larger total variation defines high frequencies.The ordering applies the classical DSP convention to graph-Fourier components.
  • Real spectra: For graphs with real spectra, the frequency ordering from lowest to highest is unique.The lowest frequency is λ0 and the highest is λM−1 under the stated eigenvalue ordering.
  • Complex spectra: For complex spectra, frequencies are ordered by distance from |λmax| on the complex plane, so the ordering need not be unique.Distinct eigenvalues on the same circle centered at |λmax| have equal total variation.
  • Finite periodic time series: In finite periodic time series, λm and λN−m have equal variation, producing the conventional order λ0, λ1, λN−1, λ2, λN−2, ….The lowest frequency is λ0 = 1, while the highest is −1 for even N or λ(N±1)/2 for odd N.
  • Finite periodic time series: The proposed ordering for finite periodic time series matches the conventional frequency ordering in classical DSP.

C. Frequency Ordering Based on Quadratic Form

The paper introduces a graph shift quadratic form for ordering graph frequencies and shows that this ordering matches the one induced by total variation.

  • C. Frequency Ordering Based on Quadratic Form: The quadratic form is a positive-semidefinite seminorm that is small when signal values resemble corresponding combinations of neighboring values and large otherwise.This gives the form an interpretation based on local signal variation over the graph.
  • C. Frequency Ordering Based on Quadratic Form: The graph shift quadratic form provides an alternative basis for ordering graph Fourier components from low to high frequencies.The ordering is constructed from the quadratic form evaluated on graph Fourier basis vectors.
  • C. Frequency Ordering Based on Quadratic Form: For real eigenvalues λm < λn, the derived inequality implies S2(vm) > S2(vn), yielding the same lowest-to-highest ordering.The comparison follows from the quadratic-form expression for eigenvectors and the stated eigenvalue condition.
  • C. Frequency Ordering Based on Quadratic Form: The graph shift quadratic-form ordering coincides with the frequency ordering induced by total variation.The equivalence is established by comparing the quadratic form for eigenvectors associated with distinct eigenvalues.

V. FILTER DESIGN

The paper defines graph filter frequency responses in the usual low-, high-, and band-pass terms, then designs polynomial filters by solving interpolation systems. Degree constraints can make exact design impossible, requiring approximation.

  • V. FILTER DESIGN: Low-pass filters attenuate high frequencies, high-pass filters attenuate low frequencies, and band-pass filters retain a specified frequency band.These definitions follow the conventional DSP interpretation of pass and stop behavior.
  • V. FILTER DESIGN: Graph filters alter signal frequency content through their frequency response, which completely specifies the action for diagonalizable adjacency matrices.Filtered Fourier coefficients equal the input coefficients multiplied element-wise by the filter response.
  • V. FILTER DESIGN: Designing a filter to suppress selected frequencies requires setting its response near zero at the corresponding frequencies.The filter polynomial should satisfy h(λm) ≈0 where attenuation is desired.
  • V. FILTER DESIGN: Graph filter construction is a linear inverse-polynomial-interpolation problem with M equations and L + 1 polynomial coefficients.The resulting system uses a full-rank M × (L + 1) Vandermonde matrix.
  • V. FILTER DESIGN: When M ≥ L + 1, the design system is overdetermined and lacks an exact solution, so least-squares approximation can be used.This situation commonly arises when computational efficiency or numerical stability restricts the filter length.
  • V. FILTER DESIGN: For the 150-station weather graph, degree-10 low- and high-pass filters are least-squares approximations to ideal responses.The filters use αm = 1 on the passband and 0 otherwise, with the high-pass assignment reversed.

VI. APPLICATIONS

The applications treat sensor measurements as graph signals whose local irregularities produce high-frequency content. High-pass filtering detects corrupted measurements, while the experiments report strong detection performance.

  • VI. APPLICATIONS: The DSPG framework applies graph filtering and regularization to sensor-network and data-classification problems.The applications extend standard signal-processing techniques to datasets indexed by graphs.
  • VI. APPLICATIONS: Temperature measurements across nearby cities concentrate most signal energy at low frequencies, indicating slow variation over the sensor graph.Nearby cities tend to have similar temperatures in the example dataset.
  • VI. APPLICATIONS: A 20-degree corruption at one station creates a large difference from neighboring measurements and increases high-frequency content.The example compares the true and corrupted Colorado Springs measurement within a sensor-graph subgraph.
  • VI. APPLICATIONS: The detection procedure high-pass filters the corrupted signal and declares malfunction when one or more Fourier coefficients exceed a threshold.The experiment changes one sensor measurement by 20 degrees before filtering and thresholding.
  • VI. APPLICATIONS: 54,750 tests across 365 daily measurements and 150 stations yielded an average detection accuracy of 89%.The reported accuracy corresponds to correctly detecting a corrupted measurement almost 9 times out of 10.
  • VI. APPLICATIONS: High-pass-filtered spectral coefficients distinguish the uncorrupted signal from signals corrupted at five different station locations.The comparison uses coefficients above thresholds as indicators of corruption.

B. Data Classification

The paper formulates partially labeled data classification as graph-signal regularization, using graph similarity to infer unknown labels. Experiments on handwritten digits and political blogs show that total-variation minimization, especially on directed graphs, improves classification accuracy.

  • Classification method: The method represents known two-class labels as a graph signal and predicts unknown labels by finding the signal with the least variation on the graph.Known labels are encoded as +1, −1, or 0 for unknown classes; a parameter controls preservation of known labels.
  • Datasets: Experiments use 2,000 handwritten-digit images and 1,224 political blogs represented by directed graphs.The digit graph connects each image to six nearest neighbors; blog edges represent hyperlink references.
  • Results: For both datasets, total-variation minimization on directed graphs produced the highest classification accuracies.The result indicates that retaining edge direction improves regularization-based classification accuracy.
  • Results: On undirected graphs, the proposed approach significantly outperformed Laplacian-based regularization, with gaps exceeding 10% for image recognition and 20% for blog classification at small known-label ratios.The comparison used the same undirected graphs for both methods.
  • Interpretation: True political-blog labels concentrate more energy in lower frequencies than randomly altered labels, supporting the assumption that correct labels vary smoothly over the graph.The synthetic labels were created by switching 7 of 40 labels in a blog subgraph.
  • Limitation: Blog classification reaches a maximum accuracy of 96% because 50 of 1,224 blogs violate the assumption that most hyperlinks point to blogs of the same type.Those 50 blogs constitute 4% of the dataset and are always misclassified under this assumption.

VII. CONCLUSIONS

The paper concludes that graph total variation provides a frequency ordering for generic graphs and supports low-, high-, and band-pass graph filters. Experiments apply these tools to sensor analysis, regularization, and classification of partially labeled data.

  • Contributions: The paper introduces low-, high-, and band-pass graph signals and filters.These concepts address the lack of simple frequency interpretations for signals on general graphs.
  • Frequency ordering: Graph total variation measures the difference between a graph signal and its shifted version, then orders graph frequencies by that variation.The resulting ordering defines low- and high-pass graph signals and filters.
  • Filter design: The paper designs filters with specified frequency responses by finding least-squares approximations to solutions of linear algebraic systems.
  • Applications: Experiments use temperature measurements from a sensor network and datasets of images and hyperlinked documents.
  • Applications: The reported applications include sensor-malfunction detection, graph-signal regularization, and classification of partially labeled data.

APPENDIX A: JORDAN DECOMPOSITION

The appendix constructs the Jordan decomposition of an arbitrary matrix by organizing eigenvectors and generalized eigenvectors into Jordan chains and blocks. These blocks are concatenated into a Jordan basis and block-diagonal normal form.

  • Eigenstructure: An arbitrary matrix A in C^N×N may have M distinct eigenvalues, each associated with multiple eigenvectors.
  • Jordan chains: Each eigenvector can generate a Jordan chain containing R_m,d generalized eigenvectors.
  • Jordan basis: All eigenvectors and corresponding generalized eigenvectors are linearly independent.
  • Jordan blocks: The appendix forms a Jordan block for each eigenvector and its associated Jordan chain.Each block has dimensions R_m,d × R_m,d.
  • Jordan basis: Concatenating all Jordan-chain matrices produces the matrix V, whose columns form the Jordan basis.
  • Jordan decomposition: The matrix A is represented using the Jordan basis and a block-diagonal Jordan normal form.

APPENDIX B: CONNECTION WITH LAPLACIAN-BASED VARIATION

The appendix compares the proposed graph-shift variation with Laplacian-based variation. Although the quadratic forms differ on general graphs, they induce the same frequency ordering on regular graphs.

  • Laplacian framework: For undirected graphs with real non-negative edge weights, the Laplacian has non-negative eigenvalues and an orthonormal eigenbasis.
  • Laplacian frequency ordering: The Laplacian-based Fourier transform expands graph signals in the eigenbasis of the Laplacian and orders frequencies using Laplacian variation.
  • General graphs: For general graphs, the proposed graph-shift quadratic form and the Laplacian quadratic form are different.
  • Regular graphs: On regular graphs, the two quadratic forms induce the same ordering on the graph Fourier basis.The theorem establishes this equivalence for regular graphs.
  • Regular-graph relation: For a d-regular graph, the Laplacian and adjacency matrix share eigenvectors, with Laplacian eigenvalues β_m = d − λ_m.The smallest Laplacian eigenvalue is β_0 = 0, implying λ_max = d.
  • Regular-graph relation: Because β^2/(2d^2) increases monotonically for β ≥ 0, ordering by the graph-shift quadratic form matches Laplacian frequency ordering on regular graphs.
Loading 1307.0468v2…