Methods of network embeddings and their applications

Makarov, Ilya (author), Šubelj, Lovro (mentor)

Many systems in the real world can be modeled as graphs or networks. One of the main goals of graph modeling is to formulate a general technique able to process structural data including relations between objects, which may also have some domain-specific information. In this thesis we deal with network representation learning, aiming to automatically learn low-dimensional vector features for the simplest graph motifs, such as nodes and edges. We search for a way that would enable efficiently solve machine learning problems on graphs, which include node classification, link prediction, node clustering, and graph visualization. We start with experimenting on embedding operators for pairs of nodes over existing node embedding models to efficiently solve the link prediction problem. We formulate several constraints on the embedding of pair of nodes based on their local proximity and validate our findings in classification and regression settings via various experiments on link prediction problem. We interpret the obtained results on the binary classification of missing links in co-authorship networks as a recommender system for scientific matchmaking on a real-world HSE University dataset. Taking the idea of joint node-edge embeddings, we develop new techniques of embedding nodes and edges under joint constraints via autoencoding graph and related to it Line graph. We incorporate two graph autoencoders for the graph and its Line graph while adding structural feature engineering, Laplacian regularization, and training the model with the help of $\beta$-masking on graph reconstruction task. The core feature of the model is in joint constraints on node and edge embeddings in the graph and its Line graph that help our model outperforming existing baselines for the node classification and the link prediction problems in unsupervised and semi-supervised settings. Following the growth of research in the field of network representation learning, we provide an extensive overview of existing network embedding techniques based on different taxonomies, such as model construction ideas, network data types, application settings, and stated open problems in network representation learning. Our survey is accompanied by state-of-the-art models' performance comparison on benchmark datasets and random graphs, thus shedding light on which model should be chosen for which network data under node classification, link prediction, node clustering, and visualization frameworks. Focusing on one of the open research questions on attributed network representations, we study the problem of constructing combined embedding models for networks attributed with text data and provide an in-depth analysis of fusion models for text and graph information on benchmark datasets considering node classification, link prediction, and graph visualization problems. We show that despite not having one fusion model to outperform all the others, there is an opportunity to choose a simple model based on text and network properties to be on par with state-of-the-art graph neural network models. Overall, the thesis covers the rapidly developing field of network representation learning and provides a comparison of modern models performance in benchmark settings. We provide novel models of network representation learning and partially answer the question, which models under which training setting and network dataset may perform better. We also show applications of network embedding models in machine learning, recommender systems, and information fusion.

• Language: English
• Keywords: graph embeddings, information fusion, node classification, link prediction, node clustering, community detection, graph visualization, network science
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-134243
• COBISS.SI-ID: 88478211
• Publication date in RUL: 03.01.2022

Secondary language

• Language: Slovenian
• Title: Metode vložitve omrežij in njihove aplikacije

Abstract

Številne realne sisteme je moč modelirati z grafi ali omrežji. Eden glavnih ciljev modeliranja grafov je razvoj splošnih tehnik, ki so sposobne obdelovati strukturne podatke, vključujoč relacije med entitetami, ki pa so lahko obogatene tudi z domensko specifičnimi podatki. V doktorski disertaciji se ukvarjamo z učenjem predstavitve omrežij, katere cilj je samodejno učenje nizkorazsežnih vektorskih značilk oziroma vložitev za najpreprostejše motive grafov, kot so vozlišča in povezave. S tem iščemo način, ki bi omogočil učinkovito reševanje problemov strojnega učenja na grafih, kar vključuje klasifikacijo vozlišč, napovedovanje povezav, razvrščanje vozlišč v skupine in vizualizacijo grafov. Pričnemo s primerjavo operatorjev za vložitve parov vozlišč, temelječ na obstoječih pristopih vložitve posameznih vozlišč z namenom učinkovitega reševanja problema napovedovanja povezav. Predlagamo več omejitev vložitve parov vozlišč glede na njihovo lokalno okolico in potrdimo svoje ugotovitve preko različnih eksperimentov napovedovanja povezav za primer klasifikacije in regresije. Rezultate binarne klasifikacije manjkajočih povezav v omrežjih soavtorstev tolmačimo kot priporočilni sistem za znanstveno sodelovanje nad resničnim naborom podatkov iz Univerze HSE. Z uporabo ideje o sočasni vložitvi vozlišč in povezav razvijemo nove pristope vložitve vozlišč in povezav pod skupnimi omejitvami nad grafom in z njim povezanim povezavnim grafom. Model vključuje dva samokodirnika za graf in njegov povezavni graf z dodano gradnjo strukturnih značilk, Laplaceovo regularizacijo in učenjem modela z uporabo $\beta$-maskiranja. Glavna značilnost modela je v skupnih omejitvah vložitve vozlišč in povezav v grafu in njegovem povezavnem grafu, s čimer model preseže uspešnost obstoječih pristopov klasifikacije vozlišč in napovedovanja povezav pri nenadzorovanem in delno-nadzorovanem učenju. Sledeč razmahu raziskav na področju učenja omrežnih predstavitev, disertacija poda obsežen pregled obstoječih pristopov vložitve omrežij preko različnih dimenzij, kot so različne tehnike gradnje modelov, vrste omrežnih podatkov, praktične aplikacije in primeri uporabe ter odprti problemi pri učenju omrežnih predstavitev. Pregled področja vključuje tudi primerjavo uspešnosti najsodobnejših pristopov na resničnih omrežjih in naključnih grafih. Slednje je v pomoč pri izbiri ustreznega modela za klasifikacijo vozlišč, napovedovanje povezav, razvrščanje vozlišč ali vizualizacijo izbranih omrežnih podatkov. Eno izmed odprtih vprašanj pri učenju omrežnih predstavitev predstavljajo omrežja s pripisanimi poljubnimi podatki o vozliščih. V disertaciji se osredotočimo na primer omrežij s pripisanimi besedilnimi podatki in podamo poglobljeno analizo modelov za združeno vložitev besedil in omrežij na različnih naborih podatkov klasifikacije vozlišč, napovedovanja povezav in vizualizacije grafov. Kljub temu da ne obstaja en združen model, ki bi presegel vse ostale, pa je moč izbrati preprost model, združujoč besedilne in omrežne podatke, ki je vsaj tako uspešen kot sodobni modeli grafovskih nevronskih mrež. Disertacija naslavlja hitro razvijajoče se področje učenja predstavitve omrežnih podatkov in podaja enotno primerjavo uspešnosti sodobnih modelov omrežne predstavitve. Predlagamo različne nove modele omrežne predstavitve in delno odgovorimo na vprašanje, kateri modeli so uspešnejši pri izbranih kriterijih učenja in vrsti omrežnih podatkov. Poleg tega predstavimo različne primere uporabe vložitve omrežnih podatkov v strojnem učenju, priporočilnih sistemih in združevanju podatkov.

• Keywords: vložitve grafov, združevanje informacij, klasifikacija vozlišč, napovedovanje povezav, razvrščanje vozlišč, odkrivanje skupnosti, vizualizacija grafov, omrežna znanost