III: Small: A Submodular Framework for Scalable Graph Matching with Performance Guarantees

III：小型：具有性能保证的可扩展图匹配的子模块框架

基本信息

批准号：
1908070
负责人：
Nikolaos Sidiropoulos
金额：
$ 45.67万
依托单位：
University of Virginia Main Campus
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908070&HistoricalAwards=false
关键词：
III Small Submodular Framework Scalable

项目摘要

Graphs are a natural and convenient abstraction for modeling structures arising in a broad spectrum of science and engineering disciplines. In many applications, a key problem is to align a pair of graphs (or "embed" one into the other). This is known as graph matching, and it frequently emerges in machine vision (e.g., landmark matching), learning (knowledge graphs), and graph mining; computational biology (protein-protein interactions); social sciences (social / organizational networks); and electronic circuit layout verification, to name a few areas. Graph matching is a computationally demanding problem, yet modern applications easily generate graphs with millions of vertices. In that regime, there is a pressing need for approximation algorithms which are both theoretically sound and highly scalable. This project considers graph matching from a fresh perspective -- through the lens of submodular optimization. The proposed research will yield exciting new theoretical and methodological insights that will also inform other walks of combinatorial optimization and its applications. In parallel with the research activities, the PIs will contribute to state-wide efforts to broaden participation in computing, via guest lectures in introductory engineering courses, and teaming up with a nonprofit that trains K-12 teachers to empower them to teach coding and computational thinking.Existing graph matching approximations based on relaxing the combinatorial constraints either do not scale well, or fail to provide performance guarantees (except in special cases). None of these directly tackles the combinatorial nature of the problem; the conventional wisdom being that the difficulty stems from the constraints, not the cost function. In preliminary work, the PIs have established that graph matching can be equivalently reformulated as minimizing a submodular function over the intersection of a pair of partition matroids. Using this preliminary result as a stepping stone, this project is focused on designing successive submodular approximation algorithms that feature both theoretical performance guarantees and scalability; hard and soft graph matching (via continuous extension); validation using real-world data; and leveraging the practical insights gained through validation to close the loop and drive further methodological and algorithmic developments. Breaking from the mold, the approach embraces combinatorial optimization using a judicious combination of discrete and continuous optimization tools which promises to go a long way towards improving the state-of-art for this fundamental problem.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.

图是对广泛的科学和工程学科中出现的结构进行建模的自然而方便的抽象。在许多应用中，一个关键问题是对齐一对图（或将一个图“嵌入”另一个图）。这被称为图匹配，它经常出现在机器视觉（例如地标匹配）、学习（知识图）和图挖掘中；计算生物学（蛋白质-蛋白质相互作用）；社会科学（社会/组织网络）；以及电子电路布局验证等领域。图匹配是一个计算要求很高的问题，但现代应用程序可以轻松生成具有数百万个顶点的图。在这种情况下，迫切需要理论上合理且高度可扩展的近似算法。该项目从全新的角度考虑图匹配——通过子模优化的视角。拟议的研究将产生令人兴奋的新理论和方法论见解，也将为组合优化及其应用的其他领域提供信息。在开展研究活动的同时，PI 将通过在入门工程课程中做客座讲座，并与一家培训 K-12 教师的非营利组织合作，帮助他们教授编码和计算知识，从而为全州范围内扩大计算参与做出贡献。现有的基于放宽组合约束的图匹配近似要么不能很好地扩展，要么无法提供性能保证（特殊情况除外）。这些都没有直接解决问题的组合性质；传统观点认为，困难源于约束，而不是成本函数。在初步工作中，PI 已经确定图匹配可以等效地重新表述为最小化一对分区拟阵交集上的子模函数。以这一初步结果为垫脚石，该项目致力于设计兼具理论性能保证和可扩展性的连续子模逼近算法；硬图和软图匹配（通过不断扩展）；使用真实世界数据进行验证；并利用通过验证获得的实际见解来闭环并推动进一步的方法和算法开发。该方法打破了模式，采用离散和连续优化工具的明智组合进行组合优化，这有望在提高这一基本问题的技术水平方面发挥很大作用。该奖项反映了 NSF 的法定使命，并被视为值得通过使用基金会的智力优点和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

XPL-CF: Explainable Embeddings for Feature-based Collaborative Filtering

DOI：
10.1145/3459637.3482221
发表时间：
2021-10
期刊：
Proceedings of the 30th ACM International Conference on Information & Knowledge Management
影响因子：
0
作者：
Faisal M. Almutairi;N. Sidiropoulos;Bo Yang
通讯作者：
Faisal M. Almutairi;N. Sidiropoulos;Bo Yang

GAGE: Geometry Preserving Attributed Graph Embeddings

DOI：
10.1145/3488560.3498467
发表时间：
2020-11
期刊：
Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining
影响因子：
0
作者：
Charilaos I. Kanatsoulis;N. Sidiropoulos
通讯作者：
Charilaos I. Kanatsoulis;N. Sidiropoulos

Phased: Phase-Aware Submodularity-Based Energy Disaggregation

阶段性：基于阶段感知子模块的能量分解

DOI：
10.1145/3427771.3427860
发表时间：
2020
期刊：
2020.
影响因子：
0
作者：
Almutairi, Faisal M.;Konar, Aritra;Zamzam, Ahmed S.;Sidiropoulos, Nicholas D.
通讯作者：
Sidiropoulos, Nicholas D.

TeX-Graph: Coupled tensor-matrix knowledge-graph embedding for COVID-19 drug repurposing