A Simple yet Effective Method for Graph Classification

Junran Wu, Shangzhe Li, Jianhao Li, Yicheng Pan, Ke Xu

Abstract

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.

Introduction

Graph classification is a fundamental task in machine learning, with applications ranging from drug discovery to social network analysis. Traditionally, this task is handled by Graph Neural Networks (GNNs) or graph kernels that rely on iterative message passing between neighboring nodes. While effective, these methods often suffer from high computational complexity, typically $O(hm)$ where $m$ is the number of edges and $h$ is the number of iterations. As researchers strive for higher accuracy, models have become increasingly complex, incorporating attention mechanisms and sophisticated pooling layers, further driving up computational costs.

This research challenges the "complexity for performance" paradigm. Instead of building more intricate models, the authors propose simplifying the underlying data representation. By transforming complex graphs into streamlined "coding trees," they enable a more efficient learning process that achieves state-of-the-art results with significantly reduced overhead.

Methodology: From Graphs to Coding Trees

The core of the proposed approach is a two-step process: graph simplification and hierarchical reporting.

Structural Entropy Minimization

The first step involves converting the input graph into a coding tree. This transformation is guided by the principle of structural entropy minimization. Structural entropy quantifies the complexity of a graph's hierarchical organization. By finding a tree structure that minimizes this entropy, the method extracts the essential hierarchical features of the graph while discarding redundant information.

Overview of the graph classification pipeline: from raw graph data to label prediction via coding tree transformation.

Hierarchical Reporting

With the coding tree established, the authors introduce Hierarchical Reporting, a novel message-passing scheme. Unlike standard GNNs where information flows across a complex web of edges, features in this scheme are transferred strictly from leaf nodes up to the root node along the tree's branches. This structured flow reduces the runtime complexity to $O(n)$, where $n$ is the number of nodes, making it particularly efficient for dense graphs.

The researchers implemented this scheme through two primary models:

  1. WL-CT (Weisfeiler-Lehman Coding Tree) Kernel: A tree-based adaptation of the classic WL graph kernel.
  2. HRN (Hierarchical Reporting Network): A convolutional neural network specifically designed to operate on coding trees.

Experimental Evaluation

The proposed methods were evaluated on five standard graph classification benchmarks, including social networks (IMDB-BINARY, IMDB-MULTI, COLLAB) and bioinformatics datasets (MUTAG, PTC). These datasets provide a diverse testing ground, from small molecular structures to large-scale social interactions.

Performance and Efficiency

The results demonstrate that simplification does not come at the cost of accuracy. The WL-CT kernel outperformed traditional graph kernels on four out of five datasets. Meanwhile, the HRN achieved state-of-the-art performance on three benchmarks, surpassing more complex models like GIN-0.

The most significant advantage, however, is computational efficiency. The HRN requires substantially fewer floating-point operations (FLOPs) than its competitors. For instance, on the COLLAB dataset, the computational volume is drastically lower than that of GIN-0 or LP-GNN-Multi.

Computational efficiency comparison on the COLLAB dataset, highlighting the significantly lower FLOPs/Batch required by the proposed method (red bar).

Discussion and Conclusion

The success of coding trees suggests that they successfully capture the most critical structural features of graphs. This is especially evident in social network datasets, where the hierarchical structure decoded by structural entropy appears highly conducive to learning.

While the current approach is limited to connected graphs and focused on graph-level classification, it opens new avenues for research. Future work could extend these principles to node-level tasks or incorporate advanced mechanisms like attention into the Hierarchical Reporting Network. Ultimately, this work proves that simplifying the learning process can be a powerful strategy for improving both the performance and efficiency of graph-based models.

Summary updated

Abstract

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.
BibTeX
@inproceedings{wu2022simple,
  author = {Junran Wu and Shangzhe Li and Jianhao Li and Yicheng Pan and Ke Xu},
  title = {{A Simple yet Effective Method for Graph Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/497},
}
Figure