This was part of Randomness in Topology and its Applications

Multi-Scale Analysis of Random Functions on Graphs

Alex Strang, University of Chicago

Friday, March 24, 2023



Abstract:

The global structure of edge flows, alternating functions on graph edges, and their simplicial extensions can be characterized via projection onto principled subspaces associated with graph operators. Classically, the edge-incidence matrix acts as a discrete gradient whose associated subspaces are widely used to decompose an edge flow into a conservative and rotational component. Simplicial homology extends this idea to complexes via chains of operators that map between simplices of neighboring dimension. The expected structure of randomly sampled functions is determined by the covariance of the sampled function, and the projector onto the associated subspace. We analyze the relation between expected structure, covariance, and graph topology, by expanding both the covariance and the projector onto powers of a weighted adjacency matrix defined by the operator and its adjoint. We show that, in this basis, the expected structure is easily interpreted using the coefficients of the associated power series, and that truncating the series can produce accurate approximations even when the graph topology is not known exactly. We then study the spectral characteristics of graph families that enable approximation with a small number of terms.