Manuscript ID : iranaict-47079 Visit : 1085 Page: 240 - 263

Article Type: Review Article

Survey on the Applications of the Graph Theory in the Information Retrieval

Subject Areas : ICT

Maryam Piroozmand ¹ , Amir Hosein Keyhanipour ² , Ali Moeini ³

1 -
2 - University of Tehran
3 -

Received: 2023-06-05 Accepted : 2023-09-05 Published : 2024-06-20

Keywords: Graph Theory, Information Retrieval, Learning to Rank, Knowledge Graph, Graph-based Dataset Representation,

Abstract :

Due to its power in modeling complex relations between entities, graph theory has been widely used in dealing with real-world problems. On the other hand, information retrieval has emerged as one of the major problems in the area of algorithms and computation. As graph-based information retrieval algorithms have shown to be efficient and effective, this paper aims to provide an analytical review of these algorithms and propose a categorization of them. Briefly speaking, graph-based information retrieval algorithms might be divided into three major classes: the first category includes those algorithms which use a graph representation of the corresponding dataset within the information retrieval process. The second category contains semantic retrieval algorithms which utilize the graph theory. The third category is associated with the application of the graph theory in the learning to rank problem. The set of reviewed research works is analyzed based on both the frequency as well as the publication time. As an interesting finding of this review is that the third category is a relatively hot research topic in which a limited number of recent research works are conducted.

References:

[1] C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Information Retrieval. Cambridge University Press, 2008. doi: 10.1017/cbo9780511809071.
[2] R. Baeza-Yates, Modern Information Retrieval: The Concepts and Technology Behind Search, Second Eit. Addison-Wesley Professional, 2011.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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
[16] 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
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] K. Byrne, “Populating the Semantic Web-Combining Text and Relational Databases as RDF Graphs,” The University of Edinburgh, 2008.
[27] K. Balog et al., “SaHaRa: Discovering Entity-Topic Associations in Online News,” 2009.
[28] 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
[29] 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.
[30] 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
[31] 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.
[32] 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.
[33] 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.
[34] 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.
[35] 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.
[36] 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.
[37] 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.
[38] 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
[39] 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.
[40] T. Menezes and C. Roth, “Semantic Hypergraphs,” Aug. 2019, Accessed: Apr. 07, 2023. [Online]. Available: http://arxiv.org/abs/1908.10784
[41] 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.
[42] B. A., “ObjectRank : Authority-Based Keyword Search in Databases,” VLDB 2004, 2004.
[43] 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.
[44] 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.
[45] 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.
[46] 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.
[47] H. Li, “Learning to Rank for Information Retrieval and Natural Language Processing, Second Edition,” Synth. Lect. Hum. Lang. Technol., vol. 7, no. 3, pp. 1–123, Oct. 2015, doi: 10.2200/S00607ED2V01Y201410HLT026.
[48] 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.
[49] 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.
[50] 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.
[51] 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.
[52] 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.
[53] 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.
[54] 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
[55] 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.
[56] Y. Li et al., “LtrGCN: Large-Scale Graph Convolutional Networks-Based Learning to Rank for Web Search,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 14174 LNAI, pp. 635–651, 2023, doi: 10.1007/978-3-031-43427-3_38.
[57] A. H. Keyhanipour, “Graph-based comparative analysis of learning to rank datasets,” Int. J. Data Sci. Anal., vol. 17, no. 2, pp. 165–187, Mar. 2024, doi: 10.1007/S41060-023-00406-8/METRICS.
[58] M. Xu and J. Zhang, “MGL2Rank: Learning to rank the importance of nodes in road networks based on multi-graph fusion,” Inf. Sci. (Ny)., vol. 667, p. 120472, May 2024, doi: 10.1016/J.INS.2024.120472.

Full-Text:

$G:\دوفصلنامه ارتباطات و فناوری اطلاعات\ITRC-Logo\Farsi - v2.png$ دوفصلنامه

فناوری اطلاعات و ارتباطات ایران

سال شانزدهم، شماره های 59 و 60، بهار و تابستان 1403، صفحه 240 الی 263

Survey on the Applications of the Graph Theory in the Information Retrieval

Maryam Piroozmand1, Amir Hosein Keyhanipour2 ¹, Ali Moeini3

1 Faculty of Engineering Science, School of Engineering, University of Tehran, Tehran, Iran

2 Computer Engineering Department, Faculty of Engineering, College of Farabi, University of Tehran, Tehran, Iran

3 Faculty of Engineering Science, School of Engineering, University of Tehran, Tehran, Iran

Received: 05 June 2023, Revised: 12 August 2023, Accepted: 05 September 2023

Paper type: Review

Abstract

Keywords: Graph Theory, Information Retrieval, Learning to Rank, Knowledge Graph, Graph-based Dataset Representation.

بررسی کاربردهای نظریه گراف در بازیابی اطلاعات

مریم پیروزمند1، امیرحسین کیهانی پور2²، علی معینی3

1 گروه الگوریتم و محاسبات، دانشکده علوم مهندسی، دانشکدگان فنی، دانشگاه تهران، تهران، ایران

2 گروه مهندسی کامپیوتر، دانشکده مهندسی، دانشکدگان فارابی، دانشگاه تهران، تهران، ایران

3 گروه الگوریتم و محاسبات، دانشکده علوم مهندسی، دانشکدگان فنی، دانشگاه تهران، تهران، ایران

تاریخ دریافت: 15/03/1402 تاریخ بازبینی: 21/05/1402 تاریخ پذیرش: 14/06/1402

نوع مقاله: مروری

چکيده

نظریه گراف بواسطه توانمندی در مدلسازی روابط پیچیده بین عناصر در مسائل مختلف، بصورت گسترده مورد استفاده قرار گرفته است. از سوی دیگر، بازیابی اطلاعات یعنی استخراج اطلاعات مورد نیاز کاربر، به عنوان یکی از مسائل مهم در دنیای الگوریتم و محاسبات مطرح است. با توجه به کارآمدی راهکارهای مبتنی بر گراف در بازیابی اطلاعات، این مقاله، به بررسی تحلیلی و دسته‏بندی کاربردهای نظریه گراف در بازیابی اطلاعات، می‏پردازد. این راهکارها در سه دسته کلی، قابل تفکیک هستند؛ دسته نخست، شامل الگوریتم‏هایی می‏باشد که در آنها از بازنمایی گرافی دادگان در فرآیند بازیابی اطلاعات، استفاده می‏شود. دسته دوم پژوهش‏ها، به حل مسئله بازیابی معنایی اطلاعات با استفاده از نظریه گراف می‏پردازند و نهایتا دسته سوم، مربوط به یادگیری رتبه‏بندی با استفاده از نظریه گراف است. این سه دسته بصورت جزئی‏تر در هشت زیردسته، دسته‏بندی شده‏اند. همچنین از منظر آماری، پژوهش‏های صورت گرفته در هر دسته‏ بر اساس تعداد و سال انتشار، بررسی شده‏اند. از جمله یافته‏های این مطالعه، این است که دسته سوم، هم از نظر تعداد پژوهش‏ها و نیز سال انتشار آنها، شاخه نوظهوری محسوب می‏شود و می‏تواند حوزه تحقیقاتی جالب توجهی برای محققان محسوب ‏شود.

کلیدواژگان: نظریه گراف، بازیابی اطلاعات، یادگیری رتبه‏بندی، گراف دانش، بازنمایی گرافی دادگان.

[1] * Corresponding Author’s email: keyhanipour@ut.ac.ir

[2] * رایانامة نويسنده مسؤول: keyhanipour@ut.ac.ir

1- مقدمه

بازیابی اطلاعات به عنوان یکی از بنیادی‏ترین مسائل دنیای فناوری اطلاعات، فرآیندی است که هدف آن فراهم نمودن امکان دستیابی کاربر به اطلاعات مورد نیاز، می‏باشد. با این وجود، فرآیند بازیابی اطلاعات، با چالشهای زیادی مواجه است. بخشی از این معضلات، بواسطه حجم بسیار زیاد اطلاعات مورد جستجو، بروز می‏کند. از سوی دیگر غیر ساخت‏یافته بودن اطلاعات و مسائل مربوط به تشخیص دقیق نیازمندی‏های کاربران، شناسایی اطلاعات مرتبط با نیاز آنان را امری دشوار ساخته است. این چالشها در خصوص سامانه‏های بازیابی اطلاعات وب، به ویژه جویشگرهای وب و نیز سامانه‏های توصیه‏گر، بسیار جدی‏تر است. از این رو، بهره‏گیری از قابلیت‏های دیگر ابزارهای نظری و عملیاتی به منظور ارتقا کیفیت بازیابی اطلاعات، همواره یکی از علاقه‏مندی‏های پژوهشگران و صاحب‏نظران بوده است. بصورت مشخص، نظریه گراف، به عنوان رویکردی برای مدلسازی روابط میان عناصر درگیر در مسائل مختلف که به لحاظ نظری، پیشینه و غنای بالایی دارد، به عنوان یکی از رویکردهای ارتقای بازیابی اطلاعات و ارائه مدل‏های کارآمد در این زمینه، همواره مورد توجه جامعه پژوهشگران بوده است.

در این نوشتار، بصورت مشخص، به مطالعه، بررسی و دسته‏بندی تحقیقات صورت گرفته در زمینه بهره‏گیری از نظریه گراف در فرآیند بازیابی اطلاعات، خواهیم پرداخت. نویسندگان این مقاله بر این باور هستند که این کار می‏تواند ضمن تببین کارآمدی استفاده از نظریه گراف در بازیابی اطلاعات، دیدگاه مناسبی در خصوص انواع کاربرد این نظریه در حل چالش‏های فرآیند بازیابی اطلاعات، در اختیار پژوهشگران قرار دهد و در عین حال، با دسته‏بندی و تحلیل نقاط قوت و ضعف این روش‏ها، شرایط را به منظور ارائه روش‏های کارآمدتر، فراهم آورد. برای نیل به این مقصود، در این نوشتار، بیش از پنجاه پژوهش شاخص در این زمینه، مورد مطالعه و بررسی قرار گرفته است و کوشش شده است تا با دسته‏بندی و ارزیابی تحلیلی آنها، شناخت جامعی در زمینه پژوهش‏های صورت گرفته در رابطه با بکارگیری نظریه گراف در حوزه بازیابی اطلاعات، فراهم آید.

در ادامه، در بخش 2، دسته‏بندی جامعی از پژوهش‏های انجام شده در زمینه بازیابی اطلاعات بر پایه نظریه گراف، در قالب سه دسته کلی و هشت زیر دسته، ارائه خواهد شد. پس از آن، در بخش 3، به اختصار نسبت به معرفی شاخص‏های ارزیابی مورد استفاده در ارزیابی عملکرد الگوریتم‏های بازیابی اطلاعات مبتنی بر گراف، پراخته خواهد شد و سپس در بخش‌های 4، 5 و 6، پژوهش‏های مرتبط با هر یک از سه دسته فوق‏الذکر، بصورت تحلیلی، بررسی خواهد شد. نهایتا بخش 7 نیز به جمع‏بندی و نتیجه‏گیری حاصل از این پژوهش اختصاص یافته است.

2- دسته‏بندی پژوهش‏های صورت گرفته

با توجه به کاربردی بودن نظریه گراف در مدل‏سازی کارآمد عناصر مسئله بازیابی اطلاعات، پژوهش‏های گسترده‏ای در زمینه بکارگیری نظریه گراف در فرآیند بازیابی اطلاعات، صورت گرفته است. این پژوهش‏ها چه از منظر رویکرد و نحوه حل مسئله و چه از نظر شاخص‏های ارزیابی مورد استفاده در ارزیابی عملکرد الگوریتم‏های ارائه شده و نیز مجموعه دادگان مورد استفاده در فرآیند ارزیابی، بسیار متنوع و متفاوت هستند. از این رو به منظور تسهیل بررسی این پژوهش‏ها، ابتدا بایستی به نحوی، اقدام به دسته‏بندی آنها نمود. برای نیل به این مقصود، در این نوشتار با عنایت به نوع مسئله مورد مطالعه در پژوهش‏های مورد مطالعه و همچنین نحوه بهره‏گیری از نظریه گراف در فرآیند بازیابی اطلاعات در آنها، کوشش شده است تا دسته‏بندی کلانی از این پژوهش‏ها، ارائه گردد و سپس به صورت تفصیلی، به بررسی روش‏های ارائه شده در هر دسته نیز پرداخته شود.

بطور کلی، می‏توان حوزه بازیابی اطلاعات را از نظر نوع داده‏های مورد بازیابی، به دو دسته عمده بازیابی اطلاعات متنی و بازیابی اطلاعات وب، تقسیم‏بندی نمود ]1[. از سوی دیگر، این تفکیک می‏تواند از منظر نحوه انجام فرآیند بازیابی اطلاعات نیز صورت گیرد ]2[. در این صورت، روش‏های متداول تحت عنوان سبد کلمات (BOW) و روش‏های بازیابی معنایی، می‏توانند مورد استفاده، واقع شوند. با توجه به این ملاحظات، می‏توان گفت که بطور کلی، چهار دسته کلان از الگوریتم‏ها در حوزه بازیابی اطلاعات، مطرح هستند. از سوی دیگر، در بررسی‏های انجام شده در حوزه کاربرد نظریه گراف در بازیابی اطلاعات، روش بازیابی اطلاعات متنی عمدتا با استفاده از مدل سبد کلمات، صورت گرفته است. لذا، کاربردهای نظریه گراف در فرآیند بازیابی اطلاعات، در سه دسته کلی، به شرح ذیل، قابل تفکیک و دسته‏بندی است:

· الف) بازیابی اطلاعات بر مبنای ارائه بازنمایی گرافی از دادگان بازیابی اطلاعات که در دو دسته کلی زیر، قابل تفکیک می‏باشند:

o بازنمایی گرافی دادگان جهت استخراج ویژگی‏های مبتنی بر گراف و ترکیب این ویژگی‏ها با ویژگی‏های پایه دادگان مسئله به منظور ارائه راهکارهای نوین در حوزه بازیابی اطلاعات.

o استخراج ویژگی‏های آماری دادگان و ارائه بازنمایی گرافی این ویژگی‏ها

· ب) بازیابی معنایی اطلاعات با استفاده از نظریه گراف که در چهار دسته زیر، قابل دسته‏بندی می‏باشند ]3[:

o بازیابی اطلاعات با استفاده از گراف دانش

o ایجاد گراف موجودیت بر اساس دادگان مسئله بازیابی اطلاعات

o مدل‏های مبتنی بر هایپر گراف‏

o مدل‏های مبتنی بر گراف پویش تصادفی

· ج) ارائه بازنمایی گرافی از مسائل حوزه یادگیری رتبه‏بندی که در دو دسته‏ اصلی ایجاد رتبه‏بندی و تجمیع رتبه‏بندی، تقسیم‌بندی می‏شوند.

در شکل 1 نمایی از این دسته‏بندی ارائه شده است.

شکل 1. دسته‏بندی پیشنهادی از روش‏های مطرح شده در زمینه بکارگیری نظریه گراف در بازیابی اطلاعات

در ادامه این بخش، به بیان برخی از پژوهش‏های اصلی صورت گرفته در هر یک از سه دسته فوق‏الذکر، پرداخته خواهد شد. ضمن اینکه بایستی خاطر نشان نمود، در انتخاب پژوهش‏های مرتبط با هر دسته، عمدتا تاکید بر انتخاب مقالات سال‏های اخیر بوده است. علاوه بر آن، دسته‏بندی فوق‏الذکر، بر مبنای پژوهش‏های صورت گرفته است. بر این اساس، ممکن است حوزه‏های پژوهشی بالقوه‏ای در ذیل هر دسته مطرح باشد که تا کنون به آنها پرداخته نشده باشد. شناسایی این شکاف‏های تحقیقاتی و عرضه آنها به عنوان حوزه‏های تحقیقاتی بکر، یکی از اهداف اصلی این نوشتار می‏باشد.

3- شاخص‏های ارزیابی مورد استفاده در ارزیابی عملکرد الگوریتم‏های بازیابی اطلاعات مبتنی بر گراف

در ارزیابی الگوریتم‏های ارائه شده در حوزه بازیابی اطلاعات بر پایه نظریه گراف، مشخص شد، عمده پژوهش‏ها بر اساس شاخص‏های استاندارد بازیابی اطلاعات نظیر P@n، MAP، MRR، ERR@n و NDCG، نسبت به بررسی عملکرد خود در قبال روش‏‏های پایه، اقدام نموده‏اند. از این رو، در این بخش، به اختصار نسبت به معرفی این شاخص‏ها خواهیم پرداخت.

· شاخص MRR¹: عکس موقعیت نخستین پاسخ مرتبط در بین فهرست نتایج جستجو را نشان می‏دهد ]1[:

که n برابر با موقعیت اولین پاسخ مرتبط با پرس‏وجوی کاربر در بین فهرست نتایج جتسجو می‏باشد.

· دقت² در نقطه k (): اگر قضاوت انساني در خصوص میزان مرتبط بودن اسناد به پرس‏وجوهای کاربران، به‌صورت دودويي در اختيار باشد، مثلاً برچسب اسناد مرتبط، يک و برچسب اسناد نامرتبط، صفر باشد، در این صورت، به‌صورت زير تعريف مي‌شود ]1[:

که تابع شاخص است و به برچسب سند قرار گرفته در موقعيت ليست مرتب نتايج، ، اشاره مي‌کند.

· متوسط ميانگين دقت³ (): بر اساس تعريف ارائه شده از دقت در موقعيت ، میانگین دقت⁴ () عبارتست از ]1[:

در رابطه فوق، تعداد کل اسناد متناظر پرس‌وجوي است و تعداد زير مجموعه‌اي از اين اسناد است که میزان مرتبط بودن آنها برابر با يک باشد. مقدار ميانگين روي همه پرس‌وجوهاي آزمون، متوسط ميانگين دقت () ناميده مي‌شود.

· بهره انباشته کاهشی هنجار شده⁵ (NDCG) در نقطه (): این شاخص بر پایه میانگین‏گیری از شاخص بهره انباشته کاهشي⁶ ()، محاسبه می‏شود. شاخص بهره انباشته کاهشي () مي‌تواند قضاوت‌هاي ميزان مرتبط بودن را که به‌صورت طبقه‌بندي‌هاي مرتب چندگانه ارائه شده باشند، در ارزیابی مورد استفاده قرار دهد؛ ضمن آنکه در تعريف آن، يک ضريب کاهشي بر اساس موقعيت اسناد، در نظر گرفته شده است ]1[. برای بیان این موضوع به زبان رياضي، فرض کنيد که ليست مرتبي از نتايج نظير به ازاي پرس‌وجوي وجود داشته باشد؛ در اين صورت، مقدار شاخص در موقعيت به‌صورت زير، تعريف مي‌شود:

که در آن، رتبه يک سند است که عموماً به ‌صورت بیان مي‌شود. همچنین يک ضريب کاهشي بر اساس موقعيت سند است، که غالباً به‌صورت تعريف مي‌شود. با هنجار سازي مقادير با يک مقدار بيشينه (مثلاً ) شاخص بهره انباشته کاهشی هنجار شده () حاصل مي‌گردد که عبارتست از:

· رتبه متقابل مورد انتظار⁷ (ERR) در نقطه (): این شاخص احتمال برآورده شدن نیاز کاربر پس از مشاهده k سند نخست موجود در فهرست نتایج جستجو را نشان می‏دهد. اگر احتمال تامین نیاز کاربر در سند k برابر با باشد و طول فهرست پاسخ‏های به پرس‏وجوی کاربر، K سند باشد، آنگاه ]1[:

4- بازیابی اطلاعات بر مبنای ارائه بازنمایی گرافی از دادگان بازیابی اطلاعات

ایده کلی این روش‏ها، بهره‏گیری از قابلیت نظریه گراف در مدل‏سازی روابط پیچیده بین عناصر مسئله، به منظور ارائه یک مدل مبتنی بر گراف از دادگان مسئله بازیابی اطلاعات است. البته رویکرد انجام اینکار در هر زیر دسته متفاوت است. به عنوان مثال، الگوریتم‏های دسته نخست، مستقیما با اعمال نظریه گراف روی دادگان مورد استفاده، یک بازنمایی گرافی از آن، ایجاد نموده و سپس با استخراج ویژگی‏های مبتنی بر این گراف و ترکیب ویژگی‏های بدست آمده با ویژگی‏های پایه دادگان مسئله، به ارائه الگوریتم‏های بازیابی اطلاعات متناسب با مسئله مورد بررسی می‏پردازند. در مقابل، از ویژگی‏های آماری دادگان مسئله، اقدام به تولید بازنمایی گرافی متناظر با این ویژگی‏ها می‏کنند.

4-1- بازنمایی گرافی دادگان جهت استخراج ویژگی‏های مبتنی بر گراف و ترکیب این ویژگی‏ها با ویژگی‏های پایه دادگان مسئله

از جمله پژوهش‏های صورت گرفته در دسته اول می‏توان به کار تحقیقاتی ]4[ اشاره نمود که در آن، روشی برای جستجوی افراد مرتبط با حوزه علمی مورد نظر کاربر، پیشنهاد شده است. در روش پیشنهادی، برای تخمین میزان تخصص پژوهشگران مختلف، از دو رویکرد مختلف استفاده شده است. روش نخست، با استفاده از اطلاعات متنی از جمله داده‏های مندرج در پروفایل محققان مختلف، تخمینی از میزان خبرگی آنان را محققان مختلف، بدست می‏دهد و در مقابل، روش دوم، بر اساس گراف ارجاعات بین مقالات مختلف، میزان تخصص هر پژوهشگر را تعیین می‏نماید. سپس با تلفیق این دو تخمین با کمک روش‏های یادگیری رتبه‏بندی تحت نظارت و نیز الگوریتم‏های تجمیع رتبه‏بندی و نیز الگوریتم‏های ترکیب اطلاعات، رتبه‏بندی نهایی، تعیین می‏گردد. در آزمایش‏های صورت گرفته به منظور ارزیابی روش پیشنهادی، از مجموعه داده DBLP استفاده شده است. چند نمونه از ویژگی‏های گراف ارجاعات که در این تحقیق مورد استفاده واقع شده است، عبارتند از: شاخص Hirsch که به ازای یک پژوهشگر خاص، ترکیبی از میزان کلی تولید علم توسط وی و نیز میزان اعتبار موسسه تحقیقاتی متبوع او را نشان می‏دهد، شاخص Hirsch مبتنی بر پرس‏وجوی کاربر که میزان معتبر بودن یک پژوهشگر در یک حوزه علمی خاص را نشان می‏دهد، شاخص Hirsch مبتنی بر زمان، شاخص آلفا که میزان تاثیر گذاری مهمترین مقالات یک فرد یا موسسه متبوع وی را نشان می‏دهد و نیز شاخص که میزان مازاد ارجاعات یک محقق را که در محاسبه شاخص لحاظ نمی‏شوند، را تعیین می‏کند. نتایج ارزیابی نشان می‏دهد که ترکیب ویژگی‏های متنی مستخرج از پروفایل و نیز ویژگی‏های برگرفته از گراف ارجاعات، توانسته است مطابق شاخص‏های ارزیابی استاندارد نظیر P@n، NDCG@n و MAP، نسبت به الگوریتم‏های مرجع، به عملکرد مناسب‏تری دست یابد. همچنین در ]5[ برای رتبه‏بندی محصولات مورد درخواست کاربران در سیستم‏های درخواست دهنده، خصوصیات ساختار گراف و مدل شبکه عصبی را ادغام کرده است. این کار دو مزیت دارد: اول اینکه با استفاده از ساختار گراف می‏توان مشکل کم تعداد بودن تعداد درخواست‏ها به ازای برخی ازکالاها در سیستم‏های توصیه‏گر را حل کرد (مقابله با پراکندگی محصولات و درخواست‏ها). همچنین می‏توان از ساختار گراف دوبخشی، اطلاعاتی در خصوص ارتباط گره‏های بین هر بخش گراف بدست آورد (ترکیب اطلاعات خارجی ناهمگن برای کمک به بهبود رتبه‏بندی در شبکه عصبی). در این مقاله بر روی دادگان CIKM Cup 2016 Track 2 مدل رتبه‏بندی شامل گراف برای جستجوی محصولات ارائه داده است و با استفاده از مقایسه شاخص‏های MRR، MAP و NDCG نشان داده است که مدل پیشنهادی، عملکرد بهتری نسبت به مدل‏های ارائه شده قبلی دارد. مزیت این الگوریتم استفاده از اطلاعات خاصیت تعدی در پیش بینی ارتباطات است که با استفاده از خواص گراف و از ارتباطات بین آیتم‏ها حاصل می‏شود. همچنین در مقاله ]6[، به موضوع تولید یک روش حاشیه نگاری⁸ خودکار برای داده‏های چند رسانه‏ای پرداخته شده است، به نحوی که به ازای هر قلم داده چند رسانه‏ای، متن مستخرج از این روش، عملاً معادل متن توصیف آن داده خواهد بود و بر اساس آن، می‏توان رتبه‏بندی داده‏های چند رسانه‏ای را بر اساس نیاز اطلاعاتی کاربر، به صورت یک الگوریتم یادگیری رتبه‏بندی، انجام داد. در پژوهش‏هاي قبلي که بر روی حاشیه نگاری خودکار ارایه شده، معمولا از ابرداده⁹ استفاده شده است که در اغلب موارد در دسترس نیست. در روش پیشنهادی، بر اساس تعاملات کاربر در دسترسی به هر یک از اقلام داده چند رسانه‏‏ای، گرافی تحت عنوان گراف تعاملات¹⁰ ایجاد می‏گردد. با توجه به این واقعیت که تعداد این داده‏ها بسیار زیاد است، به منظور کاهش پیچیدگی زمانی الگوریتم، به صورت تدریجی و بازگشتی، در هر بازه زمانی مشخص، تعدادی از داده‏های شاخص‏تر و حائز اهمیت بیشتر، در تولید زیر گراف تعاملات، مورد استفاده قرار می‏گیرند. نکته قابل توجه در ایده پیشنهادی، استفاده از دو دسته از ویژگی‏های مختلف در توصیف مشخصات گراف تعاملات است. یکی از این دو دسته، ویژگی‏های ایستا¹¹ است که عمدتاً بر پایه نتایج آماری حاصل از ترجیح بعضی از اقلام داده چند رسانه‏ای نسبت به بقیه توسط کاربران، استخراج می‏شوند و وابسته به ساختار گراف ترجیحات نیستند. در مقابل، دسته دوم، عمدتا شامل ویژگی‏های توپولوژیک و ساختاری¹² گراف مانند ضریب خوشه‏بندی است. این دو دسته ویژگی، به عنوان ورودی به الگوریتم‏های پایه رتبه‏بندی نظیر RankBoost و AdaRank، عرضه می‏شوند و امکان ایجاد اولویت‌بندی بین اقلام داده‏ای ممکن را فراهم می‏سازند. برای ارزیابی عملکرد روش پیشنهادی، از مجموعه سوابق اطلاعات وبسایت Douban طی یک بازه شش ساله و در دو بخش کتاب و فیلم، استفاده شده است. همچنین از الگوریتم‏های شاخص یادگیری رتبه‏بندی نظیر AdaRank و AdaBoost، در ارزیابی نتایج روش پیشنهادی، بهره گرفته شده است. ضمنا شاخص‎‏های ارزیابی مورد استفاده عبارتند از: P@n، MAP و NDCG. نکته جالب توجه در خصوص نتایج آزمایش‏های به عمل آمده، این است که طی آنها سعی شده است تا نقش و تاثير هر يك از اين دو دسته ويژگي‏های ایستا و توپولوژیک در فرآيند يادگيري رتبه‏بندي مطابق شاخص‏هاي ارزيابي رتبه‏بندي، تعیین شود. در این خصوص ذكر اين نكته نیز حائز اهمیت است که در برخی شرایط، بکارگیری صرف ویژگی‏های توپولوژیک، منجر به بهبود بیشتر رتبه‏بندی در قیاس با ویژگی‏های ایستا شده است. ضمن آنكه همواره تركيب اين دو دسته ويژگي‏ها نسبت به هر دسته، منجر به عملكرد بهتري مي‏شود. با توجه به ضعف عملکرد این الگوریتم در شرایط محدود بودن محتوای متنی، توسعه الگوریتم به منظور جبران این نقیصه، حائز اهمیت است. همچنین نظر به هزینه‏بر بودن اجرای متوالی گام‏های استخراج ویژگی‏ها و رتبه‏بندی زیر گراف‏ها، می‏توان به ادغام این دو گام در قالب یک گام واحد نیز پرداخت. دستیابی به یک شرط توقف خودکار که مصالحه مابین هزینه و دقت عملکرد را ممکن سازد، نیز جالب توجه می‏باشد. از سوی دیگر، نویسندگان ]7[، بر مبنای نظریه گراف‏ها، الگوریتم یادگیری رتبه‏بندی جدیدی را برای بهبود عملکرد سامانه‏های توصیه‏گر ارائه نموده‏اند. ایده اصلی آنها، محاسبه دسته‏ای از ویژگی‏ها بر اساس هایپرگراف¹³ ارتباط بین کاربران و کالاهای عرضه شده توسط سامانه است. مسئله مورد نظر در این مقاله، بهبود عملکرد سامانه‏هاي توصيه‏گر با عرضه گونه جديدي از ويژگي‏ها موسوم به ویژگی‏های طیفی¹⁴ است. در واقع ويژگي‏هاي بصري و متني كه در الگوريتم‏هاي پايه رتبه‏بندي در سامانه‏هاي توصيه‏گر، مورد استفاده قرار مي‏گيرند، ممكن است به ازاي همه اقلام كالايي و همه كاربران، موجود نباشد. در اين شرايط، ویژگی‏های طیفی همچنان قابل محاسبه و استفاده خواهند بود. بر اين اساس، ایده اصلی این مقاله، ایجاد یک هایپرگراف¹⁵ روی کاربران و اقلام است. یک هایپرگراف، تعمیمی از گراف ساده است که در آن یک هایپریال¹⁶ تعدادی از رئوس (و نه لزوماً فقط دو راس) را به هم متصل می‏سازد. در ادامه، مجموعه‏ای از ویژگی‏ها موسوم به ویژگی‏های طیفی با استفاده از ماتریس لاپلاسین، استخراج می‏شوند. برای این منظور از ماتریس لاپلاسین، مقادیر ویژه استخراج می‏شود و سپس با استفاده از k مقدار ویژه بیشینه، ماتریس ویژگی‏های طیفی¹⁷، استخراج می‏گردد. ویژگی‏های طیفی، میزان مشابهت کاربران و اقلام کالایی را در نمایش گرافی سامانه‏‏های توصیه‏گر نشان می‏دهند. به كمك اين ويژگي‏ها، يك الگوريتم يادگيري رتبه‏بندي جفتي¹⁸ ايجاد مي‏گردد كه قادر است اولويت نسبي كالاها به ازاي يك كاربر خاص را تعيين نمايد. به منظور ارزیابی عملکرد روش پیشنهاد شده، از مجموعه دادگان وبسایت آمازون در دو بخش البسه و جواهرات، استفاده شده است. نتایج ارزیابی عملکرد الگوریتم ارائه شده نسبت به روش‏های مرجع نظیر فاکتورسازی ماتریس احتمالاتی¹⁹، رتبه‏بندی شخصی‏شده بیزین²⁰، رتبه‏بندی شخصی‏شده بیزین بر مبنای ترجیح گروهی²¹ و نیز رتبه‏بندی شخصی‏شده بیزین بصری²²، حاکی از تفوق این الگوریتم بر اساس شاخص‏های F1 و NDCG@n می‏باشد. از آنجا که روش پیشنهادی در شرایطی قادر به عملکرد مناسب است که بازخورد صریح کاربران به ازای کالاهای مورد نظر در اختیار باشد، لذا توسعه این الگوریتم در حالتی که بازخورد صریح در اختیار نباشد، حائز اهمیت خواهد بود. همچنین در مقاله ]8[ به منظور یافتن میزان مشابهت بین عناصر داده‏ای مختلف نظیر اسناد و پرس‏وجوها و بهبود نتایج رتبه‏بندی، الگوریتم جدیدی ارائه شده است. ابتدا بایستی توجه داشت که در کارهای قبلی عمدتاً از دو دسته از روش‏های رتبه‏بندی یعنی «روش‏های رتبه‏بندی مبتنی بر ویژگی‏ها» و «روش‏های مبتنی بر گراف بین اسناد و پرس‏وجوها»، استفاده شده است. بر این اساس، در اين مقاله، نقاط قوت دو دسته روش‏ فوق‏الذکر، ترکیب شده است. در روش ارائه شده، مسئله يادگيري مشابهت سند و پرس‏وجو را با استفاده از یک گراف دوبخشيِ بدون جهت متناظر با اطلاعات کلیک‏های کاربران، مدلسازی شده است که متشکل از اسناد و پرس‏وجوها است. در این گراف، ابرداده‏ی²³ گره‏ها، شامل انواع مختلفی از ویژگی‏ها است و وزن یال‏ها نیز نشان دهنده تعداد کلیک‏های کاربران می‏باشد. علاوه بر آن، فرض مي‏شود كه ابرداده غني به ازاي هر يك از گره‏هاي اين گراف، موجود باشد. اين ابرداده، شامل اطلاعات ويژگي‏هاي مختلف به ازاي اسناد يا پرس‏وجوها است. بر اساس این مدل، در این پژوهش، الگوریتم يادگيري رتبه‏بندي جديدي، پیشنهاد شده است که بر مبنای الگوریتم M-PLS عمل می‏کند. روش M-PLS، يك توسعه چند وجهي از فرآیند آماری PLS²⁴ است. بطور خلاصه در الگوریتم PLS، برای مدلسازی رابطه بین دو یا چند مجموعه داده، آنها را به یک فضای نهفته²⁵، نگاشت می‏کنند. بدین ترتیب، بررسی هم‏خطی بودن²⁶ این مجموعه‏های داده، ممکن خواهد شد. برای ارزیابی الگوریتم پیشنهاد شده، عملکرد آن روی مجموعه داده غير عمومي موتور جستجوي Bing متعلق به شركت مايكروسافت بررسی شده است. این ارزیابی‏ها که بر اساس شاخص‏های ارزیابی MAP و NDCG@n صورت گرفته است، حاکی از برتری روش فوق نسبت به الگوریتم‏های پایه رتبه‏بندی نظیر BM25 است. همچنین در این مقاله، بلحاظ نظری، ثابت شده است که الگوريتم ارائه شده، عملكرد بهينه سراسري دارد. به عنوان کارهای تحقیقاتی آتی می‏توان موازي سازي الگوريتم پيشنهادي جهت استفاده از مجموعه‏هاي داده حجيم‏تر و در نتيجه بهبود عملكرد و نتايج را بررسی کرد. در ]9[ نیز الگوریتمی برای حل مسئله رتبه‏بندی رئوس گراف‏های دوبخشی بر اساس یک شاخص معین، ارائه شده است. گراف‏های دو بخشی را می‏توان به عنوان مدل پایه در تحلیل بسیاری از سامانه‏های مهم بازیابی اطلاعات نظیر سامانه‏های بازاریابی برخط، سامانه‏های توصیه‏گر، سامانه‏های پرسش و پاسخ و نظایر آنها در نظر گرفت. بنابراین رتبه‏بندی رئوس در این گراف‏ها حائز اهمیت بالایی می‏باشد. برای این منظور، در روش پیشنهاد شده، از اطلاعات ساختاري گراف دوبخشي به عنوان اطلاعات پایه استفاده شده است و در ادامه به منظور بهبود عملکرد، از تركيب آن با ابرداده مربوط به رئوس گراف، استفاده شده است. بصورت مشخص، فرض می‏شود كه هر راس از يك بخش گراف، به صورت بالقوه با تمامي رئوس از بخش مقابل، اتصال دارد كه ميزان اين ارتباط با يك مقدار عددي تحت عنوان وزن اين يال، مشخص مي‏گردد (در صورت عدم وجود اتصال، وزن مربوطه، صفر در نظر گرفته مي‏شود). سپس، مشابه الگوريتم PageRank، به هر گره، یک درجه اهمیت تخصیص می‏یابد. این وزن، با استفاده از ایده الگوریتم HITS، بصورت تقویتی و طی یک فرآیند بازگشتی، از ترکیب خطی درجه اهمیت و وزن رئوس مرتبط از بخش مقابل، محاسبه می‏گردد. وجه تمایز الگوریتم ارائه شده موسوم به BiRank نسبت به روش‏های کلاسیک رتبه‏بندیِ مبتنی بر پویش تصادفی²⁷، این است که این الگوریتم، طی فرآیند محاسبات مکرّر، یک تابع منظم سازی را بهینه می‏کند که وظیفه هموار سازی گراف با استفاده از اطلاعات بردار پرس‏وجو را به عهده دارد. ارزیابی عملکرد الگوریتم پیشنهادی در دو مسئله متفاوت یعنی پیش‏بینی میزان محبوبیت کالاها در آینده و نیز توصیه کالاهای مورد علاقه به کاربران، بر مبنای شاخص NDCG@n انجام شده است. سطح ارزیابی نخست بر اساس گراف‏های مصنوعی با توزیع درجه یکنواخت و power-law انجام شده است و علاوه بر آن، در مسئله نخست، از سه نوع داده واقعی مختلف یعنی YouTube، Flicker و Last.fm استفاده شده است و به همین ترتیب، در ارزیابی مسئله دوم دادگان Yelp و Amazon، بکار گرفته شده است. نتایج این ارزیابی‏ها حاکی از عملکرد مطلوب روش پیشنهادی در قیاس با الگوریتم PageRank و یکی از توسعه‏های موسوم به TagRW می‏باشد. به منظور توسعه این الگوریتم، سه ایده بكارگيري ويژگي‏هاي بيشتري از اسناد و پرس‏وجوها، توسعه روش پيشنهادي با استفاده از چارچوب بيزين و نیز يادگيري ادغام پارامترها به صورت خودكار، بیان شده است. علاوه بر موارد فوق، در ]10[ روشی برای پیشنهاد مخاطب در شبکه‏های اجتماعی، ارائه شده است که در آن، شبکه اجتماعی به صورت یک گراف جهت‏دار، مدل‏سازی شده است. در این گراف، گره‏ها معادل افراد عضو شبکه اجتماعی مورد نظر هستند و انواع ارتباط بین آنها (نظیر دوستی و تعاملات مختلف)، معادل یال‏های این گراف هستند. به ازای هر گره، سه دسته همسایه، شامل همسایه‏های ورودی (افرادی که پیوندهای به گره مورد بحث دارند)، همسایه‏های خروجی (افرادی که گره مورد نظر، پیوندهایی به آنها دارد) و نیز اجتماع هر دو دسته فوق، می‏توان در نظر گرفت. به این ترتیب به سادگی می‏توان مسئله پیشنهاد مخاطب را به مسئله رتبه‏بندی، نگاشت نمود. بر این اساس، مسئله پیشنهاد مخاطب به یک کاربر مشخص، بصورت اولویت‌بندی همسایگان کاربر مورد نظر بر مبنای میزان مشابهت آنان به وی، قابل مدلسازی خواهد بود. در پیاده‏سازی این الگوریتم، از روش رتبه‏بندی پایه BM25 استفاده شده است. همچنین به منظور ارزیابی روش ارائه شده، از مجموعه دادگان Twitter و Facebook و نیز شاخص‎‏های ارزیابی MAP و NDCG@n استفاده شده است. این بررسی‏ها حاکی از توفیق روش پیشنهادی نسبت به الگوریتم‏های شناخته شده رتبه‏بندی نظیر VSM و PageRank می‏باشد. همچنین در ]11[ بر مبنای بکارگیری یادگیری رتبه‏بندی، روشی برای اولویت‌بندی فرمولهای درج شده در یک مقاله علمی، ارائه شده است. در روش پیشنهادی، دو دسته ویژگی‏های ثانویه به ازای هر فرمول، محاسبه می‏شود که یک دسته، بر اساس تحلیل ارجاعات بین مقالات و دسته دوم بر اساس تحلیل معنایی درون مقاله مورد نظر، بدست می‏آید. ابتدا با استفاده از یک پیکره بزرگ، گراف ارجاعات به فرمول‏ها، تولید و تحلیل می‏شود تا بکمک آن، اهمیت نسبی هر یک از فرمول‏ها تعیین شود. برای این منظور، در گراف ایجاد شده، بر اساس تحلیل توپولوژیک پیوندهای مقالات، ویژگی‏های بین مقاله‏ای فرمول‏ها، استخراج می‏شود. سپس مدل تعبیه کلمات²⁸ به منظور استخراج ویژگی‏های درونی مقاله، مورد استفاده قرار می‏گیرد تا رابطه معنایی بین فرمول مورد نظر و آن مقاله تعیین شود. بر این اساس، جمعاً یازده ویژگی مختلف در قالب سه دسته ویژگی به شرح زیر استخراج می‏شود: سه ویژگی مبتنی بر خصوصیات فرمول، پنج ویژگی درون مقاله‏ای و نیز سه ویژگی بین مقاله‏ای. نهایتاً با اِعمال الگوریتم یادگیری رتبه‏بندی ListNet روی ویژگی‏های استخراج شده، رتبه‏بندی فرمول‏ها، صورت می‏گیرد. برای ارزیابی روش ارائه شده از زیر مجموعه دادگان ویکی‏پدیا در تاریخ 22-7-2016 شامل 332 مقاله استفاده شده است. بررسی صورت گرفته نشان دهنده برتری عملکرد روش پیشنهادی نسبت به روش‏های پایه بر مبنای شاخص‏های P@n و NDCG@n است. از سوی دیگر، مراجعه به جویشگرهای کدهای برنامه‏نویسی، یک روش رایج بین برنامه‏نویسان به منظور یافتن راهکارهای پیاده‏سازی در حل مسائل پیش رو به شمار می‏رود. از این رو، بکارگیری روش‏های یادگیری رتبه‏بندی به منظور اولویت‌بندی پاسخ‏های پیشنهادی، حائز اهمیت است. در پژوهش ]12[، روشی برای رتبه‏بندی نمونه‏های کد پیاده‏سازی شده بر اساس سوال کاربر، عرضه شده است. در این الگوریتم، بر اساس رابطه فراخوانی بین قطعات کد مختلف، ابتدا گرافی موسوم به گراف فراخوانی بین آنها ایجاد می‏شود و سپس میزان PageRank هر قطعه کد در این گراف، محاسبه می‏شود. علاوه بر این ویژگی، یازده ویژگی دیگر که برخی از آنها وابسته به سوال کاربر و برخی مربوط به خصوصیات ذاتی قطعات کد هستند، نیز استخراج می‏شوند. دو نمونه از این ویژگی‏ها عبارتند از: مشابهت متن پرس‏وجوی کاربر و محتوای هر قطعه کد، میزان معروفیت کد که بر اساس میزان مشابهت بین الگوی پیاده‏سازی استفاده شده در آن کد و الگوی غالب در پیاده‏سازی قطعات کد موجود در مخزن مورد بررسی، تعیین می‏شود. این دوازه ویژگی، به الگوریتم رتبه‏بندی RankBoost عرضه می‏شود تا فرآیند یادگیری رتبه‏بندی، انجام گردد. داده محک مورد استفاده برای ارزیابی روش پیشنهادی، بکمک خزش داده‏های موجود در GoogleCode با برچسب Android بدست آمده است و شامل 360000 قطعه کد مربوط به 586 پروژه پیاده‏سازی شده با زبان اندروید می‏باشد. ارزیابی صورت گرفته نشان می‏دهد الگوریتم ارائه شده بر اساس شاخص‏های ارزیابی NDCG و ERR، عملکرد مناسبی داشته است. در ]13[ نیز الگوریتم جدیدی برای یادگیری رتبه‏بندی ارائه شده است که از ویژگی‏های گراف دو بخشی متناظر با کلیک‏های کاربران روی اسناد وب، در فرآیند رتبه‏بندی استفاده می‏کند. در این گراف، وزن متناظر با یک زوج سوال و سند، برابر با تعداد کلیک‏های صورت گرفته بین این زوج است. اسناد و پرس و جوهای کاربران با استفاده از مدل فضای برداری، نمایش داده می‏شوند. در مرحله بعدی که یک فرآیند تکرار شونده است، فرآیند انتشار بردار بین اسناد و پرس وجوهای هم کلیک، انجام می‏شود. بدین معنی که مثلا اگر از سمت پرس و جوها شروع کنیم، به ازای هر سند، جمع وزندار بردارهای متناظر با پرس و جوهای هم کلیک، بردار متناظر با آن سند را بدست می‏دهد. در تکرار بعدی، بردار متناظر یک پرس‏وجو با استفاده از جمع وزندار بردارهای متناظر با اسناد هم کلیک متناظر، محاسبه می‏شود. این توالی تا زمان همگرایی این بردارها تداوم خواهد داشت. در ارزیابی کاربرد این الگوریتم از سوابق تراکنش‏های کاربران جویشگر Yahoo شامل حدود هشت میلیارد پرس‏وجو و نیز حدود سه میلیارد سند استفاده شده است. ارزیابی‏های بعمل آمده بر اساس شاخص NDCG@n حاکی از بهبود رتبه‏بندی با استفاده از روش پیشنهادی است. از سوی دیگر، پژوهشگران در ]14[ الگوریتم یادگیری رتبه‏بندی جدیدی برای سامانه‏های توصیه‏گر ارائه کرده‏اند که بر مبنای رتبه‏بندی محلی و ادغام سراسری عمل می‏کند. استفاده از این روش، امکان آن را فراهم می‏آورد که از چندین فضای ویژگی‏های ریز دانه در قالب یادگیری رتبه‏بندی استفاده شود. در این الگوریتم، ایجاد گراف‏های وزن دار کاربران و کالاها مبنای مراحل بعدی است. در ایجاد گراف کاربران، چنانچه دو کاربر به کالای واحدی ارتباط داشته باشند، بین آنها یال ایجاد می‏شود. وزن متناظر با این یال، بر اساس میزان رای دهی این دو کاربر به کالاهای مشترک، تعیین می‏گردد. همین روند در تولید گراف کالاها نیز استفاده می‏شود. سپس در گام نخست الگوریتم ارائه شده، فرآیند گام زدن تصادفی دو مرحله ای روی گراف کاربران و اقلام کالاها، اعمال می‏شود تا کاربران و کالاهای با حداکثر میزان ارتباط، در قالب گروه‏های محلی محدود، شناسایی شود. در مرحله بعد، با استفاده از الگوریتم رتبه‏بندی بیزین زوج-محور روی این گروه‏های محلی، لیست‏های رتبه‏بندی محلی در هر گروه، حاصل می‏شود. نهایتا یک روش ادغام سراسری روی این لیست‏های مرتب محلی، اجرا می‏شود تا برای هر یک از کاربران، برترین اقلام کالایی، شناسایی شوند. به منظور ارزیابی روش پیشنهادی، از مجموعه دادگان Movielens-100K، Movielens-1M و نیز Yahoo!R3 استفاده شده است. مطابق نتایج حاصل از این آزمایش‏ها، روش پیشنهاد شده توانسته است بنا به شاخص‏های ارزیابی MAP و NDCG، عملکرد بهتری نسبت به روش‏های پایه رتبه‏بندی در حوزه سامانه‏های توصیه‏گر نظیر PersonalRank، CLLORMA و RWLMA داشته باشد. یک رویکرد تحقیقاتی دیگر در این حوزه، موضوع رتبه‏بندی عادلانه نتایج جستجو می‏باشد که با هدف به حداقل رسانیدن نابرابری در عرضه اطلاعات، انجام می‏شود. در پژوهش ]15[، هدف از این مقوله، ارائه نتایج تحقیقات گروه‏های مختلف محققان در جستجوی محتوای علمی است. برای این منظور، در این مقاله روش‏های متفاوتی ارائه شده است. در روش نخست از ویژگی‏های مختلف مقالات نظیر عنوان، نام نویسندگان، محل انتشار، تعداد مراجع و نیز تعداد ارجاعات به آنها، به منظور رتبه‏بندی آنها بر اساس الگوریتم یادگیری رتبه‏بندی پیشنهاد شده در ]16[، استفاده شده است. در ادامه برای یکسان کردن شانس اسناد با میزان مرتبط بودن همسان به منظور رتبه‏بندی همانند، یک عنصر تصادفی با توزیع یکنواخت، به میزان درجه مرتبط بودن مقالات، افزوده می‏شود. هدف روش دوم، تخصیص شانس یکسان جهت عرضه تحقیقات انجام شده توسط گروه‏های مختلف محققین است. برای این منظور، از گراف مشارکت محققین در مقالات منتشر شده، استفاده شده است. سپس گروه‏های محققین بکمک روش ]17[ و بر مبنای فاصله آنها در گراف مذکور، از این گراف شناسایی می‏شوند. بدین ترتیب هر پژوهشگر در گروهی قرار می‏گیرد که یا با دیگر اعضای آن، مقاله مشترکی داشته باشد یا اینکه با آنها بواسطه پژوهشگر مشترک دیگری، مرتبط شده باشد. به ازای یک پرس‏وجوی مشخص، از هر گروه پژوهشگران، مقالات مرتبط با استفاده از ایده روش نخست، شناسایی و رتبه‏بندی می‏شوند. ارزیابی روش‏های پیشنهادی بر اساس شاخص‏های MAP و NDCG@n با استفاده از داده Semantic Scholar (S2) Open Corpus که شامل اطلاعات مربوط به حدود ششصد پرس‏وجوی متفاوت است، نشان می‏دهد که روش ساده‏تر اول، عملکرد بهتری داشته است. ضمن اینکه روش نخست، این مزیت را نیز دارا است که در فرآیند بازیابی و جستجو، نیازی به اطلاعات مازاد مندرج در مقالات در رابطه با محققین ندارد. یک رویکرد دیگر مربوط به فرآیند تست نرم‌افزار است که بخش مهمی از مهندسی نرم‌افزار را در بر می‏گیرد که به منظور رفع نواقص موجود و اصلاح نرم‌افزار، انجام می‏شود. با این حال، در فرآیند تست سامانه‏های نرم‌افزاری بزرگ و پیچیده، غالباً تعداد زیادی ایراد، کشف می‏شود که پس از اصلاح نرم‌افزار، موارد تست متناظر با آنها تدوین می‏شود. در ]18[، دو دسته راه‏حل برای اولویت‌بندی موارد تست و نیز کلاس‏های مورد تست در فرآیند مهندسی نرم‌افزار، ارائه شده است که بر اساس اهداف تست (مثلا میزان تاثیر خطاهای نرم‌افزاری) عمل می‏کند. یک مجموعه از روش‏های پیشنهادی، الگوریتم یادگیری رتبه‏بندی هستند که از مجموعه‏ای از ویژگی‏های متناظر با کد در حال تست و نیز تعدادی از خصوصیات فرآیند تست نرم‌افزار نظیر سوابق هر تست، استفاده می‏کنند. در مقابل، روش‏های پیشنهاد شده در دسته دوم، الگوریتم‏های یادگیری تقویتی هستند که عامل یادگیرنده، طی هر گام از تعامل با محیط پیرامونی، از فرآیند رتبه‏بندی به منظور بهبود عملکرد خود، بهره می‏گیرد. بدین ترتیب این امکان وجود خواهد داشت که با عنایت به تغییرات مداوم نتایج تست در طی فاز تحویل نر‏م‏افزار، فرآیند یکپارچه سازی پیوسته نرم‏افزار، انعطاف و پویایی بیشتری داشته باشد. فرآیند پیشنهادی، شامل دو مرحله انتخاب مجموعه تست‏ها در مرحله فعلی و سپس اولویت‌بندی آنها به منظور بررسی می‏باشد. در گام نخست، بر مبنای تحلیل ایستای وابستگی بین اجزا نرم‌افزار، در سطح کلاس‏ها، به صورت دقیق و کم هزینه می‏توان زیر مجموعه‏ای از کل تست‏ها به منظور بررسی در وهله بعدی تحویل نرم‌افزار، انتخاب نمود. برای این منظور، گراف وابستگی بین کلاس‏ها ایجاد می‏شود. از بررسی این گراف، می‏توانیم کلاس‏های تحت تاثیر ناشی از اصلاحات تست در دیگر کلاس‏های نرم‌افزاری را شناسایی کنیم و مجموعه موارد تست مرحله بعد را تعیین کنیم و سپس بر اساس دو شاخص میزان تاثیر آنها در کشف خطاهای نرم‌افزار و نیز مدت زمان مورد نیاز جهت انجام، موارد تست منتخب را اولویت‏دهی و رتبه‏بندی کنیم. در ارزیابی عملکرد روش‏های پیشنهادی از اطلاعات مربوط به حدود هزار پروژه موجود در GitHub استفاده شده است. این بررسی‏ها بر اساس شاخص پایه FPA²⁹ حاکی از عملکرد مناسب روش‏های پیشنهاد شده نسبت به الگوریتم‏های کلاسیک است. همچنین در ]19[ روشی برای رتبه‏بندی پژوهشگران شاخص در حوزه‏های مختلف علوم ارائه شده است که بر مبنای شاخص‏های مستخرج از گراف نویسندگان مشترک مقالات علمی، اقدام به شناسایی محققان برتر می‏کند. روش سنتی انجام اینکار بر مبنای محاسبه شاخص‏های علم سنجی نظیر تعداد مقالات منتشر شده، میزان ارجاعات به این مقالات و نیز h-index عمل می‏کنند که از میان آنها میزان ارجاعات به مقالات محقق مورد نظر، نقش پر رنگ تری دارد. عموما مدتی پس از چاپ یک مقاله، ارجاع دیگر محققان به آن شروع می‏شود و میزان ارجاعات به یک مقاله طی یک بازه زمانی چندین ساله، مبنای دقیقی برای ارزیابی اهمیت آن مقاله محسوب می‏شود. از این رو، استفاده از این قبیل شاخص‏ها برای رتبه‏بندی محققان جوان، چندان دقیق نخواهد بود. به منظور حل این مسئله، در این پژوهش، روشی برای اولویت‌بندی پژوهشگران بر مبنای شاخص‏های میزان مرکزیت گره‏ها در گراف نویسندگان مشترک، ارائه شده است. در ارزیابی روش پیشنهادی از اطلاعات مربوط به 671 کاندیدای مربوط به 24 جایزه بین‌المللی معتبر در حوزه ریاضیات استفاده شده است. آزمایش‏های صورت گرفته نشان داده است که مطابق معیار P@n، رتبه‏بندی بر مبنای شاخص‏های شبکه گراف نویسندگان مشترک، در مقایسه با شاخص‏های علم سنجی، در شناسایی محققین برتر، تقریبا عملکرد مشابهی داشته است. با این حال، با استفاده از روش پیشنهادی، می‏توان محققان جوان و شاخص در هر حوزه را شناسایی نمود.

4-2- استخراج ویژگی‏های آماری دادگان و ارائه بازنمایی گرافی این ویژگی‏ها

به عنوان نمونه تحقیقات دسته دوم، می‏توان به ]20[ اشاره نمود که در آن، یک مدل رتبه‏بندی بر اساس الگوریتم تعمیم یافته PageRank معرفی شده است. در این روش، با استفاده از تحلیل بیزین نتایج بازی‏های انجام شده، گرافی از تیم‏ها و ارتباطات بین آنها ساخته شده است. پارامترهای این مدل با هدف حداقل کردن فاصله تابع زیان بین رتبه‏بندی واقعی تیم‏ها و پیش بینی مدل، تخمین زده می‏شوند. برای ارزیابی روش پیشنهادی از داده‏های ده سال مسابقات بسکتبال که از سایت NBA استخراج شده، استفاده شده است. مزیت استفاده از این مدل در مقایسه با PageRank این است که می‏توان دانش اولیه را در مدل گنجاند و بدین ترتیب می‏توان مدل را با سایر مدل‏های رتبه‏بندی ترکیب کرد. همچنین مقادیر پارامترها در مدل را می‏توان بر اساس بازی‏های جدید اصلاح و بروزرسانی کرد. علاوه بر آن، تابع مربوط به ارتباطات گره‏ها یک بردار چند بعدی است که اطلاعات بیشتری نسبت به امتیاز بازی‏ها یا برنده شدن تیمها دارد. در آزمایش‏های به عمل آمده، عملکرد الگوریتم پیشنهادی نسبت به الگوریتم‏های پایه رتبه‏بندی، از لحاظ همبستگی رتبه‏بندی نتایج کندال، دقت پیش بینی نتایج در هر فصل و نیز دقت نتایج بازی‏های Playoff بررسی شده است. این بررسی‏ها نشان می‏دهد که مدل ارائه شده در بیشتر فصول، عملکرد بهتری نسبت به سایر مدل‏های رتبه‏بندی داشته است. روش پیشنهادی، تاثیر حاشیه‏ای هر یک از بازی‏های انجام شده توسط یک تیم را در فرآیند ارزیابی قدرت آن تیم در نظر می‏گیرد. با این حال، در این فرآیند، عامل زمان در نظر گرفته نشده است، یعنی اثر یک بازی ممکن است در طول زمان تضعیف شود. به منظور توسعه روش پیشنهادی، می‏توان به نتیجه هر بازی، وزنی متناسب با فاصله زمانی آن نسبت به زمان حال را اختصاص داد. علاوه بر این، بررسی گونه‏های دیگر توابع پیوند و نیز توابع زیان، می‏تواند جالب توجه باشد. ضمنا عملکرد روش پیشنهادی، به منظور رتبه‏بندی تیم‏ها یا ورزشکاران دیگر رشته‏های ورزشی نیز می‏تواند مورد بررسی قرار گیرد. همچنین در ]21[، دسته‏ای از الگوریتم‏های یادگیری رتبه‏بندی روی گراف‏ها ارائه شده است که در آنها، هدف کلی، رتبه‏بندي اشيايي است كه به هم مرتبط هستند. الگوریتم‏های استفاده شده بر مبنای ایده graph regularization طراحی شده‏اند که قبلا در زمینه حل مسائل یادگیری گراف‏ها ارائه شده بود. در این تحقیق، مسئله رتبه‏بندي به صورت گرافی وزن‏دار بازنمايي شده است که وزن بین دو راس، نشان دهنده ترتیب نسبی بین آن دو است. بر این اساس، به ازای یادگیری رتبه‏بندی صحیح رئوس این گراف، تابع جریمه‏ای تعریف می‏شود که به ازای یک روش رتبه‏بندی خاص، بر اساس وزن یال‏های گراف فوق، محاسبه می‏شود. بصورت خلاصه، در روش پیشنهاد شده، از طریق بازتولید فضای هسته هیلبرت، تابع رتبه‏بندی مستخرج از گراف، فرا گرفته می‏شود. این امر باعث می‏شود، الگوریتم‏های بدست آمده، حائز ویژگی‏های جالب توجهی نظیر پایداری و تعمیم‏پذیری باشند. پیاده‏سازی این ایده به دو روش یعنی با استفاده از رگرسیون SVM و نیز توسعه الگوریتم پایه RankSVM با تابع جریمه‏ فوق‏الذکر، انجام شده است. به منظور ارزیابی عملکرد روش‏های پیشنهادی، کارآیی آنها در دو مسئله‏ پايه، مورد بررسي و ارزیابی قرار گرفته است که عبارتند از: تشخيص ميزان كيناس در شبكه تعامل پروتئين‏ها و نیز تعيين ميزان مشاركت ساختارهاي شيميايي پايه در توليد داروهاي مورد نظر. نتايج حاصل از آزمایش‏های صورت گرفته، حاكي از برتري شکل دوم پیاده‏سازی روش پيشنهادي نسبت به گونه نخست پیاده‏سازی این الگوریتم بر اساس شاخص‏های P@n، MAP و NDCG@n است. به عنوان توسعه‏های آتی، دو مسیر پیشنهاد شده است که یکی از آنها، استفاده از توابع جریمه دیگر بجای Hinge Loss Function است که در این مقاله استفاده شده است. همچنین، تلاش برای بهبود عملکرد روی شاخص‏های دیگر بازیابی نظیر MAP و MeanNDCG، مسیر توسعه پیشنهاد شده بعدی است.

در جدول 1 خلاصه پژوهش‏های بررسی شده در دسته الف (بازیابی اطلاعات بر مبنای ارائه بازنمایی گرافی از دادگان بازیابی اطلاعات) آمده است.

از سوی دیگر، فراوانی تعداد مقالات مرتبط بررسی شده در دسته نخست در شکل 2 آمده است. بر اساس این نمودار، اگر چه از سال‏های گذشته، پژوهش‏هایی در این زمینه انجام شده است، اما عمده این تحقیقات مربوط به سالهای اخیر است.

شکل 2. فراوانی تعداد مقالات مرتبط بررسی شده در دسته نخست (بازیابی اطلاعات با استفاده از بازنمایی گرافی دادگان)

5- بازیابی معنایی اطلاعات با استفاده از نظریه گراف

وجه مشترک الگوریتم‏های ذیل این بخش، در پرداختن آنها به مقوله بازیابی معنایی اطلاعات با بهره‏گیری از نظریه گراف می‏باشد که بنا به اهمیت و گستره کاربرد وسیع روش‏های بازیابی معنایی اطلاعات، به صورت مستقل در این بخش، مورد مطالعه قرار گرفته‏اند. البته این دسته از روش‏ها، بر اساس نحوه بکارگیری نظریه گراف در فرآیند بازیابی معنایی اطلاعات، خود به چهار زیر دسته کلی، تفکیک شده‏اند:زیر دسته اول، پژوهش‏هایی را در بر می‏گیرد که از تکنیک گراف دانش در فرآیند بازیابی معنایی اطلاعات، استفاده می‏کنند. در مقابل، زیر دسته دوم از این پژوهش‏ها، با ایجاد گراف روابط معنایی بین عناصر داده‏ای مرتبط با مسئله بازیابی اطلاعات، به انجام بازیابی معنایی اطلاعات می‏پردازند. از سوی دیگر، در زیر دسته سوم پژوهش‏های بررسی شده، از مدل‏های مبتنی بر هایپر گراف در بازیابی معنایی استفاده شده است؛ و نهایتا زیر دسته چهارم، شامل پژوهش‏هایی می‌باشد که با بکارگیری مدل پویش تصادفی، عملیات بازیابی معنایی اطلاعات را انجام می‏دهند.

[1] Mean Reciprocal Rank

[2] Precision

[3] Mean Average Precision

[4] Average Precision

[5] Normalized Discounted Cumulative Gain

[6] Discounted Cumulative Gain

[7] Expected Reciprocal Rank

[8] Annotation

[9] Metadata

[10] Interaction Graph

[11] Static Features

[12] Topologic Features

[13] Hypergraph

[14] Spectral Features

[15] Hypergraph

[16] Hyperedge

[17] Spectral Feature Matrix

[18] Pairwise Learning to Rank

[19] Probabilistic Matrix Factorization

[20] Bayesian Personalized Ranking

[21] Group Preference-based Bayesian Personalized Ranking

[22] Visual Bayesian Personalized Ranking

[23] Metadata

[24] Partial Least Squares

[25] Latent Space

[26] Collinearity

[27] Random Walk

[28] Word Embedding

[29] Fault Percentile Average

جدول 1. خلاصه مقالات ارزیابی شده در دسته الف (بازیابی اطلاعات بر مبنای ارائه بازنمایی گرافی از دادگان بازیابی اطلاعات)

نقاط ضعف	نقاط قوت	ایده اصلی	سال چاپ	دسته‌بندی روش	مقاله
وجود پارامترهای متعدد جهت پیکربندی الگوریتم	شناسایی پژوهشگران با دقت مطلوب	یافتن پژوهشگران بر اساس ادغام اطلاعات پروفایل و گراف ارجاعات به کمک عملگرهای ترکیب اطلاعات	2015	الف-1	[4]
هزینه محاسباتی بالا	دقت مطلوب به ازای محصولات با تعداد فروش محدود	بهبود توصیه‏گرها با ایجاد گراف دوبخشی بین خریداران و کالاها و استخراج ویژگی‏های گرافی و ادغام آنها با مشخصات کالاها توسط یادگیری ژرف	2019	الف-1	[5]
هزینه محاسباتی بالا و عملکرد ضعیف در شرایط محدود بودن داده	توجه به سوابق تعامل کاربران با داده‏ها و نیز استفاده از ابرداده‏ متناظر با این محتوا	مدل‏سازی تعامل کاربر با محتوا توسط نظریه گراف جهت حاشیه‏نگاری خودکار در شبکه‏های اجتماعی برخط	2014	الف-1	[6]
نیاز به وجود بازخورد صریح کاربران در قبال کالاها	امکان استفاده در شرایط فقدان ويژگي‏هاي بصري و متني برای همه کالاها یا کاربران	ارائه مفهوم ویژگی‏های طیفی از هایپرگراف روابط بین کاربران و کالاها در سامانه توصیه‏گر	2019	الف-1	[7]
عدم مقیاس‏پذیری محاسبات در قبال کلان داده‏ها	استفاده از اطلاعات سوابق کاربران در ارتقای فرآیند بازیابی اطلاعات	مدل‏سازی رفتار کاربران با استفاده از گراف دوبخشی تعاملات کاربران با داده‏ها	2013	الف-1	[8]
هزینه محاسباتی بالا و عدم استفاده از شاخص‏های استاندارد ارزیابی بازیابی اطلاعات	قابلیت کاربرد در سامانه‏های مختلف بازیابی اطلاعات	رتبه‏بندی رئوس گراف‏های دوبخشی با ترکیب مشخصات ساختاري گراف و ابرداده رئوس	2017	الف-1	[9]
عدم توجه به تنوع گرایش‏ها و خصوصیات افراد پیشنهادی	امکان پیاده‏سازی توسط روش‏های کم هزینه رتبه‏بندی نظیر BM25	نگاشت مسئله پیشنهاد مخاطب در شبکه‏های اجتماعی به مسئله رتبه‏بندی	2020	الف-1	[10]
پیچیدگی زمانی زیاد	دقت قابل قبول به دلیل ترکیب ویژگی‏های متنی و گراف	رتبه‏بندی فرمول‏های مقالات علمی بر اساس ترکیب ویژگی‏های متنی و گراف ارجاعات درون و برون مقاله‏ای	2018	الف-1	[11]
ارزیابی محدود روش پیشنهادی	عملکرد مطلوب در رتبه‏بندی	رتبه‏بندی قطعات کد بر اساس ادغام مشخصات پرس‏وجوها و ویژگی‏های قطعات کد	2017	الف-1	[12]
هزینه محاسباتی بالا	عملکرد مطلوب در شرایط نویز و محدود بودن تعاملات کاربران	توسعه مدل فضای برداری با ایجاد گراف دوبخشی بین اسناد وب و کلیک‏های کاربران	2016	الف-1	[13]
محدودیت عملکرد به وجود اطلاعات امتیازدهی کالاها توسط کاربران	امکان موازی‏سازی پردازش داده‏ها به منظور کاهش هزینه محاسبه	ایجاد گراف‏های کاربران و کالاها و رتبه‏بندی محلی گره‏ها در زیرگروه‏ها و سپس ادغام رتبه‏بندی‏های محلی	2020	الف-1	[14]
هزینه محاسباتی بالا	کارآمدی مناسب در رتبه‏بندی	رتبه‏بندی عادلانه نتایج جستجوهای علمی با ترکیب ویژگی‏های گراف مشارکت محققین و نیز ویژگی‏های متناظر با متن مقالات	2020	الف-1	[15]
عدم امکان استفاده در نرم‏افزارهای با مقیاس کم یا متوسط	قابلیت بکارگیری در مدیریت فرآیند مهندسی نرم‌افزار در پروژه‏های کلان نرم‌افزاری	رتبه‏بندی موارد تست نرم‏افزار بر اساس گراف وابستگی بین اجزای نرم‏افزاری و سوابق تست	2020	الف-1	[18]
عدم استفاده از همه اطلاعات گراف نویسندگان	کارآمدی مناسب به خصوص شناسایی محققان جوان‏تر	رتبه‏بندی محققان شاخص توسط گراف نویسندگان مشترک	2020	الف-1	[19]
عدم توجه به عامل زمان در مدل گراف بازی‏ها	قابلیت بکارگیری دانش اولیه و نیز امکان یادگیری رتبه‏بندی پویا	رتبه‏بندی تیم‏های ورزشی بر اساس سابقه بازی‏های انجام شده با استفاده از گراف بازی‏ها	2020	الف-2	[20]
هزینه محاسباتی بالا و عملکرد نه چندان مطلوب	قابیلت بکارگیری در مسائل مختلف بازیابی اطلاعات	توسعه روش‏های یادگیری رتبه‏بندی با مدل‏سازی مسئله رتبه‏بندی بر اساس نظریه گراف	2010	الف-2	[21]

5-1- بازیابی اطلاعات با استفاده از گراف دانش

از جمله پژوهش‏های گروه نخست، می‏توان به ]22 و 23[ اشاره نمود که در آنها ضمن مرور قابلیت‏های داده ساختار گراف‏های دانش به بیان طیف وسیعی از کاربردهای آنها در سامانه‏های پرسش و پاسخ، سامانه‏های توصیه‏گر و نیز سامانه‏های بازیابی اطلاعات می‌پردازد. در ]24[ نشان داده شده است که جستجوی معنایی بر پایه هستان شناسی ¹ می‏تواند بر اساس شاخص P@n، منجر به بهبود روش کلاسیک جستجوی مبتنی بر کلید واژه‏های کاربران شود. برای این منظور، آنها معماری نوینی بر سامانه‏های پرسش و پاسخ ارائه کردند که با ایجاد نمایه مفهوم-محور و ادغام آن با نمایه مبتنی بر اسناد، اقدام به بازیابی معنایی اسناد نماید. بصورت مشخص، در این تحقیق از سامانه PowerAqua ]25[ برای نگاشت کلید واژه‏های موجود در پرس‏وجوهای مطرح شده به زبان طبیعی به عناصر هستان شناسی استفاده شده است. در ]26[ روشی برای نمایش یکپارچه پایگاه‏های داده ترکیبی ارائه شده است که قادر به ادغام داده‏های ساخت یافته و نیز داده‏های بدون ساختار است. این کار از طریق سه‏تایی RDF² شامل فاعل، مسند و مفعول و ایجاد نمایش گرافی متناظر با آن، صورت گرفته است. بدین ترتیب، انواع داده‏ها شامل داده‏های ساخت یافته موجود در پایگاه‏های داده رابطه ای، داده‏های غیر ساخت یافته مربوط به موجودیت‏ها و نیز روابط استخراج شده از متون غیر ساخت یافته، قابل یکپارچه سازی خواهند بود. ارزیابی‏های صورت گرفته حاکی از بهبود عملکرد این روش نسبت به روش‏های پایه مطابق شاخص‏های دقت³ و صحت⁴ است. در ]27[ سامانه‏ای تحت عنوان SaHaRa برای جستجوی موجودیت-محور⁵ ارائه شده است که قادر به جستجوی اطلاعات مورد نیاز کاربر در مخزن اخبار است. بازیابی اطلاعات با استفاده از مدل‏های زبانی صورت می‏گیرد و امکان بازیابی متون و موجودیت‏ها وجود دارد. در این سامانه دو نگاه سند-محور و موجودیت-محور به صورت توامان استفاده شده است. بر مبنای این دو دیدگاه، در SaHaRa علاوه بر متن اخبار، پیوندهای اخبار مرتبط با آنها و نیز موجودیت‏های متناظر نیز نمایش داده می‏شود. در ]28[ چندین نوع از روابط بین موجودیت‏ها مورد بررسی قرار گرفته است تا بهترین حضور توامان آنها به منظور تولید متون داستانی، شناسایی و مورد استفاده قرار گیرد. در انجام این تحقیق، از مخزن بزرگی از دادگان TREC در رابطه با بازیابی سوالات پیچیده کاربران، استفاده شده است و کارآمدی 12 ویژگی مختلف مربوط به موجودیت‏ها و حضور توامان آنها و نیز ترکیب آنها بکمک روش‏های یادگیری رتبه‏بندی، بر اساس شاخص‏های دقت و MAP، مورد ارزیابی قرار گرفته است. همچنین در ]29[ روشی تحت عنوان MIRRE⁶ برای بازیابی داده‏های چند رسانه‏ای ارائه شده که قادر است بصورت غیرخطی و چند وجهی، اسنادِ شامل داده‏های چند رسانه‏ای یکپارچه‏سازی شده را جستجو نماید. در روش پیشنهاد شده، وجوه مختلف داده‏های چند رسانه‏ای و نیز عناصر رسانه‏ای موجود در آنها (اعم از متن، صوت، تصویر، ویدیو و نظایر آن) را در فرآیند جستجو مورد استفاده قرار دهد. برای نیل به این منظور، از مدل داده‏ای گراف استفاده شده است که در آن، گره‏ها، اسناد چند رسانه‏ای هستند و یال‏ها، معادل شباهت چند وجهی و روابط معنایی بین گره‏ها می‏باشند. این شباهت‏سنجی بر مبنای مجموع مشابهت مابین عناصر داده‏ای موجود در اسناد، محاسبه می‏گردد. علاوه بر آن، در این پژوهش، واسط کاربری جدیدی نیز برای جستجوی اطلاعات چند رسانه‏ای، طراحی و پیاده‏سازی شده است. در این سامانه، داده‏های چند رسانه‏ای بصورت نمایه معکوس⁷، نمایه‏گذاری می‏شوند و پرس‏وجوهای کاربران نیز به صورت معمول، شامل تعدادی کلید واژه متنی هستند. با انجام شباهت سنجی بین پرس‏وجوهای کاربران و اجزاء چند وجهی هر داده چند رسانه‏ای، میزان ارتباط هر یک از این اجزا با پرس‏وجوی کاربر مشخص می‏شود و سپس بر اساس مدل گرافی تهیه شده، عناصر مشابه به سوال کاربر در گراف متناظر، تعیین و بازیابی می‏شوند. برای سنجش عملکرد الگوریتم ارائه شده، از دادگان I-Search استفاده شده است. این دادگان شامل بیش از ده هزار داده چند رسانه‏ای است که توصیف آنها در قالب اسناد XML نیز موجود است. ارزیابی‏های صورت گرفته بر اساس شاخص‏های تشخیص میزان کاربر پسندی سامانه، نشان می‏دهد که میزان کاربردی بودن و رضایتمندی کاربران در نتیجه استفاده از واسط کاربری تهیه شده برای ارائه نتایج عملکرد روش پیشنهادی، مطلوب بوده است. محققان این پژوهش، در نظر دارند روش‏های خوشه‏یابی و داده‏کاوی را به منظور بهبود عملکرد روش ارائه شده، در فرآیند محاسبات، دخیل کنند و در عین حال، ارتقای عملکرد واسط کاربری تهیه شده نیز مد نظر آنان است. در ]30[ الگوریتم رتبه‏بندی جدیدی برای سامانه‏های پرسش و پاسخ‏⁸ ارائه شده است که بر اساس خوشه‏بندی گراف‏های دانش با مقیاس بزرگ و اولویت‏بندی زیرگراف‏های ایجاد شده، عمل می‏کند به نحوی که زیرگراف‏های با اولویت بالاتر به منظور تهیه پاسخ به ازای سوالات کاربران، مورد استفاده قرار می‏گیرند. بدین ترتیب، ضمن کاهش هزینه محاسباتی کار با گراف‏های بسیار بزرگ، صرفا بخش‏هایی از گراف دانش در فرآیند پاسخ‏دهی، استفاده می‏شوند که حاوی اطلاعات با میزان حداکثر مرتبط بودن به سوالات کاربران ‏باشند. در عین حال، بر اساس شاخص‏های ارزیابی دقت، صحت و F1، نسبت به الگوریتم‏های پایه نیز بهبود، حاصل شده است. از سوی دیگر، در ]31[ روشی برای پیوند دهی ضمنی موجودیت‏های اطلاعاتی موجود در گراف‏های دانش ارائه شده است که در آن، موجودیت‏های اطلاعاتی بر مبنای توییت‏های کاربران، اولویت‏بندی و مرتبط می‏شوند. بر اساس نتایج ارزیابی این روش طبق شاخص‎های MRR و P@n، روش پیشنهادی، عملکرد مناسب داشته است. همچنین در ]32[ روشی برای برای پیشنهاد دروس به دانشجویان بر اساس رتبه‏بندی دروس بر اساس سوابق تحصیلی آنها ارائه شده است که از گراف دانش برای اولویت‏بندی دروس، استفاده می‏کند. در ]33[ کاربرد روش‏های مبتنی بر شبکه‏های عصبی برای رتبه‏بندی گراف پرس‏وجوی کاربر به منظور حل مسئله پاسخ‏دهی به پرسش‏های پیچیده با استفاده از گراف دانش، مورد بررسی قرار گرفته است. علاوه بر آن، با توجه به ساختار گراف‏های متناظر با پرسش‏های کاربران، الگوریتم جدیدی برای اولویت‏بندی گراف‏های پرسش‏های کاربران بر مبنای گراف دانش در اختیار، ارائه شده است. به منظور سنجش عملکرد این روش نسبت به الگوریتم‏های پایه، از شاخص‏های ارزیابی استانداردی نظیر دقت، صحت، MRR و F1 استفاده شده است. علاوه بر این، در ]34[ روشی برای انتساب خطاهای گزارش شده سامانه‏های نرم‏افزاری به مولفه‏های تشکیل دهنده آنها، ارائه شده است که قادر است بر اساس اطلاعات موجود در سوابق انتساب‏های درست یا نادرست قبلی، عملکرد مطلوبی داشته باشد. برای این منظور، بر اساس وظایف مولفه‏های مختلف سامانه نرم‏افزاری مورد نظر و نیز روابط منطقی بین آنها، یک گراف دانش، ایجاد می‏شود و طی فرآیند یادگیری، انتساب صحیح خطاها به مولفه‏های نرم‌افزاری متناظر، صورت می‏گیرد. در مقایسه عملکرد این روش نسبت به دیگر روش‏های مشابه، شاخص‏های P@n و NDCG@n، بهره گرفته شده است. همچنین در ]35[ روشی برای بازیابی موجودیت‏های اطلاعاتی متناظر با نیازهای کاربران از گراف‏های دانش بسیار بزرگ، ارائه شده است که در آن، ابتدا زیرگراف‏های مرتبط با پرس‏وجوهای کاربران، شناسایی و هرس می‏شوند و سپس با استفاده از شبکه‏های عصبی عمیق، اقدام به اولویت‏بندی موجودیت‏های مرتبط در این زیرگراف‏ها می‏کند. همچنین در ارزیابی عملکرد الگوریتم ارائه شده نسبت به دیگر روش‏های شاخص از معیارهای ارزیابی دقت و MAP استفاده شده است.

5-2- ایجاد گراف موجودیت بر اساس دادگان مسئله بازیابی اطلاعات

دسته بعدی از پژوهش‏ها مربوط به ایجاد گراف روابط معنایی بر اساس دادگان مسئله بازیابی اطلاعات می‌باشد. از جمله این تحقیقات می‏توان به ]1[ اشاره نمود که در آن مروری بر الگوریتم‏های ارائه شده در حوزه جستجوی موجودیت-محور ارائه شده است. بر اساس این مطالعه، فاصله معناداری بین روش‏های بازیابی متن‏-محور و بازیابی دانش-محور وجود دارد. الگوریتم‏های بازیابی متن‏-محور، قابلیت لحاظ نمودن روابط معنایی پیچیده را ندارند، در حالیکه روش‏های بازیابی دانش-محور، فاقد امکان پردازش پرس‏وجوهای مبتنی بر کلید واژه‏های کاربران و نیز بازیابی بر اساس رتبه‏بندی نتایج، می‏باشند. از سوی دیگر در ]36[ روشی برای بازنمایی اسناد بکمک گراف مفهوم⁹ ارائه شده است تا از این طریق بتوان شباهت معنایی اسناد را تعیین نمود. در این تحقیق از ابزار TAGME¹⁰ به منظور اتصال اسناد به مفاهیم Wikipedia استفاده شده است. سپس گرافی از مفاهیم به عنوان رئوس و روابط بین آنها به عنوان یال‏ها تشکیل می‏شود. در این گراف، وزن یال‏ها متناظر با نوع رابطه متناظر با مفاهیم دو سوی آن یال، تعیین می‏شود. این روابط می‏توانند از سه گونه زمینه، رده و ساختار باشند. ضمنا وزن متناظر با رئوس هم معادل میزان مرکزیت نزدیکی¹¹ آنها در نظر گرفته شده است. بر اساس این وزن دهی، میزان شباهت مفاهیم بصورت تابعی از شباهت رئوس متناظر در گراف مفهوم و نیز وزن یال‏های متصل کننده آنها تعیین می‏شود. مقایسه این روش با الگوریتم‏های مشابه، مطابق شاخص همبستگی پیرسن¹²، صورت گرفته است. از سوی دیگر در ]37[ با استفاده از فاکتورسازی تنسور¹³، معناشناسی نهفته در روابط موجودیت‏ها استخراج شده است. در این الگوریتم، به منظور تشریح روابط بین موجودیت‏ها بر اساس مسندهای مختلف، یک تنسور تعریف شده است که بصورت چندین ماتریس مجاورت می‏باشد و هر ماتریس به ازای هر مسند روی بعد سوم تنسور، در نظر گرفته شده است. همچنین برای رتبه‏بندی نتایج، از روش یادگیری رتبه‏بندی جفتی استفاده شده که عملکرد آن با استفاده از درخت‏های رگرسیون ارتقا یافته، به ازای شاخص NDCG بهینه شده است. در این کار از ویژگی‏های واژه-محور و نیز ویژگی‏های ساختاری، استفاده شده است. ضمنا بایستی اشاره نمود که ارزیابی عملکرد این روش، بر اساس معیارهای P@n، MAP و NDCG@n انجام شده است. همچنین در ]38[ روشی برای حل مسئله پیوند زمینه‏ای¹⁴ ارائه شده است. در این مسئله کوشش می‏شود هر خبر ارائه شده، جامع باشد به نحوی که شامل پیشینه موضوع آن خبر و نیز اطلاعات زمینه‏ای مرتبط باشد تا بتواند درک صحیحی را در ذهن مخاطب ایجاد نماید. روش پیشنهاد شده که بر مبنای الگوریتم رتبه‏بندی LambdaMART می‏باشد، برای رتبه‏بندی هر خبر، ترکیبی از ویژگی‏های استاندارد متناظر با متن آن خبر و نیز ویژگی‏های مربوط به گراف موجودیت‏ها را ایجاد می‏کند. ابتدا به ازای هر خبر، موجودیت‏های بالقوه، شناسایی و استخراج می‏شوند و سپس گراف روابط بین موجودیت‏ها، بر مبنای ارتباطات مابین آنها تشکیل می‏شود. برای اینکار از مخزن دانش ویکی‏پدیا، به عنوان گراف کلی روابط معنایی بین موجودیت‏ها، استفاده می‏شود. در این گراف، که غیر جهت‏دار و وزن‏دار می‏باشد، رئوس، همان موجودیت‏ها هستند و وزن یال‏ها، معادل میزان ارتباط معنایی بین موجودیت‏های متناظر است. در ادامه، گراف بدست آمده هرس می‏شود بنحوی که تنها شامل بزرگترین مولفه همبند باشد. سپس با بکارگیری الگوریتم تشخیص انجمن Girvan-Neman، از مولفه همبند فوق، بزرگترین انجمن موجود، شناسایی و استخراج می‏شود. در مرحله بعدی، استخراج ویژگی‏های متناظر با اسناد صورت ‏می‏گیرد. این ویژگی‏ها که خود یا مرتبط با اسناد یا پرس‏وجوهای کاربران هستند، می‏توانند از متن اسناد و نیز گراف معنایی روابط مابین موجودیت‏ها استخراج شوند. در گام بعدی، با استفاده از الگوریتم یادگیری رتبه‏بندی LambdaMART، مدل‏های رتبه‏بندی مختلفی تولید می‏شود که در هر یک از آنها، از زیرمجموعه محدودی از کل ویژگی‏های تولید شده طی مراحل قبلی، استفاده شده است. نهایتاً در مرحله ترکیب، تعداد مشخصی از مدل‏های مرحله قبلی با الگوریتم ساده CombSUM، با هم ادغام می‏شوند تا خروجی نهایی، بدست آید. الگوریتم ارائه شده در حالات مختلف ترکیب با تعداد اجراهای متفاوت با الگوریتم پایه BM25 با شاخص‏های NDCG، P@n و Reciprocal Rank مقایسه می‏شود. برای ارزیابی روش پیشنهادی، از Washington Post Corpus vs2 و New York Times Annotated Corpus، استفاده شده است. با این کار مجموعه آموزشی غنی‏تر شده است اما این کار به دلیل عدم هماهنگی بین درجات مرتبط بودن در این دو مجموعه داده، باعث محدودیت‌های ناشی از یادگیری انتقالی¹⁵ شده است. نتایج نشان می‏دهد که تعداد اجراهای بیشتر ترکیب منجر به بهبود نتیجه رتبه‏بندی نمی‏شود. با این حال، مطابق نتایج ارزیابی طبق شاخص‏های P@n و NDCG@n، ایده ترکیب نتایج، منجر به بهبود عملکرد می‏شود. به علاوه هر چه اسناد بیشتری برای رتبه‏بندی بکار گرفته شوند، عملکرد الگوریتم پیشنهادی نسبت به الگوریتم BM25 پایین می‏آید. دلایل ضعیف بودن روش پیشنهادی آن است که اولا روش یادگیری انتقالی به کارگرفته شده است، که از رسیدن بعضی موضوعات به بالاترین درجه اثربخشی جلوگیری می‏کند. دوم اینکه ممکن است از اسناد، گراف‏های موجودیت خوش فرمی ایجاد نشود و این امر باعث می‏شود الگوریتم یادگیرنده صرفا از ویژگی‏های متن برای امتیازدهی استفاده کند.

5-3- مدل‏های مبتنی بر هایپر گراف

از جمله روش‏های دسته سوم که مبتنی بر بکارگیری هایپر گراف‏ها می‏باشند، می‏توان به ]39[ اشاره نمود که در آن هایپر گراف پرس‏وجوهای کاربران، پیشنهاد و طراحی شده است. در این هایپر گراف، گره‏ها متناظر با مفاهیم متناظر با پرس وجو هستند و یال‏ها، وابستگی‏های بین زیر مجموعه‏هایی از این گره‏ها و اسناد را نمایش می‏دهند. بر این اساس، هایپر گراف پرس وجوها قادر به مدلسازی سطوح بالاتر وابستگی بین واژه‏ها می‏باشد. به منظور تخصیص امتیاز به زوج‏های اسناد و پرس وجوها، از نمایش گراف فاکتور به ازای هایپر گراف پرس وجوها استفاده شده است. برای مقایسه عملکرد این روش با الگوریتم‏های پایه از شاخص‏های MAP و ERR@n، استفاده شده است. از سوی دیگر در ]40[ مفهومی تحت عنوان هایپرگراف معنایی¹⁶ معرفی شده است که راهکاری برای بازنمایی دانش استخراج شده از مخازن داده بر اساس هایپرگراف‏های مرتب معکوس می‏باشد. در این ساختار، گره‏ها که معادل واژه‏ها هستند، می‏توانند دارای ترتیب نسبی در هایپر یال متناظر باشند و موجودیت‏ها را به صورت توالی از کلمات، توصیف نمایند. همچنین، با توجه به ویژگی بازگشتی بودن بودن این هایپرگراف، می‏توان هر هایپر یال را بر اساس دیگر هایپریال‏ها بیان نمود. محصول این پژوهش، ارائه یک کتابخانه نرم‌افزاری در زبان پایتون موسوم به ¹⁷GraphBrain است که امکان پردازش هایپر گراف‏های معنایی را در کاربردهای مرتبط با پردازش زبان طبیعی و جستجو و استنتاج دانش، فراهم می‏سازد. همچنین در ]41[ الگوریتمی تحت عنوان ENT Rank، یک روش رتبه‏بندی موجودیت‏ها بر اساس بکارگیری هایپر گراف‏ها ارائه شده است، که در آن از اطلاعات متنی به منظور بهبود بازیابی موجودیت‏ها استفاده شده است. در این الگوریتم، هایپر گراف مورد استفاده به گراف چندگانه متناظر با حضور توامان موجودیت‏ها، تبدیل می‌شود و در آن از ویژگی‏های متعددی نظیر ویژگی‏های همسایگان و نیز ویژگی‏های مرتبط بودن زمینه، به منظور ایجاد مدل یادگیری رتبه‏بندی، استفاده می‌شود. در واقع مدل پیشنهادی، گونه‏ای از الگوریتم پویش تصادفی با راه‏اندازی مجدد تصادفی، محسوب می‌شود. در ارزیابی عملکرد این روش، از شاخص‏های MAP و NDCG@n استفاده شده است.

5-4- مدل‏های مبتنی بر گراف پویش تصادفی

دسته چهارم از کاربردهای نظریه گراف در بازیابی معنایی اطلاعات مربوط به مدل‏های بازیابی معنایی مبتنی بر پویش تصادفی می‏باشد. در این دسته می‏توان از الگوریتم‏های نظیر ObjectRank و HopRank نام برد که روی گراف‏های RDF قابل اعمال هستند. همچنین روش‏های DING و PageRank معنایی نیز مطرح هستند که قابلیت ترکیب گراف وب و گراف موجودیت‏ها را دارند. الگوریتم ObjectRank ]42[ بر پایه الگوریتم PageRank برای جستجوی کلید واژه‏ها در پایگاه‏های داده‏ای است که به صورت گراف‏های برچسب‏دار، مدلسازی شده‏اند. در واقع در این الگوریتم، مشابه الگوریتم HITS از یک مجموعه پایه از اسناد به منظور ایجاد گراف موضوعی، استفاده می‏شود. در این الگوریتم، دو شاخص ObjectRank سراسری و نیز ObjectRank به ازای همه گراف‏های مبتنی بر کلید واژه‏ها، محاسبه و با هم ادغام می‏شوند. مقایسه این الگوریتم نسبت به روش‏های مشابه بر اساس پیچیدگی زمان و فضای محاسباتی مورد نیاز، انجام شده است. الگوریتم HubRank توسعه‏ای از الگوریتم ObjectRank می‏باشد که منجر به ارتقای کارآمدی آن می‏شود ]43[. در سنجش عملکرد روش پیشنهادی، علاوه بر شاخص‏های پیچیدگی زمان و فضای محاسباتی مورد نیاز، از شاخص صحت نیز استفاده شده است. الگوریتم HopRank به منظور مدلسازی نحوه تعامل انسانی با شبکه‏های معنایی طراحی شده است ]44[. بر اساس نتایج حاصل از تحلیل رفتار کاربران انسانی در وبسایت BioPortal¹⁸ که مخزنی از هستان‏شناسی‏های زیست پزشکی است، مشخص شده است که کاربران بجای حرکت تصادفی روی گره‏های آنتولوژی مورد بررسی، غالباً گرایش به پرش به گره‏هایی در فاصله مشخص k از گره فعلی را دارا می‌باشند. احتمال متناظر با این پرش که تحت عنوان k-hop نامیده می‌شود، افرازی روی گره‏ها تحت عنوان HopPortation را به وجود می‏آورد.

گروه دوم از روش‏های مطرح شده در دسته چهارم از الگوریتم‏های بازیابی مبتنی بر نظریه گراف، شامل الگوریتم‏های نظیر DING و PageRank معنایی می‌باشد. بطور مشخص، در الگوریتم DING، یک روش تحلیل سلسله مراتبی از پیوندها ارائه شده است که بر اساس یکی از گسترش‏های PageRank تحت عنوان DatasetRank عمل می‏کند ]45[ و روی یک مدل دو‏لایه‏ای از وب معنایی، اعمال می‏شود. ضمنا ایده اصلی الگوریتم DatasetRank، ادغام رتبه محلی موجودیت‏ها و نیز احتمال پرش به دیگر مجموعه‌های داده، می‏باشد. در ارزیابی عملکرد این روش، از معیارهای ارزیابی استاندارد حوزه بازیابی اطلاعات نظیر P@n، MAP و NDCG@n استفاده شده است. همچنین در الگوریتم PageRank معنایی، توسعه‏ای از الگوریتم پایه PageRank به منظور پیشنهاد پیوند بر اساس گراف علایق کاربران، مطرح شده است ]46[. در این پژوهش از دو نوع بازنمایی گرافی از علایق کاربران، استفاده شده است که یکی از آنها بصورت دوتایی‏هایی از کاربر-داده است و دومی شامل سه‏تایی‌هایی از کاربر-داده-منبع می‌باشد. مطابق ارزیابی‏های صورت گرفته طبق شاخص‏های MAP و NDCG، بهترین عملکرد این الگوریتم مربوط به شرایطی است که در آن، گراف‏های متناظر با علایق کاربران، تراکم کمتری داشته باشند.

در جدول 2، خلاصه مقالات ارزیابی شده ذیل دسته ب (بازیابی معنایی اطلاعات با استفاده از نظریه گراف)، بیان شده است.

به لحاظ آماری، تعداد مقالات مرتبط بررسی شده در دسته دوم در شکل 3 آمده است. مطابق این آمار، کاربرد نظریه گراف در فرآیند بازیابی معنایی اطلاعات، در سال‏های اخیر مورد توجه بیشتری قرار گرفته است.

[1] Ontology

[2] Resource Description Framework

[3] Precision

[4] Recall

[5] Entity-oriented Search

[6] Multimedia Information Retrieval Results Exploration

[7] Inverted Index

[8] Question Answering

[9] Concept Graph

[10] https://tagme.d4science.org/tagme/

[11] Closeness centrality

[12] Pearson Correlation

[13] Tensor Factorization

[14] Background Linking

[15] Transfer Learning

[16] Semantic Hypergraph

[17] https://graphbrain.net

[18] https://bioportal.bioontology.org

جدول 2. خلاصه مقالات ارزیابی شده در دسته ب (بازیابی معنایی اطلاعات با استفاده از نظریه گراف)

نقاط ضعف	نقاط قوت	ایده اصلی	سال چاپ	دسته‌بندی روش	مقاله
محدود بودن به جستجوی موجودیت-محور	بررسی و دسته‏بندی مدل‏های متعدد جستجوی موجودیت-محور مبتنی بر گراف	مرور مدل‏های مبتنی بر گراف برای جستجوی موجودیت-محور	2021	ب-2	[3]
محدود بودن مقاله به معرفی روش‏های پایه و عدم بررسی توسعه‏های روش‏های مطالعه شده	شناسایی و دسته‏بندی تحقیقات صورت گرفته در زمینه کاربرد گراف دانش و چالش‏های آن	بررسی کاربردهای گراف دانش در سامانه‏های پرسش و پاسخ و سامانه‏های توصیه‏گر	2020	ب-1	[22]
عدم توجه به نحوه کاربری روش‏های بررسی شده در دسته‏بندی ارائه شده	ارائه دسته‎بندی سلسله مراتبی از پژوهش‏های انجام شده و نیز نرم‏افزارهای مرتبط	بررسی روش‏های استخراج گراف دانش و به ویژه گراف‏های دانش زمان-محور و بررسی برخی از کاربردهای گراف دانش در سامانه‏های بازیابی اطلاعات	2022	ب-1	[23]
محدود بودن اطلاعات قابل استخراج از گراف دانش مبتنی بر وب معنایی	ایجاد نمایه مفهوم-محور و ادغام آن با نمایه مبتنی بر اسناد به منظور بازیابی معنایی اسناد	توسعه یک روش جستجوی معنایی بر پایه هستان شناسی	2008	ب-1	[24]
عدم استفاده از روش‏های پردازش زبان طبیعی در ایجاد گراف	امکان ادغام داده‏های ساخت یافته و نیز داده‏های بدون ساختار	ارائه روشی برای نمایش یکپارچه پایگاه‏های داده ترکیبی بر اساس گراف‏های RDF	2008	ب-1	[26]
محدود بودن کاربری به جستجوی اخبار برخط	ترکیب توامان دو نگاه سند-محور و موجودیت-محور در انجام جستجو	جستجوی موجودیت-محور با استفاده از مدل‏های زبانی	2009	ب-1	[27]
عملکرد ضعیف در شرایط غنی نبودن پایگاه دانش	بهره‏گیری از روش‏های یادگیری رتبه‏بندی برای ادغام ویژگی‏های استخراج شده	استخراج ویژگی‏های وابسته به روابط بین موجودیت‏ها جهت پاسخ‏دهی به سوالات پیچیده کاربران	2021	ب-1	[28]
عدم استفاده از روش‏های یادگیری ماشین	امکان تعمیم روش پیشنهادی به جستجو در انواع مختلف داده	بازنمایی رابطه معنایی بین اسناد چند‏ رسانه‏ای با استفاده از مدل گراف	2021	ب-1	[29]
بزرگی نسبی زیرگراف‏های تولید شده	کاهش هزینه محاسباتی ناشی از پردازش گراف‏های بسیار بزرگ	رتبه‏بندی نتایج سامانه‏های پرسش و پاسخ بر اساس خوشه‏بندی گراف‏های دانش حجیم	2021	ب-1	[30]
عدم ترکیب اطلاعات ویژگی‏های صریح و ضمنی با یکدیگر	اولویت‏بندی موجودیت‏های اطلاعاتی طبق توییت‏های کاربران	پیوند دهی ضمنی موجودیت‏های اطلاعاتی موجود در گراف‏های دانش	2021	ب-1	[31]
نیاز به حجم نسبتا زیاد داده برای آموزش مدل تصمیم‏گیری	استفاده از گراف دانش برای اولویت‏بندی دروس	پیشنهاد دروس به دانشجویان بر اساس سوابق تحصیلی آنها	2020	ب-1	[32]
عدم امکان انتقال دانش از مدل‏های زبانی تولید شده قبلی	قابلیت پاسخ‏دهی به پرسش‏های پیچیده با استفاده از گراف دانش	اولویت‏بندی گراف‏های پرسش‏های کاربران بر مبنای گراف دانش موجود	2019	ب-1	[33]
عدم استفاده از اطلاعات مربوط به موضوع و رده خطا	ایجاد گراف دانش بر اساس وظایف مولفه‏های مختلف سامانه نرم‏افزاری مورد نظر و نیز روابط بین آنها	انتساب خطاهای گزارش شده سامانه‏های نرم‏افزاری به مولفه‏های تشکیل دهنده آنها	2021	ب-1	[34]
نیاز به حجم نسبتا زیاد داده آموزشی	استخراج روابط زمینه‏ای بین موجودیت‏ها برای فرآیند بازیابی	بازیابی موجودیت‏های اطلاعاتی طبق نیاز کاربر از گراف‏های دانش بسیار بزرگ	2022	ب-1	[35]
دقت نسبتا پایین مولفه تشخیص هدف اسناد	استفاده از مفاهیم ویکیپدیا در مدل‏سازی	محاسبه شباهت معنایی اسناد به کمک گراف مفهوم	2016	ب-2	[36]
نیاز به حجم زیاد داده برای آموزش سیستم	مقیاس پذیری مناسب روی گراف‏های حجیم	استخراج معناشناسی نهفته در روابط موجودیت‏ها	2013	ب-2	[37]
عدم امکان استفاده از الگوریتم پیشنهادی به ازای خبرهای با میزان محتوای متنی محدود	بکارگیری خصوصیات متناظر با گراف موجودیت‏ها و تلفیق آن با ویژگی‏های متنی	حل مسئله پیوند زمینه‏ای با ترکیب ویژگی‏های متناظر با متن خبر و نیز ویژگی‏های مربوط به گراف موجودیت‏ها	2021	ب-2	[38]
هزینه محاسباتی نسبتا بالا	تخصیص امتیاز به زوج‏های اسناد و پرس وجوها توسط نمایش گرافی	استفاده از هایپرگراف پرس وجوها به منظور مدلسازی سطوح بالاتر وابستگی بین واژه‌ها	2012	ب-3	[39]
محدود بودن دادگان مورد استفاده در تولید مدل	ارائه یک کتابخانه نرم‌افزاری در زبان پایتون	بازنمایی دانش استخراج شده از مخازن داده بر اساس هایپرگراف‏های مرتب معکوس	2019	ب-3	[40]
عدم استفاده از داده‏های متنی در تولید هایپر گراف	تبدیل هایپرگراف مورد استفاده به گراف چندگانه متناظر با حضور توامان موجودیت‏ها	رتبه‏بندی موجودیت‏ها بر اساس بکارگیری هایپر گراف‏ها	2019	ب-3	[41]
تعداد زیاد پارامترها در روش پیشنهادی	استفاده از ایده روش HITS در ایجاد گراف موضوعی از اسناد موجود	توسعه الگوریتم PageRank برای جستجو در پایگاه‏های داده‏ مدلسازی به صورت گراف‏های برچسب دار	2004	ب-4	[42]
هزینه محاسباتی بالا بدلیل عدم نمایه سازی و خوشه‏بندی گراف مورد پردازش	استفاده از روش جستجوی مبتنی بر مجاورت در گراف روابط معنایی بین موجودیت‏ها	توسعه روش [42]	2007	ب-4	[43]
نیاز به حجم نسبتا زیاد سوابق تعاملات انسانی	مدلسازی نحوه تعامل انسانی با شبکه‏های معنایی	توسعه روش [43]	2019	ب-4	[44]
رتبه‏بندی مستقل از پرس‏وجوی کاربر	ادغام رتبه محلی موجودیت‏ها	توسعه الگوریتم PageRank با استفاده از مدل دو لایه‏ای از وب معنایی	2010	ب-4	[45]
محدود بودن به منابع مستقیما مرتبط با علایق کاربران	بازنمایی گرافی از علایق کاربران	توسعه الگوریتم PageRank با کمک تکنیک‏های بازیابی معنایی	2017	ب-4	[46]

شکل 3. روش‌های وب کاوی

6- بکارگیری نظریه گراف در یادگیری رتبه‏بندی

رویکرد یادگیری رتبه‏بندی به عنوان یک رویکرد نوین و در عین حال کارآمد در حل مسئله رتبه‏بندی، مورد اقبال گسترده جامعه پژوهشگران قرار گرفته است و از این رو، تلاش بر ارتقای عملکرد روش‏های موجود و یا ارائه راهکارهای نوین، طی حدود یک دهه اخیر، همواره مورد توجه جدی، بوده است. بر این اساس، در این بخش، به صورت خاص به بررسی نحوه بکارگیری نظریه گراف در حل مسئله یادگیری رتبه‏بندی، پرداخته شده است. با توجه به تقسیم‏بندی کلی روش‏های یادگیری رتبه‏بندی به دسته عمده تجمیع رتبه‏بندی و ایجاد رتبه‏بندی ]47[، الگوریتم‏های مورد بررسی در این بخش، ذیل دو زیر دسته فوق، تقسیم‏بندی شده‏اند.

6-1- مدل‏های مبتنی بر تجمیع رتبه‏بندی

از جمله این پژوهش‏ها می‏توان به ]48[ اشاره نمود که در آن، روشی برای حل مسئله ادغام رتبه‏بندی¹ بر اساس بکارگیری نظریه گراف‏ها ارائه شده است.در این پژوهش، از یادگیری بدون نظارت استفاده می‏شود. این روش قادر است نسبت به ترکیب لیست‏های رتبه‏بندی داده که از رتبه‏بندهای مختلف دریافت می‏شود، اقدام نماید. روش پیشنهادی بر اساس مفهومی تحت عنوان گراف ادغام²‏ بنا شده است. بر این اساس، روش ارائه شده، شامل یک فرآیند دو مرحله‏ای است که مرحله برون‏خط، وظیفه بازنمایی مجموعه پاسخ بصورت گراف‏های‏ ادغام را بر عهده دارد. در مقابل، بخش برخط، مسئولیت پردازش پرس‏وجوی دریافتی از کاربر و تهیه رتبه‏بندی نهایی را دارا می‏باشد. در هر دو مرحله، گام استخراج گراف ادغام وجود دارد. طی این گام، بر اساس رتبه‏بندی دریافت شده از هر یک از رتبه‏بندی کننده‏های پایه، یکپارچه‏سازی رتبه‏بندی‏های متناظر با پرس‏وجوی مورد نظر انجام می‏شود. بدین ترتیب، فرآیند جستجو به مسئله یافتن زیرگراف‏های کمینه مشترک³، تبدیل می‏شود. بررسی عملکرد روش پیشنهادی روی دادگان مختلفی صورت گرفته است که مربوط به داده‏های متنی و تصاویر و نیز داده‏های چند رسانه‏ای می‏باشند. این دادگان عبارتند از: Ohsumed و Brodatz برای اطلاعات متنی، MPEG-7 و Soccer برای اطلاعات تصاویر و نیز دادگان UW و UKBench برای دادگان شامل ترکیب متون و داده‏های چند رسانه‏ای. بررسی‏های صورت گرفته روی دادگان فوق، مطابق شاخص NDCG@n، نشان داده است که روش ارائه شده، عملکرد مناسب‏تری نسبت به روش‏های پایه در مسئله ادغام رتبه‏بندی نظیر CombSUM، CombMNZ، CombMIN، CombMAX و BordaCount داشته است. مقایسه روش فوق با روش‏های یادگیری تحت نظارت و نیز ارتقای الگوریتم فوق برای مقیاس‏پذیری در شرایط واقعی، از جمله مسیرهای توسعه آتی این روش است. همچنین در ]49[ روشی برای یکپارچه‏سازی فهرست پیشنهادات در سامانه‏های توصیه‏گر ارائه شده است که بر مبنای الگوریتم فرا ابتکاری⁴ موسوم به تکامل تفاضلی⁵، عمل می‏کند. در واقع، روش پیشنهادی یک الگوریتم یادگیری تحت نظارت است که در آن، با بکارگیری الگوریتم تکامل تفاضلی، تلاش شده است تا عملکرد روش پیشنهادی بر مبنای شاخص متوسط دقت⁶ (AP)، بهینه شود. روش ارائه شده، این قابلیت را دارد که بر مبنای علایق کاربر، تنظیم شود. در پیاده‏سازی روش پیشنهادی، از چهار الگوریتم پایه SVD، BPR، WMF و WARP استفاده شده است . هر چهار الگوریتم فوق، بر مبنای روش فاکتور سازی ماتریسی⁷ طراحی شده‏اند و ویژگی‏های پایه هر فرد جمعیت تکاملی را به ازای هر کالا و هر کاربر، بر اساس ماتریس کالا-کاربر، محاسبه می‏کنند. این ویژگی‏ها را اصطلاحاً ویژگی‏های نهفته⁸ می‏نامند. به منظور بررسی عملکرد روش فوق، از دادگان MovieLens 100k استفاده شده است. ارزیابی‏های صورت گرفته نشان می‏دهد که الگوریتم ارائه شده، بر مبنای شاخص‏های ارزیابی نظیر P@n و MAP، قادر است نسبت به الگوریتم‏های پایه ترکیب اطلاعات نظیر Borda Count و Majority Voting، عملکرد مناسب‏تری داشته باشد. به منظور توسعه روش پیشنهادی، می‏توان تکنیکی برای ارزیابی اولیه توصیه‏کننده‏های پایه، طراحی نمود به نحوی که پیش از یکپارچه‏سازی فهرست‏های پیشنهادی، پیشنهاد دهنده‏های ضعیف، شناسایی و حذف شوند. از سوی دیگر، تصمیم‏گیری برای محل تحصیل، یکی از دغدغه‏های اصلی دانشجویان است. وجود رتبه‏بندی‏های مختلف، اتخاذ تصمیم مناسب را با مشکلاتی مواجه می‏کند. بر این اساس، در پژوهش ]50[، روشی برای رتبه‏بندی دانشگاه‏های جهان، ارائه شده است که قادر است از ترکیب رتبه‏بندی‏های مختلف انجام شده، فهرست یکپارچه‏ای را تولید کند. روش پیشنهادی، یک الگوریتم مبتنی بر گراف است که بر پایه ایجاد و پردازش گراف رقابت بین دانشگاه‏های مختلف، طراحی شده است. در این گراف جهت دار و وزن‏دار، هر گره، معادل یک دانشگاه است و هر یال از یک دانشگاه به دانشگاه دیگر، به صورت تابعی از میزان برتری دانشگاه اول نسبت به دانشگاه دوم در رتبه‏بندی‏های پایه است. بر مبنای این برتری، شاخصی تحت عنوان کیفیت برای هر دانشگاه تعریف می‏شود که معادل نسبت درجه خروجی به ورودی به ازای راس متناظر در گراف رقابت است. رتبه‏بندی نهایی دانشگاه‏ها بر اساس شاخص فوق، صورت می‏گیرد. به منظور بررسی و تحلیل روش پیشنهادی، از مجموعه پنج دادگان مختلف شامل USNEWS، ARWU، QS، THE و URAP استفاده شده است. آزمایش‏های انجام شده طبق شاخص‏های دقت و صحت، نشان می‏دهد روش پیشنهادی، قادر است رتبه‏بندی جامعی از دانشگاه‏ها را ارائه دهد و در عین حال، نویز موجود در لیست‏های رتبه‏بندی دریافتی را نیز حذف کند. پژوهشگران این تحقیق در نظر دارند کاربرد الگوریتم پیشنهادی را در حوزه‏های دیگری نظیر رتبه‏بندی برندها، رتبه‏بندی نتایج جستجو در وب و رتبه‏بندی تیم‏های ورزشی، بررسی کنند. علاوه بر آن، در ]51[ روشی مبتنی بر گراف برای ترکیب رتبه‏بندی در حوزه بازیابی تصاویر، ارائه شده است. ایده اصلی در الگوریتم، انتخاب ویژگی‏های موثر در فرآیند رتبه‏بندی است. برای این منظور، گرافی ایجاد می‏شود که گره‏های آن، ویژگی‏های مختلف تصاویر نظیر رنگ، بافت و نظایر آنها هستند و وزن یال‏های بین گره‏ها، میزان مکمل بودن نسبی آنها را نشان می‏دهد. این گراف، بصورت تدریجی، بر مبنای آستانه‏های مختلف میزان موثر بودن ویژگی‏ها، بروز رسانی می‏شود تا بر این اساس، امکان شناسایی موثرترین ویژگی‏ها حاصل شود. سپس یال‏های این گراف بر مبنای آستانه‏های همبستگی رتبه‏بندی ویژگی‏های متناظر، بروز می‏شود. بدین ترتیب، یال‏ها شامل اطلاعات میزان مکمل هم بودن ویژگی‏ها خواهند بود. گراف تولید شده، قادر است تخمینی از میزان موثر بودن هر ویژگی و مکمل آن نسبت به بقیه ویژگی‏ها را بدست دهد. ویژگی‏های منتخب نهایی بر مبنای مولفه‏های همبند گراف فوق، تعیین می‏شوند. ارزیابی عملکرد این الگوریتم روی دادگان مختلفی نظیر Flowers، Holidays، Corel5k و UKBench، طبق شاخص MAP نشان می‏دهد که روش پیشنهادی قادر است ترکیبات کارآمدی از ویژگی‏های کلیدی در فرآیند رتبه‏بندی را شناسایی و مورد استفاده قرار دهد. بکارگیری روش‏های مختلف ترکیب اطلاعات و ترکیب گونه‏های مختلف الگوریتم ارائه شده، از جمله مسیرهای تحقیقاتی پیشنهای در این پژوهش است.

6-2- مدل‏های مبتنی بر ایجاد رتبه‏بندی

از نمونه‏های کاربرد نظریه گراف در ایجاد رتبه‏بندی می‏توان به ]52 و 53[ اشاره نمود که در آنها الگوریتم یادگیری رتبه‏بندی جدیدی ارائه شده است که طی آن، ابتدا بر مبنای محاسبه شاخص Kendall’s tau بین هر زوج از ویژگی‏های موجود در دادگان پایه مورد استفاده در یادگیری رتبه‏بندی، گراف شباهت بین ویژگی‏های دادگان یادگیری رتبه‏بندی، ایجاد می‏گردد. در ادامه، بر مبنای یک آستانه حداقل شباهت، این گراف، هرس می‏شود. سپس از الگوریتم‏ خوشه‏یابی طیفی⁹ به منظور اِفراز گراف فوق، استفاده می‏شود تا ویژگی‏های با میزان مشابهت قابل توجه، در خوشه‏های یکسانی قرار گیرند. در مرحله بعد و بر مبنای خوشه‏یابی بعمل آمده، دو گام موازی، طی می‏شود. در یکی از این دو گام، از هر خوشه، زیر مجموعه محدودی از ویژگی‏های مهم‏تر، انتخاب می‏شود و نهایتاً از ترکیب آنها، الگوریتم یادگیری رتبه‏بندی جدیدی، حاصل می‏شود. در گام موازی دوم نیز از گراف شباهت ویژگی‏ها، برای محاسبه میزان اهمیت و مرتبط بودن نسبی ویژگی‏های پایه به کمک الگوریتم Biased PageRank، استفاده می‏شود. برای ارزیابی عملکرد الگوریتم ارائه شده، از مجموعه دادگان LETOR، استفاده شده است. نتایج حاصل از آزمایش‏های انجام شده، طبق شاخص‏های MAP و NDCG@n نشان می‏دهد که الگوریتم پیشنهاد شده، عملکرد بهتری نسبت به روش‏های مطرح در یادگیری رتبه‏بندی نظیر RankSVM دارد. به منظور توسعه این روش، می‏توان از روش‏های ترکیب اطلاعات بر مبنای وزن‏دهی نسبی ویژگی‏های منتخب در هر خوشه استفاده نمود. همچنین استفاده از ویژگی‏های منتخب در توسعه روش‏های رتبه‏بندی پایه، جالب توجه می‏باشد. علاوه بر آن بررسی استفاده از شاخص‏های آماری دیگری نظیر Spearman’s rho جهت ایجاد گراف مشابهت بین ویژگی‏ها، حائز اهمیت می‏باشد. از سوی دیگر در ]54[، یک الگوریتم یادگیری رتبه‏بندی تصاویر، ارائه شده است که قادر است بر اساس ادغام خصوصیات متن صفحات و نیز ویژگی‏های متناظر با تصاویر، اقدام به اولویت‌بندی تصاویر نماید. در این الگوریتم با استفاده از ویژگی‏های تصویری سطح پایین متناظر با تصاویر، گراف مشابهت بین تصاویر مختلف ایجاد می‏شود و بکمک روش یادگیری خروجی حاشیه‏ای ساخت‏یافته¹⁰ ]55[ و ترکیب آنها با ویژگی‏های متنی تصاویر، اقدام به اولویت‏بندی آنها می‏کند. ضمناً در سنجش عملکرد این روش از شاخص NDCG@n استفاده شده است. در بررسی صورت گرفته در ]56[، بیان شده است که به دلیل وجود تعداد کم پیوندهای بین پرس و جوها و صفحات وب در گراف دوبخشی بین این دو و نیز عدم تعادل بین تعداد صفحات(تریلیون) و تعداد پرس و جوهای کاربران (بیلیون) و همچنین در تعداد حاشیه نویسی‏ها، استفاده و افزایش مقیاس شبکه‏های عصبی مبتنی بر گرافهای پیچشی، دشوار است. لذا در این مقاله ابتدا دو زیرگراف تک بخشی Q و W با حفظ ارتباطات معرفی شده اند و سپس یک ساختار LTRGCN پیشنهاد شده است که یک کانال ارتباطی یادگیری رتبه‏بندی است. این ساختار از این دو زیرگراف برای نمونه‏برداری استفاده می‌کند و در نهایت امتیازات رتبه‏بندی را پیش ‏بینی می‏کند. برای ارزیابی LtrGCN از دو مجموعه داده‌ی دنیای واقعی و آزمایش‌های برخط بر اساس آزمون A/B در یک موتور جستجوی مقیاس بزرگ استفاده شده است. نتایج برون‏خط نشان می‌دهد که LtrGCN می‌تواند شاخص NDCG را بین 2.89 تا 3.97 درصد نسبت به روشهای پایه افزایش دهد. الگوریتم LtrGCN با ترافیک واقعی در یک موتور جستجوی مقیاس بزرگ نیز استفاده شده است و پیشرفتهای چشمگیری را در حالت برخط نیز نشان می‏هد. همچنین در ]57[، با استفاده از یک روش مبتنی بر نظریه گراف، بازنمایی دادگان مختلف یادگیری رتبه‏بندی و مقایسه تطبیقی آنها صورت گرفته است. در روش پیشنهادی، به ازای هر مجموعه داده یادگیری رتبه‏بندی، گرافی تحت عنوان گراف مشابهت ویژگی‏ها ایجاد می‏شود که گره‏های آن، ویژگی‏های ارائه شده در مجموعه داده مورد بررسی می‏باشد و وزن‏ هر یال، متناظر با میزان شاخص کندال به ازای زوج ویژگی‏های دو سر آن یال می‏باشد. از گراف حاصل و نیز مولفه غول‏پیکر آن، مجموعه‏ای از خصوصیات ساختاری و نیز تعدادی از خصوصیات متناظر با ویژگی‏ها استخراج می‏شود. این خصوصیات، امکان مقایسه دادگان محک در حوزه یادگیری رتبه‏بندی را فراهم می‏سازد. در ]58[ نیز الگوریتمی برای رتبه‏بندی گره‏ها در گراف متناظر با راه‏های مواصلاتی ارائه شده است. این الگوریتم، شامل یک مولفه جاسازی است که از شبکه عمیق رمزگذار برای یادگیری بازنمایی‏ نهفته به ازای هر قطعه از جاده استفاده می‏کند. از سوی دیگر با بکارگیری روش ادغام گراف‏های چندگانه، امکان نگاشت بخش‏های مختلف شبکه راه‏ها را فراهم می‏آورد. بدین ترتیب، یک روش یادگیری رتبه‏بندی به منظور اولویت‏بندی بخش مختلف شبکه مواصلاتی بر اساس مشخصات مختلف آنها نظیر ویژگی‏های ترافیکی، تعداد باندهای جاده و نیز متوسط سرعت در هر بخش، بدست می‏آید.

در جدول 3، خلاصه مقالات ارزیابی شده ذیل دسته ج (بازنمایی گرافی از مسائل حوزه یادگیری رتبه‏بندی)، آمده است.

به لحاظ آماری، تعداد مقالات مرتبط بررسی شده در دسته سوم در شکل 4 آمده است. بر اساس داده‏های این نمودار، رویکرد استفاده از نظریه گراف در یادگیری رتبه‏بندی، رویکرد نوینی است و عمده تحقیقات در این حوزه، مربوط به چند سال اخیر است.

شکل 4. فراوانی تعداد مقالات مرتبط بررسی شده در دسته سوم (بکارگیری نظریه گراف در یادگیری رتبه‏بندی)

7- جمع‏بندی و نتيجه‏گیری

بازیابی اطلاعات که با هدف تهیه اطلاعات مورد نیاز کاربر، انجام می‏شود، فرآیندی دشوار می‏باشد که همواره نیازمند ارتقا و بهبود می‏باشد. از سوی دیگر غنای نظریه گراف و کاربردهای گسترده آن در حل مسائل روزمره، پژوهشگران را به استفاده از این نظریه به منظور طراحی الگوریتم‏های کارآمد بازیابی اطلاعات ترغیب نموده است. با عنایت به موفقیت قابل توجه این الگوریتم‏ها، در این پژوهش، به بررسی کاربرد نظریه گراف در فرآیند بازیابی اطلاعات پرداخته شد و در این خصوص، پنجاه و دو مورد از تحقیقات مرتبط، مورد مطالعه و دسته‏بندی قرار گرفت.

[1] Rank Aggregation

[2] Fusion Graph

[3] Minimum Common Subgraphs

[4] Metaheuristic

[5] Differential Evolution

[6] Average Precision

[7] Matrix Factorization

[8] Latent Features

[9] Spectral clustering

[10] Margin structured output learning

جدول 3. خلاصه مقالات ارزیابی شده در دسته ج (بازنمایی گرافی از مسائل حوزه یادگیری رتبه‏بندی)

نقاط ضعف	نقاط قوت	ایده اصلی	سال چاپ	دسته‌بندی روش	مقاله
هزینه محاسباتی زیاد	امکان استفاده برای رتبه‏بندی گونه‏های مختلف داده‏های متنی و چند رسانه‏ای	بازنمایی پرس‏وجوها و فهرست رتبه‏بندی دریافتی از هر رتبه‏بندی کننده گراف ادغام	2019	ج-1	[48]
عملکرد ضعیف در صورت ضعف پیشنهاد دهنده‏های پایه	عملکرد مطلوب در بازیابی اطلاعات	استخراج ویژگی‏های نهفته به ازای پیشنهاد دهنده‏های پایه و استفاده از روش فرا ابتکاری تکامل تفاضلی	2022	ج-1	[49]
هزینه محاسباتی زیاد	حذف تاثیر نویز موجود در لیست‏های رتبه‏بندی پایه	ایجاد گرافی جهت دار و وزن‏دار موسوم به گراف رقابت از روی رتبه‏بندی‏های پایه	2021	ج-1	[50]
عدم استفاده از عملگرهای مطرح در حوزه ترکیب اطلاعات به منظور ادغام ویژگی‏های منتخب	کارآمدی و موثر بودن روش ارائه شده بواسطه استفاده از تعداد محدود ویژگی‏ها بواسطه انتخاب ویژگی‏های مکمل	ارائه روشی برای ترکیب رتبه‏بندی در حوزه بازیابی تصاویر که در آن، با تشکیل گراف مکمل بین ویژگی‏های مختلف تصاویر، ویژگی‏های موثر در فرآیند رتبه‏بندی، انتخاب و ترکیب می‏شوند.	2020	ج-1	[51]
بررسی محدود عملکرد روش پیشنهادی	هزینه محاسباتی اندک	ایجاد گراف مشابهت ویژگی‏های دادگان یادگیری رتبه‏بندی و استفاده از زیرمجموعه محدودی از ویژگی‏های پایه	2022	ج-2	[52]
بررسی محدود عملکرد روش پیشنهادی	استفاده صرف از ویژگی‏های مهم در فرآیند یادگیری رتبه‏بندی	ایجاد گراف مشابهت بین ویژگی‏ها و انتخاب ویژگی‏ها با حداقل افزونگی	2020	ج-2	[53]
نیاز به حجم زیاد دادگان آموزشی	استفاده از ویژگی‏های تصویری سطح پایین تصاویر در تولید مدل	یادگیری رتبه‏بندی تصاویر بر اساس ادغام خصوصیات متن و نیز ویژگی‏های تصاویر	2009	ج-2	[54]
بهبود محدود نسبت به روش‏های پایه علیرغم هزینه محاسباتی بالا	امکان بکارگیری در شرایط تعداد کم بودن پیوندهای بین پرس و جوها و صفحات وب در گراف دوبخشی بین این دو و نیز عدم تعادل بین تعداد صفحات و تعداد پرس و جوهای کاربران و همچنین در تعداد حاشیه نویسی‏ها	استفاده از شبکه‏ گراف پیچشی به منظور ارائه یک روش یادگیری رتبه‏بندی	2023	ج-2	[56]
عدم ترکیب این روش بازنمایی دادگان با روش‏های آماری کلاسیک	امکان مقایسه دادگان با مختصات و ویژگی‏های متفاوت	ارائه یک روش مبتنی بر نظریه گراف برای بازنمایی دادگان مختلف یادگیری رتبه‏بندی و مقایسه تطبیقی آنها	2024	ج-2	[57]
نیاز به حجم زیاد داده آموزش	در نظر گرفتن مشخصات مختلف مسیرهای مواصلاتی نظیر ویژگی‏های ترافیکی، تعداد باندهای جاده و نیز متوسط سرعت در هر بخش از جاده	اولویت‌بندی قطعات شبکه راه‏ها با استفاده از خصوصیات مختلف مسیرها با بکارگیری روش ادغام گراف‏های چندگانه	2024	ج-2	[58]

بر این اساس، مشخص شد، این تحقیقات، در سه دسته کلی، قابل تفکیک می‏باشند. دسته نخست، شامل تحقیقاتی است که در آنها از بازنمایی گرافی از دادگان در فرآیند بازیابی اطلاعات، استفاده شده است. در مقابل، دسته دوم شامل کاربرد نظریه گراف در بازیابی معنایی اطلاعات است و نهایتاً دسته سوم مربوط به بکارگیری نظریه گراف در فرآیند یادگیری رتبه‏بندی است. از سوی دیگر، در یک بررسی دقیق‏تر مشخص شد که تحقیقات دسته نخست، در دو زیر دسته، قابل گروه‌بندی است: در زیر دسته اول، از بازنمایی گرافی دادگان جهت استخراج ویژگی‏های مبتنی بر گراف و ترکیب این ویژگی‏ها با ویژگی‏های پایه دادگان، استفاده شده است؛ در حالی که زیر دسته دوم شامل روش‏هایی است که در آنها ویژگی‏های آماری دادگان استخراج می‏شود و سپس، یک بازنمایی گرافی از این ویژگی‏ها، به منظور ارتقای فرآیند بازیابی اطلاعات، ارائه می‏شود. در مقابل، دسته دوم، شامل پژوهش‏هایی است که در آنها از نظریه گراف به منظور بازیابی معنایی اطلاعات، استفاده شده است. در این خصوص، پژوهش‏های بررسی شده، از چهار رویکرد متفاوت، شامل: استفاده از گراف دانش، ایجاد گراف موجودیت، بکارگیری مدل‏های مبتنی بر هایپر گراف و نیز مدل پویش تصادفی، استفاده کرده‏اند. نهایتاً دسته سوم مربوط به بهره‏گیری از نظریه گراف در فرآیند یادگیری رتبه‏بندی است که خود در دو زیر دسته‏ اصلی، یعنی ایجاد رتبه‏بندی و تجمیع رتبه‏بندی، تقسیم‌بندی می‏شوند.

از سوی دیگر، به لحاظ آماری، در این نوشتار، از دسته نخست، یعنی بکارگیری بازنمایی گرافی از دادگان در فرآیند بازیابی اطلاعات، تعداد 16 پژوهش شاخص، شناسایی و بررسی شد. در مقابل، از دسته دوم یعنی بکارگیری نظریه گراف در فرآیند بازیابی معنایی اطلاعات، تعداد 25 تحقیق، شناسایی و ارزیابی شد و نهایتاً از دسته سوم تحقیقات مربوط به بکارگیری نظریه گراف در یادگیری رتبه‏بندی، تعداد 7 پژوهش، مورد مطالعه و بررسی، قرار گرفت. بر این اساس، بنظر می‌رسد در دو دسته اول و دوم، تعداد نسبتا زیادی از تحقیقات، صورت گرفته است، در حالی که بکارگیری نظریه گراف در یادگیری رتبه‏بندی، کماکان می‌تواند یک موضوع تحقیقاتی جذاب در حوزه بازیابی اطلاعات باشد.

در عین حال، به عنوان پیشنهادهایی به منظور توسعه آتی هر دسته از روش‏های بررسی شده، می‏توان به موارد ذیل اشاره نمود. در دسته نخست که به بازیابی اطلاعات بر مبنای ارائه بازنمایی گرافی از دادگان بازیابی اطلاعات، پرداخته است، مواردی نظیر بکارگیری نظریه ترکیب اطلاعات و استفاده از توان محاسباتی عملگرهای ترکیب اطلاعات به منظور ادغام ویژگی‏های گرافی و ویژگی‏های پایه به طور خاص با توجه به نایقینی موجود در ویژگی‏های پایه و ویژگی‏های گرافی و بکارگیری نظریه استدلال شهودی و انتگرال‏های فازی، از جمله زمینه‏های توسعه روشهای بازیابی اطلاعات در این دسته به نظر می‏رسند. در خصوص دسته دوم کاربردهای گراف در بازیابی اطلاعات که مربوط به بازیابی معنایی اطلاعات با استفاده از نظریه گراف می‏باشد، با عنایت به تعدد و تنوع عناصر داده‏ای متناظر با اسناد و پرس و جوهای کاربران و نیز پیچیدگی‏های ارتباطات معنایی مابین آنها، بکارگیری مدل‏های یادگیری ژرف به منظور شناسایی الگوهای کارآمد در بازیابی اطلاعات یک ضرورت جدی، محسوب می‏شود. ضمنا وجود انواع موجودیت‏های داده‏ای و نیز روابط توام با درجاتی از نایقینی مابین آنها چه در متن اسناد و چه در واژگان بکار رفته در پرس و جوی کاربر، نیاز مبرم به بکارگیری نظریه‏های توانمند در مدلسازی و مواجه با نایقینی نظیر استدلال شهودی و انتگرا‏‏ل‏های فازی را بوجود آورده است. نهایتا در دسته سوم که مربوط به بهره‏گیری از نظریه گراف در یادگیری رتبه‏بندی است، استفاده از مدل‏های یادگیری ماشین قدرتمندی نظیر یادگیری ژرف امکان ارائه مدل‏های پیچیده‏تر و کامل‏تر یادگیری رتبه‏بندی را فراهم می‏آورد. در عین حال توجه به این نکته که سامانه‌های بازیابی اطلاعات سامانه‏های کاربر محوری هستند، بکارگیری نظریه گراف به منظور مدلسازی رفتار تعاملی کاربر با این سامانه‏ها بسیار مفید خواهد بود. در کنار همه این موارد بهره‏گیری از رویکرد ترکیب اطلاعات به منظور تلفیق کارآمد عناصر اطلاعاتی بسیار حائز اهمیت خواهد بود. ضمنا توجه به ارتباط معنایی اجزای اسناد و پرس و جوهای کاربر و نیز ویژگی‏های متناظر با آنها و بکارگیری مدل‏های بازیابی معنایی اطلاعات بخش مهمی از معضلات مد‏ل‏های پایه فعلی مورد استفاده در سامانه‏های بازیابی اطلاعات را که عمدتا مبتنی بر مدل سبد کلمات هستند، تقلیل خواهد داد.

مراجع

[1] C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Information Retrieval. Cambridge University Press, 2008. doi: 10.1017/cbo9780511809071.

[2] R. Baeza-Yates, Modern Information Retrieval: The Concepts and Technology Behind Search, Second Eit. Addison-Wesley Professional, 2011.

[3] 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.

[4] 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.

[5] 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.

[6] 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.

[7] 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.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] 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.

[13] 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.

[14] 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.

[15] 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

[16] 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

[17] 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.

[18] 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.

[19] 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.

[20] 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.

[21] 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.

[22] 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.

[23] 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.

[24] 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.

[25] 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.

[26] K. Byrne, “Populating the Semantic Web-Combining Text and Relational Databases as RDF Graphs,” The University of Edinburgh, 2008.

[27] K. Balog et al., “SaHaRa: Discovering Entity-Topic Associations in Online News,” 2009.

[28] 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

[29] 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.

[30] 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

[31] 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.

[32] 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.

[33] 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.

[34] 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.

[35] 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.

[36] 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.

[37] 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.

[38] 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

[39] 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.

[40] T. Menezes and C. Roth, “Semantic Hypergraphs,” Aug. 2019, Accessed: Apr. 07, 2023. [Online]. Available: http://arxiv.org/abs/1908.10784

[41] 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.

[42] B. A., “ObjectRank : Authority-Based Keyword Search in Databases,” VLDB 2004, 2004.

[43] 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.

[44] 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.

[45] 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.

[46] 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.

[47] H. Li, “Learning to Rank for Information Retrieval and Natural Language Processing, Second Edition,” Synth. Lect. Hum. Lang. Technol., vol. 7, no. 3, pp. 1–123, Oct. 2015, doi: 10.2200/S00607ED2V01Y201410HLT026.

[48] 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.

[49] 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.

[50] 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.

[51] 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.

[52] 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.

[53] 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.

[54] 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

[55] 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.

[56] Y. Li et al., “LtrGCN: Large-Scale Graph Convolutional Networks-Based Learning to Rank for Web Search,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 14174 LNAI, pp. 635–651, 2023, doi: 10.1007/978-3-031-43427-3_38.

[57] A. H. Keyhanipour, “Graph-based comparative analysis of learning to rank datasets,” Int. J. Data Sci. Anal., vol. 17, no. 2, pp. 165–187, Mar. 2024, doi: 10.1007/S41060-023-00406-8/METRICS.

[58] M. Xu and J. Zhang, “MGL2Rank: Learning to rank the importance of nodes in road networks based on multi-graph fusion,” Inf. Sci. (Ny)., vol. 667, p. 120472, May 2024, doi: 10.1016/J.INS.2024.120472.

Share To

Article Url

Survey on the Applications of the Graph Theory in the Information Retrieval

Rimag

Links

Related Centers

Technical Support

Official pages