EAGER: Spectral Network Alignment

EAGER：光谱网络对齐

• 批准号: 2039863
• 负责人: Ioannis Koutis
• 金额: $ 15万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2039863&HistoricalAwards=false
• 关键词: 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.

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

项目成果

Peer Learning Through Targeted Dynamic Groups Formation

通过有针对性的动态团体形成进行同伴学习

• DOI: 10.1109/icde51399.2021.00018
• 发表时间: 2021
• 期刊: 2021 IEEE 37th International Conference on Data Engineering (ICDE
• 作者: Wei, Dong;Koutis, Ioannis;Roy, Senjuti Basu
• 通讯作者: Roy, Senjuti Basu

A generalized Cheeger inequality

广义奇格不等式

• DOI: 10.1016/j.laa.2023.01.014
• 发表时间: 2023
• 期刊: Linear Algebra and its Applications
• 影响因子: 1.1
• 作者: Koutis, Ioannis;Miller, Gary;Peng, Richard
• 通讯作者: Peng, Richard

Ensemble Learning as a Peer Process

集成学习作为同伴过程

• 发表时间: 2022
• 期刊: Agent Learning in Open-Endedness (ALOE
• 作者: Beikihassan, Ehsan;Hoover, Amy;Koutis, Ioannis;Parviz, Ali
• 通讯作者: Parviz, Ali

Long Range Graph Benchmark

• DOI: 10.48550/arxiv.2206.08164
• 发表时间: 2022-06
• 期刊: ArXiv
• 作者: Vijay Prakash Dwivedi;Ladislav Rampášek;Mikhail Galkin;Alipanah Parviz;Guy Wolf;A. Luu;D. Beaini

Generalized Laplacian Positional Encoding for Graph Representation Learning

• DOI: 10.48550/arxiv.2210.15956
• 发表时间: 2022-10
• 期刊: ArXiv
• 作者: Sohir Maskey;Alipanah Parviz;Maximilian Thiessen;Hannes Stärk;Ylli Sadikaj;Haggai Maron