بررسی کاربردهای نظریه گراف در بازیابی اطلاعات
الموضوعات : فناوری اطلاعات و دانشمریم پیروزمند 1 , امیرحسین کیهانی پور 2 , علی معینی 3
1 - گروه الگوریتم و محاسبات، دانشکده علوم مهندسی، دانشکدگان فنی، دانشگاه تهران
2 - گروه مهندسی کامپیوتر، دانشکده مهندسی، دانشکدگان فارابی، دانشگاه تهران
3 - دانشگاه تهران
الکلمات المفتاحية: نظریه گراف, بازیابی اطلاعات, یادگیری رتبه بندی, گراف دانش, بازنمایی گرافی دادگان,
ملخص المقالة :
نظریه گراف بواسطه توانمندی در مدلسازی روابط پیچیده بین عناصر در مسائل مختلف، بصورت گسترده مورد استفاده قرار گرفته است. از سوی دیگر، بازیابی اطلاعات یعنی استخراج اطلاعات مورد نیاز کاربر، به عنوان یکی از مسائل مهم در دنیای الگوریتم و محاسبات مطرح است. با توجه به کارآمدی راهکارهای مبتنی بر گراف در بازیابی اطلاعات، این مقاله، به بررسی تحلیلی و دسته بندی کاربردهای نظریه گراف در بازیابی اطلاعات، می پردازد. این راهکارها در سه دسته کلی، قابل تفکیک هستند؛ دسته نخست، شامل الگوریتمهایی می باشد که در آنها از بازنمایی گرافی دادگان در فرآیند بازیابی اطلاعات، استفاده می شود. دسته دوم پژوهشها، به حل مسئله بازیابی معنایی اطلاعات با استفاده از نظریه گراف می پردازند و نهایتا دسته سوم، مربوط به یادگیری رتبه بندی با استفاده از نظریه گراف است. این سه دسته بصورت جزئی تر در هشت زیردسته، دسته بندی شده اند. همچنین از منظر آماری، پژوهشهای صورت گرفته در هر دسته بر اساس تعداد و سال انتشار، بررسی شده اند. از جمله یافته های این مطالعه، این است که دسته سوم، هم از نظر تعداد پژوهشها و نیز سال انتشار آنها، شاخه نوظهوری محسوب می شود و میتواند حوزه تحقیقاتی جالب توجهی برای محققان محسوب شود.
[1] J. Devezas and S. Nunes, “A Review of Graph-Based Models for Entity-Oriented Search,” SN Computer Science, vol. 2, no. 6. Springer, pp. 1–36, Nov. 01, 2021. doi: 10.1007/s42979-021-00828-w.
[2] C. Moreira, P. Calado, and B. Martins, “Learning to rank academic experts in the DBLP dataset,” Expert Syst., vol. 32, no. 4, pp. 477–493, Aug. 2015, doi: 10.1111/exsy.12062.
[3] Y. Zhang, D. Wang, and Y. Zhang, “Neural IR meets graph embedding: A ranking model for product search,” in The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019, May 2019, pp. 2390–2400. doi: 10.1145/3308558.3313468.
[4] T. Xu, H. Zhu, E. Chen, B. Huai, H. Xiong, and J. Tian, “Learning to annotate via social interaction analytics,” Knowl. Inf. Syst., vol. 41, no. 2, pp. 251–276, Oct. 2014, doi: 10.1007/s10115-013-0717-8.
[5] W. Yu and Z. Qin, “Spectrum-enhanced pairwise learning to rank,” in The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019, May 2019, pp. 2247–2257. doi: 10.1145/3308558.3313478.
[6] W. Wu, H. Li, and J. Xu, “Learning query and document similarities from click-through bipartite graph with metadata,” in WSDM 2013 - Proceedings of the 6th ACM International Conference on Web Search and Data Mining, 2013, pp. 687–696. doi: 10.1145/2433396.2433481.
[7] X. He, M. Gao, M. Y. Kan, and D. Wang, “BiRank: Towards Ranking on Bipartite Graphs,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 1, pp. 57–71, Jan. 2017, doi: 10.1109/TKDE.2016.2611584.
[8] J. Sanz-Cruzado, P. Castells, C. Macdonald, and I. Ounis, “Effective contact recommendation in social networks by adaptation of information retrieval models,” Inf. Process. Manag., vol. 57, no. 5, p. 102285, Sep. 2020, doi: 10.1016/j.ipm.2020.102285.
[9] K. Yuan, L. Gao, Z. Jiang, and Z. Tang, “Formula Ranking within an Article,” in Proceedings of the ACM/IEEE Joint Conference on Digital Libraries, May 2018, pp. 123–126. doi: 10.1145/3197026.3197061.
[10] H. Niu, I. Keivanloo, and Y. Zou, “Learning to rank code examples for code search engines,” Empir. Softw. Eng., vol. 22, no. 1, pp. 259–291, Feb. 2017, doi: 10.1007/s10664-015-9421-5.
[11] S. Jiang et al., “Learning query and document relevance from a web-scale click graph,” in SIGIR 2016 - Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, Jul. 2016, pp. 185–194. doi: 10.1145/2911451.2911531.
[12] X. Yang and B. Wang, “Local ranking and global fusion for personalized recommendation,” Appl. Soft Comput. J., vol. 96, p. 106636, Nov. 2020, doi: 10.1016/j.asoc.2020.106636.
[13] A. Ferraro, L. Porcaro, and X. Serra, “Balancing Exposure and Relevance in Academic Search,” 2020. Accessed: Nov. 14, 2022. [Online]. Available: https://fair-trec.github.io/2020/doc/guidelines-2020.pdf
[14] C. J. C. Burges, “From ranknet to lambdarank to lambdamart: An overview,” 2010. Accessed: Nov. 14, 2022. [Online]. Available: http://www.ccs.neu.edu/home/vip/teach/MLcourse/4_boosting/materials/msr-tr-2010-82.pdf
[15] V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech. Theory Exp., vol. 2008, no. 10, p. P10008, Oct. 2008, doi: 10.1088/1742-5468/2008/10/P10008.
[16] A. Bertolino, A. Guerriero, B. Miranda, R. Pietrantuono, and S. Russo, “Learning-to-rank vs ranking-to-learn: Strategies for regression testing in continuous integration,” in Proceedings - International Conference on Software Engineering, Jun. 2020, pp. 1261–1272. doi: 10.1145/3377811.3380369.
[17] S. Maqsood, M. A. Islam, M. T. Afzal, and N. Masood, “A comprehensive author ranking evaluation of network and bibliographic indices,” Malaysian J. Libr. Inf. Sci., vol. 25, no. 1, pp. 31–45, Apr. 2020, doi: 10.22452/mjlis.vol25no1.2.
[18] J. Shi and X.-Y. Tian, “Learning to Rank Sports Teams on a Graph,” Appl. Sci., vol. 10, no. 17, p. 5833, Aug. 2020, doi: 10.3390/app10175833.
[19] S. Agarwal, “Learning to rank on graphs,” Mach. Learn., vol. 81, no. 3, pp. 333–357, Dec. 2010, doi: 10.1007/s10994-010-5185-8.
[20] X. Zou, “A Survey on Application of Knowledge Graph,” in Journal of Physics: Conference Series, Apr. 2020, vol. 1487, no. 1, p. 012016. doi: 10.1088/1742-6596/1487/1/012016.
[21] S. Ji, S. Pan, E. Cambria, P. Marttinen, and P. S. Yu, “A Survey on Knowledge Graphs: Representation, Acquisition, and Applications,” IEEE Trans. Neural Networks Learn. Syst., vol. 33, no. 2, pp. 494–514, Feb. 2022, doi: 10.1109/TNNLS.2021.3070843.
[22] M. Fernandez et al., “Semantic search meets the Web,” in Proceedings - IEEE International Conference on Semantic Computing 2008, ICSC 2008, 2008, pp. 253–260. doi: 10.1109/ICSC.2008.52.
[23] V. Lopez, M. Sabou, and E. Motta, “PowerMap; Mapping the real semantic web on the fly,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2006, vol. 4273 LNCS, pp. 414–427. doi: 10.1007/11926078_30.
[24] K. Byrne, “Populating the Semantic Web-Combining Text and Relational Databases as RDF Graphs,” The University of Edinburgh, 2008.
[25] K. Balog et al., “SaHaRa: Discovering Entity-Topic Associations in Online News,” 2009.
[26] P. Oza, L. D.-C. workshop Proceedings, and U. 2021, “Which entities are relevant for the story?,” in Text2Story’21 Workshop, 2021, pp. 41–48. Accessed: Apr. 03, 2023. [Online]. Available: https://par.nsf.gov/biblio/10300275
[27] U. Rashid, K. Saleem, and A. Ahmed, “MIRRE approach: nonlinear and multimodal exploration of MIR aggregated search results,” Multimed. Tools Appl., vol. 80, no. 13, pp. 20217–20253, May 2021, doi: 10.1007/s11042-021-10603-x.
[28] H. Gao, L. Wu, P. Hu, Z. Wei, F. Xu, and B. Long, “Graph-augmented Learning to Rank for Querying Large-scale Knowledge Graph,” Nov. 2021, Accessed: Mar. 17, 2023. [Online]. Available: http://arxiv.org/abs/2111.10541
[29] H. Hosseini and E. Bagheri, “Learning to rank implicit entities on Twitter,” Inf. Process. Manag., vol. 58, no. 3, p. 102503, May 2021, doi: 10.1016/j.ipm.2021.102503.
[30] H. Wu and F. J. Meng, “Research on the Application of Personalized Course Recommendation of Learn to Rank Based on Knowledge Graph,” in Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, 2020, vol. 331, pp. 19–30. doi: 10.1007/978-3-030-62205-3_2.
[31] G. Maheshwari, P. Trivedi, D. Lukovnikov, N. Chakraborty, A. Fischer, and J. Lehmann, “Learning to Rank Query Graphs for Complex Question Answering over Knowledge Graphs,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, vol. 11778 LNCS, pp. 487–504. doi: 10.1007/978-3-030-30793-6_28.
[32] Y. Su et al., “Reducing Bug Triaging Confusion by Learning from Mistakes with a Bug Tossing Knowledge Graph,” in Proceedings - 2021 36th IEEE/ACM International Conference on Automated Software Engineering, ASE 2021, 2021, pp. 191–202. doi: 10.1109/ASE51524.2021.9678574.
[33] P. Jafarzadeh, Z. Amirmahani, and F. Ensan, “Learning to Rank Knowledge Subgraph Nodes for Entity Retrieval,” in SIGIR 2022 - Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Jul. 2022, pp. 2519–2523. doi: 10.1145/3477495.3531888.
[34] Y. Ni et al., “Semantic documents relatedness using concept graph representation,” in WSDM 2016 - Proceedings of the 9th ACM International Conference on Web Search and Data Mining, Feb. 2016, pp. 635–644. doi: 10.1145/2835776.2835801.
[35] N. Zhiltsov and E. Agichtein, “Improving entity search over linked data by modeling latent semantics,” in International Conference on Information and Knowledge Management, Proceedings, 2013, pp. 1253–1256. doi: 10.1145/2505515.2507868.
[36] O. Irrera and G. Silvello, “Background Linking: Joining Entity Linking with Learning to Rank Models.,” ceur-ws.org, vol. 2816, 2021, Accessed: Aug. 24, 2022. [Online]. Available: http://ceur-ws.org/Vol-2816/paper6.pdf
[37] M. Bendersky and W. B. Croft, “Modeling higher-order term dependencies in information retrieval using query hypergraphs,” in SIGIR’12 - Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, Aug. 2012, pp. 941–950. doi: 10.1145/2348283.2348408.
[38] T. Menezes and C. Roth, “Semantic Hypergraphs,” Aug. 2019, Accessed: Apr. 07, 2023. [Online]. Available: http://arxiv.org/abs/1908.10784
[39] L. Dietz, “ENT rank: Retrieving entities for topical information needs through entity-neighbor-text relations,” in SIGIR 2019 - Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, Jul. 2019, pp. 215–224. doi: 10.1145/3331184.3331257.
[40] B. A., “ObjectRank : Authority-Based Keyword Search in Databases,” VLDB 2004, 2004.
[41] S. Chakrabarti, “Dynamic personalized pagerank in entity-relation graphs,” in 16th International World Wide Web Conference, WWW2007, May 2007, pp. 571–580. doi: 10.1145/1242572.1242650.
[42] L. Espín-Noboa, F. Lemmerich, S. Walk, M. Strohmaier, and M. Musen, “HopRank: How semantic structure influences teleportation in PageRank (a case study on bioPortal),” in The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019, May 2019, pp. 2708–2714. doi: 10.1145/3308558.3313487.
[43] R. Delbru, N. Toupikov, M. Catasta, G. Tummarello, and S. Decker, “Hierarchical link analysis for ranking web data,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, vol. 6089 LNCS, no. PART 2, pp. 225–239. doi: 10.1007/978-3-642-13489-0_16.
[44] C. Musto, G. Semeraro, M. de Gemmis, and P. Lops, “Tuning personalized pagerank for semantics-aware recommendations based on linked open data,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, vol. 10249 LNCS, pp. 169–183. doi: 10.1007/978-3-319-58068-5_11.
[45] I. C. Dourado, D. C. G. Pedronette, and R. da S. Torres, “Unsupervised graph-based rank aggregation for improved retrieval,” Inf. Process. Manag., vol. 56, no. 4, pp. 1260–1279, Jul. 2019, doi: 10.1016/j.ipm.2019.03.008.
[46] M. Bałchanowski and U. Boryczka, “Aggregation of Rankings Using Metaheuristics in Recommendation Systems,” Electronics, vol. 11, no. 3, p. 369, Jan. 2022, doi: 10.3390/electronics11030369.
[47] Y. Zhang, Y. Xiao, J. Wu, and X. Lu, “Comprehensive world university ranking based on ranking aggregation,” Comput. Stat., vol. 36, no. 2, pp. 1139–1152, Jun. 2021, doi: 10.1007/s00180-020-01033-8.
[48] L. P. Valem and D. C. G. Pedronette, “Graph-based selective rank fusion for unsupervised image retrieval,” Pattern Recognit. Lett., vol. 135, pp. 82–89, Jul. 2020, doi: 10.1016/j.patrec.2020.03.032.
[49] J. Y. Yeh and C. J. Tsai, “A Graph-based Feature Selection Method for Learning to Rank Using Spectral Clustering for Redundancy Minimization and Biased PageRank for Relevance Analysis,” Comput. Sci. Inf. Syst., vol. 19, no. 1, pp. 141–164, Jan. 2022, doi: 10.2298/CSIS201220042Y.
[50] J. Y. Yeh and C. J. Tsai, “Graph-based Feature Selection Method for Learning to Rank,” in ACM International Conference Proceeding Series, Nov. 2020, pp. 70–73. doi: 10.1145/3442555.3442567.
[51] B. Geng, L. Yang, and X.-S. Hua, “Learning to Rank with Graph Consistency,” 2009. [Online]. Available: https://www.microsoft.com/en-us/research/wp-content/uploads/2009/08/MSRA-TR-CAR.pdf
[52] J. Fan, H. Luo, Y. Gao, and R. Jain, “Incorporating concept ontology for hierarchical video classification, annotation, and visualization,” IEEE Trans. Multimed., vol. 9, no. 5, pp. 939–957, Aug. 2007, doi: 10.1109/TMM.2007.900143.