Graph-based data processing algorithms impact a variety of application domains ranging from transportation networks, artificial intelligence systems, cellphone networks, social networks, and the Web. Nevertheless, the emergent big-data era poses key conceptual challenges: several existing graph-based methods used in practice exhibit unreasonably high running time; several other methods operate in the absence of correctness guarantees. These challenges severely imperil the safety and reliability of higher-level decision-making systems of which they are a part. This research introduces an innovative new computational framework for graph learning and inference that addresses these challenges. Specific applications studied in this project include: better approaches for monitoring roadway congestion and identify traffic incidents in a timely manner; root-cause analysis of complex events in social networks; and design of better personalized learning systems, lowering educational costs and increasing quality nationwide. Activities include integrated programs to increase participation of women and under-represented minorities in the computational sciences.
From a technical standpoint, the investigator pursues three research themes: (i) designing scalable non-convex algorithms for learning the edges (and weights) of an unknown graph given a sequence of independent static and/or time-varying local measurements; (ii) designing new approximation algorithms for utilizing the structure of a given graph to enable scalable post-hoc decision making in complex systems; (iii) developing provable algorithms for training special families of artificial neural networks, and filling gaps between rigorous theory and practice of neural network learning. Progress in each of the above themes will be extensively evaluated using real-world data from engineering applications including social network data, highway monitoring data, and fluid-flow simulation data. Collaborations with domain experts in each of these application areas will ensure that the new theory, tools, and software emerging from this project will lead to meaningful societal benefits.
