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

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

Classical asymptotic theory for statistical inference usually involves calibrating a statistic by fixing the dimension $d$ while letting the sample size $n$ increase to infinity. Recently, much effort has been dedicated towards understanding how these methods behave in high-dimensional settings, where $d$ and $n$ both increase to infinity together. This often leads to different inference procedures, depending on the assumptions about the dimensionality, leaving the practitioner in a bind: given a dataset with 100 samples in 20 dimensions, should they calibrate by assuming $n \gg d$, or $d/n \approx 0.2$? This paper considers the goal of dimension-agnostic inference; developing methods whose validity does not depend on any assumption on $d$ versus $n$. We introduce an approach that uses variational representations of existing test statistics along with sample splitting and self-normalization to produce a new test statistic with a Gaussian limiting distribution, regardless of how $d$ scales with $n$. The resulting statistic can be viewed as a careful modification of degenerate U-statistics, dropping diagonal blocks and retaining off-diagonal blocks. We exemplify our technique for some classical problems including one-sample mean and covariance testing, and show that our tests have minimax rate-optimal power against appropriate local alternatives. In most settings, our cross U-statistic matches the high-dimensional power of the corresponding (degenerate) U-statistic up to a $\sqrt{2}$ factor.

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

网络研究中最根本的问题之一是社区检测。随机块模型（SBM）是一种流行的模型，具有不同的估计方法，其社区检测一致性结果揭晓。但是，SBM受到强烈假设的限制：同一社区中的所有节点在随机上都是等效的，这可能不适合实际应用。我们引入了成对协变量调整后的随机块模型（PCABM），这是SBM的概括，该模型包含成对协变量信息。我们研究协变量和社区分配系数的最大似然估计。结果表明，在适当的稀疏条件下，协变量和社区分配的系数估计均一致。引入了带有调节的光谱聚类（SCWA），以有效地求解PCABM。在某些条件下，我们得出了SCWA下社区检测的错误限制，并表明它是社区检测一致的。此外，研究了模型的选择，并研究了成对协变量的特征选择，并提出了两种相应的算法。当可访问协变量信息时，PCABM与SBM或学位校正的随机块模型（DCBM）进行比较。

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.

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.

Testing the significance of a variable or group of variables $X$ for predicting a response $Y$, given additional covariates $Z$, is a ubiquitous task in statistics. A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. However, when the model is misspecified, the test may have poor power, for example when $X$ is involved in complex interactions, or lead to many false rejections. In this work we study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests, to yield both robust error control and high power. The procedure involves using these methods to perform regressions, first to estimate a form of projection of $Y$ on $X$ and $Z$ using one half of the data, and then to estimate the expected conditional covariance between this projection and $Y$ on the remaining half of the data. While the approach is general, we show that a version of our procedure using spline regression achieves what we show is the minimax optimal rate in this nonparametric testing problem. Numerical experiments demonstrate the effectiveness of our approach both in terms of maintaining Type I error control, and power, compared to several existing approaches.

本文研究了由$ 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 $足够大。我们还提供了几种离线和在线的估计算法，它充分利用了观察到的数据的时间性。我们在数据稀疏性和可识别性的各种假设下分析所提出的估计算法的准确性。数值实验表明，即使是社区分配的初始估计（例如，盲目随机猜测）也会导致在少量迭代之后通过在线算法获得的高精度，并且在非常稀疏的方案中也是如此。

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

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

统计推断中的主要范式取决于I.I.D.的结构。来自假设的无限人群的数据。尽管它取得了成功，但在复杂的数据结构下，即使在清楚无限人口所代表的内容的情况下，该框架在复杂的数据结构下仍然不灵活。在本文中，我们探讨了一个替代框架，在该框架中，推断只是对模型误差的不变性假设，例如交换性或符号对称性。作为解决这个不变推理问题的一般方法，我们提出了一个基于随机的过程。我们证明了该过程的渐近有效性的一般条件，并在许多数据结构中说明了，包括单向和双向布局中的群集误差。我们发现，通过残差随机化的不变推断具有三个吸引人的属性：（1）在弱且可解释的条件下是有效的，可以解决重型数据，有限聚类甚至一些高维设置的问题。 （2）它在有限样品中是可靠的，因为它不依赖经典渐近学所需的规律性条件。 （3）它以适应数据结构的统一方式解决了推断问题。另一方面，诸如OLS或Bootstrap之类的经典程序以I.I.D.为前提。结构，只要实际问题结构不同，就需要修改。经典框架中的这种不匹配导致了多种可靠的误差技术和自举变体，这些变体经常混淆应用研究。我们通过广泛的经验评估证实了这些发现。残留随机化对许多替代方案的表现有利，包括可靠的误差方法，自举变体和分层模型。

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

网络可能具有弱信号和严重程度的异质性，并且可能在一次出现时非常稀疏，但在另一个发生中非常致密。得分（Jin，2015）是最近网络社区检测的方法。它适应严重的程度异质性，并适应不同水平的稀疏性，但它对具有弱信号的网络的性能尚不清楚。在本文中，我们认为，在广泛的网络设置中，我们允许弱信号，严重程度异质性和广泛的网络稀疏性，得分实现了完善的聚类，并且在汉明集群中具有所谓的“指数率”错误。证据对网络邻接矩阵的领先特征向量进行了最新的进出方程。理论分析向我们保证，在弱信号设置中，得分继续运行，但它不排除分数可以进一步提高的可能性，以在实际应用中具有更好的性能，特别是对于具有弱信号的网络。作为纸张的第二份贡献，我们提出得分+作为改进的分数版本。我们调查了8个网络数据集的得分+，发现它优于几种代表性的方法。特别是，对于具有相对强烈的信号的6个数据集，得分+具有与得分相似的性能，但对于2个数据集（Simmons，Caltech）具有可能弱信号，得分+的误差率较低。得分+提出了几个变化以得分。我们使用理论和数值研究的混合物仔细解释每个变化的基本原理。

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

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.

由于其出色的经验表现，随机森林是过去十年中使用的机器学习方法之一。然而，由于其黑框的性质，在许多大数据应用中很难解释随机森林的结果。量化各个特征在随机森林中的实用性可以大大增强其解释性。现有的研究表明，一些普遍使用的特征对随机森林的重要性措施遭受了偏见问题。此外，对于大多数现有方法，缺乏全面的规模和功率分析。在本文中，我们通过假设检验解决了问题，并提出了一个自由化特征 - 弥散性相关测试（事实）的框架，以评估具有偏见性属性的随机森林模型中给定特征的重要性，我们零假设涉及该特征是否与所有其他特征有条件地独立于响应。关于高维随机森林一致性的一些最新发展，对随机森林推断的这种努力得到了赋予的能力。在存在功能依赖性的情况下，我们的事实测试的香草版可能会遇到偏见问题。我们利用偏置校正的不平衡和调节技术。我们通过增强功率的功能转换将合奏的想法进一步纳入事实统计范围。在相当普遍的具有依赖特征的高维非参数模型设置下，我们正式确定事实可以提供理论上合理的随机森林具有P值，并通过非催化分析享受吸引人的力量。新建议的方法的理论结果和有限样本优势通过几个模拟示例和与Covid-19的经济预测应用进行了说明。

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

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.

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