Graphon Signal Processing
Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs as their number of nodes goes to infinity. This paper derives a theory of graphon signal processing centered on the notions of graphon Fourier transform and linear shift invariant graphon filters, the graphon counterparts of the graph Fourier transform and graph filters. It is shown that for convergent sequences of graphs and associated graph signals: (i) the graph Fourier transform converges to the graphon Fourier transform when the graphon signal is bandlimited; (ii) the spectral and vertex responses of graph filters converge to the spectral and vertex responses of graphon filters with the same coefficients. These theorems imply that for graphs that belong to certain families, i.e., that are part of sequences that converge to a certain graphon, graph Fourier analysis and graph filter design have well defined limits. In turn, these facts extend applicability of graph signal processing to graphs with large number of nodes -- since signal processing pipelines designed for limit graphons can be applied to finite graphs -- and to dynamic graphs -- since we can relate the result of SP pipelines designed for different graphs from the same convergent graph sequence.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Modeling Sparse Graph Sequences and Signals Using Generalized Graphons
Graphons are limit objects of sequences of graphs and are used to analyze the behavior of large graphs. Recently, graphon signal processing has been developed to study signal processing on large graphs. A major limitatio…
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 cas…
Stochastic Block ModelSampling and Uniqueness Sets in Graphon Signal Processing
In this work, we study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits. To this end, we extend to graphon signals the notion of removable and uniqueness s…
Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs
In this paper we propose a pooling approach for convolutional information processing on graphs relying on the theory of graphons and limits of dense graph sequences. We present three methods that exploit the induced grap…
Dimensionality ReductionGraph and graphon neural network stability
Graph neural networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of large-scale network data. GNN stability is thus important as in real-world s…
Movie Recommendation