Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Graph Representations for Reinforcement Learning
DOI:
https://doi.org/10.24215/16666038.24.e03Keywords:
Computational Intelligence, Reinforcement Learning, Graph Embeddings, unsupervised GRL, Whole Graph EmbeddingAbstract
Graph analysis is becoming increasingly important due to the expressive power of graph models and the efficient algorithms available for processing them. Reinforcement Learning is one domain that could benefit from advancements in graph analysis, given that a learning agent may be integrated into an environment that can be represented as a graph. Nevertheless, the structural irregularity of graphs and the lack of prior labels make it difficult to integrate such a model into modern Reinforcement Learning frameworks that rely on artificial neural networks. Graph embedding enables the learning of low-dimensional vector representations that are more suited for machine learning algorithms, while retaining essential graph features. This paper presents a framework for evaluating graph embedding algorithms and their ability to preserve the structure and relevant features of graphs by means of an internal validation metric, without resorting to subsequent tasks that require labels for training. Based on this framework, three defined algorithms that meet the necessary requirements for solving a specific problem of Reinforcement Learning in graphs are selected, analyzed, and compared. These algorithms are Graph2Vec, GL2Vec, and Wavelet Characteristics, with the latter two demonstrating superior performance.
Downloads
Download data is not yet available.
References
L.Freeman,“Visualizingsocialnetworks,”Journalof social structure, vol. 1, no. 1, p. 4, 2000.
R. Ferrer I Cancho and R. Sole ́, “The small world of human language,” Proc. Biological sciences, vol. 268, no. 1482, p. 2261—2265, November 2001. [Online]. Available: https://doi.org/10.1098/rspb.2001.1800
T. Theocharidis, S. van Dongen, A. Enright, and T. Freeman, “Network visualization and analysis of gene expression data using biolayout express(3d),” Nature Protocols, vol. 4, no. 10, pp. 1535 –1550, 2009. [Online]. Available: https://doi.org/10.1038/ nprot.2009.177
J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM Trans. on Knowl.Discovery from
Data, vol. 1, no. 1, pp. 2–43, 2007. [Online]. Available: https://doi.org/10.1145/1217299.1217301
P.GoyalandE.Ferrara,“Graphembeddingtechniques, applications, and performance: A survey,” Knowledge- Based Systems, vol. 151, pp. 78–94, 2018. [Online]. Available: https://doi.org/10.1016/j.knosys.2018.03. 022
B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proc, of the 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, ser. KDD ’14. New
KDD ’16. New York, USA: Assoc. for Computing Machinery, 2016, p. 1105–1114. [Online]. Available: https://doi.org/10.1145/2939672.2939751
C. Ding, X. He, H. Zha, M. Gu, and H. Simon, “A min-max cut algorithm for graph partitioning and data clustering,” in Proc. 2001 IEEE Int. Conf. on Data Mining, 2001, pp. 107–114. [Online]. Available: https://doi.org/10.1109/ICDM.2001.989507
D.Wang,P.Cui,andW.Zhu,“Structuraldeepnetwork embedding,” in Proc. of the 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, ser. KDD ’16. New York, USA: Assoc. for Computing Machinery, 2016, p. 1225–1234. [Online]. Available: https://doi.org/10.1145/2939672.2939753
I. Chami, S. Abu-El-Haija, B. Perozzi, C. Re ́, and K. Murphy, “Machine learning on graphs: A model and comprehensive taxonomy,” Journal of Machine Learning Research, vol. 23, no. 89, pp. 1 –64, 2022. [Online]. Available: http://jmlr.org/papers/v23/20-852. html
P. Cui, X. Wang, J. Pei, and W. Zhu, “A survey on network embedding,” IEEE transactions on knowledge and data engineering, vol. 31, no. 5, pp. 833 –852, 2018.
C.L.Staudt,A.Sazonovs,andH.Meyerhenke,“Net- workit: A tool suite for large-scale complex network analysis,” Network Science, vol. 4, no. 4, pp. 508 –530, 2016.
R. Sutton and A. Barto, Reinforcement learning: An introduction. MIT press, 2018.
A. G. Barto, R. S. Sutton, and C. W. Anderson, “Looking back on the actor–critic architecture,” IEEE Trans.on Syst., Man and Cybernetics: Systems, vol. 51, no. 1, pp. 40–50, 2021. [Online]. Available:
https://doi.org/10.1109/TSMC.2020.3041775
E. Schab, C. Casanova, and F. Piccoli, “Solving an instance of a routing problem through reinforce- ment learning and high performance computing,” in Cloud Computing, Big Data & Emerging Topics, E. Rucci, M. Naiouf, F. Chichizola, L. De Giusti, and A. De Giusti, Eds. Cham: Springer Int. Publishing, 2022, pp. 107 –121.
A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, and S. Jaiswal, “graph2vec: Learning distributed representations of graphs,” 2017.
H. Chen and H. Koga, “Gl2vec: Graph embedding enriched by line graphs with edge features,” in Neural Information Processing, T. Gedeon, K. W. Wong, and M. Lee, Eds. Cham: Springer Int. Publishing, 2019, pp. 3 –14. [Online]. Available: https://doi.org/10.1007/978-3-030-36718-3 1
B. Rozemberczki and R. Sarkar, “Characteristic func- tions on graphs: Birds of a feather, from statistical descriptors to parametric models,” 2020.
Z. C. Lipton, J. Berkowitz, and C. Elkan, “A critical review of recurrent neural networks for sequence learn- ing,” 2015.
Z. Li, F. Liu, W. Yang, S. Peng, and J. Zhou, “A survey of convolutional neural networks: Analysis, applications, and prospects,” IEEE Transactions on Neural Networks and Learning Systems, vol. 33, no. 12, pp. 6999–7019, 2022. [Online]. Available: https://doi.org/10.1109/TNNLS.2021.3084827
A.-L. Baraba ́si, “Network science,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 371, no. 1987, p. 20120375, 2013.
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: Going beyond euclidean data,” IEEE Signal Processing Magazine, vol. 34, no. 4, pp. 18–42, 2017. [Online]. Available: https://doi.org/10.1109/MSP.2017.2693418
H.Cai,V.W.Zheng,andK.Chang,“Acomprehensive survey of graph embedding: Problems, techniques, and applications,” IEEE Transactions on Knowledge & Data Engineering, vol. 30, no. 09, pp. 1616–1637, sep 2018. [Online]. Available: https://doi.org/10.1109/ TKDE.2018.2807452
A. Bordes, X. Glorot, J. Weston, and Y. Bengio, “A semantic matching energy function for learning with multi-relational data: Application to word-sense disam- biguation,” Machine Learning, vol. 94, pp. 233 –259, 2014.
X.Wang,P.Cui,J.Wang,J.Pei,W.Zhu,andS.Yang, “Community preserving network embedding,” in Proc.
of the AAAI Conf. on AI, vol. 31, no. 1, 2017.
S. F. Mousavi, M. Safayani, A. Mirzaei, and H. Ba- honar, “Hierarchical graph embedding in vector space by graph pyramid,” Pattern Recognition, vol. 61, pp. 245–254, 2017.
M.Nie,D.Chen,andD.Wang,“Reinforcementlearn- ing on graphs: A survey,” 2023.
D. Grattarola, D. Zambon, F. M. Bianchi, and C. Alippi, “Understanding pooling in graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems, pp. 1–11, 2022. [Online]. Available: https://doi.org/10.1109/TNNLS.2022.3190922
A. A. Hagberg, D. A. Schult, and P. J. Swart, “Ex- ploring network structure, dynamics, and function us- ing networkx,” in Proc. of the 7th Python in Science
Conf., G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15.
B.Rozemberczki,O.Kiss,andR.Sarkar,“KarateClub: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs,” in Proc. of the 29th ACM Int. Conf. on Information and Knowledge Management (CIKM ’20). ACM, 2020, p. 3125–3132.
E. A. Schab, “estebanschab/RL-GraphEmbeddings: Release for publication in JCC2023,” Apr. 2023. [Online]. Available: https://doi.org/10.5281/zenodo. 7830059
G. Clarke and J. W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, vol. 12, no. 4, pp. 568 –581, 1964. [Online]. Available: http://www.jstor.org/stable/167703
M. Asghari and M. Mirzapour Al-e-hashem, “Green vehicle routing problem: A state-of-the-art review,” Int. Journal of Production Economics, vol. 231, p. 107899, 2021. [Online]. Available: https://doi.org/10.1016/j. ijpe.2020.107899
B. Jain and K. Obermayer, “Graph quantization,” Computer Vision and Image Understanding, vol. 115, no. 7, pp. 946–961, 2011. [Online]. Available: https://doi.org/10.1016/j.cviu.2011.03.004
Q. Le and T. Mikolov, “Distributed representations of sentences and documents,” in Int. Conf. on machine learning. PMLR, 2014, pp. 1188 –1196.
T.Mikolov,I.Sutskever,K.Chen,G.S.Corrado,and J. Dean, “Distributed representations of words and phrases and their compositionality,” Advances in neu- ral information processing systems, vol. 26, 2013.
Downloads
Published
2024-04-22
Issue
Section
Original Articles
License
Copyright (c) 2024 Esteban Schab, Carla Casanova, Fabiana Piccoli
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
How to Cite
[1]
“Graph Representations for Reinforcement Learning”, JCS&T, vol. 24, no. 1, p. e03, Apr. 2024, doi: 10.24215/16666038.24.e03.
