CIF: SMALL: Mathematical Foundations for Machine Learning with Latent Space Graphs

Graphs encode relationships between items. Data in the form of graphs is widespread across the sciences, technology, and everyday life. Examples include social networks indicating friendships between individuals, protein interaction networks capturing compatibility of proteins, and flight networks containing links between airports. Graph data has the potential to play an integral role in machine learning systems, yet it remains unclear how to best make use of this data. The goal of this project is to develop a mathematical foundation to guide the principled use of graph data in a wide variety of machine learning tasks. Due to the basic nature of the research, potential downstream applications of new algorithmic insights span a multitude of applied domains; an example is improved therapeutic drug discovery through accurate predictions of drug efficacy with significantly fewer costly and time-consuming experiments. The project involves the mentoring of both PhD students and undergraduate researchers. The results generated from this project will be integrated into advanced undergraduate and graduate courses on probability and algorithmic statistical inference. Many real-world networks are accurately represented by graphs with underlying geometry: for instance, in a social network, the nodes are associated to a list of features (e.g., the individual's location, age, hobbies, personality, etc.), and edges between pairs of nodes are formed as a function of their unobserved feature vectors. The project develops principled methodology for optimally exploiting structure in the latent space underlying a graph in order to carry out machine learning tasks. The first of three project components characterizes how the geometry of the underlying space affects structural or combinatorial properties of the graph. The second component studies the problem of recovering latent feature vectors from an observed graph, and aims to derive optimal algorithms for a wide variety of latent space graphs. The third component investigates semi-supervised learning with graph data, and aims to find computationally efficient algorithms achieving the best possible prediction accuracy. 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.