{'fraction_non_alphanumeric': 0.03658100776453007, 'fraction_numerical': 0.016828563074623958, 'mean_word_length': 4.726883720930233, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
NCGNN: Node-level Capsule Graph Neural Network

Message passing has evolved as an effective tool for designing Graph Neural Networks (GNNs). However, most existing works naively sum or average all the neighboring features to update node representations, which suffers from the following limitations: (1) lack of interpretability to identify crucial node features for GNN’s prediction; (2) over-smoothing issue where repeated averaging aggregates excessive noise, making features of nodes in different classes over-mixed and thus indistinguishable. In this paper, we propose the Node-level Capsule Graph Neural Network (NCGNN) to address these issues with an improved message passing scheme. Specifically, NCGNN represents nodes as groups of capsules, in which each capsule extracts distinctive features of its corresponding node. For each node-level capsule, a novel dynamic routing procedure is developed to adaptively select appropriate capsules for aggregation from a subgraph identified by the designed graph filter. Consequently, as only the advantageous capsules are aggregated and harmful noise is restrained, overmixing features of interacting nodes in different classes tends to be avoided to relieve the over-smoothing issue. Furthermore, since the graph filter and the dynamic routing identify a subgraph and a subset of node features that are most influential for the prediction of the model, NCGNN is inherently interpretable and exempt from complex post-hoc explanations. Extensive experiments on six node classification benchmarks demonstrate that NCGNN can well address the over-smoothing issue and outperforms the state of the arts by producing better node embeddings for classification.


Introduction
Message passing has proved to be the cornerstone of numerous Graph Neural Networks (GNNs) for analyzing data with irregular structures, including citation networks (Kipf and Welling 2017;Gao, Wang, and Ji 2018;Veličković et al. 2018), point clouds (Simonovsky and Komodakis 2017;Wang et al. 2019), chemical molecules (Duvenaud et al. 2015;Gilmer et al. 2017), and recommendation systems (Ying et al. 2018). The essential idea is to update the representation of each node by iteratively aggregating features from its topological neighborhoods. Commencing with the great success of GCN (Kipf and Welling 2017) in semisupervised node classification, a myriad of studies have been developed to ameliorate the vanilla message passing scheme with attention mechanism (Veličković et al. 2018;Zhang et al. 2020), edge attributes (Gong and Cheng 2019), multirelational features (Vashishth et al. 2020), and structural information (Pei et al. 2020;Ye et al. 2020;Zhang et al. 2020).
Despite the promising performance, most existing message passing schemes rely on the naive sum or average aggregator to fuse all the neighborhood information. Therefore, two severe challenges have been presented for GNNs: • Summing up or averaging all the neighboring features make GNNs lack human intelligible explanations. Since the most influential part of node features for the prediction of the model cannot be identified, complex post-hoc methods would be required to explain GNNs in certain application domains (Ying et al. 2019;Yuan et al. 2020). • Excessive noise might be aggregated, when stacking multiple message passing layers to capture long-range neighborhood information. Node features in different classes would be over-mixed and indistinguishable, which is the over-smoothing issue in GNNs. Inspired by the interpretability and dynamic routing procedure of capsule networks (Hinton, Krizhevsky, and Wang 2011;Sabour, Frosst, and Hinton 2017;Hinton, Sabour, and Frosst 2018;Tsai et al. 2020), we propose the Node-level Capsule Graph Neural Network (NCGNN) to address these challenges with adaptive message passing between interacting nodes. To the best of our knowledge, NCGNN is the first inherently interpretable graph model that leverages dynamic routing between node-level capsules to produce better node embeddings and address the over-smoothing issue for semi-supervised node classification. Existing capsulerelated GNNs (Verma and Zhang 2018;Xinyi and Chen 2019;Ma et al. 2019) commonly focus on graph-level classification or flatten the capsules back to scalar features (or both). A detailed discussion is provided to distinguish our work in the evaluation section.
To be concrete, NCGNN first transforms each node from the scalar-based features to a group of primary node capsules (vectors), in which each capsule reflects the distinctive properties of a node by projecting the node features into different subspaces. As in CapsNet (Sabour, Frosst, and Hinton 2017), the orientation of a capsule represents specific types of properties. Thus, the message passing scheme in NCGNN is designed to address two enlightening questions: • Q1: For each target node, how to identify the graph nodes (a subgraph) where information should be aggregated?
• Q2: For each capsule of an individual node, how to aggregate an appropriate subset of capsules that contains little noise from the subgraph to prevent feature over-mixing?
To address question Q1, we employ two graph filters in the attention-and diffusion-based manner, respectively, to select a subgraph for each target node to perform feature aggregation. Unlike most existing works (e.g., GCN (Kipf and Welling 2017), MoNet (Monti et al. 2017), and GAT (Veličković et al. 2018)) that only aggregate one-hop neighborhood information in each message passing step, the designed graph filters can adapt to higher-order neighborhoods to directly capture long-range dependencies and support explanations from both spatial and spectral aspects.
When the subgraph nodes with associated primary node capsules for each target node are obtained, we solve question Q2 by designing a capsule graph layer that leverages a novel neighborhood-routing-by-agreement mechanism between node-level capsules to improve the existing message passing schemes. As studied in (Li, Han, and Wu 2018;Chen et al. 2020a), the naive average aggregator is a special form of Laplacian smoothing that forces connected nodes to produce similar features, thereby easing the downstream node classification task. However, in real-world graphs, features from neighboring nodes are not always desirable. Repeated averaging would also aggregate excessive noise and over-mix node features in different classes, which severely hampers the node classification performance. By contrast, benefiting from dynamic routing, each node-level capsule adaptively selects the advantageous neighboring capsules for aggregation in our capsule graph layer. Harmful noise from neighborhoods would be restrained to relieve the oversmoothing issue.
Furthermore, we can naturally achieve an interpretable GNN model by solving these two questions, as it identifies a subgraph and a subset of node features that are most influential for the prediction of the model, following the same principle as the post-hoc explanation method in (Ying et al. 2019). For empirical evaluation, we conduct comprehensive experiments on six node classification benchmarks. Experimental results demonstrate that, contrary to the existing message passing schemes that might suffer from the over-smoothing issue in extracting high-order neighborhood information, NCGNN achieves performance gains with the increasing orders (hops) of neighborhoods. We further show that the dynamic routing procedure between node-level capsules indeed produces more separable node embeddings for nodes in different classes, which also verifies the effectiveness of NCGNN for tackling the over-smoothing problem.

Preliminaries
Notations and Problem Setting This paper focuses on the task of graph-based semi-supervised learning. By definition, a simple undirected graph with N nodes is represented as a is the node set, and A ∈ R N ×N is the adjacency matrix where each entry a ij is set to 1 for the existence of edge linking nodes v i and v j and 0 otherwise. The normalized graph Laplacian is defined The multi-head (channel) message passing scheme with four independent sum aggregators. (c) The dynamic routing procedure between node-level capsules in NCGNN. For a better view, we only plot the dynamic routing between one capsule of node y and the capsules of node x. The intensity of the arrow color indicates the coupling degree between capsules.
is the degree matrix with d i denoting the degree of node v i . The eigendecomposition of L gives us L = UΛU . Here, Λ is a diagonal matrix of the eigenvalues of L, and the columns of U are the orthonormal eigenvectors termed graph Fourier basis. In spectral graph theory, a graph filter can be defined as a parameterized polynomial function g θ (L) of L, and a graph signal x ∈ R N filtered by g θ can be written as y = g θ (L)x = Ug θ (Λ)U x ∈ R N . We also have a feature matrix X = [x 1 , . . . , x N ] ∈ R N ×f with each row corresponding to the feature vector of an individual node. Given a subset of graph nodes V l ⊂ V with labels, the task is to predict the classes of unlabeled nodes V u = V\V l based on G and X.
Message passing based GNNs The core of most GNNs is message passing scheme. Denote with W (l) the learnable weights in the l-th layer, N (i) the set of neighboring node indices for node v i , and σ(·) the nonlinear activation function, a basic message passing layer takes the following form: where h (l) j is the input representation of node v j in the l-th layer, and α (l) ij is the edge weight for the message passing from node v j to node v i , which can be computed via different mechanisms (Kipf and Welling 2017;Veličković et al. 2018;Ma et al. 2019;Ye et al. 2020;Zhang et al. 2020).
Here gives a brief comparison of different message passing schemes. Figure 1(a) depicts the vanilla sum aggregator in GCN (Kipf and Welling 2017), where each node sums all the neighboring features with fixed edge weights to update its representation. Figure 1(b) shows the multi-head (channel) attention utilized by models such as GAT (Veličković et al. 2018) and DisenGCN (Ma et al. 2019). Although the Figure 2: Workflow of NCGNN: NCGNN first transforms each node from the scalar-based features to K primary node capsules. Subsequently, the designed graph filter selects a subgraph for each target node to perform message passing and dynamic routing is leveraged to generate C class node capsules for it, where C is the number of classes. In capsule graph layer (CGL), each node-level capsule adaptively selects appropriate capsules to update its representation and noisy features from neighborhoods are restrained to avoid over-smoothing. For a better view, we only plot the message passing procedure for generating the class node capsules of the brown node. Note that CGLs can be further stacked if necessary, though we only use one CGL to produce C class node capsules for each target node. edge weights can be learned with diverse mechanisms to improve the model capacity, each independent channel is still a naive averaging operation that sums all the neighboring features, which can be seen as an ensemble of graph models. Figure 1(c) demonstrates the dynamic routing procedure in NCGNN, where each node-level capsule adaptively aggregates an appropriate subset of capsules and restrains harmful noise from neighboring nodes, which helps prevent feature over-mixing to address the over-smoothing problem.
Over-smoothing in GNNs As illustrated in (Chen et al. 2020a), over-smoothing is caused by the feature over-mixing of nodes in different classes. To address this problem, several works have been proposed. JK-Net (Xu et al. 2018) and DNA (Fey 2019) utilize skip connection and attention mechanism for preserving the information in each message passing step. APPNP (Klicpera, Bojchevski, and Günnemann 2019) considers graph diffusion to replace the adjacency matrix with personalized PageRank matrix that takes the root node into account. GCNII (Chen et al. 2020b) modifies GCN with initial residual and identity mapping. Besides, some tricks have been studied. DropEdge (Rong et al. 2020) randomly removes a certain fraction of edges in each training step to reduce message passing. AdaEdge (Chen et al. 2020a) constantly adjusts the graph topology (adding intraclass edges and removing inter-class edges) according to the predictions made by GNNs in a self-training-like fashion. BBGDC (Hasanzadeh et al. 2020) generalizes DropEdge and Dropout (Srivastava et al. 2014) by adaptive connection sampling. In comparison, our NCGNN addresses oversmoothing by directly restraining noisy messages passing between interacting nodes to prevent feature over-mixing.

Methodology
In this section, we introduce the proposed Node-level Capsule Graph Neural Network (NCGNN), an inherently interpretable graph model for tackling the over-smoothing issue in GNNs with an adaptive message passing scheme. Figure 2 demonstrates the workflow of NCGNN.
NCGNN first converts each node from the scalar-based features to a group of primary node capsules by projecting the node features into K subspaces: where · denotes the Euclidean norm, h (k) i ∈ R fp is the k-th primary node capsule of node v i , W (k) ∈ R fp×f and b (k) ∈ R fp are the learnable weights and bias with respect to the k-th subspace.
Having obtained the primary node capsules, in what follows we elaborate the mechanisms of the designed graph filter and capsule graph layer for solving questions Q1 and Q2 to address the over-smoothing problem.

Graph Filter
For each target node, the graph filter identifies a subgraph where it should aggregate features and determines the influence of each subgraph node on it. In the vanilla GCN (Kipf and Welling 2017), the graph filter is defined as the symmetric normalized transition matrixÃ =D − 1 2ÂD − 1 2 , wherê A = A+I N andD = D+I N . This graph filter and its variants (Veličković et al. 2018;Zhang et al. 2020) are widely used in existing GNNs where only the one-hop neighborhood features are aggregated. However, higher-order neighborhood information are also useful for generating node embeddings, as studied in (Abu-El-Haija et al. 2019; Lee et al. 2019;Klicpera, Bojchevski, and Günnemann 2019). To extract long range dependencies, we define the generalized graph filter as in Eq. (3) with two specific forms in the attention-and diffusion-based manner, respectively.
Here, M is the set of multiple distances (hops) (e.g., M = {1, 2, 4, 5}), f ξ is a polynomial function parameterized by coefficients ξ i (i ∈ M). Considering that the exponentiation operationÃ i may result in a dense matrix even for a small i due to the small-world property (Mehlhorn and Schreiber 2013) of real-world graphs, we maintain the sparsity property by using either an -threshold or top-k sparsification as in (Klicpera, Weißenberger, and Günnemann 2019), i.e., entries ofÃ i that are smaller than a threshold or are not the top-k values in each row are set to 0, and the symmetric normalization are recalculated for the sparsified version ofÃ i subsequently. Then, each row ofĀ identifies part of the N nodes (a subgraph) for the corresponding node to aggregate information, and each non-zero entry denotes the influence of the message passing between two interacting nodes.
Attention-based Graph Filter The attention-based graph filter is flexible and learnable, i.e., there is no constraint on M and the coefficients are data-driven. Given M andÃ i of distance i (i ∈ M), the corresponding coefficient satisfies: which is the common softmax operation and ζ j (j ∈ M) are free parameters directly learned via backpropagation. Thus, the coefficients of the polynomial function f ξ can be interpreted as the attention scores assigned to neighborhoods of different hops. Note that although this attention mechanism is not node-adaptive (i.e., shared across graph nodes), this weight sharing fashion helps prevent overfitting and performs well on all the benchmark datasets.
Diffusion-based Graph Filter In recent works (Klicpera, Bojchevski, and Günnemann 2019;Klicpera, Weißenberger, and Günnemann 2019;Bojchevski et al. 2020), graph diffusion has demonstrated promising performance by propagating features using personalized PageRank (PPR) and heat kernel (HK). In this work, we also evaluate the performance of PPR matrix as the fixed diffusion-based graph filter (HK is omitted due to comparable performance) in NCGNN: where α ∈ (0, 1) is termed teleport probability and M = N. When tackling large-scale graphs for which it is inefficient to compute matrix inversion, we use the truncated form as in Eq. (6). We also apply sparsification to the fixed diffusionbased graph filter.Ā Discussion The designed graph filter in Eq.
(3) can be explained from both spatial and spectral aspects. In the spatial domain, each entryā ij ofĀ represents the influence of the message passing from node v j to node v i . In the spectral domain, the following proposition indicates the relationship betweenĀ and g θ (L) (see more details in the Appendix of (Klicpera, Weißenberger, and Günnemann 2019)):

Capsule Graph Layer
After obtaining the subgraph nodes {v j |ā ij = 0} identified by the graph filterĀ and a set of primary node capsules S = {h (k) j |ā ij = 0, k = 1, . . . , K} for each target node v i ∈ V, this subsection elucidates how the designed capsule graph layer transforms node v i from K primary node capsules to C class node capsules T = {u (l) i |l = 1, . . . , C} for classification with adaptive feature aggregation from S to T .
Denote with f p the dimension of primary node capsules, f c the dimension of class node capsules, W kl ∈ R fc×fp the weights between the k-th primary node capsules and the lth class node capsules, and b l ∈ R fc the bias for the l-th class node capsules. The feature generation rule for the l-th class node capsule u where c jkl is the coupling coefficient between h (k) j and p (l) j , an intermediate capsule representing the properties of class l extracted from node v j . As per dynamic routing, c jkl is computed via an iterative neighborhood-routing-by-agreement procedure to adaptively select appropriate primary node capsules for aggregation from S, which will be discussed later. a ij is computed by the graph filterĀ, determining the influence of the message passing from node v j to node v i .
As in CapsNet (Sabour, Frosst, and Hinton 2017), we want the length of the output vector of each class node capsule u (l) i to indicate the presence of an instance of class l. Hence, we use the "squash" activation function as in Eq. (8) to ensure that the length of the output vector of u (l) i lies between zero and one, representing the probability that node v i belongs to class l. We also use the separate margin loss as in Eq. (9) for each class node capsule.

v
where L (l) i is the loss for the l-th class node capsule of node v i , T k = 1 if node v i belongs to class k and 0 otherwise, m + is close to 1 (commonly 0.8), m − is close to 0 (commonly 0.2), and λ (0.5 in this work) is a parameter for preventing all class node capsules from shrinking to 0 at the beginning of training. The total loss is L = 1

4:
for l = 1, . . . , C do 5: For all nodes: p j ), ∀k = 1, . . . , K. Neighborhood-routing-by-agreement While in CapsNet and CapsGNN (Xinyi and Chen 2019), the coupling coefficients between a capsule and all the capsules in the layer above sum to 1, which implies that each capsule gets sent to an appropriate parent in the next layer, our neighborhoodrouting-by-agreement results from different motivations. In our NCGNN framework, the coupling coefficients between a class node capsule and the primary node capsules of each individual node in the subgraph sum to 1, i.e., K k=1 c jkl = 1. This means that for each subgraph node, some of its primary node capsules are in agreement, i.e., to be aggregated, while some are considered as noise to be restrained. The agreement is in the form of dot product of two vectors, and c jkl is iteratively adjusted according to Eq. (10) for iterations t = 0, . . . , T , starting by initializing c jkl as where i . The procedure of the capsule graph layer in node-wise fashion is summarized in Algorithm 1.

Complexity Analysis
Denote with N the number of nodes needed for computation, L the number of layers of GCN, T the routing iterations of NCGNN, and D the dimension of node embeddings (for simplicity, we assume it is fixed for all layers and Kf p = Cf c = D). Based on these notations, the time complexity of GCN is O(LN D 2 + L Ã 0 D), and that of NCGNN is O(2N D 2 +T Ā 0 D +T N KD). Although our graph filterĀ contains more higher-order neighborhood information than the first-order normalized adjacency matrix A utilized in GCN,Ā is processed with -threshold or top-k   (Bojchevski et al. 2020), as it only has one capsule graph layer to directly incorporate high-order neighborhood features, which is exempt from the exponential neighborhood expansion issue, i.e., to generate the class node capsules for each target node, we only need to load the features of its neighboring nodes identified byĀ.

Evaluations
We evaluate NCGNN on the task of semi-supervised node classification. Extensive experiments on six datasets show that NCGNN outperforms a variety of state of the arts and well addresses the over-smoothing problem in GNNs.

Datasets
Six well-known benchmark datasets are utilized for validating all the baselines and our NCGNN framework, including four citation networks and two segments from the Amazon co-purchase graph. Cora (Sen et al. 2008), Cora-ML (Mc-Callum et al. 2000;Bojchevski and Günnemann 2018), Citeseer (Sen et al. 2008), and Pubmed (Namata et al. 2012) are citation networks, where nodes represent documents, edges denote citations, and node features are bag-of-words representations of papers. Amazon Photo and Amazon Computers (Shchur et al. 2018) are two segments of the Amazon copurchase graph, where nodes are goods, edges indicate that two goods are frequently bought together, and node features are bag-of-words encoded product reviews. The statistics of the datasets are summarized in Table 1. Under the setting of semi-supervised node classification, for each dataset we use 20 labeled nodes per class as the training set, 500 nodes as the validation set, and the rest is set for test. For a fairer comparison, we select 5 random train/validation/test splits for each dataset and run 10 turns with different weight initialization seeds in each split. Then we measure the average test accuracy of all the 50 runs' results.

Experimental Set-up
Baselines We compare with the following baselines: three representative graph models: GCN (Kipf and Welling 2017), GAT (Veličković et al. 2018), and SGC (Wu et al. 2019); graph diffusion based message passing: APPNP (Klicpera, Bojchevski, and Günnemann 2019); two recently proposed GNNs for tackling over-smoothing: JK-Net (Xu et al. 2018) NCGNN-A 81.8 82.2 83.2 83.7 83.7 69.1 69.3 69.5 70.1 70.1 78.6 79.2 79.1 78.9 79.2 85.3 85.7 85.4 85.3 85.7 Table 2: Average test accuracy (%) over 5 random data splits with 10 random weight initializations for each split on the four citation networks."-D" denotes diffusion-based graph filter, "-A" denotes attention-based graph filter. OM means out of memory. N/A denotes the corresponding model does not converge. Note that we compute the fully personalized PageRank matrix in Eq. (5) for Cora, Citeseer, and Cora-ML, while use the truncated form in Eq. (6) with P = 5 for Pubmed, and GCNII achieves the best performance with 64, 32, 16, 64 hops for the four datasets from left to right, respectively.  Table 3: Average test accuracy (%) over 5 random data splits with 10 random weight initializations for each split on the Amazon co-purchase graph. OM denotes out of memory.

Model Configurations
The dimension of class node capsules (f c ) is set to 16. Dropout of p = 0.9 is applied to the primary node capsules. We use Adam (Kingma and Ba 2015) optimizer to minimize the error function with learning rate of 1e − 3. Training epochs are manually set for each dataset. 2 regularization on the learnable parameters is also employed with weight decay of 5e − 3 for Cora and Citeseer and 1e − 2 for the others. The teleport probability α is set to 0.05 for Cora and Cora-

Results and Analysis
Citation Networks We compare NCGNN with the baselines under different sizes of receptive field (the maximum hop of neighborhoods) on the four citation networks. The average test accuracy is summarized in Table 2 and the best accuracy in each column is highlighted in bold. It can be observed that NCGNN-A achieves the state of the art performance on all datasets, and NCGNN-D outperforms all the baselines except on Pubmed (slightly worse than GCNII). We further plot the accuracy curve with varying sizes of receptive field. As shown in Figure 3, NCGNN-A consistently obtains optimum performance with receptive field size ranging from 2 to 5. Moreover, NCGNN-A does not suffer from the over-smoothing issue and even gains performance boosts with message passing from higher-order neighborhoods.
Amazon Co-purchase Graph For Amazon co-purchase graph, we just consider 2-hop neighbors as its size is large enough for aggregating useful information (the number of 2hop neighbors of Amazon Photo is averagely 815 and that of Amazon Computers is about 1887). The average test accuracy is reported in Table 3. It shows that NCGNN achieves the best performance on both datasets and outperforms the baselines by a large margin on Amazon Computers. We argue that the performance boost is gained from the dynamic routing between node-level capsules. The reason is that the previous message passing schemes would inevitably aggregate excessive noise in Amazon Computers where the average receptive field size of nodes is very large, while NCGNN can effectively restrain noise from the large neighborhoods to prevent feature over-mixing. We also plot t-SNE (Maaten and Hinton 2008) of the node embeddings (hidden features for GCN and GAT, and the output vector of each node's class node capsule with the maximum length for NCGNN) learned on Amazon Computers in Figure 4. As can be seen, node embeddings generated by NCGNN is much more separable across different classes (colors), which also verifies    that dynamic routing can indeed aggregate appropriate features and restrain harmful noise to relieve over-smoothing.
Hyperparameter Sensitivity We investigate the impacts of two important hyperparameters in NCGNN: the number of primary node capsules (K) and the routing iterations (T ). Figure 5 demonstrates the influences of these two hyperparameters on the classification performance of NCGNN-A for Cora with a fixed dataset split (NCGNN-D shows similar performance). The results indicate that NCGNN is not sensitive to these hyperparameters. For K ranging from 4 to 12 and T ranging from 2 to 8, NCGNN shows robust performance and consistently outperforms GCN by large margins.
Interpretability As illustrated above, our NCGNN is inherently interpretable by identifying a subgraph and a sub-set of node features that are most influential for the model's prediction. For qualitative analysis, Figure 6 visualizes the attention scores and the coupling coefficients learned by a NCGNN-A with receptive field size of 5 trained on the Cora dataset. The left figure shows that, contrary to the fixed PPR matrix, the attention-based graph filter learns larger attention scores for high-order neighborhoods, which verifies that NCGNN-A indeed benefits from long range dependencies and is exempt from the over-smoothing problem. The right figure is the average coupling coefficients between the 5th class node capsules and the primary node capsules of their neighboring nodes identified byĀ. It indicates that dynamic routing between node-level capsules assigns larger coupling coefficients for a subset of node features (2nd, 3rd, and 4th primary node capsules), explaining that these capsules have a crucial role in predicting the nodes as the 5th class.

Comparison with Other Capsule-related GNNs
Existing capsule-related GNNs commonly focus on graph classification, while NCGNN is proposed for node classification. GCAPS-CNN (Verma and Zhang 2018) concatenates higher-order statistical moments over each node's neighborhood as its capsules. However, capsules are flattened back to scalar-output features for message passing between layers. CapsGNN (Xinyi and Chen 2019) does not focus on the message passing within GNNs. It employs a GNN to produce graph-level representations and then dynamic routing is utilized on top of the GNN to benefit graph embeddings. Besides, another work termed DisenGCN (Ma et al. 2019) for node classification views the disentangled node representations as capsules. However, its message passing is essentially a multi-channel ensemble as shown in Figure 1(b). There is no dynamic routing between different channels (capsules) as in capsule networks and capsules are also flattened back to scalar-based features as in GCAPS-CNN. By comparison, NCGNN leverages dynamic routing to adaptively aggregate appropriate node-level capsules and restrain harmful noise from higher-order neighborhoods for each target node.

Conclusion
In this paper, we propose Node-level Capsule Graph Neural Network (NCGNN) to address the over-smoothing issue for semi-supervised node classification. NCGNN represents nodes as groups of capsules. By leveraging the designed graph filter and capsule graph layer, each node-level capsule adaptively aggregates the advantageous capsules and restrains harmful noise from high-order neighborhoods. Experiments on six datasets show that NCGNN can benefit from aggregating high-order features while be exempt from the over-smoothing issue. Moreover, NCGNN is inherently interpretable by identifying a subgraph and a subset of node features that are crucial for the model's prediction.

Broader Implications
Graphs, as a common technique to represent the elements of a complex system and their relationships, accommodate numerous potential applications, including community detection in social networks, document classification in citation networks, and spatiotemporal forecasting in traffic networks. This work focuses on solving a fundamental task of semi-supervised node classification in the field of graphbased machine learning, and therefore is promising for many real-world applications and reduces the cost of solving social problems using machine learning with limited labeled data. Moreover, our proposed framework is inherently interpretable. Thus, it has better trustworthiness and shows potential use in decision-critical applications pertaining to fairness, privacy and safety.