光谱嵌入是可用于获得图形节点的矢量表示的过程。本文提出了称为随机点产品图的潜在网络模型的概括，以允许将这些载体表示的解释为潜在位置估计。需要泛化异化连接（例如，“对立面”）并更普遍地应对负特征值。我们表明，是否使用邻接或归一化的拉普拉斯矩阵，光谱嵌入产生均匀一致的潜在估计，渐近高斯误差（最高可识别性）。标准和混合会员随机块模型是特殊情况，其中潜在的位置只需要k $不同的向量值，代表社区，或以$（k-1）$ - simplex与那些顶点一起生活。在随机块模型下，我们的理论建议使用高斯混合模型（而不是$ k $ -means），并且根据混合成员资格，拟合封闭单纯x的最小卷，此前仅在非负面明确假设下支持的现有建议。在网络安全示例中，在网络安全示例中证明了链路预测（在随机点产品图中）的经验改进（在随机点产品图中），以及露出更丰富的潜在结构（比标准或混合隶属块模型的位置）。

光谱嵌入基于其邻接或拉普拉斯矩阵的特征向量的网络节点的矢量表示，并在整个科学中找到了应用程序。许多这样的网络是多部分的，这意味着它们的节点可以分为组，并且同一组的节点永远不会连接。当网络是多部分时，本文证明了通过光谱嵌入获得的节点表示，生存的较高维度环境空间的群体特异性低维子空间附近。因此，我们提出了光谱嵌入后的后续步骤，以在其内在的而不是环境维度中恢复节点表示形式，从而证明在低级别的，不均匀的随机图模型下均匀的一致性。我们的方法自然概括了两分光谱嵌入，其中通过双jaCencency或Bi-Laplacian矩阵的奇异值分解获得了节点表示。

网络邻接矩阵的光谱嵌入通常产生大约围绕低维子纤维结构的节点表示。特别地，当从潜在位置模型产生图表时，期望隐藏的子结构出现。此外，网络内的社区存在可能在嵌入中生成特定的特定社区的子多种结构，但是在网络的大多数统计模型中，这不明确地解释。在本文中，提出了一类称为潜在结构块模型（LSBM）的模型来解决这种情况，允许在存在社区特定的一维歧管结构时允许图形聚类。 LSBMS专注于特定的潜伏空间模型，随机点产品图（RDPG），并为每个社区的潜在位置分配潜在的子多种。讨论了来自LSBMS引起的嵌入式的贝叶斯模型，并显示在模拟和现实世界网络数据上具有良好的性能。该模型能够正确地恢复生活在一维歧管中的底层社区，即使当底层曲线的参数形式未知，也可以在各种实际数据上实现显着的结果。

我们通过证明PABM是GRDPG的一种特殊情况，其中社区对应于潜在矢量的相互正交子空间，我们连接两个随机图模型，即受欢迎程度调整块模型（PABM）和广义随机点产品图（GRDPG）。这种见解使我们能够为PABM构建用于社区检测和参数估计的新算法，并改善了依赖稀疏子空间聚类的现有算法。利用邻接光谱嵌入GRDPG的渐近特性，我们得出了这些算法的渐近特性。特别是，我们证明，随着图形顶点的数量倾向于无穷大，社区检测误差的绝对数量趋于零。仿真实验说明了这些特性。

给定图形或相似性矩阵，我们考虑了恢复节点之间真实距离的概念以及它们的真实位置的问题。我们证明这可以通过两个步骤完成：矩阵分解，然后进行非线性尺寸降低。这种组合之所以有效，是因为在第一步中获得的点云一直生活在歧管上，其中潜在距离被编码为地球距离。因此，一个非线性降低尺寸的工具，即近似地球距离，可以恢复潜在位置，直至简单的转换。我们详细说明了使用光谱嵌入，其次是ISOMAP的情况，并为其他技术组合提供了令人鼓舞的实验证据。

最近有一项激烈的活动在嵌入非常高维和非线性数据结构的嵌入中，其中大部分在数据科学和机器学习文献中。我们分四部分调查这项活动。在第一部分中，我们涵盖了非线性方法，例如主曲线，多维缩放，局部线性方法，ISOMAP，基于图形的方法和扩散映射，基于内核的方法和随机投影。第二部分与拓扑嵌入方法有关，特别是将拓扑特性映射到持久图和映射器算法中。具有巨大增长的另一种类型的数据集是非常高维网络数据。第三部分中考虑的任务是如何将此类数据嵌入中等维度的向量空间中，以使数据适合传统技术，例如群集和分类技术。可以说，这是算法机器学习方法与统计建模（所谓的随机块建模）之间的对比度。在论文中，我们讨论了两种方法的利弊。调查的最后一部分涉及嵌入$ \ mathbb {r}^ 2 $，即可视化中。提出了三种方法：基于第一部分，第二和第三部分中的方法，$ t $ -sne，UMAP和大节。在两个模拟数据集上进行了说明和比较。一个由嘈杂的ranunculoid曲线组成的三胞胎，另一个由随机块模型和两种类型的节点产生的复杂性的网络组成。

A common approach to modeling networks assigns each node to a position on a low-dimensional manifold where distance is inversely proportional to connection likelihood. More positive manifold curvature encourages more and tighter communities; negative curvature induces repulsion. We consistently estimate manifold type, dimension, and curvature from simply connected, complete Riemannian manifolds of constant curvature. We represent the graph as a noisy distance matrix based on the ties between cliques, then develop hypothesis tests to determine whether the observed distances could plausibly be embedded isometrically in each of the candidate geometries. We apply our approach to data-sets from economics and neuroscience.

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency.

随机点产品图（RDPG）是网络的生成模型，其中顶点对应于潜像欧几里德空间中的位置，并且由潜在位置的点产品确定。我们考虑从潜在空间的未知$ 1 $ 1多维二维子段中随机采样潜在位置的RDPG。原则上，限制推理，即利用子苗条结构的程序，应该比不受限制的推断更有效;然而，当子苗条未知时，尚不清楚如何进行限制推理。我们提出了用于歧管学习的技术可用于学习空气的未知子多种，以实现从受限推断的益处。为了说明，我们使用完整的一组顶点来测试1美元的FR \'{e} CHET手段的1美元 - 和2美元的假设，以推断潜伏结构。我们建议测试统计数据，用于使用从估计的潜在位置构造的邻域图上的最短路径距离来部署ISOMAP过程，以估计未知$ 1 $ -dimenmanifold上的弧长。与ISOMAP的常规应用不同，估计的潜在位置不介绍感兴趣的子群。我们将现有的收敛结果扩展到ISOMAP到此设置，并使用它们来证明，随着辅助顶点的数量增加，我们的测试的功率会收敛于当已知子纤维的相应测试的功率。最后，我们将方法应用于推理问题，这是在研究果蝇幼虫蘑菇体的结核时。单变量学习歧管测试拒绝（$ P <0.05 $），而多变量环境空间测试没有（$ p \ gg0.05 $），说明了识别和利用后续推断的低维结构的值。

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

我们提出了对学度校正随机块模型（DCSBM）的合适性测试。该测试基于调整后的卡方统计量，用于测量$ n $多项式分布的组之间的平等性，该分布具有$ d_1，\ dots，d_n $观测值。在网络模型的背景下，多项式的数量（$ n $）的数量比观测值数量（$ d_i $）快得多，与节点$ i $的度相对应，因此设置偏离了经典的渐近学。我们表明，只要$ \ {d_i \} $的谐波平均值生长到无穷大，就可以使统计量在NULL下分配。顺序应用时，该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作，因此在学位上有条件，因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法，即在测试$ K $社区时根据$（k+1）$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量，我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案，因此其效用超出了顺序测试，可用于同时测试DCSBM家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

随着图形数据变得越来越普遍，在这些复杂的数据域中进行可靠的推论图算法的需求至关重要。在许多感兴趣的情况下，存在对抗数据污染的情况更加复杂。对手的效果通常是以负面影响统计和算法性能的方式改变数据分布。我们在顶点提名的背景下研究这种现象，这是网络数据的半监督信息检索任务。在这里，一系列常见的方法依赖于光谱图嵌入，这些嵌入式既可以提供良好的算法性能和灵活的设置，在该设置中可以实现正则化技术以帮助减轻对手的效果。许多当前的正则化方法依赖于直接网络修剪来有效消除对抗性污染，尽管这种直接修剪通常会导致所得图中的复杂依赖性结构。我们提出了一种在模型空间中运行的新修剪方法，该方法可以解决块结构污染和白噪声污染（污染的分布未知）。与直接修剪相比，该模型修剪更适合理论分析，同时也证明了许多模拟的性能。

光谱聚类是网络中广泛使用的社区检测方法之一。然而，大型网络为其中的特征值分解带来了计算挑战。在本文中，我们研究了从统计角度使用随机草图算法的光谱聚类，在那里我们通常假设网络数据是从随机块模型生成的，这些模型不一定是完整等级的。为此，我们首先使用最近开发的草图算法来获得两个随机谱聚类算法，即基于随机投影和基于随机采样的光谱聚类。然后，我们在群体邻接矩阵的近似误差，错误分类误差和链路概率矩阵的估计误差方面研究得到的算法的理论界限。事实证明，在温和条件下，随机谱聚类算法导致与原始光谱聚类算法相同的理论界。我们还将结果扩展到校正的程度校正的随机块模型。数值实验支持我们的理论发现并显示随机化方法的效率。一个名为rclusct的新R包是开发的，并提供给公众。

光谱方法通过图矩阵上的特征向量计算在图中提供了一个可拖动的全局框架。 HyperGraph数据（其中实体在任意大小的边缘上相互作用）对矩阵表示构成了挑战，因此对光谱聚类构成了挑战。我们研究了基于超透明型非背带操作员的非均匀超图的光谱聚类。在审查了该操作员及其基本属性的定义之后，我们证明了Ihara-Bass类型的定理，该定理允许在较小的矩阵上进行特征Pair计算，通常可以更快地计算。然后，我们通过线性化信念传播提出了一种交替的算法，用于在超图随机块模型中推断，该算法涉及光谱聚类的步骤，再次使用非背部跟踪操作员。我们提供与该算法相关的证明，这些算法既正式又扩展了几个先前的结果。我们对光谱方法的极限和超图随机块模型中的可检测性提出了几种猜想，并通过对我们研究的操作员的特征因的不接受分析来支持它们。我们在真实和合成数据中执行实验，这些实验证明了当不同尺寸的相互作用带有有关群集结构的不同信息时，超图方法比基于图的方法的好处。

随机奇异值分解（RSVD）是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $，原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数，$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中，我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性，即，观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $（频谱规范）和$ \ ell_ {2 \ to \ infty} $（最大行行列$ \ ell_2 $ norm）$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比（SNR）和功率迭代$ g $的数量。观察到一个相变现象，其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明，每当噪声矩阵满足一定的痕量生长条件时，这些相变发生的$ g $的阈值都会很清晰。最后，我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

网络数据通常在各种应用程序中收集，代表感兴趣的功能之间直接测量或统计上推断的连接。在越来越多的域中，这些网络会随着时间的流逝而收集，例如不同日子或多个主题之间的社交媒体平台用户之间的交互，例如在大脑连接性的多主体研究中。在分析多个大型网络时，降低降低技术通常用于将网络嵌入更易于处理的低维空间中。为此，我们通过专门的张量分解来开发用于网络集合的主组件分析（PCA）的框架，我们将半对称性张量PCA或SS-TPCA术语。我们得出计算有效的算法来计算我们提出的SS-TPCA分解，并在标准的低级别信号加噪声模型下建立方法的统计效率。值得注意的是，我们表明SS-TPCA具有与经典矩阵PCA相同的估计精度，并且与网络中顶点数的平方根成正比，而不是预期的边缘数。我们的框架继承了古典PCA的许多优势，适用于广泛的无监督学习任务，包括识别主要网络，隔离有意义的更改点或外出观察，以及表征最不同边缘的“可变性网络”。最后，我们证明了我们的提案对模拟数据的有效性以及经验法律研究的示例。用于建立我们主要一致性结果的技术令人惊讶地简单明了，可能会在其他各种网络分析问题中找到使用。

这项调查旨在提供线性模型及其背后的理论的介绍。我们的目标是对读者进行严格的介绍，并事先接触普通最小二乘。在机器学习中，输出通常是输入的非线性函数。深度学习甚至旨在找到需要大量计算的许多层的非线性依赖性。但是，这些算法中的大多数都基于简单的线性模型。然后，我们从不同视图中描述线性模型，并找到模型背后的属性和理论。线性模型是回归问题中的主要技术，其主要工具是最小平方近似，可最大程度地减少平方误差之和。当我们有兴趣找到回归函数时，这是一个自然的选择，该回归函数可以最大程度地减少相应的预期平方误差。这项调查主要是目的的摘要，即线性模型背后的重要理论的重要性，例如分布理论，最小方差估计器。我们首先从三种不同的角度描述了普通的最小二乘，我们会以随机噪声和高斯噪声干扰模型。通过高斯噪声，该模型产生了可能性，因此我们引入了最大似然估计器。它还通过这种高斯干扰发展了一些分布理论。最小二乘的分布理论将帮助我们回答各种问题并引入相关应用。然后，我们证明最小二乘是均值误差的最佳无偏线性模型，最重要的是，它实际上接近了理论上的极限。我们最终以贝叶斯方法及以后的线性模型结束。

马尔可夫链是一类概率模型，在定量科学中已广泛应用。这部分是由于它们的多功能性，但是可以通过分析探测的便利性使其更加复杂。本教程为马尔可夫连锁店提供了深入的介绍，并探索了它们与图形和随机步行的联系。我们利用从线性代数和图形论的工具来描述不同类型的马尔可夫链的过渡矩阵，特别着眼于探索与这些矩阵相对应的特征值和特征向量的属性。提出的结果与机器学习和数据挖掘中的许多方法有关，我们在各个阶段描述了这些方法。本文并没有本身就成为一项新颖的学术研究，而是提出了一些已知结果的集合以及一些新概念。此外，该教程的重点是向读者提供直觉，而不是正式的理解，并且仅假定对线性代数和概率理论的概念的基本曝光。因此，来自各种学科的学生和研究人员可以访问它。