[CS] Andrew Hands MS Presentation/Dec 8, 2025

[via cs]

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

Date: Monday, December 08, 2025

Time:  2 pm CST

Location: JCL 298

Title: On the Expressivity of P-Tensor Networks

Abstract: The field of Graph Neural Networks (GNNs) is fundamentally challenged by the trade-off between scalability and expressivity, as current message-passing models are inherently limited in capturing complex topological features, often failing to surpass the expressive power of the 1-Weisfeiler-Lehman test. This work addresses the expressive power gap with P-Tensor Networks ($PT_1$), a formalism that generalizes Invariant Graph Networks (IGNs) by utilizing layers of local higher-order tensor representations. The key novelty of $PT_1$ lies in its ability to explicitly enforce overlap-preserving homomorphisms ($\text{HOM}^\cup$), which mandates that the topological structure defined by edge overlaps must be preserved in the target hypergraph, unlike the standard homomorphism criterion. The primary contribution is the establishment of an expressive hierarchy, rigorously proving that $\text{PT}_1$ is strictly superior to the critical baseline for local expressive power, $\text{HOM}(\text{GHW}_1)$, yielding the hierarchy $\text{HOM}(\text{GHW}_1) \subsetneq \text{PT}_1$. This final result validates that the $\text{HOM}^\cup$ mechanism provides non-trivial distinguishing power, allowing $PT_1$ to overcome the inherent limitations of standard $\text{HOM}$-based hypergraph analysis.


Advisor: Risi Kondor

Committee Members: Risi Kondor, Lorenzo Orecchia, Claire Donnat