GraphDIVE: Graph Classification by Mixture of Diverse Experts

1 Introduction

Graph classification aims to identify the class label of each graph in a dataset, which is a critical and challenging problem for a broad range of real-world applications, such as drug discovery, text classification, and disease diagnosis. For instance, in chemistry, a molecule can be represented as a graph, where nodes denote atoms, and edges represent chemical bonds. Correspondingly, the classification of molecular graphs can help predict target molecular properties [Hu et al., 2020].

As a powerful approach to graph representation learning, Graph Neural Network (GNN) models have been widely applied in the graph classification task [Ying et al., 2018; Xu et al., 2019]. Despite the huge success of GNNs, we find that the performances of current GNN models are largely hindered by the imbalanced class distribution, which is ubiquitous in practical applications. For example, in OGBGMOLHIV dataset [Hu et al., 2020], only about 3.5% of molecules can inhibit HIV virus replication. Figure 1 presents graph classification results of GCN [Kipf and Welling, 2017] and GIN [Xu et al., 2019] on this dataset. Considering either the test accuracy or cross-entropy loss, we observe the notorious prediction bias phenomenon [Zhou et al., 2020]: the classification performance of the minority class falls far behind that of the majority class. Apparently, the low performance of minority class hinders the overall performance of GNNs.

∗The first two authors contributed equally to this work.

†To whom correspondence should be addressed.

A straightforward solution to boost the performance of GNNs is to apply existing imbalanced learning methods, which can be divided into three categories [Liu et al., 2020]: re-sampling, re-weighting, and mixture of experts. However, these imbalanced learning methods are initially designed for Euclidean data (such as images and texts) and they cannot model the influence of topological structure. In graph classification scenario, it is widely acknowledged that the topological structure of graphs has a significant impact on the classification performance [Xu et al., 2019]. In other words, some structures might be closely related to the majority class while some other structures usually associate with the minority class. As a result, it is interesting to investigate whether and how the topological structure influences the imbalanced graph classification (IGC) problem.

To this end, we propose a novel Graph classification network with DIVerse Experts, dubbed as GraphDIVE for brevity. Among re-weighting, re-sampling, and mixture of experts (MoE) methods, we mainly investigate MoE-based methods in this paper considering the compatibility of MoE with neural networks [Jacobs et al., 1991]. To be more specific, both MoE and topological structure are related to the graph representation learning process. Therefore, we can mine the relationship between topological structure and class imbalance. In contrast, re-weighting and re-sampling is only related with the loss function and the selection of input sample, which makes it difficult to investigate the effect of topological structure. MoE is known to effectively improve typical imbalanced learning by combining the outputs of multiple experts [Dong et al., 2020]. Here, each expert refers to a classifier. The success of MoE methods rely largely on the dissimilarity of experts [Kuncheva and Whitaker, 2003; Cunningham and Carney, 2000]. To further encourage the dissimilarity of experts and investigate the effect of topological structure, we propose to extract multi-view graph representations and combine multi-view experts. Specifically, when learning multi-view graph representations, the intrinsic diverse topological characteristics across the graph are also captured by GraphDIVE.

The architecture of GraphDIVE is depicted in Figure 2. At first, GraphDIVE learns diverse representations from node and graph levels. At each level, the learning process is controlled by two hyper-parameters: α and p, where α controls the effect of topological structure and p controls the distribution of the graph representation. By setting different values to these two hyper-parameters, we can obtain diverse graph representations, which are fed into multi-view experts to make a more accurate prediction.

To sum up, the main contributions of this work are:

• To the best of our knowledge, we are probably the first to highlight the critical importance of considering class imbalance when designing GNNs for graph classification task.
• We investigate the effect of topological structure to IGC. We propose a novel graph neural network which extracts multi-view graph representations and combines multiview experts.
• Extensive experiments on four class imbalance molecular datasets demonstrate that GraphDIVE outperforms other state-of-the-art methods.

To foster reproducible research, our code is made publicly available at https://github.com/CRIPAC-DIG/DIVE.

2 RelatedWork

2.1 Imbalance Learning

Existing imbalance learning methods can be roughly divided into three types [Liu et al., 2020]: re-sampling, re-weighting, and mixture of experts.

Re-sampling methods try to alleviate the imbalanced class distribution issue by controlling each class's sample frequencies. It can be achieved by over-sampling or under-sampling [Chawla et al., 2002]. Nevertheless, traditional random sampling methods usually cause over-fitting in minority classes or under-fitting in majority classes. Re-weighting methods generally assign different weights to different samples. However, these methods re-weight classes proportionally to the inverse of the class frequency, which tends to make optimization difficult under extremely imbalanced settings [Huang et al., 2016]. Meanwhile, we notice that Pan et al. [Pan and Zhu, 2013] assign different weights to graphs. But they do not consider GNN for imbalanced classification, therefore not in scope of our study. Mixture of Experts (MoE) is a wellstudied research topic, which is also usually under a different name: classifier ensembles [Dong et al., 2020]. MoE is mainly based on divide-and-conquer principle, in which the problem space is first divided and then is addressed by specialized experts [Jacobs et al., 1991]. Different from above existing MoE methods that rely on a single view of representation, GraphDIVE is specially designed for graph data and explicitly explores diverse multi-view graph representations.

3 Preliminary

3.1 ProblemDescription

Let D = {(G1,Y1), . . . , (Gn,Yn)} denote training data, where Gi = (Ai,Xi) denotes a graph containing the adjacency matrix and the node attribute matrix. Yi represents the labels of Gi. The task of graph classification is to learn a mapping f : Gi →Yi. Under imbalanced classification setting, the number of instances of majority classes is far more than that of minority classes. The imbalanced graph classification (IGC) problem exists widely in practical applications, such as drug discovery, text classification and disease diagnosis.

3.2 MoE-based Imbalanced Learning

MoE is established based on Divide-and-Conquer (D&C) principle. Specifically, the problem space is first partitioned stochastically into a number of subspaces, then several experts are leveraged and become specialized on each subspace [Jacobs et al., 1991]. The partition process is controlled by a gating network, which is trained together with the experts. Such a D&C mechanism is formulated as:

where x is the learned representation of a sample and y denotes the label. Θ denotes learnable parameters of gating network and expert networks. z ∈ {1, 2, . . . ,M} is a latent variable indicating expert index, and M is the number of experts. Besides, ∑Mz=1 p(z|x;Θ) = 1 and p(z|x;Θ) is the output of the gating network, indicating the probability of assigning x to the z-th expert. p(y|z, x;Θ) represents output distribution of the z-th expert.

For imbalanced learning, since using one shared classifier will inevitably lead to prediction bias towards majority classes [Zhou et al., 2020], MoE methods assign different experts for different clusters instead. Here, each cluster contains semantically-close instances, and the distinction of different clusters is achieved by the gating function. Specifically, for instances of minority classes, the gating function assigns larger weights to some certain experts. Therefore, these experts become specialized on minority classes. Similarly, there are some other experts specialized on majority classes. As a result, the diversity of experts is a key factor for the success of MoE methods [Kuncheva and Whitaker, 2003].

4 ProposedMethod

In this section, we present the details of the proposed Graph classification network with DIVerse Experts (GraphDIVE). Existing work [Kuncheva and Whitaker, 2003; Cunningham and Carney, 2000] have found that the diversity of experts is a key factor for the success of MoE methods. Nevertheless, as formulated in Eq. (1), the experts of canonical MoE methods are based on only one shard representation, which might hinder the diversity of experts. Inspired by the development of multi-view learning [Xu et al., 2013], we propose to learn multi-view graph representations to boost the diversity of experts, with the overview presented in Figure 2. GraphDIVE learns diverse graph representations from both node-level and graph-level. This corresponds to intrinsic diverse graph topological structure characteristics. Specifically, from node-level perspective, different nodes have different numbers of adjacent neighbors. From global level, different sub-graphs (motifs) recur in a graph with different frequencies. These subgraphs are also combined in a rather complex way. As a result, multi-view graph representations can not only encourage the diversity of experts, but also capture diverse topological structure characteristics. We will introduce the details of GraphDIVE as follows.

4.1 Diverse Node-level Aggregators

To obtain diverse graph representations, we first design diverse node-level aggregators. This is reasonable, since only after diverse node-level characteristics are obtained, can distinct graph-level representations be captured. The diverse node-level aggregators are defined as follows:

where xki indicates the representation of the i-th node at the k-th iteration, and Ni is the set of nodes adjacent to node i as well as itself. wj denotes the importance weight of neighbor node j, and αl is a hyper-parameter controlling the effect of wj. ci denotes bias and pl controls the distributions of the output embeddings. Notably, the subscript l is used to distinguish α and p from those in Eq. (4). Next, we present the approach of computing wj and pl in detail.

Structure-aware Node Weighting

GraphDIVE assigns different weights to different nodes according to the topological structure. It is well known that neighbor nodes contribute differently in neighborhood aggregation process [Veliˇckovi´c et al., 2018]. Since topological structure plays a crucial role in GNNs, we propose to weight different nodes considering topological structure. In graph theory and network science, node degree is a popular indicator that judges the importance of nodes in the graph. It is defined as the number of adjacent neighbors upon a node. Considering node centrality values may vary across orders of magnitude [Newman, 2018], we set wj = log(1 + dj)/δ to alleviate the impact of nodes with extremely dense connections. Specifically, δ = 1 | train | ∑i∈ train log (di +1) denotes the average degree of the training data.

Besides, αl ∈ {0, 1} controls the effect of importance weighting. Specifically, when αl equals to 0, GraphDIVE aggregates the information from neighborhoods without considering node importance. When αl equals to 1, the node weighting scheme is activated.

Exploring Diverse Information from Neighborhoods

To capture divese node-level characteristics of graphs, GraphDIVE also facilitates the exploring of diverse information from the neighborhoods. Each kind of information corresponds to each specific distribution in the embedding space.

As formulated in Eq. (2), the hyper-parameter pl > 0 controls the distributions of the output embeddings. When pl = 1, this aggregator behaves as average pooling and pl = ∞ leads to max-pooling results. When pl = 2 and ci = 1 |Ni | ∑j∈Ni xj, it generates standard deviation of the node embeddings. Besides, pl ≥ 3 enables GraphDIVE to explore other distributions from the neighborhoods.

By setting T different values to αl and pl, we can get multiple aggregated node representations: ˜ x(1) i , · · · , ˜ x(T ) i . Then these diverse representations are concatenated and fed into a fully connected (FC) layer that yields the updated node representation as:

where ∥ is the concatenation operation. By doing so, we not only enrich node representation by explicitly exploring diverse node-level topological structure information, but also model the complex relations among these information.

In fact, the above diverse node-level aggregators resemble those in PNA [Corso et al., 2020]. However, GraphDIVE is distinct from PNA in both motivation and technique. In motivation, GraphDIVE targets at alleviating prediction bias in the context of imbalance graph classification. It learns diverse graph representations to boost the diversity of MoE experts. In contrast, PNA focuses on distinguishing two graphs while ignoring the class imbalance problem. Technically, GraphDIVE uses multiple readouts and diverse experts, while PNA generates only one representation for each graph and uses one classifier.

4.2 Diverse Graph-level Readouts

In addition to promoting the diversity of node-level representations, we further encourage the diversity of graph-level representations that are generated from multiple readout functions. This is crucial, as only one graph representation is not able to fully capture the intrinsic diverse characteristics across the graph. Besides, only one graph representation may limit the diversity of experts' prediction results, hindering the performance of MoE methods. For such cases, we propose diverse graph-level readout functions as:

where x ∈ R1×d is the global graph representation, and d denotes the hidden dimension of graph embedding. N denotes the set of nodes in the graph and wi is the importance weight of node i. αg and pg are hyper-parameters which are similar to those defined in Eq. (2). Apparently, this readout function is similar to the node-level aggregator in form. That is, each node i in the graph is weighted by wi according to topology structure, and the weighting effect is controlled by

αg. Besides, pg controls the distributions of the output graph embeddings. By setting different values to αg and pg, diverse graph representations can be obtained. The difference is that the node-level aggregator gathers information from local neighborhoods, while the graph-level readout function generates representation from all nodes of the graph.

From the perspective of multi-view learning [Xu et al., 2013], diverse graph-level readouts generate multi-view representations for each graph. Each pair of αg and pg corresponds to a particular view, and each view of the representation may contain some knowledge that other views do not have. Therefore, multiple views of representations can describe the graphs comprehensively and complementarily.

4.3 Mixture of Multi-view Experts

Based on multi-view graph representations, GraphDIVE applies multi-view experts and sends each view of graph representation to a specific view of experts. Each view of experts refers to a specific group of classifiers. In this manner, the output of different views of experts tend to be distinct, which will boost the performance of MoE. Formally, GraphDIVE generates predictions by combining the results from multiview experts:

where x(i) is the extracted graph representation from the ith view. Θ = {Winter ∈ Rd×K ,Wintra ∈ Rd×M ,We ∈ Rd×C } denotes learnable parameters of inter-view gating network, intra-view gating network, and expert networks respectively. K, M, and C denote the number of views, experts, and label categories. Compared to conventional MoE methods in Eq. (1), the key distinction for GraphDIVE is that the outer summation formula combines the predictions of multiview experts. Specifically, conventional MoE methods make predictions based on one shared (single view) representation while GraphDIVE applies different groups (multi-view) of experts on different views of representations. As shown in [Blum and Mitchell, 1998], the independence of different views can serve as a helpful complement to the multi-view learning. Applying specific experts for each individual representation promotes the independence of different views and encourages the diversity of different experts.

Since we implement each view of experts with the same network design, we drop the superscript of view index for notation simplicity and bear in mind that x , Winter, Wintra andWe are different in different view indices. First, we implement each expert with one separate fully connected layer followed by a sigmoid function:

where W(z) e ∈ Rd×C denotes the parameters for the z-th expert.

Then, in each view of experts, the gating network generates an input-dependent soft partition of the dataset based on cosine similarity between graph representations and gating parameters:

where τ is the temperature hyper-parameter tuning the distribution of the gating function, and Wintra [j] ∈ Rd×1 is the j-th column of Wintra, which represents the gating parameter for the j-th expert.

Considering the predictions obtained in different views are based on different graph representations, they should have different contributions in judging the graph label. As such, we compute a weight score for each view as:

where γ is a hyper-parameter that tunes the distribution. Winter [i] ∈ Rd×1 is the i-th column of Winter, which represents learnable gating parameters for each view.

4.4 Model Optimization

To encourage the difference of experts in the i-th view, we introduce a Kullback-Leibler (KL) divergence regularization term as:

where DKL(·, ·) is the KL divergence of two distributions. Then, the final loss function can be formulated as:

where λ is a hyper-parameter that controls the extent of regularization.

5 Experiments

5.1 Datasets and Implementation Details

Datasets. We conduct experiments on four benchmark molecular property prediction datasets [Hu et al., 2020], including HIV, PCBA, BACE, and BBBP. Each graph in molecular graph datasets represents a molecule, where nodes are atoms, and edges are chemical bonds. Each node contains a 9-dimensional attribute vector, including atomic number and chirality, as well as other additional atom features such as formal charge and whether the atom is in the ring.

Implementation Details. For a fair comparison, we implement our method and all baselines in the same experimental settings as [Hu et al., 2020]. Specifically, we follow the original scaffold train-validation-test split with the ratio of 80/10/10. We run ten times for each experiment with random seed ranging from 0 to 9, and report the mean and standard deviation of test ROC-AUC for all datasets except PCBA.

Following the practice in [Hu et al., 2020], we report average precision for PCBA dataset.

We evaluate the performance of the proposed GraphDIVE method on the molecular property prediction task that is a typical graph classification application. We compare with the following strong and representative GNN methods: GCN [Kipf and Welling, 2017], GIN [Xu et al., 2019], FLAG [Kong et al., 2020], GSN [Bouritsas et al., 2020] WEGL [Kolouri et al., 2021], and PNA [Corso et al., 2020]. For all these methods, we use official implementation and follow the original setting.

In addition, we compare GraphDIVE with state-of-theart imbalanced learning methods that are initially designed for Euclidean data, including FocalLoss [Lin et al., 2017], LDAM [Wallach et al., 2020], GHM [Li et al., 2019], and Decoupling [Kang et al., 2019]. The first three methods belong to re-weighting strategy and the last one belongs to re-sampling strategy. Since there is no GNN based method which considers the IGC problem, we combine these imbalanced learning methods with the representative GCN.

For hyper-parameter setting, we train the model using Adam optimizer [Kingma and Ba, 2015] with initial learning rate of 0.001. For HIV and PCBA datasets, we train the network for 200 epochs in light of the scale of the dataset. Moreover, for all the other datasets, we train the model for 100 epochs. According to the average performance on the validation dataset, we use grid-search to find the optimal value for K (i.e., the number of views), M (i.e., the number of experts), and λ. We set the hyper-parameter space of K and M as {2, 3, 4, 5, 6, 7, 8} and the hyper-parameter space of λ as {0.001, 0.01, 0.1, 1, 10}, respectively. Besides, the hyperparameter space of α is {0, 1} and the hyper-parameter space of p is {1, 2, 3,+∞}. The hyper-parameter space of τ and γ is {0.001, 0.01, 0.1, 1, 10, 100}.

5.2 Molecular Property Prediction

Comparison with other GNNs. For molecular property prediction task, we report classification results of state-of-the-art GNN models in Table 2. Overall, GraphDIVE consistently outperforms other GNN models across all four datasets. For example, PNA [Corso et al., 2020] is one of the latest stateof-the-art GNN methods for graph classification, and we can observe that GraphDIVE achieves 0.68%, 0.44%, 3.19%, and 1.23% absolute improvement on HIV, PCBA, BACE, and BBBP dataset, respectively.

Comparison with other imbalanced learning methods. We also compare GraphDIVE with other state-of-the-art imbalance learning methods in Table 2. Firstly, it can be observed that the state-of-the-art imbalanced learning methods, such as LDAM and Decoupling, do not seem to offer significant or stable improvements over GNN models. For example, LDAM performs better than GCN on HIV and PCBA dataset, but it is inferior to GCN on BACE and BBBP dataset. We suppose the reason is that either re-sampling or re-weighting methods make the model focus more on minority class, resulting in potential over-fitting to minority class [Zhou et al., 2020]. Besides, they cannot capture the diverse topological structure either. In contrast, we observe that GraphDIVE outperforms these imbalanced learning methods by a large margin. We conduct more experiments in the following parts to investigate why GraphDIVE brings performance improvement.

5.3 Prediction Bias Analysis

In this subsection, we study whether the overall performance improvement of GraphDIVE is achieved by alleviating the IGC problem. Specifically, we report the classification accuracy of minority class in Figure 3.

We have the following observations. First of all, GraphDIVE outperforms GCN, PNA and existing imbalanced learning methods regarding the performance of minority class. This result demonstrates that GraphDIVE can alleviate the prediction bias. Secondly, existing state-of-the-art reweighting and re-sampling methods, such as LDAM and Decoupling, have marginal performance improvements or even performance degradation in minority class. This may be because re-weighting and re-sampling methods cannot model the relationship between the topological structure and the class imbalance. We give a more detailed study in Sec. 5.4.

5.4 Ablation Study

To verify the effectiveness of each component, we conduct an ablation study on node-level neighborhood aggregators, graph-level readout functions and multi-view experts respectively. The results are shown in Table 3. When each component is individually applied (2nd, 3rd and 4th row), the performance is improved compared with vanilla GCN (1st row). This can be attributed to the exploring of complementary graph information and the D&C mechanism, respectively. Besides, comparing the 4th row and the last two rows, we can observe that multi-view node-level representations and graph-level representations can improve the performance of vanilla MoE methods. This is because diverse graph representations encourage the diversity of different experts.

Aside from the above results shown in Table 3, we also investigate effect of topological structure. Specifically, we discard the structure-aware node weighting scheme by setting αl and αg as zero. We observe 0.75% and 1.16% performance degradation on HIV and BACE dataset, respectively. This result demonstrates that it is necessary and beneficial to model topological structure for the IGC problem.

6 Conclusion

Existing GNNs largely suffer from the ubiquitous class imbalance problem. In this paper, we have proposed GraphDIVE, a graph neural network with mixture of diverse experts to alleviate the prediction bias towards majority classes. GraphDIVE learns multi-view graph representations from both node-level and graph level. These multi-view graph representations can not only encourage the diversity of experts, but also capture diverse topological structure characteristics. Experimental results on four datasets exhibit the effectiveness and generalization ability of GraphDIVE.

Acknowledgements

This work is jointly supported by National Natural Science Foundation of China (62141608, U19B2038) and CAAI Huawei MindSpore Open Fund.