A Dual Approach to Graph CNNs

Convolutional neural networks (CNNs) have been very successful with learning on grid-based data such as time series and images. However, traditional CNNs do not perform well on irregular-structured data defined on a graph. Graph convolutional neural networks (graph CNNs) define convolutional layers using graph signal processing (GSP) concepts. They perform well on data defined on a graph such as citation networks and NYC taxi pickup data. Polynomial filter graph CNNs use a polynomial of the graph adjacency matrix A in the convolutional layer. However, they have been shown to fail on graph classification problems when the convolutional layer produces the same output for non-isomorphic graphs and identical graph signals. Recently, a spectral domain shift, M, has been proposed in GSP as the dual to the vertex domain shift and adjacency matrix, A. This has led to a spectral domain theory, dual to the existing vertex domain theory. In this paper, we redefine and dualize the convolutional layer for graph CNNs using M in the spectral domain. In doing so, we solve the problem of graph CNNs failing when applied to certain graph inputs. We show theoretically and experimentally the advantages of our solution on both synthetic and real datasets.