A Simple yet Effective Method for Graph Classification

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

Introduction

In the rapidly evolving field of Graph Neural Networks (GNNs), the prevailing trend has been toward increasing model complexity. To achieve better performance, researchers often add more layers, complex attention mechanisms, or sophisticated pooling schemes. However, this "bigger is better" approach comes with a significant computational cost. This paper challenges that paradigm by asking a provocative question: Can we boost performance by decreasing model complexity?

The authors identify that graphs are inherently complex, non-grid structures often riddled with "noise" that makes efficient processing difficult. By simplifying graph data into hierarchical coding trees through the minimization of structural entropy, they extract the essential structural backbone of a graph. This approach enables new algorithms that achieve state-of-the-art accuracy while requiring only a fraction of the computational resources used by standard GNNs.

Methods: Structural Entropy and Coding Trees

The core of the proposed framework is Structural Entropy, a metric designed to measure the complexity of a graph’s hierarchical organization. The methodology follows a three-step pipeline to transform raw graph data into a format suitable for efficient learning.

  1. Graph Simplification: Using a greedy algorithm, the raw graph is transformed into a "coding tree." This tree is optimized to minimize structural entropy, effectively capturing the graph's most critical hierarchical community structure while stripping away redundant information.
  2. Hierarchical Reporting: Instead of the standard messy message-passing between neighbors, the authors propose a structured scheme. Features are transferred from leaf nodes (the original graph nodes) up through the hierarchy to the root of the coding tree.
  3. Algorithmic Implementation: Two new algorithms are introduced:
  4. WL-CT (Weisfeiler-Lehman Coding Tree) Kernel: A kernel-based method that counts common labels in coding trees with a runtime complexity of $O(n)$, making it significantly faster than traditional subtree kernels.
  5. HRN (Hierarchical Reporting Network): A deep learning model that utilizes Multi-Layer Perceptrons (MLPs) and sum-aggregation to learn representations directly from the coding tree structure.
The proposed framework for graph classification using structural entropy minimization and coding trees.

Key Results and Insights

The researchers evaluated their methods on five standard benchmarks, including social networks (IMDB-BINARY, IMDB-MULTI, COLLAB) and bioinformatics datasets (MUTAG, PTC). The results highlight a powerful synergy between simplicity and performance.

Accuracy and Efficiency

The HRN model achieved state-of-the-art or highly competitive results across all benchmarks. Notably, it outperformed the popular Graph Isomorphism Network (GIN) on social network datasets. The most striking finding, however, is the efficiency gain. Because these algorithms operate on trees rather than general graphs, the runtime complexity drops to $O(n)$.

Empirical data shows that HRN is incredibly lean, requiring only about 20% to 25% of the Floating Point Operations (FLOPs) needed by models like GIN-0 or LP-GNN to achieve comparable or superior results.

Comparison of computational complexity (FLOPs/Batch) across different datasets.

The Role of Entropy

The authors demonstrated that the specific structure of the tree matters. Using a Random Balanced Binary Tree (RBBT) resulted in poorer performance than entropy-minimized coding trees. This confirms that structural entropy successfully captures the "meaningful" hierarchical parts of the graph, acting as a guide to avoid overfitting to noise.

Conclusion and Future Directions

This research proves that simplifying a graph to its essential hierarchical structure can lead to models that are both more accurate and significantly more efficient. By moving away from the complexity of general graph message-passing and toward structured hierarchical reporting, the HRN and WL-CT methods set a new standard for resource-conscious graph classification.

While highly effective for classification, the current approach has limitations with disconnected graphs. Future work may explore extending this "simplification" philosophy to node classification and dynamic graphs that change over time, potentially bringing the benefits of structural entropy to a wider array of graph-based challenges.

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