# Tutorial on Graph Rewiring: From Theory to Applications in Fairness

This page provides information and materials about Graph Rewiring: From Theory to Applications in Fairness, following the tutorial presented at Learning on Graphs 2022 on the 11th of December, 2022. For the corresponding resources, check out the following links:

Here are some additional resources, and we expect to keep updating and improving the content in the future, stay tuned!

## Outline

Section Content
Motivation
10am ET (16:00 CET)
• Graph Classification and Expressiveness
• Node Classification and Over-smoothing
• Desiderates
Introduction to Spectral Theory
Code Available
• Average Cut Problem
• Fiedler Vector
• Graph Laplacian and Dirichlet Energies
• Laplacian Eigenfunctions and Spectrum
• Spectral Theorem
• Spectral Commute Times
Transductive Rewiring
Code Available
• Diffusive Rewiring
• Cheeger Constant
• Curvature-Based Rewiring
Inductive Rewiring
Code Available
• CT and the Lovász Bound
• CT and Sparsification
• CT and Directional Graph Networks
• CT-Layer
• CT-Layer and its Loss function
• Learned CT Embedding and CT distances
• Experiments in Graph and Node Classification
• CT-Layer as Differentiable Curvature
• CT and Cheeger Constant
• GAP-Layer
• Spectral Derivatives
• Learning the Fiedler vector
Graph Fairness
• Algorithmic Fairness Concepts
• Structure: a New Dimension
• Cause of Graph Bias
• Taxonomy of Graph Fairness Definitions
• Graph Rewiring Methods for Fairness
Panel
12am-1pm ET
(18:00-19:00 CET)
• Nuria Oliver (Moderator)
• Marinka Zitnik
• Petar Veličković
• Francesco Di Giovanni
• [TBC] Francesco Fabbri
Q&A Questions

## Citation

• If you use the code or the tutorial from parts Introduction to Spectral Theory, Introduction to Lovász Bound, Transductive RW or Inductive Rewiring (DiffWire), please cite the original sources and:
``````@inproceedings{arnaiz2022diffwire,
title={DiffWire: Inductive Graph Rewiring via the Lovasz Bound},
author={Adrian Arnaiz-Rodriguez and Ahmed Begga and Francisco Escolano and Nuria Oliver},
booktitle={The First Learning on Graphs Conference},
year={2022},
url={https://openreview.net/pdf?id=IXvfIex0mX6f}
}
``````
• If you use the code or the tutorial from Graph Fairness part, please cite the original sources : To Be Added.

## Tutorial Overview

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. Despite their promising results, GNNs 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. Graph rewiring consists of modifying (editing and/or re-weighting) the edges of a graph so that the information flow is optimized for a specific task, such as graph/node classification or link prediction. 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, empirical and ethical perspective.

## Goals

The main goal of this tutorial is to teach the fundamentals of graph rewiring and its current challenges. We will motivate the need for mathematically sound graph rewiring methods as a solution to address the main limitations of GNNs: under-reaching, over-smoothing and over-squashing. We will explain the two main approaches proposed in the literature to achieve graph rewiring:

• Transductive methods compute a new convolution matrix of each graph as a pre-processing step in order to improve the performance of the task at hand. Examples are parameterized diffusion or curvature-based approaches.
• Inductive methods learn new convolution matrices from training on subgraphs/graphs and then predict those in unseen graphs. Ideally, this process is fully differentiable and parameter free. We will delve into the implementation of this methods. Hands-on section.

In addition, we will discuss the potential that graph rewiring has to address social and ethical challenges posed by AI, and particularly as a tool to achieve algorithmic fairness.

## Target Audicence

This tutorial has a good balance between intermediate and advanced materials. Attendees should have knowledge of Graph Theory and Machine Learning, particularly GNNs. Intermediate algebra, probability theory and programming knowledge are recommended, as we will show programming libraries and specific examples in the form of Jupyter notebooks to ease the understanding of key concepts. This tutorial will be of particular interest to those who would like to deepen their knowledge on GNNS for a variety of purposes, including building more expressive GNN architectures, improving their robustness, enhancing their explicability or developing trustworthy graph methods. As the tutorial will be held virtually, the maximum number of participants are not a strong requirement (ideally up to 200).

## Expected learning outcomes

Attendees of this tutorial will acquire understanding of the essential concepts in:

• Spectral Graph Theory
• Laplacians
• Dirichlet energies
• Isoperimetric problems
• Random walks
• Spectral gap
• Commute Times (aka effective resistance)
• Rewiring
• Transductive Methods
• Inductive Methods
• Theory and hands-on content
• Graph Algorithmic Fairness
• Basic concepts of algorithmic fairness