Helsinki Algorithms Seminar: "Low-rank methods for network alignment" David Gleich, Purdue University

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Date: Thursday 21.6.2018 at 13:15-14:00
Venue: room T5, CS building, Konemiehentie 2

Speaker:
David Gleich, Purdue University

Title:
Low-rank methods for network alignment

Abstract:

Network alignment is the problem of finding a large, common subgraph between two graphs, and more generally k graphs.  The problem is NP-hard. Practical algorithms to approach it via solving some form of a relaxed version of the NP-hard problem or by defining certain heuristics measures of similarity between the graphs. These algorithms normally work well when there is some form of prior known similarity between the nodes of the graphs to be aligned.  The absence of such information makes the problem much harder and many practical methods and heuristics fail to complete in reasonable amount of time.

I will give a brief overview of the network alignment problem and focus on the case when the similarity measure is absent.  I will discuss two of our recent algorithms that relate to pairwise network alignment as well as multiple network alignment when no prior similarity is provided.  These algorithms exploit a low-rank structure in the network alignment problem and thus perform much faster than classic state of the art network alignment algorithms. They enable hundreds of networks with thousands of nodes to be aligned in less than 30 minutes.

Software:
https://github.com/nassarhuda/lowrank_spectral
https://github.com/nassarhuda/MSD

Papers:
10.1145/3178876.3186128
https://arxiv.org/abs/1703.10511

Bio:

David Gleich is the Jyoti and Aditya Mathur Associate Professor in the Computer Science Department at Purdue University whose research is on novel models and fast large-scale algorithms for data-driven scientific computing including scientific data analysis, bioinformatics, and network analysis. He is committeed to making software available based on this research and has written software packages such as MatlabBGL with thousands of users worldwide.

Gleich has received a number of awards for his research including a SIAM Outstanding Publication prize (2018), a Sloan Research Fellowship (2016), an NSF CAREER Award (2011), the John von Neumann post-doctoral fellowship at Sandia National Laboratories in Livermore CA (2009). His research is funded by the NSF, DOE, DARPA, and NASA. For more information, see his website.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.