Graph Linear Canonical Transform: Definition, Vertex-Frequency Analysis and Filter Design

Jian Yi Chen, Yu Zhang, Bing Zhao LiIEEE TSP 2024 · DOI

TL;DR

This paper introduces the Graph Linear Canonical Transform (GLCT), a novel signal processing tool for graph-structured data that offers adjustable "smoothing" capabilities. By extending traditional time-frequency analysis to the graph domain, the GLCT and its associated vertex-frequency analysis methods can better capture local graph signal features, leading to improved performance in tasks like image classification.

What Problem Does This Paper Address?

Graph signal processing (GSP) aims to analyze and process data residing on graphs, which are prevalent in fields like computer vision, social networks, and image processing. A key challenge in GSP is effectively representing and analyzing signals that exhibit local variations and complex structures within the graph. Traditional methods, like the Graph Fourier Transform (GFT), often rely on fixed spectral properties derived from the graph Laplacian, which can limit their ability to adapt to diverse signal characteristics and capture fine-grained local information. Specifically, existing vertex-frequency analysis methods struggle with the "smooth diversity" requirement – the ability to select different smoothing modes to better align with the signal's intrinsic local features.

Methods

The core contribution is the Graph Linear Canonical Transform (GLCT). The GLCT is built upon the Linear Canonical Transform (LCT), a generalized integral transform that encompasses Fourier, fractional Fourier, and Fresnel transforms. The GLCT parameter matrix is decomposed into three fundamental operations:

  1. Graph Fractional Fourier Transform (GFrFT): An extension of the fractional Fourier transform to the graph domain.
  2. Graph Scaling Transform: Adapts the scale of the signal on the graph.
  3. Graph Chirp Modulation (CM): Introduces a chirp-like modulation to the graph signal.

These three components are combined in a specific order to define the GLCT. This decomposition allows for adjustable parameters (σ, ξ, β) that control the "smoothing mode" of the transform, enabling it to better match the local characteristics of graph signals.

Building on the GLCT, the paper develops vertex-frequency analysis methods. These methods aim to localize signals in both the vertex and "linear canonical" frequency domains. Techniques like the Windowed Graph Linear Canonical Transform (WGLCT) and Localized Graph Linear Canonical Transform (LGLCT) are introduced to achieve this localization.

Finally, the paper explores filter design for graph signals. This includes:

  • Optimal Filter Design: Deriving filters that minimize a defined loss function.
  • Filter Learning: Employing stochastic gradient descent (SGD) to learn optimal filter parameters, particularly for image classification tasks.

Datasets

The paper uses the following datasets for demonstration and evaluation:

  • Simulated Graphs: A 128-node sensor network graph and a 256-node Swiss roll graph are used to visualize signal properties and transform results.
  • MNIST Dataset: A standard benchmark dataset for image classification is used to evaluate the performance of the designed filters in a graph-based convolutional neural network context. The authors specifically focus on distinguishing between digits '4' and '9'.

Key Insights and Ideas

  • Tunable Smoothing: The GLCT's key advantage is its ability to adjust its "smoothing" behavior through its parameters (σ, ξ, β). This allows it to adapt to signals with varying local structures, unlike fixed-mode transforms.
  • Bridging Time-Frequency and Graph Domains: The paper successfully extends the concepts of time-frequency analysis and linear canonical transforms to the graph domain, opening new avenues for analyzing complex graph-structured data.
  • Local Information Capture: Vertex-frequency analysis methods based on GLCT are shown to be more effective at capturing local information within graph signals, overcoming limitations of traditional spectral methods.
  • Filter Design for Graph Neural Networks: The proposed filter design methods, especially the learned filters, are presented as potential building blocks for spectral graph neural networks (SGNNs), suggesting practical applications.

Key Results

  • Visualizations: Figures demonstrate how the GLCT can adapt its spectral representation to different graph signals and how its eigenvectors change with parameter adjustments, showcasing its flexibility.
  • Image Classification Performance: In Example 15, using a 4-NN graph on the MNIST dataset, the proposed method achieved a training accuracy of 95.15% and a test accuracy of 93.58% with Chebyshev polynomial filters. Example 16 suggests that fine-tuning GLCT parameters can further enhance model performance, with the best accuracy achieved at σ = 0.9, ξ = 0, and β = 0.5.
  • Filter Equivalence: The paper demonstrates that fast computation methods for WGLCT yield results equivalent to direct calculation.

Limitations and Future Work

  • Computational Complexity: While fast algorithms are proposed, the inherent complexity of graph transforms can still be a challenge for very large graphs.
  • Parameter Selection: The optimal selection of GLCT parameters (σ, ξ, β) for specific applications might require further investigation.
  • Future Work: The authors plan to delve deeper into exploring the impact of linear canonical parameters to ensure their widespread applicability. They also suggest that the filter design section, akin to convolutional layers in SGNNs, could be employed in large-scale SGNNs. Further research into the practical applications of GLCT and its associated methods in various fields is anticipated.

Summary updated

Abstract

This paper proposes a graph linear canonical transform (GLCT) by decomposing the linear canonical parameter matrix into fractional Fourier transform, scale transform, and chirp modulation for graph signal processing. The GLCT enables adjustable smoothing modes, enhancing alignment with graph signals. Leveraging traditional fractional domain time-frequency analysis, we investigate vertex-frequency analysis in the graph linear canonical domain, aiming to overcome limitations in capturing local information. Filter design methods, including optimal design and learning with stochastic gradient descent, are analyzed and applied to image classification tasks. The proposed GLCT and vertex-frequency analysis present innovative approaches to signal processing challenges, with potential applications in various fields.
BibTeX
@article{chen2024graph,
  author = {Jian Yi Chen and Yu Zhang and Bing Zhao Li},
  title = {{Graph Linear Canonical Transform: Definition, Vertex-Frequency Analysis and Filter Design}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2024},
  doi = {10.1109/tsp.2024.3507787},
}
Figure