Description: Temporal graph embedding has been widely studied due to its superiority in tasks such as prediction and recommendation. Despite the advancement in algorithms and novel frameworks such as deep learning, there has been relatively little work on systematically studying the properties of temporal network models and their cornerstones, the graph time-series representations that are used in these approaches. This paper aims to fill this gap by introducing a general framework that extends an arbitrary existing static embedding approach to handle dynamic tasks, and conducting a systematic study of seven base static embedding methods and six temporal network models.
Reference: On Generalizing Static Node Embedding to Dynamic Settings. Di Jin, Ryan Rossi, Sungchul Kim, Danai Koutra. In The Fifteenth International Conference on Web Search and Data Mining (WSDM), October 2021 [PDF]
Description: In-depth study on the scalable graph learning algorithm based on temporal random walk, which operates on dynamic input graphs and has attracted less attention in the architecture community compared to GCN. We propose high-performance CPU and GPU implementations of two important graph learning tasks, that cover a broad class of applications, using random walks on continuous-time dynamic graphs: link prediction and node classification. We show that the resulting workload exhibits distinct characteristics, measured in terms of irregularity, core and memory utilization, and cache hit rates, compared to graph traversals, deep learning, and GCN. We further conduct an in-depth performance analysis focused on both algorithm and hardware to guide future software optimization and architecture exploration. The algorithm-focused study presents a rich trade-off space between algorithmic performance and runtime complexity to identify optimization opportunities.
Reference: A Deep Dive Into Understanding The Random Walk-Based Temporal Graph Learning. Nishil Talati, Di Jin, Haojie Ye, Ajay Brahmakshatriya, Saman Amarasinghe, Trevor Mudge, Danai Koutra, Ronald Dreslinski. In The the 2021 IEEE International Symposium on Workload Characterization (IISWC), November 2021 [PDF]
Description: Unsupervised method for refining initial alignments between the nodes of two graphs. RefiNA’s goal is to increase the matched neighborhood consistency of the alignment solution produced by any of the many existing methods for network alignment, thereby improving its quality.
Reference: Refining Network Alignment to Improve Matched Neighborhood Consistency. Mark Heimann, Xiyuan Chen, Fatemeh Vahedian, Danai Koutra. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), April 2021 [PDF]
Description: We propose the problem of mining activity that persists through time in continually evolving networks. We extend the notion of temporal motifs to capture activity among specific nodes, in what we call activity snippets, which are small sequences of edge-updates that reoccur. We propose axioms and properties that a measure of persistence should satisfy, and develop such a persistence measure. Then, we propose PENminer, an efficient framework for mining activity snippets’ Persistence in Evolving Networks, and design both offline and streaming algorithms.
Reference: Mining Persistent Activity in Continually Evolving Networks. Caleb Belth, Carol Xinyi Zheng, Danai Koutra. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), May 2020 [PDF]
Description: We introduce a unified solution to KG characterization by formulating the problem as unsupervised KG summarization with a set of inductive, soft rules, which describe what is normal in a KG, and thus can be used to identify what is abnormal, whether it be strange or missing.
Reference: What is Normal, What is Strange, and What is Missing in a Knowledge Graph: Unified Characterization via Inductive Summarization. Caleb Belth, Carol Xinyi Zheng, Jilles Vreeken, Danai Koutra. In The WEB Conference, February 2020 [PDF]
Description: We propose personalized summaries of large encyclopedic knowledge graphs containing the facts most relevant to individual users’ interests.
Reference: Personalized Knowledge Graph Summarization: From the Cloud to Your Pocket. Tara Safavi, Caleb Belth, Lukas Faber, Davide Mottin, Emmanuel Müller, Danai Koutra. In IEEE International Conference on Data Mining (ICDM), November 2019 [PDF]
Description: Given any set of node embeddings for a graph, we propose a scalable, principled method for computing a feature descriptor for the entire graph that captures the distribution of its nodes’ embeddings in vector space.
Reference: Distribution of Node Embeddings as Multiresolution Features for Graphs. Mark Heimann, Tara Safavi, Danai Koutra. In IEEE International Conference on Data Mining (ICDM), November 2019 [PDF]
Description: We propose an efficient framework that represents multi-dimensional features of node contexts with binary hashcodes to handle the task of visitor stitching, i.e., identifying and matching various online references to the same user in real-world web services.
Reference: 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]
Description: An inductive framework that derives representation independent of graph sizes while retaining the ability to compute node embeddings on the fly.
Reference: Latent Network Summarization: Bridging Network Embedding and Summarization. Di Jin, Ryan Rossi, Eunyee Koh, Sungchul Kim, Anup Rao, Danai Koutra. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019 [PDF]
Description: A fast node embedding method that incorporates both graph directionality and edge weights. We show its application on inferring professional hierarchy of employees across companies.
Reference: 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 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), August 2019 [PDF]
Description: In this work, we have developed a graph neural network model that can provide interpretable results beyond fast and accurate graph classification.
Reference: 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]
Description: We develop a scalable algorithm that uses learned structural node embeddings to match nodes across multiple graphs.
Reference: 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]
Description: We propose a locality-sensitive hashing (LSH) framework for matching nodes across multiple undirected, weighted, and/or attributed graphs.
Reference: 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]
Description: We introduce a two-step divide-and-conquer approach to solving linear systems in settings where many queries need to be handled. Our parallelizable method, FlowR, uses a one-time message exchange between subproblems. We further speed up our proposed method by extending our formulation to carefully designed overlapping subproblems (FlowR-OV) and by leveraging the strengths of iterative methods (FlowR-Hyb).
Reference: 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]
Description: We introduce EAGLE (Exploratory Analysis of Graphs with domain knowLEdge), a novel method that creates interpretable, feature-based, and domain-specific graph summaries in a fully automatic way.
Reference: Exploratory Analysis of Graph Data by Leveraging Domain Knowledge. Di Jin, Danai Koutra. In IEEE International Conference on Data Mining (ICDM), November 2017 [PDF]
Description: We propose a fast network discovery approach from time series based on ABC, a new locality-sensitive hashing (LSH) family, which randomly selects and matches time series subsequences.
Reference: Scalable Hashing-based Network Discovery. Tara Safavi, Chandra Sripada, Danai Koutra. In IEEE International Conference on Data Mining (ICDM), November 2017 [PDF]
Description: Perseus-Hub is an interactive graph summarization and anomaly detection system designed to help practitioners understand their data.
Reference: 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]
VoG: Vocabulary-based summarization of Graphs code
Description: We propose VoG, which summarizes a graph via the subgraphs that describe it best. To do so, we use the Minimum Description Length (MDL) principle: a subgraph is included in the summary if it decreases the total description length of the graph.
Reference: 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]