text-only page produced automatically by Usablenet Assistive Skip all navigation and go to page content Skip top navigation and go to directorate navigation Skip top navigation and go to page navigation
National Science Foundation
design element
Search Awards
Recent Awards
Presidential and Honorary Awards
About Awards
Grant Policy Manual
Grant General Conditions
Cooperative Agreement Conditions
Special Conditions
Federal Demonstration Partnership
Policy Office Website

Award Abstract #1217559

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

Div Of Information & Intelligent Systems
divider line
Initial Amendment Date: August 25, 2012
divider line
Latest Amendment Date: July 31, 2014
divider line
Award Number: 1217559
divider line
Award Instrument: Continuing grant
divider line
Program Manager: Maria Zemankova
IIS Div Of Information & Intelligent Systems
CSE Direct For Computer & Info Scie & Enginr
divider line
Start Date: September 15, 2012
divider line
End Date: August 31, 2016 (Estimated)
divider line
Awarded Amount to Date: $528,578.00
divider line
Investigator(s): Christos Faloutsos christos@cs.cmu.edu (Principal Investigator)
Duen Horng Chau (Co-Principal Investigator)
Aniket Kittur (Co-Principal Investigator)
divider line
Sponsor: Carnegie-Mellon University
5000 Forbes Avenue
PITTSBURGH, PA 15213-3815 (412)268-9527
divider line
divider line
Program Reference Code(s): 7364, 7453, 7923, 9251
divider line
Program Element Code(s): 7364, 7453


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.


Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Leman Akoglu, Hanghang Tong, Danai Koutra. "Graph-based Anomaly Detection and Description: A Survey," Data Mining and Knowledge Discovery (DAMI), 2014.

Wolfgang Gatterbauer, Stephan GŁnnemann, Danai Koutra, and Christos Faloutsos. "Linearized and single-pass belief propagation," PVLDB, v.8, 2015, p. 581?592. 


Please report errors in award information by writing to: awardsearch@nsf.gov.



Print this page
Back to Top of page
Research.gov  |  USA.gov  |  National Science Board  |  Recovery Act  |  Budget and Performance  |  Annual Financial Report
Web Policies and Important Links  |  Privacy  |  FOIA  |  NO FEAR Act  |  Inspector General  |  Webmaster Contact  |  Site Map
National Science Foundation Logo
The National Science Foundation, 4201 Wilson Boulevard, Arlington, Virginia 22230, USA
Tel: (703) 292-5111, FIRS: (800) 877-8339 | TDD: (800) 281-8749
  Text Only Version