Signal processing on large networks with group symmetries
Current methods of graph signal processing rely heavily on the specific structure of the underlying network: the shift operator and the graph Fourier transform are both derived directly from a specific graph. In many cases, the network is subject to error or natural changes over time. This motivated a new perspective on GSP, where the signal processing framework is developed for an entire class of graphs with similar structures. This approach can be formalized via the theory of graph limits, where graphs are considered as random samples from a distribution represented by a graphon. When the network under consideration has underlying symmetries, they may be modeled as samples from Cayley graphons. In Cayley graphons, vertices are sampled from a group, and the link probability between two vertices is determined by a function of the two corresponding group elements. Infinite groups such as the 1-dimensional torus can be used to model networks with an underlying spatial reality. Cayley graphons on finite groups give rise to a Stochastic Block Model, where the link probabilities between blocks form a (edge-weighted) Cayley graph. This manuscript summarizes some work on graph signal processing on large networks, in particular samples of Cayley graphons.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic Block ModelSimilar Papers 제목 키워드 기반
Algebraic Convolutional Filters on Lie Group Algebras
Group convolutional neural networks are a useful tool for utilizing symmetries known to be in a signal; however, they require that the signal is defined on the group itself. Existing approaches either work directly with …
Approximately Equivariant Graph Networks
Graph neural networks (GNNs) are commonly described as being permutation equivariant with respect to node relabeling in the graph. This symmetry of GNNs is often compared to the translation equivariance of Euclidean conv…
Image InpaintingPose EstimationTranslationLie Group Algebra Convolutional Filters
In this paper we propose a framework to leverage Lie group symmetries on arbitrary spaces exploiting \textit{algebraic signal processing} (ASP). We show that traditional group convolutions are one particular instantiatio…
Multi-Dimensional Scaling on Groups
Leveraging the intrinsic symmetries in data for clear and efficient analysis is an important theme in signal processing and other data-driven sciences. A basic example of this is the ubiquity of the discrete Fourier tran…
Dimensionality ReductionUnified 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 C…
Stochastic Block Model