IJCAI-24 Tutorial

Enhancing Graph Representation Learning through Subgraph Strategies

Abstract

Recently, numerous seemingly distinct methods have leveraged representing graphs through their induced subgraphs to overcome the limitations of Graph Neural Networks in expressive power, generalization capabilities, and scalability. This tutorial will, for the first time, unify these methods into a common, theoretically grounded framework, better highlighting their differences, similarities, and some of the challenges that remain open in graph representation learning.

This tutorial examines the foundations and limitations of Graph Neural Networks (GNNs), revealing their bounded effectiveness in distinguishing non-isomorphic graphs and handling prediction tasks involving link and higher-order patterns. First, attendees will explore a novel family of GNNs, offering enhanced expressive power by leveraging the decomposition of graphs into sets of their induced subgraphs. Then, we will demonstrate how these subgraph GNNs can be conceptualized as part of a broader framework of distance encoding schemes and present their implementation in various tasks involving multiple nodes. Furthermore, attendees will gain an intuitive understanding of how to mitigate the computational challenges posed by learning on subgraphs with structural encodings through a scalable paradigm of algorithm and system co-design.

Building upon the introduced theoretical principles, this tutorial presents exciting cutting-edge applications of subgraph-based methods, ranging from biochemistry to programming languages. Through easy-to-follow, hands-on coding demonstrations, participants will witness the superior performance and potential of subgraph methods in drug design and neurological disorder diagnosis. The tutorial concludes with future directions and open challenges, emphasizing how this unified framework for subgraph-based representations can help drive future advancements in graph representation learning.

[News]

12/2024 The SubG library is now available on Github.

12/2024 The slides and coding examples will be released soon.

Outline

Foundations of Graph Neural Networks and their Limitations (10 mins)
- Introduction of Graph Neural Networks (GNNs)
- Limitations of Message-passing Neural Networks (MPNNs)
Leveraging Subgraphs for Increased Expressive Power (30 mins)
- Family Hierarchy of Subgraph GNNs
- Expressiveness, Design Space, and Scalability
- Unified Framework under Distance Encodings
Scalable and Efficient Learning on Subgraphs (30 mins)
- Learning Subgraphs with Unified Structural Features
- Computational Bottleneck of Subgraph-based Methods
- New Paradigm: Algorithm-System Codesign
Broad and Emerging Applications [Hands-on] (20 mins)
- Frontier Applications in Biochemical Science, Programming Languages
- Hands-on Demos in Drug Discovery, Disease Diagnosis
Final Remarks and Future Directions (10 mins, including Q&A section)

Organizers

Haoteng Yin, CS@Purdue

Haoteng Yin is a Ph.D. candidate in Machine Learning at Purdue University, supervised by Prof. Pan Li. Before Purdue, he attained MPhil in Data Science at Peking University and received BEng in Computer Science from Taishan College (Honors Program), Shandong University. His research interests focus on efficient, scalable, and privacy-preserving graph learning algorithms and foundation models. Haoteng was named one of the 2024 AI 2000 Most Influential Scholars (Honorable Mention, #60) in AAAI/IJCAI by AMiner.org. He won the Best Paper Award at SMP '16, the Top Reviewer Award at NeurIPS '22, and the Purdue Teaching Academy Graduate Teaching Award in 2024.

Beatrice Bevilacqua, CS@Purdue

Beatrice Bevilacqua is a Ph.D. candidate in Computer Science at Purdue University advised by Prof. Bruno Ribeiro, and also working closely with Prof. Haggai Maron. Prior to joining Purdue, she earned a MSc. in Computer Engineering at Sapienza, University of Rome. Her research interests are expressivity and extrapolation capabilities of models for graph data. Beatrice was a Research Scientist Intern at Google DeepMind working with Dr. Petar Veličković, and a Research Scientist Intern at Meta AI (FAIR). She won the 2024 Employee Recognition Award from Purdue University, the Top Reviewer Award at NeurIPS '22 and '23, the Honors Award from Sapienza University of Rome, and she was also the recipient of the Andrews PhD Fellowship.

Bruno Ribeiro, CS@Purdue

Bruno Ribeiro is an Associate Professor in the Department of Computer Science at Purdue University, currently a Visiting Associate Professor at Stanford University. Prior to joining Purdue in 2015, he earned his Ph.D. from the University of Massachusetts Amherst and was a postdoctoral fellow at Carnegie Mellon University. Ribeiro is interested in the intersection between relational learning and causality in deep learning. Ribeiro received an NSF CAREER award in 2020, an Amazon Research Award in 2022, and multiple best paper awards.

Pan Li, ECE@GaTech

Pan Li joined ECE at Georgia Tech as an assistant professor in 2023 Spring and an on-leave position at Purdue CS. Before joining Purdue, Pan worked as a postdoc in the SNAP group at Stanford for one year, where he worked in the SNAP group led by Prof. Jure Leskovec. Before joining the SNAP group, Pan did his Ph.D. in Electrical and Computer Engineering at the University of Illinois Urbana - Champaign (2015 - 2019). His PhD advisor at UIUC was Prof. Olgica Milenkovic. At UIUC, he also worked with several wonderful collaborators including Prof. Niao He, Prof. Arya Mazumdar, Prof. Jiawei Han, Prof. David Gleich, etc. Before coming to UIUC, Pan Li received his M.S. degree in Electronic Engineering from Tsinghua University where his advisor was Prof. Xiqin Wang and he also worked with Prof. Huadong Meng and Prof. Yuan Shen. Before that, he got my B.S. degrees in both Physics and Electrical Engineering from Beijing Jiaotong University. Pan Li has got the NSF CAREER award, the Best Paper award from Learning on Graph (LoG) 2022, Sony Faculty Innovation Award, JPMorgan Faculty Award, Ross-Lynn Faculty Award.

Page updated

Google Sites

Report abuse