{'fraction_non_alphanumeric': 0.03661375661375661, 'fraction_numerical': 0.009312169312169312, 'mean_word_length': 4.4350826743350105, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-Channel Graph Convolutional Networks

Graph neural networks (GNN) has been demonstrated to be effective in classifying graph structures. To further improve the graph representation learning ability, hierarchical GNN has been explored. It leverages the differentiable pooling to cluster nodes into fixed groups, and generates a coarse-grained structure accompanied with the shrinking of the original graph. However, such clustering would discard some graph information and achieve the suboptimal results. It is because the node inherently has different characteristics or roles, and two non-isomorphic graphs may have the same coarse-grained structure that cannot be distinguished after pooling. To compensate the loss caused by coarse-grained clustering and further advance GNN, we propose a multi-channel graph convolutional networks (MuchGCN). It is motivated by the convolutional neural networks, at which a series of channels are encoded to preserve the comprehensive characteristics of the input image. Thus, we define the specific graph convolutions to learn a series of graph channels at each layer, and pool graphs iteratively to encode the hierarchical structures. Experiments have been carefully carried out to demonstrate the superiority of MuchGCN over the state-of-the-art graph classification algorithms.


Introduction
Classifying graph-structured data has become an important problem in various domains, such as the biological graph analysis [1]. Among the numerous graph classification techniques, graph neural networks (GNN) [2,3,4] tends to achieve the superior performance. The core idea is to update each node's embedding iteratively, via aggregating the representations of its neighbors and itself. The graph representation is generated through a global pooling layer over all the nodes [5,6,7], which encodes the input graph flatly.
To further improve performance, the hierarchical GNNs are proposed to encode both the local and coarsegrained structures of the input graph [8,9,10]. Taking the social network as an example, the local structure is represented by the individual nodes and direct links. After clustering, the coarse-grained structure is constructed by the communities and their correlations in the social network. The motivation is the inherent hierarchy of the graph-structured data, like the different resolutions of image. Accordingly, the pooling modules are leveraged to cluster nodes and generate a coarsegrained graph at the next layer. GNNs are then stacked to encode the hierarchical graphs. While the pooling module obtains the hierarchical representations of the input graph, the accompanied information loss is problematic for the task of classifying graphs. First, given two non-isomorphic graphs, they may be pooled into the same one at the higher layer of model. Similar graph representations would be learned and make them indistinguishable. Second, there is only one coarse-grained graph generated at each layer, which ignores the multiview poolings of the input graph. For example, the individual social nodes generally have multiple characteristics, and they could be clustered into communities in different ways. Recently, the multi-graph GNNs have been proposed to learn the various node characteristics [11,12,13]. It duplicates a series of instances from the input graph, and implements GNNs on them independently to encode the specific characteristics.
To tackle the above problems, we propose the hierarchical framework of being able to encode a series of coarse-grained graphs layer by layer. It is comparable with the convolutional neural networks (CNN), where both the pooling layer and convolutional filter work together to operate on the image channels hierarchically. The grid-like image could be regarded as a special type of the graph-structured data, at which the pixel is represented by a node. The pixel has the fix size of neighborhood patch, e.g., 8 directly adjacent pixels. These neighbors have the determined orders from the upper left to the lower right. However, there are two challenges in building up such a deep neural network for the graph-structured data. First, across each graph, the nodes have various numbers and uncertain orders of their neighbors. The local convolutions in CNN cannot be directly applied to learn the nodes' characteristics, For each layer, the graph convolutions updates the node embedding, and then the feature learning prepares a series of graph channels encoded with different node characteristics. Between the successive two layers, the pooling module is applied to obtain the coarse-grained ones of the graphs at the last layer. Graph embeddings learned at each layer are concatenated to represent the entire graph. It is fed into the differentiable classifier to predict the corresponding label.
since it is predefined with the shape of local neighbors and their orders. Second, considering the coarse-grained graphs as shown by (X 1 , A 1 ) and (X 2 , A 2 ) in Figure 1, they have the different adjacency structures. The nodes and edges of one channel cannot be mapped to those of the others. It prevents us from using the channelwise convolutional filter to add one graph on top of the others to aggregate their features. The filter could only sum up the images with the same and grid-like shape. To address the above challenges, we develop the multi-channel graph convolutional networks (MuchGCN) as shown in Figure 1. To be specific, it could be separated as the following two research questions. (i) How to define the convolutional filters to learn the various nodes' characteristics for the graph-structured data? (2) How to define the graph convolutions to combine the distinct coarse-grained graphs? In summary, our major contributions are described below.
• We propose the new graph representation learning architecture, at which the series of coarse-grained graphs are encoded hierarchically.
• We design the convolutional filter to learn the series of graph channels, without reliance on the shape and order of the node's neighbors.
• We define the inter-channel graph convolutions to aggregate the graph channels via message passing.
• The experiments show that the graph classification accuracy of MuchGCN is superior than the stateof-the-art baselines.

Preliminaries
The goal of graph classification is to map graphs into a set of labels. Let G = (A, X) denote the directed or undirected graph consisting of n nodes, where A ∈ {0, 1} n×n denotes the adjacency matrix, and X ∈ R n×d denotes the feature matrix in which each row represents a d-dimensional feature vector of a node. Given a set of graphs {G 1 , . . . , G N } ⊂ G and the corresponding labels {y 1 , . . . , y N } ⊂ Y, the challenge is to extract the informative graph representations to facilitate the following graph classification: f : G → Y.
2.1 Graph Neural Networks. GNN uses the adjacency structure and node features to learn the node embeddings. A general "message-passing" based GNN could be expressed by [14]: where H k denotes the hidden node embedding after k steps of graph convolutions, W k ∈ R d×d denotes the linear transformation matrix, and σ denotes the activation function of ReLU. We have H 0 = X. Node embedding is updated by aggregating representations of its neighbors and itself, which is the same with the graph convolutional networks (GCN) excepts for the normalization of adjacency matrix [15]. After K steps of message passing, we could reach out to the neighbors that are at maximum K hops away from the central node. For the simplicity of expression, we denote GNN associated with K steps of message passing as Z = GNN(A, X) ∈ R n×d . To tackle the task of graph classification, the graph representation is generated by globally pooling the n node embedding in matrix Z.

Differentiable Pooling.
A major limitation of Equation (2.1) is that it encodes only the superficial structure of the input graph. Recently, the differentiable pooling [8] (DIFFPOOL) is proposed to cluster nodes from the input graph gradually, and generate the hierarchical coarse-grained graphs layer by layer. Formally, let n l and n l+1 denote the node numbers of coarse-grained graphs at layers l and l + 1, respectively. Generally we have n l+1 < n l < n in order to obtain the more abstract graphs at the higher layer of model. Let S (l) ∈ R n l ×n l+1 and Z (l) ∈ R n l ×d denote the cluster matrix and node embedding learned at layer l, respectively. DIFFPOOL module clusters the graph from layer l and generates a more coarser one at layer l + 1 as follows: where A (l+1) and X (l+1) denote the adjacency matrix and node features of the graph at layer l + 1, respectively. To prepare the cluster matrix S (l) and node embedding Z (l) at layer l, two GNN modules are used: Z (l) = GNN l,embed (A (l) , X (l) ) and S (l) = softmax(GNN l,pool (A (l) , X (l) )). The softmax function is applied in the row-wise fashion to determine the assignment probability of each node at layer l to the clusters at layer l + 1. Given the coarse-grained graphs of all layers, GNNs are stacked to encode the inherently hierarchical structures of the input graph.

Multi-Graph
Learning. In the real-world graph-structured data, nodes have various roles or characteristics, and they have different types of correlations. Under this prior knowledge, the multi-graph GNN learns the multiple characteristics of nodes that could be informative for the representation learning. Formally, given the input graph associated with feature X, it is first duplicated to generate a series of graph instances. Considering graph instance i, a specific adjacency matrix A i is formulated to consider one class of the node characteristics and correlations. Based on Equation (2.1), the graph convolutions learn the node embedding at each graph instance independently as fol-lows: Z i = GNN(A i , X). The final node representation is obtained via globally pooling the set of node embeddings Z i learned at different graph instances.

Multi-channel Graph Convolutional Networks
The differentiable pooling has its own bottlenecks in the graph representation learning. On the one hand, the input graph is distorted gradually after each layer of pooling. It may be difficult to distinguish the heterogeneous graphs at the higher layer of model. On the other hand, the pooling discards the inherent various graph information that would be informative for the graph classification. One of the promising solutions is to learn the various nodes' characteristics and reserve as more coarse-grained structures as possible, in order to compensate for the information loss of pooling. However, the multi-graph learning directly duplicate the input graph, and ignores its hierarchical structures. The adjacency matrix for each graph instance is formulated manually to encode one the nodes characteristics. It prevents us from learning the hidden representation adaptively given a specific task.
To further improve the graph representation learning, we propose the new framework named MuchGCN in Figure 1. It mimics the advanced neural architecture of CNN for the graph-structured data, where a series of graph channels would be learned hierarchically. Before elaborating our framework, we first define two key concepts for the consistency of presentation: Definition 1. Layer: A layer is composed of operations of graph convolutions and feature learning as shown in Figure 1. Let l denote the index of layer. The input to layer l is a set of graphs (e.g., [{X 1 , A 1 }, {X 2 , A 2 }] at layer 1), while the output is a series of graphs associated with the learned node embeddings (e.g., [Z (1,1) , · · · , Z (1,4) ] at layer 1). Definition 2. Channel: Given a specific layer, a channel represents the input graph denoted by G i = {X i , A i }, where i denotes the channel index. As shown in Figure 1, layer 0 consists of one channel: 3.1 Proposed Method. Compared with CNN, the challenges of building up MuchGCN lie in the following two facts. First, nodes across the graph have different numbers of direct neighbors. For example, the upperleft node in graph {X 0 , A 0 } has only one neighbor as shown in Figure 1, while the others have at least two. There is also no determined order for all the neighbors of one node. In the graph-structured data, the grid-like local filter (e.g., 3×3) cannot learn the node's character-istics directly based on its neighborhood shape. Second, the coarse-grained graph channels at a layer have different shapes of adjacency structures, such as the {X 1 , A 1 } and {X 2 , A 2 }. It is hard to map the nodes and edges of one channel to those of another one. In consequence, the series of graph channels cannot be stacked and pooled together in the node-wise and edge-wise fashions. This precludes the straightforward way to aggregate features of the various graph channels and generate a new channel at the next layer, like in CNN.
We address the above challenges by carefully designing two key components in MuchGCN: (i) the convolutional filter defined based on the steps of message passing, instead of the direct neighbors; (ii) the interchannel graph convolutions passing messages among the graph channels to aggregate their features. As shown in Figure 1, we first describe how MuchGCN learns the node's characteristics in the single channel at layer 0. Following this, we describe how MuchGCN operates graph convolutions on the multiple channels at layer 1.
3.1.1 Single-channel Learning Process. We consider the graph G 0 = {X 0 , A 0 } at channel i = 0 of layer l = 0. It is given by the input graph, where X 0 = X and A 0 = A. The graph convolutions stage applies GNNs to generate embeddings iteratively. Node embedding after k steps of message passing at channel i is given by: k denotes the trainable parameter for the kth message passing at layer l. Note that embedding H i k represents the neighborhood structure of height k. Based on the Weisfeiler-Leman (WL) algorithm [14], two non-isomorphic graphs can be distinguished if their node embeddings H i k are different at any step k. In the context of graph representation learning, we consider the embedding multiset H 0 = [X 0 , H 0 k ] that consists of the input feature and all intermediate node embeddings, where k = 1, · · · , K. The feature learning stage learns the node's characteristics via a set of trainable filters. At the same time, it generates a series of graphs to improve the graph classification ability. Formally, filter θ (l,j) ∈ R 1×(K+1) learns the new graph associated with embedding Z (l,j) as follows: where index tuple (l, j) denotes the j-th newly generated graphs at layer l, and b is a trainable scalar. We have (l, j) = (0, 1) and (0, 2) as shown in Figure 1. φ, sum and denote the non-linear function of multilayer perceptron (MLP), summation function and elementwise multiplication, respectively. Following the same process of graph convolution and feature learning, we could also obtain the cluster matrices S (l,j) for the two new graphs at layer 0. Based on the graph pooling defined in Equation (2.2), channel j at the next layer are generated from the learned embeddings Z (l,j) and S (l,j) . As shown in Figure 1, we have channels G 1 = {X 1 , A 1 } and G 2 = {X 2 , A 2 } at layer 1, which encode different coarsegrained structures of the input graph G 0 . In addition, there exists adjacency connection between these two channels. Formally, the inter-channel adjacency matrix between channels 1 and 2 is given as follows: The row and column of A 1,2 represent nodes at channels 1 and 2, respectively.
3.1.2 Multi-channel Learning Process. Unlike the layer 0, the input to layer 1 is given by a series of channels. They represents the different characteristics of the input graph, and have the various coarsegrained structures. It is required to aggregate features from this series of channels to generate the more abstract representation at the higher layer of model. In this section, we introduce the novel graph convolutions, which updates the node embedding at one channel by additionally exploiting information of the others.
Considering channel i = 1, the graph convolutions includes both the intra-channel and inter-channel ones to receive information from the current channel i = 1 and neighboring channel c = 2, respectively. The intrachannel graph convolutions is given by Equation (3.3), at which the indexes of channel and layer are replaced by i = 1 and l = 1. Based on Equation (3.3), the interchannel graph convolutions is defined as follows: H i,c k denotes the node embedding of channel i, after k steps of feature aggregations from neighboring channel c. We define H i,c 0 = X i . A i,c denotes the inter-channel adjacency matrix between channels i and c, at which i = 1 and c = 2 at layer 1. Compared with the intrachannel convolutions, we replace the adjacency matrix and neighbor embedding by X i , A i,c , respectively. In this way, the messages of neighboring channels c are passed to update embedding at channel i, although they have the different adjacency structure shapes.
Following the graph convolutions, the feature learning stage learns the node's characteristics based on Equation (3.4). Different with embedding multiset H 0 at channel 0, the one at channel i is given by  Figure 1, they are denoted by Z (1,1) and Z (1,2) , respectively. By repeating the previous process for channel 2, we obtain the graphs associated with embeddings Z (1,3) and Z (1,4) . n l named assign ratio, and define T l C l+1 C l named channel expansion. Generally, the relation of 0 < r l ≤ 1 is satisfied to generate more coarse-grained graphs. The one of T l > 1 is given to learn the various characteristics of nodes. For each layer l, we generate a series of graphs whose node embeddings are given by Z (l,j) , j = 1, · · · , C l T l . As shown in Figure 1, we have C 1 T 1 = 2 × 2 at layer 1. The graph representation Y (l) learned at layer l could be obtained by combining the generated graphs as follows: where GlobalPool denotes the global pooling function to read out the graph representation. The entire graph representation Y is generated by concatenating Y (l) from all the layers: Y = ⊕ l Y (l) ∈ R d·L×1 . It encodes both the local and the hierarchically coarse-grained structures of the input graph. Given the input of Y , the downstream differentiable classifier, like MLP, is applied to predict the corresponding graph label.

Theoretical Analysis.
We analyze how the various coarse-grained structures are produced by learning the different characteristics of nodes. Considering channel i at layer l, we prepare the embedding mul- based on the intra-channel and inter-channel graph convolutions. Then, Equation (3.4) encodes a specific characteristic via filter θ (l,j) , and generates the graph associated with embedding Z (l,j) . Note that the representation of node a is given by the a-th row of embedding matrix. Correspondingly, we have the embedding multiset of node a denoted as H(a) = [x a , h a k , h a,c k ]. In addition, node embedding in the generated graph Z (l,j) is denoted as z a . Proposition 1: Assume the set constructed by all d-dimensional node embeddings is countable. There exist MLP function φ and infinitely many scalars b in Equation (3.4), so that node a has the unique embedding z a if the following conditions are satisfied: a) Node a has unique multiset H(a). b) The trainable filter θ (l,j) = 0. A proof is provided in Section C of Appendix. Node characteristic is computationally represented by the convolutions between multiset H(a) and θ (l,j) . The diverse nodes are assigned with different embeddings based on the previous proposition. In the pooling module, nodes are clustered together only if they are similar at the specific characteristic. Using a set of filters, we could learn the various characteristics of nodes, and obtain a series of coarse-grained graphs. Complexity Analysis. Considering channel i at layer l, we analyze the time complexity to learn the node's characteristics based on Equation It is linearly increase with the product of step K and channels C l . We provide the running time analysis in the Appendix.

Experiments
We evaluate our MuchGCN on the task of graph classification to answer the following three questions: • Q1: How does MuchGCN perform when it is compared with other state-of-the-art models?
• Q2: How does the multiple channels in MuchGCN help improve the graph representation learning ability and the classification accuracy?  Table 4 in Appendix.

Baselines.
We compare MuchGCN with three classes of state-of-the-art baselines: (1) the kernel methods that include WL subtree [21] and GRAPHLET [22]; (2) the flat GNNs that contain GCN [15], GRAPHSAGE [23], PATCHYSAN [24], DCNN [25], DGCNN [26] and ECC [27]; (3) the hierarchical GNN of DIFFPOOL. In the flat GNNs, the graph representation is produced via the global pooling or with the 1-D convolutions over the ordered nodes. DIFF-POOL stacks GRAPHSAGE hierarchically to learn the coarse-grained structures in work [8]. We implement the another DIFFPOOL framework built on GCN, and compare with both of them. The graph classification performances of GCN and DIFFPOOL based on GCN are obtained via running the models under the same environment with MuchGCN. Those of the others are reported from the publications directly.

Implementation Details. MuchGCN is built upon the intra-channel and inter-channel graph convolutions as shown in Equations (3.3) and (3.5).
We have K = 3 for the message passing step, and d = 64 for the hidden dimension. The assign ratios r l of 0.25 and 0.1 are applied for the 3-layer and 2-layer architectures, respectively. The GlobalPool function is given by the maximization pooling to read out the graph representation. Batch normalization [28] and l 2 normalization are applied after each step of graph convolutions to make the training more stable. We regularize the objective function by the entropy of cluster matrix to make the cluster pooling more sparse [8]. The Adam optimizer is adopted to train MuchGCN, and the gradient is clipped when its norm exceeds 2.0. We evaluate MuchGCN with the 10-fold cross validation, at which the average classification accuracy and standard deviation are reported. The model is trained with total of 100 epochs on each fold. Three variants of MuchGCN are considered here: • MuchGCN-M: the tailored MuchGCN framework only learns the multiple characteristics of nodes. We have channel expansion T l = 4, at which a set of 4 convolutional filters learns a series of new graphs based on Equation 3.4. In addition, we have layer number L = 1 to remove the pooling module. It encodes the input graph like the multi-graph GNN.
• MuchGCN-H, the tailored one only learns the hierarchical architectures. We apply the following architecture settings: T l = 1 and L > 1. MuchGCN encodes one coarse-grained structure at each layer like DIFFPOOL. To be specific, a total of L = 3 lay-ers are used for PROTEINS datasets, while the other datasets have the similar performances when L = 2.
• MuchGCN-MH, the complete MuchGCN framework learns the multiple characteristics and hierarchical architectures simultaneously. Here the framework have the same channel expansion with MuchGCN-M, and the same layer number with MuchGCN-H. Table 1 compares the graph classification accuracy of MuchGCN-MH to those of all the baselines, and provides positive answers for Q1. We observe that MuchGCN-MH achieves state-ofthe-art classification performance on 6 out of 7 benchmarks. To be specific, we consider the baseline methods of WL subtree, GCN, DIFFPOOL-GCN, variants MuchGCN-H and MuchGCN-M. MuchGCN-MH obtains the average improvements of 9.45%, 4.33%, 3.22%, 2.13% and 3.29%, respectively. Especially, it outperforms DIFFPOOL-GCN significantly on REDDIT-MULTI-12K dataset. This is expected because the baseline methods are not in line with the task of graph classification with the following facts. First, the kernel method predefines some substructure features to measure the input graph manually, failing to learn the representative hidden embedding. Second, GNN obtains the graph representation flatly with a simple global pooling layer. It is problematic for classifying the graphstructured data, which is inherently multi-characteristic and hierarchical. Third, the hierarchical networks of DIFFPOOL and MuchGCN-H pool the input graph gradually and generate a coarse-grained structure at each layer. The pooling module loses the detailed graph information at the higher layers of model, and makes it hard to distinguish the heterogeneous graphs. Although the multi-graph GNN of MuchGCN-M exploits the various characteristics of nodes, it is actually a shallow model that would be unable to reach the abstract expression of the input graph. MuchGCN-MH successfully encodes both the multiple characteristics and hierarchical structures of the input graph. It bridges the gap between the hierarchical and multi-graph frameworks. One the one hand, the pooling modules are stacked to built up a hierarchical model. The graph convolutions operate on the coarsegrained graphs to learn the abstract representation. On the other hand, the convolutional filters learn the various characteristics of nodes. Via pooling the nodes in different ways, we generate a series of coarse-grained graphs at the next layer. That would help preserve the information of input graph to a large extent.

Effectiveness Validation of Multiple
Channels. There is a series of channels learned at each layer of MuchGCN. They could be concatenated and regarded as a super graph. At layer l, the total node numbers in DIFFPOOL and MuchGCN are given by n l and C l n l , respectively. When channel number C l > 1, MuchGCN has much more nodes than the DIFFPOOL. It would be hard to claim that the performance advantage of MuchGCN relies mostly on the channels encoded with different characteristics, rather than simply reserving more nodes. In this subsection, we validate how multiple channels improve the graph representation learning ability to answer Q2. The channel expansion and cluster ratio of MuchGCN are fixed to control the related variables: T l = 4 and r l = 0.25. For DIFFPOOL, we gradually increase the node number in the coarse-grained graphs by considering the following ratios r l : 0.25, 0.5 and 1. The last one has the same node number with MuchGCN at each layer, in order to provide a fair comparison. We compare the two models comprehensively by considering different depths of the hierarchical neural networks, and show their graph classification accuracies in Table 2.
The following observations are made to claim the effectiveness of multiple channels in learning the graph representation. First, comparing the DIFFPOOL frameworks with different r l (i.e., 0.25 and 1), the larger ratio leads to a more smaller classification accuracy  when layer number L = 4. Ratio r l of 1 preserves more node clusters and structure information in the pooled graphs, which are expected to help distinguish the graphs. However, in the deeper hierarchical frameworks, these extra node clusters may introduce noise to the coarse-grained structure of the input graph. That is because the optimal number of node clusters could be decided under the supervision by the given task. Second, it is observed that MuchGCN outperforms DIFF-POOL consistently even when they have the same node number (i.e., DIFFPOOL of r l = 1). Especially, while the classification accuracy of DIFFPOOL decreases significantly with L, those of MuchGCN remain stable accompanied with a small variance. Instead of directly retaining more nodes, we learn the various characteris-  tics of nodes, and pool them is different ways to obtain a series of channels. This is in line with the real-world graph-structured data, which is intrinsically multi-view.

Performance improvement via Increasing
Channels. Moving a step forward, we study the variation of graph classification performance with the channel numbers, and answer the research question Q2. We reuse two of the well-performed MuchGCN frameworks in the previous experiments: L = 2 and L = 3. Both of them have the cluster ratio r l of 0.25. Enhancing the channel expansion T l from 1 to 4, we show the classification accuracy of MuchGCN in Table 3 It is obvious that the larger T l is, the better the classification accuracy could be achieved generally. The reason is intuitive that the multiple channels help encode more graph characteristics. By preserving more and more graph information at the higher layer of model, it would be more easier for the downstream classifier to distinguish the non-isomorphic graphs.

Hyperparameter Studies. We investigate the effects of some important hyperparameters on
MuchGCN to provide answer for research question Q3. Both cluster ratio r l and message passing step K are evaluated in this section. The pooling module equipped with large r l will generate the more complex coarsegrained graphs. The large step K compute the neighborhood structure of much more hops away in the graph convolutions. We use the following basic configuration of MuchGCN: L = 2 and T l = 4. The effects of hyperparameters r l and K on this underlying framework are shown in Figure 2.
We observe that different r l have the similar best ones of classification accuracy. That is because the pooling module can adaptively learn the appropriate number of node clusters. Compared with the case of small r l , some node clusters in the coarse-grained graph may be empty or even introduce noise in the case of large r l . This phenomenon is also explained in the previous experiments and the related works [8]. Considering the message passing step K, the larger one provides the more accurate classification when r l is small. Otherwise when r l is large, the smaller one of K tends to achieve the better classification accuracy. On the one hand, the increasing convolutional steps update the node embedding globally with the distant neighbors. The improved node embedding help improve the graph representation learning and hence the classification performance when r l is small. On the other hand, the node embeddings across a graph are close to each other in the Euclidean space with the increment of message passing steps K. The unrelated nodes may be assigned together to the noisy and redundant clusters when r l is large.

Conclusion
Motivated by the CNN architecture, we propose the framework named MuchGCN to learn the graph representation specifically. Comparable with CNN, the series of coarse-grained graph channels are encoded layer by layer for the graph-structured data. In detail, we design the graph convolutional filters to learn the various characteristics of nodes in the series of graph channels. The inter-channel graph convolutions are given to aggregate the entire graph channels and generate the one at the next layer. Experimental results show that we achieve state-of-the-art performance on the task of graph classification, and improve model robustness greatly. In the future works, we would apply MuchGCN to other tasks, such as the node classification and link prediction.

A Dataset Statistics
The statistics of all the 7 datasets are summarized in Table 4. Each one consists of a series of graphs accompanied with the graph labels. In Table 4, # Graphs denotes the total number of graphs in the corresponding dataset. # Classes denotes the class number of the graph label. The fourth and fifth columns denotes the average numbers of nodes and edges in each graph. The column of Node Label denotes whether there exists the node attribute or not in the dataset. B.2 Features of Input Graph. Importantly, our goal is to learn the hierarchical graph representations via graph structure A rather than relying on the input feature X. We don't choose the specific input features for each dataset to further improve the classification accuracy. We follow the experimental setting in the state-of-the-art frameworks. The input feature X in the bioinformatic datasets includes categorical label, degree and clustering coefficient. It contains only the degree information in the social network datasets. The maximum node number of input graph is set to 100 to cover all graphs in PTC, IMDB-B and IMDB-M. On the other hand, it takes the value of 500 in D&D, PROTEINS, COLLAB and RDT-M12K.

B.3 Implementation Details of MuchGCN.
Our proposed MuchGCN is built upon intra-channel and inter-channel graph convolutions as shown in Equations (3.3) and (3.5) in the paper. We have K = 3 for the message passing step, and d = 64 for the hidden dimension. A total of L = 3 layers are used for PRO-TEINS datasets, while the others have similar performance when L = 2. The assign ratio r l is set to 0.25 and 0.1 for the 3-layer and 2-layer architectures, respectively. The non-linear functions σ and f are given by RuLU and MLP, respectively. GlobalPool function is realized by maximization pooling to read out graph representation. Batch normalization and l 2 normalization are applied after each graph convolution operation to make the training more stable. We regularize the objective function by the entropy of the assignment matrix to make the cluster assignment sparse. 10-fold cross validation is applied to evaluate the performance of MuchGCN, whose average classification accuracy and standard deviation are reported. Total of 100 epochs is trained. The Adam optimizer is adopted to train MuchGCN, and the gradient is clipped when its norm exceeds 2.0.
B.4 Implementation Details of Baselines. For the baselines of GCN and DIFFPOOL-GCN, we implement the source code provided by the authors of DIFF-POOL [8]. The running environment setting is the same with the suggestions in the publication. For the other baseline methods, we directly cite the results from the corresponding publications.

C Proof for Proposition 1
Proof. In this section, we provide proof to analyze how Equation (3.4) assigns unique embedding for node a. To facilitate the following analysis, we ignore the notation of (l, j) in Equation (3.4) in the paper. The embedding multiset of node a is represented as follows: We use vector h a i to represent the input feature x a , embedding features h a k and h a,c k aggregated from the current and neighboring channels, respectively. The size of multiset H(a) is denoted by m.
Here m = 1 + KC l , at which K denotes the message passing step and C l denotes the channel number. According to Equation (3.4) in paper, the final embedding of node a is given by: where θ i is the i-th element of filter θ, and φ is realized by MLP function. Note that θ i is a scalar and h a i is a d-dimensional vector.
We need to prove that the embedding z a of nodes a is unique if it has unique multisets H(a). Assume the set H constructed by all d-dimensional node embeddings is countable. According to Corollary 6 in [14], there exists function f : H → R d , so that the value of h a i ∈H(a) f (h a i ) is unique for each unique multiset H(a). Suppose that filter θ is normalized where i θ i = 1. We then reformulate Equation (3.7) as z a = φ( i θ i (h a i + b)). Thanks to the universal approximation theorem, we could model and learn function f via the nonlinear function φ implemented by MLP. Since MLP can represent the composition of two consecutive MLP, we have the following equivalence in generating embedding Based on Corollary 6 in [14], to prove z a is unique for each unique multiset H(a), we first need to show that the new set H new composed of the scaled embeddings θ i (h a i + b) is countable. It's obvious that the set H b obtained by adding bias b into each element of H is still countable. Set H θi obtained by scaling each element of H b with θ i is also countable. In consequence, the new set H new is countable since it is constructed by the union as follows: (3.9) H new = H b ∪ H θ1 · · · ∪ H θm . Suppose that H new (a) and H new (c) are the same multiset. Then there exits m matched pairs of θ i (h a i +b) and θ j (h c j + b), which satisfies the condition of θ i (h a i + b) = θ j (h c j + b). For each i-th element in H new (a), their exits the matched j-th element in H new (c). It means that the condition of θ i h a i − θ j h c j = (θ j − θ i )b needs to be satisfied for all matched pairs. However, there exists infinitely many b that are not applicable to such condition. Let us consider the following three cases when index i = j: (1) θ i = θ j but h a i = h c j , (2) θ i = θ j but h a i = h c j , and (3) θ i = θ j and h a i = h c j . For the first case, the condition is reduced to θ i (h a i − h c j ) = 0, which is obviously not satisfied by any choice of b since θ i = 0. For the second case, the condition is reduced to h a i = −b, which means that some embeddings h a i during the K steps of message passing are equal to scalar b. It is generally hard to be satisfied since the node embedding changes after aggregating neighbor features at each step. For the third case, the condition is reduced to b = θih a i −θj h c j θj −θi , which is also generally impossible because it is hard to force all elements of d-dimensional vector of

D Running Time Analysis
Given the time complexity analysis in the paper, we evaluate the running time of MuchGCN under the abovementioned environment. We study the running time variation with the message passing step K and channel expansion C l . The underlying neural architecture of MuchGCN is shown as follows: L = 2 and r l = 0.1. The average running time of each epoch is shown in Figure 3.
It is obvious that the running time of MuchGCN is almost linearly increasing with step K and channel expansion C l . The experimental result is consistent with our analysis in the paper.