Commute Graph Neural Networks
This addresses a specific problem in graph learning for directed graphs, offering a novel method for handling asymmetrical node relationships, though it is incremental in improving existing GNN frameworks.
The paper tackles the challenge of applying Graph Neural Networks (GNNs) to directed graphs by introducing Commute Graph Neural Networks (CGNN), which integrates node-wise commute time into message passing to capture mutual, asymmetric relationships, achieving superior performance on 8 benchmarking datasets against 13 state-of-the-art methods.
Graph Neural Networks (GNNs) have shown remarkable success in learning from graph-structured data. However, their application to directed graphs (digraphs) presents unique challenges, primarily due to the inherent asymmetry in node relationships. Traditional GNNs are adept at capturing unidirectional relations but fall short in encoding the mutual path dependencies between nodes, such as asymmetrical shortest paths typically found in digraphs. Recognizing this gap, we introduce Commute Graph Neural Networks (CGNN), an approach that seamlessly integrates node-wise commute time into the message passing scheme. The cornerstone of CGNN is an efficient method for computing commute time using a newly formulated digraph Laplacian. Commute time is then integrated into the neighborhood aggregation process, with neighbor contributions weighted according to their respective commute time to the central node in each layer. It enables CGNN to directly capture the mutual, asymmetric relationships in digraphs. Extensive experiments on 8 benchmarking datasets confirm the superiority of CGNN against 13 state-of-the-art methods.