Sampling Random Graph Homomorphisms and Its Applications in Network Data Analysis
Hanbaek Lyu, Facundo Memoli, David Sivakoff; 24(9):1−79, 2023.
Abstract
A graph homomorphism refers to a mapping between two graphs that preserves adjacency relations. This study focuses on the problem of sampling a random graph homomorphism from a graph into a large network. We propose two complementary Markov Chain Monte Carlo (MCMC) algorithms for this purpose and provide bounds on their mixing times as well as the concentration of their time averages. Our sampling algorithms serve as the foundation for a novel framework for network data analysis, which overcomes certain limitations associated with methods based on independent and neighborhood sampling. By analyzing various time averages of the MCMC trajectory, we can compute different observables, including well-known ones such as homomorphism density and average clustering coefficient, as well as their generalizations. Additionally, we demonstrate the stability of these network observables with respect to a suitably renormalized cut distance between networks. To illustrate our framework, we present several examples and simulations using synthetic networks. Furthermore, we apply our framework to network clustering and subgraph classification tasks using the Facebook100 dataset and Word Adjacency Networks of a set of classic novels.
[abs]