# Theoretical Foundations of Efficient and Scalable Graph Learning

> **NSF 01002526DB NSF RESEARCH & RELATED ACTIVIT** · Massachusetts Institute of Technology (MA) · $187,000

## Abstract

This project aims to develop mathematical foundations for understanding and improving graph neural networks (GNNs), which are widely used machine learning models for data with graph structures. Such data arises in recommender systems, molecular modeling and a range of scientific and technological domains. While GNNs have achieved notable empirical success, key theoretical challenges remain, including limited expressivity, suboptimal performance on specific graph types, and performance degradation in deep architectures. This project addresses these challenges by building and analyzing principled models that are both expressive and computationally efficient. The research outcomes will contribute to the development of robust machine learning tools for analyzing complex graph-structured data. Undergraduate and high school students will be actively involved through mentoring and educational programs.

The project combines mathematical analysis and model design to advance the theory and practice of graph learning. It will pursue three interconnected directions: (1) developing GNN architectures for solving quadratic programs, a broad class of optimization problems; (2) analyzing the expressivity of subgraph GNNs on graphs with bounded cycles, which frequently occur in applications; and (3) designing new approaches to mitigate the oversmoothing phenomenon in deep GNNs. The work will draw on techniques from graph theory, optimization, and neural network theory. These efforts aim to 

## Key facts

- **NSF award ID:** 2509011
- **Awardee organization:** Massachusetts Institute of Technology (MA)
- **SAM.gov UEI:** E2NYLCDML6V1
- **PI:** Philippe Rigollet
- **Primary program:** 01002526DB NSF RESEARCH & RELATED ACTIVIT
- **All programs:** Artificial Intelligence (AI), Machine Learning Theory
- **Estimated total:** $187,000
- **Funds obligated:** $187,000
- **Transaction type:** Standard Grant
- **Period:** 07/01/2025 → 06/30/2028

## Primary source

NSF Award Search: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2509011

## Citation

> US National Science Foundation, Award 2509011, Theoretical Foundations of Efficient and Scalable Graph Learning. Retrieved via AI Analytics 2026-06-08 from https://api.ai-analytics.org/grant/nsf/2509011. Licensed CC0.

---

*[NSF Awards dataset](/datasets/nsf-awards) · CC0 1.0*