Convolution acts as a local feature extractor in convolutional neural networks (CNNs). However, the convolution operation is not applicable when the input data is supported on an irregular graph such as with social networks, citation networks, or knowledge graphs. This paper proposes the topology adaptive graph convolutional network (TAGCN), a novel graph convolutional network that generalizes CNN architectures to graph-structured data and provides a systematic way to design a set of fixed-size learnable filters to perform convolutions on graphs. The topologies of these filters are adaptive to the topology of the graph when they scan the graph to perform convolution, replacing the square filter for the grid-structured data in traditional CNNs. The outputs are the weighted sum of these filters’ outputs, extraction of both vertex features and strength of correlation between vertices. It
 can be used with both directed and undirected graphs. The proposed TAGCN not only inherits the properties of convolutions in CNN for grid-structured data, but it is also consistent with convolution as defined in graph signal processing. Further, as no approximation to the convolution is needed, TAGCN exhibits better performance than existing graph-convolution-approximation methods on a number
 of data sets. As only the polynomials of degree two of the adjacency matrix are used, TAGCN is also computationally simpler than other recent methods. Convolutional neural network (CNN) architectures exhibit state-of-the-art performance on a variety of learning tasks dealing with 1D, 2D, and 3D grid-structured data such as acoustic signals, images, and videos, in which convolution serves as a feature extractor BID12 . However, the (usual) convolution operation is not applicable when applying CNN to data that is supported on an arbitrary graph rather than on a regular grid structure, since the number of neighbors of each vertex on the graph varies, and it is difficult to design a fixed-size filter scanning over the graph-structured data for feature extraction.Recently, there has been an increasing interest in graph CNNs (Bruna et al., 2014; BID3 BID10 BID13 , attempting to generalize deep learning methods to graph-structured data, specifically focusing on the design of graph CNN . In this paper, we propose the topology adaptive graph convolutional network (TAGCN), a unified convolutional neural network to learn nonlinear representations for the graph-structured data. It slides a set of fixed-size learnable filters on the graph simultaneously, and the output is the weighted sum of these filters' outputs, which extract both vertex features and strength of correlation between vertices. Each filter is adaptive to the topology of the local region on the graph where it is applied. TAGCN unifies filtering in both the spectrum and vertex domains; and applies to both directed and undirected graphs.In general, the existing graph CNNs can be grouped into two types: spectral domain techniques and vertex domain techniques. In Bruna et al. (2014) , CNNs have been generalized to graph-structured data, where convolution is achieved by a pointwise product in the spectrum domain according to the convolution theorem. Later, BID3 and BID13 proposed spectrum filtering based methods that utilize Chebyshev polynomials and Cayley polynomials, respectively. The assumption of symmetric adjacency matrix in these spectrum based methods restrict the application to undirected graphs. BID10 simplified this spectrum method and obtained a filter in the vertex domain, which achieves state-of-the-art performance. Other researchers BID0 worked on designing feature propagation models in the vertex domain for graph CNNs. BID22 ; BID2 ; Grover & Leskovec (2016) ; BID5 study transforming graph-structured data to embedding vectors for learning problems. Nevertheless, it still remains open how to extend CNNs from grid-structured data to arbitrary graph-structured data with local feature extraction capability. This paper proposes a modification to the graph convolution step in CNNs that is particularly relevant for graph structured data. Our proposed TAGCN is graph-based convolution and draws on techniques from graph signal processing. We define rigorously the graph convolution operation on the vertex domain as multiplication by polynomials of the graph adjacency matrix, which is consistent with the notion of convolution in graph signal processing. In graph signal processing, polynomials of the adjacency matrix are graph filters, extending to graph based data from the usual concept of filters in traditional time or image based signal processing. Thus, comparing ours with existing work on graph CNNs, our paper provides a solid theoretical foundation for our proposed convolution step instead of an ad-hoc approach to convolution in CNNs for graph structured data.Further, our method avoids computing the spectrum of the graph Laplacian as in Bruna et al. (2014) , or approximating the spectrum using high degree Chebyshev polynomials of the graph Laplacian matrix (in BID3 , it is suggested that one needs a 25 th degree Chebyshev polynomial to provide a good approximation to the graph Laplacian spectrum) or using high degree Cayley polynomials of the graph Laplacian matrix (in BID13 , 12 th degree Cayley polynomials are needed). We also clarify that the GCN method in BID10 is a first order approximation of the Chebyshev polynomials approximation in BID3 , which is very different from our method. Our method has a much lower computational complexity than the complexity of the methods proposed in Bruna et al. (2014) ; BID3 ; BID13 , since our method only uses polynomials of the adjacency matrix with maximum degree 2 as shown in our experiments. Finally, the method that we propose exhibits better performance than existing methods. Our contributions are summarized follows:• We propose a general K-localized filter for graph convolution in the vertex domain to extract local features on a set of size-1 up to size-K receptive fields. The topologies of these filters are adaptive to the topology of the graph as they scan the graph to perform convolution. It replaces the fixed square filters in traditional CNNs for the input gridstructured data volumes in traditional CNNs. Thus, our convolution definition that we use in the convolution step for the vertex domain is consistent with convolution in traditional CNNs.• TAGCN is based on the graph signal processing and it is consistent with the convolution in graph signal processing. It applies to both directed and undirected graphs. Moreover , it has a much lower computational complexity compared with recent methods since it only needs polynomials of the adjacency matrix with maximum degree 2 compared with the 25 th and 12 th degree Laplacian matrix polynomials in BID3 and BID13 .• As no approximation to the convolution is needed in TAGCN, it achieves better performance compared with existing methods. We contrast TAGCN with recently proposed graph CNN including both spectrum filtering methods (Bruna et al., 2014; BID3 and vertex domain propagation methods BID10 BID0 , evaluating their performances on three commonly used data sets for graph vertices classification. Our experimental tests show that TAGCN outperforms consistently all other approaches for each of these data sets. We have defined a novel graph convolutional network that rearchitects the CNN architecture for graph-structured data. The proposed method, known as TAGCN, is adaptive to the graph topology as the filter scans the graph. Further, TAGCN inherits properties of the convolutional layer in classical CNN, i.e., local feature extraction and weight sharing. It can further extract the strength of correlation between vertices in the filtering region. On the other hand, by the convolution theorem, TAGCN that implements in the vertex domain offers implement in the spectrum domain unifying graph CNN in both the spectrum domain and the vertex domain. TAGCN is consistent with convolution in graph signal processing. These nice properties lead to a noticeable performance advantage in classification accuracy on different graph-structured datasets for semi-supervised graph vertex classification problems with low computational complexity.
Low computational complexity graph CNN (without approximation) with better classification accuracy Proposes a new CNN approach to graph classification using a filter based on outgoing walks of increasing length to incorporate information from more distant vertices in one propagation step. Proposal for a new neural network architecture for semi-supervised graph classification, building upon graph polynomial filters and utilizing them on successive neural network layers with ReLU activation functions. The paper introduces Topology Adaptive GCN to generalize convolutional networks to graph-structured data