Explorando GNNs Sensíveis a Arestas para Previsão de Carga em uma Rede Backbone
Resumo
Redes neurais de grafos (GNNs) são ferramentas para aplicação de aprendizado de máquina a vários tipos de dados complexos estruturados em grafos. A maioria das GNNs, no entanto, é focada em representar nós ou grafos inteiros, deixando de lado informações que possam estar contidas em atributos de arestas. Neste trabalho, apresentamos um modelo de GNN sensível a arestas com mecanismos de atenção aplicado à previsão de carga em nós de uma rede backbone. O modelo proposto é capaz de processar atributos implícitos e explícitos de arestas juntamente aos atributos de nós, contribuindo para aprimorar a representação dos dados. Nos testes realizados para previsão de carga, nosso modelo superou os resultados obtidos pelo estado da arte dos modelos de GNNs não sensíveis às arestas. A ferramenta que desenvolvemos para testes está disponível publicamente.
Referências
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD int. conference on knowledge discovery & data mining, pages 2623–2631.
Bandyopadhyay, S., Biswas, A., Murty, M. N., and Narayanam, R. (2019). Beyond node embedding: A direct unsupervised edge representation framework for homogeneous networks. CoRR, abs/1912.05140.
Barabási, A.-L. et al. (2016). Network Science. Cambridge University Press.
Bessadok, A., Mahjoub, M. A., and Rekik, I. (2021). Graph neural networks in network neuroscience. CoRR, abs/2106.03535.
Bielak, P., Kajdanowicz, T., and Chawla, N. V. (2020). Attre2vec: Unsupervised attributed edge representation learning. CoRR, abs/2012.14727.
Breuer, M. A. (1977). A class of min-cut placement algorithms. In Proceedings of the 14th Design Automation Conference, DAC ’77, page 284–290. IEEE Press.
Capanema, C., Silva, F., and Loureiro, A. (2022). Redes Neurais de Grafos no Contexto das Cidades Inteligentes, pages 135–176.
da Silva, D. N. R., Ziviani, A., and Porto, F. (2019). Aprendizado de máquina e inferência em Grafos de Conhecimento, pages 93–122.
Fang, J., Vardi, Y., and Zhang, C.-H. (2007). An iterative tomogravity algorithm for the estimation of network traffic, page 12–23. Institute of Mathematical Statistics.
Gao, Z., Fu, G., Ouyang, C., et al. (2019). edge2vec: Representation learning using edge semantics for biomedical knowledge discovery. BMC Bioinformatics 20.
Gong, L. and Cheng, Q. (2019). Exploiting edge features in graph neural networks. CoRR, abs/1809.02709.
Grover, A. and Leskovec, J. (2016). node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining, pages 855–864. ACM.
Hamilton, W., Ying, Z., and Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems, pages 1024–1034.
Hanin, B. (2018). Which neural net architectures give rise to exploding and vanishing gradients? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Hope, O. D. N. (2020). Generalisable data-driven routing using deep rl with gnns. Master’s thesis, University of Cambridge, Cambridge.
Jiang, X., Ji, P., and Li, S. (2019). Censnet: Convolution with edge-node switching in graph neural networks. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 2656–2662.
Jo, J., Baek, J., Lee, S., et al. (2021). Edge representation learning with hypergraphs. CoRR, abs/2106.15845.
Kim, J., Kim, T., Kim, S., and Yoo, C. D. (2019). Edge-labeling graph neural network for few-shot learning. CoRR, abs/1905.01436.
Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
Kipf, T. N. and Welling, M. (2016). Semi-Supervised Classification with Graph Convolutional Networks. arXiv preprint arXiv:1609.02907.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Luo, T. and Pan, D. Z. (2008). Dplace2.0: A stable and efficient analytical placement based on diffusion. In 2008 Asia and South Pacific Design Automation Conference, pages 346–351.
Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J., Songhori, E., Wang, S., Lee, Y.-J., Johnson, E., Pathak, O., Nazi, A., Pak, J., Tong, A., Srinivasa, K., Hang, W., Tuncer, E., Le, Q., Laudon, J., Ho, R., Carpenter, R., and Dean, J. (2021). A graph placement methodology for fast chip design. Nature, 594:207–212.
Peng, Y., Guo, J., and Yang, C. (2024). Learning resource allocation policy: Vertex-gnn or edge-gnn? IEEE Transactions on Machine Learning in Communications and Networking, 2:190–209.
Perozzi, B., Al-Rfou, R., and Skiena, S. (2014). Deepwalk: Online Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining, pages 701–710. ACM.
Qi, C. R., Su, H., Mo, K., and Guibas, L. J. (2016). Pointnet: Deep learning on point sets for 3d classification and segmentation. CoRR, abs/1612.00593.
Qiu, L., Jin, L., and Chai, L. (2023). Network traffic prediction based on spatio-temporal graph convolutional network. In 2023 42nd Chinese Control Conference (CCC), pages 8426–8431. IEEE.
Snell, J., Swersky, K., and Zemel, R. S. (2017). Prototypical networks for few-shot learning. CoRR, abs/1703.05175.
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., and Mei, Q. (2015). LINE: Large-Scale Information Network Embedding. In Proceedings of the 24th Int. Conference on World Wide Web, pages 1067–1077.
Tao, J., Cao, K., and Liu, T. (2023). Traffic matrix prediction based on cross aggregate gnn. In 2023 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech), pages 0234–0239. IEEE.
Teitelbaum, B., Hares, S., Dunn, L., Neilson, R., Narayan, V., and Reichmeyer, F. (1999). Internet2 qbone: building a testbed for differentiated services. IEEE Network, 13(5):8–16.
Tsitsulin, A., Palowitch, J., Perozzi, B., and Müller, E. (2023). Graph clustering with graph neural networks.
Valadarsky, A., Schapira, M., Shahaf, D., and Tamar, A. (2017). Learning to route. In Proceedings of the 16th ACM Workshop on Hot Topics in Networks, HotNets-XVI, page 185–191, New York, NY, USA. Association for Computing Machinery.
Veličković, P. (2023). Everything is connected: Graph neural networks. Current Opinion in Structural Biology, 79:102538.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph attention networks.
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. (2018). Dynamic graph cnn for learning on point clouds.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural networks? CoRR, abs/1810.00826.
Yang, Y. and Li, D. (2020). Nenn: Incorporate node and edge features in graph neural networks. In Asian Conference on Machine Learning, pages 593–608.
Yang, Z., Yang, L. T., Wang, H., Ren, B., and Yang, X. (2023). Bayesian tensor completion for network traffic data prediction. IEEE Network, 37(4):74–80.
Zheng, W., Li, Y., Hong, M., Zhao, G., and Fan, X. (2024). Network traffic matrix prediction with incomplete data via masked matrix modeling. Information Sciences, 657:119835.
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. (2020). Graph neural networks: A review of methods and applications. AI Open, 1:57–81.
Bandyopadhyay, S., Biswas, A., Murty, M. N., and Narayanam, R. (2019). Beyond node embedding: A direct unsupervised edge representation framework for homogeneous networks. CoRR, abs/1912.05140.
Barabási, A.-L. et al. (2016). Network Science. Cambridge University Press.
Bessadok, A., Mahjoub, M. A., and Rekik, I. (2021). Graph neural networks in network neuroscience. CoRR, abs/2106.03535.
Bielak, P., Kajdanowicz, T., and Chawla, N. V. (2020). Attre2vec: Unsupervised attributed edge representation learning. CoRR, abs/2012.14727.
Breuer, M. A. (1977). A class of min-cut placement algorithms. In Proceedings of the 14th Design Automation Conference, DAC ’77, page 284–290. IEEE Press.
Capanema, C., Silva, F., and Loureiro, A. (2022). Redes Neurais de Grafos no Contexto das Cidades Inteligentes, pages 135–176.
da Silva, D. N. R., Ziviani, A., and Porto, F. (2019). Aprendizado de máquina e inferência em Grafos de Conhecimento, pages 93–122.
Fang, J., Vardi, Y., and Zhang, C.-H. (2007). An iterative tomogravity algorithm for the estimation of network traffic, page 12–23. Institute of Mathematical Statistics.
Gao, Z., Fu, G., Ouyang, C., et al. (2019). edge2vec: Representation learning using edge semantics for biomedical knowledge discovery. BMC Bioinformatics 20.
Gong, L. and Cheng, Q. (2019). Exploiting edge features in graph neural networks. CoRR, abs/1809.02709.
Grover, A. and Leskovec, J. (2016). node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining, pages 855–864. ACM.
Hamilton, W., Ying, Z., and Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems, pages 1024–1034.
Hanin, B. (2018). Which neural net architectures give rise to exploding and vanishing gradients? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Hope, O. D. N. (2020). Generalisable data-driven routing using deep rl with gnns. Master’s thesis, University of Cambridge, Cambridge.
Jiang, X., Ji, P., and Li, S. (2019). Censnet: Convolution with edge-node switching in graph neural networks. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 2656–2662.
Jo, J., Baek, J., Lee, S., et al. (2021). Edge representation learning with hypergraphs. CoRR, abs/2106.15845.
Kim, J., Kim, T., Kim, S., and Yoo, C. D. (2019). Edge-labeling graph neural network for few-shot learning. CoRR, abs/1905.01436.
Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
Kipf, T. N. and Welling, M. (2016). Semi-Supervised Classification with Graph Convolutional Networks. arXiv preprint arXiv:1609.02907.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Luo, T. and Pan, D. Z. (2008). Dplace2.0: A stable and efficient analytical placement based on diffusion. In 2008 Asia and South Pacific Design Automation Conference, pages 346–351.
Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J., Songhori, E., Wang, S., Lee, Y.-J., Johnson, E., Pathak, O., Nazi, A., Pak, J., Tong, A., Srinivasa, K., Hang, W., Tuncer, E., Le, Q., Laudon, J., Ho, R., Carpenter, R., and Dean, J. (2021). A graph placement methodology for fast chip design. Nature, 594:207–212.
Peng, Y., Guo, J., and Yang, C. (2024). Learning resource allocation policy: Vertex-gnn or edge-gnn? IEEE Transactions on Machine Learning in Communications and Networking, 2:190–209.
Perozzi, B., Al-Rfou, R., and Skiena, S. (2014). Deepwalk: Online Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining, pages 701–710. ACM.
Qi, C. R., Su, H., Mo, K., and Guibas, L. J. (2016). Pointnet: Deep learning on point sets for 3d classification and segmentation. CoRR, abs/1612.00593.
Qiu, L., Jin, L., and Chai, L. (2023). Network traffic prediction based on spatio-temporal graph convolutional network. In 2023 42nd Chinese Control Conference (CCC), pages 8426–8431. IEEE.
Snell, J., Swersky, K., and Zemel, R. S. (2017). Prototypical networks for few-shot learning. CoRR, abs/1703.05175.
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., and Mei, Q. (2015). LINE: Large-Scale Information Network Embedding. In Proceedings of the 24th Int. Conference on World Wide Web, pages 1067–1077.
Tao, J., Cao, K., and Liu, T. (2023). Traffic matrix prediction based on cross aggregate gnn. In 2023 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech), pages 0234–0239. IEEE.
Teitelbaum, B., Hares, S., Dunn, L., Neilson, R., Narayan, V., and Reichmeyer, F. (1999). Internet2 qbone: building a testbed for differentiated services. IEEE Network, 13(5):8–16.
Tsitsulin, A., Palowitch, J., Perozzi, B., and Müller, E. (2023). Graph clustering with graph neural networks.
Valadarsky, A., Schapira, M., Shahaf, D., and Tamar, A. (2017). Learning to route. In Proceedings of the 16th ACM Workshop on Hot Topics in Networks, HotNets-XVI, page 185–191, New York, NY, USA. Association for Computing Machinery.
Veličković, P. (2023). Everything is connected: Graph neural networks. Current Opinion in Structural Biology, 79:102538.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph attention networks.
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. (2018). Dynamic graph cnn for learning on point clouds.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural networks? CoRR, abs/1810.00826.
Yang, Y. and Li, D. (2020). Nenn: Incorporate node and edge features in graph neural networks. In Asian Conference on Machine Learning, pages 593–608.
Yang, Z., Yang, L. T., Wang, H., Ren, B., and Yang, X. (2023). Bayesian tensor completion for network traffic data prediction. IEEE Network, 37(4):74–80.
Zheng, W., Li, Y., Hong, M., Zhao, G., and Fan, X. (2024). Network traffic matrix prediction with incomplete data via masked matrix modeling. Information Sciences, 657:119835.
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. (2020). Graph neural networks: A review of methods and applications. AI Open, 1:57–81.
Publicado
24/05/2024
Como Citar
ALMEIDA, Wagner; RAMOS, Fábio; BORGES, Alex V.; NACIF, José Augusto M.; SANTOS, Ricardo F. dos.
Explorando GNNs Sensíveis a Arestas para Previsão de Carga em uma Rede Backbone. In: WORKSHOP DE GERÊNCIA E OPERAÇÃO DE REDES E SERVIÇOS (WGRS), 29. , 2024, Niterói/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 84-97.
ISSN 2595-2722.
DOI: https://doi.org/10.5753/wgrs.2024.3246.
