Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR20-135 | 22nd May 2022 13:53

Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds

RSS-Feed




Revision #3
Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Accepted on: 22nd May 2022 13:53
Downloads: 290
Keywords: 


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 $\gamma_1$ or more than $\gamma_2$, where $\gamma_1$ and $\gamma_2$ are two constants with $0\leq \gamma_1 < \gamma_2 \leq 1$. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where $\gamma_1$ 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 multi-sets 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 Alice-Bob 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 multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set \textbf{with} replacement. In this paper, our (main) contribution is to introduce the problem of \emph{(tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set \textbf{without} replacement} and to show that \emph{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 non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample \textbf{without} replacement) is at the heart of
tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples \textbf{without} replacement) opens an entirely new direction in the world of testing properties of distributions.



Changes to previous version:

Improved the writing.


Revision #2 to TR20-135 | 12th July 2021 22:58

Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds





Revision #2
Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Accepted on: 12th July 2021 22:58
Downloads: 411
Keywords: 


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 $\gamma_1$ or more than $\gamma_2$, where $\gamma_1$ and $\gamma_2$ are two constants with $0\leq \gamma_1 < \gamma_2 \leq 1$. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where $\gamma_1$ 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 multi-sets 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 Alice-Bob 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 multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set \textbf{with} replacement. In this paper, our (main) contribution is to introduce the problem of \emph{(tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set \textbf{without} replacement} and to show that \emph{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 non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample \textbf{without} replacement) is at the heart of
tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples \textbf{without} replacement) opens an entirely new direction in the world of testing properties of distributions.



Changes to previous version:

Added new results on Communication Complexity
To appear in RANDOM 2021


Revision #1 to TR20-135 | 11th July 2021 01:03

Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds





Revision #1
Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Accepted on: 11th July 2021 01:03
Downloads: 574
Keywords: 


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 $\gamma_1$ or more than $\gamma_2$, where $\gamma_1$ and $\gamma_2$ are two constants with $0\leq \gamma_1 < \gamma_2 \leq 1$. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where $\gamma_1$ 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 multi-sets 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 Alice-Bob 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 multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set \textbf{with} replacement. In this paper, our (main conceptual) contribution is to introduce the problem of \emph{(tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set \textbf{without} replacement} and to show that \emph{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 non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample \textbf{without} replacement) is at the heart of
tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples \textbf{without} replacement) opens an entirely new direction in the world of testing properties of distributions.



Changes to previous version:

Added new results on communication complexity.
To appear in RANDOM 21.


Paper:

TR20-135 | 9th September 2020 22:30

Estimation of Graph Isomorphism Distance in the Query World





TR20-135
Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Publication: 9th September 2020 23:48
Downloads: 880
Keywords: 


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 $\gamma_1$ or more than $\gamma_2$, where $\gamma_1$ and $\gamma_2$ are two constants with $0\leq \gamma_1 < \gamma_2 \leq 1$. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where $\gamma_1$ is $0$) has been studied by Fischer and Matsliah (SICOMP'08).

In this paper, we study both the upper and lower bounds of tolerant graph isomorphism testing. We prove an upper bound of $\widetilde{{\cal O}}(n)$ for this problem. Our upper bound algorithm crucially uses the tolerant testing of the well studied Earth Mover Distance (EMD), as the main subroutine, in a slightly different setting from what is generally studied in property testing literature.

Testing tolerant EMD between two probability distributions is equivalent to testing EMD between two multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set with replacement. In this paper, our (main conceptual) contribution is to introduce the problem of tolerant EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set 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 non-tolerant 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 multi-sets (when we get samples without replacement) opens an entirely new direction in the world of testing properties of distributions.



ISSN 1433-8092 | Imprint