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

社区检测是指基于对表示节点之间关系的图的观察来推断和识别图的聚类。基于观察它们的成对关系的节点聚类是机器学习中的中心问题，并且具有广泛且不断增加的应用，从生物学到犯罪学、社交网络、政治、链接预测和广告。图结构在制定和解决推理问题中的效用是网络推理和社区检测成功和流行的主要驱动力。尽管如此，在几乎所有涉及图的实际应用中，也存在与推理任务相关的非图数据。例如，社交网络可以访问个体属性和变量以及连接属性。这些非图形数据可能不完全适合现有的图形推理框架，因此尚未在其中被广泛利用。该项目致力于在非图形数据存在的情况下开发图形推理领域。图推理可以以各种方式受益于有效地合并可用的非图数据。例如，非图数据，也称为边信息，可以用来减少社区检测算法的残留误差并提高其性能。边信息还可以减少本地置信传播算法和标签恢复的信息理论限制之间的计算间隙，扩展置信传播可以用于良好效果的制度集。该项目分析了带有边信息的标签恢复的信息限制，并探讨了边信息如何影响有效局部算法（如置信传播）以及其他有效算法（如半定规划）的限制。这个奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估的支持。

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.