Web-based interactions can be frequently represented by an attributed graph, and node clustering in such graphs has received much attention lately. Multiple efforts have successfully applied Graph Convolutional Networks (GCN), though with some limits on accuracy as GCNs have been shown to suffer from over-smoothing issues. Though other methods (particularly those based on Laplacian Smoothing) have reported better accuracy, a fundamental limitation of all the work is a lack of scalability. This paper addresses this open problem by relating the Laplacian smoothing to the Generalized PageRank and applying a random-walk based algorithm as a scalable graph filter. This forms the basis for our scalable deep clustering algorithm, RwSL, where through a self-supervised mini-batch training mechanism, we simultaneously optimize a deep neural network for sample-cluster assignment distribution and an autoencoder for a clustering-oriented embedding. Using 6 real-world datasets and 6 clustering metrics, we show that RwSL achieved improved results over several recent baselines. Most notably, we show that RwSL, unlike all other deep clustering frameworks, can continue to scale beyond graphs with more than one million nodes, i.e., handle web-scale. We also demonstrate how RwSL could perform node clustering on a graph with 1.8 billion edges using only a single GPU.
翻译:以网络为基础的互动通常可以用一个归属图来表示,而这种图表中的节点组合最近引起人们的极大注意。多方面的努力成功地应用了图表革命网络(GCN ) 。尽管由于GCN 的精确度有一定的局限性,但GCN 被证明存在过度移动的问题。尽管其他方法(特别是基于拉巴西平滑的方法)报告更加准确,但所有工作的根本性限制是缺乏可缩放性。本文通过将拉巴西平滑与通用的PageRank 平滑和将随机行走算法作为可缩放的图表过滤器来解决这一开放问题。特别是,这构成了我们可缩放的深集算法(RwSL ) 的基础, 通过自我监督的小型组培训机制,我们同时优化了样本集群分布的深度神经网络和面向集群的嵌入器。 使用6个真实世界数据集和6个组合指标,我们显示RwSL 在某些最近的基线上取得了改进的结果。 最明显的是,我们显示RwSL, 与所有其他的深度组合框架不同,我们无法用一个比SLG的图像更深层的大小的图像继续显示,我们如何使用。