EAGER: Spectral Network Alignment

假设一个人想了解两个非常大的未知网络之间的相似性，例如，大脑网络、基因表达网络或蛋白质网络。有两个相关的问题是非常重要的：如何量化相似性，以及如何在合理的时间内检测它，考虑到网络可能有数百万或数十亿的连接。研究人员使用了受组合数学和网络理论启发的方法，但到目前为止，这些方法遇到了许多复杂性理论的障碍，并且还不清楚它们是否能够捕获网络的真正功能相似性。最近的方法是基于谱图理论，这是研究人员的专业知识。特别是，这里采取的方法是一个原始的应用程序的图形拉普拉斯算子和quantitativealgorithms周围的真实的二次型。在这一领域有许多自然的和未探索的算法和复杂性理论问题，研究人员将继续研究。这个建议的一个特别有趣的方面是它如何与图同构问题相关，但处理可能使这个古老的障碍得以克服的放松。该研究员与生物学家和健康科学家建立了联系，他还将把自己的工作应用于更实用的网络校准软件。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.