[CS] Andrew Hands MS PresentationSep 22, 2025

[via cs]

This is an announcement of Andrew Hands's MS Presentation
===============================================
Candidate: Andrew Hands

Date: Monday, September 22, 2025

Time: 11 am CST

Location: JCL 298

Title: Hierarchical Universal Subgraph Neural Networks for Bounded Treewidth Graphs

Abstract: Current graph neural networks face fundamental limitations in capturing complex, higher-order relationships due to their reliance on local aggregation, leading to over-smoothing and over-squashing that prevent effective modeling of global graph properties. While recent advances have explored cellular complexes and subgraph aggregation, these approaches lack systematic methods for selecting and combining subgraphs while maintaining theoretical guarantees.
We propose Abstract Subgraph Message Passing Neural Networks (ASMPNNs), a novel framework that achieves joint equivariance across multiple subgraphs through principled subgraph selection and message passing. Our approach centers on two key innovations: (1) a hierarchical connectivity algorithm that systematically identifies subgraph coverings with provable universality properties, and (2) an abstract message passing framework that maintains equivariance while enabling expressive representation learning.

Our main contributions are: (1) Algorithmic Framework: A hierarchical connectivity algorithm that efficiently computes universal subgraph selections, with complexity polynomial in graph size for bounded treewidth graphs. (2) Theoretical Analysis: We establish the first complete characterization of when subgraph selections achieve universality, providing rigorous foundations for understanding the expressive power of subgraph-based architectures. (3) Unified Framework: We introduce Abstract Subgraph Message Passing Neural Networks (ASMPNNs) that generalize existing subgraph methods while maintaining theoretical guarantees, with competitive performance on molecular property prediction tasks.

Our work provides both practical algorithms and theoretical foundations for next-generation graph neural networks that can systematically capture multi-scale graph structures with provable expressivity guarantees, advancing the state-of-the-art in both algorithmic design and theoretical understanding of subgraph-based neural architectures

Advisors: Risi Kondor

Committee Members: Risi Kondor, Claire Donnat, and Lorenzo Orecchia