An MBO scheme for clustering and semi-supervised clustering of signed networks
An MBO scheme for clustering and semi-supervised clustering of signed networks
复制标题
DOI：
10.4310/cms.2021.v19.n1.a4
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Mihai Cucuringu;A. Pizzoferrato;Y. Gennip
中科院分区：
文献类型：
--
作者：
Mihai Cucuringu;A. Pizzoferrato;Y. Gennip
我们介绍了一个原则性的方法，签署的聚类问题，其目标是分区的边权重采取正值和负值的图，这样，在同一个集群内的边缘大多是积极的，而跨集群的边缘大多是负面的。我们的方法依赖于一个基于图形的扩散界面模型制定利用金斯堡-朗道功能，基于经典的数值梅里曼-本斯-奥舍（MBO）计划的适应，以尽量减少这种基于图形的泛函。提出的目标函数旨在最小化簇间正加权边的总权重，同时最大化簇间负加权边的总权重。我们的方法可以扩展到大型稀疏网络，并且可以很容易地调整以包含标记的数据信息，这在半监督学习的背景下通常是这样。我们在一些合成随机块模型和真实世界的数据集（包括金融相关矩阵）上测试了我们的方法，并获得了与最近文献中的一些最先进的方法相媲美的有希望的结果。
We introduce a principled method for the signed clustering problem, where the goal is to partition a graph whose edge weights take both positive and negative values, such that edges within the same cluster are mostly positive, while edges spanning across clusters are mostly negative. Our method relies on a graph-based diffuse interface model formulation utilizing the Ginzburg-Landau functional, based on an adaptation of the classic numerical Merriman-Bence-Osher (MBO) scheme for minimizing such graph-based functionals. The proposed objective function aims to minimize the total weight of inter-cluster positively-weighted edges, while maximizing the total weight of the inter-cluster negatively-weighted edges. Our method scales to large sparse networks, and can be easily adjusted to incorporate labelled data information, as is often the case in the context of semi-supervised learning. We tested our method on a number of both synthetic stochastic block models and real-world data sets (including financial correlation matrices), and obtained promising results that compare favourably against a number of state-of-the-art approaches from the recent literature.