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

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

Xuan Jiang, Zhiyong Yang, Peisong Wen, Li Su, Qingming Huang

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 2094-2100. https://doi.org/10.24963/ijcai.2022/291

The over-smoothing issue is a well-known challenge for Graph Convolutional Networks (GCN). Specifically, it is often observed that increasing the depth of GCN ends up in a trivial embedding subspace where the difference among node embeddings belonging to the same cluster tends to vanish. This paper believes that the main cause lies in the limited diversity along the message passing pipeline. Inspired by this, we propose a Sparse-Motif Ensemble Graph Convolutional Network (SMEGCN). We argue that merely employing the original graph Laplacian as the spectrum of the graph cannot capture the diversified local structure of complex graphs. Hence, to improve the diversity of the graph spectrum, we introduce local topological structures of complex graphs into GCN by employing the so-called graph motifs or the small network subgraphs. Moreover, we find that the motif connections are much denser than the edge connections, which might converge to an all-one matrix within a few times of message-passing. To fix this, we first propose the notion of sparse motif to avoid spurious motif connections. Subsequently, we propose a hierarchical motif aggregation mechanism to integrate the graph spectral information from a series of different sparse-motif message passing paths. Finally, we conduct a series of theoretical and experimental analyses to demonstrate the superiority of the proposed method.
Keywords:
Data Mining: Networks