Clustering Graphs Using Minimum Factorization Distance

Jicong Fan

doi:10.1109/tpami.2026.3747791

Clustering Graphs Using Minimum Factorization Distance

2026-10-27

0

PRE

AI

J

Jicong Fan

DOI：10.1109/tpami.2026.3747791

原文链接

摘要

En 中文

将图聚类到不同组别是一个具有挑战性的问题，由于难以量化图之间的相似性或距离，尤其是在图规模较大的情况下。在本文中，我们提出了一种新颖的方法，将两个图的邻接矩阵视为源自某个未知不定核函数应用于两个离散分布的核矩阵。基于此观点，我们定义了一种称为MMFD的度量来通过图的基础分布之间的距离量化图之间的不相似性。我们证明了MMFD是一个伪度量。尽管MMFD的初始表述看似复杂，但我们证明了它具有计算简单的闭式解。为提高大规模聚类任务的效率，我们进一步提出了MMFD-KM方法，其时间复杂度和空间复杂度相对于图的数目呈线性。此外，我们引入了广义版本MFD及其变体MFD$_{\rm{OT}}$，具有理论保证，能更有效地利用邻接矩阵中的因子信息。基于MFD，建立了一种高效的图聚类算法MFD-KD。在合成图上的实验直观地证实了我们的方法在图比较中的有效性。在18个真实数据集上的结果表明，我们的方法在三个评估指标上的聚类性能显著优于竞争方法，同时减少了计算时间。

Keyword:

Clustering

graph learning

unsupervised learning

Clustering Graphs Using Minimum Factorization Distance

摘要

期刊

机构

引用论文