Chakraborty, Sourav ;
Ghosh, Arijit ;
Mishra, Gopinath ;
Sen, Sayantan
Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds
Abstract
The graph isomorphism distance between two graphs G_u and G_k is the fraction of entries in the adjacency matrix that has to be changed to make G_u isomorphic to G_k. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in the query model. In other words, if G_k is a known graph and G_u is an unknown graph whose adjacency matrix has to be accessed by querying the entries, what is the query complexity for testing whether the graph isomorphism distance between G_u and G_k is less than γ₁ or more than γ₂, where γ₁ and γ₂ are two constants with 0 ≤ γ₁ < γ₂ ≤ 1. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The nontolerant version (where γ₁ is 0) has been studied by Fischer and Matsliah (SICOMP'08).
In this paper, we prove a (interesting) connection between tolerant graph isomorphism testing and tolerant testing of the well studied Earth Mover’s Distance (EMD). We prove that deciding tolerant graph isomorphism is equivalent to deciding tolerant EMD testing between multisets in the query setting. Moreover, the reductions between tolerant graph isomorphism and tolerant EMD testing (in query setting) can also be extended directly to work in the two party AliceBob communication model (where Alice and Bob have one graph each and they want to solve tolerant graph isomorphism problem by communicating bits), and possibly in other sublinear models as well.
Testing tolerant EMD between two probability distributions is equivalent to testing EMD between two multisets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multiset with replacement. In this paper, our (main) contribution is to introduce the problem of {(tolerant) EMD testing between multisets (over Hamming cube) when we get samples from the unknown multiset without replacement} and to show that this variant of tolerant testing of EMD is as hard as tolerant testing of graph isomorphism between two graphs. {Thus, while testing of equivalence between distributions is at the heart of the nontolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample without replacement) is at the heart of tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multisets (when we get samples without replacement) opens an entirely new direction in the world of testing properties of distributions.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2021.34,
author = {Chakraborty, Sourav and Ghosh, Arijit and Mishra, Gopinath and Sen, Sayantan},
title = {{Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {34:134:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14727},
URN = {urn:nbn:de:0030drops147273},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.34},
annote = {Keywords: Graph Isomorphism, Earth Mover Distance, Query Complexity}
}
15.09.2021
Keywords: 

Graph Isomorphism, Earth Mover Distance, Query Complexity 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 