Reordering graphs for node embedding

In today’s interconnected world, graphs are widely used to model complex relationshipsand structures across various domains, from social networks and transportationsystems to biological networks and recommendation systems. However, the high dimensionalityand intricate connectivity of these graphs pose significant challengesfor analysis and processing. Node embedding techniques have emerged as powerfultools to address these challenges by transforming graph nodes into low-dimensionalvectors while preserving the inherent structural properties and relationships of theoriginal graph. Despite their effectiveness, node embedding can be an expensiveprocess, particularly for large-scale graphs, due to the substantial computationalresources and time required. This thesis aims to improve node embedding frameworksthat utilize GPUs by reordering matrices that represent graphs. We proposea probabilistic part-skipping strategy on reordered graphs that eliminates the overheadcreated by moving parts of the graph into and out of the GPU memory andtherefore speeding up the process significantly. The resulting embeddings performas well as embeddings learned on a randomly ordered graph and in some casesperform significantly better on link prediction tasks. We also present link predictionresults after reordering on various graphs obtained from SuiteSparse and TheNetwork Repository. The results show that the class of reordering algorithms thatemphasize the connectivity structure and community information found within thegraphs improve the link prediction results regardless of the graph type used.