Νευρωνικά Δίκτυα σε Γράφους
Creators: name: Νούσιας, Χρυσόστομος Ευάγγελου
Publisher: name: Aristotle University of Thessaloniki
Year: 2019
Subjects: Νευρωνικά Δίκτυα
Γράφοι
Μηχανική Μάθηση
Neural Networks
Graphs
Machine Learning

description: Σκοπός της διπλωματικής μεταπτυχιακής εργασίας είναι η διερεύνηση μεθόδων νευρωνικών δικτύων πάνω σε γράφους για την ανάπτυξη μοντέλων ταξινόμησης. Κίνητρο της εργασίας αποτέλεσε το πρόβλημα ταξινόμησης αντικειμένων τριών διαστάσεων κωδικοποιημένων ως γράφοι που φέρουν στους κόμβους τους επιπλέον πληροφορία. Η διερέυνηση αυτή χωρίζεται σε δύο μέρη: (ι) σε μία βιβλιογραφική έρευνα πάνω στις μεθόδους ταξινόμησης γράφων από τα πεδία των των νευρωνικών δικτύων, καθώς και των συναρτήσεων πυρήνα σε γράφους, (ιι) στην υλοποίηση και εφαρμογή των μεθόδων αυτών πάνω σε προβλήματα ταξινόμησης γνωστών σετ αναφοράς από το πεδίο της βιοπληροφορικής. Αρχικά, πραγματοποιείται μία εισαγωγή σε απαραίτητες έννοιες από τη θεωρία γράφων, της αναπαράστασής γράφων στο πεδίο της Γραμμικής Άλγεβρας καθώς και ενός εύρους ζητημάτων σχετιζόμενων με την θεώρησή τους στο πεδίο της Μηχανικής Μάθησης. Στη συνέχεια, διερευνώνται αλγόριθμοι ικανοί να προσδιορίσουν ένα μέτρο ομοιότητας μεταξύ γράφων. Οι αλγόριθμοι αυτοί βασίζονται στην έννοια της Αντιστοίχισης Γράφων με χαρακτηριστικότερη μέθοδο την Απόσταση Επεξεργασίας Γράφων. Λόγω των εγγενών περιορισμών αυτών των μεθόδων, ερευνάται η εφαρμογή συναρτήσεων πυρήνα πάνω σε γράφους, οι οποίες συνιστούν ένα αρκετά πλούσιο και ανεπτυγμένο πεδίο έρευνας με πετυχημένες εφαρμογές στην βιοπληροφορική και στη μελέτη κοινωνικών δικτύων. Οι εν λόγω μέθοδοι αν και αποδεικνύονται ιδιαίτερα πετυχημένες και με ένα στέρεο μαθηματικό υπόβαθρο, φαίνεται να έχουν κάποια εγγενή όρια στην αποτελεσματικότητά τους. Συνεπώς, διερευνάται η επέκταση μοντέλων Νευρωνικών Δικτύων πάνω σε γράφους, αναλύονται οι φασματικές και οι χωρικές προσεγγίσεις αλλά και αναδεικνύονται μοντέλα που ξεχωρίζουν λόγω του συνολικού τους χαρακτήρα, της ευκολίας υλοποίησής τους και της δυνατότητάς τους να πραγματοποιήσουν συμπερασμό σε γράφους ανεξαρτήτως τύπου ή μεγέθους. Ιδιαίτερο ενδιαφέρουν παρουσιάζει η εξέλιξη σύγκλισης μεταξύ των διαφόρων μεθόδων και μπορεί να ειπωθεί ότι οι εν λόγω αρχιτεκτονικές έχουν ξεπεράσει το στάδιο της διερεύνησης, μπορούν να εφαρμοστούν σε πραγματικά προβλήματα εφαρμογής αλλά και ταυτόχρονα φαίνεται να έχουν σημαντικά περιθώρια βελτίωσής. Τέλος, πραγματοποιούνται δύο υλοποιήσεις πάνω στο πρόβλημα ταξινόμησης γράφων, (ι) με την εφαρμογή διακεκριμένων μοντέλων από το πεδίο των πυρήνων γράφων, (ιι) με την ανάπτυξη αρχιτεκτονικών νευρωνικών δικτύων στα πλαίσια των ενοποιημένων μεθόδων, όπου δοκιμάζονται διαφορετικές αρχιτεκτονικές, η αποτελεσματικότητά τους καθώς και μέθοδοι βελτιστοποίησής τους. Οι λεπτομέρειες υλοποίησης περιγράφονται αναλυτικά και τα αποτελέσματα των μεθόδων αυτών δίνονται σε μορφή πινάκων. Η διπλωματική εργασία κλείνει με μία αποτίμηση των μεθόδων που χρησιμοποιήθηκαν, καθώς και την πρόταση μίας σειράς πιθανών θεμάτων μελλοντικής διερεύνησης, πάνω στα νευρωνικά δίκτυα σε γράφους.
description: Goal of this thesis project is a systematic investigation of methods for carrying classification tasks on graphs using neural networks. Motivating application of the thesis is the classification of 3-dimensional objects encoded as graphs that carry on their nodes local information. This investigation is divided in two parts: (i) a review of relative research in the subject of graph classification from the fields of Neural Networks on graphs as well as Graph Kernel methods, (ii) implementing and applying this kind of methods on classification tasks of well-known benchmark datasets from the field of Bioinformatics. At first, basic notions from Graph Theory are introduced as well as the connection of graphs to methods and aspects of Linear Algebra. In addition, a series of subjects that are deemed necessary for contextualizing graphs in a Machine Learning framework are investigated. Then, algorithms that are capable of defining similarity measures between graphs are investigated. These algorithms are based in the general notion of Graph Matching methods with the algorithm “Graph Edit Distance” to appear to be its most representative method. Because of inherent limitations of Graph Matching methods with respect to time and space complexity, the possible extension of kernel methods on graphs is investigated. Kernel methods constitute a rich and developed field of research with successful implementations in the fields of Bioinformatics and Social Networks. These methods which appear to be successful with a firm mathematical foundation appear to have some limits in their effectiveness. Afterwards, the extension of Graph Neural Networks on graphs is investigated. Spectral as well as spatial methods are analyzed and models are highlighted that stand out based on their overall character, their ease of implementation and their ability to run inference models on graphs regardless of graph type or size. Of special interest is the development and convergence of various different methods in unified methods on graphs, and it is safe to say that these methods have surpassed the stage of preliminary research, can be successfully applied in real world problems, but in the meantime have considerable room for improvement. Finally, classification tasks on graphs are carried out: (i) firstly by implementing standing out methods from the field of graph kernels (ii) by the implementation of Graph Neural Network architectures in the context of the unified spatial methods, where their expressiveness is tested as well as methods for optimizing them. The details of the implementation are thoroughly described and the results are given in the form of tables. The thesis project concludes with a summary of the proposed methods as well as a series of possible future research subjects in the field of neural networks on graphs.
description: Σε συνεργασία με: Λογιστικής και Χρηματοοικονομικής (Πανεπιστήμιο Μακεδονίας)