2017/04/18 by Lin Li, Li, Lin, William M. Campbell +3
Computer Science · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Graph Theory and Algorithms #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1704.05516
openalex publication_date 2017/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.