Vertex Similarity in Graphs using Feature Learning
Authors
Carstens, Bjarke Thorn ; Jensen, Mads Riis ; Spaniel, Mathias Friis ; Hermansen, Anders
Term
4. term
Education
Publication year
2017
Abstract
This thesis investigates how to measure vertex similarity in graphs using feature learning. We conduct a detailed study of node2vec, which learns node embeddings via biased random walks, and assess the authors’ claim that parameters p and q can control whether the model captures structural similarity or proximity. We identify a key limitation: node2vec ignores node attributes and edge types. To address this, we propose extensions that represent walks as sequences of feature vectors, enabling the use of both node and edge information in multi-relational graphs. In exploratory analysis we show that node2vec can distinguish roles such as hubs, periphery, and mainstream, but that p and q have little influence on the type of similarity recovered; instead, walk length and the number of walks matter more. Incorporating attributes and edge relations makes semantic similarity discoverable. We evaluate our extensions on real networks through multiclass and multilabel classification using macro and micro F1-scores. The results show improvements over node2vec on multiclass tasks, while multilabel performance is mixed across datasets.
Denne afhandling undersøger, hvordan knudelighed i grafer kan måles ved hjælp af feature learning. Vi foretager en dybdegående analyse af node2vec, der lærer indlejringer af knuder via biaisede tilfældige vandringer, og vurderer forfatternes påstand om, at parametrene p og q kan styre, om modellen fanger strukturel lighed eller nærhed. Vi peger på en vigtig begrænsning: node2vec ignorerer knudeattributter og kanttyper. Som løsning foreslår vi udvidelser, hvor vandringer repræsenteres som sekvenser af featurevektorer, så både knude- og kantinformation i multirelationelle grafer kan udnyttes. I en eksplorativ analyse viser vi, at node2vec kan skelne roller som hub, periferi og mainstream, men at p og q kun i ringe grad påvirker, hvilken lighedstype der findes; længden af vandringer og antallet af vandringer har større betydning. Når attributter og kantrelationer inddrages, bliver det muligt at finde semantisk lighed. Vi evaluerer vores udvidelser på virkelige netværk via multiclass og multilabel klassifikation målt med macro og micro F1-score. Resultaterne viser forbedringer i forhold til node2vec på multiclass-opgaver, mens multilabel-resultaterne er blandede på tværs af datasæt.
[This apstract has been generated with the help of AI directly from the project full text]