Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around a given set of seed nodes. Popular and principled ways to capture the local structure are the local hypergraph clustering problem and related seed set expansion problem. In this work, we propose the first local diffusion method that achieves edge-size-independent Cheeger-type guarantee for the problem of local hypergraph clustering while applying to a rich class of higher-order relations that covers many previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has a natural network flow interpretation, and the dual problem has a cut-based interpretation using the $\ell_2$-norm penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-the-art methods on both synthetic and real-world data.


翻译:最近,高音由于能够捕捉各实体之间的复杂关系而引起人们的极大关注。高音暴发后,出现了规模和复杂性不断增大的数据,显示出有趣的小型和地方结构,例如小型社区和围绕一组种子节点的局部节点。捕捉当地结构的流行和有原则的方法是当地高音集聚问题和相关的种子集成扩展问题。在这项工作中,我们提议了第一个本地传播方法,即对本地高音集成问题实现边缘大小独立的Cheeger型担保,同时对以前研究过的许多特殊案例适用丰富的高音集成型关系。我们的方法基于原始-双优化配制,其中原始问题具有自然网络流动解释,而双重问题则使用对相关削减成本的$_2美元-诺姆罚款进行剪切解释。我们证明新技术比合成和现实世界数据方面的最新方法要好得多。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Type-augmented Relation Prediction in Knowledge Graphs
Arxiv
3+阅读 · 2020年2月5日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
VIP会员
相关VIP内容
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员