我们提出了一种基于图形神经网络的图分算法。对于图表中的每个节点，网络输出每个分区的概率。图形神经网络由两个模块组成：嵌入阶段和分区阶段。首先通过最小化由光谱图理论的启发的损耗函数来训练嵌入阶段。分区模块通过损耗函数培训，该损耗函数对应于归一化切割的预期值。神经网络的两部分依赖于Sage卷积层和粗糙化粗糙匹配的图表。神经网络的多级结构受到多重级算法的启发。我们的方法概括了更大的图表，并且与Metis，Scotch和光谱分区相当的分区质量，与Metis和光谱分区相比具有较短的运行时。

超图允许使用多向高阶关系建模问题。然而，大多数现有超图的算法的计算成本可能严重取决于输入的超图尺寸。为了解决不断增加的计算挑战，可以通过积极聚合其顶点（节点）来预先处理给定的超图来促进图表粗化。然而，未经纳入启发式图粗化技术的最先进的超图分区（聚类）方法未得到优化，以保留超图的结构（全局）属性。在这项工作中，我们提出了一种有效的光谱超图粗化方案（HypersF），以保持超图的原始光谱（结构）特性。我们的方法利用了最近的强烈局部最大流量的聚类算法，用于检测最小化比例的超图形顶点集。为了进一步提高算法效率，我们通过利用与原始超图对应的二分形图的光谱聚类来提出分频和征服方案。我们从现实世界VLSI设计基准提取的各种超图的实验结果表明，与现有最先进的现有技术相比，所提出的超图粗略化算法可以显着提高超图和运行时效率的多线电导算法。

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

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

Graph Convolutional Networks (GCNs) are extensively utilized for deep learning on graphs. The large data sizes of graphs and their vertex features make scalable training algorithms and distributed memory systems necessary. Since the convolution operation on graphs induces irregular memory access patterns, designing a memory- and communication-efficient parallel algorithm for GCN training poses unique challenges. We propose a highly parallel training algorithm that scales to large processor counts. In our solution, the large adjacency and vertex-feature matrices are partitioned among processors. We exploit the vertex-partitioning of the graph to use non-blocking point-to-point communication operations between processors for better scalability. To further minimize the parallelization overheads, we introduce a sparse matrix partitioning scheme based on a hypergraph partitioning model for full-batch training. We also propose a novel stochastic hypergraph model to encode the expected communication volume in mini-batch training. We show the merits of the hypergraph model, previously unexplored for GCN training, over the standard graph partitioning model which does not accurately encode the communication costs. Experiments performed on real-world graph datasets demonstrate that the proposed algorithms achieve considerable speedups over alternative solutions. The optimizations achieved on communication costs become even more pronounced at high scalability with many processors. The performance benefits are preserved in deeper GCNs having more layers as well as on billion-scale graphs.

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.

图形卷积网络（GCN）已被证明是一个有力的概念，在过去几年中，已成功应用于许多领域的各种任务。在这项工作中，我们研究了为GCN定义铺平道路的理论，包括经典图理论的相关部分。我们还讨论并在实验上证明了GCN的关键特性和局限性，例如由样品的统计依赖性引起的，该图由图的边缘引入，这会导致完整梯度的估计值偏置。我们讨论的另一个限制是Minibatch采样对模型性能的负面影响。结果，在参数更新期间，在整个数据集上计算梯度，从而破坏了对大图的可扩展性。为了解决这个问题，我们研究了替代方法，这些方法允许在每次迭代中仅采样一部分数据，可以安全地学习良好的参数。我们重现了KIPF等人的工作中报告的结果。并提出一个灵感签名的实现，这是一种无抽样的minibatch方法。最终，我们比较了基准数据集上的两个实现，证明它们在半监督节点分类任务的预测准确性方面是可比的。

This paper introduces a scalable algorithmic framework (HyperEF) for spectral coarsening (decomposition) of large-scale hypergraphs by exploiting hyperedge effective resistances. Motivated by the latest theoretical framework for low-resistance-diameter decomposition of simple graphs, HyperEF aims at decomposing large hypergraphs into multiple node clusters with only a few inter-cluster hyperedges. The key component in HyperEF is a nearly-linear time algorithm for estimating hyperedge effective resistances, which allows incorporating the latest diffusion-based non-linear quadratic operators defined on hypergraphs. To achieve good runtime scalability, HyperEF searches within the Krylov subspace (or approximate eigensubspace) for identifying the nearly-optimal vectors for approximating the hyperedge effective resistances. In addition, a node weight propagation scheme for multilevel spectral hypergraph decomposition has been introduced for achieving even greater node coarsening ratios. When compared with state-of-the-art hypergraph partitioning (clustering) methods, extensive experiment results on real-world VLSI designs show that HyperEF can more effectively coarsen (decompose) hypergraphs without losing key structural (spectral) properties of the original hypergraphs, while achieving over $70\times$ runtime speedups over hMetis and $20\times$ speedups over HyperSF.

大图通常出现在社交网络，知识图，推荐系统，生命科学和决策问题中。通过其高级别属性总结大图有助于解决这些设置中的问题。在光谱聚类中，我们旨在确定大多数边缘落在簇内的节点簇，而在簇之间只有很少的边缘。此任务对于许多下游应用和探索性分析很重要。光谱聚类的核心步骤是执行相应图的拉普拉斯矩阵（或等效地，奇异值分解，SVD）的特征分类。迭代奇异值分解方法的收敛取决于给定矩阵的光谱的特征，即连续特征值之间的差异。对于对应于群集图的图形的图形拉普拉斯，特征值将是非负的，但很小（小于$ 1 $）的减慢收敛性。本文引入了一种可行的方法，用于扩张光谱以加速SVD求解器，然后又是光谱群集。这是通过对矩阵操作的多项式近似来实现的，矩阵操作有利地改变矩阵的光谱而不更改其特征向量。实验表明，这种方法显着加速了收敛，我们解释了如何并行化和随机近似于可用的计算。

Machine Unerning是在收到删除请求时从机器学习（ML）模型中删除某些培训数据的影响的过程。虽然直接而合法，但从划痕中重新训练ML模型会导致高计算开销。为了解决这个问题，在图像和文本数据的域中提出了许多近似算法，其中SISA是最新的解决方案。它将训练集随机分配到多个碎片中，并为每个碎片训练一个组成模型。但是，将SISA直接应用于图形数据可能会严重损害图形结构信息，从而导致的ML模型实用程序。在本文中，我们提出了Grapheraser，这是一种针对图形数据量身定制的新型机器学习框架。它的贡献包括两种新型的图形分区算法和一种基于学习的聚合方法。我们在五个现实世界图数据集上进行了广泛的实验，以说明Grapheraser的学习效率和模型实用程序。它可以实现2.06 $ \ times $（小数据集）至35.94 $ \ times $（大数据集）未学习时间的改进。另一方面，Grapheraser的实现最高62.5美元\％$更高的F1分数，我们提出的基于学习的聚合方法可达到高达$ 112 \％$ $ F1分数。 github.com/minchen00/graph-unlearning}。}。}

将计算谐波分析工具扩展到常规格子的经典设置到更普通的图形和网络的设置是非常重要的，最近已经完成了许多研究。由IRION和SAITO（2014）开发的通用HAAR-WALSH变换（GHWT）是图形上的信号的多尺度变换，这是古典哈拉和沃尔什哈拉德变换的概括。我们提出了扩展的广义Haar-Walsh变换（eGHWT），这是Thiele和Villemoes（1996）的适应时频倾斜的概括。 eGHWT不仅检查了图形域分区的效率，还可以同时查看“续间域”分区。因此，图形信号的EGHWT及其相关的最佳基础选择算法显着提高了以前的计算成本，$ O（n \ log n）$的先前GHW的性能，其中$ n $是一个节点的数量输入图。虽然GHWT最佳基础算法在$ \ mathbb {r} ^ $可能的正交基础中寻求给定任务的最适合的正常正常基础。在$ \ mathbb {r} ^ n $，eghwt最佳基础算法可以找到一个通过在$ \ mathbb {r} ^ n $中搜索超过0.618美元\ cdot（1.84）^ n $可能的正交基础。本文介绍了EGHWT最佳基础算法的细节，并使用包括真正曲线信号的若干示例以及作为曲线图信号观看的传统数字图像来展示其优越性。此外，我们还通过将它们视为从其列和行生成的图表的张量乘积来展示如何扩展到2D信号和矩阵形式数据，并展示其对图像近似的应用的有效性。

Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.

图形神经网络（GNN）已被证明可以实现竞争结果，以解决与图形相关的任务，例如节点和图形分类，链接预测和节点以及各种域中的图形群集。大多数GNN使用消息传递框架，因此称为MPNN。尽管有很有希望的结果，但据报道，MPNN会遭受过度平滑，过度阵型和不足的影响。文献中已经提出了图形重新布线和图形池作为解决这些局限性的解决方案。但是，大多数最先进的图形重新布线方法无法保留该图的全局拓扑，因此没有可区分（电感），并且需要调整超参数。在本文中，我们提出了Diffwire，这是一个在MPNN中进行图形重新布线的新型框架，它通过利用LOV \'ASZ绑定来原理，完全可区分且无参数。我们的方法通过提出两个新的，mpnns中的新的互补层来提供统一的图形重新布线：首先，ctlayer，一个学习通勤时间并将其用作边缘重新加权的相关函数；其次，Gaplayer是优化光谱差距的图层，具体取决于网络的性质和手头的任务。我们从经验上验证了我们提出的方法的价值，并使用基准数据集分别验证了这些层的每个层以进行图形分类。 Diffwire将通勤时间的可学习性汇集到相关的曲率定义，为发展更具表现力的MPNN的发展打开了大门。

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.

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.

我们从光谱的角度解决图形生成问题，首先生成图形laplacian光谱的主要部分，然后构建与这些特征值和特征向量相匹配的图。光谱调节允许直接建模全局和局部图结构，并有助于克服单发图生成器的表达性和模式崩溃问题。我们的新颖的甘（Spectre）称为Spectre，可以使用一声模型来产生比以前可能更大的图。Spectre的表现优于最先进的深度自动回归发电机在建模忠诚方面，同时还避免了昂贵的顺序产生和对节点排序的依赖。一个很好的例子，在相当大的合成和现实图形中，Specter的幽灵比最佳竞争对手的最佳竞争对手的改进是4到170倍，该竞争对手不合适，比自回旋发电机快23至30倍。

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

图表学习方法为解决图形所代表的复杂的现实世界问题打开了新的可能性。但是，这些应用程序中使用的许多图包括数百万节点和数十亿个边缘，并且超出了当前方法和软件实现的功能。我们提供葡萄，这是一种用于图形处理和表示学习的软件资源，能够通过使用专业和智能数据结构，算法和快速并行实现来通过大图扩展。与最先进的软件资源相比，葡萄显示出经验空间和时间复杂性的数量级的改善，以及边缘预测和节点标签预测性能的实质和统计学上的显着改善。此外，葡萄提供了来自文献和其他来源的80,000多种图，标准化界面允许直接整合第三方库，61个节点嵌入方法，25个推理模型和3个模块化管道，以允许公平且可重复的方法比较以及用于图形处理和嵌入的库。

在过去十年中，图形内核引起了很多关注，并在结构化数据上发展成为一种快速发展的学习分支。在过去的20年中，该领域发生的相当大的研究活动导致开发数十个图形内核，每个图形内核都对焦于图形的特定结构性质。图形内核已成功地成功地在广泛的域中，从社交网络到生物信息学。本调查的目标是提供图形内核的文献的统一视图。特别是，我们概述了各种图形内核。此外，我们对公共数据集的几个内核进行了实验评估，并提供了比较研究。最后，我们讨论图形内核的关键应用，并概述了一些仍有待解决的挑战。

在处理大规模网络和关系数据时，降低图是基本的。它们可以通过在粗糙的结构中求解它们来缩小高度计算影响的尺寸。同时，图减少起着在图神经网络中合并层的作用，从结构中提取多分辨率表示。在这些情况下，还原机制保留距离关系和拓扑特性的能力似乎是基本的，以及可扩展性，使其能够应用于实际大小的问题。在本文中，我们基于最大重量$ k $独立的集合的图理论概念引入了图形粗化机制，从而提供了一种贪婪的算法，该算法允许在GPU上有效地并行实现。我们的方法是常规数据（图像，序列）中的第一个图形结构化对应物。我们证明了在路径长度上的失真界限的理论保证，以及在污垢图中保留关键拓扑特性的能力。我们利用这些概念来定义我们在图形分类任务中经验评估的图表合并机制，表明它与文献中的合并方法进行了比较。