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）在年度Allerton通信，控制和计算会议上，研究生的职业和生活技能指导；（c）指导女性和少数族裔学生研究。该研究分为四个相互关联的领域，从单个图的推理问题到涉及两个图的推理，以便研究一般家庭的图形分类：（a）学习社区结构在动态图中的学习界结构，具有重型尾巴分配，尤其是重型范围的barabasi-allabasi-eactential prefental eactentials prefential prefental prefental prefential prefential prefential prefential prefential prefential prefential prefential prefentials prefentials prefental alberbert offient alberberbert; （b）恢复社区以外的图形结构，包括但不限于在遗传测序问题和在粒子跟踪问题中产生的两分图中产生的隐藏的哈密顿周期的恢复；（c）通过识别顶点对应关系，尤其是匹配ERDOS-RENYI随机图和Barabasi-Albert优先附件图的扰动版本的匹配，将两个图相匹配；（d）使用采样的图形学习属性，包括沿图上的随机步行进行采样。设计了估计局部结构数量（例如边缘和三角形）和全局结构的计算有效算法。网络动力学和子采样以及不一定低等级或静态的网络结构的推理，可以通过采用从信息理论，信息传播，光谱和非凸方法的技术以及凸的方法以及线性，四次，典型和半定义的奖励来通过评估NSF的宣传奖，以表现出nsf的宣传，以表现出nsf的宣传，以表现出nsf的范围，以表现出nsf的范围，以表现出nsf的范围。和更广泛的影响审查标准。