# Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks

arXiv: https://arxiv.org/abs/1906.02174 · HTML: https://mlsanity.com/paper/1906.02174/

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2019.

## Built on by (most cited first, 30 of 62)

- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods](https://mlsanity.com/paper/2111.04840/) (2021)
- [A Fractional Graph Laplacian Approach to Oversmoothing](https://mlsanity.com/paper/2305.13084/) (2023)
- [MUDiff: Unified Diffusion for Complete Molecule Generation](https://mlsanity.com/paper/2304.14621/) (2023)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study](https://mlsanity.com/paper/2108.10521/) (2021)
- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [Scalable deeper graph neural networks for high-performance materials property prediction](https://mlsanity.com/paper/2109.12283/) (2021)
- [Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networks](https://mlsanity.com/paper/2212.10822/) (2022)
- [Affinity-Aware Graph Networks](https://mlsanity.com/paper/2206.11941/) (2022)
- [Beyond Low-pass Filtering: Graph Convolutional Networks with Automatic Filtering](https://mlsanity.com/paper/2107.04755/) (2021)
- [Skeleton-based Action Recognition via Temporal-Channel Aggregation](https://mlsanity.com/paper/2205.15936/) (2022)
- [Learnable Filters for Geometric Scattering Modules](https://mlsanity.com/paper/2208.07458/) (2022)
- [What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks](https://mlsanity.com/paper/2406.18854/) (2024)
- [MGC: A Complex-Valued Graph Convolutional Network for Directed Graphs](https://mlsanity.com/paper/2110.07570/) (2021)
- [Neighborhood Homophily-based Graph Convolutional Network](https://mlsanity.com/paper/2301.09851/) (2023)
- [When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability](https://mlsanity.com/paper/2304.14274/) (2023)
- [Search For Deep Graph Neural Networks](https://mlsanity.com/paper/2109.10047/) (2021)
- [Graph Neural Networks Intersect Probabilistic Graphical Models: A Survey](https://mlsanity.com/paper/2206.06089/) (2022)
- [Representation Learning on Heterophilic Graph with Directional Neighborhood Attention](https://mlsanity.com/paper/2403.01475/) (2024)
- [Clarify Confused Nodes via Separated Learning](https://mlsanity.com/paper/2306.02285/) (2023)
- [GCEPNet: Graph Convolution-Enhanced Expectation Propagation for Massive MIMO Detection](https://mlsanity.com/paper/2404.14886/) (2024)
- [Spatio-Temporal Dual Graph Neural Networks for Travel Time Estimation](https://mlsanity.com/paper/2105.13591/) (2021)
- [Multitask Weakly Supervised Learning for Origin Destination Travel Time Estimation](https://mlsanity.com/paper/2301.05336/) (2023)
- [Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning](https://mlsanity.com/paper/2409.05755/) (2024)

## Abstract (arXiv)

Recently, neural network based approaches have achieved significant improvement for solving large, complex, graph-structured problems. However, their bottlenecks still need to be addressed, and the advantages of multi-scale information and deep architectures have not been sufficiently exploited. In this paper, we theoretically analyze how existing Graph Convolutional Networks (GCNs) have limited expressive power due to the constraint of the activation functions and their architectures. We generalize spectral graph convolution and deep GCN in block Krylov subspace forms and devise two architectures, both with the potential to be scaled deeper but each making use of the multi-scale information in different ways. We further show that the equivalence of these two architectures can be established under certain conditions. On several node classification tasks, with or without the help of validation, the two new architectures achieve better performance compared to many state-of-the-art methods.