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

借助辅助信息学习稀疏网络数据中隐藏结构的鲁棒且可扩展的算法

• 批准号: 2311024
• 负责人: Adel Javanmard
• 金额: $ 27.5万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-15 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2311024&HistoricalAwards=false
• 关键词: Robust; scalable; algorithms; learning; hidden

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.

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