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

Authors Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.34.pdf
  • Filesize: 0.9 MB
  • 23 pages

Document Identifiers

Author Details

Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Arijit Ghosh
  • Indian Statistical Institute, Kolkata, India
Gopinath Mishra
  • Indian Statistical Institute, Kolkata, India
Sayantan Sen
  • Indian Statistical Institute, Kolkata, India

Acknowledgements

The authors would like to thank an anonymous reviewer for pointing out a mistake in an earlier version of this paper, as well as the reviewers of RANDOM for various suggestions that improved the presentation of the paper.

Cite AsGet BibTex

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.34

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Graph Isomorphism
  • Earth Mover Distance
  • Query Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. arXiv preprint arXiv:1507.05952, 2015. Google Scholar
  2. Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff. Efficient sketches for earth-mover distance, with applications. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 324-330. IEEE, 2009. Google Scholar
  3. Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high-dimensional spaces. In SODA, volume 8, pages 343-352, 2008. Google Scholar
  4. Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn. Sketching and embedding are equivalent for norms. SIAM Journal on Computing, 47(3):890-916, 2018. Google Scholar
  5. László Babai. Graph Isomorphism in Quasipolynomial Time. In Proceedings of the 48th Annual ACM symposium on Theory of Computing, STOC, pages 684-697, 2016. Google Scholar
  6. Laszlo Babai and Sourav Chakraborty. Property Testing of Equivalence under a Permutation Group Action. ACM Transactions on Computation Theory (ToCT), 2010. Google Scholar
  7. László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The Graph Isomorphism Problem (Dagstuhl Seminar 15511). Dagstuhl Reports, 5(12):1-17, 2015. URL: https://doi.org/10.4230/DagRep.5.12.1.
  8. Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing Random Variables for Independence and Identity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, FOCS, pages 442-451, 2001. Google Scholar
  9. Clément L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020. Google Scholar
  10. Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Interplay between graph isomorphism and earth mover’s distance in the query and communication worlds. In Electron. Colloquium Comput. Complex., volume 27, page 135, 2020. Google Scholar
  11. Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2012. Google Scholar
  12. Khanh Do Ba, Huy L Nguyen, Huy N Nguyen, and Ronitt Rubinfeld. Sublinear time algorithms for earth mover’s distance. Theory of Computing Systems, 48(2):428-442, 2011. Google Scholar
  13. Eldar Fischer and Arie Matsliah. Testing Graph Isomorphism. SIAM Journal on Computing, 38(1):207-225, 2008. Google Scholar
  14. David Freedman. A remark on the difference between sampling with and without replacement. Journal of the American Statistical Association, 72(359):681-681, 1977. Google Scholar
  15. Oded Goldreich. Testing isomorphism in the bounded-degree graph model. Electron. Colloquium Comput. Complex., 26:102, 2019. URL: https://eccc.weizmann.ac.il/report/2019/102.
  16. Subhash Khot and Assaf Naor. Nonembeddability theorems via fourier analysis. Mathematische Annalen, 334(4):821-852, 2006. Google Scholar
  17. Reut Levi and Moti Medina. Distributed testing of graph isomorphism in the congest model. arXiv preprint arXiv:2003.00468, 2020. Google Scholar
  18. Chih-Long Lin. Hardness of Approximating Graph Transformation Problem. In Proceedings of the 5th International Symposium on Algorithms and Computation, ISAAC,, pages 74-82, 1994. Google Scholar
  19. Krzysztof Onak and Xiaorui Sun. The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 165-171, 2018. Google Scholar
  20. Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750-4755, 2008. Google Scholar
  21. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012-1042, 2006. Google Scholar
  22. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM Journal on Computing, 39(3):813-842, 2009. Google Scholar
  23. Shashank Singh and Barnabás Póczos. Minimax distribution estimation in wasserstein distance. arXiv preprint arXiv:1802.08855, 2018. Google Scholar
  24. Xiaorui Sun. On the Isomorphism Testing of Graphs. PhD thesis, Columbia University, 2016. Google Scholar
  25. Gregory Valiant and Paul Valiant. The Power of Linear Estimators. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 403-412, 2011. Google Scholar
  26. Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):429-455, 2017. Google Scholar
  27. Paul Valiant. Testing Symmetric Properties of Distributions. SIAM Journal on Computing, 40(6):1927-1968, 2011. Google Scholar
  28. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213. ACM, 1979. URL: https://doi.org/10.1145/800135.804414.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail