Finding Multidimensional Constraint Reachable Paths for Attributed Graphs
DOI:
https://doi.org/10.4108/eetsis.v9i4.2581Keywords:
hashing, attributed graph, matrix factorization, constraint reachabilityAbstract
A graph acts as a powerful modelling tool to represent complex relationships between objects in the big data era. Given two vertices, vertex and edge constraints, the multidimensional constraint reachable ( MCR) paths problem finds the path between the given vertices that match the user-specified constraints. A significant challenge is to store the graph topology and attribute information while constructing a reachability index. We propose an optimized hashing-based heuristic search technique to address this challenge while solving the multidimensional constraint reachability queries. In the proposed technique, we optimize hashing and recommend an efficient clustering technique based on matrix factorization. We further extend the heuristic search technique to improve the accuracy. We experimentally prove that our proposed techniques are scalable and accurate on real and synthetic datasets. Our proposed extended heuristic search technique is able to achieve an average execution time of 0.17 seconds and 2.55 seconds on MCR true queries with vertex and edge constraints for Robots and Twitter datasets respectively.
References
T. He and K. C. C. Chan (2018) Discovering Fuzzy Structural Patterns for Graph Analytics, IEEE Transactions on Fuzzy Systems, Vol. 26(5), pp. 2785–2796.
Falih, Issam and Grozavu, Nistor and Kanawati, Rushed and Bennani, Younès (2018) ANCA : Attributed Network Clustering Algorithm, Complex Networks & Their Applications VI, Springer International Publishing, pp. 241–252.
L.D.J. (Lucien) Valstar (2016) Landmark Indexing for Scal-able Evaluation of Label-Constrained Reachability Queries, Masters Thesis, Department of Mathematics and Com-puter Science Web Engineering Research Group, Eind-hoven University of Technology, Netherlands.
Zhou, Yang and Cheng, Hong and Yu, Jeffrey Xu (2009) Graph Clustering Based on Structural/Attribute Similarities, Proc. VLDB Endow., Vol. 2(1):718–729.
Likhyani, Ankita and Bedathur, Srikanta(2013) Label Constrained Shortest Path Estimation, Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, pp. 1177–1180.
Wu, Zhonggang and Lu, Zhao and Ho, Shan-Yuan (2016) Community Detection with Topological Structure and Attributes in Information Networks ACM Trans. Intell. Syst. Technol., Vol. 8(2), pp. 33:1–33:17.
Wang, Hao and Yang, Yan and Liu, Bing and Fujita, Hamido(2019) A study of graph-based system for multi-view clustering Knowledge-Based Systems , ELsevier, Vol. 163, pp. 1009–1019.
M. T. Al Amin and C. Aggarwal and S. Yao and T. Abdelzaher and L. Kaplan (2017) Unveiling polarization in social networks: A matrix factorization approach, Proceedings of IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1–9.
Duncan Yung and Shi-Kuo Chang (2016) Fast Reachabil-ity Query Computation on Big Attributed Graphs 2016 IEEE International Conference on Big Data, pp.3370–3380.
Ka Wai (Duncan) Yung (2017) Query Processing on Attributed Graphs PhD Thesis, University of PittsBurgh.
B. Bhargavi and Rani K. Swarupa, (2018), Bounded Paths for LCR Queries in Labeled Weighted Directed Graphs, Advances in Computing and Data Sciences, pp. 124–133.
Zhao, Anqi and Liu, Guanfeng and Zheng, Bolong and Zhao, Yan and Zheng, Kai, (2020), Temporal paths discovery with multiple constraints in attributed dynamic graphs, World Wide Web, Springer, Vol. 23(1), pp. 313–336.
Bhargavi B. and Swarupa Rani K. (2019) Implicit land-mark path indexing for bounded label constrained reachable paths, International Journal of Recent Technology and Engineering (IJRTE), Vol. 8(4):p.10.
Namaki, Mohammad Hossein and Song, Qi and Wu, Yinghui and Yang, Shengqi (2019) Answering why-questions by exemplars in attributed graphs, Proceedings of the 2019 International Conference on Management of Data , pp. 1481–1498.
Guo, Ying and Zheng, Lianzhen and Zhang, Yuhan and Liu, Guanfeng, (2020) MCOPS-SPM: Multi-Constrained Optimized Path Selection Based Spatial Pattern Matching in Social Networks, Cloud Computing, Smart Grid and Innovative Frontiers in Telecommunications, Springer International Publishing, pp. 3–19.
Wang, Yanhao and Li, Yuchen and Fan, Ju and Ye, Chang and Chai, Mingke (2021) A survey of typical attributed graph queries, World Wide Web, Springer, Vol. 24(1), pp. 297–346.
Bhargavi B. (2020) A Study of Constrained Reachability Query Processing in Directed Graphs Preprint, PhD Thesis, University of Hyderabad.
Jure Lescovec, (2016), SNAP: A general purpose network analysis and graph mining library in C++, <http://snap.stanford.edu/snap>.
Cohen, Edith and Halperin, Eran and Kaplan, Haim and Zwick, Uri (2002) Reachability and Distance Queries via 2-hop Labels Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pp.937–946.
Jin, Ruoming and Hong, Hui and Wang, Haixun and Ruan, Ning and Xiang, Yang (2010) Computing Label-constraint Reachability in Graph Databases Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 123-134.
Jin, Ruoming and Xiang, Yang and Ruan, Ning and Fuhry, David (2009) 3-HOP: A High-compression Indexing Scheme for Reachability Query, Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 813–826.
Zarayeneh, Neda and Kalyanaraman, Ananth (2019) A Fast and Efficient Incremental Approach toward Dynamic Community Detection,Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 9–16.
Peng, You and Zhang, Ying and Lin, Xuemin and Qin, Lu and Zhang, Wenjie (2020) Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond, VLDB Endowment, Vol. 13(6), pp. 812–825.
Leskovec, Jure and Klecberg, Jon and Faloutsos, Christos (2007) Graph Evolution: Densification and Shrinking Diameters, ACM Trans. Knowl. Discov. Data, Vol. 1(1), pp. 2-44.
Réka Albert and Albert-lászló Barabási (2002) Statistical mechanics of complex networks, Rev. Mod. Phys, pp. 47–94.
Robert Tibshirani and Guenther Walther and Trevor Hastie (2000) Estimating the number of clusters in a dataset via the Gap statistic, Journal of Royal Statistical Methodology, Vol. 63, pp. 411–423.
Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford (2009) Introduction to Algorithms, Third Edition.
Wang, Haixun and He2, Hao and Yang, Jun and Yu, Philip S. and Yu, Jeffrey Xu and Yu, Jeffrey Xu (2006)
Dual Labeling: Answering Graph Reachability Queries in Constant Time, Proceedings of the 22nd International Conference on Data Engineering, IEEE Computer Society, pp. 1–12.
Duda, Richard O. and Hart, Peter E. and Stork, David G. (2000) Pattern Classification (2nd Edition), Wiley-Interscience.
Zhengkui Wang and Qi Fan and Huiju Wang and Tan, Kian Lee and Divyakant Agrawal and El Abbadi,
Amr (2014) Pagrol: Parallel Graph OLAP over large-scale attributed graphs, Proceedings - ICDE, IEEE Computer Society, pp. 496–507.
Sakr, Sherif and Elnikety, Sameh and He, Yuxiong (2011) G-SPARQL: A Hybrid Engine for Querying Large Attributed Graphs, Microsoft Technical Report.
Yang, Jaewon and Leskovec, Jure (2013) Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach, Proceedings of the Sixth ACM International Conf. on Web Search and Data Mining, Vol. 13(6), ACM, pp. 587–596.
Xu, Zhiqiang and Ke, Yiping and Wang, Yi and Cheng, Hong and Cheng, James (2012) A Model-Based Approach to Attributed Graph Clustering, Proceedings of the 2012 ACM SIGMOD International Conf. on Management of Data, pp. 505–516.
G. Qi and C. C. Aggarwal and T. Huang (2012) Community Detection with Edge Content in Social Media Networks, 2012 IEEE 28th ICDE, pp. 534–545.
Aggarwal, Charu C. and Wang, Haixun (2012) Managing and Mining Graph Data, Springer Publishing Company, Incorporated.
(2017) Robots Dataset, <http://tinyurl.com/gnexfoy/>.
(2016) MurmurHash, <https://github.com/aappleby/smhasher>.
Page, L. and Brin, S. and Motwani, R. and Winograd, T. (1998) The PageRank citation ranking: Bringing order to the Web, Proceedings of the 7th International World Wide
Web Conference, (pp. 161–172).
Z. Lin, Z. Kang, L. Zhang and L. Tian, (2021) Multi-view Attributed Graph Clustering in IEEE Trans-actions on Knowledge and Data Engineering, doi: 10.1109/TKDE.2021.3101227.
Atzmueller, M., Günnemann, S. and Zimmermann, A. (2021) Mining communities and their descriptions on attributed graphs: a survey. Data Min Knowl Disc, Vol. 35, pp. 661–687. https://doi.org/10.1007/s10618-021-00741-z.
Isma Hamid and Yu Wu and Qamar Nawaz and Runqian Zhao (2017) An improved attributed graph clustering method for discovering expert role in real-world communities, In proceedings of 10th EAI International Conference on Mobile Multimedia Communications, EAI MOBIMEDIA, https://doi.org/10.4108/eai.13-7-2017.2270341.
Xin Chen, You Peng, Sibo Wang, and Jeffrey Xu Yu (2022) DLCR: efficient indexing for label-constrained reachability queries on large dynamic graphs. Proc. VLDB Endow., Vol. 15(8), pp. 1645–1657, https://doi.org/10.14778/3529337.3529348.
Yangjun Chen and Gagandeep Singh (2021) Graph Indexing for Efficient Evaluation of Label-constrained Reach-ability Queries ACM Trans. Database Syst. 46, 2, Article 8 (June 2021), 50 pages. https://doi.org/10.1145/3451159.
Arasu, Arvind and Cho, Junghoo and Garcia-Molina, Hector and Paepcke, Andreas and Raghavan, Sriram.(2001) Searching the Web ACM Trans. Internet Technol., Vol. 1(1), pp. 2–43.
Bhargavi B. and K. Swarupa Rani (2020) Finding Frequent Subgraphs and Subpaths through Static and Dynamic Window Filtering Techniques, EAI Endorsed Transactions on Scalable Information Systems, Vol. 7(27):p.13.
B. Bhargavi, K. P. Supreethi (2012) Graph Pattern Mining: A Survey of Issues and Approaches, International Journal of Information Technology and Knowledge Management, Vol. 5(2), pp. 401-407.
Bhargavi Balla, Supreethi Kalyandurgam Pujari (2012) An Efficient Computation of Reachability Labeling for Graph Pattern Matching, Second International Conference on Social Eco-Informatics, IARIA, pp. 58-62.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 EAI Endorsed Transactions on Scalable Information Systems
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
This is an open access article distributed under the terms of the CC BY-NC-SA 4.0, which permits copying, redistributing, remixing, transformation, and building upon the material in any medium so long as the original work is properly cited.
