Learning graphons from data: Random walks, transfer operators, and spectral clustering

Many signals in the real world that evolve in time can be modeled as a stochastic process with the signal randomly jumping from one state to another as time proceeds. When the signal can only exhibit a finite number of possible states, one can interpret the evolution of the signal as a random walk on a graph with vertices representing the states of the signal and edge weights giving way to the transition probabilities from one state to another. In particular, one arrives at a Markov chain representation of the signal that can be estimated using only the signal data. However, many realistic signals can take on a continuum of values, and so the goal of this work is to present a framework for modeling continuous-space stochastic signals and to identify metastable and coherent sets via clustering techniques. We present a data-driven method to learn the discrete-time transition probabilities of stochastic signals evolving in continuous space, which can be regarded as a generalization of the discrete space case considered in [25, 22]. The underlying theory is developed by evoking the concept of a graphon, which can be defined as the limit of sequences of dense networks that grow without bound [35, 34, 21, 18]. As recently shown in [43], graphons provide a well-developed framework for extending the concepts of random walks on finite graphs to stochastic processes evolving in continuous space. For example, random walks on graphs can be used to measure the centrality of vertices, and these concepts can also be extended to graphons [4]. Our goal is to identify transition probabilities, clusters, and the graphon itself from random walk data.