Multi-Channel Graph Convolutions

## Abstract

Abstract 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 mu lti- ch annel 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.

## 1 Introduction

Classifying graph-structured data has become an important problem in various domains, such as the biological graph analysis []. Among the numerous graph classification techniques, graph neural networks (GNN) [, , ] 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 [, , ], which encodes the input graph flatly.

To further improve performance, the hierarchical GNNs are proposed to encode both the local and coarse-grained structures of the input graph  [, , ]. 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 coarse-grained 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 multi-view 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.

Figure: Figure 1: An illustration of the MuchGCN framework consisted of $2$ layers. 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.
Refer to caption: /html/1912.08306/assets/x1.png

Recently, the multi-graph GNNs have been proposed to learn the various node characteristics [, , ]. 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, 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](#S1.F1), 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 channel-wise 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](#S1.F1). 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 state-of-the-art baselines.

## 2 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\in\{0,1\}^{n\times n}$ denotes the adjacency matrix, and $X\in\mathbb{R}^{n\times 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},\dots,G_{N}\}\subset\mathcal{G}$ and the corresponding labels $\{y_{1},\dots,y_{N}\}\subset\mathcal{Y}$, the challenge is to extract the informative graph representations to facilitate the following graph classification: $f:\mathcal{G}\to\mathcal{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 []:

$$ (2.1) $H_{k}=\sigma((H_{k-1}+AH_{k-1})W_{k})\in\mathbb{R}^{n\times d},$ $$

where $H_{k}$ denotes the hidden node embedding after $k$ steps of graph convolutions, $W_{k}\in\mathbb{R}^{d\times d}$ denotes the linear transformation matrix, and $\sigma$ 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 []. 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=\mathrm{GNN}(A,X)\in\mathbb{R}^{n\times d}$. To tackle the task of graph classification, the graph representation is generated by globally pooling the $n$ node embedding in matrix $Z$.

### 2.2 Differentiable Pooling.

A major limitation of Equation ([2.1](#S2.E1)) is that it encodes only the superficial structure of the input graph. Recently, the differentiable pooling [] (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)}\in\mathbb{R}^{n_{l}\times n_{l+1}}$ and $Z^{(l)}\in\mathbb{R}^{n_{l}\times 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:

$$ (2.2) $\displaystyle X^{(l+1)}$ $\displaystyle=S^{(l)^{T}}Z^{(l)}\in\mathbb{R}^{n_{l+1}\times d},$ $\displaystyle A^{(l+1)}$ $\displaystyle=S^{(l)^{T}}A^{(l)}S^{(l)}\in\mathbb{R}^{n_{l+1}\times n_{l+1}},$ $$

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 $\mathrm{GNN}$ modules are used: $Z^{(l)}=\mathrm{GNN}_{l,\mathrm{embed}}(A^{(l)},X^{(l)})$ and $S^{(l)}=\mathrm{softmax}(\mathrm{GNN}_{l,\mathrm{pool}}(A^{(l)},X^{(l)}))$. The $\mathrm{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.

### 2.3 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](#S2.E1)), the graph convolutions learn the node embedding at each graph instance independently as follows: $Z^{i}=\mathrm{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.

## 3 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](#S1.F1). 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](#S1.F1). 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)},\cdots,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](#S1.F1), layer 0 0 consists of one channel: $[G^{0}=\{X^{0},A^{0}\}]$, and layer $1$ consists of two channels $[G^{1}=\{X^{1},A^{1}\},G^{2}=\{X^{2},A^{2}\}]$.

### 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 upper-left node in graph $\{X^{0},A^{0}\}$ has only one neighbor as shown in Figure [1](#S1.F1), 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\times 3$) cannot learn the node’s characteristics 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 inter-channel graph convolutions passing messages among the graph channels to aggregate their features. As shown in Figure [1](#S1.F1), we first describe how MuchGCN learns the node’s characteristics in the single channel at layer 0 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:

$$ (3.3) $H^{i}_{k}=\sigma([H^{i}_{k-1}+A^{i}\cdot H^{i}_{k-1}]\cdot W^{(l)}_{k}),$ $$

where $W^{(l)}_{k}$ denotes the trainable parameter for the $k$-th 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  [], 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 $\mathcal{H}^{0}=[X^{0},H^{0}_{k}]$ that consists of the input feature and all intermediate node embeddings, where $k=1,\cdots,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 $\theta^{(l,j)}\in\mathbb{R}^{1\times(K+1)}$ learns the new graph associated with embedding $Z^{(l,j)}$ as follows:

$$ (3.4) $Z^{(l,j)}=\phi(\mathrm{sum}(\mathcal{H}^{i}\odot\theta^{(l,j)})+b)\in\mathbb{R}^{n_{l}\times d},$ $$

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](#S1.F1). $\phi$, $\mathrm{sum}$ and $\odot$ denote the non-linear function of multilayer perceptron (MLP), summation function and element-wise 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 0.

Based on the graph pooling defined in Equation ([2.2](#S2.E2)), channel $j$ at the next layer are generated from the learned embeddings $Z^{(l,j)}$ and $S^{(l,j)}$. As shown in Figure [1](#S1.F1), we have channels $G^{1}=\{X^{1},A^{1}\}$ and $G^{2}=\{X^{2},A^{2}\}$ at layer $1$, which encode different coarse-grained 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: $A^{1,2}=S^{(0,1)^{T}}A^{0}S^{(0,2)}\in\mathbb{R}^{n_{1}\times n_{1}}$. 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 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 coarse-grained 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 intra-channel graph convolutions is given by Equation ([3.3](#S3.E3)), at which the indexes of channel and layer are replaced by $i=1$ and $l=1$. Based on Equation ([3.3](#S3.E3)), the inter-channel graph convolutions is defined as follows:

$$ (3.5) $H^{i,c}_{k}=\sigma([H^{i,c}_{k-1}+A^{i,c}\cdot H^{c}_{k-1}]\cdot W^{(l)}_{k}).$ $$

$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 intra-channel 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](#S3.E4)). Different with embedding multiset $\mathcal{H}^{0}$ at channel 0 0, the one at channel $i$ is given by $\mathcal{H}^{i}=[X^{i},H^{i}_{k},H^{i,c}_{k}]$ at the higher layer of model. It includes embedding $H^{i,c}_{k}$ to aggregate features from all the neighboring channels $c$.
Specifically, we have $\mathcal{H}^{1}=[X^{1},H^{1}_{k},H^{1,2}_{k}]$ at channel $1$. Given the set of filter $\theta^{(l,j)}$, Equation ([3.4](#S3.E4)) encodes the various characteristics and obtains a series of graphs from channel $1$. As shown in Figure [1](#S1.F1), 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)}$.

#### 3.1.3 Multi-channel Graph Convolutional Networks.

We stack $L$ layers of graph convolutions and feature learning in MuchGCN, at which $L=2$ in Figure [1](#S1.F1). Let $n_{l}$ and $C_{l}$ denote the node number of a graph and the channel number at layer $l$, respectively. We define $r_{l}\triangleq\frac{n_{l+1}}{n_{l}}$ named *assign ratio*, and define $T_{l}\triangleq\frac{C_{l+1}}{C_{l}}$ named *channel expansion*. Generally, the relation of $0<r_{l}\leq 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,\cdots,C_{l}T_{l}$. As shown in Figure [1](#S1.F1), we have $C_{1}T_{1}=2\times 2$ at layer $1$. The graph representation $Y^{(l)}$ learned at layer $l$ could be obtained by combining the generated graphs as follows:

$$ (3.6) $Y^{(l)}=\sum_{j=1}^{C_{l}T_{l}}(\mathrm{GlobalPool}(Z^{(l,j)}))\in\mathbb{R}^{d\times 1},$ $$

where $\mathrm{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=\oplus_{l}Y^{(l)}\in\mathbb{R}^{d\cdot L\times 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.

### 3.2 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 multiset $\mathcal{H}^{i}=[X^{i},H^{i}_{k},H^{i,c}_{k}]$ based on the intra-channel and inter-channel graph convolutions. Then, Equation ([3.4](#S3.E4)) encodes a specific characteristic via filter $\theta^{(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 $\mathcal{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 $\phi$ and infinitely many scalars $b$ in Equation ([3.4](#S3.E4)), so that node $a$ has the unique embedding $z^{a}$ if the following conditions are satisfied:

a) Node $a$ has unique multiset $\mathcal{H}(a)$.

b) The trainable filter $\theta^{(l,j)}\neq 0$.

A proof is provided in Section [C](#A3) of Appendix. Node characteristic is computationally represented by the convolutions between multiset $\mathcal{H}(a)$ and $\theta^{(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 ([3.4](#S3.E4)). First, node embeddings $H^{i}_{k}$ and $H^{i,c}_{k}$ within multiset $\mathcal{H}^{i}$ need to be prepared according to Equations ([3.3](#S3.E3)) and ([3.5](#S3.E5)), respectively. Let $m$ denote the maximum number of edges within channel $i$ or between channels $i$ and $j$. Since adjacency matrices $A^{i}$ and $A^{i,c}$ are usually sparse, we have $m\ll n_{l}^{2}$. The complexities of Equations ([3.3](#S3.E3)) and ([3.5](#S3.E5)) are $\mathcal{O}(md^{2})$ and $\mathcal{O}(n_{l}d^{2}+md^{2})$, respectively. There are total $K$ steps of message passing in the graph convolutions, and $C_{l}-1$ neighboring channels waited to be aggregated. Therefore, the complexity of obtaining embedding multiset $\mathcal{H}^{i}$ is given by $\mathcal{O}(K[C_{l}md^{2}+(C_{l}-1)n_{l}d^{2}])$. Second, the element-wise multiplication in Equation ([3.4](#S3.E4)) takes the computation cost of $\mathcal{O}((KC_{l}+1)n_{l}d)$. Based on the above two components, the sum of time complexity in feature learning is shown as follows: $\mathcal{O}(K[C_{l}md^{2}+(C_{l}-1)n_{l}d^{2}]+(KC_{l}+1)n_{l}d)$. It is linearly increase with the product of step $K$ and channels $C_{l}$. We provide the running time analysis in the Appendix.

## 4 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?
- •
Q3: How does the important hyperparameters in MuchGCN affect the network performance?

### 4.1 Experiment Settings

#### 4.1.1 Datasets.

We use $7$ graph classification benchmarks suggested in [, ]: $3$ bioinformatic datasets (PTC, DD,
PROTEINS [, ]) and $4$ social network datasets (COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY-MULTI-12K []). The detailed statistics of these seven datasets are summarized in Table [4](#A1.T4) in Appendix.

#### 4.1.2 Baselines.

We compare MuchGCN with three classes of state-of-the-art baselines: (1) the kernel methods that include WL subtree [] and GRAPHLET []; (2) the flat GNNs that contain GCN [], GRAPHSAGE [], PATCHYSAN [], DCNN [], DGCNN [] and ECC []; (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. DIFFPOOL stacks GRAPHSAGE hierarchically to learn the coarse-grained structures in work []. 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.

#### 4.1.3 Implementation Details.

MuchGCN is built upon the intra-channel and inter-channel graph convolutions as shown in Equations ([3.3](#S3.E3)) and ([3.5](#S3.E5)). 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 $\mathrm{GlobalPool}$ function is given by the maximization pooling to read out the graph representation. Batch normalization [] 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 []. 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](#S3.E4). 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$ layers 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.

### 4.2 Graph Classification Results

#### 4.2.1 Model Comparison.

Table [1](#S4.T1) 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-of-the-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 graph-structured 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 coarse-grained 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.

**Table 1: Classification accuracy and stand deviation in percent. The best results are highlighted with boldface. DP-GSAGE and DP-DCN denote the baseline DIFFPOOL built upon GRAPHSAGE and GCN, respectively. Symbol ’-’ represents that we cannot find the available classification results in the publications.**
| Methods | Datasets |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| PTC | DD | PROTEINS | COLLAB | IMDB-B | IMDB-M | RDT-M12K |  |
| WL subtree | $59.90$$\pm 4.3$ | $79.78$$\pm 0.4$ | $75.00$$\pm 3.1$ | $78.90$$\pm 1.9$ | $73.80$$\pm 3.9$ | $50.90$$\pm 3.8$ | $39.03$ |
| GRAPHLET | $57.26$$\pm 1.4$ | $78.45$ | $71.67$$\pm 0.6$ | $72.84$$\pm 0.3$ | $65.87$$\pm 1.0$ | $43.89$$\pm 0.4$ | $31.82$$\pm 0.1$ |
| GCN | $62.26$$\pm 4.8$ | $77.83$$\pm 4.2$ | $76.30$$\pm 2.3$ | $80.78$$\pm 1.8$ | $78.48$$\pm 1.9$ | $54.60$$\pm 2.2$ | $45.03$$\pm 1.9$ |
| GRAPHSAGE | $63.9$$\pm 7.7$ | $75.42$ | $70.48$ | $68.25$ | $72.3\pm 5.3$ | $50.9\pm 2.2$ | $42.24$ |
| PATCHYSAN | $62.29$$\pm 5.7$ | $76.27$$\pm 2.6$ | $75.00$$\pm 2.5$ | $72.60$$\pm 2.2$ | $71.00$$\pm 2.3$ | $45.23$$\pm 2.8$ | $41.32$$\pm 0.4$ |
| DCNN | $56.60$ | - | $61.30$ | $52.10$ | $49.10$ | $33.50$ | - |
| DGCNN | $58.59$$\pm 2.5$ | $79.37$$\pm 1.0$ | $75.54$$\pm 1.0$ | $73.76$$\pm 0.5$ | $70.03$$\pm 0.9$ | $47.83$$\pm 0.9$ | $41.82$ |
| ECC | - | $73.65$ | $72.65$ | $67.79$ | - | - | $41.73$ |
| DP-GSAGE | - | $80.64$ | $76.25$ | $75.48$ | - | - | $\bm{47.08}$ |
| DP-GCN | $64.85$$\pm 4.3$ | $79.43$$\pm 4.1$ | $75.63$$\pm 2.7$ | $81.25$$\pm 1.1$ | $80.18$$\pm 1.8$ | $55.0$$\pm 2.4$ | $19.24$$\pm 2.0$ |
| MuchGCN-M | $67.69$$\pm 7.1$ | $80.47$$\pm 4.3$ | $79.30$$\pm 3.3$ | $81.56$$\pm 1.4$ | $80.59$$\pm 2.6$ | $56.20$$\pm 2.2$ | $38.47$$\pm 1.1$ |
| MuchGCN-H | $63.67$$\pm 4.6$ | $78.67$$\pm 4.0$ | $78.93$$\pm 2.7$ | $81.36$$\pm 1.4$ | $80.99$$\pm 3.0$ | $56.07$$\pm 2.4$ | $44.99$$\pm 3.0$ |
| MuchGCN-MH | $\bm{68.08}$$\bm{\pm 4.8}$ | $\bm{80.87}$$\bm{\pm 4.4}$ | $\bm{79.84}$$\bm{\pm 2.6}$ | $\bm{81.72}$$\bm{\pm 1.6}$ | $\bm{81.26}$$\bm{\pm 2.5}$ | $\bm{56.73}$$\bm{\pm 1.7}$ | $45.92$$\pm 2.9$ |

#### 4.2.2 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](#S4.T2).

**Table 2: Classification accuracy in percent on PROTEINS dataset. MuchGCN and DIFFPOOL built upon GCN are compared under different scenarios of layer number $L$, which ranges from $2$ to $4$.**
| Methods | $r_{l}$ | $T_{l}$ | Layer number $L$ | Variance |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | 3 | 4 |  |  |  |  |
| DP-GCN | $0.25$ | $1$ | $77.15$ | $75.63$ | $73.42$ | $2.35$ |
| DP-GCN | $0.5$ | $1$ | $77.88$ | $71.68$ | $70.03$ | $11.42$ |
| DP-GCN | $1$ | $1$ | $78.59$ | $78.74$ | $73.23$ | $6.57$ |
| MuchGCN | $0.25$ | $4$ | $\bm{79.21}$ | $\bm{79.84}$ | $\bm{78.94}$ | $\bm{0.14}$ |

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 DIFFPOOL 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 characteristics 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.

#### 4.2.3 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](#S4.T3)。

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.

**Table 3: Classification accuracy in percent on PROTEINS dataset. A series of channel expansions are evaluated to measure their contributions to the graph representation learning of MuchGCN.**
| Layer | Ratio | Channel expansion $T_{l}$ |  |  |  |
| --- | --- | --- | --- | --- | --- |
| $L$ | $r_{l}$ | 1 | 2 | 3 | 4 |
| 2 | $0.25$ | $78.85$ | $79.75$ | $\bm{79.93}$ | $79.21$ |
| 3 | $0.25$ | $78.93$ | $79.38$ | $79.83$ | $\bm{79.84}$ |

#### 4.2.4 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 coarse-grained 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](#S4.F2).

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 []. 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.

Figure: Figure 2: Classification accuracy in percent on PROTEINS dateset. The hyperparameters of cluster ration $r_{l}$ and message passing step $K$ are evaluated to measure their effects on MuchGCN.
Refer to caption: /html/1912.08306/assets/x2.png

## 5 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.

## Appendix A Dataset Statistics

The statistics of all the $7$ datasets are summarized in Table [4](#A1.T4). Each one consists of a series of graphs accompanied with the graph labels. In Table [4](#A1.T4), # 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.

**Table 4: Dataset Statistics.**
| Datasets | # Graphs | # Classes | Avg.# Nodes per Graph | Avg.# Edges per Graph | Node Label |
| --- | --- | --- | --- | --- | --- |
| PTC | $344$ | $2$ | $14.29$ | $14.69$ | Y |
| D&D | $1178$ | $2$ | $284.32$ | $715.66$ | Y |
| PROTEINS | $1113$ | $2$ | $39.06$ | $72.82$ | Y |
| COLLAB | $5000$ | $3$ | $74.49$ | $2457.78$ | Y |
| IMDB-B | $1000$ | $2$ | $19.77$ | $96.53$ | N |
| IMDB-M | $1500$ | $3$ | $13.00$ | $65.94$ | N |
| RDT-M12K | $11929$ | $11$ | $391.41$ | $456.89$ | N |

## Appendix B Implementation Details

### B.1 Running Environment.

The baseline methods of GCN, DIFFPOOL-GCN and our proposed MuchGCN are implemented in PyTorch, and tested on a machine with 24 Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GB processors, 4 GeForce GTX-1080 Ti 12 GB GPU, and 128GB memory size. The random seed for packages numpy and torch is set to $100$.

### 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 PROTEINS 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 $\sigma$ and $f$ are given by RuLU and MLP, respectively. $\mathrm{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 DIFFPOOL []. 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.

## Appendix 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: $\mathcal{H}(a)=[h^{a}_{i}]$, $i=1,\cdots m$. 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 $\mathcal{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:

$$ (3.7) $z^{a}=\phi(\sum_{i}\theta_{i}h^{a}_{i}+b),$ $$

where $\theta_{i}$ is the $i$-th element of filter $\theta$, and $\phi$ is realized by MLP function. Note that $\theta_{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 $\mathcal{H}(a)$. Assume the set $\mathcal{H}$ constructed by all $d$-dimensional node embeddings is countable. According to Corollary $6$ in [], there exists function $f:\mathcal{H}\to\mathbb{R}^{d}$, so that the value of $\sum_{h^{a}_{i}\in\mathcal{H}(a)}f(h^{a}_{i})$ is unique for each unique multiset $\mathcal{H}(a)$. Suppose that filter $\theta$ is normalized where $\sum_{i}\theta_{i}=1$. We then reformulate Equation ([3.7](#A3.E7)) as $z^{a}=\phi(\sum_{i}\theta_{i}(h^{a}_{i}+b))$. Thanks to the universal approximation theorem, we could model and learn function $f$ via the non-linear function $\phi$ implemented by MLP. Since MLP can represent the composition of two consecutive MLP, we have the following equivalence in generating embedding $z^{a}$:

$$ (3.8) $\displaystyle z^{a}$ $\displaystyle=\phi(\sum_{i}\theta_{i}(h^{a}_{i}+b))$ $\displaystyle=\phi(\sum_{i}\phi(\theta_{i}(h^{a}_{i}+b)))$ $\displaystyle=\sum_{i}\phi(\theta_{i}(h^{a}_{i}+b)).$ $$

Based on Corollary $6$ in [], to prove $z^{a}$ is unique for each unique multiset $\mathcal{H}(a)$, we first need to show that the new set $\mathcal{H}^{new}$ composed of the scaled embeddings $\theta_{i}(h^{a}_{i}+b)$ is countable. It’s obvious that the set $\mathcal{H}^{b}$ obtained by adding bias $b$ into each element of $\mathcal{H}$ is still countable. Set $\mathcal{H}^{\theta_{i}}$ obtained by scaling each element of $\mathcal{H}^{b}$ with $\theta_{i}$ is also countable. In consequence, the new set $\mathcal{H}^{new}$ is countable since it is constructed by the union as follows:

$$ (3.9) $\mathcal{H}^{new}=\mathcal{H}^{b}\cup\mathcal{H}^{\theta_{1}}\cdots\cup\mathcal{H}^{\theta_{m}}.$ $$

Following the above analysis, embedding $z^{a}$ is unique only if the scaled multiset $\mathcal{H}^{new}(a)=[\theta_{i}(h^{a}_{i}+b)]$ is still unique. Given different multisets $\mathcal{H}(a)=[h^{a}_{i}]$ and $\mathcal{H}(c)=[h^{c}_{i}]$ of nodes $a$ and $c$, we need to show that the scaled multisets $\mathcal{H}^{new}(a)=[\theta_{i}(h^{a}_{i}+b)]$ and $\mathcal{H}^{new}(c)=[\theta_{i}(h^{c}_{i}+b)]$ are still different. In the following, we provide the proof by contradiction.

Suppose that $\mathcal{H}^{new}(a)$ and $\mathcal{H}^{new}(c)$ are the same multiset. Then there exits $m$ matched pairs of $\theta_{i}(h^{a}_{i}+b)$ and $\theta_{j}(h^{c}_{j}+b)$, which satisfies the condition of $\theta_{i}(h^{a}_{i}+b)=\theta_{j}(h^{c}_{j}+b)$. For each $i$-th element in $\mathcal{H}^{new}(a)$, their exits the matched $j$-th element in $\mathcal{H}^{new}(c)$. It means that the condition of $\theta_{i}h^{a}_{i}-\theta_{j}h^{c}_{j}=(\theta_{j}-\theta_{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\neq j$: (1) $\theta_{i}=\theta_{j}$ but $h^{a}_{i}\neq h^{c}_{j}$, (2) $\theta_{i}\neq\theta_{j}$ but $h^{a}_{i}=h^{c}_{j}$, and (3) $\theta_{i}\neq\theta_{j}$ and $h^{a}_{i}\neq h^{c}_{j}$. For the first case, the condition is reduced to $\theta_{i}(h^{a}_{i}-h^{c}_{j})=0$, which is obviously not satisfied by any choice of $b$ since $\theta_{i}\neq 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=\frac{\theta_{i}h^{a}_{i}-\theta_{j}h^{c}_{j}}{\theta_{j}-\theta_{i}}$, which is also generally impossible because it is hard to force all elements of $d$-dimensional vector of $\frac{\theta_{i}h^{a}_{i}-\theta_{j}h^{c}_{j}}{\theta_{j}-\theta_{i}}$ to have the same value of $b$. Multisets $\mathcal{H}^{new}(a)$ and $\mathcal{H}^{new}(c)$ are the same only the following condition is satisfied: $h^{a}_{i}=h^{c}_{i}$ for $i=1,\cdots,m$. But this condition is contradicted with the assumption of multisets $\mathcal{H}(a)$ and $\mathcal{H}(c)$ are different. In consequence, we reach the result that multisets $\mathcal{H}^{new}(a)=[\theta_{i}(h^{a}_{i}+b)]$ and $\mathcal{H}^{new}(c)=[\theta_{i}(h^{c}_{i}+b)]$ are still different.

Given the node embedding $z^{a}$ generated by Equation ([3.8](#A3.E8)), we conclude that embedding $z_{a}$ is unique if multiset $\mathcal{H}(a)$ is unique.

Figure: Figure 3: Average running time of MuchGCN for each epoch.
Refer to caption: /html/1912.08306/assets/x3.png

## Appendix 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](#A3.F3).

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.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: - Figures 1 and 3 would require more detailed explanations in the caption, as they are currently difficult to understand.
- I think the definition “For d = 1, we refer to this as a single-channel signal, while for d > 1, we call it a multi-channel signal” may create confusion in the reader, as it seems to refer to the dimensionality of the feature. This is an essential point and would benefit from greater clarity.
- I would clearly explain the difference with multiple attention heads.
soundness: 2
strengths: The mathematical definition of convolution for multi-channel signals is very interesting and offers great potential; the authors, for example, used it as a basis for MC-GIN.
summary: The authors propose a multi-channel graph convolution (MCGC) based on the convolution theorem and the graph Fourier transform, specifically designed for multi-channel signals. In this context, the authors also introduce the multi-channel graph isomorphism network (MC-GIN), which provides a linear map with the same expressive power as the Graph Isomorphism Network (GIN).
weaknesses: Here is a list of points in the paper that do not convince me  (not in order of importance):
- I see no actual discussion regarding complexity (I may have missed it); only MAE-related times are reported, which are not very indicative.
- I find the introduction to the multi-channel concept confusing right from the initial definitions. For greater clarity, I would suggest also explaining the difference between multi-in multi-out and single-in multi-out from the beginning and perhaps providing clearer examples
- Unfortunately, although the paper is ok in many sections, the experimental part is truly lacking. Not only is the presentation of the experiments unclear, but the experiments themselves are also insufficient.
- While the idea of the Fourier transform for graphs is valid, it is unclear how innovative it truly is, which also affects the scientific contribution.
- The strengths of the work have not been clearly highlighted.

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 2
questions: None
soundness: 1
strengths: None
summary: The paper purports to define graph neural networks with multiple channels. Graph neural networks with multiple channels exist. They are actually standard in applications.
weaknesses: The paper proposes a learning architecture that already exits in the literature.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please refer to the Weaknesses section.
soundness: 2
strengths: 1. The authors' analysis and extension of the existing graph convolution definition is commendable.

2. Thm. 3 (although I still think it should be labeled as a Definition) is explained in detail, even though there are some typos.

3. The first set of experiments shows that using GAT+softmax is not suitable, which supports the previous analysis.
summary: Previous graph convolutions are generally defined on single-channel input signals, which are then applied to all channels in spectral GNNs. This paper proposes a definition of graph convolutions on multi-channel signals (**MCGCs**).

MCGCs are computationally difficult to implement, so the authors further propose an approximation of MCGCs called **MC-GINs**, allowing for localized computation. Before deriving MC-GINs, the authors point out that GAT+softmax cannot be directly applied to various graph structures, as it would make the graph row-stochastic. Based on such careful considerations with MC-GINs' architecture, the authors provide an expressiveness analysis. 

In the experiments, the authors validate the function-fitting ability of MC-GINs. They also conduct graph classification experiments, comparing MC-GINs with several classic baseline models.
weaknesses: 1. I believe the biggest issue is that the transition from MCGCs to MC-GINs is quite unconvincing. The authors mention the perspective of multiple edge relations, but **it's still too unclear what the relationship between Eq. 2 and Eq. 3 is**. The authors claim that MCGCs are computationally impractical, but the graphs used in the experiments are quite small. It should have been possible to conduct experiments on MCGCs without deriving MC-GINs.

2. Regarding **"Theorem 3.1"**, the authors state: "We emphasize that this form is a mathematical fact and not a definition made by us." However, I still consider this to be a definition by the authors: to handle multi-channel signals, couldn't we simply learn different filter functions for each channel separately? I think this is also a type of definition—similar to what JacoviConv and OptBasisGNN do.

3. **TYPO**: In the third block equation below Eq. 2, the tensor shapes on both sides of the element-wise multiplication do not match.

4. The **baselines** used in the second set of experiments are quite simple. Given the motivation of the paper, it seems more appropriate to compare against Spectral GNNs.

5. The authors emphasize that MC-GINs should be **localized**, but Proposition 3.3's **implementation of $f$ is not localized**. Because of this, the graphs used in the experiments are all small.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - Theorem 3.1 appears to be presented as a theorem, but it reads more like a mathematical definition of multi-channel convolution. Could the authors clarify this distinction? Is this an actual contribution of this paper?
- Beginning of section 3.1: can the authors elaborate on what are the different $\hat{A}^{(i)}$?
- Can the authors elaborate on the interplay between Theorem 3.2 and Figure 3? While the model shares GIN's expressivity, it is unclear why it outperforms for so much the single-channel GIN in simple function approximation. This difference in function approximation within the same class of expressivity is worth some discussion after Theorem 3.2.
- Is there a straightforward extension for multi-channel edges?
soundness: 2
strengths: - Innovative (even if the extension from scalar to vector data in graph convolution seems natural) and promising approach, with potential for further exploration. The concept of mixing node channels to form layer-specific learned representations is interesting, and the initial results look promising.
- The paper presents a clear and coherent storyline, making it accessible.
- Theorem 3.2 is a relevant extension of GIN's expressivity properties
summary: This paper introduces multi-channel data mixing for convolution-based graph neural networks. To achieve this, the authors propose Multi-Channel Graph Convolutions (MCGCs), which use the convolution theorem and graph Fourier transform to manage multi-feature node data—unlike conventional MPNNs, limited to single-channel signals. This multi-channel design allows MCGCs to create richer embeddings by amplifying distinct signals across channels. Building on this, the authors develop a scalable approximation, the Multi-Channel Graph Isomorphism Network (MC-GIN), which retains GIN-level expressivity (1-WL) while improving scalability. Experimental results indicate MCGCs can capture complex functions more effectively, although they may risk overfitting as task complexity grows.
weaknesses: - The authors frame the paper as offering a promising direction for improving convolution-based GNN architectures, yet more research is required on alternative approximations (e.g., MC-GIN) with better justification.
- Despite promising, the work is still preliminary and would benefit from further empirical validation; it’s only tested on a simple and carefully designed synthetic case and one real-world dataset. More comprehensive experiments are needed.
- The proposed method introduces new hyperparameters (e.g., the number of channels in intermediate layers), yet no strategy or guidance is offered for tuning these to avoid overfitting, as noted in the conclusion.
- Due to the additional parameters, this model incurs extra computational overhead. This point needs more clarification, discussion, and eventually empirical support by reporting runtimes. 
- Since runtime is crucial in model selection, the overhead imposed by MCGC and derived architectures (e.g., MC-GIN) should be discussed and illustrated with more datasets.
- Figure 2 is somewhat cluttered and challenging to interpret; reducing input/output channels or nodes/eigenvalues could improve clarity.  
- Figure 3 needs better formatting. Tables 1 and 2 would benefit from similar refinements. In these tables, runtime variability is not reported.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: I will encourage the authors to make a convincing argument for the novelty of their method. Also, I would encourage the authors to consider a numerical example in which the benefits of the proposed methodology are seen.
soundness: 3
strengths: 1. The paper is well-written. 
2. The main ideas ideas of the paper are clearly presented.
summary: The paper introduces an architecture for GNNs to be able to process more than one graph at a time. The proposed GNNs are based on multi-channel convolutions which are introduced in section 3. The paper is well-written and the ideas are clearly presented. However, this work carries little novelty, and the motivation for the work is poorly motivated. The numerical examples fail to show a clear benefit of the method here presented.
weaknesses: 1. The paper has very little novelty, multi-channel GNNs have been introduced long ago and in several contexts:

Multi-Channel Graph Neural Networks
Kaixiong Zhou et al. 

Multi-Channel Graph Neural Network for Entity Alignment
Yixin Cao et al.

DeepMCGCN: Multi-channel Deep Graph Neural Networks
Lei Meng et al. 

The authors should explain what is new in this work. 

2. Multi-channel graph convolutions are an example of polynomials on multi-graphs with degree 1:

Convolutional Filters and Neural Networks with Non-Commutative Algebras
A Parada-Mayorga, L Butler, A Ribeiro
IEEE Transactions on Signal Processing

Convolutional learning on multigraphs
L Butler, A Parada-Mayorga, A Ribeiro
IEEE Transactions on Signal Processing 71, 933-946

I fail to understand the benefit of the proposed methodology versus more general architectures. The authors should explain why their method (which is a particular case of multigraph convolutions) is both novel and beneficial.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. Don't the A's in the definition of MCGC have to be symmetric? I don't see it written.

2.  "a countable multiset" line 338 is not a valid definition. The multiset is finite (n elements) and each element comes from a space of countable size.

3. The proof of Proposition 3.3 is very uninformative and missing key details. The definition of the function f is not understandable. Please rewrite this proof much more rigorously.
soundness: 3
strengths: 1. Background on previous work is well-written and clear. It seems the authors are well-versed.

2. Injectivity results and derivation of results are correct as far as I can tell and are presented rigorously.

3. Important extension of a very popular graph learning paradigm with good empirical results.
summary: This paper proposes an extension of the popular GCN architecture to multiple channels. It relies on Fourier analysis and follows a derivation to that of GCN but for the multi-channel case. Then it offers a GNN, MCGC, based on this theoretical analysis and proves the 1-WL expressivity of the GNN. The utility of MCGC is demonstrated by an approximation experiment and strong results on the ZINC dataset.
weaknesses: 1. The connection between the derivation of MCGC and the actual architecture is lacking. I understand it but it is not clear, please respond with a better explanation of the connection.

2. The submission has many typos (lines 336, 347, 151, etc.). This needs to be revised as I don't feel this is presentation-ready yet.

3. Proposition 3.3 relies on relatively old tools and there are much newer theoretical insights that not only work on countable spaces, but on continuous feature vectors, where this work is applied, see [Amir et al.]

4. The way the architecture is implemented in practice is not well explained and I did not understand the difference between the MCGC and MC-GIN variants. 

5. The experiments are not sufficient: The function approximation is nice as a bonus and the real-world experiment is onyl done on one dataset. I would expect to see results on QM9 such as the classical GIN was measured and also compaison against GAT and GCN on experiments in the original papers.

 [Amir et al.] Amir, Tal, et al. "Neural injective functions for multisets, measures and graphs via a finite witness theorem." Advances in Neural Information Processing Systems 36 (2024).‏

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: I would like for the authors to put their contribution in perspective with the current state of the art.
soundness: 2
strengths: The idea is exciting and easy to understand. The authors did a great job in terms of clarity.
summary: The paper proposes a new GCN where each channel's convolution operation is performed independently, similar to Convolutional neural networks. The authors show all the steps required to derive the formulation in the spectral space and its approximation for deriving the message-passing formulation for a GCN and a modified version of GIN. Finally, the authors test their model on two datasets: ZINC and synthetic.
weaknesses: There is no related work section, and finding papers with similar titles and contents that should have been considered is straightforward. For example: 

hang, X.; Wang, J.; Wang, R.; Wang, T.; Wang, Y.; Li, W. Multi-Channel Graph Convolutional Networks for Graphs with Inconsistent Structures and Features. Electronics 2024, 13, 607. https://doi.org/10.3390/electronics13030607

Zhai, Rui, Libo Zhang, Yingqi Wang, Yalin Song, and Junyang Yu. "A multi-channel attention graph convolutional neural network for node classification." The Journal of Supercomputing 79, no. 4 (2023): 3561-3579.

Meng, L., Ye, Z., Yang, Y. et al. DeepMCGCN: Multi-channel Deep Graph Neural Networks. Int J Comput Intell Syst 17, 41 (2024). https://doi.org/10.1007/s44196-024-00432-9

 How the proposed approach differs from or improves upon the multi-channel approaches in these works?

Moreover, the final formulation for an MC-CGN is similar to that performed by Roth et al. 2024: "In this work, we propose to split graphs into multi-relational graphs and operate MPNNs on these." However, the differences are not discussed, nor is this method included in the experimental evaluation. The authors should explicitly compare their approach to Roth et al. 2024, highlighting key similarities and differences and including it in the experimental evaluation.

The experimental evaluation is minimal, with just a synthetic dataset and Zinc, which cannot support the author's claims. The authors should consider the setup proposed in Roth et al. 2024.