Robust and scalable algorithms for learning hidden structures in sparse network data with the aid of side information

University Of Southern California, Los Angeles CA

Investigators

Abstract

Network data is becoming increasingly relevant in various areas, including social sciences, biology, computer science, and engineering. In the social sciences, network data is used to study social interactions and relationships, such as friendship networks, political affiliations, and knowledge transfer networks. In biology, network data is used to model and analyze biological systems, such as gene regulation networks, protein-protein interaction networks, and food webs. Learning the hidden structures within networks, in particular detecting and modeling community structures, is of paramount importance. This process not only enhances the interpretability of data but also enables data compression, manages data heterogeneity by detecting latent subpopulations and fitting appropriate models to each, and addresses the issue of missing labels. Despite a plethora of clustering algorithms, current approaches often suffer from scalability and robustness issues, limiting their effectiveness in real-world applications. Furthermore, as data sharing becomes more prevalent, there is often a wealth of contextual information available about the nodes in a network, such as demographic information or browsing history for users on an online platform, that can be effectively combined with network data to greatly enhance the effectiveness of clustering procedures. To tackle these limitations and advance the field, this project will develop robust and scalable inferential network methods, which adapt to the heterogeneity of node degrees and allows to combine nodewise side information with pairwise interaction data for a more effective analysis. This project will support education in statistical and machine learning research by providing training opportunities for graduate students, from diverse backgrounds, to participate in cutting-edge research. It also benefits society by providing tools for understanding and managing complex network systems. This research consists of three interrelated parts, which work in concert to provide a unifying framework for learning latent structures in sparse network data. In the first part, we devise clustering algorithms based on semidefinite programming which allows us to combine the high-dimensional contextual information on the nodes with the interaction graph. In the second part, we will develop methods to improve the robustness of the inferential algorithms to adversarial perturbations in the nodewise contextual data or the interaction graph. The third part builds on the algorithms devised in the previous two parts and provides low-computation and memory-efficient implementation of these algorithms that can scale to large-scale network data. In addition, the project will investigate the potential uses of this project across diverse domains, utilizing the resulting clustering algorithms and optimization-statistical tools. 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.