Abstract. Visualization is a powerful paradigm for exploratory data analysis. Visualizing large graphs, however, often results in excessive edges crossings and overlapping nodes. We propose a new scalable approach called Facets that helps users adaptively explore large million-node graphs from a local perspective, guiding them to focus on nodes and neighborhoods that are most subjectively interesting to users.

We contribute novel ideas to measure this interestingness in terms of how surprising a neighborhood is given the background distribution, as well as how well it matches what the user has chosen to explore. Facets uses Jensen-Shannon divergence over information-theoretically optimized histograms to calculate the subjective user interest and surprise scores.

Participants in a user study found Facets easy to use, easy to learn, and exciting to use. Empirical runtime analyses demonstrated Facets’s practical scalability on large real-world graphs with up to 5 million edges, returning results in fewer than 1.5 seconds