数据处理的最新进展刺激了对非常大尺度的学习图的需求。众所周知,图形神经网络(GNN)是解决图形学习任务的一种新兴和有力的方法,很难扩大规模。大多数可扩展模型应用基于节点的技术来简化GNN的昂贵图形消息传播过程。但是,我们发现当应用于百万甚至数十亿尺度的图表时,这种加速度不足。在这项工作中,我们提出了Scara,这是一种可扩展的GNN,具有针对图形计算的特征优化。 Scara有效地计算出从节点功能中嵌入的图形,并进一步选择和重用功能计算结果以减少开销。理论分析表明,我们的模型在传播过程以及GNN培训和推理中具有确保精度,实现了子线性时间的复杂性。我们在各种数据集上进行了广泛的实验,以评估圣aca的功效和效率。与基线的性能比较表明,与快速收敛和可比精度相比,与当前的最新方法相比,圣aca最高可达到100倍的图形传播加速度。最值得注意的是,在100秒内处理最大的十亿个GNN数据集纸100m(1.11亿节点,1.6B边缘)上的预先计算是有效的。
translated by 谷歌翻译
图表卷积网络(GCNS)在各种半监督节点分类任务中取得了令人印象深刻的实证进步。尽管取得了巨大的成功,但在大型图形上培训GCNS遭受了计算和内存问题。规避这些障碍的潜在路径是基于采样的方法,其中在每个层处采样节点的子集。虽然最近的研究已经证明了基于采样的方法的有效性,但这些作品缺乏在现实环境下的理论融合担保,并且不能完全利用优化期间演出参数的信息。在本文中,我们描述并分析了一般的双差异减少模式,可以在内存预算下加速任何采样方法。所提出的模式的激励推动是仔细分析采样方法的差异,其中示出了诱导方差可以在前进传播期间分解为节点嵌入近似方差(Zeroth阶差异)(第一 - 顺序变化)在后向传播期间。理论上,从理论上分析所提出的架构的融合,并显示它享有$ \ Mathcal {O}(1 / T)$收敛率。我们通过将建议的模式集成在不同的采样方法中并将其应用于不同的大型实际图形来补充我们的理论结果。
translated by 谷歌翻译
最近提出了基于子图的图表学习(SGRL)来应对规范图神经网络(GNNS)遇到的一些基本挑战,并在许多重要的数据科学应用(例如链接,关系和主题预测)中证明了优势。但是,当前的SGRL方法遇到了可伸缩性问题,因为它们需要为每个培训或测试查询提取子图。扩大规范GNN的最新解决方案可能不适用于SGRL。在这里,我们通过共同设计学习算法及其系统支持,为可扩展的SGRL提出了一种新颖的框架Surel。 Surel采用基于步行的子图表分解,并将步行重新形成子图,从而大大降低了子图提取的冗余并支持并行计算。具有数百万个节点和边缘的六个同质,异质和高阶图的实验证明了Surel的有效性和可扩展性。特别是,与SGRL基线相比,Surel可以实现10 $ \ times $ Quad-Up,具有可比甚至更好的预测性能;与规范GNN相比,Surel可实现50%的预测准确性。
translated by 谷歌翻译
Graph convolutional network (GCN) has been successfully applied to many graph-based applications; however, training a large-scale GCN remains challenging. Current SGD-based algorithms suffer from either a high computational cost that exponentially grows with number of GCN layers, or a large space requirement for keeping the entire graph and the embedding of each node in memory. In this paper, we propose Cluster-GCN, a novel GCN algorithm that is suitable for SGD-based training by exploiting the graph clustering structure. Cluster-GCN works as the following: at each step, it samples a block of nodes that associate with a dense subgraph identified by a graph clustering algorithm, and restricts the neighborhood search within this subgraph. This simple but effective strategy leads to significantly improved memory and computational efficiency while being able to achieve comparable test accuracy with previous algorithms. To test the scalability of our algorithm, we create a new Amazon2M data with 2 million nodes and 61 million edges which is more than 5 times larger than the previous largest publicly available dataset (Reddit). For training a 3-layer GCN on this data, Cluster-GCN is faster than the previous state-of-the-art VR-GCN (1523 seconds vs 1961 seconds) and using much less memory (2.2GB vs 11.2GB). Furthermore, for training 4 layer GCN on this data, our algorithm can finish in around 36 minutes while all the existing GCN training algorithms fail to train due to the out-of-memory issue. Furthermore, Cluster-GCN allows us to train much deeper GCN without much time and memory overhead, which leads to improved prediction accuracy-using a 5-layer Cluster-GCN, we achieve state-of-the-art test F1 score 99.36 on the PPI dataset, while the previous best result was 98.71 by [16]. Our codes are publicly available at https://github.com/google-research/google-research/ tree/master/cluster_gcn.
translated by 谷歌翻译
最近,图形神经网络(GNN)通过利用图形结构和节点特征的知识来表现出图表表示的显着性能。但是,他们中的大多数都有两个主要限制。首先,GNN可以通过堆叠更多的层来学习高阶结构信息,但由于过度光滑的问题,无法处理较大的深度。其次,由于昂贵的计算成本和高内存使用情况,在大图上应用这些方法并不容易。在本文中,我们提出了节点自适应特征平滑(NAFS),这是一种简单的非参数方法,该方法构建了没有参数学习的节点表示。 NAFS首先通过特征平滑提取每个节点及其不同啤酒花的邻居的特征,然后自适应地结合了平滑的特征。此外,通过不同的平滑策略提取的平滑特征的合奏可以进一步增强构建的节点表示形式。我们在两个不同的应用程序方案上对四个基准数据集进行实验:节点群集和链接预测。值得注意的是,具有功能合奏的NAFS优于这些任务上最先进的GNN,并减轻上述大多数基于学习的GNN对应物的两个限制。
translated by 谷歌翻译
图形神经网络(GNN)在学习强大的节点表示中显示了令人信服的性能,这些表现在保留节点属性和图形结构信息的强大节点表示中。然而,许多GNNS在设计有更深的网络结构或手柄大小的图形时遇到有效性和效率的问题。已经提出了几种采样算法来改善和加速GNN的培训,但他们忽略了解GNN性能增益的来源。图表数据中的信息的测量可以帮助采样算法来保持高价值信息,同时消除冗余信息甚至噪声。在本文中,我们提出了一种用于GNN的公制引导(MEGUIDE)子图学习框架。 MEGUIDE采用两种新颖的度量:功能平滑和连接失效距离,以指导子图采样和迷你批次的培训。功能平滑度专为分析节点的特征而才能保留最有价值的信息,而连接失败距离可以测量结构信息以控制子图的大小。我们展示了MEGUIDE在多个数据集上培训各种GNN的有效性和效率。
translated by 谷歌翻译
图表表示学习是一种快速增长的领域,其中一个主要目标是在低维空间中产生有意义的图形表示。已经成功地应用了学习的嵌入式来执行各种预测任务,例如链路预测,节点分类,群集和可视化。图表社区的集体努力提供了数百种方法,但在所有评估指标下没有单一方法擅长,例如预测准确性,运行时间,可扩展性等。该调查旨在通过考虑算法来评估嵌入方法的所有主要类别的图表变体,参数选择,可伸缩性,硬件和软件平台,下游ML任务和多样化数据集。我们使用包含手动特征工程,矩阵分解,浅神经网络和深图卷积网络的分类法组织了图形嵌入技术。我们使用广泛使用的基准图表评估了节点分类,链路预测,群集和可视化任务的这些类别算法。我们在Pytorch几何和DGL库上设计了我们的实验,并在不同的多核CPU和GPU平台上运行实验。我们严格地审查了各种性能指标下嵌入方法的性能,并总结了结果。因此,本文可以作为比较指南,以帮助用户选择最适合其任务的方法。
translated by 谷歌翻译
图形神经网络(GNN)是具有无核数据的应用的有前途的方法。但是,具有数亿节点的大规模图上的培训GNN既是资源又是耗时的。与DNN不同,GNN通常具有更大的内存足迹,因此GPU内存能力和PCIE带宽是GNN培训中的主要资源瓶颈。为了解决此问题,我们提出分叉:一种图形量化方法,通过显着减少内存足迹和PCIE带宽要求来加速GNN训练,以便GNN可以充分利用GPU计算功能。我们的关键见解是,与DNN不同,GNN不太容易发生量化引起的输入特征的信息丢失。我们确定图形特征量化中的主要准确性影响因素,从理论上证明,分叉训练会收敛到网络,在该网络中,损失在未压缩网络的最佳损失的$ \ epsilon $之内。我们使用几种流行的GNN模型和数据集对分叉进行了广泛的评估,包括最大的公共图数据集MAG240M上的图形。结果表明,分叉达到30以上的压缩率,并在边际准确性损失的情况下提高了GNN训练速度200%-320%。特别是,分叉在一小时内仅使用四个GPU在MAG240M上的训练图来实现记录。
translated by 谷歌翻译
Using graph neural networks for large graphs is challenging since there is no clear way of constructing mini-batches. To solve this, previous methods have relied on sampling or graph clustering. While these approaches often lead to good training convergence, they introduce significant overhead due to expensive random data accesses and perform poorly during inference. In this work we instead focus on model behavior during inference. We theoretically model batch construction via maximizing the influence score of nodes on the outputs. This formulation leads to optimal approximation of the output when we do not have knowledge of the trained model. We call the resulting method influence-based mini-batching (IBMB). IBMB accelerates inference by up to 130x compared to previous methods that reach similar accuracy. Remarkably, with adaptive optimization and the right training schedule IBMB can also substantially accelerate training, thanks to precomputed batches and consecutive memory accesses. This results in up to 18x faster training per epoch and up to 17x faster convergence per runtime compared to previous methods.
translated by 谷歌翻译
图形神经网络(GNN)在许多基于图的应用程序中取得了巨大成功。但是,巨大的尺寸和高稀疏度的图表阻碍了其在工业场景下的应用。尽管为大规模图提出了一些可扩展的GNN,但它们为每个节点采用固定的$ k $ hop邻域,因此在稀疏区域内采用大型繁殖深度时面临过度光滑的问题。为了解决上述问题,我们提出了一种新的GNN体系结构 - 图形注意多层感知器(GAMLP),该架构可以捕获不同图形知识范围之间的基本相关性。我们已经与天使平台部署了GAMLP,并进一步评估了现实世界数据集和大规模工业数据集的GAMLP。这14个图数据集的广泛实验表明,GAMLP在享有高可扩展性和效率的同时,达到了最先进的性能。具体来说,在我们的大规模腾讯视频数据集上的预测准确性方面,它的表现优于1.3 \%,同时达到了高达$ 50 \ times $ triending的速度。此外,它在开放图基准的最大同质和异质图(即OGBN-PAPERS100M和OGBN-MAG)的排行榜上排名第一。
translated by 谷歌翻译
Given a large graph with few node labels, how can we (a) identify the mixed network-effect of the graph and (b) predict the unknown labels accurately and efficiently? This work proposes Network Effect Analysis (NEA) and UltraProp, which are based on two insights: (a) the network-effect (NE) insight: a graph can exhibit not only one of homophily and heterophily, but also both or none in a label-wise manner, and (b) the neighbor-differentiation (ND) insight: neighbors have different degrees of influence on the target node based on the strength of connections. NEA provides a statistical test to check whether a graph exhibits network-effect or not, and surprisingly discovers the absence of NE in many real-world graphs known to have heterophily. UltraProp solves the node classification problem with notable advantages: (a) Accurate, thanks to the network-effect (NE) and neighbor-differentiation (ND) insights; (b) Explainable, precisely estimating the compatibility matrix; (c) Scalable, being linear with the input size and handling graphs with millions of nodes; and (d) Principled, with closed-form formula and theoretical guarantee. Applied on eight real-world graph datasets, UltraProp outperforms top competitors in terms of accuracy and run time, requiring only stock CPU servers. On a large real-world graph with 1.6M nodes and 22.3M edges, UltraProp achieves more than 9 times speedup (12 minutes vs. 2 hours) compared to most competitors.
translated by 谷歌翻译
图形神经网络(GNNS)由于图形数据的规模和模型参数的数量呈指数增长,因此限制了它们在实际应用中的效用,因此往往会遭受高计算成本。为此,最近的一些作品着重于用彩票假设(LTH)稀疏GNN,以降低推理成本,同时保持绩效水平。但是,基于LTH的方法具有两个主要缺点:1)它们需要对密集模型进行详尽且迭代的训练,从而产生了极大的训练计算成本,2)它们仅修剪图形结构和模型参数,但忽略了节点功能维度,存在大量冗余。为了克服上述局限性,我们提出了一个综合的图形渐进修剪框架,称为CGP。这是通过在一个训练过程中设计在训练图周期修剪范式上进行动态修剪GNN来实现的。与基于LTH的方法不同,提出的CGP方法不需要重新训练,这大大降低了计算成本。此外,我们设计了一个共同策略,以全面地修剪GNN的所有三个核心元素:图形结构,节点特征和模型参数。同时,旨在完善修剪操作,我们将重生过程引入我们的CGP框架,以重新建立修剪但重要的连接。提出的CGP通过在6个GNN体系结构中使用节点分类任务进行评估,包括浅层模型(GCN和GAT),浅但深度散发模型(SGC和APPNP)以及Deep Models(GCNII和RESGCN),总共有14个真实图形数据集,包括来自挑战性开放图基准的大规模图数据集。实验表明,我们提出的策略在匹配时大大提高了训练和推理效率,甚至超过了现有方法的准确性。
translated by 谷歌翻译
最近,Graph神经网络(GNNS)已成为聚光灯作为强大的工具,可以有效地在图形结构化数据上执行各种推理任务。随着现实图表的大小继续扩展,GNN训练系统面临可扩展性挑战。分布式培训是一种流行的方法,可以通过扩展CPU节点来应对这一挑战。但是,对基于磁盘的GNN培训的关注不多,该培训可以通过利用NVME SSD等高性能存储设备来以更具成本效益的方式扩展单节点系统。我们观察到,主内存和磁盘之间的数据移动是基于SSD的训练系统中的主要瓶颈,并且常规的GNN训练管道是不错的选择,而无需考虑此开销。因此,我们提出了Ginex,这是第一个基于SSD的GNN训练系统,可以在单台计算机上处​​理数十亿个图形数据集。受到编译器优化的检查员执行模型的启发,Ginex通过分开样品和收集阶段来重组GNN训练管道。这种分离使Ginex能够实现一种可证明的最佳替换算法,即被称为Belady的算法,用于存储器中的Caching特征向量,该算法是I/O访问的主要部分。根据我们对40亿尺度图数据集的评估,Ginex平均比SSD扩展的Pytorch几何得出了2.11倍的训练吞吐量(最大最高2.67倍)。
translated by 谷歌翻译
在许多现实世界应用中,基于图表编辑距离(GED)等指标(GED)等图表之间计算相似性得分的能力很重要。计算精确的GED值通常是一个NP硬性问题,传统算法通常在准确性和效率之间实现不令人满意的权衡。最近,图形神经网络(GNNS)为该任务提供了数据驱动的解决方案,该解决方案更有效,同时保持小图中的预测准确性(每图约10个节点)相似性计算。现有的基于GNN的方法分别嵌入了两个图(缺乏低水平的横向互动)或用于整个图表对(冗余和耗时)的部署跨冲突相互作用,在图中的节点数量增加。在本文中,我们着重于大规模图的相似性计算,并提出了“嵌入式磨合匹配”框架cosimgnn,该框架首先嵌入和粗大图形具有自适应池操作,然后在污垢的图表上部署细粒度的相互作用,以便在污垢的图形上进行污垢的互动最终相似性得分。此外,我们创建了几个合成数据集,这些数据集为图形相似性计算提供了新的基准测试。已经进行了有关合成数据集和现实世界数据集的详细实验,并且Cosimgnn实现了最佳性能,而推理时间最多是以前的Etab-The-The-The-ART的1/3。
translated by 谷歌翻译
图形神经网络(GNN)已被证明是分析非欧国人图数据的强大工具。但是,缺乏有效的分布图学习(GL)系统极大地阻碍了GNN的应用,尤其是当图形大且GNN相对深时。本文中,我们提出了GraphTheta,这是一种以顶点为中心的图形编程模型实现的新颖分布式和可扩展的GL系统。 GraphTheta是第一个基于分布式图处理的GL系统,其神经网络运算符以用户定义的功能实现。该系统支持多种培训策略,并在分布式(虚拟)机器上启用高度可扩展的大图学习。为了促进图形卷积实现,GraphTheta提出了一个名为NN-Tgar的新的GL抽象,以弥合图形处理和图形深度学习之间的差距。提出了分布式图引擎,以通过混合平行执行进行随机梯度下降优化。此外,除了全球批次和迷你批次外,我们还为新的集群批次培训策略提供了支持。我们使用许多网络大小的数据集评估GraphTheta,范围从小,适度到大规模。实验结果表明,GraphTheta可以很好地扩展到1,024名工人,用于培训内部开发的GNN,该工业尺度的Aripay数据集为14亿个节点和41亿个属性边缘,并带有CPU虚拟机(Dockers)群的小群。 (5 $ \ sim $ 12GB)。此外,GraphTheta比最先进的GNN实现获得了可比或更好的预测结果,证明其学习GNN和现有框架的能力,并且可以超过多达$ 2.02 \ tims $ $ 2.02 \ times $,具有更好的可扩展性。据我们所知,这项工作介绍了文献中最大的边缘属性GNN学习任务。
translated by 谷歌翻译
Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based inductive learning method that improves training efficiency and accuracy in a fundamentally different way. By changing perspective, GraphSAINT constructs minibatches by sampling the training graph, rather than the nodes or edges across GCN layers. Each iteration, a complete GCN is built from the properly sampled subgraph. Thus, we ensure fixed number of well-connected nodes in all layers. We further propose normalization technique to eliminate bias, and sampling algorithms for variance reduction. Importantly, we can decouple the sampling from the forward and backward propagation, and extend GraphSAINT with many architecture variants (e.g., graph attention, jumping connection). GraphSAINT demonstrates superior performance in both accuracy and training time on five large graphs, and achieves new state-of-the-art F1 scores for PPI (0.995) and Reddit (0.970).
translated by 谷歌翻译
图形神经网络(GNNS)依赖于图形结构来定义聚合策略,其中每个节点通过与邻居的信息组合来更新其表示。已知GNN的限制是,随着层数的增加,信息被平滑,压扁并且节点嵌入式变得无法区分,对性能产生负面影响。因此,实用的GNN模型雇用了几层,只能在每个节点周围的有限邻域利用图形结构。不可避免地,实际的GNN不会根据图的全局结构捕获信息。虽然有几种研究GNNS的局限性和表达性,但是关于图形结构数据的实际应用的问题需要全局结构知识,仍然没有答案。在这项工作中,我们通过向几个GNN模型提供全球信息并观察其对下游性能的影响来认证解决这个问题。我们的研究结果表明,全球信息实际上可以为共同的图形相关任务提供显着的好处。我们进一步确定了一项新的正规化策略,导致所有考虑的任务的平均准确性提高超过5%。
translated by 谷歌翻译
我们提出了一个框架,该框架会自动将不可缩放的GNN转换为基于预典型的GNN,该GNN对于大型图表有效且可扩展。我们框架的优势是两倍。1)它通过将局部特征聚合与其图形卷积中的重量学习分开,2)通过将其边缘分解为小型图形,将其有效地在GPU上进行了预先执行,将各种局部特征聚合与重量学习分开,将各种局部特征聚合从重量学习中分离出来,从而使各种不可估计的GNN转换为大规模图表。和平衡的集合。通过大规模图的广泛实验,我们证明了转化的GNN在训练时间内的运行速度比现有的GNN更快,同时实现了最先进的GNN的竞争精度。因此,我们的转型框架为可伸缩GNN的未来研究提供了简单有效的基础。
translated by 谷歌翻译
图表学习方法为解决图形所代表的复杂的现实世界问题打开了新的可能性。但是,这些应用程序中使用的许多图包括数百万节点和数十亿个边缘,并且超出了当前方法和软件实现的功能。我们提供葡萄,这是一种用于图形处理和表示学习的软件资源,能够通过使用专业和智能数据结构,算法和快速并行实现来通过大图扩展。与最先进的软件资源相比,葡萄显示出经验空间和时间复杂性的数量级的改善,以及边缘预测和节点标签预测性能的实质和统计学上的显着改善。此外,葡萄提供了来自文献和其他来源的80,000多种图,标准化界面允许直接整合第三方库,61个节点嵌入方法,25个推理模型和3个模块化管道,以允许公平且可重复的方法比较以及用于图形处理和嵌入的库。
translated by 谷歌翻译
图表神经网络(GNNS)在各种机器学习任务中获得了表示学习的提高。然而,应用邻域聚合的大多数现有GNN通常在图中的图表上执行不良,其中相邻的节点属于不同的类。在本文中,我们示出了在典型的异界图中,边缘可以被引导,以及是否像是处理边缘,也可以使它们过度地影响到GNN模型的性能。此外,由于异常的限制,节点对来自本地邻域之外的类似节点的消息非常有益。这些激励我们开发一个自适应地学习图表的方向性的模型,并利用潜在的长距离相关性节点之间。我们首先将图拉普拉斯概括为基于所提出的特征感知PageRank算法向数字化,该算法同时考虑节点之间的图形方向性和长距离特征相似性。然后,Digraph Laplacian定义了一个图形传播矩阵,导致一个名为{\ em diglaciangcn}的模型。基于此,我们进一步利用节点之间的通勤时间测量的节点接近度,以便在拓扑级别上保留节点的远距离相关性。具有不同级别的10个数据集的广泛实验,同意级别展示了我们在节点分类任务任务中对现有解决方案的有效性。
translated by 谷歌翻译