Apprentissage de la Représentation des Graphes : des Noyaux aux Réseaux Neuronaux
Changmin Wu · HAL (Le Centre pour la Communication Scientifique Directe) · 2021
Graphs are ubiquitous as most real-world data can be naturally represented in the form of graphs. Capturing information from graph-structured data, i.e. graph mining or graph representation learning, has thus long become and remains an important topic. In this dissertation, we present a series of research contributions on subjects of machine learning on graphs using kernel methods and the emerging graph neural networks (GNNs).In the first part, we present a novel framework for constructing a valid optimal assignment graph kernel that computes the similarity between two graphs by computing a correspondence of their node embeddings residing in the same space. Using a clustering algorithm, we construct a hierarchy of the vertices in this space, through which the proposed kernel can find an optimal matching of the vertices that maximises the overall similarity of all the pairs. This framework is not limited to graphs. It can be used to compare any objects that are set of vectors. Moreover, the kernel feature map is a more expressive node embedding than the original embedding methods. We demonstrate the efficiency of the proposed kernel empirically on graph classification, link prediction and text categorisation tasks.The second part of this dissertation is devoted to the GNNs, particularly the Message-Passing Neural Networks (MPNNs), a dominating class of GNNs. As an emerging model, the MPNN soon became a leading tool for graph representation learning, mainly due to its power of projecting attributed graphs into high-level embeddings, making it versatile to different types of graphs and different application areas.We first demonstrate the power of MPNNs by an application in the field of temporal networks. We tackle the evolution prediction of dynamic graphs by proposing a sequential framework. Precisely, we use MPNNs to encode the sequence of evolving graphs into a sequence of embeddings in a latent space correlated by time. A recurrent architecture then generates the prediction of embedding at the next timestep. Finally, a generative model is employed to re-construct the graph instance corresponding to that prediction of embedding in the latent space. GNNs significantly improve the performance against traditional models such as random graph models on predicting the topology of evolving graphs.The following two works move closer to the fundamentals of MPNNs by addressing their limitations in terms of computational cost and robustness against structural noise. We notice that the MPNN can be divided into two disjoint steps: one is related to the graph structure, namely the aggregation step, and the other only concerns node features, namely the update step. Through extensive experiments, we found that the update step seems to play a less important role in model performance, as it can be substantially simplified by sparsifying, or in some cases, even omitting the whole, as long as the non-linear activation stays.This finding indicates that the MPNN might be vulnerable to graph-structural noise. Indeed, if the main contribution to model performance comes from the aggregation step, then the impact of structural noise would also be amplified. This work proposes a theoretical model based on random matrix theory to analyse the interaction between graph structure information and node feature information, precisely when graph structure is heavily perturbed. The main result is that graph structural noise will heavily overshadow node feature information. When a graph is structurally perturbed enough, node feature information will have no contribution to model performance, even itself might be informative. This theoretical finding inspires us to robustify MPNNs against graph structural noise with a node feature kernel. Empirical evaluations show the effectiveness of our proposed kernel as it improves the model performance significantly when the graph structure is heavily perturbed.