Finding Cheeger cuts in hypergraphs via heat equation
Finding Cheeger cuts in hypergraphs via heat equation
复制标题
通过热方程求超图中的 Cheeger 割
DOI：
10.1016/j.tcs.2022.07.006
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Yoshida Yuichi
中科院分区：
文献类型：
--
作者：
Ikeda Masahiro;Miyauchi Atsushi;Takai Yuuki;Yoshida Yuichi
Cheeger不等式指出，可以使用与G相关联的归一化拉普拉斯算子的特征向量从图G中提取紧连通子集。更具体地说，我们可以计算G中电导为O（G）的顶点子集，其中G是G的最小电导。最近的研究表明，Cheeger不等式可以推广到超图。然而，由于超图的归一化拉普拉斯算子不再是矩阵，我们只能近似其特征向量;这导致所获得子集的电导损失。为了解决这个问题，我们在这里考虑超图上的热方程，这是一个利用归一化拉普拉斯算子的微分方程。我们证明了热方程有唯一的整体解，并且在一个温和的条件下，我们可以从解中提取出一个具有电导率的子集。一个类似的结果也适用于有向图。
Cheeger's inequality states that a tightly connected subset can be extracted from a graph G using an eigenvector of the normalized Laplacian associated with G. More specifically, we can compute a vertex subset in G with conductance O (ϕ G), where ϕ G is the minimum conductance of G. It has recently been shown that Cheeger's inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique global solution and that we can extract a subset with conductance ϕ G from the solution under a mild condition. An analogous result also holds for directed graphs.