ELLIS Doctoral Symposium logo

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!

Organizers

Adrián Arnaiz
Adrián Arnaiz
PhD Student
ELLIS Alicante
Speaker, panel moderator and content creator
Francisco Escolano
Francisco Escolano, PhD
Full Professor
ELLIS Alicante, University of Alicante
Speaker and content creator
Nuria Oliver
Nuria Oliver, PhD
Director of ELLIS Alicante
Panel Moderator and content creator
Edwin Hancock
Edwin Hancock, PhD
Emeritus Professor
University of York
Speaker and content creator
Ahmed Begga
Ahmed Begga
Research Intern, MSc Student
University of Valencia
Content creator

Panel

Marinka Zitnik
Marinka Zitnik, PhD
Assistant Professor
Harvard University
Petar Veličković
Petar Veličković, PhD
Staff Research Scientist
DeepMind
Francesco Di Giovanni
Francesco Di Giovanni, PhD
ML Researcher, PostDoc
Twitter
Francesco Fabbri
Francesco Fabbri, PhD
Research Scientist
Spotify

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{arnaiz-rodriguez2022diffwire,
  title={DiffWire: Inductive Graph Rewiring via the Lov\'asz Bound},
  author={Adrian Arnaiz-Rodriguez and Ahmed Begga and Francisco Escolano and Nuria Oliver},
  booktitle={Learning on Graphs Conference},
  year={2022},
  url={https://openreview.net/forum?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
    • Dyadic fairness
    • Edge editing methods

Last but not least, attendees will acquire technical skills to perform inductive rewiring in a hands-on part of the tutorial, and very useful insights from recognized experts in the field in the panel session.

This combination of methodologies will provide attendees with the necessary knowledge and tools to use GNNs to address problems in a variety of domains, such as medicine, biology, chemistry, social and communication network analysis and computational social sciences.

Learning on Graphs Conference 2022

Learning on Graphs. LoG22 was the first edition of this conference. There were 70+ attendes during the 3 hours of the conference on Sunday 11th December. The conference was held in a virtual format, and the talks were recorded and uploaded to the conference website. The conference was a great success, and we are looking forward to the next edition.

The posts promoting the event had (at least) 25000 visualizations on different social media platforms.