Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

TL;DR

This paper establishes a fundamental equivalence between testing graph isomorphism (GI) and testing Earth Mover's Distance (EMD) between multisets, particularly in the challenging setting where samples are drawn without replacement. This connection reveals that approximating GI is as hard as approximating EMD in this specific sampling model, offering new insights into the complexity of both problems.

What Problem Does This Paper Address?

The paper delves into the computational complexity of tolerant graph isomorphism (GI) testing. In simpler terms, GI asks if two graphs have the same structure. Tolerant GI testing is a more relaxed version: given two graphs, we want to know if they are "close" to being isomorphic (meaning only a small fraction of edges need to be changed to make them isomorphic) or if they are "far" from being isomorphic. The authors focus on the query model, where one graph is known, and the other is accessed by querying its adjacency matrix.

A key challenge in this area is understanding the query complexity – how many queries are needed to distinguish between "close" and "far" cases. While the non-tolerant version of GI testing has been studied, the tolerant version, especially in the query model, remained less understood. The paper bridges this gap by connecting it to another fundamental problem: Earth Mover's Distance (EMD). EMD measures the "cost" of transforming one probability distribution into another. The paper specifically investigates EMD in the context of multisets and, crucially, when samples are drawn without replacement, a scenario that poses unique algorithmic challenges.

Methods

The core of the paper's contribution lies in establishing a reduction between tolerant GI testing and tolerant EMD testing of multisets. This means they show that solving one problem can be used to solve the other, implying they have similar computational hardness.

  • Lower Bound (GI is as hard as EMD): The authors construct a novel gadget that transforms a tolerant EMD testing problem (with samples without replacement) into a tolerant GI testing problem. This construction is intricate and relies on carefully designed graphs whose structure encodes information about the multisets. The key insight here is that the difficulty of distinguishing between EMD values in the "without replacement" sampling model directly translates to the difficulty of distinguishing between GI distances.
  • Upper Bound (EMD is as hard as GI): Conversely, they show how a tolerant EMD tester can be used as a black box to build an algorithm for tolerant GI testing. This involves phases of sampling subsets of vertices, finding embeddings, and using the EMD tester to check consistency. The use of EMD is crucial here, as it allows for a more flexible notion of "closeness" compared to simply checking for exact matches, which is necessary for the tolerant version of GI.

A significant aspect of their methodology is the focus on sampling without replacement for EMD testing. This is a less standard model than sampling with replacement, and the paper introduces and analyzes its complexity.

Datasets

Not discussed in the paper. The problems are defined on abstract graphs and multisets, not specific datasets.

Key Insights and Ideas

  • Fundamental Equivalence: The most significant insight is the direct equivalence between tolerant GI testing and tolerant EMD testing of multisets when sampling without replacement. This suggests that these seemingly different problems are deeply intertwined in terms of their computational complexity.
  • The Importance of "Without Replacement": The paper highlights that the "without replacement" sampling model for EMD is not just a minor variation but introduces a distinct algorithmic challenge. The hardness of tolerant GI testing is shown to be intrinsically linked to this specific sampling model for EMD.
  • Tolerant vs. Non-Tolerant: The paper emphasizes how the tolerant nature of the problems (allowing for small errors) necessitates different approaches compared to the non-tolerant versions. For instance, using EMD testers instead of equivalence testers is crucial for the tolerant GI algorithm.
  • Query Complexity: The work provides tight bounds on the query complexity for tolerant GI testing, showing it's essentially dictated by the complexity of tolerant EMD testing in the "without replacement" setting.

Key Results

  • Theorem 1.4 (Main Result): The query complexity of tolerant GI testing is equivalent (up to polylogarithmic factors) to the query complexity of tolerant EMD testing of multisets with samples drawn without replacement. Specifically, $Q_{GI}(G_u, G_k) = \tilde{O}(Q_{WOREMD}(n))$.
  • Lower Bound: Tolerant GI testing requires $\Omega(Q_{WOREMD}(n))$ queries. This implies that approximating GI is at least as hard as approximating EMD in this sampling model.
  • Upper Bound: An algorithm for tolerant GI testing is presented with a query complexity of $\tilde{O}(Q_{WOREMD}(n))$, demonstrating that the two problems are indeed computationally equivalent.
  • Connection to Communication Complexity: The reductions presented also hold for the communication complexity model, suggesting a similar equivalence between GI and EMD in that setting.

Limitations and Future Work

  • Polylogarithmic Factors: While the paper establishes equivalence, the exact polylogarithmic factors in the reductions are not always precisely determined, which is common in theoretical computer science.
  • Open Questions: The authors pose several open questions:
  • What is the exact query complexity of tolerant EMD testing when sampling without replacement?
  • What is the randomized communication complexity of tolerant GI testing?
  • What is the query complexity of tolerant GI testing when both graphs are unknown?
  • General Metric Spaces: The current work focuses on the Hamming cube for EMD. Extending these results to more general metric spaces could be a future direction.

Summary updated

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 non-tolerant 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 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 with replacement. In this paper, our (main) 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.
BibTeX
@inproceedings{chakraborty2021interplay,
  author = {Sourav Chakraborty and Arijit Ghosh and Gopinath Mishra and Sayantan Sen},
  title = {{Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds}},
  booktitle = {APPROX-RANDOM},
  year = {2021},
  doi = {10.4230/lipics.approx/random.2021.34},
}
Figure