A Simple yet Effective Method for Graph Classification

1 Introduction

Over the years, deep learning has achieved great success in perception tasks, such as recognizing objects or understanding language, which are difficult for traditional machine learning methods [Bengio et al., 2021]. To further enhance performance, research efforts have generally been devoted to designing more complex models based on previously developed basic ones; such improvements include increasing model depths (e.g., ResNet [He et al., 2016]), integrating more complicated components (e.g., Transformer [Vaswani et al., 2017]) or even both (e.g., GPT3 [Brown et al., 2020] and NAS [Liu et al., 2020]). However, little work has focused on the research direction of boosting performance through simplifying the basic model learning process.

∗Equal Contribuation.

†Correspondence to: Yicheng Pan, Ke Xu.

Similarly, there are many interesting tasks involving graphs that are hard to learn with normal deep learning models, which prefer data with a grid-like structure. Thus, graph neural networks (GNNs) have recently been ubiquitous within deep learning for graphs, and achieve great success in various domains because of their ability to model structural information [Hamilton et al., 2017; Zhang et al., 2018; Xu et al., 2019]. In order to pursuit more superior performance, various more complex components have also been developed and integrated into basic GNNs [Veliˇckovi´c et al., 2018; Ying et al., 2018; Zhang et al., 2018]. In this context, the improvement in performance comes at the price of model complexity, analogous to routines in deep learning. Here, we investigate the feasibility of improving graph classification performance by simplifying model learning. Generally, given a problem, a simpler data structure comes with a simpler algorithm. Motivated by structural entropy [Li and Pan, 2016], a metric designed to assess the structural information of a graph, the essential structure of a graph can be decoded by this metric as a measure of the complexity of its hierarchical structure. Therefore, as shown in Fig. 1, we propose an algorithm to simplify the given data sample of a graph by transforming it into a corresponding coding tree that reflects the hierarchical organization of data, in which the crucial structural information underlying the graph can be retained in the coding tree with minimal structural entropy.

Based on the simplified coding trees, we propose a novel feature combination scheme for graph classification, termed hierarchical reporting. In this scheme, we transfer features from leaf nodes to root nodes based on the hierarchical structures of the associated coding trees. For two kinds of basic learning algorithms (i.e., kernel-based methods and GNNs), we propose two corresponding simplified learning algorithms; put differently, we present an implementation of our scheme in a tree kernel and a convolutional network, denoted the Weisfeiler-Lehman coding tree (WL-CT) kernel and hierarchical reporting network (HRN), to perform graph classification. The tree kernel follows the label propagation in the Weisfeiler-Lehman (WL) subtree kernel but has a lower runtime complexity of O(n). HRN is an implementation of our tree kernel in the deep learning field. Finally, we empirically validate our WL-CT kernel and HRN on various graph classification datasets. Our tree kernel surpasses the state-ofthe-art kernel-based methods and even outperforms GNNs on several benchmarks. Our HRN also achieves state-of-the-art performance on most benchmarks.

We list our contributions in this work as follows:

• We present a novel direction to boost the performance of learning models while reducing complexity.
• With structural entropy minimization, we optimize the given data sample from graphs to coding trees, which are much simpler data structures that also retain the crucial structural information of graphs.
• We develop two efficient learning algorithms, i.e., WLCT and HRN, and empirically present their discriminative power on many graph classification benchmarks.

2 RelatedWork

GNNs have achieved state-of-the-art results on various tasks with graphs, such as node classification [Veliˇckovi´c et al., 2018], link prediction [Zhang and Chen, 2018] and graph classification [Hamilton et al., 2017; Zhang et al., 2018; Xu et al., 2019]. In this work, we devote our attention to graph classification scenarios.

Graph classification involves identifying the characteristics of an entire graph and is ubiquitous in a variety of domains, such as social network analysis [Backstrom and Leskovec, 2011], chemoinformatics [Duvenaud et al., 2015], and bioinformatics [Borgwardt et al., 2005]. In addition to previous techniques such as graph kernels [Shervashidze et al., 2011], GNNs have recently emerged and become a popular way to handle graph-related tasks due to their effective and automatic extraction of graph structural information [Hamilton et al., 2017; Zhang et al., 2018; Xu et al., 2019]. To address the limitations of various GNN architectures, the graph isomorphism network (GIN) [Xu et al., 2019] was presented in theoretical analyses regarding the expressive power of GNNs in terms of capturing graph structures. All GNNs are broadly based on a recursive message passing (or neighborhood aggregation) scheme, where each node recursively updates its feature vector with the "message" propagated from neighbors [Gilmer et al., 2017; Xu et al., 2019]. The feature vector representing an entire graph for graph classification can be obtained by a graph pooling scheme [Ying et al., 2018], such as the summation of all node feature vectors of the graph. Accordingly, much effort has been devoted to exploiting graph pooling schemes, which are applied before the final classification step [Zhang et al., 2018; Ying et al., 2018]. All these pooling methods help models achieve state-of-the-art results but increase the model complexity and the volume of computations.

Structural entropy is a measure of the complexity of the hierarchical structure of a graph [Li and Pan, 2016]. The structural entropy of a graph is defined as the average length of the codewords obtained under a specific coding scheme for a random walk. That is, when a random walk takes one step from node u to node v, the codeword of the longest common ancestor of u and v on the coding tree, which is also their longest common prefix, is omitted. This shortens the average codeword length. Equivalently, the uncertainty of a random walk is characterized by this value, which is the origin of the term structural entropy. The coding tree of a graph that achieves the minimum structural entropy indicates the optimal hierarchical structure. Furthermore, two- and three-dimensional structural entropy, which measure the complexity of two- and three-level hierarchical structures, respectively, have been applied in bioinformatics [Li et al., 2018], medicine [Li et al., 2016b], the structural robustness and security of networks [Li et al., 2016a], etc. For tasks regarding graphs, structural entropy can be used to decode the essential structure as a measure of the complexity of its hierarchical structure.

Thus far, there has been little attention paid to the model promotion and efficiency rising through data sample simplification. In this paper, with the guidance of structural entropy, we investigate the feasibility of improving graph classification performance with lower model complexity.

3 Methodology

In this section, we first introduce an algorithm for graph simplification in which we decode the essential structure of an input graph to the corresponding coding tree by minimizing its structural entropy. Based on the coding trees, we propose a tree kernel and a corresponding implementation in a deep learning model for graph classification. We elaborate on them in the following.

3.1 Graph Simplification via Structural Entropy Minimization

According to the definition in [Li and Pan, 2016], given a graph G = (V, E) and a coding tree T for G, where |V | = n and |E| = m, the structural entropy of G on T is defined as

where vt is a nonroot node in T that also represents a node subset ⊂ V , v+ t refers to the parent node of vt, gvt is the number of edges with exactly one endpoint in vt, and vol(V ) and vol(vt) are the sums of degrees of nodes in V and vt, respectively. The structural entropy of G is defined to be the minimum entropy among all coding trees, and it is denoted by H(G) = minT {HT (G)}.

To formulate a natural coding tree with a certain height, the k-dimensional structural entropy of G for any positive integer k is the minimum value among all coding trees with heights of at most k:

In this paper, to realize the simplification of given graphs with a certain k-dimensional structural entropy, we propose a greedy algorithm to compute the k-dimensional coding tree with minimum structural entropy in Algorithm 1. Specifically, we first build a full-height binary coding tree from an initial coding tree. In this phase, we iteratively merge two nonroot nodes, which can minimize the structural entropy at each step. Then, to form the k-dimensional coding tree T for G, we repeatedly delete one edge from T, which can minimize the structural entropy restoration at each step. Finally, a coding tree T with a certain height k for G can be obtained, where T = (VT , ET ), VT = (V 0 T , . . . , V k T ) and V 0 T = V .

The time complexity of k-dimensional coding tree is O(hmax(m log n + n)), where hmax is the maximum height of coding tree T during the generation of the full-height binary coding tree. Since the minimized structural entropy tends to construct balanced coding trees, hmax is generally of order O(log n). Furthermore, the number of edges of graph is generally greater than the number of nodes, thus the runtime of Algorithm 1 almost scales linearly in the number of edges.

3.2 A Tree Kernel for Graph Classification

To perform classification on coding trees, following the construction of the WL subtree kernel [Shervashidze et al., 2011], we propose a novel tree kernel that measures the similarity between coding trees named the WL-CT kernel. The key difference between the two kernels is the label propagation scheme, where we develop a hierarchical reporting scheme to propagate labels from child nodes to their parents based on the hierarchical structures of coding trees. Finally, our tree kernel adopts the counts of node labels of the entire coding tree as the feature vector of the original graph.

Hierarchical reporting. The key idea of this scheme is to assign labels to nonleaf nodes by aggregating and sorting the labels from their child nodes and then to compress these sorted label sets into new and short labels. Labels from the leaf nodes are iteratively propagated to the root node, which means that the iteration time of this scheme is determined by the height of the coding tree, and naturally avoids the convergence problem of WL subtree kernel.

Algorithm 1 k-dimensional coding tree on structural entropy

Input: a graph G = (V, E), a positive integer k > 1

Output: a k-dimensional coding tree T

• 1: Initialize T with one root node vr and all nodes in V as leaves;
• 2: Define the function merge(vi, vj) for T to insert a new node between vr and (vi, vj);
• 3: Define the function delete(vp, vc) for T to delete vc from T and link vc.children to vp, where vc.parent = vp;
• 4: // Generate the full-height binary coding tree T for G;
• 5: while |vr.children| > 2 do
• 6: Select vi and vj from vr.children, which make argmax(vi ,vj ){HT (G) - HTmerge(vi ,vj ) (G)};
• 7: Execute merge(vi, vj);
• 8: end while
• 9: if Height(T) ≤ k then
• 10: return T ;
• 11: end if
• 12: // Compress T to height k;
• 13: while Height(T ) > k do
• 14: Select vp and vc from T, which make argmin(vp,vc){HTdelete(vp,vc) (G) - HT (G)};
• 15: Execute delete(vp, vc);
• 16: end while
• 17: return T;

Definition 1. Let T1 and T2 be any two coding trees with the same height k. There exists a set of letters Σi ∈ Σ, which are node labels appearing at the i-th (i < k) layer of T1 or T2 (i.e., the nodes with height i are assigned labels with hierarchical reporting). Σ0 is the set of leaf node labels of T1 and T2. Assume that any two Σi are disjoint, and every Σi = {bi1 , . . . , bi|Σi | } is ordered without a loss of generality. We define a function ci : {T1, T2}×Σi → B such that ci (T1, bij ) counts the number of letter bij in coding tree T1.

The tree kernel on the two trees (T1 and T2) with height k after the root nodes are assigned labels is defined as:

where

and

Following the label counting process in the WL subtree kernel, our tree kernel is also designed to count the number of common labels in two coding trees.

Theorem 1. The WL-CT kernel on two coding trees T1 and T2 with the same height k can be computed in time O(n), which is much simpler than the WL subtree kernel (O(hm)) with h iterations on m edges [Shervashidze et al., 2011] and is the method in graph classification with the lowest time complexity to the best of our knowledge [Wu et al., 2020].

Proof. Given a graph G, the runtime of the WL subtree kernel is O(hm) for h iteration, as there are O(m) elements in the multisets of a graph in each WL test iteration. Correspondingly, given a coding tree T for G, the time complexity of the WL-CT kernel is also the total number of elements in the multiset of the coding tree due to the similar label propagation scheme. In addition, the number of elements in the multiset is determined by the number of times that label propagation occurs, which is the edge number |E| = m. Thus, the time complexity of the WL-CT kernel is determined by the number of edges in T. As shown in Algorithm 1, the coding tree T with the most edges is the full-height binary coding tree TB, i.e., O(T) ≤ O(TB). The complexity on the full-height binary coding tree is calculated as:

□

3.3 AConvolutional Network for Graph Classification

Based on our tree kernel, we develop a novel graph convolutional network, HRN, that generalizes the hierarchical reporting scheme to update the hidden features of nonleaf nodes for graph classification. HRN uses the hierarchical structure of coding tree and leaf node features Xv to learn the representation vector of the entire coding tree rT . HRN follows the proposed hierarchical reporting scheme, where the representation of a nonleaf node is updated by aggregating the hidden features of its children. Formally, the i-th layer of HRN is

where riv is the feature vector of node v with height i in the coding tree, r0 v = xv, and C(v) is a set of child nodes of v. As shown in Equation 4, we employ summation and multilayer perceptrons (MLPs) to perform hierarchical reporting in HRN. Sum aggregators have been theoretically proven to be injective over multisets and more powerful than mean and max aggregators [Xu et al., 2019]. MLPs are capable of representing the compositions of functions because of the universal approximation theorem [Hornik et al., 1989; Hornik, 1991].

For graph classification, the root node representation rk v can be naively employed as the representation of the entire coding tree rT . However, as discussed in [Xu et al., 2019], better results could be obtained from features in earlier iterations. To cover all hierarchical information, we employ hidden features from each height/iteration of the model. This is achieved by an architecture similar to the GIN [Xu et al., 2019], where we model the entire coding tree with layer representations concatenated across all heights/layers of the HRN structure:

where riv is the feature vector of node v with height i in coding tree T and k is the height of T. In HRN, LAYERPOOL in Equation 5 can be replaced with the summation or averaging of all node vectors within the same iterations, which generalizes our tree kernel.

4 Experiments

We validate the feasibility of performance improving while simplifying model complexity by comparing the experimental results of the WL-CT kernel and HRN with those of the most popular kernel-based methods and GNNs on graph classification tasks 1 .

Datasets. We conduct graph classification on five benchmarks: three social network datasets (IMDB-BINARY, IMDB-MULTI, and COLLAB) and two bioinformatics datasets (MUTAG and PTC) [Morris et al., 2020] 2 . The data of the bioinformatic datasets and social network datasets differ in that the nodes in bioinformatics graphs have categorical labels that do not exist in social networks. Thus, the initial node labels for the tree kernel are organized as follows: the node degrees are taken as node labels for social networks, whereas the node degrees and node categorical labels are taken according to each bioinformatic dataset. Correspondingly, the initial node features of the HRN inputs are set to one-hot encodings of the node degrees for social networks and a combination of the one-hot encodings of the degrees and categorical labels for bioinformatic graphs. Table 1 summarizes the characteristics of the five employed datasets.

Configurations. Following [Xu et al., 2019], 10-fold crossvalidation is conducted, and we present the average accuracies achieved to validate the performance of our methods in graph classification 3 Regarding the configuration of our tree kernel, we adopt the C-support vector machine (C-SVM) [Chang and Lin, 2011] as the classifier and tune the hyperparameter C of the SVM and the height of the coding tree ∈ [2, 3, 4, 5]. We implement the classification program with an SVM from Scikit-learn, where we set another hyperparameter γ as auto for IMDB-BINARY and IMDB-MULTI and as scale for COLLAB, MUTAG and PTC, and we set the other hyperparameters as their default values.

For configuration of HRN, the number of HRN iterations is consistent with the height of the associated coding trees, which is also ∈ [2, 3, 4, 5]. All MLPs have 2 layers, as in the setting of the GIN. For each layer, batch normalization is applied to prevent overfitting. We utilize the Adam optimizer and set its initial learning rate to 0.01. For a better fit, the learning rate decays by half every 50 epochs. Other tuned hyperparameters for HRN include the number of hidden dimensions ∈ {16, 32, 64}, the minibatch size ∈ {32, 128}, and the dropout ratio ∈ {0, 0.5} after LAYERPOOL. The number of epochs for each dataset is selected based on the best accuracy within cross-validation results. We apply the same layer-level pooling approach (LAYERPOOL in Eq. 5) for HRN; specifically, sum pooling is conducted on the bioinformatics datasets, and average pooling is conducted on the social datasets to ensure a direct comparison with GIN-0.

1 The code of the WL-CT kernel and HRN can be found at https: //github.com/Wu-Junran/HierarchicalReporting.

2 Considering the limitations of coding trees on disconnected graphs, we only adopt datasets that do not contain such graphs.

3 Currently, there have been three kinds of configurations for experimental results; we elaborate on them in Appendix https://github. com/Wu-Junran/HierarchicalReporting/blob/master/appendix.pdf.

Baselines. It is worth noting that recent research efforts have been devoted to the adoption of attention or graph pooling mechanisms, which also sheds light on the path of our future work. However, little attention has been paid to the core part of graph classification models. Therefore, in this paper, we employ models without an attention mechanism or welldesigned graph pooling for a fair comparison. We compare our WL-CT kernel and HRN configured above with several state-of-the-art baselines for graph classification: (1) kernelbased methods, i.e., the WL subtree kernel [Shervashidze et al., 2011] and AWE [Ivanov and Burnaev, 2018]; (2) state-of-the-art deep learning methods, i.e., DCNN [Atwood and Towsley, 2016], PATCHY-SAN [Niepert et al., 2016], DGCNN [Zhang et al., 2018], GIN-0 [Xu et al., 2019] and LP-GNN [Tiezzi et al., 2021]. The accuracies of the WL subtree kernel are derived from [Xu et al., 2019]. For AWE and the deep learning baselines, we utilize the accuracies contained in their original papers.

5 Results

The results of validating the WL-CT kernel and HRN on graph classification tasks are presented in Table 1. Our methods are shown in boldface. In the panel of kernel-based methods, we can observe that the accuracies of the WL-CT kernel exceed those of other kernel-based methods on four out of five benchmarks. For the only failed dataset, MUTAG, the WL-CT kernel still achieves very competitive performance. Notably, the WL-CT kernel even outperforms the state-ofthe-art deep learning method (i.e., GIN-0) on IMDB-MULTI, COLLAB and MUTAG, which implies that superior performance can sometimes be obtained through a traditional machine learning methods rather than a deep learning model.

In the lower panel containing the deep learning methods, we can observe that the results of HRN are naturally superior to the accuracies of the WL-CT kernel, which further confirms the excellent performance of neural networks. In addition, HRN also yields the best performance on three out of five datasets, while competitive performance can still be observed on the other two datasets. In particular, the best performance of HRN is achieved on three social network datasets, which means social networks are more redundant than bioinformatic networks and that the key structure decoded from social networks is more conducive to model learning. In the light of the runtime complexity and experimental accuracies presented above, we can conclude that there is a way to boost the performance with simplified learning algorithms.

Variants of HRN with different LAYERPOOL approaches. In the experimental setup, we employ sum pooling for the bioinformatics datasets and average pooling for social network datasets to ensure a fair comparison with GIN0. However, as described in the paper of GIN, sum pooling on bioinformatics datasets and average pooling on social datasets are adopted due to their better test performance [Xu et al., 2019]. To explore the upper limits of HRN, we adopt various basic pooling approaches for the five benchmarks. In particular, in addition to the adopted sum and average pooling, we also select the hidden feature of the root node as the representation of the entire coding tree, denoted ROOT. The classification accuracies of HRN with three kinds of LAYERPOOL approaches for coding trees under different heights are shown in Table 2. With the exception of PTC and IMDBMULTI, HRN does not achieve the optimal performance for the other three benchmarks with the LAYERPOOL selection of GIN-0. Specifically, HRN obtains the highest accuracies of 77.6% for IMDB-BINARY with sum pooling, 82.2% for COLLAB with ROOT, and 91.4% for MUTAG with average pooling. In particular, the best result of HRN on COLLAB is realized with the root node representation rather than the sum or average pooling designed with skip connections for better performance. The reason for this phenomenon may be that the model overfits the detailed information in the shallow layers, which leads to misjudgment of the global property of graphs, especially considering that the average number of nodes in COLLAB is the largest (see Table 1); specifically, more detailed information is encountered. In summary, these results of HRN with different pooling methods indicate the great potential of HRN in graph representation learning.

The guidance of structural entropy. Despite the state-ofthe-art performance of our methods, we further evaluate the effectiveness of our k-dimensional coding tree algorithm. In particular, we do not form coding trees with the structural entropy minimization but use only a random coding tree, i.e., a randomly balanced binary tree (RBBT) with a height of two. For each graph within datasets, we produce the corresponding RBBT with graph nodes as leaves and employ our designed WL-CT kernel and HRN to perform graph classification (i.e., WL-CT-RBBT and HRN-RBBT). To ensure a fair comparison, we also fix the height of the coding tree to two (i.e., WL-CT-H2 and HRN-H2). The results are shown in Table 3. As can be seen, the structural entropy-guided coding tree surpasses the random coding tree not only on kernelbased methods but also on deep learning methods. The RBBT obtains higher accuracy only on the IMDB-BINARY dataset with kernel-based methods.

The effectiveness of essential structure within graphs. Following the label propagation scheme within the WL subtree kernel [Shervashidze et al., 2011], we present a WL-CT kernel to take full advantage of the hierarchical structure of coding trees and validate its superior performance on five benchmarks. Here, we delve deeper into the effectiveness of the essential structure within graphs. Specifically, we employ those classical graph kernels, including the Core Framework kernel, Neighborhood Hash kernel, ODD-STh kernel, Propagation kernel, Pyramid Match kernel, and Shortest Path kernel, rather than the WL-CT kernel to perform classification. Note that the nonleaf nodes within coding trees are virtual nodes without initial labels; thus, we assign all nonleaf nodes in coding trees with the same label 0. As shown in Table 4, graphs and coding trees have distinct advantages under different kernels, while coding trees can still achieve superior performance even with these kernels designed for graphs with the exception of the core framework kernel, which further confirms that the coding trees decoded by structural entropy minimization are key structures of given graphs.

Computational efficiency. In addition to the lower runtime complexity of our HRN than that of state-of-the-art GNNs (O(n) < O(hm)), we further compare the volumes of computations, i.e., the numbers of floating-point operations per second (FLOPs), required by HRN, GIN-0 and LPGNN-Multi under the same parameter settings on all datasets. Specifically, we fix the number of iterations to four (the five GNN layers of GIN-0 include the input layer), the number of hidden units to 32, the batch size to 128 and the final dropout ratio to 0. The results are shown in Fig. 2. One can see that the volume of computations required by HRN is consistently smaller than that of GIN-0 and LP-GNN-Multi. More concretely, HRN needs only 20% (25%) of the volume of computations needed by the GIN-0 (LP-GNN-Multi) on average.

6 Conclusion

In this paper, we investigate the feasibility of improving graph classification performance while simplifying the learning process. In particular, through structural entropy minimizing, we decode the essential structure of given graphs to a simpler data form, i.e., coding trees. With this optimized new structure, we improve upon the graph classification performance by simplifying the corresponding kernel method and deep learning method. In summary, our proposed WL-CT kernel and HRN are not only theoretically and experimentally much more efficient but also capable of achieving state-ofthe-art performance on most benchmarks. In addition to the excellent graph classification performance, out methods are not fit for another important task in the graph realm, i.e., node classification. Hence, determining how to improve the performance of node classification with a simpler learning model may be another underlying direction for future work.

Acknowledgments

This research was supported by NSFC (Grant No. 61932002).