FACETS: Adaptive local exploration of large graphs

Robert Pienta, Minsuk Kahng, Zhiyuan Lin, Jilles Vreeken, Partha Talukdar, James Abello, Ganesh Parameswaran, Duen Horng Chau

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 17th SIAM International Conference on Data Mining, SDM 2017
EditorsNitesh Chawla, Wei Wang
PublisherSociety for Industrial and Applied Mathematics Publications
Pages597-605
Number of pages9
ISBN (Electronic)9781611974874
StatePublished - Jan 1 2017
Event17th SIAM International Conference on Data Mining, SDM 2017 - Houston, United States
Duration: Apr 27 2017Apr 29 2017

Publication series

NameProceedings of the 17th SIAM International Conference on Data Mining, SDM 2017

Other

Other17th SIAM International Conference on Data Mining, SDM 2017
CountryUnited States
CityHouston
Period4/27/174/29/17

Fingerprint

Scalability
Visualization

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications

Cite this

Pienta, R., Kahng, M., Lin, Z., Vreeken, J., Talukdar, P., Abello, J., ... Chau, D. H. (2017). FACETS: Adaptive local exploration of large graphs. In N. Chawla, & W. Wang (Eds.), Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017 (pp. 597-605). (Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017). Society for Industrial and Applied Mathematics Publications.
Pienta, Robert ; Kahng, Minsuk ; Lin, Zhiyuan ; Vreeken, Jilles ; Talukdar, Partha ; Abello, James ; Parameswaran, Ganesh ; Chau, Duen Horng. / FACETS : Adaptive local exploration of large graphs. Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017. editor / Nitesh Chawla ; Wei Wang. Society for Industrial and Applied Mathematics Publications, 2017. pp. 597-605 (Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017).
@inproceedings{48906c15b4154901a74ffe0ba16dd211,
title = "FACETS: 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.",
author = "Robert Pienta and Minsuk Kahng and Zhiyuan Lin and Jilles Vreeken and Partha Talukdar and James Abello and Ganesh Parameswaran and Chau, {Duen Horng}",
year = "2017",
month = "1",
day = "1",
language = "English (US)",
series = "Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017",
publisher = "Society for Industrial and Applied Mathematics Publications",
pages = "597--605",
editor = "Nitesh Chawla and Wei Wang",
booktitle = "Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017",
address = "United States",

}

Pienta, R, Kahng, M, Lin, Z, Vreeken, J, Talukdar, P, Abello, J, Parameswaran, G & Chau, DH 2017, FACETS: Adaptive local exploration of large graphs. in N Chawla & W Wang (eds), Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017. Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017, Society for Industrial and Applied Mathematics Publications, pp. 597-605, 17th SIAM International Conference on Data Mining, SDM 2017, Houston, United States, 4/27/17.

FACETS : Adaptive local exploration of large graphs. / Pienta, Robert; Kahng, Minsuk; Lin, Zhiyuan; Vreeken, Jilles; Talukdar, Partha; Abello, James; Parameswaran, Ganesh; Chau, Duen Horng.

Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017. ed. / Nitesh Chawla; Wei Wang. Society for Industrial and Applied Mathematics Publications, 2017. p. 597-605 (Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - FACETS

T2 - Adaptive local exploration of large graphs

AU - Pienta, Robert

AU - Kahng, Minsuk

AU - Lin, Zhiyuan

AU - Vreeken, Jilles

AU - Talukdar, Partha

AU - Abello, James

AU - Parameswaran, Ganesh

AU - Chau, Duen Horng

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85027849753&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027849753&partnerID=8YFLogxK

M3 - Conference contribution

T3 - Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017

SP - 597

EP - 605

BT - Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017

A2 - Chawla, Nitesh

A2 - Wang, Wei

PB - Society for Industrial and Applied Mathematics Publications

ER -

Pienta R, Kahng M, Lin Z, Vreeken J, Talukdar P, Abello J et al. FACETS: Adaptive local exploration of large graphs. In Chawla N, Wang W, editors, Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017. Society for Industrial and Applied Mathematics Publications. 2017. p. 597-605. (Proceedings of the 17th SIAM International Conference on Data Mining, SDM 2017).