EAGER: Spectral Network Alignment

Suppose one wants to understand the similarities between two, very

large, unknown networks from an application domain, e.g., brain

networks, gene expression networks, or protein networks. There are two

associated problems that are far from trivial: how to quantify

similarity, and how to detect it in a reasonable amount of time,

considering that the networks can have millions or billions of

connections. Researchers have used methods inspired by combinatorics

and network theory, but so far these methods have run into many

complexity-theoretic barriers and it is not clear whether they can

capture true functional similarities of networks.

A more recent approach is based on spectral graph theory, which is the

expertise of the investigator. In particular, the approach taken here

is an original application of graph Laplacians and quantitative

algorithms around real quadratic forms. There are numerous natural and

unexplored algorithmic and complexity-theoretic questions in this area

that the investigator will pursue. A particularly interesting aspect

of this proposal is how it is related to the graph isomorphism

problem, but deals with relaxations that potentially enable

circumventing this venerable barrier. The investigator, with his

established connections with biologists and health scientists, will

also apply his work toward more practical software for network

alignment.

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.