Making Sense out of Large Graphs: Bridging HCI with Data Mining

 
Christos Faloutsos & Aniket Kittur
Phone: (412)-268.1457
School of Computer Science Fax : (412)-268.5576
Carnegie Mellon Univ. Email: {christos,nkittur} AT cs.cmu.edu
Pittsburgh, PA 15213 WWW page: http://www.cs.cmu.edu/~christos

This material is based upon work supported by the National Science Foundation under Grant No. IIS-1217559. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

1. GENERAL INFORMATION

1.1. Abstract

Link to NSF abstract

The goal of this research project is to help people make sense of large graphs, ranging from social networks to network traffic. The approach consists of combining two complementary fields that have historically had little interaction -- data mining and human-computer interaction -- to develop interactive algorithms and interfaces that help users gain insights from graphs with hundreds of thousands of nodes and edges. The goal of the project is to develop mixed-initative machine learning, visualization, and interaction techniques in which computers do what they are best at (sifting through huge volumes of data and spotting outliers) while humans do what they are best at (recognizing patterns, testing hypotheses, and inducing schemas). This research addresses two classes of tasks: first, attention routing -- using machine learning to direct an analyst's attention to interesting nodes or subgraphs that do not conform to normal behavior. Second, sensemaking -- helping analysts build in-depth representations and mental models of a specific areas or aspects of a graph. Evaluation of the tools will involve both controlled laboratory studies as well as long-term field deployments.

As large graphs appear in many settings -- national security, intrusion detection, business intelligence (recommendation systems, fraud detection), biology (gene regulation), and academia (scientific literature) -- the potential benefits of new tools for making sense of graphs is far reaching. Project results, including open-source software and annotated data sets, will be disseminated via the project web site (http://kittur.org/large_graphs.html) and incorporated into educational activities.

1.2. Keywords

Data mining, HCI, graph mining.

1.3. Funding agency

2. PEOPLE INVOLVED

In addition to the PIs, the following graduate students work on the project.

Publications

  1. BiG-ALIGN: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. ICDM 2013: 389-398
  2. Net-Ray: Visualizing and Mining Billion-Scale Graphs. U Kang, Jay-Yoon Lee, Danai Koutra, and Christos Faloutsos. PAKDD 2014, Tainan, Taiwan.
  3. VoG:Summarizing and Understanding Large Graphs Danai Koutra, U Kang, Jilles Vreeken, Christos Faloutsos. SDM 2014, Philadelphia, PA, April 2014.
  4. Influence Propagation: Patterns, Model and Case Study Yibin Lin, Agha Ali Raza, Jay-Yoon Lee, Danai Koutra, Roni Rosenfeld, Christos Faloutsos. PAKDD 2014, Tainan, Taiwan, May 2014.
  5. Com2: Fast Automatic Discovery of Temporal (Comet) Communities Miguel Araujo, Spiros Papadimitriou, Stephan Guennemann, Christos Faloutsos, Prithwish Basu, Ananthram Swami, Evangelos E. Papalexakis, Danai Koutra. PAKDD 2014, Tainan, Taiwan, May 2014.
  6. Graph-based Anomaly Detection and Description: A Survey. Leman Akoglu, Hanghang Tong, Danai Koutra. Data Mining and Knowledge Discovery (DAMI), April 2014.

3. OFFICIAL WEB SITE

From Prof. Aniket (Niki) Kittur

Last updated: June 4, 2014, by Christos Faloutsos.