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.
Specifically, my current research interests involve 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 am interested in the connection between node representation learning methods based on deep learning-inspired language modeling techniques, matrix factorization, and low-rank matrix approximation. I also have broader interests in develping scalable methods for various data mining tasks involving network data.
I have an eclectic set of other interests ranging from competitive (high-level) chess and (novice-level) powerlifting to music and amateur baking. Sometimes I manage to combine them with my work; for instance, I am very interested in creating artificial intelligence technology for music analysis and performance, as well as the design and use of electronic effects especially for augmenting acoustic instruments. Most of the time, though, they exist in the space left for them by life as a PhD student, but I'm always happy to talk about them.
Research Projects
- Multi-Network Representation Learning: Most representation learning methods for nodes in graphs, despite their popularity for downstream graph mining tasks on a single graph, produce embeddings that are not comparable across multiple graphs, because the criteria they optimize only make sense in a single graph. We develop a new method for representation learning, 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 allows our method to scale to extremely large networks. We show the comparability of the xNetMF embeddings by using them for graph alignment: our framework REGAL (REpresentation learning for Graph ALignment) leverages data structures for efficiently similarity search to infer alignments from the similarity of the learned embeddings.
- 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, and Danai Koutra. Node Representation Learning for Multiple Networks: The Case of Graph Alignment. Preprint, 2018.
- 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 Methods for Solving Linear Systems in a Distributed 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.