Spectral methods for single and multiple graph inference

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

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.