Multi-Channel Pooling Graph Neural Networks

1 Introduction

Convolution Neural Networks (CNNs) [Montavon et al., 2012] have shown great capability in various machine learning tasks, such as image recognization [He et al., 2016] and video classification [Karpathy et al., 2014]. As images and texts are Euclidean data, which have regular grid-like structures, convolution and pooling operations can be conveniently conducted in. Given the powerful capability of CNNs on gridlike data, it is appealing to generalize convolution and pooling operations on graph-structured data [Gori et al., 2005]. However, significantly different from grid-like data, the locality of nodes cannot be clearly defined in a graph, making the generalization of convolution and pooling operations on graphs extremely challenging.

∗Corresponding author

1 https://github.com/kingloon/MultiChannelPooling

In recent years, there has been a myriad of attempts to extend convolution operations to arbitrarily shaped graphs, referred as Graph Neural Networks (GNNs). The application of various GNNs for node representation learning [Veliˇckovi´c et al., 2018] have obtained outstanding performance in graphrelated learning tasks, such as node classification [Veliˇckovi´c et al., 2018] and link prediction [Schlichtkrull et al., 2018]. However, in some scenarios, the graph-level representation is also needed to perform graph-level machine learning tasks such as predicting the physical property of a given molecule [Wang et al., 2019]. Although considerable efforts have been made in studying the convolution operation in GNNs, one essential problem in graph representation learning, how to effectively perform the pooling operation to downsample the graphs, is not fully studied and remains to be a challenging research problem.

Early graph representation learning models generally utilize simple readout function (such as mean pooling and max pooling) [Henaff et al., 2015] to summarize all the nodes' representations to represent the graph. Such simple readout function methods are inherently flat [Zhang et al., 2019] as the graph topology information is largely ignored. To capture the global topology structure of a graph, coarsening pooling methods, such as DiffPool [Ying et al., 2018], utilize differentiable pooling operators to learn soft assignment matrices to map each node into sets of clusters. Then the nodes of a cluster are pooled as one node to form a coarsened graph. Another line of researchers propose the dropping pooling methods, including Graph U-Nets [Gao and Ji, 2019], AttPool [Huang et al., 2019] and SAGPool [Lee et al., 2019], to better capture the local topology structure. The general idea behind these approaches is to first select top-k important nodes of a graph and then drop all the other nodes to downsample the graph. However, there lacks an effective method to integrate the two types of methods so that both the local and the global topology structure of a graph can be well captured.

To address the limitations of existing graph pooling methods, we propose a novel multi-channel graph pooling method named MuchPool, which can effectively integrate the global topology structure, the local topology structure and the node features in graph pooling via using three channels. To be specific, we use two channels to conduct dropping pooling based on the local structure and node features respectively, and one channel to conduct coarsening pooling based on the global topology structure. Then a cross-channel graph convolution operation is proposed to integrate and refine the node representations of the three channels. Finally, the pooling results of different channels are aggregated to form the final pooled graph. To utilize MuchPool in the task of graph classification, we implement an end-to-end architecture by stacking graph convolution layers and the MuchPool layers to learn a hierarchical representation for a graph. We conduct extensive experiments over six widely used graph datasets in GNNs. The results show that our proposal achieves significant performance improvement on graph classification compared with current state-of-the-art models. We summarize our main contributions as follows.

• We for the first time propose a novel multi-channel graph pooling method that can capture and integrate local patch, coarse-grained structure and node features simultaneously.
• We design a cross-channel graph convolution operation to refine the node representations, and propose a pooling aggregation operation to integrate the pooling results of different channels.
• We conduct extensive experiments on multiple public datasets to demonstrate MuchPool's capability of learning effective graph representation by comparing it with several state-of-the-art methods.

2 RelatedWork

2.1 Graph Neural Networks

GNNs can be generally divided into two categories: spectral and spatial approaches. Based on spectral graph theory, Bruna et al. [Bruna et al., 2014] first defined convolution operation in Fourier transform domain. When utilizing spectral filters, graph Laplacian has to be computed, causing heavy computation cost, so this method is hard to generalize to graphs with large size. To address this challenge, Kipf and Welling [Kipf and Welling, 2017] proposed a simplified model by utilizing 1-st approximation of the Chebyshev expansion. The spatial approaches define convolution by aggregating the information of central node and its neighbors, aiming at making it work on graphs directly. Among them, GraphSAGE [Hamilton et al., 2017] generates node embeddings via aggregating nodes information from sampling strategy. GAT [Veliˇckovi´c et al., 2018] integrates attention mechanism into the process of information aggregation. Both spectral and spatial methods can fit within the framework of "neural message-passing" [Gilmer et al., 2017]. Under this framework, GNN is regarded as a message-passing algorithm where node representations are computed iteratively by aggregating messages from its neighboring nodes through edges using a differentiable function.

2.2 Graph Pooling

Pooling operation can downsize inputs, thus reduce the number of parameters and enlarge receptive fields, leading to better generalization performance. Recent graph pooling methods can be grouped into two big branches: global pooling and hierarchical pooling.

Global graph pooling, also known as a graph readout operation [Xu et al., 2019; Lee et al., 2019], adopts summation operation or neural networks to integrate all the node embeddings into a vector as graph representation. Set2set [Vinyals et al., 2015] uses the LSTM model to find the important nodes in a graph and generate graph representation. DGCNN [Zhang et al., 2018] sorts node embeddings and then summarizes the graph by concatenating some of the node embeddings. Though flexible to apply on graphs with different sizes, global graph pooling methods perform pooling operations only based on node features, and thus some structural information could be lost.

Hierarchical graph pooling methods aim at learning a hierarchical representation via building hierarchical GNNs. DiffPool [Ying et al., 2018] uses graph neural networks to learn a soft assignment matrix mapping nodes to a set of clusters, so it is computation expensive. U-Nets [Gao and Ji, 2019], SAGPool [Lee et al., 2019] and AttPool [Huang et al., 2019] design top-k node selection strategy to pick out the most important nodes to form a pooled graph with them. Such methods are more effective as they only need to calculate an important score for each node, but they neglect to consider the graph topology during this procedure. EdgePool [Diehl, 2019] gets a pooled graph by contracting the edges in a graph. It is unflexible since it can only cut the number of nodes in half each time. EigenPool [Ma et al., 2019] performs pooling operation based on graph Fourier transform. Due to operating spectral clustering, it is very time-consuming. To sum up, there still lacks an effective method that can combine the top-k based and graph coarsening based methods to yield a better hierarchical graph representation.

3 Problem Statement

In this paper, we focus on the graph classification task, which maps each graph to a set of labels. Considering an arbitrary graph G = (A,X), we have A ∈ {0, 1}n×n denotes the adjacency matrix, and X ∈ Rn×d denotes the feature matrix in which each row represents a d-dimentional feature vector of a node. Given a dataset D = {(G1, y1), (G2, y2), ...}, the task of graph classification is to learn a mapping function f : G → Y, where G = {G1,G2, ...,Gn} is the set of input graphs and Y = {y1, y2, ..., yn} is the set of labels associated with the graphs.

3.1 Graph Convolution Networks

Graph Convolution Network (GCN) [Kipf and Welling, 2017] is an effective tool to extract discriminative features in graphs and achieves state-of-the-art performance in many machine learning tasks. We use GCN as a module of our graph classification model, which is defined as:

where ˆ A = A+I is the adjacency matrix with self-loop added to each node, ˆD = ∑j ˆ Ai,j is the degree matrix of ˆ A and W (l) is a learnable matrix at layer l. The initial node features are used at the first graph convolution, i.e., X(0) = X.

Step 2: Cross-channel convolution Step 3: Pooling aggregation

Figure 1: The framework of the proposed MuchPool model.

4 MuchPool: Multi-Channel Graph Pooling

The main idea of MuchPool is to use three channels to perform graph pooling to capture different characteristics of a graph, and then aggregate the three channels' pooling results. The original graph is first fed into three GCN layers to learn node embeddings. Based on the intermediate result, we generate two fine-grained pooled graphs Gfine1 and Gfine2, and a coarse-grained graph Gcoarse as shown in step 1 of Figure 1. At step 2, we conduct cross-channel convolution between channel 2 and channels 1 and 3, respectively. At step 3, we aggregate the outputs of channel 1 and channel 3 to form the final pooled graph Gpool.

4.1 Multi-Channel Pooling

Channel 1: Local topology based pooling. In channel 1, we propose to use the local topology-based mask method to generate a fine-grained pooled graph Gfine1. Specifically, we use the degree measurement to rank the importance of the nodes. In other words, the larger the degree of a node, the more important it is to the entire graph. For example, the nodes with high degrees in road networks may represent some central or important areas and these nodes can better represent the outline of the whole road network [Song et al., 2020; Wang et al., 2020]. The following equations are applied to get the importance scores of each node:

where si denotes the degree of i-th node of original graph, s1 = [s1, s2, ..., sn], A denotes the adjacency matrix of the graph, k is the number of nodes selected to reserve in the fine-grained pooled graph. rank(s, k) function is used to sort nodes based on their degree, and it returns the index set of the k-largest values in s.

Channel 2: Global topology based pooling. In channel 2, we aim at forming a coarse-grained graph Gcoarse. Many graphs have rich hierarchical structures [Ma et al., 2018], and capturing this kind of structural information is significant for downstream graph classification tasks. Motivated by DiffPool [Ying et al., 2018], we adopt a graph clustering method that uses a GNN to learn a cluster assignment matrix for generating Gcoarse. The assignment matrix is generated by the following equation:

where n is the number of nodes in the input graph and c is the predefined cluster number, GNNpool is the GNN used to cluster nodes, X and A are the feature and adjacency matrices of the input graph, respectively. Based on the assignment matrix, we can obtain Gcoarse by the following formulas:

where Z ∈ Rn×d denotes the node embeddings learned from the input graph, Xcoarse and Acoarse denote the feature and adjacency matrices of Gcoarse. S and Z are both obtained by GNN modules, and the softmax function is used in rowwise manner on ST to determine the assignment probability of each node of the input graph to the clusters.

Channel 3: Node feature based pooling. In channel 3, we select the most important nodes based on their feature embeddings. To be specific, we first use a readout module to get a representation of the current graph, and then transform it with a learnable matrix. The process can be formulated as:

where Z is the shallow graph representation obtained by using the mean readout operation and ˜ Z is its variant through a nonlinear transformation, W ∈ Rd×d is a learnable parameter matrix. To select the top-k important nodes in the current graph based on features, we calculate an importance score for each node by applying the following formula.

where i is the index of node vi, si denotes the importance score of it, s2 = [s1, s2, ..., sn], and · denotes the operation of inner-product. With this score, a fraction of most important nodes from the aspect of features can be selected, whose indexes are obtained with the same rank(s, k) function:

4.2 Cross-Channel Convolution

As shown in step 2 of Figure 1, with the outputs of channels 1 to 3, we get three pooled graphs Gfine1, Gfine2 and Gcoarse. Since the three pooled graphs reflect the different aspects of the initial input graph, we next need to fuse them. To this end, we propose a cross-channel convolution operation between Gfine1 and Gcoarse, Gfine2 and Gcoarse. The cross-channel convolution operation is defined as follows.

Hfine = σ([Hfine +Across · Hcoarse] · W) (12) Hfine ∈ Rk×d denotes the node embedding matrix of the fine-grained graph Gfine1 or Gfine2, Hcoarse denotes the node embedding matrix of Gcoarse, and Across ∈ Rk×c denotes the connection relationship between coarse- and finegrained pooled graphs, where k and c are the node numbers in the two pooled graphs, respectively. In particular, we obtain Across by utilizing the assignment matrix S and the important node indices via applying the following equation:

The GNNs within the message-passing scheme can be ex-

pressed as:Hk = σ([Hk-1 + AHk-1] · Wk) ∈ Rn×d (14) where Hk denotes the hidden node embeddings after k steps of graph convolution, A ∈ {0, 1}n×n denotes the adjacent matrix, and Wk ∈ Rn×d denotes a learnable weight matrix, which needs to operate on the same graph. Compared with the formula (12), we replace the adjacency matrix and embedding matrix of the fine-grained graph by Across and Hcoarse separately.

4.3 Pooling Aggregation

With the above operations, we have two refined pooled graphs from channels 1 and 3 as shown in the right part of Figure 1. To reduce the loss of discriminative information for graph classification, we need to aggregate them. We denote the indices of the selected nodes in channel 1 as Idx1 and the embedding matrix after the cross-channel convolution step as X1. Likewise, the indices of selected nodes and the embedding matrix in channel 3 are Idx2 and X2, respectively. The pooled graphs aggregation process can be performed by the following formulations:

With the index, a subgraph that consists of the most representative nodes of the original graph can be extracted, whose adjacency matrix is denoted as:

where K = |Idx| is the order of the indices set of nodes in the original graph that will be reserved, N is the total number of nodes in the original graph. Then, we apply the following two formulas to generate the final pooled graph:

where Xp ∈ RK×d is the node feature matrix for the aggregated pooled graph, and Ap ∈ {0, 1}K×K is its adjacency matrix accordingly.

4.4 Hierarchical Pooling Framework with MuchPool

To use MuchPool in the graph classification task, we implement an end-to-end trainable model by stacking several GCN layers with MuchPool module inserted. The model framework is illustrated in Figure 2. Concretely, we view a GCN layer followed by a MuchPool layer as a complete function unit and name it MuchPool GCN layer for convenience. For a MuchPool GCN layer, it takes a graph as input and outputs a pooled graph that is represented with a new feature matrix and adjacency matrix. Then, the pooled graph is fed into the next MuchPool GCN layer, and it is fed into a readout module at the same time, in which the embedding is added up as the graph embedding in this layer. Finally, the graph embeddings in all layers are added up to generate the final graph representation, and it is taken as the input of a MLP classifier to predict the label of the original graph.

5 Experiments

5.1 Datasets and Baselines

We use the following 6 widely used datasets in the classification tasks to evaluate the performance of our proposed model. D&D and PROTEINS [Dobson and Doig, 2003] are two protein graph datasets, where nodes represent the aminoacids. The label indicates whether or not a protein is a non-enzyme. NCI1 and NCI109 [Shervashidze et al., 2011] are two biological datasets for anticancer activity classification, where each graph is a compound graph with nodes and edges representing atoms and chemical bonds separately. ENZYMES is a dataset of protein tertiary structures, and each enzyme belongs to one of the 6 EC top-level classes. COLLAB [Leskovec et al., 2005] is a scientific collaboration dataset, where nodes represent scientists and edges represent collaboration relation between two scientists; each graph is labeled to a physics field that the researcher belongs to. Statistics of the datasets are shown in Table 1.

We take three kinds of methods as baselines: (1) the kernelbased methods including WL [Morris et al., 2019] subtree; (2) GNN-based methods including GCN [Kipf and Welling, 2017], GIN [Xu et al., 2019], GAT [Veliˇckovi´c et al., 2018], GRAPHSAGE [Hamilton et al., 2017], Set2Set [Vinyals et al., 2015] and DGCNN [Zhang et al., 2018]; (3) hierarchical graph pooling methods including DiffPool [Ying et al., 2018], Graph U-Nets [Gao and Ji, 2019] and AttPool [Huang et al., 2019].

5.2 Implementation and Experiment Settings

We implement our MuchPool model with the PyTorch framework. The part of cluster formation in channel 2 follows the implementation of DiffPool [Ying et al., 2018] and we make some adjustments according to our problem setting. The dimensions of node representation and graph representation are set as 64. The node retention ratio r is set as 0.5 for three channels in all layers. We adopt the mean pooling function to read out the graph representation. GCN is used as our backbone network. The first MuchPool GCN layer uses 2 GCN layers while the subsequent MuchPool GCN layers use only

1 GCN layer for aggregating information. A MLP consisting of two fully connected layers with 128 neurons is set to follow the final MuchPool GCN layer, followed by a softmax classifier. It takes the graph representation as input and outputs the categories probability to finish the prediction task.

We follow the experiment setting of the state-of-the-art model Graph U-Nets [Gao and Ji, 2019] and evaluate our model over 20 random seeds using 10-fold cross validation. A total of 200 testing results are used to report the average accuracy and standard deviation for each model on each dataset. We use Xavier normal distribution [Glorot and Bengio, 2010] for weight initialization, Adam optimizer to initialize our model and negative log-likelihood loss function is utilized to train our model. For all datasets, we train our model for 300 epochs and the batch size is set to 16 or 32 (depending on the graph size). The optimal hyperparameters are obtained by applying the strategy of grid search.

5.3 Performance Comparison

We compare the performance of our proposed MuchPool with baseline methods on the 6 benchmark datasets for the graph classification task, and the accuracy and standard deviation are reported in Table 2. First, one can observe that the performance of MuchPool is superior to its counterparts on five out of six benchmarks. To be specific, MuchPool improves the performance by 3.72% and 5.66% over the best baselines DiffPool and AttPool on ENZYMES and PROTEINS datasets respectively, which demonstrates the effectiveness of MuchPool. Next, MuchPool consistently outperforms GCN on all the datasets significantly, indicating the necessity of adding pooling modules in the learning process. This is because MuchPool can extract more useful graph topology information than the global pooling based GCN. By comparing with other GNN based models including GCN, GAT, GIN and GraphSAGE, both DiffPool and MuchPool achieve better performance. It reals that capturing coarse-grained structure is helpful for graph representation learning, especially for those graphs with obvious community structure. One can also see that DiffPool does not always show better results than local topology and feature based pooling methods AttPool and Graph U-Nets. This further verifies the effectiveness of combining the node features, local topology and global topology. Moreover, compared with AttPool, MuchPool scores relatively moderately on COLLAB datasets. This is because many collaboration graphs in COLLAB show only single-layer community structures. MuchPool uses three layers model to learn the graph representation, which is too complex and may lead to overfitting.

5.4 Ablation Study

In this subsection, we conduct an ablation study to verify that all three channels are helpful to graph pooling. We compare the complete MuchPool model with its variants by removing one of the three channels in it and keep other parts the same. For convenience, we name the MuchPool model without local topology, global topology and feature based pool channel as MuchPoolNL, MuchPoolNG and MuchPoolNF , respectively. As shown in Figure 3, the performances of the three variants are all inferior to MuchPool over the four datasets EN- ZYMES, PROTEINS, NCI1 and NCI109. This demonstrates the effectiveness of the three channels. Especially, MuchPool outperforms MuchPoolNG by 36.64%, 4.63%, 5.08% and 3.90% on four datasets, respectively. The result suggests that global topology is significantly important in some graphs (for instance, protein molecule graphs), and capturing the global structure is especially useful for the classifier to distinguish the graphs with fixed functional units. One can also see that the results of MuchPoolNL and MuchPoolNF are close to each other. It is probably because some nodes are important in terms of both local topology and node features, which leads to the large overlap between the selected nodes from channels 1 and 3.

5.5 Parameter Sensitivity Analysis

We further investigate the effects of some important hyperparameters onMuchPool. In detail, we study how the number of neural network layers k, graph representation dimension d will affect the graph classification performance. As shown in Figure 4, MuchPool achieves better performance when setting d = 64 and k = 2, respectively. One can also observe that with the dimension d increasing, the classification accuracy presents a slight increase trend accordingly. This is because different types of graphs have larger margins in higherdimensional representation space, making it easier to distinguish their categories. Considering the neural network layer k, a larger k provides a more accurate classification result, but too large a k will hurt the performance.

6 Conclusion

In this paper, we propose a novel multi-channel graph pooling method MuchPool. MuchPool uses three channels to capture the local topology, the global topology and node features separately, and then uses a cross-channel convolution operation to integrate them. Based on MuchPool, we construct an end-to-end hierarchical graph representation learning model for graph classification. We evaluate our proposal on several graph classification benchmark datasets. The result shows that MuchPool achieves superior or comparable results compared with state-of-the-art methods.

Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (No.: NZ2020014) and Guangdong Basic and Applied Basic Research Foundatoin (2021A1515012239).