EAGER: Spectral Network Alignment

点击翻译按钮获取中文摘要

Suppose one wants to understand the similarities between two, verylarge, unknown networks from an application domain, e.g., brainnetworks, gene expression networks, or protein networks. There are twoassociated problems that are far from trivial: how to quantifysimilarity, and how to detect it in a reasonable amount of time,considering that the networks can have millions or billions ofconnections. Researchers have used methods inspired by combinatoricsand network theory, but so far these methods have run into manycomplexity-theoretic barriers and it is not clear whether they cancapture true functional similarities of networks.A more recent approach is based on spectral graph theory, which is theexpertise of the investigator. In particular, the approach taken hereis an original application of graph Laplacians and quantitativealgorithms around real quadratic forms. There are numerous natural andunexplored algorithmic and complexity-theoretic questions in this areathat the investigator will pursue. A particularly interesting aspectof this proposal is how it is related to the graph isomorphismproblem, but deals with relaxations that potentially enablecircumventing this venerable barrier. The investigator, with hisestablished connections with biologists and health scientists, willalso apply his work toward more practical software for networkalignment.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.