Understanding Oversmoothing in Graph Neural Networks (GNNs): Insights from Two Theoretical Studies
From Google TechTalks · 1:06:30
Show by Google TechTalks
A Google TechTalk, presented by Xinyi Wu, 2024-01-18A Google Algorithm Seminar. ABSTRACT: Oversmoothing in Graph Neural Networks (GNNs) refers to the phenomenon where increasing network depth leads to homogeneous node representations. Over the last few years, it has remained as one of the central challenges of building more powerful Graph Neural Networks (GNNs). In this talk, I will discuss two recent papers on this phenomenon and provide some new insights.Uploaded 26-01-24The first work studies why oversmoothing happens at a relatively shallow depth in GNNs. By carefully analyzing the oversmoothing mechanisms in a stylized formulation, we distinguish between adverse mixing that homogenizes nodes across different classes and beneficial denoising within the same class. We quantify these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM) and show that oversmoothing occurs once the mixing effect starts to dominate the denoising effect. We establish that the number of layers required for this transition is O(logN/log(logN)) for sufficiently dense graphs with N nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR), or equivalently, the effects of initial residual connections on oversmoothing, and shed light on when and why they might not be an ideal solution to the problem.In the second work, we study oversmoothing in attention-based GNNs, such as Graph Attention Networks (GATs) and transformers. Treating attention-based GNNs as dynamical systems, our study demonstrates that the graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially. From a technical point of view, the proposed framework significantly extends the existing results on oversmoothing, and can account for asymmetric, state-dependent and time-varying aggregation operators and a wide range of common nonlinear activation functions, such as ReLU, LeakyReLU, GELU and SiLU.The talk is based on the following papers: https://arxiv.org/abs/2212.10701, https://arxiv.org/abs/2305.16102. Joint works with Amir Ajorlou (MIT), Zhengdao Chen (NYU/Google), William Wang (MIT), Zihui Wu (Caltech) and Ali Jadbabaie (MIT).ABOUT THE SPEAKER: Xinyi Wu is a fourth-year Ph.D. student in the Institute for Data, Systems, and Society (IDSS) at Massachusetts Institute of Technology (MIT), advised by Professor Ali Jadbabaie. She is affiliated with the Laboratory for Information and Decision Systems (LIDS). She is a recipient of the MIT Michael Hammer Fellowship. She is interested in applied graph theory, dynamical systems, networks, and machine learning on graphs. Her work on oversmoothing in GNNs has been awarded as Spotlight paper in NeurIPS 2023.
More episodes of Google TechTalks
More episodes
- Java Posse Episode 100 (Live Special)
- Cascading Adversarial Bias from Injection to Distillation in Language Models
- Practical Common Lisp
- Cascading Adversarial Bias from Injection to Distillation in Language Models
- Security is Broken
- POPri: Private Federated Learning using Preference-Optimized Synthetic Data
- Everything is Miscellaneous
- Leveraging Per-Instance Privacy for Machine Unlearning
- Impact of Technology on Reducing Poverty and Alleviating...
- Disparate Privacy Risks from Medical AI - An Investigation into Patient-level Privacy Risk
PodSearch is a free, independent podcast search engine. Read about PodSearch, the privacy policy or contact us.