Graph clustering is a central topic in unsupervised learning with a multitude
of practical applications. In recent years, multi-view graph clustering has
gained a lot of attention for its applicability to real-world instances where
one has access to multiple data sources. In this paper we formalize a new
family of models, called \textit{multi-view stochastic block models} that
captures this setting.
For this model, we first study efficient algorithms that naively work on the
union of multiple graphs. Then, we introduce a new efficient algorithm that
provably outperforms previous approaches by analyzing the structure of each
graph separately. Furthermore, we complement our results with an
information-theoretic lower bound studying the limits of what can be done in
this model. Finally, we corroborate our results with experimental evaluations.

在无监督学习中，图聚类是一个重要的主题，也有很多实际应用。最近，多视图图聚类因其适用于可访问多个数据源的现实世界实例而受到关注。本文我们正式提出了一种新的模型族，称为 “多视图随机块模型”，用于捕捉这种情况。对于该模型，我们首先研究了在多个图的并集上有效的算法。然后，通过分析每个图的结构，引入了一种新的高效算法，证明其优于先前的方法。此外，我们通过信息理论的下界研究了在该模型中可以实现的极限，并通过实验评估结果证实了我们的结果。

多景随机块模型

Multi-View Stochastic Block Models

Recently there is a growing focus on graph data, and multi-view graph
clustering has become a popular area of research interest. Most of the existing
methods are only applicable to homophilous graphs, yet the extensive real-world
graph data can hardly fulfill the homophily assumption, where the connected
nodes tend to belong to the same class. Several studies have pointed out that
the poor performance on heterophilous graphs is actually due to the fact that
conventional graph neural networks (GNNs), which are essentially low-pass
filters, discard information other than the low-frequency information on the
graph. Nevertheless, on certain graphs, particularly heterophilous ones,
neglecting high-frequency information and focusing solely on low-frequency
information impedes the learning of node representations. To break this
limitation, our motivation is to perform graph filtering that is closely
related to the homophily degree of the given graph, with the aim of fully
leveraging both low-frequency and high-frequency signals to learn
distinguishable node embedding. In this work, we propose Adaptive Hybrid Graph
Filter for Multi-View Graph Clustering (AHGFC). Specifically, a graph joint
process and graph joint aggregation matrix are first designed by using the
intrinsic node features and adjacency relationship, which makes the low and
high-frequency signals on the graph more distinguishable. Then we design an
adaptive hybrid graph filter that is related to the homophily degree, which
learns the node embedding based on the graph joint aggregation matrix. After
that, the node embedding of each view is weighted and fused into a consensus
embedding for the downstream task. Experimental results show that our proposed
model performs well on six datasets containing homophilous and heterophilous
graphs.

提出了一种自适应混合图滤波方法（AHGFC）用于多视图图聚类，通过设计图联合处理和聚合矩阵，以使图中的低频和高频信号更可区分，进而基于图联合聚合矩阵学习节点嵌入，实验证明该方法在同质和异质图上表现出色。