Document Open Access Logo

Some Vignettes on Subgraph Counting Using Graph Orientations (Invited Talk)

Author C. Seshadhri

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.3.pdf
  • Filesize: 0.68 MB
  • 10 pages

Document Identifiers

Author Details

C. Seshadhri
  • Department of Computer Science & Engineering, University of California, Santa Cruz, CA, USA

Funding

NSF DMS-2023495, CCF-1740850, 1908384, 1909790

Cite As Get BibTex

C. Seshadhri. Some Vignettes on Subgraph Counting Using Graph Orientations (Invited Talk). In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 3:1-3:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICDT.2023.3

Abstract

Subgraph counting is a fundamental problem that spans many areas in computer science: database theory, logic, network science, data mining, and complexity theory. Given a large input graph G and a small pattern graph H, we wish to count the number of occurrences of H in G. In recent times, there has been a resurgence on using an old (maybe overlooked?) technique of orienting the edges of G and H, and then using a combination of brute-force enumeration and indexing. These orientation techniques appear to give the best of both worlds. There is a rigorous theoretical explanation behind these techniques, and they also have excellent empirical behavior (on large real-world graphs). Time and again, graph orientations help solve subgraph counting problems in various computational models, be it sampling, streaming, distributed, etc. In this paper, we give some short vignettes on how the orientation technique solves a variety of algorithmic problems.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • subgraph counting
  • graph degeneracy
  • homomorphism counting
  • graph algorithms

Metrics

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

References

  1. Escape. URL: https://bitbucket.org/seshadhri/escape.
  2. Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick Duffield. Efficient graphlet counting for large networks. In International Conference on Data Mining, 2015. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  4. Suman K Bera, Amit Chakrabarti, and Prantar Ghosh. Graph coloring via degeneracy in streaming and other space-conscious models. In International Colloquium on Automata, Languages, and Programming (ICALP), 2020. Google Scholar
  5. Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. Journal of the ACM, 69(3), 2022. Google Scholar
  6. Suman K Bera, Noujan Pashanasangi, and C Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six. In Innovations in Theoretical Computer Science, 2020. Google Scholar
  7. Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 2315-2332, USA, 2021. Google Scholar
  8. Suman K Bera and C Seshadhri. How the degeneracy helps for triangle counting in graph streams. In Principles of Database Systems, pages 457-467, 2020. Google Scholar
  9. Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Counting graph homomorphisms. In Topics in discrete mathematics, pages 315-371. Springer, 2006. Google Scholar
  10. Marco Bressan. Faster subgraph counting in sparse graphs. In International Symposium on Parameterized and Exact Computation (IPEC), 2019. Google Scholar
  11. Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 83:2578-2605, 2021. Google Scholar
  12. Graham R Brightwell and Peter Winkler. Graph homomorphisms and phase transitions. Journal of combinatorial theory, series B, 77(2):221-262, 1999. Google Scholar
  13. Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In Symposium on Theory of Computing (STOC), pages 77-90, 1977. Google Scholar
  14. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14:210-223, 1985. Google Scholar
  15. Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci., 86(2):243-266, 1991. Google Scholar
  16. Jonathan Cohen. Graph twiddling in a MapReduce world. Computing in Science & Engineering, 11:29-41, 2009. Google Scholar
  17. J. Coleman. Social capital in the creation of human capital. American Journal of Sociology, 94:S95-S120, 1988. Google Scholar
  18. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 210-223, 2017. Google Scholar
  19. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1-3):315-323, 2004. Google Scholar
  20. Maximilien Danisch, Oana Denisa Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs. In Conference on the World Wide Web (WWW), pages 589-598, 2018. Google Scholar
  21. Holger Dell, Marc Roth, and Philip Wellnitz. Counting answers to existential questions. In International Colloquium on Automata, Languages, and Programming (ICALP), 2019. Google Scholar
  22. Josep Díaz, Maria Serna, and Dimitrios M Thilikos. Counting h-colorings of partial k-trees. Theoretical Computer Science, 281(1-2):291-309, 2002. Google Scholar
  23. Reinhard Diestel. Graph Theory, Fourth Edition. Springer, 2010. Google Scholar
  24. Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3-4):260-289, 2000. Google Scholar
  25. T. Eden, A. Levi, D. Ron, and C Seshadhri. Approximately counting triangles in sublinear time. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 614-633, 2015. Google Scholar
  26. T. Eden, D. Ron, and C. Seshadhri. Sublinear time estimation of degree distribution moments: The degeneracy connection. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 7:1-7:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.7.
  27. T. Eden, D. Ron, and C. Seshadhri. On approximating the number of k-cliques in sublinear time. In Symposium on Theory of Computing (STOC), pages 722-734, 2018. Google Scholar
  28. T. Eden and W. Rosenbaum. On sampling edges almost uniformly. In Symposium on Simplicity in Algorithms (SOSA), pages 1-9, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.7.
  29. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. ACM Journal of Experimental Algorithmics, 18, 2013. Google Scholar
  30. G. Fagiolo. Clustering in complex directed networks. Phys. Rev. E, 76:026107, August 2007. Google Scholar
  31. Irene Finocchi, Marco Finocchi, and Emanuele G. Fusco. Clique counting in mapreduce: Algorithms and experiments. ACM Journal of Experimental Algorithmics, 20, 2015. Google Scholar
  32. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892-922, 2004. Google Scholar
  33. G. Goel and J. Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 159-167. Springer, 2006. Google Scholar
  34. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  35. O. Goldreich and D. Ron. Approximating average parameters of graphs. Random Structures and Algorithms, 32(4):473-493, 2008. Google Scholar
  36. P. Holland and S. Leinhardt. A method for detecting structure in sociometric data. American Journal of Sociology, 76:492-513, 1970. Google Scholar
  37. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413-423, 1978. Google Scholar
  38. Shweta Jain and C. Seshadhri. A Fast and Provable Method for Estimating Clique Counts Using Turán’s Theorem. In Conference on the World Wide Web (WWW), pages 441-449, 2017. Google Scholar
  39. Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Conference on the World Wide Web (WWW), pages 441-449, 2017. Google Scholar
  40. Madhav Jha, C Seshadhri, and Ali Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Conference on the World Wide Web (WWW), pages 495-505, 2015. Google Scholar
  41. László Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18(3-4):321-328, 1967. Google Scholar
  42. László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012. Google Scholar
  43. David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30(3):417-427, 1983. Google Scholar
  44. C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39(1):12, 1964. Google Scholar
  45. J. Nešetřil and P. Ossana de Mendez. Sparsity: Graphs, Structures, and Algorithms. Springer, 2012. Google Scholar
  46. Mark Ortmann and Ulrik Brandes. Efficient orbit-aware triad and quad census in directed and undirected graphs. Applied network science, 2(1), 2017. Google Scholar
  47. Noujan Pashanasangi and C Seshadhri. Efficiently counting vertex orbits of all 5-vertex subgraphs, by evoke. In International Conference on Web Search and Data Mining (WSDM), pages 447-455, 2020. Google Scholar
  48. Ali Pinar, C Seshadhri, and Vaidyanathan Vishal. Escape: Efficiently counting all 5-vertex subgraphs. In Conference on the World Wide Web (WWW), pages 1431-1440, 2017. Google Scholar
  49. Marc Roth and Philip Wellnitz. Counting and finding homomorphisms is universal for parameterized complexity theory. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 2161-2180, 2020. Google Scholar
  50. Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Experimental and Efficient Algorithms, pages 606-609. Springer Berlin / Heidelberg, 2005. Google Scholar
  51. C. Seshadhri and Srikanta Tirthapura. Scalable subgraph counting: The methods behind the madness: WWW 2019 tutorial. In Conference on the World Wide Web (WWW), 2019. Google Scholar
  52. Jessica Shi, Laxman Dhulipala, and Julian Shun. Parallel clique counting and peeling algorithms. In Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA), pages 135-146, 2021. Google Scholar
  53. K. Shin, T. Eliassi-Rad, and C. Faloutsos. Patterns and anomalies in k-cores of real-world graphs with applications. Knowledge and Information Systems, 54(3):677-710, 2018. Google Scholar
  54. Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In Conference on the World Wide Web (WWW), pages 607-614, 2011. Google Scholar
  55. Johan Ugander, Lars Backstrom, and Jon M. Kleinberg. Subgraph frequencies: mapping the empirical and extremal geography of large graph collections. In Conference on the World Wide Web (WWW), pages 1307-1318, 2013. Google Scholar
  56. Stanford Network Analysis Project (SNAP). Available at URL: http://snap.stanford.edu/.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact