Adaptive Local Exploration of Large Graphs

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.

Related Publications

Pienta, R, Kahng, M, Lin, Z, Vreeken, J, Talukdar, P, Abello, J, Parameswaran, G & Chau, DH Adaptive Local Exploration of Large Graphs. In: Proceedings of the SIAM International Conference on Data Mining (SDM), SIAM, 2017. (overall 26% acceptance rate)
Pienta, R, Lin, Z, Kahng, M, Vreeken, J, Talukdar, PP, Abello, J, Parameswaran, G & Chau, DH AdaptiveNav: Adaptive Discovery of Interesting and Surprising Nodes in Large Graphs. In: Proceedings of the IEEE Conference on Visualization (VIS), IEEE, 2015.video
Pienta, R, Lin, Z, Kahng, M, Vreeken, J, Talukdar, PP, Abello, J, Parameswaran, G & Chau, DH Seeing the Forest through the Trees: Adaptive Local Exploration of Large Graphs. Technical Report 1505.06792, arXiv, 2015.