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

CIF：小型：社区检测遇到非图数据：原理与应用

基本信息

批准号：
2008684
负责人：
Aria Nosratinia
金额：
$ 44.94万
依托单位：
University of Texas at Dallas
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2024-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008684&HistoricalAwards=false
关键词：
CIF Small Community Detection Meets

项目摘要

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.

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