LANCZOSNET: MULTI-SCALE DEEP GRAPH CONVO- LUTIONAL NETWORKS
We propose the Lanczos network (LanczosNet), which uses the Lanczos algorithm to construct low rank approximations of the graph Laplacian for graph convolution. Relying on the tridiagonal decomposition of the Lanczos algorithm, we not only efficiently exploit multi-scale information via fast approximated computation of matrix power but also design learnable spectral filters. Being fully differentiable, LanczosNet facilitates both graph kernel learning as well as learning node embeddings. We show the connection between our LanczosNet and graph based manifold learning methods, especially the diffusion maps. We benchmark our model against several recent deep graph networks on citation networks and QM8 quantum chemistry dataset. Experimental results show that our model achieves the state-of-the-art performance in most tasks.
This paper proposes to use a Lanczos alogrithm, to get approximate decompositions of the graph Laplacian, which would facilitate the computation and learning of spectral features in graph convnets. It further proposes an extension with back propagation through the Lanczos algorithm, in order to train end to end models. 
Overall, the idea of using Lanczos algorithm to bypass the computation of the eigendecomposition, and thus simplify filtering operations in graph signal processing is not new [e.g., 35]. However, using this algorithm in the framework of graph convents is new, and certainly interesting. The authors seem to claim that their method permits to learn spectral filters, what other methods could not do - this is not completely true and should probably be rephrased more clearly: many graph convnets, actually learn features. 
The general construction and presentation of the algorithms are generally clear, and pretty complete. A few things that could be clarified are the following:
- in the spectral filters of Eq (4), what gets fundamentally different from polynomial filters proposed in other graph convnets architectures?
- what happens when the graph change? Do the learned features make sense on different graphs? And if yes, why? If not, the authors should be more explicit in their presentation
- what is the complexity of the proposed methods? that should be minimally discussed (at least), as it is part of the key motivations for the proposed algorithms
- how is the learning done in 3.2? If there is any learning at all? (btw, S below Eq (6) is a poor notation choice, as S is used earlier for something else)
- the results are not very impressive - they are good, but not stellar, and could benefit from showing an explicit tradeoff in terms of complexity too?
The discussion in the related work, and the analogy with manifold learning are interesting. However, that brings probably to one of the main issues with the papers - the authors are obviously very knowledgeable in graph convnets, graph signal processing, and optimisation. However, there are really too many things in this paper, which leads to numerous shortcuts, and some time confusion. Given the page limits, not everything can be treated with the level of details that it would deserve. It might be good to consider trimming down the paper to its main and core aspects for the next version.