Overview of Research

Here are representative publications and descriptions of our ongoing research areas:


Representation learning [top]

The goal of network representation learning is to automatically learn low-dimensional embeddings of graph structural properties as a principled alternative to heuristic and/or manual feature extraction. These methods, which are often either inspired by deep learning or directly use deep learning, have shown to be extremely effective in many downstream data mining and machine learning tasks. In our lab, we’re developing network representation learning techniques toward goals like node alignment among multiple graphs and role inference in social networks.

  • node2bits: Compact Time- and Attribute-aware Node Representations for User Stitching
    Di Jin, Mark Heimann, Ryan Rossi, Danai Koutra
    In Proceedings of the ECML/PKDD European Conference on Principles and Practice of Knowledge Discovery in Databases, September 2019
    [PDF]

  • When to Remember Where You Came from: Node Representation Learning in Higher-order Networks
    Caleb Belth, Fahad Kamran, Donna Tjandra, Danai Koutra
    In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), August 2019
    [PDF]

  • Latent Network Summarization: Bridging Network Embedding and Summarization
    Di Jin, Ryan Rossi, Eunyee Koh, Sungchul Kim, Anup Rao, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • Smart Roles: Inferring Professional Roles in Email Networks
    Di Jin*, Mark Heimann*, Tara Safavi, Mengdi Wang, Wei Lee, Lindsay Snider, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data
    Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • REGAL: Representation Learning-based Graph Alignment
    Mark Heimann, Haoming Shen, Tara Safavi, Danai Koutra
    In ACM Conference on Information and Knowledge Management (CIKM), October 2018
    [PDF] [Code]


Multi-network analysis [top]

Many important problems in the natural and social sciences involve not one but multiple networks, like protein-protein network alignment and user re-identification across social networks. Under this umbrella, we’re studying the problems of node alignment to identify corresponding entities across networks and graph similarity to quantify the similarity between two or more graphs.

  • REGAL: Representation Learning-based Graph Alignment
    Mark Heimann, Haoming Shen, Tara Safavi, Danai Koutra
    In ACM Conference on Information and Knowledge Management (CIKM), October 2018
    [PDF] [Code]

  • HashAlign: Hash-based Alignment of Multiple Graphs
    Mark Heimann, Wei Lee, Shengjie Pan, Kuan-Yu Chen, Danai Koutra
    In Proceedings of the 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), April 2018
    [PDF] [Code]

  • BIG-ALIGN: Fast Bipartite Graph Alignment
    Danai Koutra, Hanghang Tong, David Lubensky
    In IEEE 13th International Conference on Data Mining (ICDM), December 2013
    [PDF]

  • Network similarity via multiple social theories
    Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, Christos Faloutsos
    In Advances in Social Networks Analysis and Mining 2013 (ASONAM), August 2013
    [PDF]

  • DeltaCon: A Principled Massive-Graph Similarity Function
    Danai Koutra, Joshua Vogelstein, Christos Faloutsos
    In Proceedings of the 13th SIAM International Conference on Data Mining (SDM), May 2013
    [PDF]


Graph summarization [top]

While recent advances in computing resources have made processing enormous amounts of data possible, human ability to quickly identify patterns in such data has not scaled accordingly. Computational methods for condensing and simplifying data are thus a crucial part of the data-driven decision making process. Similar to text summarization, which shortens a body of text while retaining meaning and important information, the goal of graph summarization is to create a smaller, abstracted version of a large graph by describing it with its most “important” or “interesting” structures.

  • Latent Network Summarization: Bridging Network Embedding and Summarization
    Di Jin, Ryan Rossi, Eunyee Koh, Sungchul Kim, Anup Rao, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • Graph Summarization Methods and Applications: A Survey
    Yike Liu, Tara Safavi, Abhilash Dighe, Danai Koutra
    In ACM Computing Surveys (CSUR), June 2018
    [PDF]

  • Reducing large graphs to small supergraphs: a unified approach
    Yike Liu, Tara Safavi, Neil Shah, Danai Koutra
    In Social Network Analysis and Mining (SNAM), February 2018
    [PDF] [Demo]

  • Exploratory Analysis of Graph Data by Leveraging Domain Knowledge
    Di Jin, Danai Koutra
    In IEEE International Conference on Data Mining (ICDM), November 2017
    [PDF] [Code]

  • TimeCrunch: Interpretable Dynamic Graph Summarization
    Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, Christos Faloutsos
    In Proceedings of the 21st ACM International Conference on Knowledge Discovery and Data Mining (KDD), August 2015
    [PDF]

  • VOG: Summarizing and Understanding Large Graphs
    Danai Koutra, U Kang, Jilles Vreeken, Christos Faloutsos
    In Proceedings of the 2014 SIAM International Conference on Data Mining (SDM), April 2014
    [PDF] [Code]
    Best paper nominee


Distributed graph methods [top]

Many graph mining tasks involve iteratively solving linear systems: for example, classifying entities in a network setting with limited supervision and finding similar nodes. As data volumes grow, faster methods for solving linear systems are becoming more and more important. We work on speeding up such methods for large graphs in both sequential and distributed environments, exploring tradeoffs between computational complexity and accuracy for both static and dynamic graphs.

  • Fast Flow-based Random Walk with Restart in a Multi-query Setting
    Yujun Yan, Mark Heimann, Di Jin, Danai Koutra
    In Proceedings of the 2018 SIAM International Conference on Data Mining (SDM), February 2018
    [PDF] [Code]

  • Linearized and Single-pass Belief Propagation
    Wolfgang Gatterbaur, Stephan Gunnemann, Danai Koutra, Christos Faloutsos
    In Proceedings of the VLDB Endowment (VLDB), January 2015
    [PDF]

  • Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms
    Danai Koutra, Tai-You Ke, U Kang, Duen Horng (Polo) Chau, Hsing-Kuo Kenneth Pao, Christos Faloutsos
    In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD), September 2011
    [PDF]


Brain network analysis [top]

Advances in brain imaging machinery have led to the generation of brain maps that describe the brain’s network organization. Analyzing these networks may be key to understanding a variety of brain processes, like maturation, aging, and disease. In our lab, we focus on efficient network-theoretical methods to aid neuroscience practitioners in tasks like abnormality detection and network inference.

  • GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data
    Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • Fast Network Discovery on Sequence Data via Time-Aware Hashing
    Tara Safavi, Chandra Sripada, Danai Koutra
    In Knowledge and Information Systems (KAIS), August 2018
    [PDF]
    Invited from ICDM 2017

  • Scalable Hashing-based Network Discovery
    Tara Safavi, Chandra Sripada, Danai Koutra
    In IEEE International Conference on Data Mining (ICDM), November 2017
    [PDF] [Code]
    Best paper nominee

  • DeltaCon: A Principled Massive-Graph Similarity Function
    Danai Koutra, Joshua Vogelstein, Christos Faloutsos
    In Proceedings of the 13th SIAM International Conference on Data Mining (SDM), May 2013
    [PDF]


User modeling [top]

Massive amounts of available online user information–for example, in social networks, online marketplaces, and streaming music and video services–have made possible the analysis and understanding of user behavior over time at a very large scale. In this area, we’re exploring network-theoretical approaches to user modeling for several different applications, like product and service design, news consumption, and career trajectories.

  • Smart Roles: Inferring Professional Roles in Email Networks
    Di Jin*, Mark Heimann*, Tara Safavi, Mengdi Wang, Wei Lee, Lindsay Snider, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019
    [PDF]

  • Career Transitions and Trajectories: A Case Study in Computing
    Tara Safavi, Maryam Davoodi, Danai Koutra
    In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2018
    [PDF] [Data]

  • PNP: Fast Path Ensemble Method for Movie Design
    Danai Koutra, Abhilash Dighe, Smriti Bhagat, Udi Weinsberg, Stratis Ioannidis, Christos Faloutsos, Jean Bolot
    In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2017
    [PDF]

  • If Walls Could Talk: Patterns and Anomalies in Facebook Wallposts
    Pravallika Devineni, Danai Koutra, Michalis Faloutsos, Christsos Faloutsos
    In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015 (ASONAM), August 2015
    [PDF]

  • Events and Controversies: Influences of a Shocking News Event on Information Seeking
    Danai Koutra, Paul Bennett, Eric Horvitz
    In 24th International World Wide Web Conference (WWW), May 2015
    [PDF]


Interactive graph analytics [top]

The initial steps of data exploration often include visual and statistical analysis, but exploration can be time-consuming (and even unrealistic) for large-scale graphs. To help users explore their graphs, we focus on two directions. The first is visualization-based platforms that allow users to interact with graph data without being overwhelmed. The second is efficient exploratory methods for reducing the dimensionality of graph data.

  • Exploratory Analysis of Graph Data by Leveraging Domain Knowledge
    Di Jin, Danai Koutra
    In IEEE International Conference on Data Mining (ICDM), November 2017
    [PDF] [Code]

  • PERSEUS-HUB: Interactive and Collective Exploration of Large-Scale Graphs
    Di Jin, Aristotelis Leventidis, Haoming Shen, Ruowang Zhang, Junyue Wu, Danai Koutra
    In Informatics, June 2017
    [PDF] [Code]

  • PERSEUS3: Visualizing and Interactively Mining Large-Scale Graphs
    Di Jin, Ticha Sethapakdi, Danai Koutra, Christos Faloutsos
    In SIGKDD Mining and Learning with Graphs Workshop (KDD MLG), August 2016
    [PDF]

  • Perseus: an interactive large-scale graph mining and visualization tool
    Danai Koutra, Di Jin, Yuanchi Ning, Christos Faloutsos
    In Proceedings of the VLDB Endowment (VLDB), September 2015
    [PDF]

  • Graph-based Anomaly Detection and Description: A Survey
    Leman Akoglu, Hanghang Tong, Danai Koutra
    In Data Mining and Knowledge Discovery (DAMI), 2014
    [PDF]

  • OPAvion: Mining and Visualization in Large Graphs
    Leman Akoglu, Duen Horng Chau, U Kang, Danai Koutra, Christos Faloutsos
    In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD), 2012
    [PDF]