On Minimal Unique Induced Subgraph Queries
Source abstract
Abstract
In this paper, a novel type of interesting subgraph query is proposed: Minimal Unique Induced Subgraph (MUIS) query. Given a (large) graph G and a query vertex (position) q in the graph, can we find an induced subgraph containing q with the minimal number of vertices that is unique in G? MUIS query has many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. The formal definition of MUIS is given and the properties are discussed in this paper. The baseline and EQA (Efficient Query Answering) algorithms are proposed to solve the MUIS query problem under the filtering-validation framework. In the EQA algorithm, the Breadth First Search (BFS)-based candidate set generation strategy is proposed to ensure the minimality property of MUIS; the matched vertices-based pruning strategy is proposed to prune useless candidate sets and the unnecessary subgraph isomorphism; and the query position-based subgraph isomorphism is proposed to check efficiently the uniqueness of the subgraphs. Experiments are carried on real datasets and synthetic datasets to verify the effectiveness and efficiency of the proposed algorithm under novel measurements. The influencing factors of the process speed are discussed at last in the paper.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Graph Theory and Algorithms · Advanced Graph Neural Networks · Data Management and Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of System Engineering, National University of Defense Technology, Changsha 410073, China
Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA
National Institute of Information and Communication Technology, Tokyo 184-8795, Japan
Institute of Industrial Science, The University of Tokyo, Tokyo 113-8654, Japan
School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Funding
National Natural Science Foundation of China
References (40)
Show source-provided references
1. Global alignment of protein–protein interaction networks by graph matching methods10.1093/bioinformatics/btp196 ↗
2. IsoRankN: Spectral methods for global alignment of multiple protein networks10.1093/bioinformatics/btp203 ↗
3. Bond graph for dynamic modelling in chemical engineering10.1016/j.cep.2007.09.006 ↗
4. Application of Graph Theory to Cost-Effective Fire Protection of Chemical Plants During Domino Effects10.1111/risa.12712 ↗
5. Faloutsos, M. (2013, January 13–17). Detecting malware with graph-based methods: Traffic classification, botnets, and facebook scams. Proceedings of the 22nd International Conference on World Wide Web, Rio De Janeiro, Brazil.10.1145/2487788.2487980 ↗
6. Khan, K.U., Alam, A., Dolgorsuren, B., Uddin, M.A., Umair, M., Sang, U., Duong, V.T., Xu, W., and Lee, Y.K. (2017). LPaMI: A Graph-Based Lifestyle Pattern Mining Application Using Personal Image Collections in Smartphones. Appl. Sci., 7.10.3390/app7121200 ↗
7. Rezig, S., Achour, Z., Rezg, N., and Kammoun, M.A. (2015). Supervisory control based on minimal cuts and Petri net sub-controllers coordination. Int. J. Syst. Sci., 1–11.10.1080/00207721.2015.1076903 ↗
8. Control Synthesis Based on Theory of Regions with Minimal Reachability Graph Knowledge10.1016/j.ifacol.2016.07.759 ↗
9. Rezig, S., Achour, Z., and Rezg, N. (2017). Theory of Regions for Control Synthesis without Computing Reachability Graph. Appl. Sci., 7.10.3390/app7030270 ↗
10. Fortin, S. (1996). The Graph Isomorphism Problem, University of Alberta. Tech. Rep.
11. Yuan, Y., Wang, G., Chen, L., and Wang, H. (2012, January 27–31). Efficient subgraph similarity search on large probabilistic graph databases. Proceedings of the VLDB Endowment, Istanbul, Turkey.10.14778/2311906.2311908 ↗
12. Cook, S.A. (1971, January 3–5). The Complexity of Theorem-proving. Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, OH, USA.10.1145/800157.805047 ↗
13. Faster subtree isomorphism10.1006/jagm.1999.1044 ↗
14. Shasha, D., Wang, J., and Giugn, R. (2002, January 3–5). Algorithmics and applications of tree and graph searching. Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Madison, WI, USA.10.1145/543613.543620 ↗
15. A (sub)graph isomorphism algorithm for matching large graphs10.1109/TPAMI.2004.75 ↗
16. Shang, H., Zhang, Y., Lin, X., and Yu, J.X. (2008, January 23–28). Taming verification hardness: An efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment, Auckland, New Zealand.10.14778/1453856.1453899 ↗
17. Han, W.S., Lee, J., and Lee, J.H. (2013, January 22–27). TurboISO: Towards ultrafast and robust subgraph isomorphism search in large graph databases. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA.
18. Efficient processing of graph similarity queries with edit distance constraints10.1007/s00778-013-0306-1 ↗
19. Efficient structure similarity searches: A partition-based approach10.1007/s00778-017-0487-0 ↗
20. Lin, W., Xiao, X., and Ghinita, G. (April, January 31). Large-scale frequent subgraph mining in mapreduce. Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, IL, USA.
21. Horváth, T., Otaki, K., and Ramon, J. (2013, January 23–27). Efficient frequent connected induced subgraph mining in graphs of bounded tree-width. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Prague, Czech Republic.
22. Qiao, F., Zhang, X., Li, P., Ding, Z., Jia, S., and Wang, H. (2018). A parallel approach for frequent subgraph mining in a single large graph using spark. J. Appl. Sci., 8.10.3390/app8020230 ↗
23. Inokuchi, A., Washio, T., and Motoda, H. (2000, January 13–16). An apriori-based algorithm for mining frequent substructures from graph data. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Lyon, France.10.1007/3-540-45372-5_2 ↗
24. Kuramochi, M., and Karypis, G. (December, January 29). Frequent subgraph discovery. Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, CA, USA.
25. Yan, X., and Han, J. (2002, January 9–12). Gspan: Graph-based substructure pattern mining. Proceedings of the 2002 IEEE International Conference on Data Mining, Maebashi City, Japan.
26. Huan, J., Wang, W., and Prins, J. (2003, January 19–22). Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism. Proceedings of the 2003 IEEE International Conference on Data Mining, Melbourne, FL, USA.
27. Nijssen, S., and Kok, J.N. (2004, January 22–25). A quickstart in frequent structure mining can make a difference. Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, WA, USA.10.1145/1014052.1014134 ↗
28. Zou, L., Chen, L., and Lu, Y. (2009, January 21–23). Top-K correlation sub-graph search in graph databases. Proceedings of the 14th International Conference on Database Systems for Advanced Applications, Brisbane, Australia.10.1007/978-3-642-00887-0_14 ↗
29. Efficient correlation search from graph databases10.1109/TKDE.2008.86 ↗
30. Ke, Y., Cheng, J., and Ng, W. (2007, January 12–15). Correlation search in graph databases. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA.10.1145/1281192.1281236 ↗
31. Ke, Y., Cheng, J., and Yu, J.X. (2009, January 6–9). Efficient discovery of frequent correlated subgraph pairs. Proceedings of the Ninth IEEE International Conference on Data Mining, Miami, FL, USA.10.1109/ICDM.2009.54 ↗
32. Assigning numbers to the arrows: Parameterizing a gene regulation network by using accurate expression kinetics10.1073/pnas.152046799 ↗
33. Grochow, J.A., and Kellis, M. (2007, January 21–25). Network motif discovery using subgraph enumeration and symmetry-breaking. Proceedings of the Annual International Conference on Research in Computational Molecular Biology, Oakland, CA, USA.
34. G-Tries: A data structure for storing and finding subgraphs10.1007/s10618-013-0303-4 ↗
35. Fast Analytical Methods for Finding Significant Labeled Graph Motifs10.1007/s10618-017-0544-8 ↗
36. Backtrack search algorithms and the maximal common subgraph problem10.1002/spe.4380120103 ↗
37. Williams, D.W., Huan, J., and Wang, W. (2007, January 15–20). Graph database indexing using structured graph decomposition. Proceedings of the 23rd International Conference on Data Engineering, Istanbul, Turkey.10.1109/ICDE.2007.368956 ↗
38. Shokoufandeh, A., Dickinson, S.J., Siddiqi, K., and Zucker, S.W. (1999, January 23–25). Indexing using a spectral encoding of topological structure. Proceedings of the 1999 Conference on Computer Vision and Pattern Recognition, Collins, CO, USA.
39. Topological structure analysis of the protein-protein interaction network in budding yeast10.1093/nar/gkg340 ↗
40. Human protein reference database and human proteinpedia as discovery resources for molecular biotechnology10.1007/s12033-010-9336-8 ↗