research-article

SLF: : A passive parallelization of subgraph isomorphism

Authors:

Mengting YuanAuthors Info & Claims

Volume 623, Issue C

Pages 900 - 914

https://doi.org/10.1016/j.ins.2022.12.033

Published: 01 April 2023 Publication History

Highlights

•

We propose SLF, a parallel approach for subgraph isomorphism algorithm based on tree searching.

•

We propose some strategies to reduce the sharing frequency and time spent sharing.

•

We analyze the parallelization overhead of SLF and previous methods.

•

The parallelization overhead of SLF is lower than previous methods’.

Abstract

Subgraph isomorphism is one of the most important graph query operations. Existing subgraph isomorphic parallelization methods suffer from redundant sharing or fine-grained parallelism. SLF, a parallel approach for subgraph isomorphism algorithm based on tree-search, is proposed in this paper. In SLF, threads are prevented from sharing tasks blindly by an “Ask for Sharing” mechanism. The “Low-depth Priority Sharing” rule filters out unnecessary sharing, which reduces the number of sharing. The context of shared tasks is represented by embedding, which reduces the time and memory usage of sharing. We prove that the parallelization overhead of SLF is smaller than that of previous method. The experimental results show that SLF achieves higher speedup and efficiency than state-of-the-art parallelization methods.

References

[1]

V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, A. Ferro, A subgraph isomorphism algorithm and its application to biochemical data, BMC Bioinform. 14 (S7) (2013) S13.

[2]

D. Luaces, J.R. Viqueira, J.M. Cotos, J.C. Flores, Efficient access methods for very large distributed graph databases, Inf. Sci. 573 (2021) 65–81.

[3]

J. Li, M.D. Ernst, Cbcd: Cloned buggy code detector, in: 2012 34th International Conference on Software Engineering (ICSE), IEEE, 2012, pp. 310–320.

[4]

G. Bouritsas, F. Frasca, S.P. Zafeiriou, M. Bronstein, Improving graph neural network expressivity via subgraph isomorphism counting, IEEE Trans. Pattern Anal. Mach. Intell.

[5]

V. Carletti, P. Foggia, P. Ritrovato, M. Vento, V. Vigilante, A parallel algorithm for subgraph isomorphism, in: International Workshop on Graph-Based Representations in Pattern Recognition, Springer, 2019, pp. 141–151.

[6]

B. Yang, K. Lu, Y.-H. Gao, X.-P. Wang, K. Xu, Gpu acceleration of subgraph isomorphism search in large scale graph, J. Central South Univ. 22 (6) (2015) 2238–2249.

[7]

R. Raman, O. van Rest, S. Hong, Z. Wu, H. Chafi, J. Banerjee, Pgx. iso: parallel and efficient in-memory engine for subgraph isomorphism, in: Proceedings of Workshop on GRAph Data management Experiences and Systems, 2014, pp. 1–6.

[8]

L. Zeng, L. Zou, M.T. Özsu, L. Hu, F. Zhang, Gsi: Gpu-friendly subgraph isomorphism, in: 2020 IEEE 36th International Conference on Data Engineering (ICDE), IEEE, 2020, pp. 1249–1260.

[9]

V. Bonnici, R. Giugno, N. Bombieri, An efficient implementation of a subgraph isomorphism algorithm for gpus, in: 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), IEEE, 2018, pp. 2674–2681.

[10]

C. McCreesh, P. Prosser, A parallel, backjumping subgraph isomorphism algorithm using supplemental graphs, in: International conference on principles and practice of constraint programming, Springer, 2015, pp. 295–312.

[11]

B. Archibald, F. Dunlop, R. Hoffmann, C. McCreesh, P. Prosser, J. Trimble, Sequential and parallel solution-biased search for subgraph algorithms, in: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer, 2019, pp. 20–38.

[12]

R.D. Blumofe, C.E. Leiserson, Scheduling multithreaded computations by work stealing, J. ACM (JACM) 46 (5) (1999) 720–748.

[13]

V. Carletti, P. Foggia, A. Saggese, M. Vento, Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3, IEEE Trans. Pattern Anal. Mach. Intell. 40 (4) (2017) 804–818.

[14]

J.R. Ullmann, An algorithm for subgraph isomorphism, J. ACM (JACM) 23 (1) (1976) 31–42.

[15]

C. Solnon, Alldifferent-based filtering for subgraph isomorphism, Artif. Intell. 174 (12–13) (2010) 850–864.

[16]

L. Kotthoff, C. McCreesh, C. Solnon, Portfolios of subgraph isomorphism algorithms, in: International Conference on Learning and Intelligent Optimization, Springer, 2016, pp. 107–122.

[17]

C. McCreesh, P. Prosser, J. Trimble, The glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants, in: International Conference on Graph Transformation, Springer, 2020, pp. 316–324.

[18]

L.P. Cordella, P. Foggia, C. Sansone, M. Vento, An improved algorithm for matching large graphs, in: 3rd IAPR-TC15 workshop on graph-based representations in pattern recognition, 2001, pp. 149–159.

[19]

L.P. Cordella, P. Foggia, C. Sansone, M. Vento, A (sub) graph isomorphism algorithm for matching large graphs, IEEE Trans. Pattern Anal. Mach. Intell. 26 (10) (2004) 1367–1372.

Digital Library

[20]

V. Carletti, P. Foggia, M. Vento, Vf2 plus: An improved version of vf2 for biological graphs, in: International Workshop on Graph-Based Representations in Pattern Recognition, Springer, 2015, pp. 168–177.

[21]

V. Carletti, P. Foggia, A. Saggese, M. Vento, Introducing vf3: A new algorithm for subgraph isomorphism, in: International Workshop on Graph-Based Representations in Pattern Recognition, Springer, 2017, pp. 128–139.

[22]

A. Jüttner, P. Madarasi, Vf2++–an improved subgraph isomorphism algorithm, Discrete Appl. Math. 242 (2018) 69–81.

[23]

H. Shang, Y. Zhang, X. Lin, J.X. Yu, Taming verification hardness: an efficient algorithm for testing subgraph isomorphism, Proceedings of the VLDB Endowment 1 (1) (2008) 364–375.

[24]

H. He, A.K. Singh, Query language and access methods for graph databases, in: Managing and mining graph data, Springer, 2010, pp. 125–160.

[25]

W.-S. Han, J. Lee, J.-H. Lee, Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases, in: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013, pp. 337–348.

[26]

P. Zhao, J. Han, On graph query optimization in large networks, Proceedings of the VLDB Endowment 3 (1–2) (2010) 340–351.

[27]

Z.A. Ansari, M. Abulaish, et al., An efficient subgraph isomorphism solver for large graphs, IEEE Access 9 (2021) 61697–61709.

[28]

X. Liu, H. Pan, M. He, Y. Song, X. Jiang, L. Shang, Neural subgraph isomorphism counting, in: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 1959–1969.

[29]

Z. Chen, L. Chen, S. Villar, J. Bruna, Can graph neural networks count substructures?, Adv. Neural Inform. Process. Syst. 33 (2020) 10383–10395.

[30]

K. Zhao, J.X. Yu, H. Zhang, Q. Li, Y. Rong, A learned sketch for subgraph counting, in: Proceedings of the 2021 International Conference on Management of Data, 2021, pp. 2142–2155.

[31]

V. Carletti, P. Foggia, A. Greco, A. Saggese, M. Vento, The vf3-light subgraph isomorphism algorithm: when doing less is more effective, in: Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), Springer, 2018, pp. 315–325.

[32]

S. Zampelli, Y. Deville, C. Solnon, Solving subgraph isomorphism problems with constraint programming, Constraints 15 (3) (2010) 327–353.

Index Terms

SLF: A passive parallelization of subgraph isomorphism

Index terms have been assigned to the content through auto-classification.

Recommendations

Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs

Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as ...
Finding a chain graph in a bipartite permutation graph

We present a polynomial-time algorithm for solving Subgraph Isomorphism where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. Subgraph Isomorphism is studied on graph classes.A polynomial-time algorithm is given ...
Parallel Planar Subgraph Isomorphism and Vertex Connectivity
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures

We present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bounded treewidth. Our randomized low depth algorithm has a near-linear work ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 623, Issue C

Apr 2023

932 pages

ISSN:0020-0255

Issue’s Table of Contents

Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 April 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents