Learning High-Order Graph Convolutional Networks via Adaptive Layerwise Aggregation Combination

Graph convolutional networks have attracted wide attention for their expressiveness and empirical success on graph-structured data. However, deeper graph convolutional networks with access to more information can often perform worse because their low-order Chebyshev polynomial approximation cannot learn adaptive and structure-aware representations. To solve this problem, many high-order graph convolution schemes have been proposed. In this article, we study the reason why high-order schemes have the ability to learn structure-aware representations. We first prove that these high-order schemes are generalized Weisfeiler-Lehman (WL) algorithm and conduct spectral analysis on these schemes to show that they correspond to polynomial filters in the graph spectral domain. Based on our analysis, we point out twofold limitations of existing high-order models: 1) lack mechanisms to generate individual feature combinations for each node and 2) fail to properly model the relationship between information from different distances. To enable a node-specific combination scheme and capture this interdistance relationship for each node efficiently, we propose a new adaptive feature combination method inspired by the squeeze-and-excitation module that can recalibrate features from different distances by explicitly modeling interdependencies between them. Theoretical analysis shows that models with our new approach can effectively learn structure-aware representations, and extensive experimental results show that our new approach can achieve significant performance gain compared with other high-order schemes.