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

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

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

随机块模型（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.

The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i.e., assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still very limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML 2013] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to polylogarithmic factors) when the probability parameters are constant. As a byproduct, we obtain a polynomial-time algorithm with sublinear query complexity for a clustering problem with a faulty oracle, which finds all clusters of size larger than $\tilde{\Omega}({\sqrt{n}})$ even if $\Omega(n)$ small clusters co-exist in the graph. In contrast, all the previous efficient algorithms that makes sublinear number of queries cannot recover any large cluster, if there are more than $\tilde{\Omega}(n^{2/5})$ small clusters.

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

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

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

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

我们在一般随机块模型下研究现实网络中的社区层次结构，其中连接概率在二叉树中构造。在这种模型中，标准递归双分区算法基于非通知图拉普拉斯的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提供了可靠的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限制的单调变化混合在一起，从半随机模型中。

本文研究了由$ N $-$ N $ TCONOR代表的非二进制对交互估计的社区成员资格，其值为$ \ MATHCAL S $的元素，其中$ N $是节点的数量和$ \ Mathcal S $是节点之间的成对交互的空间。作为信息理论基准，我们研究由非二进制随机块模型生成的数据集，并导致社区成员资格的基本信息标准作为$ n \ to \ idty $。应用程序的示例包括加权网络（$ \ mathcal s = \ mathbb r $），链接标记的网络$（\ mathcal s = \ {0,1，1，\ dots，l \} $），多路复用网络$（\ mathcal s = \ {0,1 \} ^ m $）和时间网络（$ \ mathcal s = \ {0,1 \} ^ t $）。对于时间互动，我们表明（i）即使是$ t $的少数增加也可能对社区成员的恢复产生了很大影响，（ii）即使对于非常稀疏的数据（例如\ in in inverly degress），甚至可能存在一致的恢复$ t $足够大。我们还提供了几种离线和在线的估计算法，它充分利用了观察到的数据的时间性。我们在数据稀疏性和可识别性的各种假设下分析所提出的估计算法的准确性。数值实验表明，即使是社区分配的初始估计（例如，盲目随机猜测）也会导致在少量迭代之后通过在线算法获得的高精度，并且在非常稀疏的方案中也是如此。

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.

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

本文讨论了ERD \ H {O} S-R \'enyi图的图形匹配或网络对齐问题，可以将其视为图同构问题的嘈杂平均案例版本。令$ g $和$ g'$ be $ g（n，p）$ erd \ h {o} s--r \'enyi略微图形，并用其邻接矩阵识别。假设$ g $和$ g'$是相关的，因此$ \ mathbb {e} [g_ {ij} g'_ {ij}] = p（1- \ alpha）$。对于置换$ \ pi $，代表$ g $和$ g'$之间的潜在匹配，用$ g^\ pi $表示从$ \ pi $的$ g $的顶点获得的图表。观察$ g^\ pi $和$ g'$，我们的目标是恢复匹配的$ \ pi $。在这项工作中，我们证明，在（0,1] $中，每$ \ varepsilon \ in（0,1] $，都有$ n_0> 0 $，具体取决于$ \ varepsilon $和绝对常数$ \ alpha_0，r> 0 $，带有以下属性。令$ n \ ge n_0 $，$（1+ \ varepsilon）\ log n \ le np \ le n^{\ frac {1} {r \ log \ log \ log n}} $ （\ alpha_0，\ varepsilon/4）$。有一个多项式时算法$ f $，因此$ \ m athbb {p} \ {f（g^\ pi，g'）= \ pi \} = 1-o （1）$。这是第一种多项式时算法，它恢复了相关的ERD \ H {O} S-r \'enyi图与具有恒定相关性的相关性图与高概率相关性的确切匹配。该算法是基于比较的比较与图形顶点关联的分区树。

为了捕获许多社区检测问题的固有几何特征，我们建议使用一个新的社区随机图模型，我们称之为\ emph {几何块模型}。几何模型建立在\ emph {随机几何图}（Gilbert，1961）上，这是空间网络的随机图的基本模型之一，就像在ERD \ H上建立的良好的随机块模型一样{o} s-r \'{en} yi随机图。它也是受到社区发现中最新的理论和实际进步启发的随机社区模型的自然扩展。为了分析几何模型，我们首先为\ emph {Random Annulus图}提供新的连接结果，这是随机几何图的概括。自引入以来，已经研究了几何图的连通性特性，并且由于相关的边缘形成而很难分析它们。然后，我们使用随机环形图的连接结果来提供必要的条件，以有效地为几何块模型恢复社区。我们表明，一种简单的三角计数算法来检测几何模型中的社区几乎是最佳的。为此，我们考虑了两个图密度方案。在图表的平均程度随着顶点的对数增长的状态中，我们表明我们的算法在理论上和实际上都表现出色。相比之下，三角计数算法对于对数学度方案中随机块模型远非最佳。我们还查看了图表的平均度与顶点$ n $的数量线性增长的状态，因此要存储一个需要$ \ theta（n^2）$内存的图表。我们表明，我们的算法需要在此制度中仅存储$ o（n \ log n）$边缘以恢复潜在社区。

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

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

我们研究了情节块MDP中模型估计和无奖励学习的问题。在这些MDP中，决策者可以访问少数潜在状态产生的丰富观察或上下文。我们首先对基于固定行为策略生成的数据估算潜在状态解码功能（从观测到潜在状态的映射）感兴趣。我们在估计此功能的错误率上得出了信息理论的下限，并提出了接近此基本限制的算法。反过来，我们的算法还提供了MDP的所有组件的估计值。然后，我们研究在无奖励框架中学习近乎最佳政策的问题。根据我们有效的模型估计算法，我们表明我们可以以最佳的速度推断出策略（随着收集样品的数量增长大）的最佳策略。有趣的是，我们的分析提供了必要和充分的条件，在这些条件下，利用块结构可以改善样本复杂性，以识别近乎最佳的策略。当满足这些条件时，Minimax无奖励设置中的样本复杂性将通过乘法因子$ n $提高，其中$ n $是可能的上下文数量。