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），并行计算的图距离度量在这个家庭超过数百万个节点的大规模图形。在云计算基础设施上使用Apache Spark对大量真实世界的图形进行评估。

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.