Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of edges. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high-quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of ACMin in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that ACMin consistently outperforms all competitors in terms of result quality measured against ground-truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, ACMin outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.


翻译:鉴于每个节点都与一组属性相关联的图形 G, 以及一个参数 k 指定输出群集数目的数值, k属性图形群集( k- AGC) 将 G 中的 K属性图形群集( k- AGC) 节点组成 k 互换组群, 使同一组群中的节点具有相似的表层和属性特性, 而不同组群中的节点则不同。 这个问题在巨大的图表上具有挑战性, 例如, 数百万个节点和数十亿边缘。 对于这些图表, 现有的解决方案要么带来惊人的高成本, 或产生质量下降的质量。 在本文件中, 我们提议对 k属性群集采取有效的方法, 使 K- AGC 生成高质量的组合群集, 成本线性组合组群与输入G 的大小相直线线。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2021年6月30日
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Arxiv
0+阅读 · 2021年11月6日
Arxiv
31+阅读 · 2020年9月21日
Arxiv
4+阅读 · 2019年1月14日
Embedding Logical Queries on Knowledge Graphs
Arxiv
5+阅读 · 2018年9月6日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2021年6月30日
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
专知会员服务
42+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
相关论文
Arxiv
0+阅读 · 2021年11月6日
Arxiv
31+阅读 · 2020年9月21日
Arxiv
4+阅读 · 2019年1月14日
Embedding Logical Queries on Knowledge Graphs
Arxiv
5+阅读 · 2018年9月6日
Arxiv
3+阅读 · 2017年12月1日
Top
微信扫码咨询专知VIP会员