Learning Mixed Membership from Adjacency Graph Via Systematic Edge Query: Identifiability and Algorithm
Learning Mixed Membership from Adjacency Graph Via Systematic Edge Query: Identifiability and Algorithm
复制标题
DOI：
10.1109/icassp39728.2021.9413541
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Shahana Ibrahim;Xiao Fu
中科院分区：
文献类型：
--
作者：
Shahana Ibrahim;Xiao Fu
图群集是用于网络分析问题的核心技术，例如社区检测。这项工作为在很大程度上不完整的邻接图提供了一种节点聚类方法。在考虑的情况下，只能对图形边缘进行少量查询，以进行节点群集。在许多大规模网络分析问题中，这项任务激励了，在这些问题中，完整的图形获取的成本高昂。在节点仅接纳单个成员资格和群集是不相交的情况下，以前的工作解决了这个问题，但是在实践中通常会出现多个会员节点和重叠的群集。现有方法还依赖于随机边缘查询模式和基于凸优化的配方，这会引起许多实现和可伸缩性挑战。这项工作提供了一个框架，可证明使用有限的边缘信息从重叠的群集中学习了节点的混合成员资格。我们的方法配备了系统的边缘查询模式，相对于某些应用程序（例如基于现场调查的图形分析），相对于随机对应物的实现可以说是更易于实现的。提出了轻巧的可伸缩算法，并提出了其性能特征。数值实验用于展示我们方法的有效性。
Graph clustering is a core technique for network analysis problems, e.g., community detection. This work puts forth a node clustering approach for largely incomplete adjacency graphs. Under the considered scenario, instead of having access to the complete graph, only a small amount of queries about the graph edges can be made for node clustering. This task is well-motivated in many large-scale network analysis problems, where complete graph acquisition is prohibitively costly. Prior work tackles this problem under the setting that the nodes only admit single membership and the clusters are disjoint, yet multiple membership nodes and overlapping clusters often arise in practice. Existing approaches also rely on random edge query patterns and convex optimization-based formulations, which give rise to a number of implementation and scalability challenges. This work offers a framework that provably learns the mixed membership of nodes from overlapping clusters using limited edge information. Our method is equipped with a systematic edge query pattern, which is arguably easier to implement relative to the random counterparts in certain applications, e.g., field survey based graph analysis. A lightweight scalable algorithm is proposed, and its performance characterizations are presented. Numerical experiments are used to showcase the effectiveness of our method.