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

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.

我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲，我们的结果表明，随机块模型没有稳健性。我们的工作受到最近的银行，Mohanty和Raghavendra（SODA 2021）的工作，为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观：种植的分区可能远非最佳意义，即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知，我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化（与平方和不同的不同），这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术，其提高了任意强大的弱恢复算法的成功（输入的随机性）从恒定（或缓慢消失）概率以指数高概率。

在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法，该算法可以忍受$ \ epsilon $ - 损坏和达到错误$ o（\ epsilon） + e^{ - \ frac {c} {2} {2}（1 \ pm o（1））} $其中$ c =（\ sqrt {a} - \ sqrt {b}）^2 $是信噪比，$ a/n $和$ b/n $是互发和intra-intra-intra-社区连接概率分别。这些界限基本上与无损坏的SBM的最小值相匹配。我们还为$ \ mathbb {z} _2 $ -Synchronization提供了可靠的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限制的单调变化混合在一起，从半随机模型中。

Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficient conditions under which this testing is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We then conjecture that graph alignment is not feasible in polynomial time when the associated tree detection problem is impossible. If true, this conjecture together with our sufficient conditions on tree detection impossibility would imply the existence of a hard phase for graph alignment, i.e. a parameter range where alignment cannot be done in polynomial time even though it is known to be feasible in non-polynomial time.

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

高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构（例如低级别矩阵）。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型：在各种情况下，数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量，以检测隐藏结构的存在。在这项工作中，我们将这些方法扩展到解决估计和恢复问题（而不是检测）。对于大量的“信号加噪声”问题，我们给出了一个用户友好的下限，以获得最佳的均衡误差。据我们所知，这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用，我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征，在两种情况下都解决了有关恢复的计算复杂性的开放问题（在低度框架中）。

假设$ g $是根据所谓的HyperGraph随机块模型（HSBM）产生的，我们考虑了稀疏$ Q $均匀的HyperGraph $ G $中的社区检测问题。我们证明，基于非折线操作员的光谱方法具有很高的概率，可以降低到Angelini等人猜想的广义kesten-Stigum检测阈值。我们表征了稀疏HSBM的非背带操作员的频谱，并使用Ihara-Bass公式为超图提供有效的尺寸降低程序。结果，可以将稀疏HSBM的社区检测减少为$ 2N \ times 2n $非正态矩阵的特征向量问题，该矩阵从邻接矩阵和超级格雷普的学位矩阵中构建。据我们所知，这是第一种可证明，有效的光谱算法，它可以根据一般对称概率张量生成$ K $块的HSBMS阈值。

社区检测是网络科学中最重要的方法领域之一，在过去的几十年里引起了大量关注的方法之一。该区域处理网络的自动部门到基础构建块中，目的是提供其大规模结构的概要。尽管它的重要性和广泛的采用普及，所谓的最先进和实际在各种领域实际使用的方法之间存在明显的差距。在这里，我们试图通过根据是否具有“描述性”或“推论”目标来划分现有方法来解决这种差异。虽然描述性方法在基于社区结构的直观概念的网络中找到模式的模式，但是推理方法阐述了精确的生成模型，并尝试将其符合数据。通过这种方式，他们能够为网络形成机制提供见解，并以统计证据支持的方式与随机性的单独结构。我们审查如何使用推论目标采用描述性方法被陷入困境和误导性答案，因此应该一般而言。我们认为推理方法更通常与更清晰的科学问题一致，产生更强大的结果，并且应该是一般的首选。我们试图消除一些神话和半真半假在实践中使用社区检测时，努力改善这些方法的使用以及对结果的解释。

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.

聚类是无监督学习中的基本原始，它引发了丰富的计算挑战性推理任务。在这项工作中，我们专注于将$ D $ -dimential高斯混合的规范任务与未知（和可能的退化）协方差集成。最近的作品（Ghosh等人。恢复在高斯聚类实例中种植的某些隐藏结构。在许多类似的推理任务上的工作开始，这些较低界限强烈建议存在群集的固有统计到计算间隙，即群集任务是\ yringit {statistically}可能但没有\ texit {多项式 - 时间}算法成功。我们考虑的聚类任务的一个特殊情况相当于在否则随机子空间中找到种植的超立体载体的问题。我们表明，也许令人惊讶的是，这种特定的聚类模型\ extent {没有展示}统计到计算间隙，即使在这种情况下继续应用上述的低度和SOS下限。为此，我们提供了一种基于Lenstra - Lenstra - Lovasz晶格基础减少方法的多项式算法，该方法实现了$ D + 1 $样本的统计上最佳的样本复杂性。该结果扩展了猜想统计到计算间隙的问题的类问题可以通过“脆弱”多项式算法“关闭”，突出显示噪声在统计到计算间隙的发作中的关键而微妙作用。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

随机奇异值分解（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的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

我们研究了小组测试问题，其目标是根据合并测试的结果，确定一组k感染的人，这些k含有稀有疾病，这些人在经过测试中至少有一个受感染的个体时返回阳性的结果。团体。我们考虑将个人分配给测试的两个不同的简单随机过程：恒定柱设计和伯努利设计。我们的第一组结果涉及基本统计限制。对于恒定柱设计，我们给出了一个新的信息理论下限，这意味着正确识别的感染者的比例在测试数量越过特定阈值时会经历急剧的“全或全或无所不包”的相变。对于Bernoulli设计，我们确定解决相关检测问题所需的确切测试数量（目的是区分小组测试实例和纯噪声），改善Truong，Aldridge和Scarlett的上限和下限（2020）。对于两个小组测试模型，我们还研究了计算有效（多项式时间）推理程序的能力。我们确定了解决检测问题的低度多项式算法所需的精确测试数量。这为在少量稀疏度的检测和恢复问题中都存在固有的计算统计差距提供了证据。值得注意的是，我们的证据与Iliopoulos和Zadik（2021）相反，后者预测了Bernoulli设计中没有计算统计差距。

Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.

本文研究了一般D-均匀的HyperGraph随机块模型（D-HSBM）中精确恢复的基本限制，其中n个节点被分配到具有相对大小的k差异群落中（p1，...，pk）。具有基数d的节点的每个子集都是独立生成的，作为订单-D超边，其一定概率取决于D节点所属的地面真相群落。目标是根据观察到的超图准确地恢复K隐藏的社区。我们表明存在一个尖锐的阈值，因此可以在阈值之上实现精确的恢复，而不可能在阈值以下（除了将精确指定的小参数制度之外）。该阈值是根据我们称为社区之间普遍的Chernoff-Hellinger分歧的数量来表示的。我们对该通用模型的结果恢复了标准SBM和D-HSBM的先前结果，其中两个对称群落作为特殊情况。在证明我们的可实现结果的途径中，我们开发了一种符合阈值的多项式两阶段算法。第一阶段采用某种超图光谱聚类方法来获得社区的粗略估计，第二阶段通过局部细化步骤单独完善每个节点，以确保精确恢复。

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

我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个erd \ h {o} s-r \'enyi图$ \ mathcal {g}（n，q）$，其边缘通过潜在顶点通信相关联，我们表明该算法正确地匹配了所有范围的范围，除了所有的vertices分数外，有了很高的概率，前提是$ nq \ to \ infty $，而边缘相关系数$ \ rho $满足$ \ rho^2> \ alpha \ ailpha \大约0.338 $，其中$ \ alpha $是Otter的树木计数常数。此外，在理论上是必需的额外条件下，可以精确地匹配。这是第一个以显式常数相关性成功的多项式图匹配算法，并适用于稀疏和密集图。相比之下，以前的方法要么需要$ \ rho = 1-o（1）$，要么仅限于稀疏图。该算法的症结是一个经过精心策划的植根树的家族，称为吊灯，它可以有效地从同一树的计数中提取图形相关性，同时抑制不同树木之间的不良相关性。

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

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.