[Tutorial Learning On Graphs Conference] Graph Rewiring: From Theory to Applications in Fairness

Abstract

Graph Neural Networks (GNNs) have been shown to achieve competitive results to tackle graph-related tasks, such as node and graph classification, link prediction and node and graph clustering in a variety of domains. Most GNNs use a message passing framework and hence are called MPNNs. Despite their promising results, MPNNs have been reported to suffer from over-smoothing, over-squashing and under-reaching. Graph rewiring and graph pooling have been proposed in the literature as solutions to address these limitations. Many graph rewiring methods rely on edge sampling strategies: first, the edges are assigned new weights according to a relevance function and then they are re-sampled according to the new weights to retain the most relevant edges (i.e. those with larger weights). Edge relevance might be computed in different ways, including randomly, based on similarity or on the edge’s curvature. This tutorial provides an overview of the most relevant techniques proposed in the literature for graph rewiring based on diffusion, curvature or spectral concepts. It will explain their relationship and will present the most relevant state-of-the-art techniques and their application to different domains. The tutorial will outline open questions in this field, both from a theoretical and ethical perspective. The tutorial will end with a panel which will give the opportunity to attendees to engage in a discussion with a diverse set scientists with different technical perspectives, levels of seniority, and institutional and geographic affiliations.

Adrián Arnaiz-Rodríguez

Artificial Intelligence PhD Student

ELLIS PhD Student in Algorithmic Fairness and Graph Neural Networks at ELLIS Alicante.