A Sparse-Motif Ensemble Graph Convolutional Network against Over-smoothing

1 Introduction

Nowadays, graph structure has emerged as one of the major means to express real-world data such as knowledge base, molecules, social networks, paper citing, where a large set of nodes are organized in an irregular and complicated manner. Consequently, how to learn effectively on graphs becomes an urgent problem. A natural solution is to resort to the recent success of deep learning. This idea brings about a class of neural networks known as Graph Neural Networks (GNN). This paper mainly focuses on a major branch of GNN

∗Corresponding Author

called Graph Convolutional Network (GCN). The main idea of GCN is to extend the convolution operator on the euclidean image data to non-euclidean graph data. Hitherto, GCN has grown up as a popular topic in the machine learning community and has been applied to a wide range of applications including protein structure prediction [Shen and others, 2021; Tsubaki et al., 2019], molecular fingerprint learning [Shui and Karypis, 2020; Rahaman and Gagliardi, 2020], visual reasoning [Gao et al., 2020; Narasimhan et al., 2018], traffic prediction [Jiang and Luo, 2021; Xie et al., 2020], and social network analysis [Liu et al., 2021; Guo and Wang, 2020].

A key challenge for GCN is that it fails to perform well when its depth grows increasingly. Such an observation significantly contradicts the well-known empirical results of Convolutional Neural Networks (CNN), where increasing the depth of a network often leads to a sharp performance gain. This is because the expressive power of GCN is often hindered by the notorious over-smoothing issue, which is because that graph convolution defined in GCN is essentially a Laplacian smoothing operator. As shown in [Huang et al., 2020], after repeatedly applying the Laplacian smoothing in GCN many times, the features of all nodes in a (connected) graph would converge to similar values.

Recently, a series of studies have arisen to tackle the over-smoothing problem. However, the vast majority of the literature captures the spectral information only from the Laplacian of the original graph [Kipf and Welling, 2017; Wu et al., 2019; Xu et al., 2018]. Since over-smoothing is a natural property of Laplacian smoothing, we argue that oversmoothing might be mitigated by introducing a series of diversified representations of the graph spectrum. Moreover, it is noteworthy that the inputs of GCNs are often complex networks. It is well-known that [Benson et al., 2016] the local topological structure of such complex networks could be captured effectively by the so-called motifs, or the small network subgraphs. On the other hand, such information might be ignored if only the original graph Laplacian is employed. Inspired by this, our goal in this paper is to mitigate the oversmoothing issue through the diversity introduced by graph motifs. Specifically, we propose a Sparse-Motif Ensemble Graph Convolutional Network (SMEGCN) 1 . In a nutshell, our contribution is three-fold:

1 Code is available at: https://github.com/BoloJX/SMEGCN

• (A) Since the connections in the original definition of the motif adjacency matrix are dense, blindly employing the motif-based propagation will lead to even faster convergence to the over-smoothed representation. Seeing this, we first propose the notion of the sparse motif to remove the spurious connections and then explore the properties of its message-passing. In this way, we can extract the local topology captured by the sparse motif without worsening the over-smoothing issue.
• (B) On top of this, we propose a hierarchical motif aggregation mechanism to further mitigate the over-smoothing issue, where the features from motif-level messagepassing and graph-level message-passing are given in a learnable manner.
• (C) Theoretically, we show that the output embedding of our proposed method will not converge to a trivial subspace under mild assumptions. Empirically, we perform a series of experiments on 7 real-world datasets, demonstrating our proposed method's superiority.

2 Prior Art

In recent years, GCNs have attracted significant attention as an effective tool to handle graph data. Early methods [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018] only use shallow networks since deeper networks lead to performance degradation, which is known as over-smoothing [Huang et al., 2020]. To solve this limitation, various methods are proposed [Xu et al., 2018; Liu and others, 2020; Liu and others, 2020; Chen et al., 2020]. See Appendix A for more details. In this work, we propose a motif-based GCN to overcome over-smoothing. Unlike previous work, our main idea is to improve the diversity of the graph spectrum by multiple message-passing paths of motifs.

3 Preliminaries

3.1 Learning from the Graph Structure

In this paper, we focus on the unweighted undirected graph G = {V, E}, where V = {v1, ..., vn} is the node set and E is the edge set defined on V. Let A ∈ {0, 1}n×n denote the adjacency matrix with Ai,j = Aj,i. Then, the degrees of the nodes are defined by d = {d1, ..., dn}, where di = ∑j̸=i Ai,j. The degree matrix is further defined as the diagonal matrix D with Di,i = di, i = 1, · · · , n. Meanwhile, let X ∈ Rn×h denote the feature matrix of the nodes, where h is the dimension of feature.

Our task is to capture the informative patterns hidden in the nodes and the graph structure. As a representative method, GCNs propagate the node features by the adjacency matrix of the original graph, leading to the following formulation [Kipf and Welling, 2017]:

where ˆA = A+ I; σ(·) is the activation function; H(l) and W (l) are the embeddings and the weight matrix of the layer l, respectively. However, as presented in the introduction, focusing on the Laplacian of the original graph will lead to the notorious over-smoothing. To eliminate this issue, we propose to exploit the local topological structure of the graph, with the help of a classic tool named Motif.

3.2 Motif as a Local Topology Indicator

According to [Benson et al., 2016], the motif is a kind of graph pattern, defined as any induced subgraph, which is small and non-isomorphic. One of the motifs with three nodes is shown in Figure 1. Compared with the global information in the original graph, motifs can capture local graph topologies more effectively. Consequently, we expect to introduce motifs into the GCN framework. To perform the calculations in GCN, we need to define the adjacency matrix for a given motif. To do this, [Windels and others, 2019] defines the adjacency matrix A′ as:

We observe that the elements in A′ exhibit a highly skewed distribution, where only a small number of edges in A′ have a large frequency while the others remain small. These edges will cover the information of other important edges. Therefore, in this paper, we define A′ as an indicator function:

4 Methodology

In this section, we formally present the proposed SMEGCN. In Section 4.1, we propose the Sparse-motif-based Message Passing mechanism. On top of this, the Hierarchical Motif Aggregation is established in Section 4.2.

4.1 Sparse-motif-basedMessage Passing

Sparse Motif. To begin with, we present the message passing with a single motif. The adjacency matrix corresponding to the k-th motif is denoted as Ak. Directly passing messages with Ak will suffer from spurious connections: since two disconnected nodes vi, vj might belong to one motif, Ak,i,j could be positive even if vi and vj are not adjacent. Fig.3 illustrates a typical example. With Spurious connections, ATk will rapidly evolve into an all-one matrix when applying T times message passing, which contradicts the target of capturing local information. Therefore, we propose a preprocessing method to transfer the motif adjacency matrix into a sparse motif matrix ˜Ak:

where ⊙ refers to element-wise multiplication. In other words, we can explain each entry in ˜Ak as: ˜Ak,i,j = 1 only if vi and vj are connected and co-occurs in at least one motif. Sparse-Motif-based Message Passing. Given the output feature H(l) k of the l-th layer, the propagation process is to pass the message from the l-th layer to the l+1-th layer. Existing message-passing techniques like GCNII [Chen et al.,

2020] and APPNP [Klicpera et al., 2018] could be applied here in a plug-and-play style. Here we apply the following formulation:

where σ is the activation function. In this way, the node features are passed to relevant nodes through the local topology of the k-th motif.

Spectrum of the Sparse-Motif-based Message Passing. By introducing the sparse motif, we can largely enrich the spectral information obtained from message passing. First, the bottom m eigenvalues of k-th motif's graph Laplacian Lk = I -D-1/2 ˜AkD-1/2 becomes:

Here tr (F ⊤∆kF ) is a dirichlet energy term:

where vi k∼ vj if and only if ˜ Ak,i,j = 1. Another crucial spectral information is M (see Definition 1): the null space of Lk, which is the linear space spanned by the eigenvectors of Lk associated with the eigenvalue 0 [Elsner and Tsonis, 1996]. According to the classical results in spectral graph theory, if the graph induced by ˜ Ak has connected components C1, C2, · · · , CM, then the basis ofMare:

where M is the number of eigenvalues; ICi ∈ RN×1 and ICij = 1 if node j belongs to Ci, otherwise ICij = 0. Above all, we see that both eigenvalues and the null space depend on k∼, which is a function of the local topology conveyed in the k-th sparse motif. Hence to improve the diversity of the graph spectrum, we propose to integrate spectral information from multiple sparse motifs, which is shown in the next subsection.

4.2 Hierarchical Motif Aggregation

Outline. An overview of our method is available in Figure 2. Given the feature matrix X of a graph, we pass it through two linear layers followed by ReLU activation units and obtain a feature matrix H(0) . Afterward, we perform propagation with the adjacency matrix for a few steps to obtain early features:

where 1 ≤ l < L0 and L0 is a hyperparameter. Then, we aggregate motif-based information by sparse motif-based message passing. Finally, local motif features and global features are integrated by our proposed hierarchical Motif Aggregation. Fig.2 presents a brief summary of the proposed network.

As we analyzed above, integrating information of multiple motifs is significant to the diversity of the graph spectrum. Therefore, we propose a hierarchical motif aggregation as follows.

After extracting the initial feature H(L0) we extract multiscale and multi-topological features based on H(L0) . Specifically, for the k-th motif, we initialize H(0) k withH(L0) , and perform motif-based message passing as in Eq. 3 for L1 times. In this way, we obtain two-level features: for a specific motif k, {H(l) k }L1 l=1 contains multiscale information; for a specific layer l, {H(l) k }Kk=1 contain multi-topological information. Therefore, we could aggregate the motif-based features with rich local information in an adaptive manner:

where w(l) k > 0 are learnable parameters.

Notice that ˜Ak only contains partial edges of the original graph, thus it might fail to capture global information. Therefore, only using motif-based features for prediction is far from enough. To this end, we propose to further aggregate global information with the adjacency matrix A. Specifically, we perform similar aggregation from H(L0) with the adjacency matrix A, and obtain {H(l) glo }L1 l=1 . These features are also aggregated with learnable parameters {w(l) glo }L1 l=1 > 0:

w(l) k and w(l) glo are normalized with the Softmax operation, such that ∑L1 l=1 ∑Kk=1 w(l) k + ∑L1 l=1 w(l) glo = 1.

Moreover, to further take low level information into consideration, the early features {H(l) }L0 l=1 mentioned in Eq. 4 are aggregated in the following manner:

where ∑L0 l=1 w(l) = 1.

Finally, the merged feature is a linear combination of these features:

5 Theoretical Analysis

In our proposed method, we claim that the over-smoothing issue could be mitigated by integrating multiple motif-based message-passing branches. In this section, we will present a theoretical analysis of the claim. According to [Huang et al., 2020], the over-smoothing issue could be mathematically expressed as the distance from the final output to the null space of the graph Laplacian matrix tends to 0 as the depth increases. Hence, we will prove that such distance would not vanish with the SMEGCN method.

For simplicity, we only consider motif features from one layer and omit the superscripts if there is no ambiguity. With the representation of the output of the motif path i and the corresponding weight wi, the aggregated result Hloc is obtained as follows:

where K is the number of motifs. Without loss of generality, we assume ∑Ki=1 wi = 1.

In such a manner, Hloc will integrate the spectral information from different motifs. To survive over-smoothing, we have to additionally require the spectrum of the motifs to exhibit a certain degree of diversity. First, we have to clarify the basic definitions of the null space of the graph Laplacian, which we call trivial subspace in this paper since it is only related to the connected components and nodes degrees [Huang et al., 2020]:

Definition 1 (Trivial Subspace). Given the normalized adjacency matrix ˆA, and the number of classes C, we define M := {H ∈ RN×C ∣∣H = ˆEC,C ∈ RM×C } as an M-dimensinal subspace in RN×C . ˆE = {ˆ e1, . . . , ˆ eM} ∈ RN×M denotes the collection of bases of the largest eigenvalue of ˆA. Then the subspace M is called the trivial subspace associated with ˆA. Moreover, the distance from matrix H ∈ RN×C to M is denoted as dM(H) := infY ∈M∥H-Y ∥F with the ∥·∥F being the Frobenius norm. DenoteMk as the subspace of the k-th motif.

Then we can define the diversity based on the distance.

Definition 2 (Diversity). For outputs Hi ∈ RN×C ( i ∈ [K]) from different motif paths, we define diversity as follows:

where Projk denotes the projection onMk and vec(·) denotes the vectorization of a matrix.

Intuitively, div is large when the outputs from two different motif paths are almost orthogonal. In the next proposition, we continue to show that the diversity will be large at a high probability under certain assumptions.

Proposition 1. Assuming that for any i ∈ [K], Hi is uniformly randomly sampled with a d-dimensional uniform distribution, if d is sufficiently large, we have:

where M = k(k - 1).

Following the above proposition, we see that div will be large with a high probability when N × C is large.

Assumption 1. We assume that div has a large lower bound with a small ε:

Now, we are ready to derive the distance from ˜H to subspace Mk .

Proposition 2. For ∀k ∈ [K], for the case of simplicity, we assume that ||Projk(vec(Hi))|| = 1, ∀i, k, then:

From Proposition 2, we can draw the final conclusion: By ensembling the motif spectrum, the final out will not converge to any trivial subspace and thus the over-smoothing problem is largely mitigated. See Appendix B for more detailed proof.

6 Experiments

In this section, we conduct comprehensive experiments on semi-supervised node classification to evaluate the effectiveness of SMEGCN.

6.1 Datasets

To validate the effectiveness of our proposed method across different application scenarios, we conduct experiments on seven datasets with various sizes, densities, and homophily.

The statistic of datasets is provided in Table 1. For a fair comparison, we follow the official data split. These datasets could be categorized into three types:

• Coauthorship graphs includes Coauthor CS and Coauthor Physics [Shchur et al., 2018]. In each graph, the node set consists of authors, while the edges are determined by whether two authors have co-authored. The features are the keywords of the authors' publications.
• Co-purchase graphs includes Amazon Computers and Amazon Photo [Shchur et al., 2018]. The node set consists of different goods, and two goods are connected by an edge if they are frequently bought together.
• Web networks graphs [Pei et al., 2020] includes Cornell, Texas and Wisconsin. The nodes in these graphs are webpages, and the edge set consists of hyperlinks connecting these webpages. The feature of each node is a bag-of-words representation of the webpage.

6.2 Competitors

To show the advantages of the proposed SMEGCN against the state-of-the-art methods, we compare our method with three categories of baselines:

• Naive methods including GCN [Kipf and Welling, 2017], the first work to use GCN for node classification, and GAT [Veliˇckovi´c et al., 2018], an attention-based spatial method.
• Initial residual methods including APPNP [Klicpera et al., 2018] and GCNII [Chen et al., 2020]. The main idea of these methods is to keep local information by adding the input to deeper features.
• Skip connection methdos including JKNet [Xu et al., 2018], GPRGNN [Chien et al., 2020] and DAGNN [Liu and others, 2020]. The key design of these methods is adding skip connection to aggregate multiscale information.

6.3 Implementation Details

Calculation of Motif. According to our preliminary experiments, neighbors within four hops are more useful. Therefore, eight kinds of motifs with no more than four nodes are chosen. See Appendix C for more details. The algorithm in [Ahmed et al., 2015] is used for counting node motifs.

(a) AmazonPhoto

(b) AmazonComputers

Training strategy. Our model and the competitors are trained by minimizing the cross-entropy loss with the Adam optimizer. Concretely, the initial learning rate is set to 0.01, and the weight decay factors for the first two linear layers are respectively taken from {0.00001, 0.00005, 0.005} and {0, 0.0005}. Other hyperparameters are tuned according to the performances on the validation sets. For our model, we add dropout layers with the probability searched from [0, 0.9] with an interval of 0.1. Hyperparameters of competitors are also tuned similarly. The models are trained for at most 1000 epochs. The checkpoint with the best performance on the validation set is preserved to evaluate the corresponding performance on the test set.

6.4 Quantitative Results

The main results are shown in Table 2. Each experiment is repeated 5 times, and the mean classification accuracy, and the standard deviation are reported as well. From Table 2, we could make the following observations: a) Our proposed method achieves state-of-the-art performance in all seven datasets, which validates the effectiveness of our method. b) In the webpage datasets TEXAS, WISCONSIN, CORNELL, the improvement is more significant. The reasons are two-fold: first, webpage datasets have higher heterophily, thus finer local information from motifs is required to ensure discriminability; second, these datasets are denser and more likely to suffer from over-smoothing, while the proposed method could overcome the over-smoothing. c) Although our improvements against the best baseline are not significant in all datasets, our results are consistent in these datasets, which shows that the aggregation with multiple motifs can adapt to graphs with various topologies.

6.5 Effect of the Model Depths

To validate the effect of our method against the oversmoothing issue, we continue to show the empirical result when the model depths keep increasing from 2 to 30. We find that the top-2 model, i.e. SMEGCN and APPNP significantly outperform the other competitors. Hence, we here only visualize the top-2 results in Fig.5. Taking Fig.5-(c) for example, the results show that our model performs poorly when the model is shallow. However, when the depth exceeds 10, we can observe a sharp performance improvement of our method so that SMEGCN outperforms APPNP when the depth is 10. Meanwhile, the performance of APPNP is rather stable in terms of depth and starts to reduce when the depth exceeds 10. Above all, we can clearly see the advantage of SMEGCN in terms of the over-smoothing issue.

7 Conclusion

In this paper, we consider the over-smoothing problem by exploring the diversity of the graph spectrum. Specifically, we introduce the local topology into the graph Laplacian by introducing the notion of the motif. We find that the motiflevel graph Laplacian is much denser than the original graph, which will lead to a trivial all-one matrix after even a few iterations of message-passing. Consequently, we propose the sparse motif to remove the irrelevant connections. Furthermore, we propose a hierarchical motif aggregation mechanism to integrate early global features, motif-level local features, and graph-level global features. Theoretically, we show that our proposed method will not lead to an over-smoothed representation if the diversity across motifs is large. Experimental results on 7 real-world datasets demonstrate the superiority of our method.

(d) CoauthorPhysics

Ethical Statement

There are no ethical issues.

Acknowledgments

This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, in part by National Natural Science Foundation of China: U21B2038, 61931008, 61836002, 6212200758 and 61976202, in part by the Fundamental Research Funds for the Central Universities, in part by Youth Innovation Promotion Association CAS, in part by the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDB28000000, in part by the National Postdoctoral Program for Innovative Talents under Grant BX2021298, and in part by mindspore, which is a new AI computing framework 2 .