Massively Distributed Graph Distances
Massively Distributed Graph Distances
复制标题
DOI：
10.1109/tsipn.2020.3022003
复制
发表时间：
2020
影响因子：
3.2
通讯作者：
Armin Moharrer;Jasmin Gao;Shikun Wang;José Bento;Stratis Ioannidis
中科院分区：
文献类型：
--
作者：
Armin Moharrer;Jasmin Gao;Shikun Wang;José Bento;Stratis Ioannidis
图距离（或相似性）分数用于几个图挖掘任务，包括异常检测，最近邻和相似性搜索，模式识别，迁移学习和聚类。图距离是度量，特别是满足三角不等式，具有理论和经验优势。作为度量的著名图距离包括化学距离或Chartrand-Kubiki-Shultz（CKS）距离。不幸的是，两者都是计算上难以处理的。最近的努力提出使用化学和CKS距离的凸松弛。虽然距离计算成为凸优化问题下，这些松弛，变量的数量是二次的图形大小，这使得传统的优化算法，即使是小图禁止。我们提出了一个分布式的方法大规模并行化这个问题，使用交替方向乘法（ADMM）。我们的解决方案使用了一种新的，分布式二分法计算$p$-范数邻近算子作为一个积木。我们通过在多个并行环境中进行实验来证明其可扩展性。
Graph distance (or similarity) scores are used in several graph mining tasks, including anomaly detection, nearest neighbor and similarity search, pattern recognition, transfer learning, and clustering. Graph distances that are metrics and, in particular, satisfy the triangle inequality, have theoretical and empirical advantages. Well-known graph distances that are metrics include the chemical or the Chartrand-Kubiki-Shultz (CKS) distances. Unfortunately, both are computationally intractable. Recent efforts propose using convex relaxations of the chemical and CKS distances. Though distance computation becomes a convex optimization problem under these relaxations, the number of variables is quadratic in the graph size; this makes traditional optimization algorithms prohibitive even for small graphs. We propose a distributed method for massively parallelizing this problem using the Alternating Directions Method of Multipliers (ADMM). Our solution uses a novel, distributed bisection algorithm for computing a $p$-norm proximal operator as a building block. We demonstrate its scalability by conducting experiments over multiple parallel environments.