Over-smoothing and diffusion dynamics on graphs

Abstract

Over-smoothing is a recurrent problem when working with Graph Neural Networks that severely limits the expressiveness of well-known architectures. In this report we have gathered from different papers a mathematically tractable definition of this problem, we proposed a proof of the exponential over-smoothing of the isotropic diffusion equation on graphs and generalized it to anisotropic positive diffusion dynamics.

To prove these theorems, we introduced different pseudo-Euclidean spaces adapted to measure over-smoothing in different use cases. Finally, we implemented a fast GPU-optimized algorithm based on the Graph Fourier transformation to analyze in practice this phenomenon for Erdos-Rényi random graphs.

How to cite

@mastersthesis{lagesse2022,
  title  = {Over-smoothing and 
            diffusion dynamics on graphs},
  author = {Adrien Lagesse},
  year   = {2023},
  month  = {September},
  url    = {https://adrien-lagesse.io/publications/diffusion-dynamics-on-graphs},
  school = {Imperial College London},
  type   = {Master's thesis}
}