BIGDATA: F: Collaborative Research: Design and Computation of Scalable Graph Distances in Metric Spaces: A Unified Multiscale Interpretable Perspective

将真实世界现象表示为图形(也称为网络)无处不在，从社会和信息网络，到技术、生物、化学和大脑网络。许多图挖掘任务--包括聚类、异常检测、最近邻、相似性搜索、模式识别和迁移学习--都需要有效地计算图之间的距离。现有的图之间的距离度量还有很多需要改进的地方。它们绝大多数是基于启发式的。许多不能扩展到有数百万个节点的图；其他的不满足非负性、正定性、对称性和三角不等度量性质。这个项目研究了一个正式的数学基础，涵盖了一系列克服这些限制的图距离，重点是在生物学和社会网络分析中的现实世界应用。该项目研究、设计和评估了满足以下六个性质的图距离：(1)它们是可伸缩的--即它们在运行时是严格次二次的，并且在并行计算时获得了加速比。(2)它们是度量--即它们满足非负性、正定性、对称性和三角不等性。(3)它们是区分性的，通过与“化学距离”的比较来衡量，“化学距离”找到了两个图之间的最优映射，使边缘差异最小化。(4)它们在统计上是稳健的--即它们有可信区间。(5)它们可以结合节点和链路上可用的辅助信息。(6)它们是主题专家可以解释的。这个项目不是提供单一的度量，而是探索一系列这样的图距离度量。它还提供了一种通用的方法，使用交替方向乘子方法(ADMM)来并行计算这一族中具有数百万个节点的大规模图的图距离度量。建议的指标是在云计算基础设施上使用ApacheSpark在海量真实图形上进行评估的。

Representations of real-world phenomena as graphs (a.k.a. networks) are ubiquitous, ranging from social and information networks, to technological, biological, chemical, and brain networks. Many graph mining tasks -- including clustering, anomaly detection, nearest neighbor, similarity search, pattern recognition, and transfer learning -- require a distance measure between graphs to be computed efficiently. The existing distance measures between graphs leave a lot to be desired. They are overwhelmingly based on heuristics.  Many do not scale to graphs with millions of nodes; others do not satisfy the metric properties of non-negativity, positive definiteness, symmetry, and triangle inequality. This project studies a formal mathematical foundation covering a family of graph distances that overcome these limitations, focusing on real-world applications in biology and social network analysis. It also provides a universal methodology for parallelizing the computation of graph distance metrics within this family over massive graphs with millions of nodes, and scaling it over cloud computing resources.This project studies, designs, and evaluates graph distances that satisfy the following six properties: (1) They are scalable -- i.e., they are strictly subquadratic in runtime and achieve a speedup when computed in parallel. (2) They are metrics -- i.e., they satisfynon-negativity, positive definiteness, symmetry, and triangle inequality. (3) They are discriminative, as measured by comparisons to the "chemical distance", which finds the optimal mapping between two graphs that minimizes edge discrepancies. (4) They are statisticallyrobust -- i.e., they have confidence intervals. (5) They can incorporate auxiliary information available on nodes and links. (6) They are interpretable to subject matter experts. Rather than providing a single metric, this project explores a family of such graph distance metrics. It also provides a universal methodology, using the Alternating Directions Method of Multipliers (ADMM), to parallelizing the computation of graph distance metrics within this family over massive graphs with millions of nodes. The proposed metrics are evaluated over massive real-world graphs using Apache Spark on a cloud computing infrastructure.