Most of the existing Graph Neural Networks (GNNs) are the mere extension of the Convolutional Neural Networks (CNNs) to graphs. Generally, they consist of several steps of message passing between the nodes followed by a global indiscriminate feature pooling function. In many data-sets, however, the nodes are unlabeled or their labels provide no information about the similarity between the nodes and the locations of the nodes in the graph. Accordingly, message passing may not propagate helpful information throughout the graph. We show that this conventional approach can fail to learn to perform even simple graph classification tasks. We alleviate this serious shortcoming of the GNNs by making them a two step method. In the first of the proposed approach, a graph embedding algorithm is utilized to obtain a continuous feature vector for each node of the graph. The embedding algorithm represents the graph as a point-cloud in the embedding space. In the second step, the GNN is applied to the point-cloud representation of the graph provided by the embedding method. The GNN learns to perform the given task by inferring the topological structure of the graph encoded in the spatial distribution of the embedded vectors. In addition, we extend the proposed approach to the graph clustering problem and a new architecture for graph clustering is proposed. Moreover, the spatial representation of the graph is utilized to design a graph pooling algorithm. We turn the problem of graph down-sampling into a column sampling problem, i.e., the sampling algorithm selects a subset of the nodes whose feature vectors preserve the spatial distribution of all the feature vectors. We apply the proposed approach to several popular benchmark data-sets and it is shown that the proposed geometrical approach strongly improves the state-of-the-art result for several data-sets. For instance, for the PTC data-set, we improve the state-of-the-art result for more than 22 %. Many of the modern data/signals are naturally represented by graphs BID2 BID5 BID4 BID31 and it is of great interest to design data analysis algorithms which can work directly with graphs. Due to the remarkable success of deep learning based methods in many machine learning applications, it is an attractive research problem to design new neural network architectures which can make the deep networks able to work with graphs. The adjacency matrix of a graph exhibits the local connectivity of the nodes. Thus, it is straightforward to extend the local feature aggregation in the Convolutional Neural Networks (CNNs) to the Graph Neural Networks (GNNs) BID34 BID38 BID0 BID28 BID3 BID11 . The local feature aggregation in the graphs is equivalent to message passing between the nodes BID38 BID12 . However, if the graph is not labeled (the nodes/edges do not have feature vectors) or the feature vectors of the nodes do not carry information about the similarities between the nodes or any information about their structural role, the message passing may not propagate informative features throughout the graph. Thus, the GNN can fail to infer the topological structure of the graph. Another limitation of the current GNN architectures is that they are mostly unable to do the hierarchical feature learning employed in the CNNs BID26 BID19 . The main reason is that graphs lack the tensor representation and it is hard to measure how accurate a subset of nodes represent the topological structure of the given graph. In this paper, we address these two shortcomings of the GNNs.In the proposed approach, we provide a spatial representation of the graph to the GNN. The spatial representation makes the network aware of the similarity/difference between the nodes and also the location of the nodes in the graph. Accordingly, the local feature aggregation can propagate informative messages throughout the graph. In addition, we propose a down-sampling method to perform graph pooling. The proposed node sampling approach measures the similarities between the nodes in the spatial domain and merges the closest pairs of nodes. The main contributions of the proposed approach can be summarized as follows:• It is shown that the existing GNNs lack the important embedding step. The proposed approach enhances the capability of the GNNs in inferring the topological structure of the graphs.• A new graph pooling method is proposed which can be implemented in any GNN. The proposed pooling method preserves the spatial representation of the graph by merging the closest pairs of nodes in the spatial domain.• To the best of our knowledge, the proposed approach advances the state-of-the-art results for 5 established benchmark data-sets. For instance, the improvement in accuracy with the PTC data-set is more than 22 %.• An architecture for graph clustering is presented. In contrary to the conventional GNNs which can not be trained to cluster unlabeled graphs, the proposed approach utilizes the geometrical representation of the graph to infer the structure of the graph. We pointed this important fact out that the GNNs which are the mere extension of the CNNs to graphs may not be able to infer the structure of the graphs. In the proposed approach, the GNN analyzes a spatial representation of the graph provided by the embedding step. In other word, the graph data analysis problem is translated into a point-cloud data analysis problem. We also extended the proposed approach to a graph clustering method. In addition, we addressed one of the challenges of extending the architecture of the CNNs to graphs by proposing a graph pooling method. The proposed pooling method merges the closest pairs of nodes in the spatial domain. We showed that the proposed approach outperforms most of the existing graph classification methods. For instance, for the PTC data-set the proposed approach advances the state-of-the-art result for more than 22 %.
The graph analysis problem is transformed into a point cloud analysis problem.  Proposes a deep GNN network for graph classification problems using their adaptive graph pooling layer. The authors propose a method for learning representations for graphs