20.500.12556/RUL-184358 Pohitritev difuzijskega jedra grafa in metode NetLSD z uporabo podprostorov Krilova magistrsko delo Accelerating graph diffusion kernel and NetLSD method using Krylov subspaces Metode jedra so poleg nevronskih mrež vodilno orodje za strojno učenje na grafih. Za učenje na nivoju grafov se jedra opirajo na različne lastnosti, od soseščin vozlišč do najkrajših poti med naključnimi vozlišči, lahko pa tudi na difuzijsko jedro Laplaceove matrike, ki jo določa graf. Za velike grafe pa je natančen izračun difuzijskega jedra računsko prezahteven. V tem delu obravnavamo pohitritev izračuna z uporabo metod podprostorov Krilova, ki omogočajo učinkovite aproksimacije jedra za različne difuzijske čase. Te aproksimacije tvorijo približek metode NetLSD, ki vsak graf opiše z vektorjem na način, neodvisen od permutacije, merila in velikosti. Uporaba podprostorov Krilova omogoča kompromis med hitrostjo in natančnostjo tudi za zelo velike grafe, za katere izračun običajno ni izvedljiv. Alongside neural networks, kernel methods are a leading tool for machine learning on graphs. For graph-level learning tasks, kernel methods rely on various properties, ranging from node neighbourhoods to shortest paths between randomly selected nodes, and can also use the diffusion kernel of the graph's Laplacian matrix. However, for large graphs, exact computation of the diffusion kernel becomes computationally infeasible. In this work, we address the acceleration of this computation using Krylov subspace methods, which enable efficient approximations of the kernel for different diffusion times. These approximations form an approximation of the NetLSD method, which represents each graph with a vector that is invariant to permutation, scale, and size. The use of Krylov subspaces enables a trade-off between speed and accuracy, even for very large graphs, for which computation is typically not possible. metode jedra grafi podprostori Krilova NetLSD difuzijsko jedro kernel methods graphs Krylov subspaces NetLSD diffusion kernel true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2026-07-05 08:15:07 2026-07-05 08:15:16 2026-07-14 10:25:47 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.8 160580 283699715 21888.pdf 21888.pdf 1 C6A168F0B1F1940E2F2C2790D36CF509 97d8af8bb23396f9135fabe03aba1e1960ea12df03c6e343af37ac243e24e066 c68611aa-7838-11f1-9b0d-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=237039 Fakulteta za matematiko in fiziko 0 0 0