摘要

本文介绍了一种名为Commute Graph Neural Networks (CGNN)的新型图神经网络，专门用于处理有向图（digraphs）中的学习问题。CGNN通过将有向图中的节点通勤时间（commute time）信息整合到消息传递机制中，有效地捕捉了节点间的相互不对称关系。传统的图神经网络在处理有向图时，主要捕捉单向关系，而忽略了路径不对称性带来的复杂性。CGNN通过一种新型的有向图拉普拉斯（DiLap）计算通勤时间，并将其应用于邻居聚合过程中，根据邻居节点到中心节点的通勤时间来加权邻居的贡献。实验结果表明，CGNN在多个有向图数据集上取得了最先进的性能。

原理

CGNN的核心创新在于将有向图中的通勤时间信息融入到图神经网络的消息传递过程中。通勤时间是指从源节点到目标节点再返回的预期步数，这一概念从马尔可夫链理论中借鉴而来。首先，通过定义有向图的拉普拉斯算子DiLap，CGNN能够有效地计算通勤时间。DiLap是通过将有向图的转移矩阵融入到传统的图拉普拉斯中来实现的，确保了在有向图结构中测量信号的局部平滑度。然后，CGNN将基于通勤时间的接近度量引入到消息传递过程中，通过为邻居分配聚合权重，使得直接和单向的邻居关系不一定意味着强相似性，但相互接近度是关系紧密性的更可靠指标。

流程

CGNN的工作流程包括以下几个关键步骤：

1. 计算锚点（anchor）和节点-锚点相似性，构建一个简单的、可约的图G′，然后将G′的所有边添加到原始有向图G中，确保G的可约性。
2. 计算G的加权DiLap �T。
3. 计算R及其摩尔-彭罗斯伪逆（Moore-Penrose pseudoinverse）。
4. 计算通勤时间矩阵C。
5. 计算归一化接近度矩阵�C。
6. 进行L层的消息传递，每层中根据�Cout和�Cin进行邻居聚合。
7. 通过多层感知机（MLP）处理最后一层的输出，然后通过Softmax函数得到最终的节点分类预测。

应用

CGNN在处理有向图数据时表现出色，特别适用于那些节点间关系具有明显方向性和不对称性的应用场景，如社交网络分析、推荐系统、知识图谱等。由于CGNN能够更准确地捕捉节点间的相互关系，它在这些领域的应用有望提高模型的预测精度和鲁棒性。