Graph Rewiring

Abstract

Neural networks have proven to be a powerful tool for solving a wide range of problems in areas such as computer vision, natural language processing, and machine learning in general. However, most neural network architectures have been developed to work with vectorized data such as images and sequences, eluding the treatment of data such as graphs or point clouds. Graphs are ideal for modeling complex relationships between entities. Many applications rely on graphs, such as social networks, product recommendations, or bioinformatics. Due to the non-vectorial nature of graphs, their processing presents unique and challenging problems in machine learning. In recent years, there has been a growing trend in deep learning techniques for graphs. These techniques use neural networks to process graphs directly, using vector (latent) representations of nodes and edges. This leads to an emerging field of research known as Graph Neural Networks. Throughout this Master’s Thesis, we will explore the most common architectures for Graph Neural Networks and the problems that these architectures face, mainly the over-smoothing issue. Finally, we will propose a new metric and method based on Spectral Graph Theory, Dirichlet energies and Graph Rewiring to achieve competitive results in semi-supervised node classification.