Taming verification hardness: an efficient algorithm for testing subgraph isomorphism
The DOI matches its Crossref record; 28 of the 29 references it cites were found in a registry or an index.
Abstract
Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering -and- verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Although there are graph-based approaches that are potentially less vulnerable to such attacks, they are not feasible in practice [24] due to the NP nature of determining subgraph isomorphism [25,29,45].”
From Detecting Automatic Software Plagiarism via Token Sequence Normalization (2024) · cites this paper as [45]
Citations
Cites
(1979) · Cited by 43,841
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277 · cited 4×
“Comparing to the well adopted Ullman’s algorithm [13], QuickSI achieves up to 1-4 orders of magnitude speed-up.”
MethodInfluentialData Structures and Algorithms
(2003) · Series on software engineering and knowledge engineering · doi:10.1142/9789812791245 · Cited by 2,117
gSpan: graph-based substructure pattern mining
Yan, X., & Han, J. (2003) · 2002 IEEE International Conference on Data Mining, 2002. Proceedings. · doi:10.1109/icdm.2002.1184038 · Cited by 2,013 · cited 1×
“To overcome this problem, some recent work uses more complex and selective sub-structures as index features, mean-while adopt data mining techniques [15, 19] to improve performance and to reduce index size.”
MethodAn Automatic Method for Solving Discrete Programming Problems
Land, A. H., & Doig, A. G. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_5 · Cited by 1,988
An Automatic Method of Solving Discrete Programming Problems
Land, A. H., & Doig, A. G. (1960) · Econometrica · doi:10.2307/1910129 · Cited by 1,942
Data Structures and Algorithms
Wirth, N. (1984) · Scientific American · doi:10.1038/scientificamerican0984-60 · Cited by 1,418
Proceedings 2001 IEEE International Conference on Data Mining
(2001) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989492 · Cited by 768
Proceedings of the International Conference on Very Large Data Bases
Kerr, D. S. (1975) · ACM eBooks · Cited by 701
Research works printed but not linked: 2
- 10.5555/646514.695831 · doi:10.5555/646514.695831
- 10.5555/2993947.2993981 · doi:10.5555/2993947.2993981
Cited by
Items 301–400 of 494
A Subgraph Isomorphism-based Attack Towards Social Networks
Guo, M., Chi, C., Zheng, H., He, J., & Zhang, X. (2021) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1145/3498851.3499024 · Cited by 3
Mnemonic: A Parallel Subgraph Matching System for Streaming Graphs
Bhattarai, B. D., & Huang, H. H. (2022) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps53621.2022.00038 · Cited by 3
SICode: Embedding-Based Subgraph Isomorphism Identification for Bug Detection
Gong, Y., Nie, J., You, W., Shi, W., Huang, J., Liang, B., & Zhang, J. (2024) · IEEE International Conference on Program Comprehension (ICPC) · doi:10.1145/3643916.3646556 · Cited by 3
Subgraph matching-based reference placement for printed circuit board designs
Zhu, Z., Li, Y., Su, M., Zhang, S., Su, H., Xiao, Y., He, H., Chen, J., & Chang, Y. (2024) · The Journal of Supercomputing · doi:10.1007/s11227-024-06338-9 · Cited by 3
“Representative graph index-based methods include QuickSI [12], Spath Subgraph matching‑based reference placement for printed… [13], and TurboISO [14].”
Efficient processing of graph similarity search
Choi, R. H., & Chung, C. (2014) · World Wide Web · doi:10.1007/s11280-014-0274-4 · Cited by 3
“As for the query sets, following the previous works [4, 21, 22, 31], Q8, Q12, Q16, Q20, and Q24 query sets are used.”
MethodInfluentialStructure-preserving subgraph query services
Fan, Z., Choi, B. K. K., Chen, Q., Xu, J., Hu, H., & Bhowmick, S. S. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498410 · Cited by 3
Big-Graphs: Querying, Mining, and Beyond
Khan, A., & Ranu, S. (2017) · Springer eBooks · doi:10.1007/978-3-319-49340-4_16 · Cited by 3
Tripoul, N., Halawa, H. H., Reza, T. A., Sanders, G., Pearce, R., & Ripeanu, M. (2018) · Irregular Applications: Architectures and Algorithms · doi:10.1109/ia3.2018.00010 · Cited by 3
“Similar to our prior work [1] that uses the ad-hoc heuristics described in §V-A, many other heuristics for pattern matching based on depth-first search have been proposed [15], [16].”
MethodResultOptimized Distributed Subgraph Matching Algorithm Based on Partition Replication
Yuan, L., Bin, J., & Pan, P. (2020) · Electronics · doi:10.3390/electronics9010184 · Cited by 3
“iGraph divides the graph index set into a mining index [9] part and a non-mining index [10] part.”
BackgroundSimulation-based Approximate Graph Pattern Matching
Chen, X. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3384401 · Cited by 3
“QuickSI [12] leverages a minimum spanning tree of the query graph to further narrow the searching space.”
BackgroundSpatiotemporal RDF Data Query Based on Subgraph Matching
Meng, X., Zhu, L., Li, Q., & Zhang, X. (2021) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi10120832 · Cited by 3
Subgraph Query Matching in Multi-Graphs Based on Node Embedding
Anwar, M., Hassanien, A. E., Snåšel, V., & Basha, S. H. (2022) · Mathematics · doi:10.3390/math10244830 · Cited by 3
A Study of Laplacian Spectra of Graph for Subgraph Queries
Zhu, L., & Song, Q. (2011) · Proceedings · doi:10.1109/icdm.2011.17 · Cited by 3
“However, the effectiveness of these methods depends on the quality of extracted features.”
BackgroundExtracting top-K interesting subgraphs with weighted query semantics
Amin, N., Khan, K. U., Dolgorsuren, B., & Lee, Y.-K. (2017) · IEEE International Conference on Big Data and Smart Computing (BigComp) · doi:10.1109/bigcomp.2017.7881695 · Cited by 3
Efficient Subgraph Matching on Non-volatile Memory
Shen, Y., & Zou, Z. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-68783-4_31 · Cited by 3
A Twig-Based Algorithm for Top-k Subgraph Matching in Large-Scale Graph Data
Zhang, H., Bai, Q., Lian, Y., & Wen, Y. (2022) · Big Data Research · doi:10.1016/j.bdr.2022.100350 · Cited by 3
Scaling Subgraph Matching by Improving Ullmann Algorithm
Gouda, K., Bujdosó, G., & Hassaan, M. (2022) · Computing and Informatics · doi:10.31577/cai_2022_4_1002 · Cited by 3
GPU-based Commonsense Paradigms Reasoning for Real-Time Query Answering and Multimodal AnalysisPreprint
Tran, N. H., & Cambria, E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.08804 · Cited by 3
Efficient Mining of Frequent Subgraphs with Two-Vertex ExplorationPreprint
Jiang, P., Wang, R., & Wu, B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.07690 · Cited by 3
“All of these algorithms have exponential complexity due to the NP-hardness of this problem [6, 34].”
BackgroundOn Temporal-Constraint Subgraph Matching
Leng, X., Zeng, G., Qin, H., Lin, L., & Li, R.-H. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00188 · Cited by 2
“The first, known as Direct Enumeration, directly explores the data graph to find all results, exemplified by QuickSI [43], RI [28], and VF2++ [44].”
NeuSO: Neural Optimizer for Subgraph Queries
Yang, L., Zou, L., & Zhao, C. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3769810 · Cited by 2
Same Same But Different: Preventing Refactoring Attacks on Software Plagiarism Detection
Maisch, R., Schmid, L., Sağlam, T., & Niehues, N. (2026) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3744916.3773225 · Cited by 2
Subgraph Matching Algorithm for Graph Database
Rajput, M., & Kamalapur, S. M. (2017) · Cited by 2
A Hybrid Approach of Subgraph Isomorphism and Graph Simulation for Graph Pattern Matching
Sugawara, K., & Suzuki, N. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-98812-2_29 · Cited by 2
Homomorphic Encryption based Subgraph Isomorphism Protocol in Blockchain
Guo, M., Chi, C., Zheng, H., Zhang, K., & He, J. (2021) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1145/3498851.3498994 · Cited by 2
Fast and Accurate Efficient Streaming Subgraph Isomorphism
Duong, C. T., Hoang, T. D., Yin, H., Weidlich, M., Nguyên, T. T., Nguyen, Q. V. H., & Aberer, K. (2020) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.13140/rg.2.2.32016.23045 · Cited by 2
Cheng, C. Q., Wong, K., & Soon, L.-K. (2024) · International Conference on Electronics, Information, and Communication (ICEIC) · doi:10.1109/iceic61013.2024.10457108 · Cited by 2
“However, both TurboISO [8] and CFL-Match [4] have the common drawback that the ordering of edges is not considered when traversing the index.”
MethodOrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem
Tauhidi, S. I., Karmakar, A., Mai, T. S., & Vandierendonck, H. (2024) · IEEE International Conference on Knowledge Graph (ICKG) · doi:10.1109/ickg63256.2024.00052 · Cited by 2
MultiGraphMatch: A Subgraph Matching Algorithm for Multigraphs
Micale, G., Maria, A. D., Grasso, R., Bonnici, V., Ferro, A., Shasha, D. E., Giugno, R., & Pulvirenti, A. (2025) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3728361 · Cited by 2
Accelerating Subgraph Matching Through Advanced Compression and Label Filtering
Chai, Y., Li, J., & Zhang, Q. (2025) · Algorithms · doi:10.3390/a18090541 · Cited by 2
SIGMo: High-Throughput Batched Subgraph Isomorphism on GPUs for Molecular Matching
Caro, A. D., Cordasco, G., Ficarelli, F., & Cosenza, B. (2025) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3712285.3759782 · Cited by 2
Private Subgraph Matching Protocol
Xu, Z., Zhou, F., Li, Y., Xu, J. F., & Wang, Q. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-68637-0_27 · Cited by 2
Graph pattern mining techniques to identify potential model organisms
Nabhan, A. R. (2014) · ScholarWorks -A service of University of Vermont Libraries (University of Vermont) · Cited by 2
Amin, M. S., Bhattacharjee, A., & Jamil, H. M. (2010) · ACM Symposium on Applied Computing · doi:10.1145/1774088.1774424 · Cited by 2
GOW-LDA: Applying Term Co-occurrence Graph Representation in LDA Topic Models Improvement
Pham, P., Do, P., & Ta, C. D. C. (2018) · Lecture notes in electrical engineering · doi:10.1007/978-981-10-8276-4_40 · Cited by 2
TBSGM: A Fast Subgraph Matching Method on Large Scale Graphs
Jin, F., Yang, Y., Wang, S., Xue, Y., & Yan, Z. Y. (2018) · International Journal of Data Warehousing and Mining · doi:10.4018/ijdwm.2018100104 · Cited by 2
Evaluating Mixed Patterns on Large Data Graphs Using Bitmap Views
Wu, X., Theodoratos, D., Skoutas, D., & Lan, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-18576-3_33 · Cited by 2
A new hybrid approach to improve the efficiency of homomorphic matching for graph rules
Kong, J., Huang, J. X., Chen, H., & Gong, J. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.07.023 · Cited by 2
Scalable top-k query on information networks with hierarchical inheritance relations
Wu, F., & Gao, L. (2023) · Distributed and Parallel Databases · doi:10.1007/s10619-023-07432-2 · Cited by 2
A Multilayer Approach to Subgraph Matching in HP-graphs
Suvorov, N. M., & Lyadova, L. N. (2021) · Proceedings of the Institute for System Programming of RAS · doi:10.15514/ispras-2021-33(4)-12 · Cited by 2
Optimization of Subgraph Matching over Knowledge Graph Based on Subgraph Indexing
Lv, L., Liu, J., Li, Q., & Li, J. (2022) · International Conference on Artificial Intelligence and Big Data (ICAIBD) · doi:10.1109/icaibd55127.2022.9820592 · Cited by 2
Top-k Graph Similarity Search Algorithm Based on Chi-Square Statistics in Probabilistic Graphs
Chen, Z., Zhuang, J., Wang, X., Tang, X., Yang, K., Du, M., & Zhou, J. (2024) · Electronics · doi:10.3390/electronics13010192 · Cited by 2
Subgraph search for dynamic graphs
Choudhury, S. (2014) · Research Exchange (Washington State University) · Cited by 2
Parallel algorithms for subgraph pattern matching
Jain, A. (2014) · Cited by 2
Wu, Y., & Khan, A. (2018) · Springer eBooks · doi:10.1007/978-3-319-77525-8_74 · Cited by 2
Stochastic Optimization and Subgraph Search
Moorman, J. D. (2021) · eScholarship (California Digital Library) · Cited by 2
Subgraph Matching on Attributed Multiplex Networks with Applications to Knowledge Graphs
Tu, T. K. (2021) · eScholarship (California Digital Library) · Cited by 2
Detecting Small Query Graphs in A Large Graph via Neural Subgraph SearchPreprint
Bai, Y., Xu, D. C., Sun, Y., & Wang, W. W. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2207.10305 · Cited by 2
“…a series of baseline solvers whose source codes are provided by (Sun & Luo, 2020): L DF (Sun & Luo, 2020), N LF (Sun & Luo, 2020), Q UICK SI (Shang et al., 2008), G RAPH QL (He & Singh, 2008), T SO (Han et al., 2013), C FL (Bi et al., 2016), C ECI (Bhattarai et al., 2019), and DP-ISO (Han…”
BackgroundMethodUncertainty-aware Efficient Subgraph Isomorphism using Graph TopologyPreprint
Kusari, A., & Sun, W. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2209.09090 · Cited by 2
“We compared the proposed algorithm with nine di ff erent subgraph matching algorithms, including GraphQL [44], CECI [45], Neural [46], QuickSI [47]), VF2 ++ [48], the interior point optimization solution of Eq(2), and the continuous approximated so-lution of Eq(2).”
Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs
Yang, X., Ajwani, D., Gatterbauer, W., Nicholson, P. K., Riedewald, M., & Sala, A. (2018) · Arrow@dit (Dublin Institute of Technology) · doi:10.48550/arxiv.1802.06060 · Cited by 2
“[26] empirically compare the performance of several state-of-art subgraph isomorphism algorithms, including the Generic Subgraph Isomorphism Algorithm [11], Ullmann algorithm [36], VF2 [10], QuickSI [33], GADDI [41], and GraphQL [17].”
MethodCarletti, V., Foggia, P., Greco, A., & Vento, M. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-73973-7_24 · Cited by 1
SGPM: a privacy protected approach of time-constrained graph pattern matching in cloud
Huang, J., Chen, W., Li, Z., Zhao, P., Wang, W., Yin, H., & Zhao, L. (2020) · World Wide Web · doi:10.1007/s11280-020-00784-0 · Cited by 1
“Firstly, a lot of researchers investigate the problem of querying static graph pattern in static graphs [13, 23, 33, 35, 54, 72].”
BackgroundGraphPar: Efficient Workload-Aware Subgraph Matching System on Multiple GPUs
Zhang, K., Xiao, J., Lin, Z., Meng, K., Shui, C., Li, M., & Tan, G. (2023) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads60453.2023.00117 · Cited by 1
Tauhidi, S. I., Karmakar, A., Mai, T. S., & Vandierendonck, H. (2024) · Communications in computer and information science · doi:10.1007/978-3-031-69257-4_16 · Cited by 1
Uncertainty-aware efficient subgraph isomorphism using graph topology
Kusari, A., & Sun, W. (2025) · Pattern Recognition · doi:10.1016/j.patcog.2025.112044 · Cited by 1
“We would like to mention that we tested four different subgraph matching algorithms provided in the OpenGraphMatching toolbox (Tianchang, 2021)(GraphQL(He and Singh, 2008), CECI (Bhattarai et al., 2019), Neural (Liu et al., 2020), QuickSI (Shang et al., 2008)) which yielded no results without labels.”
GNN-based Anchor Embedding for Efficient Subgraph Retrieval
Yang, B., Ye, J., & Zou, Z. (2026) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/3805712.3809567 · Cited by 1
A Design of Smart Enterprise Asset Management
Lin, C. L., Lan, C.-W., Ye, J., & Wu, Y.-C. (2013) · IEEE International Conference on e-Business Engineering (ICEBE) · doi:10.1109/icebe.2013.71 · Cited by 1
“The exact match looks for isomorphic set of assets according to a given graphbased user query [12, 13].”
BackgroundAn efficient filtering technique for super-graph query processing
Saber, M., Aref, M. M., & Gharib, T. F. (2010) · International Conference on Digital Information Management · doi:10.1109/icdim.2010.5664712 · Cited by 1
GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING
Jin, W. (2011) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 1
On Efficient Graph Substructure Selection
Zhao, X. H., Shang, H., Zhang, W., Lin, X., & Xiao, W. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37450-0_22 · Cited by 1
“Following [8, 11], we choose the template graphs conforming to freq(t) ≥ α and disc(t) ≤ 1− β, where α and β are frequency and discrimination thresholds, respectively.”
BackgroundMethodSelf-citationA Coding Method for Efficient Subgraph Querying on Vertex- and Edge-Labeled Graphs
Zhu, L., Song, Q., Guo, Y., Du, L., Zhu, X., & Wang, G. (2014) · PLoS ONE · doi:10.1371/journal.pone.0097178 · Cited by 1
“Many researchers such as Yan et al. [12], Shang et al. [16], Zou et al. [17], and He and Singh [18] used one of its subset to test their methods, we chose it as benchmark data as well.”
MethodA Privacy Policy Conflict Detection Method Based on Sub-graph Isomorphism
Ren, Y., Peng, Z., Cheng, F., & Guo, S. (2009) · International Conference on Multimedia Information Networking and Security · doi:10.1109/mines.2009.251 · Cited by 1
Optimized Backtracking for Subgraph Isomorphism
Fu, L. (2012) · International Journal of Database Management Systems · doi:10.5121/ijdms.2012.4601 · Cited by 1
Analyzing Subgraph Isomorphism on Graphs with Diverse Structural Properties
Amin, N., Khan, K. U., & Lee, Y.-K. (2015) · International Conference on Big Data Applications and Services (BigDAS) · doi:10.1145/2837060.2837088 · Cited by 1
“Various state-of-the-art [1 2 3] follow its unique strategy by considering four aspects of graph to speed up the matching process in terms of query processing time and memory namely, indexing, candidate generation, early pruning of unpromising regions, and traversing the graph.”
BackgroundMultiple Pattern Graph Correlations for Efficient Graph Pattern Matching
Yu, J., Liu, X., Liu, Y., & Hu, Y. (2017) · IEEE/ACS International Conference on Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa.2017.174 · Cited by 1
“To use the global statistics, QuickSI [7] introduces a new tree-based matching sequence and prunes out candidates not satisfying parent-child relationship.”
MethodSelf-citationComparison of Approaches for Querying Chemical Compounds
Šípek, V., Holubová, I., & Svoboda, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-33752-0_15 · Cited by 1
DDSL: Efficient Subgraph Listing on Distributed and Dynamic Graphs
Jian, X., Wang, Y., Lei, X., Shen, Y., & Chen, L. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-59416-9_39 · Cited by 1
Accelerating subgraph matching by anchored relationship on labeled graph
Sun, Y., Jiang, W., Liu, S., Li, G., & Ning, B. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.107502 · Cited by 1
A novel framework for the efficient evaluation of hybrid tree-pattern queries on large data graphs
Wu, X., Theodoratos, D., Skoutas, D., & Lan, M. (2023) · Information Systems · doi:10.1016/j.is.2023.102249 · Cited by 1
10X Faster Subgraph Matching: Dual Matching Networks with Interleaved Diffusion Attention
Nguyen, T. T., Nguyen, Q. D., Ren, Z. X., Jo, J. H., Nguyen, Q. V. H., & Nguyên, T. T. (2023) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn54540.2023.10191159 · Cited by 1
“QuickSI [9] implements the infrequent-edge-first ordering strategy, which sorts edges of the query pattern according to the frequencies with which they appear in the target graph.”
BackgroundMethodLow-Correlation Node Filter-Based Neural Subgraph Matching
Cui, C., Wang, T., Chang, Y., Zhan, D., Wu, X., Huang, W., Fan, X., Tong, E., & Niu, W. (2023) · China Automation Congress (CAC) · doi:10.1109/cac59555.2023.10450300 · Cited by 1
“Many subgraph matching algorithms based on Ullmann have been proposed, such as the VF2 algorithm [10], the QuickSI [11], and the SPath [12].”
MethodUnderstanding High-Performance Subgraph Pattern Matching: A Systems Perspective
Sharma, A., Mehta, D. P., & Wu, B. (2024) · ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA) · doi:10.1145/3661304.3661897 · Cited by 1
View-based Explanations for Graph Neural Networks (Extended Abstract)
Chen, T., Qiu, D., Wu, Y., Khan, A., Ke, X., & Gao, Y. (2024) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew61823.2024.00058 · Cited by 1
Speeding Up Subgraph Matching Queries with Schema Guided Index
Zhao, Y., Wang, W., Chen, S., Zhang, B., Wang, J., & Wang, Z. (2024) · International Conference on Networks, Communications and Information Technology (CNCIT) · doi:10.1145/3672121.3672129 · Cited by 1
Towards Cross-Model Efficiency in SQL/PGQ
Rotschield, H., & Peterfreund, L. (2025) · ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA) · doi:10.1145/3735546.3735860 · Cited by 1
TriFMatch: a flash subgraph matching algorithm with effective filtering techniques
He, J., Chen, Y., Jia, M., Liu, Z., Li, D., & Tan, K. (2025) · Knowledge and Information Systems · doi:10.1007/s10115-025-02608-x · Cited by 1
“These query plans are derived from existing works, including IVE [16], RM [7], QSI [42], and GQL [43], along with a randomly generated plan named Random .”
Efficient Subgraph Similarity All-Matching
Zhu, G., Zhu, K., Zhang, W., Lin, X., & Xiao, C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29038-1_33 · Cited by 1
Self-citationEfficient techniques for subgraph mining and query processing
Lin, W. (2015) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/62137 · Cited by 1
“To facilitate the filter process in the filter-and-verification framework, existing approaches [22, 38, 80, 83, 101, 104, 106, 110] construct index structures in a pre-processing step.”
BackgroundMethodInfluentialBUILDING EFFICIENT AND COST-EFFECTIVE CLOUD-BASED BIG DATA MANAGEMENT SYSTEMS
Quamar, A. (2015) · University Libraries (University of Maryland) · doi:10.13016/m2hr2n · Cited by 1
Design pattern detection framework for TOSCA-topologies
Wohlfarth, M. (2017) · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · doi:10.18419/opus-9407 · Cited by 1
Improving the performance and scalability of patten subgraph queries
Katsarou, F. (2018) · Enlighten: Theses (The University of Glasgow) · Cited by 1
Fast Subgraph Matching by Exploiting Search FailuresPreprint
Arai, J., Onizuka, M., Fujiwara, Y., & Iwamura, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.14420 · Cited by 1
“The evaluation also uses CFL-Match, QuickSI [13], and GraphQL [8] for comparison.”
Influential(2010) · International Conference on Frontier of Computer Science and Technology (FCST) · doi:10.1109/fcst.2010.114 · Cited by 1
GraphflowDB: Scalable Query Processing on Graph-Structured Relations
Mhedhbi, A. (2023) · UWSpace (University of Waterloo) · Cited by 1
Otimização de consultas SPARQL em bases RDF distribuídas
Penteado, R. R. M. (2017) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 1
Neural Network-based Graph-Level Operator Learning
Bai, Y. (2023) · eScholarship (California Digital Library) · Cited by 1
Abbaci, K. (2013) · theses.fr (ABES) · doi:10.70675/e18892d8zf23bz4688zb013z6b7f8ace70d1 · Cited by 1
Querying and Mining Multigraphs
Ingalalli, V. (2017) · theses.fr (ABES) · doi:10.70675/d7b0e5acz2332z4eedz9db0z83320a46ae99 · Cited by 1
“QuickSI [Shang et al., 2008] builds a minimum spanning tree to find the next query vertex, by assigning weights to the edges of the query graph, depending on the frequency of occurrence of query vertex in the data graph.”
BackgroundMethodInfluentialCo-evolution pattern mining in dynamic attributed graphs
Desmier, É. (2014) · theses.fr (ABES) · doi:10.70675/47edfa88zc205z49f5z8fbdz2a2670210628 · Cited by 1
Delabrière, A. (2018) · theses.fr (ABES) · doi:10.70675/f4a2e680zfdaaz4d34za6f7z4644253ae172 · Cited by 1
Parallel and distributed algorithms for pattern matching in big graphs
Bouhenni, S. (2021) · theses.fr (ABES) · doi:10.70675/24cfd0f4zaa30z4382z92c0ze696126ad6f0 · Cited by 1
de Gastines, E. (2023) · theses.fr (ABES) · doi:10.70675/95fb364azf8b2z4edczb25dz3fc6ef2d836d · Cited by 1
A Study on Graph Similarity Search
Shang, H., & Kitsuregawa, M. (2012) · Journal of information processing · doi:10.11185/imt.7.1565
“Instead of trivially enumerating mappings from V (q) to V (g), QuickSI enumerates mappings from a spanning tree of V (q) to g to reduce the combinations by the connectivity restriction.”
BackgroundMethodSelf-citationAnatomy of Graph Matching based on an XQuery and RDF ImplementationPreprint
Rivero, C. R., & Jamil, H. M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.2342
“In the former, the whole query graph is processed at the same time, in which GraphQL [4], QuickSI [5], Ullman [7] and VFLib [2] are the most representative proposals.”
MethodProvenance comparison for large-scale knowledge discovery
Zhao, X. H., Ge, B., Tang, J., Xiao, W., & Shang, H. (2013) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2013.6691785
“We present PEDCode, an encoding technique adapted from [18] to support provenance.”
MethodSelf-citationAG-Index: Adjacent Edge Hash Index for Graph Databases
Wang, H. H., Peng, Y. F., & Huang, H. (2014) · Applied Mechanics and Materials · doi:10.4028/www.scientific.net/amm.631-632.1045
“In this section, we compare the new technology with state-of-the-art feature-based approach for graph indexing, namely gIndex [6, 7], FG-Index.”
MethodFast-On*: An Extended Algorithm for Graph Isomorphism Problem and Graph Query Processing
Hassaan, M. (2012) · International Journal of Database Management Systems · doi:10.5121/ijdms.2012.4602
Optimized Algorithm of Extended Subgraph Isomorphism Problem
Kai-xuan, X., & Fleischer, R. (2011) · Jisuanji gongcheng
Scalable Mining of Large Graphs and Its Applications
Xie, Y. (2013) · Figshare
Metadata
- Authors
- Shang, H., Zhang, Y., Lin, X., & Yu, J. X.
- Affiliations
- UNSW Sydney (AU)
- Chinese University of Hong Kong (HK)
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2008-08
- Volume
- 1
- Issue
- 1
- Pages
- 364-375
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2140840007
- Cited by
- 401
- References
- 29
- Citations by year
- 2026: 13 · 2025: 29 · 2024: 32 · 2023: 22 · 2022: 28 · 2021: 38 · 2020: 25 · 2019: 27 · 2018: 24 · 2017: 24 · 2016: 23 · 2015: 24 · 2014: 18 · 2013: 15 · 2012: 23
- FWCI
- 17.28
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Proceedings of the VLDB Endowment (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- subgraph isomorphism, graph retrieval, NP-hardness, scalability, query graph
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.