Unified Fourier bases for signals on random graphs with group symmetries
We consider a recently proposed approach to graph signal processing (GSP) based on graphons. We show how the graphon-based approach to GSP applies to graphs sampled from a stochastic block model derived from a weighted Cayley graph. When SBM block sizes are equal, a nice Fourier basis can be derived from the representation theory of the underlying group. We explore how the SBM Fourier basis is affected when block sizes are not uniform. When block sizes are nearly uniform, we demonstrate that the group Fourier basis closely approximates the SBM Fourier basis. More specifically, we quantify the approximation error using matrix perturbation theory. When block sizes are highly non-uniform, the group-based Fourier basis can no longer be used. However, we show that partial information regarding the SBM Fourier basis can still be obtained from the underlying group.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic Block ModelMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Compressive Recovery of Signals Defined on Perturbed Graphs
Recovery of signals with elements defined on the nodes of a graph, from compressive measurements is an important problem, which can arise in various domains such as sensor networks, image reconstruction and group testing…
compressed sensingImage ReconstructionModel SelectionPosition: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification
Spectral Graph Neural Networks (Spectral GNNs) for node classification promise frequency-domain filtering on graphs, yet rest on flawed foundations. Recent work shows that graph Laplacian eigenvectors do not in general h…
Node ClassificationWindowed Fourier Analysis for Signal Processing on Graph Bundles
We consider the task of representing signals supported on graph bundles, which are generalizations of product graphs that allow for "twists" in the product structure. Leveraging the localized product structure of a graph…
UnityMulti-dimensional Graph Fourier Transform
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 characte…
Time Series AnalysisLearning Spatially Collaged Fourier Bases for Implicit Neural Representation
Existing approaches to Implicit Neural Representation (INR) can be interpreted as a global scene representation via a linear combination of Fourier bases of different frequencies. However, such universal basis functions …
3D Reconstruction3D Shape Representation