Fast Graph Fourier Transforms Based on Graph Symmetry and Bipartition

Abstract

The graph Fourier transform (GFT) is an important tool for graph signal processing, with applications ranging from graph-based image processing to spectral clustering. However, unlike the discrete Fourier transform, the GFT typically does not have a fast algorithm. In this work, we develop new approaches to accelerate the GFT computation. In particular, we show that Haar units (Givens rotations with angle $\pi /4$) can be used to reduce GFT computation cost when the graph is bipartite or satisfies certain symmetry properties based on node pairing. We also propose a graph decomposition method based on graph topological symmetry, which allows us to identify and exploit butterfly structures in stages. This method is particularly useful for graphs that are nearly regular or have some specific structures, e.g., line graphs, cycle graphs, grid graphs, and human skeletal graphs. Though butterfly stages based on graph topological symmetry cannot be used for general graphs, they are useful in applications, including video compression and human action analysis, where symmetric graphs, such as symmetric line graphs and human skeletal graphs, are used. Our proposed fast GFT implementations are shown to reduce computation costs significantly, in terms of both number of operations and empirical runtimes.

arXiv comment14 pages, 15 figures

References in corpus (8)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• OpenPose: Realtime Multi-Person 2D Pose Estimation using Part Affinity Fields
• Autoregressive Moving Average Graph Filtering
• Irregularity-Aware Graph Fourier Transforms
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• Flexible Multi-layer Sparse Approximations of Matrices and Applications
• Steerable Discrete Fourier Transform

Cited by in corpus (9)

• Sampling Signals on Graphs: From Theory to Applications
• Generalized Sampling on Graphs With Subspace and Smoothness Priors
• Bayesian Estimation of Graph Signals
• Graph CNN for Moving Object Detection in Complex Environments from Unseen Videos
• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Joint Time-Vertex Fractional Fourier Transform
• DCT and DST Filtering with Sparse Graph Operators
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• Prediction and Sampling with Local Graph Transforms for Quasi-Lossless Light Field Compression