We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the other two make use of quantum approximate counting, and all of them obtain square-root like speedups over the fastest classical algorithms in various settings. In order to use approximate counting in the context of clustering, we show that for general weighted graphs the performance of spectral clustering is mostly left unchanged by the presence of constant (relative) errors on the edge weights. Finally, we extend the original analysis of motif clustering in order to better understand the role of multiple `anchor nodes' in motifs and the types of relationships that this method of clustering can and cannot capture.


翻译:我们为基于更高顺序模式的组合图提出了三种量子算法,称为“motif 群集 ” 。 一种是直接应用 Grover 搜索,其他两种是使用量子近似计算,它们都获得了平方根,就像在各种情况下最快速的经典算法上的加速。 为了在组合中使用近似计算,我们显示,对于一般加权图来说,光谱集的性能大部分由于边缘重量上存在恒定(相对)错误而没有变化。 最后,我们扩展了对motif 群集的原始分析,以便更好地了解多“锚节点”在运动中的作用以及这种组合方法能够并且无法捕捉到的关系类型。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
专知会员服务
76+阅读 · 2021年3月16日
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
别说还不懂依存句法分析
人工智能头条
23+阅读 · 2019年4月8日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
大数据的分布式算法
待字闺中
3+阅读 · 2017年6月13日
Arxiv
0+阅读 · 2022年1月31日
Arxiv
31+阅读 · 2020年9月21日
Arxiv
3+阅读 · 2020年2月5日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
别说还不懂依存句法分析
人工智能头条
23+阅读 · 2019年4月8日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
大数据的分布式算法
待字闺中
3+阅读 · 2017年6月13日
Top
微信扫码咨询专知VIP会员