Timezone: »
Cellular sheaves equip graphs with a ``geometrical'' structure by assigning vector spaces and linear maps to nodes and edges. Graph Neural Networks (GNNs) implicitly assume a graph with a trivial underlying sheaf. This choice is reflected in the structure of the graph Laplacian operator, the properties of the associated diffusion equation, and the characteristics of the convolutional models that discretise this equation. In this paper, we use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs in heterophilic settings and their oversmoothing behaviour. By considering a hierarchy of increasingly general sheaves, we study how the ability of the sheaf diffusion process to achieve linear separation of the classes in the infinite time limit expands. At the same time, we prove that when the sheaf is non-trivial, discretised parametric diffusion processes have greater control than GNNs over their asymptotic behaviour. On the practical side, we study how sheaves can be learned from data. The resulting sheaf diffusion models have many desirable properties that address the limitations of classical graph diffusion equations (and corresponding GNN models) and obtain competitive results in heterophilic settings. Overall, our work provides new connections between GNNs and algebraic topology and would be of interest to both fields.
Author Information
Cristian Bodnar (University of Cambridge)
Francesco Di Giovanni (Twitter)
Benjamin Chamberlain (Twitter)
Pietro Lió (University of Cambridge)
Michael Bronstein (USI)
More from the Same Authors
-
2021 : Interpretable Data Analysis for Bench-to-Bedside Research »
Zohreh Shams · Botty Dimanov · Nikola Simidjievski · Helena Andres-Terre · Paul Scherer · Urška Matjašec · Mateja Jamnik · Pietro Lió -
2021 : Structure-aware generation of drug-like molecules »
Pavol Drotar · Arian Jamasb · Ben Day · Catalina Cangea · Pietro Lió -
2021 : 3D Pre-training improves GNNs for Molecular Property Prediction »
Hannes Stärk · Dominique Beaini · Gabriele Corso · Prudencio Tossou · Christian Dallago · Stephan Günnemann · Pietro Lió -
2021 : 3D Pre-training improves GNNs for Molecular Property Prediction »
Hannes Stärk · Gabriele Corso · Christian Dallago · Stephan Günnemann · Pietro Lió -
2021 : Approximate Latent Force Model Inference »
Jacob Moss · Felix Opolka · Pietro Lió -
2022 : Learning Feynman Diagrams using Graph Neural Networks »
Alexander Norcliffe · Harrison Mitchell · Pietro Lió -
2022 : A physics-informed search for metric solutions to Ricci flow, their embeddings, and visualisation »
Aarjav Jain · Challenger Mishra · Pietro Lió -
2022 : Equivariant 3D-Conditional Diffusion Models for Molecular Linker Design »
Ilia Igashov · Hannes Stärk · Clément Vignac · Victor Garcia Satorras · Pascal Frossard · Max Welling · Michael Bronstein · Bruno Correia -
2022 : Improving Classification and Data Imputation for Single-Cell Transcriptomics with Graph Neural Networks »
Han-Bo Li · Ramon Viñas Torné · Pietro Lió -
2022 : Structure-based Drug Design with Equivariant Diffusion Models »
Arne Schneuing · Yuanqi Du · Charles Harris · Arian Jamasb · Ilia Igashov · weitao Du · Tom Blundell · Pietro Lió · Carla Gomes · Max Welling · Michael Bronstein · Bruno Correia -
2022 : A Federated Learning benchmark for Drug-Target Interaction »
Filip Svoboda · Gianluca Mittone · Nicholas Lane · Pietro Lió -
2022 : Provably Efficient Causal Model-Based Reinforcement Learning for Environment-Agnostic Generalization »
Mirco Mutti · Riccardo De Santi · Emanuele Rossi · Juan Calderon · Michael Bronstein · Marcello Restelli -
2022 : Benchmarking Graph Neural Network-based Imputation Methods on Single-Cell Transcriptomics Data »
Han-Bo Li · Ramon Viñas Torné · Pietro Lió -
2022 : Sheaf Attention Networks »
Federico Barbero · Cristian Bodnar · Haitz Sáez de Ocáriz Borde · Pietro Lió -
2022 : Surfing on the Neural Sheaf »
Julian Suk · Lorenzo Giusti · Tamir Hemo · Miguel Lopez · Marco La Vecchia · Konstantinos Barmpas · Cristian Bodnar -
2022 : On the Expressive Power of Geometric Graph Neural Networks »
Cristian Bodnar · Chaitanya K. Joshi · Simon Mathis · Taco Cohen · Pietro Liò -
2022 : On the Unreasonable Effectiveness of Feature Propagation in Learning on Graphs with Missing Node Features »
Emanuele Rossi · Henry Kenlay · Maria Gorinova · Benjamin Chamberlain · Xiaowen Dong · Michael Bronstein -
2022 : Hyperbolic Deep Reinforcement Learning »
Edoardo Cetin · Benjamin Chamberlain · Michael Bronstein · jonathan j hunt -
2022 : Human Interventions in Concept Graph Networks »
Lucie Charlotte Magister · Pietro Barbiero · Dmitry Kazhdan · Federico Siciliano · Gabriele Ciravegna · Fabrizio Silvestri · Mateja Jamnik · Pietro Lió -
2023 : Bending and Binding: Predicting Protein Flexibility upon Ligand Interaction using Diffusion Models »
Xuejin Zhang · Tomas Geffner · Matt McPartlon · Mehmet Akdel · Dylan Abramson · Graham Holt · Alexander Goncearenco · Luca Naef · Michael Bronstein -
2023 : PoseCheck: Generative Models for 3D Structure-based Drug Design Produce Unrealistic Poses »
Charles Harris · Kieran Didi · Arian Jamasb · Chaitanya K. Joshi · Simon Mathis · Pietro Lió · Tom Blundell -
2023 : Importance-Guided Diffusion »
Paris Flood · Pietro Lió -
2023 : Modelling biology in novel ways - an AI-first course in Structural Bioinformatics »
Kieran Didi · Charles Harris · Charles Harris · Pietro Lió · Rainer Beck · Rainer Beck -
2023 : RetroBridge: Modeling Retrosynthesis with Markov Bridges »
Ilia Igashov · Arne Schneuing · Arne Schneuing · Marwin Segler · Marwin Segler · Michael Bronstein · Michael Bronstein · Bruno Correia · Bruno Correia -
2023 : Pseudotime Diffusion »
Jacob Moss · Jeremy England · Pietro Lió -
2023 : Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs »
Dobrik Georgiev · Pietro Lió · Jakub Bachurski · Junhua Chen · Tunan Shi -
2023 : PoseCheck: Generative Models for 3D Structure-based Drug Design Produce Unrealistic Poses »
Charles Harris · Kieran Didi · Arian Jamasb · Chaitanya Joshi · Simon Mathis · Pietro Lió · Tom Blundell -
2023 : PoseCheck: Generative Models for 3D Structure-based Drug Design Produce Unrealistic Poses »
Charles Harris · Kieran Didi · Arian Jamasb · Chaitanya Joshi · Simon Mathis · Pietro Lió · Tom Blundell -
2023 : A framework for conditional diffusion modelling with applications in protein design »
Kieran Didi · Francisco Vargas · Simon Mathis · Vincent Dutordoir · Emile Mathieu · Urszula Julia Komorowska · Pietro Lió -
2023 : Protein-Protein Docking with Latent Diffusion »
Matt McPartlon · Céline Marquet · Tomas Geffner · Daniel Kovtun · Alexander Goncearenco · Zachary Carpenter · Luca Naef · Michael Bronstein · Jinbo Xu -
2023 : Evaluating Representation Learning on the Protein Structure Universe »
Arian Jamasb · Alex Morehead · Zuobai Zhang · Chaitanya K. Joshi · Kieran Didi · Simon Mathis · Charles Harris · Jian Tang · Jianlin Cheng · Pietro Lió · Tom Blundell -
2023 : A framework for conditional diffusion modelling with applications in motif scaffolding for protein design »
Kieran Didi · Francisco Vargas · Simon Mathis · Vincent Dutordoir · Emile Mathieu · Urszula Julia Komorowska · Pietro Lió -
2023 : RetroBridge: Modeling Retrosynthesis with Markov Bridges »
Ilia Igashov · Arne Schneuing · Marwin Segler · Michael Bronstein · Bruno Correia -
2023 : PoseCheck: Generative Models for 3D Structure-based Drug Design Produce Unrealistic Poses »
Charles Harris · Kieran Didi · Arian Jamasb · Chaitanya K. Joshi · Simon Mathis · Pietro Lió · Tom Blundell -
2023 : A framework for conditional diffusion modelling with applications in motif scaffolding for protein design »
Kieran Didi · Francisco Vargas · Simon Mathis · Vincent Dutordoir · Emile Mathieu · Urszula Julia Komorowska · Pietro Lió -
2023 : SHARCS: Shared Concept Space for\\Explainable Multimodal Learning »
Gabriele Dominici · Pietro Barbiero · Lucie Charlotte Magister · Pietro Lió · Nikola Simidjievski -
2023 : GCondNet: A Novel Method for Improving Neural Networks on Small High-Dimensional Tabular Data »
Andrei Margeloiu · Nikola Simidjievski · Pietro Lió · Mateja Jamnik -
2023 : GCondNet: A Novel Method for Improving Neural Networks on Small High-Dimensional Tabular Data »
Andrei Margeloiu · Nikola Simidjievski · Pietro Lió · Mateja Jamnik -
2023 : Incorporating LLM Priors into Tabular Learners »
Max Zhu · Siniša Stanivuk · Andrija Petrovic · Mladen Nikolic · Pietro Lió -
2023 : Everybody Needs a Little HELP: Explaining Graphs via Hierarchical Concepts »
Jonas Jürß · Lucie Charlotte Magister · Pietro Barbiero · Pietro Lió · Nikola Simidjievski -
2023 : How does over-squashing affect the power of GNNs? »
Francesco Di Giovanni · T. Konstantin Rusch · Michael Bronstein · Andreea-Ioana Deac · Marc Lackenby · Siddhartha Mishra · Petar Veličković -
2023 : Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs »
Dobrik Georgiev · Pietro Lió · Jakub Bachurski · Junhua Chen · Tunan Shi -
2023 : Bridging the Gap: Towards Flexible, Efficient, and Effective Tensor Product Networks »
Nanxiang Wang · Chen Lin · Michael Bronstein · Philip Torr -
2023 : SHARCS: Shared Concept Space for\\Explainable Multimodal Learning »
Gabriele Dominici · Pietro Barbiero · Lucie Charlotte Magister · Pietro Lió · Nikola Simidjievski -
2023 Workshop: Temporal Graph Learning Workshop @ NeurIPS 2023 »
Farimah Poursafaei · Shenyang Huang · Kellin Pelrine · Julia Gastinger · Emanuele Rossi · Michael Bronstein · Reihaneh Rabbany -
2023 Poster: Graph Denoising Diffusion for Inverse Protein Folding »
Kai Yi · Bingxin Zhou · Yiqing Shen · Pietro Lió · Yuguang Wang -
2023 Poster: Interpretable Graph Networks Formulate Universal Algebra Conjectures »
Francesco Giannini · Stefano Fioravanti · Oguzhan Keskin · Alisia Lupidi · Lucie Charlotte Magister · Pietro Lió · Pietro Barbiero -
2023 Poster: Sheaf Hypergraph Networks »
Iulia Duta · Giulia Cassarà · Fabrizio Silvestri · Pietro Lió -
2023 Poster: Curvature Filtrations for Graph Generative Model Evaluation »
Joshua Southern · Jeremy Wayland · Michael Bronstein · Bastian Rieck -
2023 Poster: Temporal Graph Benchmark for Machine Learning on Temporal Graphs »
Shenyang Huang · Farimah Poursafaei · Jacob Danovitch · Matthias Fey · Weihua Hu · Emanuele Rossi · Jure Leskovec · Michael Bronstein · Guillaume Rabusseau · Reihaneh Rabbany -
2022 : On the Expressive Power of Geometric Graph Neural Networks »
Cristian Bodnar · Chaitanya K. Joshi · Simon Mathis · Taco Cohen · Pietro Liò -
2022 : Sheaf Attention Networks »
Federico Barbero · Cristian Bodnar · Haitz Sáez de Ocáriz Borde · Pietro Lió -
2022 Workshop: Temporal Graph Learning Workshop »
Reihaneh Rabbany · Jian Tang · Michael Bronstein · Shenyang Huang · Meng Qu · Kellin Pelrine · Jianan Zhao · Farimah Poursafaei · Aarash Feizi -
2022 : Invited talk: Francesco Di Giovanni »
Francesco Di Giovanni · Francesco Di Giovanni -
2022 : Dynamic outcomes-based clustering of disease progression in mechanically ventilated patients »
Emma Rocheteau · Ioana Bica · Pietro Lió · Ari Ercole -
2022 Poster: Concept Embedding Models: Beyond the Accuracy-Explainability Trade-Off »
Mateo Espinosa Zarlenga · Pietro Barbiero · Gabriele Ciravegna · Giuseppe Marra · Francesco Giannini · Michelangelo Diligenti · Zohreh Shams · Frederic Precioso · Stefano Melacci · Adrian Weller · Pietro Lió · Mateja Jamnik -
2022 Poster: Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries »
Fabrizio Frasca · Beatrice Bevilacqua · Michael Bronstein · Haggai Maron -
2022 Poster: Graphein - a Python Library for Geometric Deep Learning and Network Analysis on Biomolecular Structures and Interaction Networks »
Arian Jamasb · Ramon Viñas Torné · Eric Ma · Yuanqi Du · Charles Harris · Kexin Huang · Dominic Hall · Pietro Lió · Tom Blundell -
2022 Poster: Composite Feature Selection Using Deep Ensembles »
Fergus Imrie · Alexander Norcliffe · Pietro Lió · Mihaela van der Schaar -
2022 Poster: SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks »
Davide Buffelli · Pietro Lió · Fabio Vandin -
2021 : GRAND: Graph Neural Diffusion »
Benjamin Chamberlain · James Rowbottom · Maria Gorinova · Stefan Webb · Emanuele Rossi · Michael Bronstein -
2021 : Neural ODE Processes: A Short Summary »
Alexander Norcliffe · Cristian Bodnar · Ben Day · Jacob Moss · Pietro Lió -
2021 : On Second Order Behaviour in Augmented Neural ODEs: A Short Summary »
Alexander Norcliffe · Cristian Bodnar · Ben Day · Nikola Simidjievski · Pietro Lió -
2021 : Structure-aware generation of drug-like molecules »
Pavol Drotar · Arian Jamasb · Ben Day · Catalina Cangea · Pietro Lió -
2021 Poster: Beltrami Flow and Neural Diffusion on Graphs »
Benjamin Chamberlain · James Rowbottom · Davide Eynard · Francesco Di Giovanni · Xiaowen Dong · Michael Bronstein -
2021 Poster: Weisfeiler and Lehman Go Cellular: CW Networks »
Cristian Bodnar · Fabrizio Frasca · Nina Otter · Yuguang Wang · Pietro Liò · Guido Montufar · Michael Bronstein -
2020 : Invited Talk 1: Geometric deep learning for 3D human body synthesis »
Michael Bronstein -
2020 Poster: Constraining Variational Inference with Geometric Jensen-Shannon Divergence »
Jacob Deasy · Nikola Simidjievski · Pietro Lió -
2020 Poster: On Second Order Behaviour in Augmented Neural ODEs »
Alexander Norcliffe · Cristian Bodnar · Ben Day · Nikola Simidjievski · Pietro Lió -
2019 Workshop: Graph Representation Learning »
Will Hamilton · Rianne van den Berg · Michael Bronstein · Stefanie Jegelka · Thomas Kipf · Jure Leskovec · Renjie Liao · Yizhou Sun · Petar Veličković