# Multihop Neighbor Information Fusion Graph Convolutional Network for Text Classification

Authors: Fangyuan Lei; Xun Liu; Zhengming Li; Qingyun Dai; Senhong Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Graph convolutional network (GCN) is an efficient network for learning graph representations. However, it costs expensive to learn the high-order interaction relationships of the node neighbor. In this paper, we propose a novel graph convolutional model to learn and fuse multihop neighbor information relationships. We adopt the weight-sharing mechanism to design different order graph convolutions for avoiding the potential concerns of overfitting. Moreover, we design a new multihop neighbor information fusion (MIF) operator which mixes different neighbor features from 1-hop tok-hops. We theoretically analyse the computational complexity and the number of trainable parameters of our models. Experiment on text networks shows that the proposed models achieve state-of-the-art performance than the text GCN.


---

## Body

## 1. Introduction

Text classification problem is a fundamental problem in many natural language processing (NLP) applications, such as text mining, spam detection, summarization, and question-answering system [1–5]. Many deep learning approaches such as convolutional neural networks [6], recurrent neural networks (RNN) [7], and long short-term memory (LSTM) [8] are introduced to text classification.Text could be constructed on a typical graph-structured network, and graph networks have natural advantages for processing such data. Scarselli et al. [9] proposed a graph neural network, which was widely used for text classification [10–12] and other NLP tasks [13]. Graph convolutional network (GCN) [10], which is the extension of the CNN on graph data, has shown good performance on text classification than the traditional CNN [14]. Yao et al. [15] proposed a text GCN to apply document nodes and weighted edges to construct the text network graph, and their model outperformed the state-of-the-art text classification methods.When the messages pass through the graph of the text network, the node’s output is affected by not only the directly connected nodes but also thek-hop nodes [16]. To obtain more neighbor node information, GCN models can expand the receptive field by stacking multiple layers. However, GNN models and GCN often suffer from the oversmoothing issue [17, 18]. On the contrary, the representation ability of the shallow network structure is clearly insufficient.To address the above issue, we propose a multihop neighbor information fusion graph convolutional network for text classification based on the GCN. In our model, we propose a novel negative minimum value fusion operator to fuse multihop neighbor information (MIF). To reduce the computational complexity, we share the trainable weight [19] among the multihop neighbor nodes. Our experimental results show that our models achieve state-of-the-art performance in several citation text datasets with lower computational complexity.The contributions of this paper are as follows. First, we propose a novel negative minimum value fusion operator, which fuses the feature information of multihop neighbors. Second, we propose high-efficiency graph convolutional network-based MIF to successfully capturek-hop neighbors for nodes’ classification of the text dataset.The remainder of this paper is organized as follows. In Section2, the related works are reviewed. In Section 3, our methods are proposed. In Section 4, the experimental results are presented. Finally, we draw the concluding remarks in Section 5.


## 2. Related Work

In this section, we will describe the related work about the graph convolutional network text classification, and we also introduce the related work about the multihop neighbor information of graph convolutional networks.


### 2.1. Graph Convolutional Network

Gori et al. [20] first proposed the concept of the graph neural network (GNN), which was based on the recurrent neural network architecture. Micheli [21] developed the GNN by random walk on the graph network [18]. Morris et al. [22] proved that the graph neural network and 1D Weisfeiler-Leman had the same ability to decompose nonisomorphic graphs.Graph convolutional networks (GCNs) were developed from convolutional neural networks [23]. However, it is difficult to apply the GCN for large-scale graphs due to the high computational burden of eigenvalue decomposition [23]. Defferrard et al. [10] proposed a localized filter using Chebyshev polynomial. Kipf and Welling [24] proposed vanilla GCN, which achieves state-of-the-art classification performance on the citation network. Niepert et al. [25] proposed PATCHY-SAN to capture the information from locally connected regions. Hamilton et al. [26] developed a set of aggregate functions by sampling nodes in the neighbor to address the limitation of transductive learning. Monti et al. [27] contributed a unified framework for generalizing convolution to non-Euclidean domains. Velickovic et al. [28] leveraged masked attention to propose a graph attention network (GAT). Ding et al. [29] developed GAT and achieved better classification performance.Recent works have been proposed for capturingk-hop neighbor information of nodes [30–33]. Zhou and Li [33] proposed a new high-order convolution operator to capture k-hop neighbor information and developed adaptive filtering to adjust the weights of the operator. Based on the motif graph attention mechanism, Lee et al. [34] proposed motif convolutional networks to capture k-hop interactive information. Mao et al. [35] proposed a Siamese framework to capture the k-hop information in the brain network. Abu-El-Haija et al. [36–38] proposed several versions of the mix-hop convolution to mix these features of different order graph convolutions using a fully connected layer.


### 2.2. Text Classification

Recently, deep learning models are introduced into text classification, which achieve far better performance than traditional models.With the development of deep learning techniques, increasingly deep learning models are applied for text classification. Kim [39] developed several variants of the CNN model for the text classification. Recurrent neural networks (RNNs) [2, 7] are widely applied for text classification, showing better results than traditional models.With the development of graph network models, many researchers developed more GCN-based classification methods [26, 40–42]. Zhaoa et al. [42] proposed the SDGCN model to capture the interdependencies hidden in the data. Liu et al. [43] developed TensorGCN to aggregate intragraph and intergraph information of the text graph. However, Text GCN [15] has a large number of parameters and high computational complexity. We will propose a novel GCN-based model to solve the issue in the Text GCN [15].


## 2.1. Graph Convolutional Network

Gori et al. [20] first proposed the concept of the graph neural network (GNN), which was based on the recurrent neural network architecture. Micheli [21] developed the GNN by random walk on the graph network [18]. Morris et al. [22] proved that the graph neural network and 1D Weisfeiler-Leman had the same ability to decompose nonisomorphic graphs.Graph convolutional networks (GCNs) were developed from convolutional neural networks [23]. However, it is difficult to apply the GCN for large-scale graphs due to the high computational burden of eigenvalue decomposition [23]. Defferrard et al. [10] proposed a localized filter using Chebyshev polynomial. Kipf and Welling [24] proposed vanilla GCN, which achieves state-of-the-art classification performance on the citation network. Niepert et al. [25] proposed PATCHY-SAN to capture the information from locally connected regions. Hamilton et al. [26] developed a set of aggregate functions by sampling nodes in the neighbor to address the limitation of transductive learning. Monti et al. [27] contributed a unified framework for generalizing convolution to non-Euclidean domains. Velickovic et al. [28] leveraged masked attention to propose a graph attention network (GAT). Ding et al. [29] developed GAT and achieved better classification performance.Recent works have been proposed for capturingk-hop neighbor information of nodes [30–33]. Zhou and Li [33] proposed a new high-order convolution operator to capture k-hop neighbor information and developed adaptive filtering to adjust the weights of the operator. Based on the motif graph attention mechanism, Lee et al. [34] proposed motif convolutional networks to capture k-hop interactive information. Mao et al. [35] proposed a Siamese framework to capture the k-hop information in the brain network. Abu-El-Haija et al. [36–38] proposed several versions of the mix-hop convolution to mix these features of different order graph convolutions using a fully connected layer.


## 2.2. Text Classification

Recently, deep learning models are introduced into text classification, which achieve far better performance than traditional models.With the development of deep learning techniques, increasingly deep learning models are applied for text classification. Kim [39] developed several variants of the CNN model for the text classification. Recurrent neural networks (RNNs) [2, 7] are widely applied for text classification, showing better results than traditional models.With the development of graph network models, many researchers developed more GCN-based classification methods [26, 40–42]. Zhaoa et al. [42] proposed the SDGCN model to capture the interdependencies hidden in the data. Liu et al. [43] developed TensorGCN to aggregate intragraph and intergraph information of the text graph. However, Text GCN [15] has a large number of parameters and high computational complexity. We will propose a novel GCN-based model to solve the issue in the Text GCN [15].


## 3. Method

In this section, we review the definition of related graph notations and analyse the layer-wise propagation model of the GCN in detail. Then, we develop a novel information propagation method to capture and fuse the multihop neighbor information. We propose two novel frameworks to capture the rich information of the text network. Finally, we analyse the computational complexity and parameter quantities of our models.


### 3.1. Notations’ Definition

We assume graph signalX∈Rn×c could be characterized by the node feature matrix of the graph, where n and c represent the number of nodes and feature dimensions, respectively. Let A be the adjacency matrix representing its edge connection. We define the normalized Laplacian matrix L as L=In−D−1/2AD−1/2, where In and D denote the identity matrix and the degree matrix of the graph, respectively.The popular convolutional propagation model [24] is as follows:(1)Hl+1=ReLUD˜−1/2A˜D˜−1/2Hlθl,where A˜ is the adjacency matrix with self-loops, namely, A˜=A+In. The degree matrix D˜ could be written as D˜ii=∑jA˜ij, where Hl denotes the propagation matrix. If l = 0, then H0=X, which means the input signal is connected to the network. The trainable weight matrix θl could be optimized by gradient descent. We repeat the application of the convolutional model to get the vanilla GCN [24] framework.(2)Y=softmaxD˜−1/2A˜D˜−1/2ReLUD˜−1/2A˜D˜−1/2Xθ0θ1,where θ0 and θ1 present different weight matrices. The classification function is softmax. The convolutional operator is essentially a linear combination of its own vertices and one-hop neighbourhood vertices to make the same category of vertex features similar. Stacking two convolutional layers makes the vertices of the same category more closely connected and further eases the classification task. However, when more layers are applied, the vertices of different categories will be mixed and become indistinguishable, which is excessive smoothing [17, 18].


### 3.2. Multihop Neighbor Information Fusion with the Graph Convolutional Operator

Definition 1 (multihop neighbor information fusion (MIF)).
It is assumed that matrixA˜ denotes the regularized adjacency matrix of graph G, where A^=D˜−1/2A˜D˜−1/2. If A∈Rn×n, then A^k∈Rn×n. The power matrix of A^ is A^k,A^k−1,…,A^1,A^0, where A^0 denotes the identity matrix. The multihop neighbor information fusion operator is to fuse the k-hop neighbor information with the element-wise topological information which is preserved. The MIF operator is defined as follows:(3)Zl=−minA^1HlWl,A^2HlWl,…,A^kHlWl,where A^kdenotes the k-hop regularized adjacency matrix and A^kHlWl represents the k-hop neighbor information.Proposition 1.
The multihop neighbor information fusion operator is a topological preserved operator.Proof.
IfAk∈Rn×n, then A0,A1…,Ak∈Rn×n, and the k-hop neighbor information in convolutional layer l has the same dimension, A^1HlWl,A^2HlWl,…,A^kHlWl∈Rn×r1. As defined in formula (3), the MIF operator is the element-wise operation. Therefore, the dimension of Zl is equal to the dimension of A^iHlWl. The MIF operator preserves topological information.
The MIF operator is an information aggregation layer that is used to mixk-order adjacency information. The procedure of the calculation of MIF is as follows:(1)
Calculating the minimum value of these features from different order graph convolutions:(4)P=minA^1HlWl,A^2HlWl,…,A^kHlWl.We give a living example to show that the MIF operator works. It is assumed thatk=3, namely, we obtain the maximum 3-hop neighbor information. We assume P1=A^1HlWh=17−10, P2=A^2HlWl=−2234, and P3=A^3HlWl=42−3−2; then, the result is as follows:(5)P=minP1,P2,P3=minP1i,j,P2i,j,P3i,j=−22−3−2.(2)
The output of the MIF operator is defined as negative for each element ofP, namely, Z=−P=2−232.
Following DIFFPOOL [44], we use the topological preserved operator MIF to improve the performance.


### 3.3. MIF Propagation Model

To address the limitations of the Text GCN, we propose a propagation model of multihop neighbor information fusion graph convolution as follows:(6)Hl+1=ReLUMIFA^1HlWl,A^2HlWl,…,A^kHlWl,where MIF⋅ is defined in formula (4), A^=D˜−1/2A˜D˜−1/2, and A^k denotes that A^ multiplies itself by k times, where A^jHlWl is the j-hop graph convolution, and Wl is the weight parameter matrix. In the MixHop model [36–38], Abu-El-Haija et al. adopted different weights for different A^k. To reduce the computational complexity, we share the weight in the same convolutional layer in the multihop convolutional operator.In formula (6), the convolutional layers combine the multihop neighbor information from 1-hop graph convolution with k-hop graph convolution. The calculation procedure is summarized in Algorithm 1. The MIF has advantages compared to Text GCN. MIF implements feature aggregation on nodes and their k-hop neighbor nodes. Therefore, MIF contains multihop neighbor information, in which it captures more information than Text GCN. In summary, MIF merges multihop neighbor information features while avoiding the extra parameter number. Those nodes in the same category are more closely connected. Furthermore, the MIF operator suppresses excessive weighting features while retaining features with small weight values, which may prevent gradient disappearance and gradient explosion problems.Algorithm 1:MIF operation.
input:A^,Hl,Woutput:Hfori = 1: kTi = A^iHlPi = TiW=A^iHlWendZl=−minP1,P2,…,PkH=ReLUZl


### 3.4. Graph Convolutional Network Based on MIF

In Figure1, we propose a two-layer graph convolutional neural network using the MIF layer. The first layer is the graph convolutional layer with MIF, and the convolutional layer is represented as follows:(7)H=σMIFA^1XW1,A^2XW1,…,A^kXW1,where W1 is the weight parameter matrix between the input layer and hidden layer.Figure 1
The proposed model.The second layer is the traditional graph convolution. We set the nonlinear activation functionσ between the two layers as ReLU and achieve multiple classifications via softmax after the second layer. The network extends the 1-hop graph convolution to k-hop graph convolution to capture multihop neighbor interactive information. The output of our model is expressed as follows:(8)Z=softmaxA^ReLUMIFA^1XW1,A^2XW1,…,A^kXW1W2,where W2 represents the weight parameter matrix between the hidden layer and output layer. The trainable weight parameters W1 and W2 would be updated by gradient descent.In the preliminary network design, we compare how many convolutional layers and hops fit to our model. The two-convolutional-layer network shows better performance than the three and more convolutional layer network. When we implement the multihop neighbor information fusion, we observe thatk=2 is better for most text networks, while k=3 is better for a few networks. In further experiments, when k≥4, the classification results would decrease. Moreover, the larger the k value, the higher the computational cost. Therefore, we only discuss the cases of k=2 and k=3 in our models.Whenk=2, our MIF operator fuses the 1-hop graph convolutional layer and 2-hop graph convolutional layer. The 2-hop MIF graph convolutional layer (MIFGC-2) is as follows:(9)Z=softmaxA^1ReLUMIFA^1XW1,A^2XW1W2.Whenk=3, the 3-hop MIF graph convolutional layer (MIFGC-3) fuses from 1-hop to 3-hop convolutional layer. The NMGC-3 model is as follows:(10)Z=softmaxA^1ReLUMIFA^1XW1,A^2XW1,A^3XW1W2.The cross-entropy loss is utilized as our model loss function:(11)ℒ=−∑l∈xL∑m=1MYlMlnZlM,where xL denotes the nodes set with labels and M represents the number of classes. YlM denotes the real labels of tag nodes, and ZlM denotes the probability value between 0 and 1 predicted by softmax.


### 3.5. Computational Complexity and Parameters

Because the actual running time is sensitive to hardware and implementations, we follow He and Sun [45] to adopt the theoretical time complexity to show the complexity rather than the actual running time. For large-scale graph networks, it is a huge challenge to directly calculate A^k. Therefore, we calculate A^kXW1 with right-to-left multiplication. For example, if k=2, we calculate A^2XW1 as A^A^XW1.A^ is usually a sparse matrix with m nonzero entries. In formulas (7)–(10), our graph convolutional layers adopt the weight-sharing mechanism. Therefore, the calculation procedure is efficient.Since different hop graph convolutions share the same weight in the same layer, the parameter quantities are consistent with the 1-hop graph convolution. It is assumed thatA^∈Rn×n, where n is the number of nodes; X∈Rn×r0, where r0 is the feature dimensions, W1∈Rr0×r1, where r1 represents the number of hidden neurons in the 1st layer, and W2∈Rr1×r2, where r2 represents the hidden neurons in the 2nd layer. Then, output dimension in the 1st layer as the same, namely, A^XW1∈Rn×r1,A^2XW1∈Rn×r1, and A^kXW1∈Rn×r1. Therefore, in the first convolutional layer of our proposed model, the computational complexity is Οk×m×r0×r1, and the trainable parameters are Οr0×r1. The whole computational complexity of our proposed model is Οk×m×r0×r1+m×r1×r2 with Ο∑i=12ri−1×ri trainable parameters. The node feature dimension is far large than the neural number, namely, r0≫r2. Therefore, the computational complexity of our network frameworks approximates Οk×m×r0×r1, and trainable parameters approximate Οr0×r1, respectively. It matches the computational complexity and parameters of vanilla GCN [24]. Similarly, Text GCN [15] takes Ο1×m×r0×r1 computational complexity and Οr0×r1 trainable parameters.


## 3.1. Notations’ Definition

We assume graph signalX∈Rn×c could be characterized by the node feature matrix of the graph, where n and c represent the number of nodes and feature dimensions, respectively. Let A be the adjacency matrix representing its edge connection. We define the normalized Laplacian matrix L as L=In−D−1/2AD−1/2, where In and D denote the identity matrix and the degree matrix of the graph, respectively.The popular convolutional propagation model [24] is as follows:(1)Hl+1=ReLUD˜−1/2A˜D˜−1/2Hlθl,where A˜ is the adjacency matrix with self-loops, namely, A˜=A+In. The degree matrix D˜ could be written as D˜ii=∑jA˜ij, where Hl denotes the propagation matrix. If l = 0, then H0=X, which means the input signal is connected to the network. The trainable weight matrix θl could be optimized by gradient descent. We repeat the application of the convolutional model to get the vanilla GCN [24] framework.(2)Y=softmaxD˜−1/2A˜D˜−1/2ReLUD˜−1/2A˜D˜−1/2Xθ0θ1,where θ0 and θ1 present different weight matrices. The classification function is softmax. The convolutional operator is essentially a linear combination of its own vertices and one-hop neighbourhood vertices to make the same category of vertex features similar. Stacking two convolutional layers makes the vertices of the same category more closely connected and further eases the classification task. However, when more layers are applied, the vertices of different categories will be mixed and become indistinguishable, which is excessive smoothing [17, 18].


## 3.2. Multihop Neighbor Information Fusion with the Graph Convolutional Operator

Definition 1 (multihop neighbor information fusion (MIF)).
It is assumed that matrixA˜ denotes the regularized adjacency matrix of graph G, where A^=D˜−1/2A˜D˜−1/2. If A∈Rn×n, then A^k∈Rn×n. The power matrix of A^ is A^k,A^k−1,…,A^1,A^0, where A^0 denotes the identity matrix. The multihop neighbor information fusion operator is to fuse the k-hop neighbor information with the element-wise topological information which is preserved. The MIF operator is defined as follows:(3)Zl=−minA^1HlWl,A^2HlWl,…,A^kHlWl,where A^kdenotes the k-hop regularized adjacency matrix and A^kHlWl represents the k-hop neighbor information.Proposition 1.
The multihop neighbor information fusion operator is a topological preserved operator.Proof.
IfAk∈Rn×n, then A0,A1…,Ak∈Rn×n, and the k-hop neighbor information in convolutional layer l has the same dimension, A^1HlWl,A^2HlWl,…,A^kHlWl∈Rn×r1. As defined in formula (3), the MIF operator is the element-wise operation. Therefore, the dimension of Zl is equal to the dimension of A^iHlWl. The MIF operator preserves topological information.
The MIF operator is an information aggregation layer that is used to mixk-order adjacency information. The procedure of the calculation of MIF is as follows:(1)
Calculating the minimum value of these features from different order graph convolutions:(4)P=minA^1HlWl,A^2HlWl,…,A^kHlWl.We give a living example to show that the MIF operator works. It is assumed thatk=3, namely, we obtain the maximum 3-hop neighbor information. We assume P1=A^1HlWh=17−10, P2=A^2HlWl=−2234, and P3=A^3HlWl=42−3−2; then, the result is as follows:(5)P=minP1,P2,P3=minP1i,j,P2i,j,P3i,j=−22−3−2.(2)
The output of the MIF operator is defined as negative for each element ofP, namely, Z=−P=2−232.
Following DIFFPOOL [44], we use the topological preserved operator MIF to improve the performance.


## 3.3. MIF Propagation Model

To address the limitations of the Text GCN, we propose a propagation model of multihop neighbor information fusion graph convolution as follows:(6)Hl+1=ReLUMIFA^1HlWl,A^2HlWl,…,A^kHlWl,where MIF⋅ is defined in formula (4), A^=D˜−1/2A˜D˜−1/2, and A^k denotes that A^ multiplies itself by k times, where A^jHlWl is the j-hop graph convolution, and Wl is the weight parameter matrix. In the MixHop model [36–38], Abu-El-Haija et al. adopted different weights for different A^k. To reduce the computational complexity, we share the weight in the same convolutional layer in the multihop convolutional operator.In formula (6), the convolutional layers combine the multihop neighbor information from 1-hop graph convolution with k-hop graph convolution. The calculation procedure is summarized in Algorithm 1. The MIF has advantages compared to Text GCN. MIF implements feature aggregation on nodes and their k-hop neighbor nodes. Therefore, MIF contains multihop neighbor information, in which it captures more information than Text GCN. In summary, MIF merges multihop neighbor information features while avoiding the extra parameter number. Those nodes in the same category are more closely connected. Furthermore, the MIF operator suppresses excessive weighting features while retaining features with small weight values, which may prevent gradient disappearance and gradient explosion problems.Algorithm 1:MIF operation.
input:A^,Hl,Woutput:Hfori = 1: kTi = A^iHlPi = TiW=A^iHlWendZl=−minP1,P2,…,PkH=ReLUZl


## 3.4. Graph Convolutional Network Based on MIF

In Figure1, we propose a two-layer graph convolutional neural network using the MIF layer. The first layer is the graph convolutional layer with MIF, and the convolutional layer is represented as follows:(7)H=σMIFA^1XW1,A^2XW1,…,A^kXW1,where W1 is the weight parameter matrix between the input layer and hidden layer.Figure 1
The proposed model.The second layer is the traditional graph convolution. We set the nonlinear activation functionσ between the two layers as ReLU and achieve multiple classifications via softmax after the second layer. The network extends the 1-hop graph convolution to k-hop graph convolution to capture multihop neighbor interactive information. The output of our model is expressed as follows:(8)Z=softmaxA^ReLUMIFA^1XW1,A^2XW1,…,A^kXW1W2,where W2 represents the weight parameter matrix between the hidden layer and output layer. The trainable weight parameters W1 and W2 would be updated by gradient descent.In the preliminary network design, we compare how many convolutional layers and hops fit to our model. The two-convolutional-layer network shows better performance than the three and more convolutional layer network. When we implement the multihop neighbor information fusion, we observe thatk=2 is better for most text networks, while k=3 is better for a few networks. In further experiments, when k≥4, the classification results would decrease. Moreover, the larger the k value, the higher the computational cost. Therefore, we only discuss the cases of k=2 and k=3 in our models.Whenk=2, our MIF operator fuses the 1-hop graph convolutional layer and 2-hop graph convolutional layer. The 2-hop MIF graph convolutional layer (MIFGC-2) is as follows:(9)Z=softmaxA^1ReLUMIFA^1XW1,A^2XW1W2.Whenk=3, the 3-hop MIF graph convolutional layer (MIFGC-3) fuses from 1-hop to 3-hop convolutional layer. The NMGC-3 model is as follows:(10)Z=softmaxA^1ReLUMIFA^1XW1,A^2XW1,A^3XW1W2.The cross-entropy loss is utilized as our model loss function:(11)ℒ=−∑l∈xL∑m=1MYlMlnZlM,where xL denotes the nodes set with labels and M represents the number of classes. YlM denotes the real labels of tag nodes, and ZlM denotes the probability value between 0 and 1 predicted by softmax.


## 3.5. Computational Complexity and Parameters

Because the actual running time is sensitive to hardware and implementations, we follow He and Sun [45] to adopt the theoretical time complexity to show the complexity rather than the actual running time. For large-scale graph networks, it is a huge challenge to directly calculate A^k. Therefore, we calculate A^kXW1 with right-to-left multiplication. For example, if k=2, we calculate A^2XW1 as A^A^XW1.A^ is usually a sparse matrix with m nonzero entries. In formulas (7)–(10), our graph convolutional layers adopt the weight-sharing mechanism. Therefore, the calculation procedure is efficient.Since different hop graph convolutions share the same weight in the same layer, the parameter quantities are consistent with the 1-hop graph convolution. It is assumed thatA^∈Rn×n, where n is the number of nodes; X∈Rn×r0, where r0 is the feature dimensions, W1∈Rr0×r1, where r1 represents the number of hidden neurons in the 1st layer, and W2∈Rr1×r2, where r2 represents the hidden neurons in the 2nd layer. Then, output dimension in the 1st layer as the same, namely, A^XW1∈Rn×r1,A^2XW1∈Rn×r1, and A^kXW1∈Rn×r1. Therefore, in the first convolutional layer of our proposed model, the computational complexity is Οk×m×r0×r1, and the trainable parameters are Οr0×r1. The whole computational complexity of our proposed model is Οk×m×r0×r1+m×r1×r2 with Ο∑i=12ri−1×ri trainable parameters. The node feature dimension is far large than the neural number, namely, r0≫r2. Therefore, the computational complexity of our network frameworks approximates Οk×m×r0×r1, and trainable parameters approximate Οr0×r1, respectively. It matches the computational complexity and parameters of vanilla GCN [24]. Similarly, Text GCN [15] takes Ο1×m×r0×r1 computational complexity and Οr0×r1 trainable parameters.


## 4. Experiment

We will evaluate our NMGC-2 and NMGC-3 on text networks and compare our methods with the classic method and deep learning methods, such as the embedding model, CNN-based, LSTM-based, and GCN-based. We analyse the terms of computational complexity and trainable parameters in detail. We investigate the impact of network framework parameters and training epochs on classification accuracy.


### 4.1. Datasets

We test our methods on five benchmark corpora datasets including R52 and R8 of Reuters-21578, 20-Newsgroups (20NG), Ohsumed, and Movie Review (MR). According to the preprocessing steps by Yao et al. [15], we process the text datasets and use the documents and words as nodes to build the text graph. In Table 1, the statistics characters of the datasets are described in detail.Table 1
Dataset statistics.
Dataset#training#test#docs#classes#words#nodes#lengthR5265322568910052889217,99269.82R85485218976748768815,36265.7220NG11,314753218,8462042,75761,603221.26Ohsumed3357404374002314,15721,557135.82MR7108355410,662218,76429,42620.39


### 4.2. Baseline and Experimental Settings

We compare with the following baseline methods as in Yao et al. [15], i.e., CNN with randomly initialized word vectors (CNN-rand) [39], CNN with pretrained word vectors (CNN-pretrain) [39], predictive text embedding (PTE) [46], LSTM framework (LSTM) [2], LSTM framework with pretrained word embeddings (LSTM-pretrain) [2], fast text classifier (fastText) [47], fast text classifier with bigrams (fastText-bigrams) [47], label embedding model with attention (LEAM) [48], simple word-embedding model (SWEM) [49], graph CNN with spline filter (GCNN-S) [23], graph CNN with Fourier filter (GCNN-F) [50], and graph CNN with Chebyshev filter (GCNN-C) [10].We tune a series of hyperparameters’ (learning rate, dropout rate, hidden units, and epochs) values to determine the best hyperparameters of our model on text networks. The hyperparameters are reported in Tables2 and 3. In our NMGC-2 and NMGC-3 models, we set L2 regularization factor as 0 and use Adam [51] to optimize the learning rate, following Yao et al. [15].Table 2
The hyperparameters in NMGC-2.
DatasetLearning rateDropout rateHidden unitsEpochsR520.0050.4128800R80.010.46420020NG0.0050.5128330Ohsumed0.0050.4128410MR0.010.46440Table 3
The hyperparameters in NMGC-3.
DatasetLearning rateDropout rateHidden unitsEpochsR520.0050.51281300R80.0150.412818020NG0.010.5128265Ohsumed0.010.6128210MR0.010.43285


### 4.3. Results’ Analysis

We compare our NMGC-2 and NMGC-3 with other baseline methods in terms of test accuracy. As shown in Table4, the proposed model NMGC-2 or NMGC-3 achieves the highest classification performance on datasets R52, R8, 20NG, and Ohsumed. Specifically, our NMGC-2 obtains the best accuracy of 94.35%, 97.31%, and 69.21% on datasets R52, R8, and Ohsumed, respectively, whereas our NMGC-3 obtains the highest accuracy of 86.68%on 20NG.Table 4
Test accuracy on five text datasets. The benchmark results were reported by Yao et al. [15]. The accuracy values are the average result of 10 runs.
MethodR52R820NGOhsumedMRCNN-rand [39]85.3794.0276.9343.8774.98CNN-pretrain [39]87.5995.7182.1558.4477.75PTE [46]90.7196.6976.7453.5870.23LSTM [2]85.5493.6865.7141.1375.06LSTM-pretrain [2]90.4896.0975.4351.1077.33fastText [47]92.8196.1379.3857.7075.14fastText-bigrams [47]90.9994.7479.6755.6976.24LEAM [48]91.8493.3181.9158.5876.95SWEM [49]92.9495.3285.1663.1276.65GCNN-S [23]92.7496.80—62.8276.99GCNN-F [50]93.2096.89—63.0476.74GCNN-C [10]92.7596.9981.4263.8677.22Text GCN [15]93.56 ± 0.1897.07 ± 0.1086.34 ± 0.0968.36 ± 0.5676.74 ± 0.20NMGC-2 (ours)94.35 ± 0.0697.31 ± 0.0986.61 ± 0.0669.21 ± 0.1776.21 ± 0.25NMGC-3 (ours)93.83 ± 0.1697.16 ± 0.1086.68 ± 0.1868.20 ± 0.3576.36 ± 0.40The success of NMGC-2 and NMGC-3 is mainly due to the following three aspects. (1) Our NMGC-2 and NMGC-3 models have the capability to capture the relations in terms of word-word and document-word in the datasets. (2) Our NMGC-2 and NMGC-3 make full use of the advantages of the GCN. We implement the feature information aggregation on the node and its 1-hop neighbor information (each layer) so that the node (word-word and document-word) features in the same cluster are similar, which are easy to classify. (3) Our NMGC-2 and NMGC-3 capture more and richer feature information from 1-hop tok-hop neighbors, which may circumvent the limitations of the GCN.On dataset MR, CNN-pretrain [39] achieves the highest classification result of 77.75%, which shows the model consecutive and short-distance semantics because CNN-pretrain [39] and LSTM-pretrain [2] model consecutive word sequences, while our NMGC-2 and NMGC-3 ignore the word orders. Another reason is that our NMGC-2 and NMGC-3 models are difficult to propagate the information among the nodes (word-word and document-word) on MR with few edges.Compared to Text GCN [15], our NMGC-2 and NMGC-3 are better by a large margin in most cases, which demonstrates the effectiveness of our method in terms of capturing high-order interactive information.


### 4.4. Hidden Units’ Analyses of Our Method

To evaluate the relationship between hidden units and the model performance, we use different hidden units to conduct experiments. We choose a representative set of hidden units as our comparative experiments in balancing computational complexity and classification performance. The results are summarized in Table5. Specifically, our NMGC-2 uses the best hidden units of 128, 64, 128, 128, and 64 to achieve the higher accuracy on R52, R8, 20NG, Ohsumed, and MR, respectively, whereas our NMGC-3 uses the best hidden units of 128, 128, 128, 128, and 32 to achieve the better accuracy on R52, R8, 20NG, Ohsumed, and MR, respectively. We note that our NMGC-2 is always better than our NMGC-3 in many cases for different hidden units. This is most likely that our NMGC-3 suffers from oversmoothing in most cases. However, NMGC-3 outperforms NMGC-2 on short MR with few edges because NMGC-3 considers higher-order node information and propagates more label information to the entire graph network. In most cases, when the number of hidden units decreases, the accuracy of our method decreases, and more epochs are required to train our network.Table 5
Comparison of hidden units.
DatasetModelHidden unitsEpochsTest Acc.R52NMGC-2 (ours)12880094.35 ± 0.0664120094.23 ± 0.2032200094.16 ± 0.14NMGC-3 (ours)128130093.83 ± 0.1664110093.29 ± 0.2632200092.85 ± 0.37R8NMGC-2 (ours)12815097.25 ± 0.136420097.31 ± 0.093233097.30 ± 0.13NMGC-3 (ours)12818097.16 ± 0.106422096.92 ± 0.083230096.69 ± 0.0620NGNMGC-2 (ours)12833086.61 ± 0.066448086.55 ± 0.123260086.02 ± 0.12NMGC-3 (ours)12826586.68 ± 0.186442086.14 ± 0.193254085.64 ± 0.13OhsumedNMGC-2 (ours)12841069.21 ± 0.176449569.07 ± 0.283279568.46 ± 0.24NMGC-3 (ours)12821068.20 ± 0.356430567.50 ± 0.243241566.25 ± 0.35MRNMGC-2 (ours)1283576.19 ± 0.43644076.21 ± 0.25325576.16 ± 0.26NMGC-3 (ours)1285076.27 ± 0.32647076.24 ± 0.11328576.36 ± 0.40


### 4.5. Computational Complexity and Trainable Weight Parameters

We design the weight-sharing mechanism to share the weight in the proposed convolutional layer, which reduces the number of parameters. When using weight sharing, our calculations are very efficient. This naturally reduces the computational complexity. We design the weight-sharing mechanism to avoid overfitting caused by many parameters.As shown in Table6, we compare our method with Text GCN [15] in terms of computational complexity and the number of trainable weight parameters. The detailed derivation process of Comp. and Params. is analysed in Section 3.5. In Table 6, we observe that our NMGC-2 and NMGC-3 could match the computational complexity of Text GCN [15]. In particular, for MR, NMGC-3 is about 1 time less than Text GCN [15] in terms of computational complexity. Interestingly, our models have the least parameters on all datasets because we use the weight-sharing mechanism on these convolutions from 1-hop graph convolution to k-hop graph convolution and a smaller number of hidden units.Table 6
Comparison of computational complexity and the number of trainable weight parameters. Comp. and Params. denote the computational complexity and parameters, respectively. Constant numbers 1, 2, and 3 represent the hops of the graph convolutional network, and constant numbers 200, 64, 128, and 32 denote the number of hidden units.
MethodComp.Params.Text GCN [15]O1×m×r0×200O(r0×200)NMGC-2 (ours)O(2×m×r0×64) (R8 and MR datasets) O(2×m×r0×128) (other datasets)O(r0×64) (R8 and MR datasets) O(r0×128) (other datasets)NMGC-3 (ours)O(3×m×r0×32) (MR dataset) O(3×m×r0×128) (other datasets)O(r0×32) (MR dataset) O(r0×128) (other datasets)


## 4.1. Datasets

We test our methods on five benchmark corpora datasets including R52 and R8 of Reuters-21578, 20-Newsgroups (20NG), Ohsumed, and Movie Review (MR). According to the preprocessing steps by Yao et al. [15], we process the text datasets and use the documents and words as nodes to build the text graph. In Table 1, the statistics characters of the datasets are described in detail.Table 1
Dataset statistics.
Dataset#training#test#docs#classes#words#nodes#lengthR5265322568910052889217,99269.82R85485218976748768815,36265.7220NG11,314753218,8462042,75761,603221.26Ohsumed3357404374002314,15721,557135.82MR7108355410,662218,76429,42620.39


## 4.2. Baseline and Experimental Settings

We compare with the following baseline methods as in Yao et al. [15], i.e., CNN with randomly initialized word vectors (CNN-rand) [39], CNN with pretrained word vectors (CNN-pretrain) [39], predictive text embedding (PTE) [46], LSTM framework (LSTM) [2], LSTM framework with pretrained word embeddings (LSTM-pretrain) [2], fast text classifier (fastText) [47], fast text classifier with bigrams (fastText-bigrams) [47], label embedding model with attention (LEAM) [48], simple word-embedding model (SWEM) [49], graph CNN with spline filter (GCNN-S) [23], graph CNN with Fourier filter (GCNN-F) [50], and graph CNN with Chebyshev filter (GCNN-C) [10].We tune a series of hyperparameters’ (learning rate, dropout rate, hidden units, and epochs) values to determine the best hyperparameters of our model on text networks. The hyperparameters are reported in Tables2 and 3. In our NMGC-2 and NMGC-3 models, we set L2 regularization factor as 0 and use Adam [51] to optimize the learning rate, following Yao et al. [15].Table 2
The hyperparameters in NMGC-2.
DatasetLearning rateDropout rateHidden unitsEpochsR520.0050.4128800R80.010.46420020NG0.0050.5128330Ohsumed0.0050.4128410MR0.010.46440Table 3
The hyperparameters in NMGC-3.
DatasetLearning rateDropout rateHidden unitsEpochsR520.0050.51281300R80.0150.412818020NG0.010.5128265Ohsumed0.010.6128210MR0.010.43285


## 4.3. Results’ Analysis

We compare our NMGC-2 and NMGC-3 with other baseline methods in terms of test accuracy. As shown in Table4, the proposed model NMGC-2 or NMGC-3 achieves the highest classification performance on datasets R52, R8, 20NG, and Ohsumed. Specifically, our NMGC-2 obtains the best accuracy of 94.35%, 97.31%, and 69.21% on datasets R52, R8, and Ohsumed, respectively, whereas our NMGC-3 obtains the highest accuracy of 86.68%on 20NG.Table 4
Test accuracy on five text datasets. The benchmark results were reported by Yao et al. [15]. The accuracy values are the average result of 10 runs.
MethodR52R820NGOhsumedMRCNN-rand [39]85.3794.0276.9343.8774.98CNN-pretrain [39]87.5995.7182.1558.4477.75PTE [46]90.7196.6976.7453.5870.23LSTM [2]85.5493.6865.7141.1375.06LSTM-pretrain [2]90.4896.0975.4351.1077.33fastText [47]92.8196.1379.3857.7075.14fastText-bigrams [47]90.9994.7479.6755.6976.24LEAM [48]91.8493.3181.9158.5876.95SWEM [49]92.9495.3285.1663.1276.65GCNN-S [23]92.7496.80—62.8276.99GCNN-F [50]93.2096.89—63.0476.74GCNN-C [10]92.7596.9981.4263.8677.22Text GCN [15]93.56 ± 0.1897.07 ± 0.1086.34 ± 0.0968.36 ± 0.5676.74 ± 0.20NMGC-2 (ours)94.35 ± 0.0697.31 ± 0.0986.61 ± 0.0669.21 ± 0.1776.21 ± 0.25NMGC-3 (ours)93.83 ± 0.1697.16 ± 0.1086.68 ± 0.1868.20 ± 0.3576.36 ± 0.40The success of NMGC-2 and NMGC-3 is mainly due to the following three aspects. (1) Our NMGC-2 and NMGC-3 models have the capability to capture the relations in terms of word-word and document-word in the datasets. (2) Our NMGC-2 and NMGC-3 make full use of the advantages of the GCN. We implement the feature information aggregation on the node and its 1-hop neighbor information (each layer) so that the node (word-word and document-word) features in the same cluster are similar, which are easy to classify. (3) Our NMGC-2 and NMGC-3 capture more and richer feature information from 1-hop tok-hop neighbors, which may circumvent the limitations of the GCN.On dataset MR, CNN-pretrain [39] achieves the highest classification result of 77.75%, which shows the model consecutive and short-distance semantics because CNN-pretrain [39] and LSTM-pretrain [2] model consecutive word sequences, while our NMGC-2 and NMGC-3 ignore the word orders. Another reason is that our NMGC-2 and NMGC-3 models are difficult to propagate the information among the nodes (word-word and document-word) on MR with few edges.Compared to Text GCN [15], our NMGC-2 and NMGC-3 are better by a large margin in most cases, which demonstrates the effectiveness of our method in terms of capturing high-order interactive information.


## 4.4. Hidden Units’ Analyses of Our Method

To evaluate the relationship between hidden units and the model performance, we use different hidden units to conduct experiments. We choose a representative set of hidden units as our comparative experiments in balancing computational complexity and classification performance. The results are summarized in Table5. Specifically, our NMGC-2 uses the best hidden units of 128, 64, 128, 128, and 64 to achieve the higher accuracy on R52, R8, 20NG, Ohsumed, and MR, respectively, whereas our NMGC-3 uses the best hidden units of 128, 128, 128, 128, and 32 to achieve the better accuracy on R52, R8, 20NG, Ohsumed, and MR, respectively. We note that our NMGC-2 is always better than our NMGC-3 in many cases for different hidden units. This is most likely that our NMGC-3 suffers from oversmoothing in most cases. However, NMGC-3 outperforms NMGC-2 on short MR with few edges because NMGC-3 considers higher-order node information and propagates more label information to the entire graph network. In most cases, when the number of hidden units decreases, the accuracy of our method decreases, and more epochs are required to train our network.Table 5
Comparison of hidden units.
DatasetModelHidden unitsEpochsTest Acc.R52NMGC-2 (ours)12880094.35 ± 0.0664120094.23 ± 0.2032200094.16 ± 0.14NMGC-3 (ours)128130093.83 ± 0.1664110093.29 ± 0.2632200092.85 ± 0.37R8NMGC-2 (ours)12815097.25 ± 0.136420097.31 ± 0.093233097.30 ± 0.13NMGC-3 (ours)12818097.16 ± 0.106422096.92 ± 0.083230096.69 ± 0.0620NGNMGC-2 (ours)12833086.61 ± 0.066448086.55 ± 0.123260086.02 ± 0.12NMGC-3 (ours)12826586.68 ± 0.186442086.14 ± 0.193254085.64 ± 0.13OhsumedNMGC-2 (ours)12841069.21 ± 0.176449569.07 ± 0.283279568.46 ± 0.24NMGC-3 (ours)12821068.20 ± 0.356430567.50 ± 0.243241566.25 ± 0.35MRNMGC-2 (ours)1283576.19 ± 0.43644076.21 ± 0.25325576.16 ± 0.26NMGC-3 (ours)1285076.27 ± 0.32647076.24 ± 0.11328576.36 ± 0.40


## 4.5. Computational Complexity and Trainable Weight Parameters

We design the weight-sharing mechanism to share the weight in the proposed convolutional layer, which reduces the number of parameters. When using weight sharing, our calculations are very efficient. This naturally reduces the computational complexity. We design the weight-sharing mechanism to avoid overfitting caused by many parameters.As shown in Table6, we compare our method with Text GCN [15] in terms of computational complexity and the number of trainable weight parameters. The detailed derivation process of Comp. and Params. is analysed in Section 3.5. In Table 6, we observe that our NMGC-2 and NMGC-3 could match the computational complexity of Text GCN [15]. In particular, for MR, NMGC-3 is about 1 time less than Text GCN [15] in terms of computational complexity. Interestingly, our models have the least parameters on all datasets because we use the weight-sharing mechanism on these convolutions from 1-hop graph convolution to k-hop graph convolution and a smaller number of hidden units.Table 6
Comparison of computational complexity and the number of trainable weight parameters. Comp. and Params. denote the computational complexity and parameters, respectively. Constant numbers 1, 2, and 3 represent the hops of the graph convolutional network, and constant numbers 200, 64, 128, and 32 denote the number of hidden units.
MethodComp.Params.Text GCN [15]O1×m×r0×200O(r0×200)NMGC-2 (ours)O(2×m×r0×64) (R8 and MR datasets) O(2×m×r0×128) (other datasets)O(r0×64) (R8 and MR datasets) O(r0×128) (other datasets)NMGC-3 (ours)O(3×m×r0×32) (MR dataset) O(3×m×r0×128) (other datasets)O(r0×32) (MR dataset) O(r0×128) (other datasets)


## 5. Conclusion

In this work, we propose a new multihop neighbor information fusion graph convolutional network on graph-structured data. We develop a novel MIF operator to combine the graph convolution features of multihop neighbor information from 1-hop graph convolution tok-hops. Experiments on text networks suggest that our models are capable of encoding in terms of node features and global graph topology in a way useful for graph classification. In this setting, our models achieve performance improvement compared to other methods while being computationally efficient and with less trainable parameters. In future work, we plan to study different fusion schemes and extend our model to more datasets.



---

*Source: 6665588-2021-05-03.xml*