CAREER: Advances in Graph Learning and Inference

基于图的数据处理算法影响了从交通网络、人工智能系统、手机网络、社交网络和网络等各种应用领域。然而，新兴的大数据时代带来了关键的概念挑战：实践中使用的几种现有的基于图形的方法显示出不合理的高运行时间；其他几种方法在缺乏正确性保证的情况下运行。这些挑战严重危及它们所属的更高级别决策系统的安全和可靠性。这项研究介绍了一种创新的新计算框架，用于图形学习和推理，以应对这些挑战。该项目研究的具体应用包括：更好地监测道路拥堵并及时识别交通事件；对社交网络中复杂事件的根本原因分析；以及设计更好的个性化学习系统，在全国范围内降低教育成本和提高质量。活动包括综合方案，以增加妇女和代表性不足的少数群体在计算科学方面的参与。从技术角度来看，研究者追求三个研究主题：(I)设计可扩展的非凸算法来学习给定的一系列独立的静态和/或时变的局部测量的未知图的边(和权重)；(Ii)设计新的近似算法以利用给定图的结构来实现复杂系统中可扩展的事后决策；(Iii)开发可证明的算法来训练特殊的人工神经网络家族，并填补神经网络学习的严密理论和实践之间的空白。将使用来自工程应用的真实世界数据，包括社会网络数据、高速公路监控数据和流体流动模拟数据，对上述每个主题的进展进行广泛评估。与这些应用领域的领域专家的合作将确保这个项目产生的新理论、工具和软件将带来有意义的社会效益。

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.