通常，通过聚类或订购将标签分配给每个元素，通常可以分析关系数据集。尽管通过聚类和排序方法可以实现数据集的类似表征，但前者比后者更积极地研究了数据集，尤其是对于表示为图的数据。这项研究通过研究几种聚类和订购方法之间的方法学关系来填补这一空白，重点是光谱技术。此外，我们评估了聚类和订购方法的结果性能。为此，我们提出了一种称为标签连续性误差的度量，该度量通常量化了一组元素的序列和分区之间的一致性程度。基于合成和现实世界数据集，我们评估了订购方法标识模块结构和聚类方法标识带状结构的范围。

在本文中，我们提出了一种新方法来检测具有归因顶点的无向图中的簇。目的是将不仅在结构连接性方面，而且在属性值方面相似的顶点分组。我们通过创建[6,38]中提出的其他顶点和边缘，将顶点之间的结构和属性相似。然后将增强图嵌入到与其拉普拉斯式相关的欧几里得空间中，在该空间中，应用了修改的K-均值算法以识别簇。修改后的k均值依赖于矢量距离度量，根据每个原始顶点，我们分配了合适的矢量值坐标集，这取决于结构连接性和属性相似性，因此每个原始图顶点都被认为是$ M+1的代表增强图的$顶点，如果$ m $是顶点属性的数量。为了定义坐标矢量，我们基于自适应AMG（代数多机）方法采用了我们最近提出的算法，该方法识别了嵌入欧几里得空间中的坐标方向，以代数平滑的矢量相对于我们的增强图Laplacian，从而扩展了laplacian，从而扩展了坐标。没有属性的图形的先前结果。我们通过与一些知名方法进行比较，分析了我们提出的聚类方法的有效性，这些方法可以免费获得软件实现，并与文献中报告的结果相比，在两种不同类型的广泛使用的合成图上以及在某些现实世界中的图形上。

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

Stochastic blockmodels have been proposed as a tool for detecting community structure in networks as well as for generating synthetic networks for use as benchmarks. Most blockmodels, however, ignore variation in vertex degree, making them unsuitable for applications to real-world networks, which typically display broad degree distributions that can significantly distort the results.Here we demonstrate how the generalization of blockmodels to incorporate this missing element leads to an improved objective function for community detection in complex networks. We also propose a heuristic algorithm for community detection using this objective function or its non-degree-corrected counterpart and show that the degree-corrected version dramatically outperforms the uncorrected one in both real-world and synthetic networks.

由于其数值益处增加及其坚实的数学背景，光谱聚类方法的非线性重构近来的关注。我们在$ p $ -norm中提出了一种新的直接多道谱聚类算法，以$ p \ in（1,2] $。计算图表的多个特征向量的问题$ p $ -laplacian，标准的非线性概括Graph Laplacian，被重用作为Grassmann歧管的无约束最小化问题。$ P $的价值以伪连续的方式减少，促进对应于最佳图形的稀疏解决方案载体作为$ P $接近。监测单调减少平衡图削减了我们从$ P $ -Levels获得的最佳可用解决方案的保证。我们展示了我们算法在各种人工测试案件中的算法的有效性和准确性。我们的数值和比较结果具有各种状态-Art聚类方法表明，所提出的方法在均衡的图形剪切度量和标签分配的准确性方面取得高质量的集群。此外，我们进行S面部图像和手写字符分类的束缚，以展示现实数据集中的适用性。

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

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.

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

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

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.

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

我们提出了一种凸锥程序，可推断随机点产品图（RDPG）的潜在概率矩阵。优化问题最大化Bernoulli最大似然函数，增加核规范正则化术语。双重问题具有特别良好的形式，与众所周知的SemideFinite程序放松MaxCut问题有关。使用原始双功率条件，我们绑定了原始和双解决方案的条目和等级。此外，我们在轻微的技术假设下绑定了最佳目标值并证明了略微修改模型的概率估计的渐近一致性。我们对合成RDPG的实验不仅恢复了自然集群，而且还揭示了原始数据的下面的低维几何形状。我们还证明该方法在空手道俱乐部图表和合成美国参议图中恢复潜在结构，并且可以扩展到最多几百个节点的图表。

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

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

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.

当节点具有人口统计属性时，概率图形模型中社区结构的推理可能不会与公平约束一致。某些人口统计学可能在某些检测到的社区中过度代表，在其他人中欠代表。本文定义了一个新的$ \ ell_1 $ -regulared伪似然方法，用于公平图形模型选择。特别是，我们假设真正的基础图表​​中存在一些社区或聚类结构，我们寻求从数据中学习稀疏的无向图形及其社区，使得人口统计团体在社区内相当代表。我们的优化方法使用公平的人口统计奇偶校验定义，但框架很容易扩展到其他公平的定义。我们建立了分别，连续和二进制数据的高斯图形模型和Ising模型的提出方法的统计一致性，证明了我们的方法可以以高概率恢复图形及其公平社区。

光谱聚类在从业者和理论家中都很受欢迎。尽管对光谱聚类的性能保证有充分的了解，但最近的研究集中于在群集中执行``公平''，要求它们在分类敏感的节点属性方面必须``平衡''人口中的种族分布）。在本文中，我们考虑了一个设置，其中敏感属性间接表现在辅助\ textit {表示图}中，而不是直接观察到。该图指定了可以相对于敏感属性互相表示的节点对，除了通常的\ textit {相似性图}外，还可以观察到。我们的目标是在相似性图中找到簇，同时尊重由表示图编码的新个人公平性约束。我们为此任务开发了不均衡和归一化光谱聚类的变体，并在代表图诱导的种植分区模型下分析其性能。该模型同时使用节点的群集成员身份和表示图的结构来生成随机相似性图。据我们所知，这些是在个人级别的公平限制下受约束光谱聚类的第一个一致性结果。数值结果证实了我们的理论发现。

There are synergies of research interests and industrial efforts in modeling fairness and correcting algorithmic bias in machine learning. In this paper, we present a scalable algorithm for spectral clustering (SC) with group fairness constraints. Group fairness is also known as statistical parity where in each cluster, each protected group is represented with the same proportion as in the entirety. While FairSC algorithm (Kleindessner et al., 2019) is able to find the fairer clustering, it is compromised by high costs due to the kernels of computing nullspaces and the square roots of dense matrices explicitly. We present a new formulation of underlying spectral computation by incorporating nullspace projection and Hotelling's deflation such that the resulting algorithm, called s-FairSC, only involves the sparse matrix-vector products and is able to fully exploit the sparsity of the fair SC model. The experimental results on the modified stochastic block model demonstrate that s-FairSC is comparable with FairSC in recovering fair clustering. Meanwhile, it is sped up by a factor of 12 for moderate model sizes. s-FairSC is further demonstrated to be scalable in the sense that the computational costs of s-FairSC only increase marginally compared to the SC without fairness constraints.

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