III: Small: Theoretical Foundations of Hypergraph Learning: Expressiveness and Sample Complexity

This research project aims to develop machine learning methods in order to better understand complex and multi-way interactions in real-world applications, such as webs of social relationships, gene-disease analysis, and brain functional analysis. The key technique this project will pursue is hypergraph learning, which generalizes standard graph learning by allowing edges to connect multiple data points at once. While experimental research has justified the promise of hypergraph learning methods, the study of their performance in theory remains a fundamental challenge. In this light, this project will seek to characterize two core features of hypergraph learning in theory: the amount of data that is needed to achieve a desired level of prediction accuracy, and the exact model architectures required by data from a specific signal source. This will be achieved by leveraging various techniques in statistics, computer science, and electrical and computer engineering. In line with the research agenda, educational efforts will be devoted to the curriculum design of courses in related subjects. The proposed outreach activities will continue to encourage the participation of all groups, strengthening the connection with local communities. The overall goal of this project is to establish the theoretical foundation of hypergraph learning and its enabled learning frameworks. As a point of departure, this project will study the expressiveness of hypergraph neural networks with tensor-based message passing mechanisms, seeking to develop discriminative models principled by hypergraph pooling and autoencoders. Orthogonally, this project will also explore the expressiveness of neural architectures in terms of their ability to discriminate between different graph structures, aiming to develop models with the ability to perform strong isomorphism tests; leveraging a subtle connection between high-order aggregation and canonical labeling, the key innovation lies in the proposed neural architectures that can simulate modules of node individualization and refinement that are invariant to hypergraph isomorphism. The last research thrust seeks to develop theoretical tools for analyzing the sample complexity of hypergraph neural networks through the PAC-Bayes framework and VC dimension. The theoretical parts will be supplemented by empirical studies to explore necessary and/or sufficient conditions for theoretical sample complexity bounds to be well-aligned with practical generalization performance. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.