# Graph Routing between Capsules

Yang Li<EMAIL_ADDRESS>Wei Zhao<EMAIL_ADDRESS>Erik
Cambria  Suhang Wang<EMAIL_ADDRESS>Steffen Eger<EMAIL_ADDRESS><EMAIL_ADDRESS>Northwestern Polytechnical University, China  Nanyang
Technological University, Singapore  Technical University of Darmstadt,
Germany  Pennsylvania State University, USA

###### Abstract

Routing methods in capsule networks often learn a hierarchical relationship
for capsules in successive layers, but the intra-relation between capsules in
the same layer is less studied, while this intra-relation is a key factor for
the semantic understanding in text data. Therefore, in this paper, we
introduce a new capsule network with graph routing to learn both
relationships, where capsules in each layer are treated as the nodes of a
graph. We investigate strategies to yield adjacency and degree matrix with
three different distances from a layer of capsules, and propose the graph
routing mechanism between those capsules. We validate our approach on five
text classification datasets, and our findings suggest that the approach
combining bottom-up routing and top-down attention performs the best. Such an
approach demonstrates generalization capability across datasets. Compared to
the state-of-the-art routing methods, the improvements in accuracy in the five
datasets we used were 0.82, 0.39, 0.07, 1.01, and 0.02, respectively.

##  1 Introduction

Since capsule networks were proposed, they have been successfully applied in
image processing [13, 22]. In recent years, a lot of works have appeared that
also adopted capsule networks for text classification. For example, Zhao et
al. [30] investigate the effectiveness of capsule networks in small data
settings, while Ren et al. [20] introduce a variant of capsule networks with
deep compositional code learning in text classification. The success of
capsule networks mainly relies on a bottom-up mechanism, namely routing by
agreement [21, 22], which routes low-level capsules to high-level capsules in
order to learn hierarchical relationships between layers. This mechanism helps
capsule networks capture spatial features well.

However, there are problems in applying capsule networks to text data.
Generally, these routing algorithms do not account for the intra-relationships
between capsules in each layer, while these intra-relationships exist in text
data usually. For example, in the sentence “The battery has a long life” with
a positive sentiment, there is a part-whole relationship between the words
“battery” and “life”, a modification relationship between the words “long” and
“life” and etc. These intra-relationships, often ignored by previous routing
methods, help understanding the positive sentiment. It is imperative to
leverage implicit knowledge in the words’ semantic context to learn
hierarchical and intra-relationships spontaneously across layers [3, 7, 1].

In this paper, we study the novel problem of simultaneously exploring these
two relationships (intra-relationship and hierarchical relationship)
interactively in the routing context. In essence, we need to solve several
challenges: i) how to evaluate the relationship between capsules in the same
layer; ii) how to further improve the quality of the learned features in text
classification; and iii) how to evaluate the quality of the relationships that
learn from the capsules. Graph convolutional networks (GCN) [15] have
demonstrated good effects in the graph feature learning [25, 19]. And we
believe this method also takes effect in the capsules feature gathering. In an
attempt to solve these challenges, we treat the capsule as a node in a graph
and propose a new graph routing mechanism that learns the intra-relationships
with GCN. In general, our proposed graph routing learns the intra-relationship
by aggregating information from other capsules in the same layers, and learns
the hierarchical relationship with routing by agreement across different
layers. Thus, the differences between proposed graph routing and existing
routing are:

  * 1.

Our graph routing method pays attention to the intra-relationship learning
with graph neural network, while existing routing methods do not;

  * 2.

Our graph routing method applies the attention mechanism in the feature
strength, and existing routing methods do not;

In this paper, the relationship between different capsules is evaluated by the
Wasserstein distance (WD) effectively, and a new normalization trick is
proposed to approximate the adjacency matrix well. Also, implicit information
in text data is identified easily with information aggregation and routing
agreement. Compared with state-of-the-art models, the performance in three of
the five datasets improved by more than 0.3 points in accuracy. Therefore, the
challenges mentioned before are solved well with the proposed graph routing,
and the main contributions of this paper are:

  * 1.

We investigate, for the first time, intra-relationships between capsules by
leveraging words’ semantic context where we treat capsules in each layer as
nodes in a graph.

  * 2.

We introduce a new routing algorithm combining bottom-up routing and top-down
attention and learn hierarchical and intra-relationships spontaneously.

  * 3.

Extensive experiments show that our proposed routing algorithm performs better
than existing routing methods.

##  2 Preliminary

When capsule networks were proposed [13], they were mainly applied in image
processing. Multiple capsules were required to be consistent in one detection.
However, the intra-relationship between capsules cannot be ignored when
processing text data. To our best knowledge, there are no works about intra-
relationship learning in the routing. Before introducing our graph routing, we
will make a preliminary introduction about the classic routing. The symbols
that this paper uses are listed in Table 1.

$\mathbf{x}$ |  The representation of a document | $I_{N}$ |  The identity matrix
---|---|---|---
$\mathbf{u_{i}}$ |  The first layer capsule vector in the routing | $\mathbf{s_{j}}$ |  The second layer capsule vector in the routing
$\mathbf{v_{j}}$ |  The output from the routing | $c_{ij}$ |  The weight variable
$W^{D}$ |  The affine transformation matrix | $e_{ij}$ |  The coupling coefficient
$W_{i}$ |  The parameters of the neural networks | $A,\tilde{A}$ |  The adjacency matrix
$D$ |  The degree matrix in the graph | $f_{att}(\cdot)$ |  The feed-forward function
$d^{w},d^{e},d^{c}$ |  The Wasserstein distance, euclidean distance and cosine distance | $g^{a}_{i}$ |  The output from N-gram convolutional layer
$h_{j}$ |  The output from GCN | $m_{j}$ |  The output from $f_{att}$
$W^{a},W^{b}$ |  The filter in the convolutional layer | $p_{i}$ |  The output from primary capsule layer
$K$ |  The size of N-gram | $s$ |  The stride size
$b_{1},b_{2}$ |  The bias term | $B_{1},B_{2}$ |  The number of the filter
$L$ |  The document length | $d$ |  The capsule dimension
$E$ |  The capsule number after the routing | $f_{1}(\cdot)$ |  The activate function (i.e. ReLU)
$C$ |  The class number | $f_{2}(\cdot)$ |  The squash function
$\alpha_{j}$ |  The attention value |  |
Table 1: The list of symbols involved in this paper.

Since dynamic routing was proposed by [22], it has been treated as the
standard routing method. Let the capsule vector in the first layer be
$\mathbf{u}_{i}$. Before routing, a transformation procedure is applied to
encode spatial relationships between local features and global features:

$\hat{u}_{j|i}=W^{D}\mathbf{u}_{i}$

where $W^{D}$ is an affine transformation matrix. Generally, routing decides
how to send the capsule vector $\mathbf{u}_{i}$ to the second layer. This is
controlled by a weight variable $c_{ij}$, which is multiplied with the
corresponding value $\hat{u}_{j|i}$:

$\mathbf{s}_{j}=\sum_{i=1}^{n}c_{ij}\hat{u}_{j|i}$

The squash function is then applied to ensure that the norm of
$\mathbf{s}_{j}$ is bounded by 1, while the direction of $\mathbf{s}_{j}$
should not be changed. The squash function has the form

$\mathbf{v}_{j}=\frac{||\mathbf{s}_{j}||^{2}}{1+||\mathbf{s}_{j}||^{2}}\frac{\mathbf{s}_{j}}{||\mathbf{s}_{j}||}$

Generally, $c_{ij}$ is a non-negative scalar, and the sum of all weights
$c_{ij}$ in the first layer is $1$. It is obtained from the softmax function:

$c_{ij}=\frac{\exp(e_{ij})}{\sum_{k}\exp(e_{ik})}$

Different from attention models, routing is a bottom up method in feature
gathering, and this is illustrated in following equation which is the across
layer operation with $i$ being the capsules from the first layer and $j$ being
the capsules from the second layer:

$e_{ij}=e_{ij}+\hat{u}_{j|i}\mathbf{v}_{j}$

$e_{ij}$ is the coupling coefficient, and the general routing method is using
the clustering method to find the probability in mapping different capsules to
related capsules across layers. However, as opposed to related works, we
investigate relationships between capsules in the same layer.

##  3 Model Architecture

To make a fair comparison with other routing mechanisms, we are using the same
architecture proposed by Zhao et al. [30]. The model architecture components
are four layers which are the $N$-gram convolutional layer (NCL), the primary
capsule layer (PCL), the routing layer (RL), and the representation layer. The
architecture is basically the same as Capsule-A in [30], which is depicted in
Figure 1.

Figure 1: The architecture of the model.

###  3.1 N-gram Convolutional Layer (NCL)

After getting the input from the word embedding, each document is represented
by $\mathbf{x}\in R^{L\times D}$, where $L$ denotes the document length
(padded where necessary), $D$ is the word embedding length. Then the input
will be fed into the NCL to detect features at different positions. The
process is depicted in equation 1,

$g_{i}^{a}=f_{1}(W^{a}\cdot\mathbf{x}_{i:i+K-s}+b_{1})$ (1)

where $K$ denotes the $N$-gram size, $s$ is the stride width, $W^{a}\in
R^{K\times D}$ is the filter during the feature detection with convolutional
operation, $b_{1}\in R$ is a bias term, and $f_{1}$ denotes the activation
function (i.e., ReLU) in that layer. After the filtering with a certain filter
$W^{a}$ over the $\mathbf{x}_{i:i+K-s}$, we get a feature value $g_{i}^{a}\in
R$. All of those features form the feature map
$\mathbf{g}^{a}=[g_{1},g_{2},...,g_{L-K+s}]$ with $\mathbf{g}^{a}\in
R^{L-K+s}$ from the NCL. The number of the filter is set to $B_{1}$. Hence,
the output of the NCL is $\mathbf{g}$ which is rearranged as

$\mathbf{g}=[\mathbf{g}_{1},\mathbf{g}_{2},...,\mathbf{g}_{B_{1}}]\in
R^{(L-K+s)\times B_{1}}$

###  3.2 Primary Capsule Layer (PCL)

Then $\mathbf{g}$ is fed into the PCL which is composed of the convolutional
operation. In this layer, each row in $\mathbf{g}$ convolves with a filter
$W^{b}\in R^{B_{1}\times d}$, where $d$ denotes the capsule dimension. This is
depicted in equation 2.

$p_{i}=f_{2}(W^{b}\cdot\mathbf{g}_{i}+b_{2})$ (2)

where $f_{2}$ is the squash function for the output vector, $b_{2}$ is a
capsule bias term. As in the NCL, there are $B_{2}$ filters in total.
Therefore, the generated features are rearranged as

$\mathbf{p}=[\mathbf{p}_{1},\mathbf{p}_{2},...,\mathbf{p}_{B_{2}}]\in
R^{(L-K+s)\times B_{2}\times d}$

Extensive computational resources are required when there is a large document
as input. Hence, the capsule compression is conducted to condense the capsule
number to a smaller one. The condensed capsule $u_{i}$ is computed as:

$u_{i}=\sum_{j}w_{j}\mathbf{p}_{j}\in R^{d}$ (3)

where $w_{j}$ is the parameter needed to be learned.

In the next step, the transformation matrix $W_{ij}$ is utilized to generate
the prediction vector $\hat{u}_{j|i}\in R^{d}$ (the parent capsule $j$) from
its child capsule $u_{i}$, where $N$ is the number of parent capsules in the
last step which is $(L-K+s)$. This vector can be computed as follows:

$\hat{u}_{j|i}=W_{ij}u_{i}+b_{j|i}\in R^{d}$ (4)

where $b_{j|i}$ denotes the capsule bias term. This step helps learn child-
parent relationships for the capsule networks as argued in [22]. Therefore,
the feature map generated from the primary capsule layer is $\mathbf{u}\in
R^{E\times N\times d}$, where $E$ is the capsule number after the matrix
transformation.

Then the graph routing algorithm is utilized to get voting results, which can
be depicted as:

$v=\text{Graph-Routing}(\hat{u})$ (5)

where $\hat{u}$ is the composition of all of the child capsules, and $v\in
R^{C\times d}$ denotes all of the parent-capsules, where $C$ denotes the class
number. Details are referred to Section 4.

###  3.3 Representation Layer

Representation layer is the last layer which gets the input $v$ from the graph
routing. The final capsule number $C$ is the same as the class number of the
document. The vector normalization is utilized to get the class probability
$\hat{p}=\left\|v\right\|\in R^{C}$ .

##  4 Graph Routing

To make the routing simple and effective, each capsule is treated as a node in
a graph. Meanings of sentences are expressed by the composition of different
phrases, and each capsule only captures a certain phrase during the feature
selection. To obtain a comprehensive understanding of a sentence, the
relationship between different capsules must be learned. Actually, there
should be connections between nodes as it will be helpful for reaching an
agreement during the routing. Inspired by GCN [15], which elaborates the
relationships among the nodes in a graph, we learn intra-correlation with the
graph convolutional operation. The structure of graph routing is shown in
Figure 2.

Figure 2: The structure of the graph routing.

The GCN procedure is shown in the red box in Figure 2, based on an undirected
complete graph that is composed by the capsules in the lower layer. There are
usually more than three iterations in a routing. Therefore, in order to make
the structure efficient and simple, a single GCN layer is used in each
iteration to gather intra-relationship within the nodes. If the number of
iterations is set to 3, we will have a routing network with three layers of
GCN. The weight $a_{ij}$ in the edge is the intra-relationship between the two
connected capsules $i$ and $j$. Generally, if two connected capsules are
semantically close, there will be a large value for the weight $a_{ij}$. And
if there is no semantic connection between these two capsules, there will be a
small value for weight $a_{ij}$. The way to get the intra-relationship between
two capsules will be discussed in the following subsection. In general, these
three distance measurements are used first, coupled with normalization trick
in subsection 4.2, when evaluating the relationship between capsules. The
attention mechanism in subsection 4.3 involved is the same as that in [2].

###  4.1 Relationship Between Capsules

In the common GCN [15], the relationship between two nodes is expressed by the
non-negative value in the adjacency matrix $A$. However, it is the prior known
information for $A$ which is predefined by the existing data. The
convolutional operation is conducted in the Fourier domain to get the hidden
feature, which is expressed in equation 6 [12].

$W_{i}\star u_{i}\approx W_{i}\tilde{A}u_{i}$ (6)

where $W_{i}$ is the parameter of the network, and $\tilde{A}$ is from
equation 7

$\tilde{A}=I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ (7)

where $A\in R^{N\times N}$ is the adjacency matrix, $N$ is the capsule number,
and $D$ is the degree matrix, with $D_{ii}=\sum_{j}A_{ij}$.

After filtering by the convolutional kernel, $u_{i}$ will aggregate more
relevant information for the classification. From equation 6, we can see that
if one capsule is related to another capsule in layer $l$, the corresponding
value in the adjacency matrix will be big. The relationship matrix is one of
the adjacency matrices, with the correlation value as the connection strength.
Generally, the adjacency matrix $A$ is known information where its values are
binary or real to express the distance between two nodes.

In our case, it is difficult to evaluate the relationship between two capsules
as this information is unknown before routing. Furthermore, the capsule vector
is a hidden representation which lacks detailed semantic meaning. Therefore,
to overcome this challenge, we use different distance measurements to find the
relationship among capsules semantically and effectively. In this paper, we
explore three distance measurements, which are Wasserstein distance (WD),
Euclidean distance (ED), and cosine similarity (CS). We argue that if two
vectors (for example, vector $y_{i}$ and vector $y_{j}$) express a similar
meaning, they will be semantically close with a large relationship value in
the adjacency matrix.

####  4.1.1 Wasserstein Distance (WD)

Wasserstein Distance is usually used in generative models [18] due to its
ability in measuring the distance between probability distributions. The
capsule vector can be treated as the probability of a certain attribute that
is captured. Therefore, WD which is calculated as $d_{ij}^{w}=\inf
E[\|y_{i}-y_{j}\|_{p}]^{1/p}$ can be applied in capsule vector relationship
evaluation, where $\inf$ denotes infimum, i.e., the greatest lower bound. In
this paper, $p$ is set to $1$. To transfer the Wasserstein distance $d^{w}$ to
the intra-relationship, $a_{ij}={-d^{w}_{ij}}$ is applied. Generally, if two
capsules are semantically close, the value of the intra relationship will be
big.

####  4.1.2 Euclidean Distance (ED)

Euclidean Distance is the straight-line distance between two vectors in
Euclidean space, and it is calculated as
$d^{e}_{ij}=\sqrt{(y_{i}-y_{j})\cdot(y_{i}-y_{j})}$. To transfer the Euclidean
distance $d^{e}$ to the intra relationship, $a_{ij}={-d^{e}_{ij}}$ is also
applied. Similarly, if two capsules are semantically close, the value of the
intra relationship will be big.

####  4.1.3 Cosine Similarity (CS)

Cosine Similarity is another popular measurement between two non-zero vectors,
and it can be calculated as $d^{c}_{ij}=\frac{y_{i}\cdot
y_{j}}{\left\|y_{i}\right\|\left\|y_{j}\right\|}$. To ensure the distance to
itself is zero which is same as the case in ED and WD, the intra relationship
between two capsules is expressed as $a_{ij}=d^{c}_{ij}-1$.

###  4.2 Normalization Trick

Generally, the renormalization trick is used in equation (7), which is
$I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\rightarrow\hat{D}^{-\frac{1}{2}}M\hat{D}^{-\frac{1}{2}}$,
with $M=A+I_{N}$ and $\hat{D}_{ii}=\sum_{j}M_{ij}$. However, if we use ED and
WD as the measurement for intra relationship, the values are negative, which
makes it difficult to apply the general normalization trick to get the
approximate adjacency matrix $A$ because it requires all of the values being
non-negative. To overcome this issue, a more general normalization trick for
equation 7 is proposed in this paper, which is given in equation 8,

$\tilde{A}\rightarrow\text{softmax}(A)+I_{N}$ (8)

Each capsule treats itself as the centroid of the clustering by adding a one-
hot vector. $\tilde{A}$ has eigenvalues in the range $[0,1]$ as the distance
to itself is $0$. And this avoids the gradients exploding/vanishing during the
neural network optimization. It is an instance-level normalization for the
capsule’s relationship learning. Different from the renormalization trick
mentioned before, the semantic distance is normalized in the view of the
current capsule by using the softmax function in the same row. It can be
treated as a variant of random Laplacian matrix normalization. This matches
the true situation in which the importance of the word is different when the
centroid word is different. Taking “The battery has a long life” as an
example, in the view of the word “The”, the word “battery” will have a high
value as “The” is the definite article for “battery”. However, in the view of
the word “battery”, “long life” will play a more important role to express the
positive sentiment than the word “The”. The ablation study shows the
effectiveness of the proposed method.

###  4.3 With Attention

To further improve the quality of the learned features from our graph routing,
and guarantee the learned features are useful, the attention mechanism is
applied. Graph routing is a bottom-up method which highly depends on lower
layer features. If there is no clear cluster center, it will be difficult to
do the feature selection. Different from the routing mechanism, attention
mechanism is a top-down method which helps the routing to select useful
relationships by considering the context information in the same layer. This
guarantees the quality of the gathered relationship. The attention is applied
to the aggregated output $h_{j}$ from GCN which is described in equation 9.

$\displaystyle m_{j}\leftarrow f_{att}(h_{j})$ (9)
$\displaystyle\alpha_{j}=\frac{\exp m_{j}}{\sum_{j}\exp m_{j}}$

Here, $f_{att}$ is the feed-forward function to get the attention weight. The
attention score $\alpha_{j}$ is then applied to the learned feature $h_{j}$
that gets from GCN. The proposed algorithm is in Algorithm 1. It is the same
framework as dynamic routing, except for GCN and attention mechanisms. As
mentioned earlier, in a routing iteration, it is a single-layer GCN for the
feature aggregation.

Algorithm 1 The Algorithm of the Graph Routing

0: Capsules $u_{i}$

1: for $l$ layers do

2: Initialize $e_{ij}\xleftarrow{}0$

3: Get the adjacency matrix $A$ about capsules in layer $l$.

4: Get $\tilde{A}$ with equation 8.

5: $h_{j}\leftarrow u_{ij}^{l}\tilde{A}_{i}W_{ij}$

6: $m_{j}\leftarrow f_{att}(h_{j})$

7: $\alpha_{j}=\text{softmax}(m_{j})$

8: $o_{j}\leftarrow\alpha_{j}h_{j}$

9: for $r$ routing number do

10: All capsule $i$ in layer $l$:

11: $c_{ij}\xleftarrow{}\text{softmax}(e_{ij}^{l})$

12: All capsule $j$ in layer $(l+1)$:

13: $s_{j}\xleftarrow{}\sum_{i}c_{ij}o_{j}$

14: $v_{j}\xleftarrow{}\text{squash}(s_{j})$

15: All capsule $i$ in layer $l$ and capsule $j$ in layer ($l$+1):

16: $e_{ij}^{l+1}\xleftarrow{}e_{ij}^{l}+u_{ij}^{l}\cdot v_{j}$

17: end for

18: return $v_{j}$

19: end for

In the lines 3-4, the $\tilde{A}$ is obtained from the adjacency matrix $A$
row by row. Lines 5-17 are the routing details about the graph routing. In
lines 5-8, GCN and attention are applied. In the line 11, the weight scalar
$c_{ij}$ is calculated from $e_{ij}$ in layer $l$. In the line 14, the squash
function is applied to get the output value $v_{j}$. In the line 16, $e_{ij}$
in layer $l+1$ is calculated.

##  5 Experiments

In this section, we conduct experiments to evaluate the effectiveness of the
proposed graph routing. Specifically, we conduct experiments of document
classification to validate the effectiveness of the proposed routing in text
classification. Then, we validate the hierarchical relationship learning with
semantic consistency, and validate intra relationship learning with adjacency
matrix illustration. Next, the ablation study is conducted to validate the
effectiveness of the proposed normalization trick. To show the generalization
of the proposed routing, we also compare to BERT [10]. Next, the case study is
illustrated to see the effectiveness of the proposed routing. Finally, we
conduct a parameter analysis.

###  5.1 Experimental Settings

####  5.1.1 Datasets

We adopt five benchmark datasets for document classification to evaluate the
effectiveness of the proposed framework. Amazon-Clothing and Amazon-Beauty are
two review datasets that we select111http://jmcauley.ucsd.edu/data/amazon/,
where each document is labeled with a rating ranging from $[1,5]$. Emotion
dataset222https://data.world/crowdflower/sentiment-analysis-in-text contains
13 emotion categories, namely: $\\{$Love, Empty, Relief, Anger, Surprise,
Neutral, Happiness, Sadness, Fun, Enthusiasm, worry, boredom, hate$\\}$.
Yelp333http://yelp.com/dataset is another review dataset we use. The label
range in Yelp dataset is also $[1,5]$. AG News [9] is a news dataset where
each document belongs one of the four classes, i.e., world, sports, business,
and technology . The statistics of those datasets are listed in Table 2.

Datasets | Train | Test | Classes | Avg-Docs | Max-Docs | Vocab Size
---|---|---|---|---|---|---
Amazon Clothing | 250k | 25k | 5 | 68.0 | 4355 | 81836
Amazon Beauty | 180k | 15k | 5 | 99.2 | 4494 | 80935
Emotion | 15k | 5k | 13 | 65.7 | 167 | 30716
Yelp | 650k | 50k | 5 | 118.4 | 1463 | 293402
AG news | 120k | 7.6k | 4 | 39.3 | 196 | 19637
Table 2: The details of the datasets.

Avg-Docs denotes the average word number in the document, while Max-Docs is
the maximum word number. Vocab size is the number of the word that the corpus
contains.

####  5.1.2 Implementation Details

We use TensorFlow in python to implement our model. In all of the experiments,
all word embeddings are initialized randomly with 300-dimensional vectors. The
capsule number is set to 50, the out channel number from NCL and PCL are 64,
the stride for the convolutional operation is 2. The batch size is set to 32,
and the learning rate is 5e-5 during the model training with the Adam
optimization algorithm [14]. All of the experimental results are averaged over
5 runs.

###  5.2 Baseline Methods

In the experiments, the compared routing methods include:

  * 1.

EM Routing: EM routing is proposed in [21]. It is good at spatial feature
extraction, and usually used in image classification.

  * 2.

Dynamic Routing: Dynamic routing is another popular routing method which is
proposed in [22], and also usually used in image classification.

  * 3.

Leaky Dynamic Routing: Leaky dynamic routing is proposed in [30] and achieves
state of the art results in sentiment classification.

  * 4.

KDE Routing: KDE routing is another robust routing model proposed in [29].
This model is good at the multi-label classification and has a good
generalization.

  * 5.

GCN: To make the ablation study about the GCN, we only utilize GCN in the
routing part. Here, the adjacency matrix is calculated with WD.

  * 6.

Transformer: The transformer-based method are very strong baseline models. It
is added on top of the model to replace the routing part while keeping other
parts identical.

To make a fair comparison, all of the compared methods share the same
parameters with the same architecture described in section 3.

###  5.3 Document Classification

The results with different routing methods are listed in Table 3. The bold
number in the table is the best result in a dataset.

Routing Methods |  Amazon Clothing |  Amazon Beauty |  Microsoft Emotion |  Yelp |  AG News
---|---|---|---|---|---
Transformer |  61.87% |  62.50% |  31.07% |  64.61% |  89.16%
EM Routing |  60.57% |  60.65% |  31.04% |  62.51% |  -
Dynamic Routing |  62.87% |  63.19% |  30.82% |  63.65% |  89.02%
Leaky DR (A) |  62.92% |  63.47% |  31.11% |  64.08% |  92.10%$\S$
Leaky DR (B) |  - |  - |  - |  - |  92.60%$\S$
KDE Routing |  62.94% |  63.95% |  31.83% |  64.45% |  90.08%
GCN |  62.86% |  63.47% |  30.87% |  63.35% |  89.61%
Graph Routing(CS) |  62.80% |  63.81% |  31.40% |  64.69% |  92.30%
Graph Routing(ED) |  63.19% |  64.03% |  31.55% |  64.61% |  91.91%
Graph Routing(WD) |  63.44% |  64.13% |  31.61% |  65.33% |  92.62%
With Attention |  63.76% |  64.34% |  31.90% |  65.62% |  92.60%
Table 3: The classification results with different routing methods over those
five datasets. $\S$ means results citing from [30]. Leaky DR is the
abbreviation of leaky dynamic routing that proposed in [30].

The word in the bracket behind the graph routing represents the intra
relationship measurement used in the adjacency matrix. In the table, we can
see that our proposed graph routing achieves competitive performance. In
particular, graph routing with different intra relationships substantially
outperforms the transformer, and there is a noticeable margin on all the
experimental datasets. Also, graph routing with different intra relationships
obtain competitive results against existing routing methods, such as dynamic
routing, leaky dynamic routing and EM routing, especially in the graph routing
with WD which achieves the best results on all of the datasets compared with
other intra relationship measurements. Therefore, we can conclude that the
graph routing with WD has obtained a good quality of the relationship between
different capsules. There is a slight improvement for the leaky dynamic
routing by using Leaky-Softmax [22] to replace the standard softmax function
in strengthening the relationship between a child and parent capsules. If we
only apply GCN to map the capsule vector to the final output by aggregating
the learned features directly, the improvement compared with existing routing
methods is limited. By combining with the attention mechanism, our graph
routing with WD has a further improvement with the best precision on most of
the datasets compared with other routing methods. That is to say, with the
help of the attention mechanism, graph routing becomes more robust and
effective.

###  5.4 Semantic Consistency

One important feature of our graph routing method is that it can learn the
hierarchical and intra relationship between capsules at the same time. In this
subsection, the effectiveness in the hierarchical relationship learning is
validated. However, it is difficult to evaluate this relationship directly as
there is no specific meaning in the capsule, even after the graph routing.
However, if this relationship between different capsules are well learned in a
layer, the capsule distribution in that layer will correlate with the final
output as well. That is to say, there will be a high semantic consistency
between the current capsule layer and the final output if the hierarchical
relationship is well learned. Thus, semantic consistency between different
layers is calculated. The final output denotes $v\in R^{C\times d}$, where $C$
is the class number, the output in each layer is transferred to $p\in
R^{m\times d}$. Each vector in $p$ will be labeled with the class number by
finding the closest vector in $v$. Then semantic consistency is calculated as
the percentage of times that the vector is in the right class. And the vectors
from the NCL, PCL, and RL are considered. Then the outputs from those three
layers will compute with the final output to get the semantic consistency.
This experiment is conducted on the AG News dataset, and the results are
listed in Table 4.

Routing Methods | NCL | PCL | RL
---|---|---|---
Dynamic Routing | 25.72% | 25.39% | 85.82%
Leaky Dynamic Routing | 21.82% | 25.05% | 85.39%
KDE Routing | 24.65% | 25.56% | 86.30%
Graph Routing | 24.85% | 25.70% | 87.55%
Table 4: The semantic consistency between different layer output.

From the Table 4, we can see that there is no difference in column NCL and PCL
compared with existing routing methods. There are four categories about the
document in the AG News. Therefore, only about 25% of the vectors from layer
NCL and PCL remain relevant to the final output. However, after the routing,
the number that related to the final output increases sharply, especially in
the case of graph routing. That is to say that the hierarchical relationship
between different capsules is learned well after the graph routing.

####  5.4.1 Different Relationship Measurements

There are different intra relationship measurements to get the adjacency
matrix between the capsules. From Table 3, we can see that the graph routing
with WD achieves the best results on all datasets compared with CS and ED.
That is to say that WD is an efficient method in distance evaluation. To
explain the goodness of the WD, the adjacency matrices with different
measurements over the same document are illustrated in Figure 3.

Figure 3: The relationship among capsules that learned with different
measurements.

From the color blocks in the red box which is selected randomly from the same
location in the three cases, we can see that the ED are noisier than the other
two measurements, and there is a clear value in WD. On the contrary, the value
in CS is blurred. That is to say that WD has a good evaluation for the intra
relationship.

###  5.5 Ablation Study

To analyze the effectiveness of the new normalization trick we proposed in
subsection 4.2, the ablation validation compared with the renormalization in
equation 7 is conducted. As there is no negative value for the adjacency
matrix, the exponential function is applied to the ED and WD. Therefore,
$a_{ij}=\exp(-d^{e}_{ij})$ in the case of ED, and $a_{ij}=\exp(-d^{w}_{ij})$
in the case of WD. CS is kept the same due to its range being $[0,1]$. Except
for the normalization trick over $\tilde{A}$ is different, all the other parts
of the model are kept the same. The results are showed in Figure 4.

Figure 4: The classification results with different normalization trick in
GCN. $y$-axis denotes the classification result, and the red line named
‘Without A’ is the result of $\tilde{A}$ being replaced by the identity
matrix.

From the figure, we can see that our normalization trick can achieve better
results compared with the normal one, especially in the case of WD and ED.
When using CS as the relationship measurement, there is no difference between
those two normalization tricks as our normalization trick can be treated as a
variant of random Laplacian matrix normalization.

To validate the importance of the intra-relations that learned by the graph
routing, we replace $\tilde{A}$ that learned from Equation 7 with the identity
matrix, and mask the intra-relations that learned among the capsules in the
same layer. The result is pictured in the red line named ‘Without A’ in Figure
4. From the red line we can see that, all these three different distance
metrics are not working under such condition. That is to say, without intra-
relations, the performance of our graph routing degrades dramatically. This
validates the importance of the intra-relations that learned by our graph
routing.

####  5.5.1 With BERT

BERT [10] is so popular that we can not ignore it. To make fair comparisons,
we set “output all encoded layers” to True in the pre-trained BERT
444https://github.com/google-research/bert model, which has been trained on
massive data and computing resources. Before sending these results (12 layers
in total, we also select last 5 layers as another example) to the classifier,
there are four ways to produce the output, which are max pooling out (Max),
average pooling out (Avg), summation (Sum) and our routing method. The results
on the Microsoft emotion dataset are reported in Table 5.

| Max | Avg | Sum | Our Routing
---|---|---|---|---
5 layers | 36.13% | 37.26% | 33.08% | 37.41%
12 layers | 36.43% | 37.00% | 31.77% | 37.03%
Table 5: Comparisons with different pooling out methods in BERT.

We can see that with the help of BERT, our graph routing achieves the best
results compared with other pooling methods both in the case of 5 layers and
12 layers. From this results, we can conclude that our graph routing has a
good generalization when applied in a new model.

###  5.6  Case Study

In this subsection, we show in Figure 5 the effectiveness of our model in
category information extraction. Each word embedding is labeled by the vector
from the graph routing.

Figure 5: The figure above is the distribution of the word. Words in red are
the science category, in blue are the world, in yellow are the sport and in
green are the business. The figures below are the category vector distribution
after the squash operation.

We can see that most of the words are labeled as the science category after
the optimization, and those words are closely related with the sentence topic.
Also, from the output vector that is shown in the text below, we can see that
the values in science are bigger compared with other categories. This example
shows the effectiveness of our routing in the semantic relationships
extraction.

###  5.7 Parameter Analysis

(a) Capsule Number

(b) Iteration Number

Figure 6: The parameters analysis about the capsule number. $y$-axis denotes
the classification result.

In this subsection, two parameters of the routing, iteration number and the
capsule dimension, are discussed. Results are in Figure 6. In Figure 6(a),
when the capsule dimension is set to 64, it achieves the best result. When the
capsule dimension is 256, the server shows the OOM error due to the huge
amount of memory occupation. There is no improvement compared with the
dimension of 64 when the dimension is 128. Therefore, it is the best choice to
set the dimension to 64. In Figure 6(b), when the iteration number is set to
3, it achieves the best result. As the iteration number increases, there is no
improvement in performance.

Routing methods | #Parameter | Time
---|---|---
EM Routing | 31.69MB | 0.1587$s$
KDE Routing | 31.68MB | 0.1439$s$
Leaky DR (A) | 69.07MB | 0.2634$s$
Dynamic Routing | 69.07MB | 0.2632$s$
Graph Routing with Attention | 40.09MB | 0.2655$s$
Table 6: The parameter number and time cost of different routing methods. $s$
denotes second.

We know that graph routing has more steps than existing routing methods, for
example, it takes time to compute the adjacency matrix with WD. To validate
its computing efficiency, a comparison of the number of parameters and the
time cost is shown in the table 6. From the table, we can see that our graph
routing has a smaller parameter number than dynamic routing and leaky dynamic
routing. Although the time cost is slightly larger than dynamic routing and
leaky dynamic routing, it is still competitive considering the number of
parameters.

##  6 Related Works

In this work, we applied the GCN in the routing between the capsules.
Therefore, the related works about the routing between capsules will be
introduced. Also, our work relates with document classification with capsule
network which will be introduced at the same time.

###  6.1 Routing Between Capsules

Since the concept of “capsule” neural networks [13] was firstly proposed, it
has become a hot research topic due to its ability in improving the
representational limitation of CNNs in which pooling operation causes the
information losing. The transformation matrices between different capsules
make the capsule network capture the part-whole relationships. Together with
the routing-by-agreement [22, 21], capsules neural network has achieved
promising results on MNIST data.

It is a bottom-up way for the dynamic routing and the EM routing proposed in
[22, 21] when clustering the vector or matrix together. There are different
variants of dynamic routing. Leaky softmax is applied by replacing the softmax
function to strengthen the relationship between a child and parent capsules
[30]. Task routing algorithm was proposed by applying the clustering procedure
in the task level [27]. Different from the general dynamic routing, task
routing introduced a new coupling coefficient $c_{ij}^{k}$ by subdividing it
to the task $k$. [26] gave empirical results over the best parameters
selection in the capsule network with dynamic routing. Especially the routing
iterations during the routing procedure affects the performance. [6] believed
that dynamic routing is not well integrated into the training procedure,
especially for the iteration number which needs to be decided manually. Thus,
there is a bottleneck for the dynamic routing due to its expense of
computation during the routing. Therefore, Zhang et al. [28] proposed weighted
Kernel Density Estimation (KDE) to accelerate the routing. In [29], an
adaptive KDE routing algorithm was proposed to make the routing decide the
iteration number automatically, which gives a further optimization for the
routing. The empirical results demonstrate its effectiveness on different
classification tasks. Apart from KDE, K-means clustering method was also
validated for its effectiveness during routing [20]. It is a bottom-up way for
the attention, while routing is a top-down way. There are also researches
about combining attention with the routing together in the capsule network
[8].

###  6.2 Capsule Network For Text Classification

Since capsule networks were proposed, most works are on image classification
[22, 21, 26, 6], while recurrent neural networks (RNNs) are more popular in
text data processing [17, 16, 5, 4]. In [23, 11], RNN-Capsule was proposed for
sentiment analysis. In [20], together with the proposed compositional coding
mechanism, bidirectional Gated Recurrent Units (GRU) were adopted for text
classification. Based on the RNN, the attention model was applied in the
capsule network for aspect-level sentiment analysis [24].

Sabour et al. [22] applied the convolutional layer, primary capsule layer in
their model similarly as in image classification. MCapsNet stacked the
convolutional network, primary capsule layer, and representation layer
together to do multi-task text classification [27]. Different from the
MCapsNet, Zhao et al. [30] paralleled three such architecture together with
filter window of 3, 4, 5 in the convolutional layer. All of those works show
the effectiveness of such architectures in text feature extraction.

##  7 Conclusion & Future Works

It is the first time to treat the capsule as a node in a graph, and our graph
routing applies GCN to explore the relationship between capsules in the same
layer. Together with the attention mechanism, graph routing also remedies the
disadvantage of the routing which highly depends on the lower level features.
Furthermore, different distances between capsules are discussed. Empirical
results show the effectiveness of the proposed model: The performance of three
out of five datasets is improved by more than 0.3 compared with state-of-the-
art models. In the future works, we will explore a more effective graph neural
network in the intra-relationship learning within the capsules, and find out a
more efficient method for feature learning of text data using capsule
networks. Also we will explore and design a new attention mechanism to
accommodate our graph routing.

##  8 Acknowledgment

This research is supported by the Agency for Science, Technology and Research
(A*STAR) under its AME Programmatic Funding Scheme (Project #A18A2b0046).

## References

  * [1] Md Shad Akhtar, Asif Ekbal, and Erik Cambria.  How intense are you? predicting intensities of emotions and sentiments using stacked ensemble.  IEEE Computational Intelligence Magazine, 15(1):64–75, 2020.
  * [2] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [3] Erik Cambria, Yang Li, Frank Xing, Soujanya Poria, and Kenneth Kwok.  SenticNet 6: Ensemble application of symbolic and subsymbolic AI for sentiment analysis.  In CIKM, pages 105–114, 2020.
  * [4] Iti Chaturvedi, Yew-Soon Ong, Ivor Tsang, Roy Welsch, and Erik Cambria.  Learning word dependencies in text by means of a deep recurrent belief network.  Knowledge-Based Systems, 108:144–154, 2016.
  * [5] Guibin Chen, Deheng Ye, Erik Cambria, Jieshan Chen, and Zhenchang Xing.  Ensemble application of convolutional and recurrent neural networks for multi-label text categorization.  In IJCNN, pages 2377–2383, 2017.
  * [6] Zhenhua Chen and David Crandall.  Generalized capsule networks with trainable routing procedure.  arXiv preprint arXiv:1808.08692, 2018.
  * [7] Prerna Chikersal, Soujanya Poria, Erik Cambria, Alexander Gelbukh, and Chng Eng Siong.  Modelling public sentiment in twitter: Using linguistic patterns to enhance supervised learning.  In Computational Linguistics and Intelligent Text Processing, pages 49–65. Springer, 2015.
  * [8] Jaewoong Choi, Hyun Seo, Suii Im, and Myungju Kang.  Attention routing between capsules, 2019.
  * [9] Alexis Conneau, Holger Schwenk, Loïc Barrault, and Yann Lecun.  Very deep convolutional networks for text classification.  In 15th Conference of the European Chapter of the Association for Computational Linguistic, 2017.
  * [10] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [11] Jingjing Gong, Xipeng Qiu, Shaojing Wang, and Xuanjing Huang.  Information aggregation via dynamic routing for sequence encoding.  arXiv preprint arXiv:1806.01501, 2018.
  * [12] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval.  Wavelets on graphs via spectral graph theory.  Applied and Computational Harmonic Analysis, 30(2):129–150, 2011\.
  * [13] Geoffrey E Hinton, Alex Krizhevsky, and Sida D Wang.  Transforming auto-encoders.  In International Conference on Artificial Neural Networks, pages 44–51. Springer, 2011.
  * [14] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [15] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [16] Wei Li, Wei Shao, Shaoxiong Ji, and Erik Cambria.  BiERU: Bidirectional emotional recurrent unit for conversational sentiment analysis.  arXiv preprint arXiv:2006.00492, 2020.
  * [17] Yang Li.  Research on Short Text Sentiment Analysis and Its Applications.  PhD thesis, Northwestern Polytechnical University, ShanXi Province, China, 12 2018.
  * [18] Yang Li, Quan Pan, Suhang Wang, Tao Yang, and Erik Cambria.  A generative model for category text generation.  Information Sciences, 450:301–315, 2018.
  * [19] Shirui Pan, Ruiqi Hu, Sai-fu Fung, Guodong Long, Jing Jiang, and Chengqi Zhang.  Learning graph embedding with adversarial training methods.  IEEE Transactions on Cybernetics, 50(6):2475–2487, 2019.
  * [20] Hao Ren and Hong Lu.  Compositional coding capsule network with k-means routing for text classification.  arXiv preprint arXiv:1810.09177, 2018.
  * [21] Sara Sabour, Nicholas Frosst, and G Hinton.  Matrix capsules with em routing.  In 6th International Conference on Learning Representations, ICLR, 2018.
  * [22] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton.  Dynamic routing between capsules.  In Advances in neural information processing systems, pages 3856–3866, 2017.
  * [23] Yequan Wang, Aixin Sun, Jialong Han, Ying Liu, and Xiaoyan Zhu.  Sentiment analysis by capsules.  In Proceedings of the 2018 World Wide Web Conference, pages 1165–1174. International World Wide Web Conferences Steering Committee, 2018\.
  * [24] Yequan Wang, Aixin Sun, Minlie Huang, and Xiaoyan Zhu.  Aspect-level sentiment analysis using as-capsules.  In The World Wide Web Conference, pages 2033–2044. ACM, 2019.
  * [25] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE Transactions on Neural Networks and Learning Systems, 2020\.
  * [26] Edgar Xi, Selina Bing, and Yang Jin.  Capsule network performance on complex data.  arXiv preprint arXiv:1712.03480, 2017.
  * [27] Liqiang Xiao, Honglun Zhang, Wenqing Chen, Yongkun Wang, and Yaohui Jin.  Mcapsnet: Capsule network for text with multi-task learning.  In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4565–4574, 2018.
  * [28] Suofei Zhang, Quan Zhou, and Xiaofu Wu.  Fast dynamic routing based on weighted kernel density estimation.  In International Symposium on Artificial Intelligence and Robotics, pages 301–309. Springer, 2018.
  * [29] Wei Zhao, Haiyun Peng, Steffen Eger, Erik Cambria, and Min Yang.  Towards scalable and reliable capsule networks for challenging NLP applications.  In ACL, pages 1549–1559, 2019.
  * [30] Wei Zhao, Jianbo Ye, Min Yang, Zeyang Lei, Suofei Zhang, and Zhou Zhao.  Investigating capsule networks with dynamic routing for text classification.  arXiv preprint arXiv:1804.00538, 2018.