Message Detouring: A Simple Yet Effective Cycle Representation for
  Expressive Graph Learning
Ziquan Wei Tingting Dan Guorong Wu
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.