PaperlayerView exact revision on arXiv

Source-linked AI summary

Vertex-Frequency Analysis on Graphs

David I Shuman, Benjamin Ricaud, Pierre Vandergheynst

arXiv:1307.5708v1math.FAcs.ITcs.SI

TL;DR

Signal-processing dictionaries for weighted graphs need to reflect irregular graph geometry, where classical translation and modulation are difficult to define. The paper introduces generalized convolution, translation, and modulation, then uses them to build a windowed graph Fourier transform. The resulting analysis supports vertex-frequency spectrograms, while localization behavior depends on graph structure and eigenvector coherence.

  • Problem

    Designing localized dictionaries and transforms for weighted-graph signals is difficult because irregular graphs lack shift-invariant translation and have discrete, bounded spectra.

  • Method

    The paper defines generalized convolution, translation, and modulation operators and uses them to construct graph-adapted windowed Fourier frames.

  • Results

    The transform enables vertex-frequency analysis, and its spectrogram reveals distinct frequency components in different graph regions.

  • Takeaways & Limitations

    Windowed Fourier analysis can be generalized to signals on undirected, connected, weighted graphs, while graph coherence affects localization behavior.

  • Takeaways & Limitations

    The construction’s classical time-frequency intuition is limited by localized graph Laplacian eigenvectors and by generalized translation operators that do not generally form a mathematical group.

Abstract

from arXiv · show

One of the key challenges in the area of signal processing on graphs is to design dictionaries and transform methods to identify and exploit structure in signals on weighted graphs. To do so, we need to account for the intrinsic geometric structure of the underlying graph data domain. In this paper, we generalize one of the most important signal processing tools - windowed Fourier analysis - to the graph setting. Our approach is to first define generalized convolution, translation, and modulation operators for signals on graphs, and explore related properties such as the localization of translated and modulated graph kernels. We then use these operators to define a windowed graph Fourier transform, enabling vertex-frequency analysis. When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph.

1. Introduction

Signal-processing dictionaries for weighted graphs must reflect the graph’s intrinsic geometry, but irregular graphs lack the shift-invariant translation used by many classical methods. The paper addresses this challenge by generalizing windowed Fourier analysis to graphs.

  • Motivation: Weighted graphs model data in social, electricity, transportation, and sensor networks, as well as similarities and geometric structure in complex domains.
  • Motivation: Dictionaries should be tailored to signal classes and account for the underlying weighted graph geometry.The paper frames dictionary design as a fundamental signal-processing problem.
  • Challenge: Irregular graphs lack a shift-invariant translation, limiting direct use of many classical dictionary-design techniques.This motivates new localized transform methods that account for the data domain.
  • Approach: Windowed Fourier transforms analyze oscillations localized in time or space, motivating their generalization to graph signals.The paper targets applications involving localized signal frequency components.
  • Approach: The paper defines generalized convolution, translation, and modulation operators, then uses them to construct graph-adapted windowed Fourier frames for vertex-frequency analysis.The construction is presented for signals on graphs and includes spectrogram and clustering examples.

2. The Classical Windowed Fourier Transform

The classical windowed Fourier transform combines translation and modulation with a localized window to analyze how signal frequency content varies over time or space. It can also be viewed as Fourier analysis after multiplying the signal by a sliding translated window.

  • Classical operators: Classical translation shifts a signal in time or space, while modulation multiplies it by a complex exponential.
  • Windowed atoms: A windowed Fourier atom is formed from a unit-norm smooth, localized window combined with translation and modulation.Figure 2 illustrates an atom using a Gaussian window with standard deviation 2.
  • Transform: The windowed Fourier transform analyzes a signal through inner products with translated and modulated windowed atoms.
  • Transform: Equivalently, it multiplies the signal by the conjugate of a translated window and Fourier-transforms the resulting localized signal.This interpretation is illustrated by a sliding window applied before Fourier analysis.
  • Transition to graphs: The graph generalization follows the classical construction by extending translation and modulation operators to graph signals.

3. Spectral Graph Theory Notation and Background

Graph Fourier analysis represents signals using eigenvectors of the graph Laplacian, whose eigenvalues provide a frequency-like ordering. Eigenvector localization and basis dependence shape how closely graph analysis follows classical intuition.

  • Graph Fourier basis: For an undirected, connected, weighted graph, the symmetric graph Laplacian has orthonormal eigenvectors with nonnegative ordered eigenvalues.These eigenvectors and eigenvalues define the graph spectral basis and spectrum.
  • Graph Fourier basis: The graph Fourier transform expands a vertex signal in the graph Laplacian eigenbasis, with an inverse transform and Parseval relation.
  • Graph Fourier basis: The graph Fourier basis depends on a potentially nonunique choice of Laplacian eigenvectors, and full eigendecomposition may be impractical for very large graphs.Sparse matrix-vector multiplication methods are preferred in such settings.
  • Frequency intuition: Lower graph Laplacian eigenvalues correspond to smoother eigenvectors, while higher eigenvalues may permit larger differences between neighboring vertex components.
  • Examples: Path-graph Laplacian eigenvectors can be chosen as globally oscillating discrete cosines, while ring-graph eigenvectors can be chosen from the DFT basis.
  • Coherence: Graph coherence measures interaction between vertex deltas and Laplacian eigenvectors; the unweighted ring has minimum coherence 1/√N.The DFT and vertex-delta bases are mutually unbiased in this case.
  • Localization and coherence: Some graphs have highly localized Laplacian eigenvectors, especially with strongly atypical degrees or high clustering, limiting classical time-frequency intuition.The paper gives examples with coherence 0.96 and 0.94 for sensor-network and Swiss-roll graphs.

4. Generalized Convolution and Translation Operators

The paper defines graph-domain convolution and translation through graph spectral operations, then analyzes how translated kernels localize and how translation differs from classical shifts.

  • Generalized convolution: Graph convolution is defined by replacing classical Fourier exponentials with graph Laplacian eigenvectors, making vertex-domain convolution multiplication in the graph spectral domain.The construction also provides an identity element and additional algebraic properties for generalized convolution.
  • Generalized translation: The generalized translation operator shifts a graph window to a chosen vertex by convolving it with a vertex-centered delta.The window is specified spectrally, translated by multiplying each kernel component by χ*ℓ(i), and transformed back to the vertex domain.
  • Generalized translation: Translated normalized heat kernels center around selected vertices, producing the intended graph-domain analogue of shifting a window.Figure 7 illustrates translations centered at vertices 200, 1000, and 2000.
  • Operator properties: Unlike classical translations, graph translations generally do not form a mathematical group, and successive translations lack a clear meaning for arbitrary graphs.The group-like relation holds only in the special shift-invariant graph case.
  • Operator properties: Graph translations are not generally isometric: translated-kernel norms can differ from the original norm and may even become zero.For normalized heat kernels, norms are not too close to zero in the illustrated graphs, whereas a higher-frequency smooth kernel has minimum translated norm 0.013.
  • Localization of translated kernels: Polynomial kernels of degree K are strictly localized within geodesic radius K, while smooth kernels exhibit distance-dependent decay rather than strict compact support.For smooth kernels, localization bounds derive from polynomial approximation; heat-kernel spread can be controlled through the diffusion parameter τ.

5. Generalized Modulation of Signals on Graphs

The paper defines graph modulation through Laplacian eigenfunctions and studies when modulated signals remain localized in the graph spectral domain.

  • Generalized modulation: Generalized modulation M_k is defined by multiplying a signal by the kth Laplacian eigenfunction.For connected graphs, M_0 is the identity.
  • Spectral behavior: Unlike classical modulation, graph modulation does not generally translate every spectral component exactly because graphs are discrete.It exactly maps the DC component to the kth eigenfunction component.
  • Spectral localization: A signal localized near eigenvalue 0 remains localized near eigenvalue λ_k after applying M_k.Figure 10 illustrates this behavior on the Minnesota graph, with λ_2000 = 4.03.
  • Localization bounds: Theorem 2 and Corollary 4 provide quantitative localization bounds for modulated kernels under spectral decay conditions.Theorem 2 is presented as an improved version of an earlier result.
  • Open questions: The paper notes that sharper conditions controlling the spectral spread of M_k f remain an open direction, with an alternative modulation treated in the appendix.The stated spread is centered around the target eigenvalue in the alternative treatment.

6. Windowed Graph Fourier Frames

Using generalized graph translation and modulation, the paper constructs windowed graph Fourier atoms and a transform that analyzes signals jointly by vertex and graph frequency.

  • Transform construction: Generalized translation and modulation operators enable windowed graph Fourier atoms and a corresponding graph Fourier transform.The construction adapts the classical windowed Fourier transform to graph signals.
  • Atom definition: The paper uses atoms g_i,k = M_k T_i g, while noting that the alternative ordering T_i M_k g can be more informative for another modulation definition.The two orderings are harder to relate on graphs than in the classical setting.
  • Vertex-frequency analysis: Each transform coefficient is computed as an inner product between the signal and an atom localized around a vertex and graph frequency.In the sensor-network example, the atom is centered at vertex 27 and frequency λ_11 = 2.49.
  • Alternative interpretation: The transform also equals the graph Fourier transform of the signal after pointwise multiplication by a translated window.This provides an alternative interpretation in the vertex and spectral domains.

6.2. Frame Bounds

The paper establishes sufficient conditions under which windowed graph Fourier atoms form frames and derives corresponding theoretical frame bounds.

  • Coefficient consistency: The alternative interpretation of the transform computes coefficients from a translated window multiplied pointwise with the signal.The example reports the same coefficient value, 0.358, from both computations.
  • Frame existence: If the graph spectral window satisfies ĝ(0) ≠ 0, the collection of windowed graph Fourier atoms forms a frame.Theorem 3 states frame inequalities for every graph signal.
  • Frame bounds: Under a further condition, the atom collection is a tight frame with equal bounds A = B = N∥g∥_2^2.The equality gives identical lower and upper frame bounds.
  • Empirical comparison: The paper compares empirical optimal frame bounds with the theoretical bounds across graphs with N = 500 vertices.The table uses normalized exponential spectral windows and includes random regular, sensor-network, and comet graphs.

6.3. Reconstruction Formula

The reconstruction result states that graph signals can be recovered from their windowed graph Fourier coefficients when the window has nonzero mean.

  • Signal recovery: A non-zero-mean window is sufficient to recover any signal f ∈ R^N from its windowed graph Fourier transform coefficients.The reconstruction formula follows from the frame structure and graph Fourier identities.
  • Normalization: The reconstruction expression omits an additional term when the window is normalized so that ∥g∥_2^2 = 1.This normalization is stated as the reason the term does not appear.

6.4. Spectrogram Examples

The spectrogram reveals frequency components localized to different graph regions, both on a path graph and on an irregular sensor network. Its coefficients can also support signal-adapted clustering that incorporates graph structure and signal content.

  • Path-graph example: On a 180-vertex path graph, the spectrogram displays three discrete cosine frequencies with their corresponding spatial localization.The signal combines χ10, χ60, and χ30 on three consecutive 60-vertex segments.
  • Sensor-network example: On a random sensor network, the spectrogram exposes three different frequency components in three different graph regions.The regions are constructed as red, blue, and green clusters, with χ10, χ27, and χ5 restricted to them, respectively.
  • Frequency-lapse view: Without prior cluster ordering, the spectrogram can be viewed as a sequence of images, one for each graph Laplacian eigenvalue.Scrolling through frequencies shows where corresponding frequency content is concentrated on the graph.
  • Signal-adapted clustering: Windowed graph Fourier coefficients can serve as vertex feature vectors for clustering that accounts for both graph structure and a signal f.The vectors are yi := Sf(i, :) ∈ RN, and standard clustering is applied to the vertex-indexed vectors.
  • Signal-adapted clustering: A signal-adapted clustering example constructs frequency-band signals restricted to graph clusters, then applies transformed coefficients and k-means clustering.The resulting clusters roughly correspond to the regions used to generate the signal.

6.6. Tiling

The graph setting broadly preserves classical vertex-frequency tiling intuition, but graph geometry can substantially change atom resolution. On the Swiss roll, highly localized eigenvectors produce atoms that are localized in both domains beyond classical expectations.

  • Tiling comparisons: Classical windowed Fourier atoms have uniform Heisenberg-box sizes, whereas classical wavelet boxes vary across scales.The comparison is made in the vertex-frequency plane for graph-based constructions and the time-frequency plane classically.
  • Tiling comparisons: On a path graph, windowed graph Fourier atoms have roughly equal Heisenberg-box sizes, while spectral graph wavelets vary across scales.Wavelet box sizes remain similar at a fixed scale but change between scales.
  • Swiss-roll example: On the Swiss roll, three atoms centered at vertex 62 are jointly localized around that vertex and their respective graph frequencies.Their Heisenberg-box sizes nevertheless differ substantially.
  • Swiss-roll example: The atom g62,983 is close to a delta in both domains because eigenvector χ983 is highly localized at vertex 62.The reported graph coherence is μ = 0.94, illustrating why classical localization intuition may fail on some graphs.

6.7. Limitations

The proposed transform has computational and frame-theoretic limitations, and its atoms are not guaranteed to be jointly localized around their nominal vertex and frequency. These deviations arise from graph-specific eigenvector localization.

  • Computational cost: Exact coefficient computation is feasible for smaller graphs, such as graphs with fewer than 10,000 vertices, but may be prohibitive for much larger graphs.The paper motivates approximate methods with better scaling.
  • Computational cost: A fast approximation for translated windows is available through Chebyshev polynomials, but the authors lack a suitable fast approximate graph Fourier transform.Such a transform would be needed to efficiently approximate all windowed graph Fourier coefficients.
  • Frame properties: Windowed graph Fourier atoms need not form a tight frame, so the spectrogram cannot always be interpreted as an energy density function.This may also reduce reconstruction stability and slow some computations.
  • Joint localization: A translated smooth window may be localized around vertex i, yet modulation by an eigenvector can move the resulting atom away from i when that eigenvector is near zero nearby.Figure 19 gives an example of this failure of vertex localization.
  • Joint localization: Multiplication by a graph Laplacian eigenvector can also alter spectral localization, unlike classical modulation by delocalized complex exponentials.Thus, joint localization around a vertex and frequency is not guaranteed.
  • Joint localization: When graph coherence is low, eigenvectors are delocalized and much classical time-frequency intuition carries over; even at high coherence, most atoms may remain jointly localized.Only atoms involving highly localized eigenvectors are typically affected, often at higher frequencies.

7. Conclusion and Future Work

The paper defines graph analogues of translation, modulation, and windowed Fourier analysis for vertex-frequency analysis on weighted graphs. Examples show classical behavior on a path and reveal hidden signal structure on a sensor network, while future work targets sharper localization theory and efficient tight-frame dictionaries.

  • Conclusion: Generalized translation and modulation operators yield a windowed graph Fourier transform for vertex-frequency analysis on undirected, connected, weighted graphs.Smooth spectral windows produce vertex-localized translations, while windows localized near zero support spectral translation through modulation.
  • Conclusion: On a path graph, the resulting spectrogram matches classical discrete-time signal-processing intuition for frequency components varying across vertices.The sensor-network example shows that graph-signal structure hidden in the vertex domain can become visible in the spectrogram.
  • Future work: Future work seeks improved translated-kernel localization results that incorporate graph weights and connect with matrix-function off-diagonal decay.The paper also points to quadrature methods for more precise numerical localization.
  • Future work: The authors are investigating a more computationally efficient dictionary-design method for tight frames jointly localized in vertex and graph spectral domains.This directly addresses limitations of the proposed atom collection.

8. Appendix

The appendix extends generalized graph translation and modulation to normalized Laplacian bases and develops an alternative modulation construction by translating on a graph built from the original spectrum. It also characterizes localization and the tradeoff between vertex- and spectral-domain concentration.

  • 8.1. Generalized Operators with the Normalized Laplacian: Using normalized graph Laplacian eigenvectors preserves the generalized convolution properties and yields corresponding translation and modulation operators.The localization results also continue to hold, with modified constants and an additional degree-dependent factor in the bounds.
  • 8.1. Generalized Operators with the Normalized Laplacian: The normalized-basis modulation operator maps the spectral component at eigenvalue ˜λ0 to the component at eigenvalue ˜λk.Its construction also preserves the identity operator for zero modulation.
  • 8.1.3. Example: Resolution Tradeoff in the Normalized Laplacian Graph Fourier Basis: Theorem 5 provides a condition ensuring that a modulated kernel is concentrated around a desired graph frequency relative to all other frequencies.The appendix combines this result with eigenvalue bounds based on the graph’s isoperimetric dimension to control spectral localization.
  • 8.1.3. Example: Resolution Tradeoff in the Normalized Laplacian Graph Fourier Basis: Increasing the heat-kernel diffusion parameter improves the guarantee for spectral localization around frequency λk but weakens the guarantee for vertex localization around vertex i.Decreasing the parameter produces the opposite tradeoff.
  • 8.2. Alternative Definition of Generalized Modulation: An alternative generalized modulation constructs a weighted graph whose vertices are the original graph’s Laplacian eigenvalues, then defines modulation as generalized translation on that spectral graph.A weighted path graph connects neighboring eigenvalues with weights inversely proportional to their spectral distances, while other weighting schemes are also possible.
  • 8.2. Alternative Definition of Generalized Modulation: The alternative construction supports kernels defined either directly on the original spectrum or on the spectrum of the auxiliary spectral graph.The latter choice facilitates bounds on modulated-kernel spread, including a bound close to the desired form when the auxiliary graph is a weighted path and the original spectrum is nearly uniform.
Loading 1307.5708v1…