Spectral methods for single and multiple graph inference

用于单图和多图推理的谱方法

• 批准号: 2210805
• 负责人: Minh Tang
• 金额: $ 15万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2210805&HistoricalAwards=false
• 关键词: Spectral; methods; single; multiple; graph

Networks provide an elegant and natural representation for describing a collection of entities and their interactions. Network data appear prominently in many scientific domains such as ecology (food webs), sociology (social networks), biology (protein-protein interactions), telecommunications, and cybersecurity (cellular and computer networks). This project addresses two important inference problems in network science. The first is to quantify the similarities between a collection of networks for the purpose of classifying a network into categories such as being typical or anomalous. The second is dimension reduction for large and complex networks; this is essential in the development of memory and computationally efficient algorithms for analyzing network data. The investigator will complement theoretical and methodological investigations by developing open-source software packages for network analysis, and mentoring graduate students in statistics and data science.The research program has three main aims. The first is to study efficient parameters estimation for latent position graphs. Given a latent position graph, the investigator will derive both uniform error bounds and normal approximations for its estimated latent positions. The second aim is to develop valid and robust two-sample testing procedures for latent position graphs with a particular emphasis on the setting where the link function is an unknown radial function. Combining these two aims allows practitioners to compare graphs while ignoring irrelevant features such as difference in edge densities or nodes relabeling in real data. The third aim is to conduct perturbation analysis of randomized singular value decomposition (RSVD) when used for dimension reduction of large, noisy graphs. Viewing the observed adjacency matrix as arising from a general “signal-plus-noise” framework, the investigator will derive upper bounds for the spectral and two-to-infinity-norm distances between the approximate singular vectors of the observed matrix and the true singular vectors of the signal matrix. These upper bounds will depend on the signal-to-noise ratio and the number of power iterations. Finally, as part of this third aim the investigator will also derive uniform entrywise approximation for recovery of a low-rank signal matrix using RSVD. Results established under this third aim can be applied to general matrix-valued data beyond graphs.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.

网络提供了一种优雅而自然的表示，用于描述实体的集合及其交互。网络数据在许多科学领域都很突出，如生态学（食物网）、社会学（社交网络）、生物学（蛋白质-蛋白质相互作用）、电信和网络安全（蜂窝和计算机网络）。 这个项目解决了网络科学中两个重要的推理问题。第一种是量化网络集合之间的相似性，以便将网络分类为典型或异常等类别。第二是大型复杂网络的降维;这对于开发用于分析网络数据的内存和计算效率算法至关重要。研究人员将通过开发用于网络分析的开源软件包来补充理论和方法研究，并指导统计和数据科学的研究生。该研究计划有三个主要目标。一是研究隐位置图的有效参数估计问题。给定一个潜在位置图，研究者将推导出其估计的潜在位置的统一误差界和正常近似。第二个目标是开发有效的和强大的双样本测试程序的潜在的位置图，特别强调的设置链接函数是一个未知的径向函数。结合这两个目标允许从业者比较图形，而忽略不相关的功能，如边缘密度或节点重新标记的差异在真实的数据。第三个目标是进行随机奇异值分解（RSVD）的扰动分析时，用于大，噪声图的维数降低。观察到的邻接矩阵所产生的一般的“信号加噪声”的框架，调查员将推导出的频谱和两个无穷大范数之间的距离的上限近似奇异向量的观察矩阵和真正的奇异向量的信号矩阵。这些上限将取决于信噪比和幂迭代的次数。最后，作为第三个目标的一部分，研究人员还将使用RSVD导出用于恢复低秩信号矩阵的均匀入口近似。在第三个目标下建立的结果可以应用于图形之外的一般矩阵值数据。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。