社区检测和正交组同步是科学和工程中各种重要应用的基本问题。在这项工作中，我们考虑了社区检测和正交组同步的联合问题，旨在恢复社区并同时执行同步。为此，我们提出了一种简单的算法，该算法由频谱分解步骤组成，然后是彼此枢转的QR分解（CPQR）。所提出的算法与数据点数线性有效且缩放。我们还利用最近开发的“休闲一淘汰”技术来建立近乎最佳保证，以确切地恢复集群成员资格，并稳定地恢复正交变换。数值实验证明了我们算法的效率和功效，并确认了我们的理论表征。

本文提出了一种以直接非凸起的方式解决社区检测和组同步问题的广义电力方法（GPM）。在随机组块模型（SGBM）下，理论分析表明该算法能够在$ O（n \ log ^ 2n）$ time中完全恢复地面真相，急剧优化了SEMIDEfinite编程（SDP）的基准方法O（n ^ {3.5}）$时间。此外，参数的下限作为精确恢复GPM的必要条件。新界违反了随机块模型（SBM）下纯社区检测的信息 - 理论阈值，从而展示了我们在连续执行两个任务的琐碎的两级方法上的同时优化算法的优越性。我们还对GPM和SDP进行了数值实验，以证据和补充我们的理论分析。

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

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

This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a reduced graph sketch constructed using random sampling. Then, the clusters of the full graph are inferred based on the clusters extracted from the sketch using a correlation-based retrieval step. Uniform random node sampling is shown to improve the computational complexity over clustering of the full graph when the cluster sizes are balanced. A new random degree-based node sampling algorithm is presented which significantly improves upon the performance of the clustering algorithm even when clusters are unbalanced. This framework improves the phase transitions for matrix-decomposition-based clustering with regard to computational complexity and minimum cluster size, which are shown to be nearly dimension-free in the low inter-cluster connectivity regime. A third sampling technique is shown to improve balance by randomly sampling nodes based on spatial distribution. We provide analysis and numerical results using a convex clustering algorithm based on matrix completion.

本文研究了聚类基质值观测值的计算和统计限制。我们提出了一个低级别的混合模型（LRMM），该模型适用于经典的高斯混合模型（GMM）来处理基质值观测值，该观测值假设人口中心矩阵的低级别。通过集成Lloyd算法和低级近似值设计了一种计算有效的聚类方法。一旦定位良好，该算法将快速收敛并达到最小值最佳的指数型聚类错误率。同时，我们表明一种基于张量的光谱方法可提供良好的初始聚类。与GMM相当，最小值最佳聚类错误率是由分离强度（即种群中心矩阵之间的最小距离）决定的。通过利用低级度，提出的算法对分离强度的要求较弱。但是，与GMM不同，LRMM的统计难度和计算难度的特征是信号强度，即最小的人口中心矩阵的非零奇异值。提供了证据表明，即使信号强度不够强，即使分离强度很强，也没有多项式时间算法是一致的。在高斯以下噪声下进一步证明了我们低级劳埃德算法的性能。讨论了LRMM下估计和聚类之间的有趣差异。通过全面的仿真实验证实了低级劳埃德算法的优点。最后，我们的方法在现实世界数据集的文献中优于其他方法。

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

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this paper we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We establish the identifiability of our model and propose a computationally efficient estimation procedure based on the higher-order orthogonal iteration algorithm (HOOI) for tensor SVD composed with a simplex corner-finding algorithm. We then demonstrate the consistency of our estimation procedure by providing a per-node error bound, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the $\ell_{2,\infty}$ tensor perturbation bound for HOOI under independent, possibly heteroskedastic, subgaussian noise that may be of independent interest. Our analysis uses a novel leave-one-out construction for the iterates, and our bounds depend only on spectral properties of the underlying low-rank tensor under nearly optimal signal-to-noise ratio conditions such that tensor SVD is computationally feasible. Whereas other leave-one-out analyses typically focus on sequences constructed by analyzing the output of a given algorithm with a small part of the noise removed, our leave-one-out analysis constructions use both the previous iterates and the additional tensor structure to eliminate a potential additional source of error. Finally, we apply our methodology to real and simulated data, including applications to two flight datasets and a trade network dataset, demonstrating some effects not identifiable from the model with discrete community memberships.

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

现实世界网络经常具有侧面信息，可以帮助提高网络分析任务等群集的性能。尽管在过去十年中对网络聚类方法进行了大量的实证和理论研究，但侧面信息的附加值和用于在聚类算法中最佳地结合的方法的附加值相对较少理解。我们向群集网络提出了一种新的迭代算法，其中包含节点的侧面信息（以协调因子的形式）提出并表明我们的算法在上下文对称随机块模型下是最佳的。我们的算法可以应用于一般上下文随机块模型，并避免与先前提出的方法相比，避免了HyperParameter调整。我们在综合数据实验中确认我们的理论结果，其中我们的算法显着优于其他方法，并表明它也可以应用于签名的图表。最后，我们展示了我们对实际数据方法的实际兴趣。

K-Subspaces（KSS）方法是用于子空间聚类的K-均值方法的概括。在这项工作中，我们介绍了KSS的本地收敛分析和恢复保证，假设数据是由Smari-random的子空间模型生成的，其中$ n $点是从$ k \ ge 2 $重叠子空间随机采样的。我们表明，如果KSS方法的初始分配位于真实聚类的邻域内，则它以高等的速率收敛，并在$ \ theta（\ log \ log \ log n）$迭代中找到正确的群集。此外，我们提出了一种基于阈值的基于内部产品的光谱方法来初始化，并证明它在该社区中产生了一个点。我们还提出了研究方法的数值结果，以支持我们的理论发展。

我们调查与高斯的混合的数据分享共同但未知，潜在虐待协方差矩阵的数据。我们首先考虑具有两个等级大小的组件的高斯混合，并根据最大似然估计导出最大切割整数程序。当样品的数量在维度下线性增长时，我们证明其解决方案实现了最佳的错误分类率，直到对数因子。但是，解决最大切割问题似乎是在计算上棘手的。为了克服这一点，我们开发了一种高效的频谱算法，该算法达到最佳速率，但需要一种二次样本量。虽然这种样本复杂性比最大切割问题更差，但我们猜测没有多项式方法可以更好地执行。此外，我们收集了支持统计计算差距存在的数值和理论证据。最后，我们将MAX-CUT程序概括为$ k $ -means程序，该程序处理多组分混合物的可能性不平等。它享有相似的最优性保证，用于满足运输成本不平等的分布式的混合物，包括高斯和强烈的对数的分布。

社区检测是网络科学中的一个基本问题。在本文中，我们考虑了从$ HyperGraph $ $ $ $ $ $ $ $ $ $ $ $ $ $ $（HSBM）中绘制的HyperGraphs中的社区检测，重点是精确的社区恢复。在整个超图未知的情况下，我们研究了多项式时间算法以进行社区检测的性能。取而代之的是，我们获得了$相似性$ $ $ $ $ $ $ w $，其中$ w_ {ij} $报告包含$ i $和$ j $的超补品的数量。在此信息模型下，Kim，Bandeira和Goemans [KBG18]确定了信息理论阈值，以进行精确恢复，并提出了他们认为是最佳的半决赛编程松弛。在本文中，我们确认了这个猜想。我们还表明，一种简单，高效的光谱算法是最佳的，将光谱算法作为选择方法。我们对光谱算法的分析至关重要地依赖于$ w $的特征向量上的强$ entrywise $界限。我们的边界灵感来自Abbe，Fan，Wang和Zhong [AFWZ20]的工作，他们开发了具有独立条目的对称矩阵的特征向量的进入界。尽管相似性矩阵的依赖性结构复杂，但我们证明了相似的入口保证。

组同步是指从嘈杂的成对测量中估计组元素的集合。这种非核解问题来自包括计算机视觉，机器人和冷冻电子显微镜的许多科学领域的大量关注。在本文中，我们专注于在不完全测量下的一般添加剂噪声模型的正交组同步问题，这比通常考虑的完整测量设置更多。从最优条件的透视提供正交组同步问题的特征以及投影梯度上升方法的固定点，其也称为广义功率方法（GPM）。值得注意的是，即使没有生成模型，这些结果仍然存在。同时，我们导出了对正交组同步问题的本地错误绑定属性，这对于不同算法的融合速率分析非常有用，并且可以是独立的兴趣。最后，我们在基于已建立的本地误差绑定属性的一般添加剂噪声模型下将GPM的线性收敛结果证明了GPM到全局最大化器。我们的理论会聚结果在若干确定性条件下持有，其可以覆盖具有对抗性噪声的某些情况，并且作为我们专门化以确定ERD \“OS-R”enyi测量图和高斯噪声的示例。

我们在非均匀超图随机块模型（HSBM）下的稀疏随机超图中的社区检测问题，是社区结构的随机网络的一般模型和高阶交互。当随机超图具有界定的预期度时，我们提供了一种频谱算法，该频谱算法输出分区，其中至少有$ \ gamma $分数正确分类，其中$ \ gamma \ in（0.5,1）$取决于信号 - 模型的噪声比（SNR）。当SNR随着顶点的数量转到无限的时，SNR慢慢地增长，我们的算法达到了弱的一致性，这改善了Ghoshdastidar和Dukkipati（2017）的上一个结果，用于非均匀的HSBMS。我们的谱算法由三个主要步骤组成：（1）HIFFEGE选择：选择某些尺寸的超高率，为诱导的子图像提供最大信噪比; （2）光谱分区：构造正则化邻接矩阵，并基于奇异向量获得近似分区; （3）纠正和合并：将超代表信息从邻接张于升级升级错误率保证。我们的算法的理论分析依赖于稀疏非均匀随机超图的邻接矩阵的浓度和正则化，这可以是独立的兴趣。

我们在一般随机块模型下研究现实网络中的社区层次结构，其中连接概率在二叉树中构造。在这种模型中，标准递归双分区算法基于非通知图拉普拉斯的Fiedler向量将网络分成两个社区，并重复分割，直到停止规则指示不进一步的社区结构。我们在广泛的模型参数下证明了这种方法的强大一致性，它包括稀疏网络，节点度为$ O（\ log n）$。此外，与大多数现有工作不同，我们的理论涵盖了多尺度网络，其中连接概率可能因数量级而异，这包括一类实际相关但技术上挑战处理的重要阶段。最后，我们展示了我们对综合性数据和实际示例算法的表现。

在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法，该算法可以忍受$ \ 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提供了可靠的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限制的单调变化混合在一起，从半随机模型中。

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

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

我们考虑一个矩阵完成问题，用于将社交或项目相似性图形作为侧面信息。我们开发了一种普遍的，无参数和计算的有效算法，该算法以分层图形聚类开始，然后迭代地改进图形聚类和矩阵额定值。在一个层次的随机块模型，尊重实际相关的社交图和低秩评级矩阵模型（要详细），我们证明了我们的算法实现了观察到的矩阵条目数量的信息 - 理论限制（即，最佳通过与较低的不可能结果一起导出的样本复杂性）通过最大似然估计。该结果的一个结果是利用社交图的层次结构，相对于简单地识别不同组的情况，在不诉诸于它们的情况下，可以产生相对于不同组的样本复杂性的大量增益。我们对合成和现实世界数据集进行了广泛的实验，以证实我们的理论结果，并展示了利用图形侧信息的其他矩阵完成算法的显着性能改进。