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.

藉由引入消息绕行概念，本研究在整个图中 hierarchically 描述周期表示，以解决计算高阶拓扑特征所面临的挑战，并展示其在图学习领域的较低计算要求下与高阶 Weisfeiler-Lehman (WL) 测试相当的表达能力。此外，本研究结合了图核和消息传递神经网络，提出了一种新颖的消息绕行神经网络，采用 Transformer 骨干在节点和边之间整合周期表示。除了理论结果外，基于各种基准数据集的实验结果表明，消息绕行在表达能力、图分类和节点分类方面明显优于当前现有方法。