Bakalárska práca

Samuel Varchol

Názov práce

Graph neural networks for Algebraic Graph Theory

Školiteľ

Mgr. Ján Pastorek

Zadanie

Anotácia

Graph neural networks (GNNs) are neural network architectures used for machine learning on graphs. Among others, graph neural networks are one of the main building blocks of AlphaFold, an artificial intelligence program developed by Google's DeepMind for solving the protein folding problem in biology.

Cieľ práce

The goal is to investigate potential applications of graph neural networks (GNNs) to problems in algebraic graph theory. The student will have the opportunity to engage with the state-of-art research in machine learning and algebraic graph theory and contribute to the field by generating new record graphs and training GNNs to predict algebraic properties.

Zoznam zdrojov a odkazov

Knihy

  • Wu, L., Cui, P., Pei, J., & Zhao, L. (2022). Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Nature Singapore. DOI: 10.1007/978-981-16-6054-2
  • Diestel, R. (2017). Graph Theory (Graduate Texts in Mathematics, Vol. 173). Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-53622-3
  • West, D.B. (2001). Introduction to Graph Theory. Prentice Hall.
  • Biggs, N. (1993). Algebraic Graph Theory (Cambridge Mathematical Library). Cambridge University Press.
  • Trudeau, R.J. (1993). Introduction to Graph Theory. Dover Publications.
  • Bollobás, B. (1985). Random Graphs (Cambridge Studies in Advanced Mathematics). Academic Press.
  • Bondy, J.A., & Murty, U.S.R. (2008). Graph Theory (Graduate Texts in Mathematics, Vol. 244, 2nd ed.). Springer.
  • Irniger, C.A.M. (2005). Graph Matching: Filtering Databases of Graphs Using Machine Learning Techniques. AKA.
  • Chartrand, G., Jordon, H., Vatter, V., & Zhang, P. (2024). Graphs and Digraphs (Textbooks in Mathematics Series, 7th ed.). CRC Press LLC.

Články a vedecké práce

  • Grohe, M. (2022). The Logic of Graph Neural Networks. arXiv. arXiv:2104.14624
  • Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020). Graph neural networks: A review of methods and applications. AI Open, 1, 57-81. DOI: 10.1016/j.aiopen.2021.01.001
  • Shervashidze, N., Schweitzer, P., Leeuwen, E.J.V., Mehlhorn, K., & Borgwardt, K.M. (2011). Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research, 12(77), 2539-2561. Link
  • Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., & Grohe, M. (2019). Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1), 4602-4609. DOI: 10.1609/aaai.v33i01.33014602
  • Huang, N.T., & Villar, S. (2021). A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants. ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing, 8533-8537. DOI: 10.1109/ICASSP39728.2021.9413523
  • Weisfeiler, B., & Lehman, A.A. (1968). A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Technicheskaya Informatsia, 2(9), 12-16.
  • Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks? arXiv. arXiv:1810.00826
  • Jajcay, R., Jajcayova, T., Szakács, N., & Szendrei, M.B. (2020). Inverse monoids of partial graph automorphisms. arXiv. arXiv:1809.04422
  • Paolino, R., Maskey, S., Welke, P., & Kutyniok, G. (2024). Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning. arXiv. arXiv:2403.13749
  • Coolsaet, K., D'hondt, S., & Goedgebeur, J. (2023). House of Graphs 2.0: A database of interesting graphs and more. Discrete Applied Mathematics, 325, 97-107. https://houseofgraphs.org
  • McKay, B.D., & Piperno, A. (2014). Practical graph isomorphism, II. Journal of Symbolic Computation, 60, 94-112.
  • Kimble, R., Schwenk, A., & Stockmeyer, P. (1981). Pseudosimilar vertices in a graph. Journal of Graph Theory, 5, 171-181.
  • Godsil, C.D., & Kocay, W.L. (1982). Constructing graphs with pairs of pseudo-similar vertices. Journal of Combinatorial Theory, Series B, 32(4), 392-399.
  • Baird, H.S., & Cho, Y.E. (1975). An artwork design verification system. Proceedings of the 12th Design Automation Conference, 414-420.

Software nástroje a knižnice

  • Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., & Dahl, G.E. (2017). Neural Message Passing for Quantum Chemistry. arXiv. arXiv:1704.01212
  • You, J., Gomes-Selman, J., Ying, R., & Leskovec, J. (2021). Identity-aware Graph Neural Networks. arXiv. arXiv:2101.10320
  • Fey, M., Sunil, J., Nitta, A., Puri, R., Shah, M., Stojanovič, B., Bendias, R., Barghi, A., Kocijan, V., Zhang, Z., He, X., Lenssen, J.E., & Leskovec, J. (2025). PyG 2.0: Scalable Learning on Real World Graphs. arXiv. arXiv:2507.16991
  • Akiba, T., Sano, S., Yanase, T., Ohta, T., & Koyama, M. (2019). Optuna: A Next-generation Hyperparameter Optimization Framework. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  • Hagberg, A.A., Schult, D.A., & Swart, P.J. (2008). Exploring Network Structure, Dynamics, and Function using NetworkX. Proceedings of the 7th Python in Science Conference, 11–15.
  • Loshchilov, I., & Hutter, F. (2019). Decoupled Weight Decay Regularization. arXiv. arXiv:1711.05101
  • Kingma, D.P., & Ba, J. (2017). Adam: A Method for Stochastic Optimization. arXiv. arXiv:1412.6980

Materiály

Týždenný denník

Týždeň 1 (16.2.2026 - 22.2.2026)

Vytvorenie webstránky a jej úvodného obsahu. Základ článku na ŠVK.

Týždeň 2 (23.2.2026 - 1.3.2026)

Analýza výsledkov z experimentov so základným GIN modelom. Počiatočný experiment s grafovým transformerom.

Týždeň 3 (2.3.2026 - 8.3.2026)

Pokračovanie článku na ŠVK. Štúdium modelu GraphGPS a jeho potenciálneho využitia. Úprava datasetu s ťažšími príkladmi.

Týždeň 4 (9.3.2026 - 15.3.2026)

Finálny dataset, pretrénovanie všetkých modelov. Spracovanie výsledkov pre článok. Dopisovanie článku na ŠVK.

Týždeň 5 (16.3.2026 - 22.3.2026)

Revízia článku na ŠVK

Týždeň 6 (23.3.2026 - 29.3.2026)

Finálna verzia ŠVK. Písanie 1. kapitoly práce.