On linear algebraic algorithms for the subgraph matching problem and its variants
Tóm tắt
For a given simple data graph G and a simple query graph H, the subgraph matching problem is to find all the subgraphs of G, each isomorphic to H. There are many combinatorial algorithms for it and its counting version, which are predominantly based on backtracking with several pruning techniques. Much less is known about linear algebraic (LA, for short), i.e., adjacency matrix algebra, algorithms for this problem. Revisiting old ideas of J. Nešetřil and S. Poljak, which reduce the general case to the case of clique-queries, and updating them, we present the first LA algorithm for the subgraph matching/counting problem. For the k-clique matching/counting problem, we present static and dynamic LA algorithms, which may be of independent interest. For the k-clique counting problem, we also provide results of computational experiments of our solver with some large graphs and several k, which speed up results of several recent solvers for it.
Từ khóa
Tài liệu tham khảo
Ahmed, N., et al.: Graphlet decomposition: framework, algorithms, and applications. Knowl. Inf. Syst. 50(3), 689–722 (2017)
Alon, N., et al.: Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13), 241–249 (2008)
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17, 209–223 (1997)
Bonne, M., Censor-Hillel, K.: Distributed detection of cliques in dynamic networks. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) Proceedings of International Colloquium on Automata, Languages, and Programming, pp 132:1–132:15. Dagstuhl Publishing (2019)
Chakaravarthy, V., et al.: Subgraph counting: Color coding beyond trees. In: O’Conner, L. (ed.) International Symposium on Parallel and Distributed Processing Symposium Proceedings, pp 2–11. Piscataway, IEEE (2016)
Chen, L., et al.: A GraphBLAS approach for subgraph counting. ArXiv, https://doi.org/10.48550/arXiv.1903.04395.
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)
Danisch, M., Balalau, O., Sozio, M.: Listing \(k\)-cliques in sparse real-world graphs. In: Champin, P.-A. et al. (eds.) Proceedings of International Conference on World Wide Web, pp 589–598. International WWW Conference Committee (2018)
Dave, V., Ahmed, N., Hasan, M.: PE-CLoG: Counting edge-centric local graphlets. In: Nie, J-Y et al. (eds.) Proceedings of International Conference on Big Data, pp 586–595. IEEE, Piscataway (2017)
Dhulipala, L., Liu, Q., Shun, J., Yu, S.: Parallel batch-dynamic \(k\)-clique counting. In: Shapira, M. (ed.) Proceedings of Symposium on Algorithmic Principles of Computer Science, pp. 129–143. SIAM, Philadelphia (2021)
Dvorak, Z., Tuma, V.: A dynamic data structure for counting subgraphs in sparse graphs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) Proceedings of Workshop on Algorithms and Data Structures, pp. 304–315. Springer-Verlag, Berlin (2013)
Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci. 326(1–3), 57–67 (2004)
Eppstein, D.: Arboricity and bipartite subgraph listing algorithms. Inf. Process. Lett. 51(4), 207–211 (1994)
Eppstein, D., Goodrich, M., Strash, D., Trott, L.: Extended dynamic subgraph statistics using h-index parameterized data structures. Theoret. Comput. Sci. 447, 44–52 (2012)
Eppstein, D., Spiro, E.: The h-index of a graph and its application to dynamic subgraph statistics. In: Dehne, F., Gavrilova, M., Sack, J., Tóth, C. (eds.) Proceedings of Workshop on Algorithms and Data Structures, pp 278–289. Springer-Verlag, Berlin (2009)
Finocchi, F., Finocchi, M., Fusco, E.: Clique counting in MapReduce: algorithms and experiments. J. Experimen. Algorithmics 20, 1.7:1-1.7:20 (2015)
Goodrich, M., Pszona, P.: External-memory network analysis algorithms for naturally sparse graphs. In: Demetrescu, C., Halldórsson, M (eds.) Proceedings of European Symposium on Algorithms, pp 664–676. 2011. Springer-Verlag, Berlin (2011)
Greyser, V., Soszynski, A., Kao, E.: Leveraging linear algebra to count and enumerate simple subgraphs. In: Proceedings of High Performance Extreme Computing Conference, pp. 1-8. IEEE, Piscataway (2020)
Jain, S., Seshadhri., C.: The power of pivoting for exact clique counting. In: Caveree, J., Hu, B., Lalmas, M., Wang, W. (eds.) Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 268–277. Association for Computing Machinery, New York (2020)
Kara, A., et al.: Counting triangles under updates in worst-case optimal time. In: Barcelo, P., Calautti, M. (eds.) Proceedings of International Conference on Database Theory, pp 4:1–4:18. Dagstuhl Publishing (2019)
Kepner, J., Gilbert, J.: Graph algorithms in the language of linear algebra. SIAM, Philadelphia (2011)
Kloks, T., Kratsch, D., Müller, H.: Finding and counting small induced subgraphs efficiently. Inform. Process. Lett. 74(3–4), 115–121 (2000)
Lai, L., et al.: Distributed subgraph matching on timely dataflow. Proc. VLDB Endow. 12(10), 1099–1112 (2019)
Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoret. Comput. Sci. 407(1–3), 458–473 (2008)
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection.http://snap.stanford.edu/data (2022). Accessed 30 December 2022
López-Presa, J., Chiroque, L., Anta, A.: Novel techniques to speed up the computation of the automorphism group of a graph. J. Appl. Math. 2014(934637), 15 (2014)
Makkar, D., Bader, D., Green, O.: Exact and parallel triangle counting in dynamic graphs. In: Smari, W. (ed.) Proceedings of International Conference on High Performance Computing and Simulation, pp 2–12. IEEE, Piscataway (2017)
McCay, B., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94–112 (2014)
Mhedhbi, A., Salihoglu, S.: Optimizing subgraph queries by combining binary and worst-case optimal joins. Proc. VLDB Endow. 12(11), 1692–1704 (2019)
Nešetřil, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 26(2), 415–419 (1985)
Papadimitriou, C., Yannakakis, M.: The clique problem for planar graphs. Inf. Process. Lett. 13, 131–133 (1981)
Pinar, A., Seshadhri,C., Vishal, V.: ESCAPE: Efficiently counting all 5-vertex subgraphs. In: Barrett, R., Cummings, R. (eds.) Proceedings of International Conference on World Wide Web, pp. 1431–1440. International WWW Conference Committee (2017)
Shi, J., Dhulipala, L., Shun, J.: Parallel clique counting and peeling algorithms. In: Bender, M., Gilbert, J., Hendrickson, B., Sullivan, B. (eds.) Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, pp. SIAM, Philadelphia (2021)
Stoichev, S.: New exact and heuristic algorithms for graph automorphism group and graph isomorphism. ACM J. Experimen. Algorithmics 24(1.15), 1–27 (2019)
Sun, Z., et al.: Efficient subgraph matching on billion node graphs. Proc. VLDB Endow. 5(9), 788–799 (2012)
Vassilevska, V.: Efficient algorithms for clique problems. Inf. Process. Lett. 109(4), 254–257 (2009)
Watts, D., Strogatz, S.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998)