2017/12/21 by Takashi Kurokawa, Kurokawa, Takashi, Taihei Oki +3 · 4 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME)
paper · pdf · doi:10.48550/arxiv.1712.07811
openalex publication_date 2017/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many signals on Cartesian product graphs appear in the real world, such as digital images, sensor observation time series, and movie ratings on Netflix. These signals are "multi-dimensional" and have directional characteristics along each factor graph. However, the existing graph Fourier transform does not distinguish these directions, and assigns 1-D spectra to signals on product graphs. Further, these spectra are often multi-valued at some frequencies. Our main result is a multi-dimensional graph Fourier transform that solves such problems associated with the conventional GFT. Using algebraic properties of Cartesian products, the proposed transform rearranges 1-D spectra obtained by the conventional GFT into the multi-dimensional frequency domain, of which each dimension represents a directional frequency along each factor graph. Thus, the multi-dimensional graph Fourier transform enables directional frequency analysis, in addition to frequency analysis with the conventional GFT. Moreover, this rearrangement resolves the multi-valuedness of spectra in some cases. The multi-dimensional graph Fourier transform is a foundation of novel filterings and stationarities that utilize dimensional information of graph signals, which are also discussed in this study. The proposed methods are applicable to a wide variety of data that can be regarded as signals on Cartesian product graphs. This study also notes that multivariate graph signals can be regarded as 2-D univariate graph signals. This correspondence provides natural definitions of the multivariate graph Fourier transform and the multivariate stationarity based on their 2-D univariate versions.