CIF: Small: Community Detection Meets Non-Graph Data: Principles and Applications

社区检测是指通过观察表示节点之间关系的图，对图的聚类进行推断和识别。基于观察其成对关系的节点聚类是机器学习中的一个核心问题，并且具有广泛且不断增加的应用，从生物学到犯罪学，社交网络，政治，链接预测和广告。图结构在表述和解决推理问题中的效用是网络推理和社区检测成功和普及的主要驱动力。然而，在几乎所有涉及图的实际应用中，也存在与推理任务相关的非图数据。例如，社交网络可以访问单个属性和变量以及连接属性。这些非图数据可能不能很好地适应现有的图推理框架，因此没有得到广泛的应用。该项目致力于在非图数据存在的情况下发展图推理领域。图推理可以从有效地结合可用的非图数据中获益。例如，非图数据，也称为侧信息，可以用来减少社区检测算法的残差，提高其性能。副信息还可以减少局部信念传播算法与标签恢复的信息论极限之间的计算差距，扩展了信念传播可以发挥良好效果的制度集。本项目分析了带有侧信息的标签恢复的信息极限，并探讨了侧信息如何影响高效的局部算法（如信念传播）以及其他高效算法（如半确定规划）的极限。该项目还包括一个涉及真实世界数据集实验的计算组件。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Community detection refers to the inference and identification of clusters of a graph based on observation of a graph representing relationships between the nodes. The clustering of the nodes based on observing their pairwise relationship is a central problem in machine learning, and has a wide and increasing set of applications, from biology to criminology, social networks, politics, link prediction, and advertising. The utility of the graph structure in formulating and solving inference problems is a main driver of the success and popularity of network inference and community detection. Still, in almost every practical application involving graphs, there also exist non-graph data that are relevant to the inference task. For example, social networks have access to individual attributes and variables as well as connective attributes. These non-graph data may not fit neatly into the existing graph inference frameworks, and therefore have not been widely utilized therein. This project is dedicated to the development of the field of graph inference in the presence of non-graph data. Graph inference can benefit in various ways from the efficient incorporation of available non-graph data. For example, non-graph data, also known as side information, can be utilized to reduce the residual error of community detection algorithms and improve their performance. Side information can also reduce the computation gap between local belief propagation algorithms and information-theoretic limits of label recovery, extending the set of regimes under which belief propagation can be used to good effect. This project analyzes the information limits of label recovery with side information, and explores how side information affects the limits of efficient local algorithms such as belief propagation, as well as other efficient algorithms such as semi-definite programming. The project also includes a computational component involving experiments on real-world data sets.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.