Learning graphons from data: Random walks, transfer operators, and spectral clustering
Many signals evolve in time as a stochastic process, randomly switching between states over discretely sampled time points. Here we make an explicit link between the underlying stochastic process of a signal that can take on a bounded continuum of values and a random walk process on a graphon. Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs whose size tends to infinity. We introduce transfer operators, such as the Koopman and Perron--Frobenius operators, associated with random walk processes on graphons and then illustrate how these operators can be estimated from signal data and how their eigenvalues and eigenfunctions can be used for detecting clusters, thereby extending conventional spectral clustering methods from graphs to graphons. Furthermore, we show that it is also possible to reconstruct transition probability densities and, if the random walk process is reversible, the graphon itself using only the signal. The resulting data-driven methods are applied to a variety of synthetic and real-world signals, including daily average temperatures and stock index values.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimization of randomized neural networks for transfer operator approximation
RaNNDy is a randomized neural network architecture for the data-driven approximation of transfer operators associated with complex dynamical systems. The weights and biases of the hidden layers of the network are randoml…
The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs, as a function of their number of layers, to distinguish between different random graph mod…
Graph Representation LearningRepresentation LearningA Spectral Framework for Graph Neural Operators: Convergence Guarantees and Tradeoffs
Graphons, as limits of graph sequences, provide an operator-theoretic framework for analyzing the asymptotic behavior of graph neural operators. Spectral convergence of sampled graphs to graphons induces convergence of t…
Fundamental Limits of Deep Graph Convolutional Networks
Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate the capabilities and limitations of GCNs, we investigate their power, as a function of their number of layers, …
Graph ClassificationGraph Representation LearningRepresentation LearningHigher-Order Graphon Neural Networks: Approximation and Cut Distance
Graph limit models, like graphons for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this …