The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely-connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach on spectral image classification, community detection, vertex classification and matrix completion tasks.
Summary: This paper proposes a new graph-convolution architecture, based on Cayley transform of the matrix. Succinctly, if L denotes the Laplacian of a graph, this filter corresponds to an operator that is a low degree polynomial of C(L) = (hL - i)/(hL+i), where h is a scalar and i denotes sqrt(-1). The authors contend that such filters are interesting because they can 'zoom' into a part of the spectrum, depending on the choice of h, and that C(L) is always a rotation matrix with eigenvalues with magnitude 1. The authors propose to compute them using Jacobi iteration (using the diagonal as a preconditioner), and present experimental results.
Opinion: Though the Cayley filters seem to have interesting properties,  I find the authors theoretical and experimental justification insufficient to conclude that they offer sufficient advantage over existing methods. I list my major criticisms below:
1. The comparison to Chebyshev filters  (small degree polynomials in the Chebyshev basis) at several places is unconvincing. The results on CORA (Fig 5a) compare filters with the same order, though Cayley filters have twice the number of variables for the same order as Chebyshev filters. Similarly for Fig 1, order 3 Cayley should be compared to Order 6 Chebyshev (roughly).
2. Since Chebyshev polynomials blow up exponentially when applied to values larger than 1, applying Chebyshev filters to unnormalized Laplacians (Fig 5b) is an unfair comparison.
3. The authors basically apply Jacobi iteration (gradient descent using a diagonal preconditioner) to estimate the Cayley filters, and contend that a constant number of iterations of Jacobi are sufficient. This ignores the fact that their convergence rate scales quadratically in h and the max-degree of the graph. Moreover, this means that the Filter is effectively a low degree polynomial in (D^(-1)A)^K, where A is the adjacency matrix of the graph, and K is the number of Jacobi iterations. It's unclear how (or why) a choice of K might be good, or why does it make sense to throw away all powers of D^(-1)Af, even though we're computing all of them.
Also, note that this means a K-fold increase in the runtime for each evaluation of the network, compared to the Chebyshev filter.
Among the other experimental results, the synthetic results do clearly convey a significant advantage at least over Chebyshev filters with the same number of parameters. The CORA results (table 2) do convey a small but clear advantage. The MNIST result seems a tie, and the comparison for MovieLens doesn't make it obvious that the number of parameters is the same. 
Overall, this leads me to conclude that the paper presents insufficient justification to conclude that Cayley filters offer a significant advantage over existing work.