MSc.Thesis Defense:Berkay Demireller

REORDERING GRAPHS FOR NODE EMBEDDING

Berkay Demireller
Computer Science and Engineering, MSc. Thesis , 2024

Thesis Jury

Assoc. Prof. Kamer Kaya (Thesis Advisor)
Prof. Hüsnü Yenigün
Assoc. Prof. Didem Unat

Date & Time: 19th, July 2024 –  3:30 PM

Place: FENS L058

Keywords : Graphs, Matrix Reordering, Node Embedding, GPU

Abstract

In today's interconnected world, graphs are widely used to model complex relationships and structures across various domains, from social networks and transportation systems to biological networks and recommendation systems. However, the high dimensionality and intricate connectivity of these graphs pose significant challenges for analysis and processing. Node embedding techniques have emerged as powerful tools to address these challenges by transforming graph nodes into low-dimensional vectors while preserving the inherent structural properties and relationships of the original graph. Despite their effectiveness, node embedding can be an expensive process, particularly for large-scale graphs, due to the substantial computational resources and time required. This thesis aims to improve node embedding frameworks that utilize GPUs by reordering matrices that represent graphs. We propose a probabilistic part-skipping strategy on reordered graphs that eliminates the overhead created by moving parts of the graph into and out of the GPU memory and therefore speeding up the process significantly. The resulting embeddings perform as well as embeddings learned on a randomly ordered graph and in some cases perform significantly better on link prediction tasks. We also present link prediction results after reordering on various graphs obtained from \textit{SuiteSparse} and \textit{The Network Repository}. The results show that the class of reordering algorithms that emphasize the connectivity structure and community information found within the graphs improve the link prediction results regardless of the graph type used.