In deep neural networks, better results can often be obtained by increasing
the complexity of previously developed basic models. However, it is unclear
whether there is a way to boost performance by decreasing the complexity of
such models. Intuitively, given a problem, a simpler data structure comes with
a simpler algorithm. Here, we investigate the feasibility of improving graph
classification performance while simplifying the learning process. Inspired by
structural entropy on graphs, we transform the data sample from graphs to
coding trees, which is a simpler but essential structure for graph data.
Furthermore, we propose a novel message passing scheme, termed hierarchical
reporting, in which features are transferred from leaf nodes to root nodes by
following the hierarchical structure of coding trees. We then present a tree
kernel and a convolutional network to implement our scheme for graph
classification. With the designed message passing scheme, the tree kernel and
convolutional network have a lower runtime complexity of $O(n)$ than
Weisfeiler-Lehman subtree kernel and other graph neural networks of at least
$O(hm)$. We empirically validate our methods with several graph classification
benchmarks and demonstrate that they achieve better performance and lower
computational consumption than competing approaches.

通过将图数据样本转换为编码树以及使用分层传递机制，提出了一种树内核和卷积网络来实现图分类，其时间复杂度低于其他图神经网络，同时验证表明其在性能和计算资源方面均优于其他方法。