Abstract

Choosing a subgraph that can concisely represent a large real-world graph is useful in many scenarios. The usual strategy employed is to sample nodes so that the induced subgraph matches the original graph’s degree distribution, clustering coefficient, etc., but no attempt is made to preserve fine-grained relationships between nodes, which are vital for applications like clustering, classification, and ranking. In this work, we model such relationships via the notion of Personalized PageRank Value (PPV). We show that induced subgraphs output by current sampling methods do not preserve PPVs, and propose algorithms for creating PPV-preserving subgraphs on any given subset of graph nodes. Experiments on three large real-world graphs show that the subgraphs created by our method improve upon induced subgraphs in terms of preserving PPVs, clustering accuracy, and maintaining basic graph properties.