CAREER: Advances in Graph Learning and Inference

基于图的数据处理算法影响各种应用领域，从交通网络、人工智能系统、手机网络、社交网络和Web。然而，新兴的大数据时代带来了关键的概念挑战：实践中使用的几种现有的基于图的方法表现出不合理的高运行时间;其他几种方法在缺乏正确性保证的情况下运行。这些挑战严重威胁到它们所属的高层决策系统的安全性和可靠性。这项研究为图学习和推理引入了一个创新的新计算框架，以解决这些挑战。该项目研究的具体应用包括：更好地监测道路拥堵和及时识别交通事故的方法;对社交网络中复杂事件的根本原因分析;以及设计更好的个性化学习系统，降低全国范围内的教育成本并提高质量。活动包括综合方案，以提高妇女和代表性不足的少数民族在计算科学的参与。从技术的角度来看，研究者追求三个研究主题：（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.