CRII: III: Theory and Practice of Learning on Graphs

College Of William And Mary, Williamsburg VA

Investigators

Abstract

Learning on graphs plays a key role in digital communications. Tech companies (social media, etc.) rely on social network analysis in their core services. Financial services (proprietary trading, funds, etc.) use interaction networks of on-list companies to "beat the market". Intelligence agencies analyze the interactions between terrorists to understand the structure of terrorist cells. However, there is a gap between the theory and practice of designing graph-learning algorithms. On the theory side, substantial progress has been made to design learning algorithms for stylized models, but the practical impacts are limited. On the practice side, efficient heuristics have been developed to analyze real-world graphs, but they often lack theoretical guarantees in terms of running time or accuracy. To bridge the theory-practice gap, this project will draw upon techniques from theoretical computer science, machine learning, and high-dimensional statistics to design theoretically sound, graph-learning algorithms that can (i) automatically choose the most suitable statistical network, (ii) leverage node-level information (e.g., users' profile in a social network), and (iii) properly handle the serial correlations in a graph. The algorithms will help practitioners to build more accurate network models at reduced cost, and have beneficial economic and social impacts on downstream applications. From a technical standpoint, this research program will study the design of statistically sound, computationally tractable, and practically relevant algorithms for inferring latent structures in graphs. It consists of two thrusts: (i) Realistic interaction models. The project will use random graph theory and kernel learning to develop data-driven procedures to automatically select the most suitable assortative graph models, and introduces and analyzes a semi-adversarial model that can analyze more realistic interactions than those captured by real-valued weighted graphs; (ii) Time-evolving statistical models. The project will study how tools from property testing results in theoretical computer science can detect change-points in a network evolution process, and then merges the spectral methods and tools from high-dimensional statistics to build new inference algorithms for serially correlated 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.