CIF: Medium: Collaborative Research: Learning in Networks: Performance Limits and Algorithms

CIF：媒介：协作研究：网络学习：性能限制和算法

• 批准号: 1856424
• 负责人: Jiaming Xu
• 金额: $ 43.54万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1856424&HistoricalAwards=false
• 关键词: CIF; Medium; Collaborative; Research; Learning

Many machine learning problems deal with networks that encode similarities or relationships among different objects, for which observational data may be limited in extent and noisy. Learning the desired information requires highly efficient algorithms that can process large-scale network data and detect tenuous statistical signatures. This project involves modeling large-scale networks and observations, devising learning algorithms, analyzing the performance of the algorithms, deriving bounds on the possible performance of best algorithms, and deploying theoretically-grounded algorithms to real network data. The research aims to significantly advance the theoretical and algorithmic understanding of graphical inference and provide key enabling technologies for high-impact applications such as ordering of short DNA sub-sequences for genetic sequencing. Improvements in the ability to sequence DNA can accelerate the use of genomics with applications in health care. The associated mechanisms for broadening participation in computing include: (a) Explorations in computing and statistics for K-12 with broad participation; (b) Career and life skills guidance for graduate students at the Annual Allerton Conference on Communications, Control, and Computing; and (c) Mentoring female and minority students in research.The research is grouped into four interrelated areas, ranging from inference problems for single graphs, to inference involving two graphs, in order to study classification of graphs from general families: (a) learning community structure in dynamic graphs with heavy-tailed degree distribution, specifically, in a new variation of the Barabasi-Albert preferential attachment model; (b) recovering graphical structures beyond communities, including but not limited to recovery of hidden Hamiltonian cycles arising in a genetic sequencing problem and hidden matchings in bipartite graphs arising in a particle tracking problem; (c) matching two graphs to each other by identifying vertex correspondences, in particular, matching of perturbed versions of Erdos-Renyi random graphs and Barabasi-Albert preferential attachment graphs; and (d) learning properties of graphs using sampling, including sampling along random walks on graphs. Computationally efficient algorithms that estimate the number of both local structures (e.g., edges and triangles) and global structures are designed. Network dynamics and subsampling, as well as inference of network structures that are not necessarily low rank or static, are addressed by employing techniques ranging from information theory, message passing, spectral and non-convex methods, and convex methods including linear, quadratic, and semi-definite relaxations.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.

许多机器学习问题处理编码不同对象之间的相似性或关系的网络，对于这些网络，观测数据可能在范围上有限且有噪声。学习所需的信息需要高效的算法，这些算法可以处理大规模的网络数据并检测细微的统计特征。该项目涉及大规模网络建模和观察，设计学习算法，分析算法的性能，推导最佳算法的可能性能界限，并将基于理论的算法部署到实际网络数据中。该研究旨在显著推进图形推理的理论和算法理解，并为高影响应用提供关键的使能技术，如基因测序的短DNA亚序列排序。DNA测序能力的提高可以加速基因组学在医疗保健中的应用。扩大参与计算的相关机制包括：(a)广泛参与的K-12的计算和统计探索；(b)在阿勒顿通信、控制和计算年度会议上为研究生提供职业和生活技能指导；(c)指导女性和少数民族学生进行研究。从单图的推理问题到双图的推理问题，本研究分为四个相互关联的领域，以研究一般族图的分类：(a)学习具有重尾度分布的动态图的社区结构，特别是在Barabasi-Albert优先依恋模型的新变体中；(b)恢复超越群落的图形结构，包括但不限于恢复基因测序问题中产生的隐藏哈密顿循环和粒子跟踪问题中产生的二部图中的隐藏匹配；(c)通过识别顶点对应来匹配两个图，特别是Erdos-Renyi随机图和Barabasi-Albert优先连接图的扰动版本的匹配；(d)使用抽样学习图的性质，包括沿图上的随机行走进行抽样。设计了计算效率高的算法来估计局部结构（如边和三角形）和全局结构的数量。网络动力学和子采样，以及不一定是低秩或静态的网络结构的推断，通过采用信息论、消息传递、谱和非凸方法以及包括线性、二次和半定松弛在内的凸方法等技术来解决。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

The planted matching problem: sharp threshold and infinite-order phase transition

种植匹配问题：尖锐阈值和无限阶相变

• DOI: 10.1007/s00440-023-01208-6
• 发表时间: 2023
• 期刊: Probability Theory and Related Fields
• 影响因子: 2
• 作者: Ding, Jian;Wu, Yihong;Xu, Jiaming;Yang, Dana
• 通讯作者: Yang, Dana

The Power of D-hops in Matching Power-Law Graphs

• DOI: 10.1145/3460094
• 发表时间: 2021-02
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: LIREN YU;Jiaming Xu;Xiaojun Lin

Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis

• DOI: 10.1007/s10208-022-09570-y
• 发表时间: 2022-06
• 期刊: Foundations of Computational Mathematics
• 影响因子: 3
• 作者: Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu

Consistent recovery threshold of hidden nearest neighbor graphs

隐藏最近邻图的一致恢复阈值

• DOI: 10.1109/tit.2021.3085773
• 发表时间: 2021
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Ding, Jian;Wu, Yihong;Xu, Jiaming;Yang, Dana
• 通讯作者: Yang, Dana

Random Graph Matching at Otter’s Threshold via Counting Chandeliers

通过计数枝形吊灯在水獭阈值上进行随机图匹配

• 发表时间: 2023
• 期刊: Proceedings of the annual ACM Symposium on Theory of Computing
• 作者: Mao, Cheng;Wu, Yihong;Xu, Jiaming;Yu, Sophie H.
• 通讯作者: Yu, Sophie H.