  In this paper, we develop a novel Backtrackless Aligned-Spatial Graph
Convolutional Network (BASGCN) model to learn effective features for graph
classification. Our idea is to transform arbitrary-sized graphs into
fixed-sized backtrackless aligned grid structures and define a new spatial
graph convolution operation associated with the grid structures. We show that
the proposed BASGCN model not only reduces the problems of information loss and
imprecise information representation arising in existing spatially-based Graph
Convolutional Network (GCN) models, but also bridges the theoretical gap
between traditional Convolutional Neural Network (CNN) models and
spatially-based GCN models. Furthermore, the proposed BASGCN model can both
adaptively discriminate the importance between specified vertices during the
convolution process and reduce the notorious tottering problem of existing
spatially-based GCNs related to the Weisfeiler-Lehman algorithm, explaining the
effectiveness of the proposed model. Experiments on standard graph datasets
demonstrate the effectiveness of the proposed model.
