Title: Graph Model Selection via Random Walks,
Abstract: In this paper, we present a novel approach based on the random walk process
for finding meaningful representations of a graph model. Our approach leverages
the transient behavior of many short random walks with novel initialization
mechanisms to generate model discriminative features. These features are able
to capture a more comprehensive structural signature of the underlying graph
model. The resulting representation is invariant to both node permutation and
the size of the graph, allowing direct comparison between large classes of
graphs. We test our approach on two challenging model selection problems: the
discrimination in the sparse regime of an Erdös-Renyi model from a
stochastic block model and the planted clique problem. Our representation
approach achieves performance that closely matches known theoretical limits in
addition to being computationally simple and scalable to large graphs.