Massively Distributed Graph Distances

doi:10.1109/TSIPN.2020.3022003

Massively Distributed Graph Distances

2020-01-01

3

OA

AI

DOI：10.1109/TSIPN.2020.3022003

Original

Save

View PDF

Abstract

En 中文

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 formassively 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.

Keywords:

ADMM

distributed algorithms

graph matching

optimization

Massively Distributed Graph Distances

Abstract

AI Summary

Journal

Organization