Spectral methods for single and multiple graph inference

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

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.