Study of semi-supervised classification algorithms on a graph, based on convolutional neural networks and kernels on graph

Graph-structured data appear in various fields, such as social networks, the World-Wide-Web, citation networks, etc. Being able to exploit the information contained in the relations linking the entities can prove to be effective for classification tasks. Dealing with graph-structured data requires both adapting traditional models (exploiting only features on nodes) and relying on the spatial autocorrelation hypothesis in which strongly interconnected and close nodes tend to look alike. Kernels on graph (measure of similarity between nodes) allow to define low-dimensional graph representations while preserving in a certain sense the graph structure. This new representation can then be injected as additional features in many machine learning algorithms (e.g: SVM). Other techniques such as the AutoSVM based on autocovariates and the Diffusion Convolutional Neural Network (DCNN) allow to directly exploit the graph structure. Our work focuses on the comparison of two classes of algorithms, namely, the SVM-based models (relying on kernels extracted from the graph and autocovariates) and the DCNN-based models (relying on the DCNN where some modifications are explored). Due to the great success of deep learning in a wide variety of tasks, we were interested in assessing whether more traditional methods (such as the SVM-based models) are still relevant today on the node classification task. Our experiences were based on 10 well-known datasets and revealed that the model performance strongly depends on the hypothesis mentioned above. However, in general, the AutoSVM seems to be a good compromise in terms of performance and scalability.