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

网络数据在各个领域变得越来越重要，包括社会科学、生物学、计算机科学和工程学。在社会科学中，网络数据被用来研究社会互动和关系，如友谊网络、政治从属关系和知识转移网络。在生物学中，网络数据被用来建模和分析生物系统，如基因调控网络、蛋白质-蛋白质相互作用网络和食物网。学习网络中隐藏的结构，特别是检测和建模社区结构，是至关重要的。这一过程不仅提高了数据的可解释性，还实现了数据压缩，通过检测潜在子群体并为每个群体匹配合适的模型来管理数据异构性，并解决了标签缺失的问题。尽管有过多的集群算法，但当前的方法经常受到可伸缩性和健壮性问题的影响，限制了它们在现实世界应用程序中的有效性。此外，随着数据共享变得更加普遍，通常存在关于网络中的节点的丰富的上下文信息，例如在线平台上用户的人口统计信息或浏览历史，这些信息可以有效地与网络数据相结合，以极大地增强集群过程的有效性。为了解决这些限制并推动该领域的发展，该项目将开发健壮且可扩展的推理网络方法，该方法适应节点度的异质性，并允许将节点侧边信息与成对交互数据相结合，以实现更有效的分析。该项目将支持统计和机器学习研究方面的教育，为来自不同背景的研究生提供参与尖端研究的培训机会。这项研究由三个相互关联的部分组成，它们共同为学习稀疏网络数据中的潜在结构提供了一个统一的框架。在第一部分中，我们设计了基于半定规划的聚类算法，它允许我们将节点上的高维上下文信息与交互图结合起来。在第二部分中，我们将开发方法来提高推理算法对节点级上下文数据或交互图中的对抗性扰动的稳健性。第三部分建立在前两部分设计的算法的基础上，并提供了这些算法的低计算量和高内存效率的实现，这些算法可以扩展到大规模的网络数据。此外，该项目将利用由此产生的集群算法和优化统计工具，调查该项目在不同领域的潜在用途。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.