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

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

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.