I am a PhD candidate in the computer science department at the University of Michigan, where I consider myself fortunate to be a member of the GEMS Lab and advised by Danai Koutra. I spent the summer of 2018 at Oak Ridge National Laboratory, working with Dr. Ramakrishnan Kannan on nonlinear dimensionality reduction. We collaborated with researchers at the Center for Nanophase Materials Sciences to develop new algorithms for hyperspectral unmixing.
My current research focuses on representation learning in networks, where I am developing methods to learn vector embeddings of nodes that can be used for multi-network problems such as network alignment. I have broader interests in methods and applications for representation learning, matrix factorization, and nonlinear dimensionality reduction.
Research Projects
- Multi-Network Representation Learning: We propose REGAL, a framework for network alignment that leverages latent feature representations of nodes (also known as node embeddings) in multiple networks. Most existing node embedding methods, despite their popularity for downstream graph mining tasks on a single graph, produce embeddings that are not comparable across multiple graphs. Thus, as part of REGAL we develop a new method for node embedding, Cross-network Matrix Factorization (xNetMF) that a) preserves node similarities based on structural identity and attribute information (if available) that can be compared in multiple graphs, and b) omits the variance-inducing context sampling with random walks that many competing methods use. Leveraging techniques from low-rank matrix approximation for embedding, and efficient data structure for embedding matching, allows REGAL to scale to extremely large networks.
- Fast Network Alignment: We develop HashAlign, a flexible framework for aligning graphs quickly by using locality-sensitive hashing to avoid comparing all possible combinations of nodes. Instead, with high probability we only compare the most similar nodes based on feature vectors for which we propose sensible construction methods. This framework is flexible, as it can be easily extended to graphs where node and/or edge attributes are known; if known, they can be incorporated into the nodes' feature vectors.
- Solving Large-Scale Linear Systems: We develop FLOWR, a fast "flow"-based methods for solving network problems that can be expressed as linear systems, including Random Walk with Restart (RWR), in a distributed setting. Such systems, we show, can be solved in a divide-and-conquer fashion by breaking them into subproblems (smaller clusters of the original network) such that the communication between subproblems (vertices adjacent to vertices in other clusters, or "flow") is minimized. Furthermore, our method can leverage the benefit of overlapping clusters, which makes individual clusters larger, but minimizes the amount of communication across clusters.
Publications
- Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. REGAL: Representation Learning-based Graph Alignment. International Conference on Information and Knowledge Management (CIKM), 2018. [code]
- Mark Heimann*, Wei Lee*, Shengjie Pan, Kuan-Yu Chen, and Danai Koutra. HashAlign: Hash-Based Alignment of Multiple Graphs. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2018.
- Yujun Yan, Mark Heimann, Di Jin, and Danai Koutra. Fast Flow-based Random Walk with Restart in a Multi-query Setting. SIAM International Conference on Data Mining (SDM), 2018.
- Mark Heimann and Danai Koutra. On Generalizing Neural Node Embedding Methods to Multi-Network Problems. KDD Workshop on Mining and Learning with Graphs (MLG), 2017.