Multi-Head Attention and Dual Message-Passing Neural Network for Neural Algorithmic Reasoning
Resumo
Neural Algorithmic Reasoning (NAR) is the research area that aims to build artificial neural networks that can mimic (classical) algorithms, reproducing intermediary steps from their execution traces. This paper introduces MHAD-MPNN (Multi-Head Attention and Dual Message-Passing Neural Network), a Triplet-GMPNN-inspired method that integrates feature representations with a multi-head attention memory block and a streamlined message-passing procedure. Our solution achieved results comparable to the current state-of-the-art. Furthermore, we conducted a comprehensive ablation study to evaluate key parameter modifications, thereby deepening our understanding of Neural Algorithmic Reasoning.
Referências
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press, 1 edition.
Back De Luca, A. and Fountoulakis, K. (2024). Simulation of graph algorithms with looped transformers. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F., editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 2319–2363. PMLR.
Bohde, M., Liu, M., Saxton, A., and Ji, S. (2024). On the markov property of neural algorithmic reasoning: Analyses and methods. In The Twelfth International Conference on Learning Representations.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
Diao, C. and Loynd, R. (2023). Relational attention: Generalizing transformers for graphstructured tasks. In The Eleventh International Conference on Learning Representations.
Dudzik, A. J. and Veličković, P. (2022). Graph neural networks are dynamic programmers. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 20635–20647. Curran Associates, Inc.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 1263–1272. JMLR.org.
Graves, A., Wayne, G., and Danihelka, I. (2014). Neural turing machines.
Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., and Battaglia, P. W. (2018). Relational inductive bias for physical construction in humans and machines. In Proceedings of the 40th Annual Conference of the Cognitive Science Society, Austin, TX.
Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., Dudzik, A. J., Bošnjak, M., Vitvitskyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, C., and Veličković, P. (2022). A generalist neural algorithmic learner. In The First Learning on Graphs Conference.
Jain, R., VeliČkoviĆ, P., and Liò, P. (2023). Neural priority queues for graph neural networks.
Jung, Y. and Ahn, S. (2023). Triplet edge attention for algorithmic reasoning. In The Second Learning on Graphs Conference.
Li, H., Peng, C., Xu, C., and Yang, Z. (2024). Open-book neural algorithmic reasoning. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C., editors, Advances in Neural Information Processing Systems, volume 37, pages 9819–9836. Curran Associates, Inc.
Mahdavi, S., Swersky, K., Kipf, T., Hashemi, M., Thrampoulidis, C., and Liao, R. (2023). Towards better out-of-distribution generalization of neural algorithmic reasoning tasks. Transactions on Machine Learning Research.
Mirjanic, V. V., Pascanu, R., and Veličković, P. (2024). Latent space representations of neural algorithmic reasoners. In Villar, S. and Chamberlain, B., editors, Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 10:1–10:24. PMLR.
Rahemi, N. and Mosavi, M. R. (2021). Positioning accuracy improvement in high-speed gps receivers using sequential extended kalman filter. IET Signal Processing, 15(4):251–264.
Reed, S. and de Freitas, N. (2016). Neural programmer-interpreters.
Robert Sedgewick, K. W. (2011). Algorithms, 4th Edition: Essential Information about Algorithms and Data Structures. Addison-Wesley.
Rodionov, G. and Prokhorenkova, L. (2023). Neural algorithmic reasoning without intermediate supervision. In Thirty-seventh Conference on Neural Information Processing Systems.
Sirish Kumar, P. and Srilatha Indira Dutt, V. (2020). The global positioning system: Popular accuracy measures. Materials Today: Proceedings, 33:4797–4801. International Conference on Nanotechnology: Ideas, Innovation and Industries.
Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. (2022). The CLRS algorithmic reasoning benchmark. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22084–22102. PMLR.
Veličković, P. and Blundell, C. (2021). Neural algorithmic reasoning. Patterns, 2(7).
Veličković, P., Buesing, L., Overlan, M., Pascanu, R., Vinyals, O., and Blundell, C. (2020). Pointer graph networks. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 2232–2244. Curran Associates, Inc.
Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. (2020). Neural execution of graph algorithms. In International Conference on Learning Representations.
Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer networks. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Xu, K. and Veličković, P. (2024). Recurrent aggregators in neural algorithmic reasoning. In The Third Learning on Graphs Conference.
Xu, K., Zhang, M., Li, J., Du, S. S., Kawarabayashi, K.-I., and Jegelka, S. (2021). How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations.
Yan, Y., Swersky, K., Koutra, D., Ranganathan, P., and Hashemi, M. (2020). Neural execution engines: Learning to execute subroutines. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 17298–17308. Curran Associates, Inc.
Zhang, Z. and Fink, O. (2026). Algorithm-informed graph neural networks for leakage detection and localization in water distribution networks. Reliability Engineering & System Safety, 265:111494.
Back De Luca, A. and Fountoulakis, K. (2024). Simulation of graph algorithms with looped transformers. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F., editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 2319–2363. PMLR.
Bohde, M., Liu, M., Saxton, A., and Ji, S. (2024). On the markov property of neural algorithmic reasoning: Analyses and methods. In The Twelfth International Conference on Learning Representations.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
Diao, C. and Loynd, R. (2023). Relational attention: Generalizing transformers for graphstructured tasks. In The Eleventh International Conference on Learning Representations.
Dudzik, A. J. and Veličković, P. (2022). Graph neural networks are dynamic programmers. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 20635–20647. Curran Associates, Inc.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 1263–1272. JMLR.org.
Graves, A., Wayne, G., and Danihelka, I. (2014). Neural turing machines.
Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., and Battaglia, P. W. (2018). Relational inductive bias for physical construction in humans and machines. In Proceedings of the 40th Annual Conference of the Cognitive Science Society, Austin, TX.
Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., Dudzik, A. J., Bošnjak, M., Vitvitskyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, C., and Veličković, P. (2022). A generalist neural algorithmic learner. In The First Learning on Graphs Conference.
Jain, R., VeliČkoviĆ, P., and Liò, P. (2023). Neural priority queues for graph neural networks.
Jung, Y. and Ahn, S. (2023). Triplet edge attention for algorithmic reasoning. In The Second Learning on Graphs Conference.
Li, H., Peng, C., Xu, C., and Yang, Z. (2024). Open-book neural algorithmic reasoning. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C., editors, Advances in Neural Information Processing Systems, volume 37, pages 9819–9836. Curran Associates, Inc.
Mahdavi, S., Swersky, K., Kipf, T., Hashemi, M., Thrampoulidis, C., and Liao, R. (2023). Towards better out-of-distribution generalization of neural algorithmic reasoning tasks. Transactions on Machine Learning Research.
Mirjanic, V. V., Pascanu, R., and Veličković, P. (2024). Latent space representations of neural algorithmic reasoners. In Villar, S. and Chamberlain, B., editors, Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 10:1–10:24. PMLR.
Rahemi, N. and Mosavi, M. R. (2021). Positioning accuracy improvement in high-speed gps receivers using sequential extended kalman filter. IET Signal Processing, 15(4):251–264.
Reed, S. and de Freitas, N. (2016). Neural programmer-interpreters.
Robert Sedgewick, K. W. (2011). Algorithms, 4th Edition: Essential Information about Algorithms and Data Structures. Addison-Wesley.
Rodionov, G. and Prokhorenkova, L. (2023). Neural algorithmic reasoning without intermediate supervision. In Thirty-seventh Conference on Neural Information Processing Systems.
Sirish Kumar, P. and Srilatha Indira Dutt, V. (2020). The global positioning system: Popular accuracy measures. Materials Today: Proceedings, 33:4797–4801. International Conference on Nanotechnology: Ideas, Innovation and Industries.
Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. (2022). The CLRS algorithmic reasoning benchmark. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22084–22102. PMLR.
Veličković, P. and Blundell, C. (2021). Neural algorithmic reasoning. Patterns, 2(7).
Veličković, P., Buesing, L., Overlan, M., Pascanu, R., Vinyals, O., and Blundell, C. (2020). Pointer graph networks. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 2232–2244. Curran Associates, Inc.
Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. (2020). Neural execution of graph algorithms. In International Conference on Learning Representations.
Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer networks. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Xu, K. and Veličković, P. (2024). Recurrent aggregators in neural algorithmic reasoning. In The Third Learning on Graphs Conference.
Xu, K., Zhang, M., Li, J., Du, S. S., Kawarabayashi, K.-I., and Jegelka, S. (2021). How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations.
Yan, Y., Swersky, K., Koutra, D., Ranganathan, P., and Hashemi, M. (2020). Neural execution engines: Learning to execute subroutines. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 17298–17308. Curran Associates, Inc.
Zhang, Z. and Fink, O. (2026). Algorithm-informed graph neural networks for leakage detection and localization in water distribution networks. Reliability Engineering & System Safety, 265:111494.
Publicado
19/10/2026
Como Citar
REIS, Felipe A. L.; PATROCÍNIO JR., Zenilton K. G. do.
Multi-Head Attention and Dual Message-Passing Neural Network for Neural Algorithmic Reasoning. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 23. , 2026, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 409-420.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2026.30002.
