CIF: Medium: Adaptive Diffusions for Scalable and Robust Learning over Graphs

每一个复杂系统的背后，无论是物理的、社会的、生物的，还是人为的，都隐藏着一个复杂的网络，它编码了其组件之间的相互作用。通过网络的统计学习有可能释放一个人对这类系统的行为进行推理的能力，理解它们的内在结构，并最终预测它们的演变。在“数据泛滥”的时代，兑现这一承诺并没有更近一步，因为巨大的挑战依然存在。其中包括：依靠稀缺的训练样本进行有效的预测；以透明的方式提供易于解释的结果；处理不可靠的数据或破坏学习过程的恶意企图；以及设法以及时和考虑资源的方式处理可能随时间变化的大规模网络。为了应对这些挑战，该项目开创了一个可扩展、可表达、可解释和健壮的多用途网络学习框架。预计将开发的工具箱将促进数据科学、网络科学、图形挖掘和大数据分析领域的尖端技术。因此，从计算生物学和神经科学到社会经济网络，它应该会影响和影响到广泛的新兴领域的技术转让。在教育方面，这项研究的多学科性质将为本科生和研究生提供引人入胜的体验，传播研究成果，并融合不同社区的想法。该项目的总体方法将图形学习统一在基于随机行走的扩散的原则框架下，目标是显著提高学习成绩，同时还确保可伸缩性和可靠性。这项研究由三个相互交织的推力组成，涉及：(T1)自适应扩散，用于在调整到任务和底层网络拓扑的网络上快速有效地学习；(T2)可扩展扩散，用于处理大规模和具有挑战性的网络；以及(T3)能够从不可信数据中学习的稳健扩散。T1中的新方法利用了精心构建的随机游动的“着陆概率”，并利用元信息和非线性扩散模型开辟了场所，以便在可能的动态图形上创新一系列学习任务。T2下的研究针对的是海量和具有挑战性的图形，其中需要一个令人望而却步的大着陆概率空间来确保高预测精度。最后，T3渴望应对使用图结构感知方法渗透网络的复杂对手，并调查防线，即使在大多数数据是恶意的情况下也是如此。分析和实验性能评估将评估与节点嵌入和图形卷积神经网络替代方案相关的新方法的优点。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Behind every complex system, be it physical, social, biological, or manmade, lies an intricate network that encodes the interactions between its components. Statistical learning over networks has the potential to unleash one's ability to reason about the behavior of such systems; to understand their innate structure; and, ultimately predict their evolution. In the era of 'data deluge,' fulfilling this promise has not moved closer, as formidable challenges remain. These include making effective predictions while relying on scarce training samples; providing easily explainable outcomes in a transparent way; dealing with unreliable data or malicious attempts to undermine the learning process; as well as managing to handle massive-scale networks that can change over time in a timely and resource-considerate fashion. Aspiring to address such challenges, this project pioneers a scalable, expressive, interpretable, and robust multi-purpose framework for learning over networks. The toolbox to be developed is expected to boost state-of-the-art in data science, network science, graph mining, and big data analytics. It should thus impact and effect technology transfer to a broad range of emerging fields, from computational biology and neuroscience to social-economic networks. On the educational front, the multidisciplinary nature of this research will provide engaging experiences for both undergraduate and graduate students, disseminate research findings, and cross-fertilize ideas from diverse communities.The overarching approach in this project unifies learning over graphs under a principled framework of random walk based diffusions with the goal of markedly improving learning performance, while also ensuring scalability and reliability. The research consists of three intertwined thrusts dealing with: (T1) Adaptive diffusions for fast and effective learning over networks tuned to the task and the underlying network topology; (T2) Scalable diffusions dealing with massive and challenging networks; and (T3) Robust diffusions capable of learning from untrusted data. The novel approach in T1 capitalizes on the 'landing probabilities' of judiciously constructed random walks, and opens venues leveraging meta-information, as well as nonlinear diffusion models, in order to innovate a gamut of learning tasks over possibly dynamic graphs. The research under T2 aims at massive and challenging graphs where a prohibitively large landing probability space is necessary to ensure high prediction accuracy. Finally, T3 aspires to cope with sophisticated adversaries employing graph structure-aware approaches to infiltrate the network, and investigates lines of defense even in settings where most data are malicious. Analytical and experimental performance evaluation will assess the merits of the novel approaches relative to node embedding and graph convolutional neural network alternatives.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.