Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification

Lu Bai, Lixin Cui, Yuhang Jiao, Luca Rossi, Edwin R. Hancock

Research output: Journal article publicationJournal articleAcademic researchpeer-review

43 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)783-798
Number of pages16
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number2
Publication statusPublished - 1 Feb 2022
Externally publishedYes


  • backtrackless walk
  • Graph convolutional networks
  • transitive vertex alignment

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification'. Together they form a unique fingerprint.

Cite this