NSF-BSF:CIF:Small:Graph Machine Learning With Non-Canonical Symmetries

In many applications, data is expressed in terms of graphs (e.g., molecules or social networks), and those graphs are typically expressed as matrices or lists of edges and nodes for processing purposes. However, the representation of a graph as a matrix or list is not unique, and the non-uniqueness can be expressed as symmetries that machine-learning models on graphs should respect.

Namely, the predictions of the model on two matrices that represent the same graph should be consistent. This is a classical idea and the fundamental concept behind the field of geometric deep learning. This project claims that one key factor that determines the computational capabilities of current graph neural networks (GNNs) is the choice of the data representation and its symmetries.

Hence, in order to explore new computational capabilities, new ways to express graphs are proposed (called non-canonical representations), with new forms of approximate symmetries (non-canonical symmetries), and corresponding approximately symmetry-preserving GNNs (non-canonical GNNs). The design of these non-canonical GNNs is inspired by applications in social networks, spatiotemporal graphs such as traffic networks, and graphs arising from complex material design.

The project includes collaborations with chemical engineers in the application of these models to protein and macromolecule design. In addition, this project will have an impact on many diversity outreach and educational activities, including mentoring Baltimore City public high-school students, and outreach and mentoring efforts targeting groups historically underrepresented in applied mathematics and computer science.

The project will explore the development of novel non-canonical representations, symmetries, and GNNs, as well as their applications. The research activities are divided into three main tasks: (1) The design of a non-canonical representation that expresses any graph as a combination of finitely many intersecting cliques or communities. The goal is to define a scalable representation and efficient data-processing algorithms.

Applications to very large graphs, like social networks, will be considered. (2) The development of a procedure for fitting coarse piecewise-constant templates to graphs, using the structure of the templates to design non-canonical GNNs that are sensitive to the large-scale structure of the graph. This method is expected to shine in domains where sensitivity to large scale is important, such as classification of proteins or shapes, molecular dynamics, and predictions on traffic and power networks. (3) The design of methods that exploit symmetries of the graph in the spectral domain. The main applications will be molecular dynamics and spatiotemporal graphs.

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.