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

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

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.