Massively Distributed Graph Distances

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Massively Distributed Graph Distances

Armin Moharrer; Jasmin Gao; Shikun Wang; José Bento; Stratis Ioannidis

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.

SPS on Twitter

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar