In colored graphs, node classes are often associated with either their neighbors class or with information not incorporated in the graph associated with each node. We here propose that node classes are also associated with topological features of the nodes. We use this association to improve Graph machine learning in general and specifically, Graph Convolutional Networks (GCN). 

 First, we show that even in the absence of any external information on nodes, a good accuracy can be obtained on the prediction of the node class using either topological features, or using the neighbors class as an input to a GCN. This accuracy is slightly less than the one that can be obtained using content based GCN.

 Secondly, we show that explicitly adding the topology as an input to the GCN does not improve the accuracy when combined with external information on nodes. However,  adding an additional adjacency matrix with edges between distant nodes with similar topology to the GCN does significantly improve its accuracy, leading to results better than all state of the art methods in multiple datasets. One of the central assumptions in node classification tasks is that neighboring nodes have similar classes (Ji & Han, 2012; Berberidis & Giannakis, 2018; Zhu et al., 2003b; Sindhwani et al., 2005) . This has been extensively used in node classification tasks (Belkin & Niyogi, 2004; Zhu et al., 2003a) . Such approaches are now often denoted as graph neural networks (i.e. machine learning where the input is a graph/network) (Scarselli et al., 2008; Gori et al., 2005; Li et al., 2015) . Four main approaches have been proposed to take advantage of a graph in machine learning: • Regularize the output requiring that neighboring nodes either in the graph or in its projection have similar classes. • Use the graph to propagate labels and learn the best propagation. • Use the graph to project the nodes to real valued vectors and use those for supervised or unsupervised learning. • Use Graph Convolutional Networks (GCN) for convolutions on the input of a node and its neighbors. Regularization or graph partitioning methods include among others partitioning the graphs based on the eigenvalues of the Laplacian (assuming that nodes with the same partition have similar classes). The Laplacian of a graph is : L = D −A , where D is a diagonal matrix, with the sum of each row in the diagonal and A is the adjacency matrix. This Laplacian is often weighted by multiplying it on the left and the right by D to normalize for the degree (Dhillon et al., 2007; Karypis & Kumar, 1995) . Other works have used variants of this idea, each using smoothness and graph distance differently (Belkin & Niyogi, 2004; Sindhwani et al., 2005) . An alternative approach is to use quadratic penalty with fixed labels for seed nodes (Zhou et al., 2004; Zhu et al., 2003a) . Multiple diffusion and information propagation models have also been proposed either through explicit diffusion, or through the projection of nodes into real valued vectors (Rosenfeld & Globerson, 2017) . For example, DeepWalk (Perozzi et al., 2014) , where a truncated random walk is performed on nodes. It then uses these sentences as an input to skipgram to compute a projection of each word into R N , maximizing the sentence probability. Planetoid Yang et al. (2016) also uses random walks combined with negative sampling. Duvenaud et al. (2015) uses a translation of subgraphs to hash functions for a similar task in the context of molecule classifications. A very similar approach was presented by Grover & Leskovec (2016) (Node2Vec) by projecting nodes minimizing the distance of neighbored nodes in a truncated random walk. The DNGR model (Cao et al., 2016) uses random walk to compute the mutual information between points (the PPMI-positive pointwise mutual information), and then a SVD decomposition to project into space. PPMI was used for word representations in Levy et al. (2015) and is a sparse high dimensional representation. Another possible approach is the projection of the graph (often using the Laplacian eigenvectors), and the usage of the projection for classification (and not only for a smoothness based regularization), where either the graph itself is used (in such a case, the eigenvectors themselves are used) or an input to the graph is used. In such a case, a convolution with these eigenvectors was used (Masci et al., 2015; Monti et al., 2017) . A Multi-Dimensional-Scaling (MDS) projection of the points in the graphs was also used for a similar goal (Belkin & Niyogi, 2002; Levy et al., 2015) . Alternative approaches were inspired again by word embedding methods (Mikolov et al., 2013) such as word2vec. These methods use the graph to define a context in relation to which the node embedding is constructed. When the data includes only the graph, the embeddings are used as features and fed into existing predictors (Perozzi et al., 2014) . These methods can be thought of as propagating features rather than labels. Henderson et al. (2011) defines local features to translate each node to a features vector and use those to predict classes. Recently, Kipfs and collaborators, in a seminal work, proposed a simplification of spectral based convolutions (Kipf & Welling, 2016; Schlichtkrull et al., 2018) , and instead use a two-layer approach, which can be summarized as: whereÃ is a normalized adjacency matrix: They test their work on multiple graphs with labeled nodes including CiteSeer, Cora, Pubmed, and Nell. Convolution approaches can also be used with the graph as a filter on the input. Most such convolutions are spectral (use the Laplacian eigenvectors). However, recent methods are based on random filters. Those include among others: Atwood & Towsley (2016) which defines predetermined convolutions with powers of the adjacency matrix and then combines these powers using learned weights to maximize the classification precision of either the full graph or the classification of nodes. Bruna et al. (2013) provide a multi-level graph convolution with pooling, where at each stage nodes are merged into clusters using agglomerative clustering methods, and combine it with a pooling method to represent the different resolution of images. This has been extended (Henaff et al., 2015; to different convolutional kernels (mainly spectral, but also diffusion-based kernels) and the classification of images, using ImageNet (see for a detailed review of all convolution methods). Vandergheynst and collaborators mainly use polynomial convolution in the spectral domain. Similar formalisms were used to study not only single snapshots, but also with recurrent networks time series of graphs, mainly again in image analysis (Seo et al., 2018) . Over the last 3 years, over 1,500 extensions and applications of GCN have been published in combination with many other learning methods, including among many others combinations of GCN with recurrent neural networks (Ling et al., 2019) , with GANs (Lei et al., 2019) and with active learning (Abel & Louzoun, 2019) . GCNs capture dependencies of nodes' features. However, current techniques consider only local neighborhoods. Thus, long-range dependencies can only be captured when these operations are applied repeatedly, propagating signals progressively through the data. To catch long-range dependencies, Kipf & Welling (2016) proposed stacking multiple layers of GCN. While this is possible in theory, it has never been successfully applied. In practice, GCN models work the best with 2-3 layers (Kipf & Welling, 2016; Monti et al., 2017; Veličković et al., 2017; Levie et al., 2018; Fey et al., 2018) . Abu-El-Haija et al. (2018) proposed using NGCN train multiple instances of GCNs over different distances regions. While this led to good performance, it is highly inefficient and does not scale to long distances (as the number of models scales linearly with the desired length). However, long range correlations can be obtained from a different direction. Recently, a correlation has been shown between the topological attributes (e.g. degree, centrality, clustering coefficient...) of nodes and their class (Shi & Malik, 2000; Yang et al., 2013; Cannistraci et al., 2013; Rosen & Louzoun, 2015; Naaman et al., 2018) . Inspired by the improvement of non-local operations in a variety of tasks in the field of computer vision Wang et al. (2018) , we propose a novel non-local operation for GCN, based on the topology of the graph. Our operation is generic and can be implemented with every GCN to capture long-range dependencies, allowing information propagation to distant nodes. There are several advantages of using non-local operations: (a) In contrast to the standard local convolution layer, non-local operations capture long-range dependencies directly by computing interactions between any two nodes, regardless of their positional distance; (b) As we show in experiments, non-local operations are efficient and achieve their best results even with only a few layers; (c) Finally, our non-local convolution can be easily combined with other graph convolution techniques (e.g. GCN, GAT). Convolution methods to aggregate information from multiple distances are among the leading image classification methods. In images, most of these convolutions are symmetric and sometimes isotropic around each point. However, in contrast with images that are typically overlaid on a 2D lattice, graphs have a complex topology. This topology is highly informative of the properties of nodes and edges (Rosen & Louzoun, 2015; Naaman et al., 2018) , and can thus be used to classify their classes. This complex topology can be combined with convolutional networks to improve their accuracy. In undirected graphs, the topology can often be captured by a distance maintaining projection into R N , using unsupervised methods, such as the classical MDS (Kruskal, 1964), or supervised methods to minimize the distance between nodes with similar classes in the training set (Cao et al., 2016) . In directed graphs, a more complex topology emerges from the asymmetry between incoming and outgoing edges (i.e., the distance between node i and node j differs from the distance between node j and node i), creating a distribution of subgraphs around each node often denoted sub-graph motifs (Milo et al., 2002) . Such motifs have been reported to be associated with both single node/edge attributes as well as whole-graph attributes (Milo et al., 2002) . We have here shown that in a manuscript assignment task, the topology around each node is indeed associated with the manuscript class. In order to combine topological information with information propagation, we proposed a novel GCN where the fraction of second neighbors belonging to each class is used as an input, and the class of the node is compared to the softmax output of the node. This method can indeed produce a high classification accuracy, but less than the one obtained using a BOW input. Moreover, explicitly combining the topology as an input with the BOW reduces the accuracy. However, using the topology to add new edges between nodes with similar topological features actually significantly improves performance in most studied datasets. This suggests that the topology is better used to correlate between the class of distant nodes than to be actually used as an input. The results presented here are a combination of information propagation and topology-based classification. While each of these two elements was previously reported, their combination into a single coherent GCN based classifier provides a novel content independent method to classify nodes. With the current ever-increasing concerns about privacy, new content independent methods for node classification become essential. The citation networks contain scientific papers divided into classes by their research field. Edges describe citations in the data set. BOW is also available to describe each publication in the dataset. BOW can be either a 1/0 vector or a TF/IDF weighted word vector for PubMed. Coauthor CS and Coauthor Physics are co-authorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 challenge 3. Here, nodes are authors, that are connected by an edge if they co-authored a paper, node features represent paper keywords for each authors papers, and class labels indicate the most active fields of study for each author. Here are the parameters used for each of the models. For T-GCN and T-GAT the parameters were optimized for PubMed ( as observed by Monti et al. (2017) and Veličković et al. (2017) ) except for Cora data for set which we used slightly different parameters (denotes as T-GCN Cora, and T-GAT Cora). The parameters are summarized in Table 3 . In all models, the activation function of the last layer is Softmax. The activation function of the first layer is presented In Table 3 . Hidden size X+Y means size of X for the original GCN operator and Y for the GCN on the dual graph. The two outputs are concatenated to a total of X+Y size. GAT heads X,Y,Z means X heads for the original GAT operator, and Y heads for the GAT on the dual graph. Z is the number of heads in the last layer. See Models And Data for more details.
Topology-Based Graph Convolutional Network (GCN)
{"src": "scitldr-AIC_train", "paper_id": "ryey1TNKvH"}