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 millionnode 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 JensenShannon divergence over informationtheoretically 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 realworld graphs with up to 5 million edges, returning results in fewer than 1.5 seconds.
Adaptive Local Exploration of Large Graphs. In: Proceedings of the SIAM International Conference on Data Mining (SDM), SIAM, 2017. (overall 26% acceptance rate) 

AdaptiveNav: Adaptive Discovery of Interesting and Surprising Nodes in Large Graphs. In: Proceedings of the IEEE Conference on Visualization (VIS), IEEE, 2015. 

Seeing the Forest through the Trees: Adaptive Local Exploration of Large Graphs. Technical Report 1505.06792, arXiv, 2015. 