A noncommutative approach to the graphon Fourier transform

DOI10.1016/J.ACHA.2022.06.004MaRDI QIDQ2168681zbMATH OpenOpenAlexFDO

Authors Mahya Ghandehari, Nauzer Kalyaniwalla, Jeannette Janssen

Publication date 26 August 2022

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.08646

zbMATH Keywords

convergent graph sequencesgraph Fourier transformgraph signal processinggraphon Fourier transformgraphons

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) General harmonic expansions, frames (42C15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Signal analysis on graphs relies heavily on the graph Fourier transform, which is defined as the projection of a signal onto an eigenbasis of the associated shift operator. Large graphs of similar structure may be represented by a graphon. Theoretically, graphons are limit objects of converging sequences of graphs. Our work extends previous research aiming to provide a common scheme for signal analysis of graphs that are similar in structure to a graphon. We extend a previous definition of graphon Fourier transform, and show that the graph Fourier transforms of graphs in a converging graph sequence converge to the graphon Fourier transform of the limiting graphon. We then apply this convergence result to signal processing on Cayley graphons. We show that Fourier analysis of the underlying group enables the construction of a suitable eigen-decomposition for the graphon, which can be used as a common framework for signal processing on graphs converging to the graphon.

Recommendations

• Vertex-frequency analysis on graphs
• Signals on graphs: transforms and tomograms
• Wavelets on graphs via spectral graph theory
• Localized Fourier analysis for graph signal processing
• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets

Cites work

• Collective dynamics of `small-world' networks
• Community detection and stochastic block models: recent developments
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Frequency Analysis
• Fast Fourier transform for fitness landscapes
• Fourier theoretic probabilistic inference over permutations
• Gabor-type frames for signal processing on graphs
• Graphon Filters: Graph Signal Processing in the Limit
• Graphon Signal Processing
• scientific article; zbMATH DE number 44595 (Why is no real title available?)
• scientific article; zbMATH DE number 1318047 (Why is no real title available?)
• scientific article; zbMATH DE number 1004944 (Why is no real title available?)
• scientific article; zbMATH DE number 918597 (Why is no real title available?)
• Large networks and graph limits
• Limits of dense graph sequences
• Limits of kernel operators and the spectral regularity lemma
• Limits of randomly grown graph sequences
• Moments of two-variable functions and the uniqueness of graph limits
• Quick approximation to matrices and applications
• Signal processing on the permutahedron: tight spectral frames for ranked data analysis
• The automorphism group of a graphon

Cited in

(8)

• Transferability of graph neural networks: an extended graphon approach
• Turing bifurcation in the Swift-Hohenberg equation on deterministic and random graphs
• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
• Frames for signal processing on Cayley graphs
• Graph limit and exponential consensus for the large-scale multi-agent system with delay
• The large deviation principle for W-random spectral measures
• Inverse graph limit problem of the graphon multi-agent systems
• Unified Fourier transform on graphs sampled from stochastic block models

This page was built for publication: A noncommutative approach to the graphon Fourier transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168681)