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