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

BIGDATA：F：协作研究：度量空间中可扩展图距离的设计和计算：统一的多尺度可解释视角

• 批准号: 1741197
• 负责人: Stratis Ioannidis
• 金额: $ 102.4万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2023-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1741197&HistoricalAwards=false
• 关键词: BIGDATA; Collaborative; Research; Design; Computation

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.

现实世界现象作为图表（又称网络）的表示形式无处不在，从社会和信息网络到技术，生物学，化学和大脑网络。许多图形挖掘任务 - 包括聚类，异常检测，最近的邻居，相似性搜索，模式识别和转移学习 - 都需要有效计算的图之间的距离测量。图之间的现有距离测量值为理想。他们绝大多数是基于启发式方法。许多人没有扩展到具有数百万个节点的图形；其他人不满足非负，积极定义，对称性和三角形不平等的度量特性。该项目研究的正式数学基础涵盖了一个克服这些局限性的图形距离家族，重点是生物学和社交网络分析中的现实应用。它还提供了一种通用方法，用于使该家族中图形距离指标的计算在大量图形上具有数百万个节点，并在云计算资源上进行扩展。此项目研究，设计和评估满足以下六个属性的满足的图形距离：（1）它们是可扩展的 - 即，它们在运行时非常快速地实现运行时，并在计算中实现了快速的计算。 （2）它们是指标 - 即，它们满足了阴性，积极的定义，对称性和三角形不平等。 （3）通过与“化学距离”进行比较，它们是歧视性的，该比较发现两个图之间的最佳映射可以最大程度地减少边缘差异。 （4）它们是统计上的 - 即，它们具有置信区间。 （5）他们可以合并有关节点和链接的辅助信息。 （6）它们可以解释为主题专家。该项目没有提供单个指标，而是探索了这样的图形距离指标的家庭。它还使用乘数的交替方向方法（ADMM）提供了通用方法，以通过数百万节点的大量图并平行该家族中图形距离指标的计算。在云计算基础架构上使用Apache Spark在大量的现实图表上评估了所提出的指标。

项目成果

STABLE: Identifying and Mitigating Instability in Embeddings of the Degenerate Core

• DOI: 10.1137/1.9781611977653.ch46
• 发表时间: 2023
• 作者: David Liu;Tina Eliassi-Rad

Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization

• DOI: 10.1137/20m1352132
• 发表时间: 2021-01
• 期刊: SIAM J. Math. Data Sci.
• 作者: Leonardo A. B. Tôrres;Kevin S. Chan;Hanghang Tong;T. Eliassi-Rad

Multilevel Network Alignment

• DOI: 10.1145/3308558.3313484
• 发表时间: 2019-05
• 期刊: The World Wide Web Conference
• 作者: Si Zhang;Hanghang Tong;Ross Maciejewski;Tina Eliassi-Rad

The Why, How, and When of Representations for Complex Systems

• DOI: 10.1137/20m1355896
• 发表时间: 2021-09-01
• 期刊: SIAM REVIEW
• 影响因子: 10.2
• 作者: Torres, Leo;Blevins, Ann S.;Eliassi-Rad, Tina
• 通讯作者: Eliassi-Rad, Tina

Massively Distributed Graph Distances

• DOI: 10.1109/tsipn.2020.3022003
• 发表时间: 2020
• 期刊: IEEE Transactions on Signal and Information Processing over Networks
• 影响因子: 3.2
• 作者: Armin Moharrer;Jasmin Gao;Shikun Wang;José Bento;Stratis Ioannidis