In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times\left( 2+ \alpha (G) \right)+n)$ to $O(m+n)$ for any given value of $\varepsilon$ for a complete signed graph with $n$ vertices and $m$ positive edges where $\alpha(G)$ is the arboricity of the graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting where edge sign flipping and vertex addition/removal are allowed. Constructing this index costs $O(m)$ memory and $O(m\times\alpha(G))$ time. We also studied the structural properties of the non-agreement measure used in the approximation algorithm. The theoretical results are accompanied by a full set of experiments concerning seven real-world graphs. These results shows superiority of our index-based algorithm to the non-index one by a decrease of %34 in time on average.

We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluster, and the total weight of vertices in the cluster. We show that our definition is closely related to popular clustering measures, namely normalized associations, which is a dual of the normalized cut objective, and normalized modularity. We give a linear time constant-approximate algorithm for our objective, which implies the first constant-factor approximation algorithms for normalized modularity and normalized associations.

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.

Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。

社交网络通常是使用签名图对社交网络进行建模的，其中顶点与用户相对应，并且边缘具有一个指示用户之间的交互作用的符号。出现的签名图通常包含一个清晰的社区结构，因为该图可以分配到少数极化社区中，每个群落都定义了稀疏切割，并且不可分割地分为较小的极化亚共同体。我们为具有如此清晰的社区结构的签名图提供了本地聚类甲骨文图的小部分。正式地，当图形具有最高度且社区数量最多为$ o（\ log n）$时，则使用$ \ tilde {o}（\ sqrt {n} \ sqrt {n} \ propatatorName {poly}（1/\ varepsilon） ）$预处理时间，我们的Oracle可以回答$ \ tilde {o}（\ sqrt {n} \ operatorname {poly}（1/\ varepsilon））$ time的每个成员查询，并且它正确地分类了$（1--1-（1-） \ varepsilon）$ - 顶点W.R.T.的分数一组隐藏的种植地面真实社区。我们的Oracle在仅需要少数顶点需要的聚类信息的应用中是可取的。以前，此类局部聚类牙齿仅因无符号图而闻名。我们对签名图的概括需要许多新的想法，并对随机步行的行为进行了新的光谱分析。我们评估了我们的算法，用于在合成和现实世界数据集上构建这种甲骨文和回答成员资格查询，从而在实践中验证其性能。

图形上的分层聚类是数据挖掘和机器学习中的一项基本任务，并在系统发育学，社交网络分析和信息检索等领域中进行了应用。具体而言，我们考虑了由于Dasgupta引起的层次聚类的最近普及的目标函数。以前（大约）最小化此目标函数的算法需要线性时间/空间复杂性。在许多应用程序中，底层图的大小可能很大，即使使用线性时间/空间算法，也可以在计算上具有挑战性。结果，人们对设计只能使用sublinear资源执行全局计算的算法有浓厚的兴趣。这项工作的重点是在三个经过良好的sublinear计算模型下研究大量图的层次聚类，分别侧重于时空，时间和通信，作为要优化的主要资源：（1）（动态）流模型。边缘作为流，（2）查询模型表示，其中使用邻居和度查询查询图形，（3）MPC模型，其中图边缘通过通信通道连接的几台机器进行了分区。我们在上面的所有三个模型中设计用于层次聚类的sublinear算法。我们算法结果的核心是图表中的剪切方面的视图，这使我们能够使用宽松的剪刀示意图进行分层聚类，同时仅引入目标函数中的较小失真。然后，我们的主要算法贡献是如何在查询模型和MPC模型中有效地构建所需形式的切割稀疏器。我们通过建立几乎匹配的下限来补充我们的算法结果，该界限排除了在每个模型中设计更好的算法的可能性。

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.

分层聚类研究将数据集的递归分区设置为连续较小尺寸的簇，并且是数据分析中的基本问题。在这项工作中，我们研究了Dasgupta引入的分层聚类的成本函数，并呈现了两个多项式时间近似算法：我们的第一个结果是高度电导率图的$ O（1）$ - 近似算法。我们简单的建筑绕过了在文献中已知的稀疏切割的复杂递归常规。我们的第二个和主要结果是一个US（1）$ - 用于展示群集明确结构的宽族图形的近似算法。该结果推出了以前的最先进的，该现有技术仅适用于从随机模型产生的图表。通过对合成和现实世界数据集的实证分析，我们所呈现的算法的实证分析表明了我们的工作的重要性，以其具有明确定义的集群结构的先前所提出的图表算法。

相关聚类是无监督的机器学习中无处不在的范式，在这种学习中解决不公平是一个主要的挑战。在此激励的情况下，我们研究了数据点可能属于不同保护组的公平相关聚类，目标是确保跨簇的所有组公平代表。我们的论文显着概括并改善了Ahmadi等人先前工作的质量保证。和Ahmadian等。如下。 - 我们允许用户指定群集中每个组表示的任意上限。 - 我们的算法允许个人具有多个受保护的功能，并确保所有这些特征同时公平。 - 我们证明，在这种一般环境中，可以保证质量和公平性。此外，这改善了先前工作中研究的特殊情况的结果。我们对现实世界数据的实验表明，与最佳解决方案相比，我们的聚类质量要比理论结果所建议的要好得多。

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.

Mazumdar和Saha \ Cite {MS17A}的开创性论文引入了有关聚类的广泛工作，并带有嘈杂的查询。然而，尽管在问题上取得了重大进展，但所提出的方法至关重要地取决于了解基础全随随随之而来的甲骨文错误的确切概率。在这项工作中，我们开发了可靠的学习方法，这些方法可以忍受一般的半随机噪声，从而在定性上获得与全随机模型中最佳方法相同的保证。更具体地说，给定一组$ n $点带有未知的基础分区，我们可以查询点$ u，v $检查它们是否在同一群集中，但是有了概率$ p $，答案可能可以受到对抗的选择。我们在理论上显示信息$ o \ left（\ frac {nk \ log n} {（1-2p）^2} \ right）$查询足以学习任何足够大尺寸的群集。我们的主要结果是一种计算高效算法，可以用$ o \ left（\ frac {nk \ log n} {（1-2p）^2} \ right） + \ text {poly} \ left（\ log（\ log） n，k，\ frac {1} {1-2p} \ right）$查询，与完全随机模型中最知名算法的保证相匹配。作为我们方法的推论，我们为全随机模型开发了第一个无参数算法，并通过\ cite {ms17a}回答一个空的问题。

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

在相关聚类问题中，我们为我们提供了一组具有成对相似性信息的对象。我们的目的是将这些对象划分为尽可能紧密匹配此信息的群集。更具体地说，成对信息是作为加权图$ g $给​​出的，其边缘标记为``类似的''或``不同''二进制分类器。目的是产生一个聚类，以最大程度地减少``分歧''的权重：跨簇中类似边缘和群集中不同边缘的权重的总和。在此博览会中，我们重点介绍$ g $完整且未加权的情况。我们探索了此假设下相关聚类问题的四种近似算法。特别是，我们描述了以下算法：（i）$ 17429- $ $近似算法，Bansal，Blum和Chawla，（II）$ 4- $ $近似算法由$ 4- $ $近似算法。 Charikar，Guruswami和Wirth（III）Ailon，Charikar和Newman和Newman（IV）的$ 3- $近似算法是Chawla，Makarychev，Schramm和Yaroslavtsev的$ 2.06- $近似算法。

在许多应用程序的动机上，我们以错误的甲骨文研究聚类。在此问题中，有$ n $的项目属于$ k $未知群集，允许算法询问甲骨文是否属于同一群集。但是，Oracle的答案仅使用概率$ \ frac {1} {2}+\ frac {\ delta} {2} $正确。目的是恢复最少数量嘈杂的查询的隐藏群集。以前的作品表明，可以用$ o（\ frac {nk \ log n} {\ delta^2} + \ text {poly}（k，\ frac {1} {\ delta}，\ log n ）$ QUERIES，而$ \ Omega（\ frac {nk} {\ delta^2}）$ queries是必要的。因此，对于任何$ k $和$ \ \ delta $的值，上限和下限之间仍然存在非平凡的差距。在这项工作中，我们获得了广泛参数的第一个匹配上限和下限。特别是，具有$ o（\ frac {n（k + \ log n）} {\ delta^2} + \ text {poly}（k，\ frac {1} {\ delta}， n））提出了$查询。此外，我们证明了$ \ omega（\ frac {n \ log n} {\ delta^2}）$的新下限，它与现有$ \ omega（\ frac {nk} {\ delta^2结合在一起） }）$绑定，将我们的上限匹配到添加$ \ text {poly}（k，\ frac {1} {\ delta}，\ log n）$ term。为了获得新的结果，我们的主要成分是我们的问题与多臂强盗之间的有趣联系，这可能为其他类似问题提供有用的见解。

已经研究了分层群集，并广泛使用作为数据分析的方法。最近，Dasgupta [2016]定义了精确的目标函数。给定一套$ n $数据点，每两个项目$ w_ {i，j} $ w_ {i，j} $ i和$ j $表示他们的相似性/ dive相似性，目标是建立递归（树）将数据点（项目）分区成连续较小的簇。他定义了一棵树$ t $的成本函数为$ compt（t）= \ sum_ {i，j \在[n]} \ big（w_ {i，j} \ times | t_ {i，j} | \大）$ where $ t_ {i，j} $是subtree植根于$ i $和$ j $最不常见的祖先，并呈现了这种聚类的第一个近似算法。然后Moseley和Wang [2017]考虑了Dasgupta的双重目标函数，以适应性的重量，并显示出随机分区和平均连锁有近似比1/3 $的近似值为1/3美元，这一系列工程为0.585 $ [Alon等al。 2020]。后来Cohen-Addad等。 [2019]认为与Dasgupta的客观函数相同，但对于基于不同的基于指标，称为$ Rev（T）$。结果表明，随机分区和平均连锁有2/3美元的比例仅为0.667078 $ 0.667078 $ [Charikar等人。 SODA2020]。我们的第一个主要结果是考虑$ Rev（T）$，并提出更精致的算法和仔细分析，实现近似值0.71604 $。我们还为基于异化的聚类介绍了一个新的目标函数。对于任何树$ t $，让$ h_ {i，j} $是$ i $和$ j $的常见祖先的数量。直观地，预计相似的项目将在尽可能深处留在同一群体内。因此，对于基于不同的指标，我们建议每棵树$ t $的成本，我们想要最小化，是$ cost_h（t）= \ sum_ {i，j \在[n]} \ big（w_ {我，j} \ times h_ {i，j} \ big）$。我们为此目标提供1.3977美元的价值。

结构分解方法，例如普遍的高树木分解，已成功用于解决约束满意度问题（CSP）。由于可以重复使用分解以求解具有相同约束范围的CSP，因此即使计算本身很难，将资源投资于计算良好的分解是有益的。不幸的是，即使示波器仅略有变化，当前方法也需要计算全新的分解。在本文中，我们迈出了解决CSP $ P $分解的问题的第一步，以使其成为由$ P $修改产生的新CSP $ P'$的有效分解。即使从理论上讲问题很难，我们还是提出并实施了一个有效更新GHD的框架。我们算法的实验评估强烈提出了实际适用性。

本文考虑了最近流行的超越最坏情况算法分析模型，其与在线算法设计集成了机器学习预测。我们在此模型中考虑在线Steiner树问题，用于指向和无向图。据了解施泰纳树在线设置中具有强大的下限，并且任何算法的最坏情况都远非可取。本文考虑了预测哪个终端在线到达的算法。预测可能是不正确的，并且算法的性能由错误预测的终端的数量进行参数化。这些保证确保算法通过具有良好预测的在线下限，并且随着预测误差的增长，竞争比率优雅地降低。然后，我们观察到该理论是预测将经验发生的事情。我们在终端从分发中绘制的图表中显示了终端，即使具有适度正确的预测，新的在线算法也具有很强的性能。

常用图是表示和可视化因果关系的。对于少量变量，这种方法提供了简洁和清晰的方案的视图。随着下属的变量数量增加，图形方法可能变得不切实际，并且表示的清晰度丢失。变量的聚类是减少因果图大小的自然方式，但如果任意实施，可能会错误地改变因果关系的基本属性。我们定义了一种特定类型的群集，称为Transit Cluster，保证在某些条件下保留因果效应的可识别性属性。我们提供了一种用于在给定图中查找所有传输群集的声音和完整的算法，并演示集群如何简化因果效应的识别。我们还研究了逆问题，其中一个人以群集的图形开始，寻找扩展图，其中因果效应的可识别性属性保持不变。我们表明这种结构稳健性与过境集群密切相关。

重新配置图中的两个最短路径意味着通过一次改变一个顶点来修改一个最短的路径，使得所有中间路径也是最短路径。这个问题有几个自然应用，即：（a）改造道路网络，（b）在同步多处理设置中重新排出数据包，（c）运输集装箱存货问题，以及（d）列车编组问题。在作为图形问题的建模时，（a）是最常规的情况而（b），（c）和（d）是对不同图形类的限制。我们表明（a）是棘手的，即使对于问题的轻松变体也是如此。对于（b），（c）和（d），我们提出了有效的算法来解决各自的问题。我们还将问题概括为当最多$ k $（对于固定整数$ k \ geq k \ ge $ k \ geq 2 $）一次连续的顶点一次可以一次更改。

随机漫游是许多机器学习算法中使用的基本原语，其中包括聚类和半监督学习中的几种应用。尽管他们的相关性，但最近推出了第一个计算随机散步的有效并行算法（Lacki等人）。不幸的是，他们的方法具有基本缺点：它们的算法是非本地的，因为它严重依赖于计算随机从输入图中的所有节点中散布，即使在许多实际应用中只对计算随机只能从一个小子集中散步感兴趣图中的节点。在本文中，我们介绍了一种新的算法，通过同时建立随机和本地的随机行走来克服这种限制。我们表明我们的技术既存储器也又高效，特别是产生有效的并行本地聚类算法。最后，我们将我们的理论分析补充了实验结果，表明我们的算法比以前的方法更可扩展。