III: Small: A Submodular Framework for Scalable Graph Matching with Performance Guarantees
III:小型:具有性能保证的可扩展图匹配的子模块框架
基本信息
- 批准号:1908070
- 负责人:
- 金额:$ 45.67万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-10-01 至 2024-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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
- 期刊:
- 影响因子:0
- 作者:Faisal M. Almutairi;N. Sidiropoulos;Bo Yang
- 通讯作者:Faisal M. Almutairi;N. Sidiropoulos;Bo Yang
Graph Matching Via the Lens of Supermodularity
- DOI:10.1109/tkde.2020.3008128
- 发表时间:2022-05
- 期刊:
- 影响因子:8.9
- 作者:Aritra Konar;N. Sidiropoulos
- 通讯作者:Aritra Konar;N. Sidiropoulos
Phased: Phase-Aware Submodularity-Based Energy Disaggregation
阶段性:基于阶段感知子模块的能量分解
- DOI:10.1145/3427771.3427860
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Almutairi, Faisal M.;Konar, Aritra;Zamzam, Ahmed S.;Sidiropoulos, Nicholas D.
- 通讯作者:Sidiropoulos, Nicholas D.
GAGE: Geometry Preserving Attributed Graph Embeddings
- DOI:10.1145/3488560.3498467
- 发表时间:2020-11
- 期刊:
- 影响因子:0
- 作者:Charilaos I. Kanatsoulis;N. Sidiropoulos
- 通讯作者:Charilaos I. Kanatsoulis;N. Sidiropoulos
Iterative Graph Alignment via Supermodular Approximation
通过超模近似进行迭代图对齐
- DOI:10.1109/icdm.2019.00141
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Konar, Aritra;Sidiropoulos, Nicholas
- 通讯作者:Sidiropoulos, Nicholas
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Nikolaos Sidiropoulos其他文献
EXISTENCE OF SOLUTIONS TO INDEFINITE QUASILINEAR ELLIPTIC PROBLEMS OF P-Q-LAPLACIAN TYPE
- DOI:
- 发表时间:
2010 - 期刊:
- 影响因子:0
- 作者:
Nikolaos Sidiropoulos - 通讯作者:
Nikolaos Sidiropoulos
Nikolaos Sidiropoulos的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Nikolaos Sidiropoulos', 18)}}的其他基金
Blind Carbon Copy on Dirty Paper: Seamless Spectrum Underlay made Practical
脏纸上的盲文复写:无缝频谱底层变得实用
- 批准号:
2118002 - 财政年份:2021
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Robust and Scalable Volume Minimization-based Matrix Factorization for Sensing and Clustering
用于传感和聚类的鲁棒且可扩展的基于体积最小化的矩阵分解
- 批准号:
1852831 - 财政年份:2018
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Collaborative Research: Multimodal Sensing and Analytics at Scale: Algorithms and Applications
协作研究:大规模多模态传感和分析:算法和应用
- 批准号:
1807660 - 财政年份:2018
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Robust and Scalable Volume Minimization-based Matrix Factorization for Sensing and Clustering
用于传感和聚类的鲁棒且可扩展的基于体积最小化的矩阵分解
- 批准号:
1608961 - 财政年份:2016
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
CIF: Small: Feasible Point Pursuit for Non-convex QCQPs: Algorithms and Signal Processing Applications
CIF:小:非凸 QCQP 的可行点追踪:算法和信号处理应用
- 批准号:
1525194 - 财政年份:2015
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Workshop on Big Data: From Signal Processing to Systems Engineering; to be held at Arlington Virginia, March 21-22, 2013.
大数据研讨会:从信号处理到系统工程;
- 批准号:
1327148 - 财政年份:2013
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
BIGDATA: Mid-Scale: DA: Collaborative Research: Big Tensor Mining: Theory, Scalable Algorithms and Applications
BIGDATA:中型:DA:协作研究:大张量挖掘:理论、可扩展算法和应用
- 批准号:
1247632 - 财政年份:2012
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Wideband cognitive sensing from a few bits
来自几个比特的宽带认知感知
- 批准号:
1231504 - 财政年份:2012
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Spectral Tweets: A Community Paradigm for Spatio-temporal Cognitive Sensing and Access
频谱推文:时空认知感知和访问的社区范式
- 批准号:
1247885 - 财政年份:2012
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
From Medium Access to Physical Layer: An Integrated DSP Framework for Wireless Packet Networks
从介质访问到物理层:无线分组网络的集成 DSP 框架
- 批准号:
0096164 - 财政年份:2000
- 资助金额:
$ 45.67万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
- 批准号:
2312089 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
- 批准号:
2342833 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
- 批准号:
2343062 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
- 批准号:
2403559 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
オミックス解析を用いたブドウ球菌 small colony variants の包括的特徴づけ
使用组学分析全面表征葡萄球菌小菌落变体
- 批准号:
24K13443 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
- 批准号:
2329908 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
- 批准号:
2331111 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331302 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331301 - 财政年份:2024
- 资助金额:
$ 45.67万 - 项目类别:
Standard Grant