Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural Networks-猫眼课题宝

DOI：

10.1609/aaai.v35i5.16590

发表时间：

2020-12

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Yuhang Yao;Carlee Joe-Wong

我们研究了动态图中节点的聚类问题，其中节点之间的连接和节点的聚类成员资格可能会随着时间的推移而变化，例如，由于社区移民。我们首先提出了一个动态的随机块模型，捕捉这些变化，和一个简单的基于衰减的聚类算法，集群节点之间的加权连接的基础上，其中的权重随着时间的推移以固定的速度下降。这个衰减率可以被解释为表示在聚类中包括历史连接信息的重要性。然而，对于具有不同周转率的簇，最佳衰减率可能不同。我们表征每个集群的最佳衰减率，并提出了一种聚类方法，实现几乎精确的恢复真正的集群。然后，我们证明了我们的聚类算法的有效性与优化的衰减率模拟图形数据。递归神经网络（RNN）是一种流行的序列学习算法，使用类似的基于衰减的方法，我们利用这一见解提出了两种新的RNN-GCN（图卷积网络）架构，用于半监督图聚类。我们最后证明，所提出的架构表现良好的真实的数据相比，国家的最先进的图聚类算法。

We study the problem of clustering nodes in a dynamic graph, where the connections between nodes and nodes' cluster memberships may change over time, e.g., due to community migration. We first propose a dynamic stochastic block model that captures these changes, and a simple decay-based clustering algorithm that clusters nodes based on weighted connections between them, where the weight decreases at a fixed rate over time. This decay rate can then be interpreted as signifying the importance of including historical connection information in the clustering. However, the optimal decay rate may differ for clusters with different rates of turnover. We characterize the optimal decay rate for each cluster and propose a clustering method that achieves almost exact recovery of the true clusters. We then demonstrate the efficacy of our clustering algorithm with optimized decay rates on simulated graph data. Recurrent neural networks (RNNs), a popular algorithm for sequence learning, use a similar decay-based method, and we use this insight to propose two new RNN-GCN (graph convolutional network) architectures for semi-supervised graph clustering. We finally demonstrate that the proposed architectures perform well on real data compared to state-of-the-art graph clustering algorithms.

Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural Networks

文献摘要

相似文献