CAREER: Learning and Leveraging the Structure of Large Graphs: Novel Theory and Algorithms

点击翻译按钮获取中文摘要

From genetic interaction networks and the brain to wireless sensor networks and the power grid, there exist many large, complex interacting systems. Graph theory provides an elegant and powerful mathematical formalism for quantifying and leveraging such interactions. Unsurprisingly, many modern tasks in science and engineering rely on the discovery and exploitation of the structure of graphs. Unfortunately, there is a stark disconnect between the purported capabilities of data-driven algorithms for graph analytics and their real world applicability. Specifically, the following key challenges emerge for existing algorithms: (i) Reliance on large number of expensive experiments/measurements; this is prohibitive in the large systems typically encountered in science and engineering. (ii) Reliance on the availability of curated and labeled datasets; this is untenable outside a narrow set of disciplines. (iii) Design for worst-case scenarios; this lack of adaptivity to structure unique to the problem severely impairs their statistical and computational efficiency. In response to the above challenges, this research program will close the loop on traditional machine learning systems where data acquisition and learning algorithms are designed separately. The project will devise several novel compressive, adaptive, and interactive algorithms that efficiently exploit structure in the problem. These will be complemented by foundational advances to the theory of learning and leveraging structure in graphs. The methodological advances will have impact on diverse areas such as resilient cyber-infrastructure, robust neuroimaging, and intervention design for pandemics. The research activities are tightly integrated with a comprehensive education, mentoring, and outreach plan that will increase awareness, access, and inclusion in STEM, especially with respect to data-driven methods in science and engineering. The technical contributions of this project are organized into two interrelated themes: (1) Learning the structure of graphs from compressively and interactively acquired data. The research in this theme will reveal new and interesting tradeoffs between the cost of data acquisition and statistical accuracy. These will be complemented by minimax optimal algorithms that achieve various points in the tradespace. (2) Leveraging the graph structure to accomplish efficient inference. The research in this theme is unified by the general problem of level set estimation on graphs and will result in foundational contributions to the theory of nonparametric learning, meta-learning, and sequential decision making. The research themes feature extensive experimental validation, collaboration with domain experts, and translational activities with the view of driving meaningful and long-term impacting on practice.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.