Nothing Special   »   [go: up one dir, main page]

Skip to main content

CAGE: Cache-Aware Graphlet Enumeration

  • Conference paper
  • First Online:
String Processing and Information Retrieval (SPIRE 2023)

Abstract

When information is (implicitly or explicitly) linked in its own nature, and is modeled as a network, retrieving patterns can benefit from this linked structure. In networks, “graphlets” (connected induced subgraphs of a given size k) are the counterparts of textual n-grams, as their frequency and shape can give powerful insights in the structure of a network and the role of its nodes. Differently from n-grams, the number of graphlets increases dramatically with their size k. We aim to push the exact enumeration of graphlets as far as possible, as enumeration (contrary to counting or approximation) gives the end-user the flexibility of arbitrary queries and restrictions on the graphlets found. For this, we exploit combinatorial and cache-efficient design strategies to cut the computational cost. The resulting algorithm CAGE (Cache-Aware Graphlet Enumeration) outperforms existing enumeration strategies by at least an order of magnitude, exhibiting a low number of L1-L2-L3 cache misses in the CPU. It is also competitive with the fastest known counting algorithms, without having their limitations on k.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 74.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Here \(G \setminus \{u\}\) is G without u and its incident edges.

  2. 2.

    We are not directly controlling the cache, but rather allowing the algorithm to run cache-friendly by making standard assumptions on the associative cache [8].

  3. 3.

    This idea can be generalized to \(k-4\), \(k-5\), and so on, but there is no payoff going further than \(k-3\) in practice as there are too many cases to handle.

  4. 4.

    https://github.com/DavideR95/CAGE.

  5. 5.

    This timeout is due to the size of the data gathered by VTune, which grows quickly over time.

  6. 6.

    i.e. the runtime raised a bad_alloc exception or a segmentation fault while reading the input graph.

References

  1. Ahmed, N.K., Neville, J., Rossi, R.A., Duffield, N.: Efficient graphlet counting for large networks. In: 2015 IEEE International Conference on Data Mining, pp. 1–10. Atlantic City, NJ, USA, IEEE (2015)

    Google Scholar 

  2. Aparício, D., Ribeiro, P., Silva, F.: Graphlet-orbit transitions (GoT): a fingerprint for temporal network comparison. PLoS ONE 13(10), e0205497 (2018)

    Article  Google Scholar 

  3. Aparício, D., Ribeiro, P., Silva, F., Silva, J.: Finding dominant nodes using graphlets. In: Cherifi, H., Gaito, S., Mendes, J.F., Moro, E., Rocha, L.M. (eds.) COMPLEX NETWORKS 2019. SCI, vol. 881, pp. 77–89. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-36687-2_7

    Chapter  Google Scholar 

  4. Bhuiyan, M.A., Rahman, M., Rahman, M., Al Hasan, M.: Guise: uniform sampling of graphlets for large graph analysis. In: 2012 IEEE 12th International Conference on Data Mining, pp. 91–100. IEEE (2012)

    Google Scholar 

  5. Bressan, M., Chierichetti, F., Kumar, R., Leucci, S., Panconesi, A.: Motif counting beyond five nodes. ACM TKDD 12(4), 1–25 (2018)

    Article  Google Scholar 

  6. Dutta, A., Riba, P., Lladós, J., Fornés, A.: Hierarchical stochastic graphlet embedding for graph-based pattern recognition. Neural Comput. Appl. 32(15), 11579–11596 (2020)

    Article  Google Scholar 

  7. Elenberg, E.R., Shanmugam, K., Borokhovich, M., Dimakis, A.G.: Beyond triangles: a distributed framework for estimating 3-profiles of large graphs. In: ACM SIGKDD, pp. 229–238 (2015)

    Google Scholar 

  8. Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. ACM Trans. Algorithms 8(1), 4:1–4:22 (2012)

    Google Scholar 

  9. Harris, S.L., Harris, D.: 8 - memory systems. In: Harris, S.L., Harris, D. (eds.) Digital Design and Computer Architecture, pp. 498–541. Morgan Kaufmann, Burlington (2022)

    Google Scholar 

  10. Jazayeri, A., Yang, C.C.: Motif discovery algorithms in static and temporal networks: a survey. J. Complex Netw. 8(4), cnaa031 (2020)

    Google Scholar 

  11. Kashani, Z.R.M., et al.: Kavosh: a new algorithm for finding network motifs. BMC Bioinform. 10(1), 318 (2009)

    Article  Google Scholar 

  12. Komusiewicz, C., Sommer, F.: Enumerating connected induced subgraphs: improved delay and experimental comparison. Discret. Appl. Math. 303, 262–282 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  13. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (2014). http://snap.stanford.edu/data

  14. Marino, A. , Crescenzi, P.: LASAGNE Networks: Laboratory of Algorithms, modelS, and Analysis of Graphs and NEtworks (2015). http://www.pilucrescenzi.it/lasagne/content/networks.html

  15. Melckenbeeck, I., Audenaert, P., Colle, D., Pickavet, M.: Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. Bioinformatics 34(8), 1372–1380 (2017)

    Article  Google Scholar 

  16. Melckenbeeck, I., Audenaert, P., Van Parys, T., Van De Peer, Y., Colle, D., Pickavet, M.: Optimising orbit counting of arbitrary order by equation selection. BMC Bioinform. 20(1), 1–13 (2019)

    Article  Google Scholar 

  17. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824–827 (2002)

    Article  Google Scholar 

  18. Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Paredes, P., Ribeiro, P.: Towards a faster network-centric subgraph census. In: IEEE/ACM ASONAM, pp. 264–271, New York, NY, USA, ACM (2013)

    Google Scholar 

  20. Pinar, A., Seshadhri, C., Vishal, V.: Escape: efficiently counting all 5-vertex subgraphs. In: The Web Conference (WWW), pp. 1431–1440 (2017)

    Google Scholar 

  21. Pržulj, N.: Biological network comparison using graphlet degree distribution. Bioinformatics 23(2), e177–e183 (2007)

    Article  Google Scholar 

  22. Ribeiro, P., Paredes, P., Silva, M.E., Aparicio, D., Silva, F.: A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv. 54(2), 1–36 (2021)

    Article  Google Scholar 

  23. Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015)

    Google Scholar 

  24. Ruskey, F.: Combinatorial generation. Preliminary Working Draft, vol. 11, pp. 20. University of Victoria, Victoria, BC, Canada (2003)

    Google Scholar 

  25. Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379–423 (1948)

    Article  MathSciNet  MATH  Google Scholar 

  26. Shervashidze, N., Vishwanathan, S.V.N., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: van Dyk, D., Welling, M. (eds.) AISTATS, vol. 5, pp. 488–495 (2009). PMLR 16–18

    Google Scholar 

  27. Shioura, A., Tamura, A., Uno, T.: An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J. Comput. 26(3), 678–692 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  28. Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theoret. Comput. Sci. 363(1), 28–42 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  29. Wang, P., Lui, J.C., Ribeiro, B., Towsley, D., Zhao, J., Guan, X.: Efficiently estimating motif statistics of large networks. ACM TKDD 9(2), 1–27 (2014)

    Article  Google Scholar 

  30. Wang, P., et al.: Moss-5: a fast method of approximating counts of 5-node graphlets in large graphs. IEEE TKDE 30(1), 73–86 (2017)

    Google Scholar 

  31. Wernicke, S.: Efficient detection of network motifs. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 347–359 (2006)

    Article  Google Scholar 

  32. Windels, S.F., Malod-Dognin, N., Pržulj, N.: Graphlet eigencentralities capture novel central roles of genes in pathways. PLoS ONE 17(1), e0261676 (2022)

    Article  Google Scholar 

Download references

Acknowledgements

Work partially supported by MIUR project n. 20174LF3T8 Algorithms for Harnessing networked Data (AHeAD).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Davide Rucci .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Conte, A., Grossi, R., Rucci, D. (2023). CAGE: Cache-Aware Graphlet Enumeration. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds) String Processing and Information Retrieval. SPIRE 2023. Lecture Notes in Computer Science, vol 14240. Springer, Cham. https://doi.org/10.1007/978-3-031-43980-3_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-43980-3_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-43979-7

  • Online ISBN: 978-3-031-43980-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics