Distributed Algorithms for Graph Embedding
Creators: name: Τουργαΐδης, Δημήτριος Παύλου
Publisher: name: Aristotle University of Thessaloniki
Year: 2022
Subjects: Ενσωμάτωση Γράφων
Μεγάλα δίκτυα
Κατανεμημένη Έκδοση του RandNE Άλγοριθμου
Graph Embedding
Large Networks
Distributed Version of RandNE Algorithm

description: Due to the continuously tendency to model domains in a network format, network representation learning (NRL) is a field where a lot of research has been carried out the recent years. Programmatically, a network is preserved in an adjacency matrix that preserves the neighbors for each network’s node. The size of the adjacency matrix is N × N, where N the number of nodes in a network. For large networks, utilizing the vectors of the network’s nodes preserved by the adjacency matrix is unfeasible in order to train machine learning models to solve various network analytic tasks. The reason is the size of the vectors, which for large networks is so big that makes practi- cally the training of the machine learning models unfeasible time-wise. The objective of NRL is to map the original representation space of a network (adjacency matrix) to a latent low-dimensional representation. The charac- teristics of the new node vectors (node embeddings) are 1) the vectors’ size is d, where d N, making the training of machine learning models time-wise feasible and 2) the vectors try to capture as much as possible characteristics of the original network to make the node embeddings as efficient as possible in regard to the machine learning models training. A lot of NRL methods have been developed and presented in the literature, which doesn’t respect the scaling fact though, making them inapplicable in large networks. In 2018, Zhang and his colleagues presented RandNE, “A novel and simple billion- scale network embedding method based on high-order proximity preserved random projection”. RandNE showed exceptional time-wise performance, but the provided implementation by [1] is 1) centralized and 2) was tested on small networks. Consequently, the objective of this thesis is the develop a distributed version of the RandNE method utilizing the Apache Spark frame- work, and examine its time-wise behavior. The implementation is available at (https://github.com/Tourgito/RandNE_Distributed). The results showed that the provided implementation produces feasible execution times on large networks. In case of a network with 334.863 nodes and 925.872 edges, a few minutes were enough in order the implementation to be executed. Except from the main objective of this thesis, this thesis is also a great entry-point for someone who is unfamiliar with the NRL field, since it covers fundamental concepts, notations and definitions of the field, as well as important NRL methods that have been developed in the literature
description: Λόγω της συνεχούς τάσης για μοντελοποίηση τομέων σε μορφή δικτύου, η εκμάθηση αναπαράστασης δικτύου είναι ένα πεδίο πάνω στο οποίο έχει πραγματο- ποιηθεί πολλή έρευνα τα τελευταία χρόνια. Προγραμματιστικά, ένα δίκτυο διατη- ρείται σε έναν πίνακα γειτνίασης που διατηρεί τους γείτονες για κάθε κόμβο του δικτύου. Το μέγεθος του πίνακα γειτνίασης είναι N × N, όπου N ο αριθμός των κόμβων σε ένα δίκτυο. Για μεγάλα δίκτυα, η χρήση των διανυσμάτων των κόμβων του δικτύου που διατηρούνται από τον πίνακα γειτνίασης, δεν είναι πρακτικά εφικτό να χρησιμοποιηθούν για την εκπαίδευση μοντέλων μηχανικής μάθησης, για την επίλυση διαφόρων αναλυτικών εργασιών δικτύου. Ο λόγος είναι το μέγεθος των διανυσμάτων, το οποίο για μεγάλα δίκτυα είναι τόσο μεγάλο που καθιστά πρακτικά ανέφικτη την εκπαίδευση των μοντέλων μηχανικής μάθησης, χρονικά. Ο στόχος της εκμάθηση αναπαράστασης δικτύου είναι να μετασχηματίσει τον αρχικό χώρο αναπαράστασης ενός δικτύου (πίνακας γειτνίασης) σε μια λανθάνων αναπαράσταση χαμηλών διαστάσεων. Τα χαρακτηριστικά των νέων διανυσμάτων των κόμβων είναι 1) το μέγεθος τους είναι d, όπου d N, καθιστώντας την εκπαίδευση των μοντέλων μηχανικής μάθησης χρονικά εφικτή και 2) προσπαθούν να συλλάβουν όσο το δυνατόν περισσότερα στοιχεία του αρχικού δικτύου, ώστε να είναι όσο το δυνατόν πιο αποτελεσματικά σε σχέση με την εκπαίδευση μοντέλων μηχανικής μάθησης. Πολλές μέθοδοι έχουν αναπτυχθεί και παρουσιαστεί στη βιβλιογραφία για το πεδίο αυτό, οι οποίες όμως δεν αντιμετωπίζουν επιτυχώς το θέμα της κλιμάκωσης, δηλαδή να μπορούν να εφαρμο- στούν σε μεγάλα δίκτυα, καθιστώντας τις ανεφάρμοστες σε τέτοιου τύπου δίκτυα. Το 2018, ο Zhang και οι συνεργάτες του παρουσίασαν την μέθοδο RandNE, “a novel and simple billion-scale network embedding method based on high-order proximity preserved random projection”. Η μέθοδος RandNE έδειξε εξαιρετική απόδοση από άποψη χρόνου, αλλά η παρεχόμενη υλοποίηση από το [1] είναι 1) υλοποιημένη ώστε να εκτελείται μόνο χρησιμοποιώντας έναν πυρήνα και 2) εξετάστηκε σε μικρά δίκτυα. Κατά συνέπεια, στόχος αυτής της διπλωματικής εργασίας είναι η ανάπτυξη μιας κατανεμημένης έκδοσης της μεθόδου RandNE, χρησιμοποιώντας το λογισμικό Apache Spark και η εξέταση της συμπεριφοράς της από άποψη χρόνου και κλιμάκωσης. Η υλοποίηση είναι διαθέσιμη στον ακόλουθο σύνδεσμο (https://github.com/Tourgito/RandNE_Distributed). Τα αποτελέσματα έδειξαν ότι η παρεχόμενη υλοποίηση παράγει αποδεκτούς χρόνους εκτέλεσης σε μεγάλα δίκτυα. Σε περίπτωση δικτύου με 334.863 κόμβους και 925.872 ακμές, λίγα λεπτά ήταν αρκετά για να εκτελεστεί η υλοποίηση. Εκτός από τον κύριο στόχο αυτής της διπλωματικής εργασίας, επιπλέον αποτελεί ένα εξαιρετικό σημείο εισόδου για κάποιον που δεν είναι εξοικειωμένος με το συγκεκριμένο πεδίο, καθώς καλύπτει θεμελιώδεις έννοιες και ορισμούς, και παρουσιάζει σημαντικές μεθόδους που έχουν αναπτυχθεί μέχρι στιγμής στη βιβλιογραφία στο πεδίο αυτό.