Message Detouring: A Simple Yet Effective Cycle Representation for Expressive Graph Learning
This addresses a computational bottleneck in graph learning for applications like bioinformatics and social networks, offering an incremental improvement in efficiency and performance.
The paper tackles the computational challenge of modeling high-order graph structures like cycles for graph learning by introducing message detouring, a method that hierarchically characterizes cycle representation using contrasts between shortest and longest pathways, achieving comparable expressiveness to high-order Weisfeiler-Lehman tests with lower computational demands and outperforming current approaches on benchmark datasets for graph and node classification.
Graph learning is crucial in the fields of bioinformatics, social networks, and chemicals. Although high-order graphlets, such as cycles, are critical to achieving an informative graph representation for node classification, edge prediction, and graph recognition, modeling high-order topological characteristics poses significant computational challenges, restricting its widespread applications in machine learning. To address this limitation, we introduce the concept of \textit{message detouring} to hierarchically characterize cycle representation throughout the entire graph, which capitalizes on the contrast between the shortest and longest pathways within a range of local topologies associated with each graph node. The topological feature representations derived from our message detouring landscape demonstrate comparable expressive power to high-order \textit{Weisfeiler-Lehman} (WL) tests but much less computational demands. In addition to the integration with graph kernel and message passing neural networks, we present a novel message detouring neural network, which uses Transformer backbone to integrate cycle representations across nodes and edges. Aside from theoretical results, experimental results on expressiveness, graph classification, and node classification show message detouring can significantly outperform current counterpart approaches on various benchmark datasets.