A Simple yet Effective Method for Graph Classification
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.