Machine learning on graphs
Authors: Νικολέντζος Ιωάννης 
Published: September 2021

Τα γραφήματα είναι δομές που έχουν μελετηθεί ευρέως και που χρησιμοποιούνται για να μοντελοποιήσουν οντότητες και τις μεταξύ τους σχέσεις. Τα τελευταία χρόνια, οι αναπαραστάσεις δεδομένων ως γραφήματα έχουν διαδοθεί σε μεγάλο βαθμό και χρησιμοποιούνται σε πολλές εφαρμογές. Για παράδειγμα, στην υπολογιστική χημεία, τα γραφήματα χρησιμοποιούνται για την αναπαράσταση μορίων, ενώ στην επεξεργασία φυσικής γλώσσας χρησιμοποιούνται για την αναπαράσταση κειμένων. Σε πολλές εφαρμογές, είναι απαραίτητο να εκτελέσουμε εργασίες μηχανικής μάθησης πάνω σε γραφήματα όπως για παράδειγμα να ταξινομήσουμε γραφήματα ή να ομαδοποιήσουμε γραφήματα. Τα τελευταία χρόνια, το πρόβλημα της ταξινόμησης μεγάλων συλλογών γραφημάτων έχει αποκτήσει ιδιαίτερη σημασία μιάς και αποτελεί τη βάση αρκετών σημαντικών εφαρμογών. Σκοπός της παρούσας διατριβής είναι να μελετήσει και να αντιμετωπίσει το πρόβλημα της ταξινόμησης γραφημάτων, εστιάζοντας τόσο στο σχεδιασμό νέων αλγορίθμων και εργαλείων, όσο και στην εφαρμογή του πρβλήματος σε τομείς όπου κυριαρχούν παραδοσιακά διαφορετικές προσεγγίσεις. Στο πρώτο μέρος της διατριβής παρουσιάζονται δύο νέοι αλγόριθμοι που είναι ικανοί να συγκρίνουν γραφήματα με βάση τις καθολικές τους ιδιότητες.Τα τελευταία χρόνια, η έρευνα στην ταξινόμηση γραφημάτων έχει επικεντρωθεί κυρίως στους πυρήνες γραφημάτων (graph kernels). Ειδικότερα, πυρήνας είναι μια συνάρτηση που λαμβάνει ως είσοδο δύο αντικείμενα και επιστρέφει έναν αριθμό, με την ιδιότητα ότι η συνάρτηση είναι συμμετρική και θετικά ημιορισμένη. Οι πυρήνες μπορούν να θεωρηθούν ως μέτρα ομοιότητας μεταξύ δυο αντικειμένων. Οι πυρήνες γραφημάτων είναι συναρτήσεις πυρήνα που μετρούν την ομοιότητα μεταξύ ζευγαριών γραφημάτων. Η πιο αξιοσημείωτη ιδιότητα αυτών των μεθόδων είναι ότι επιτρέπουν σε ορισμένους αλγορίθμους, όπως οι Μηχανές Διανυσμάτων Υποστήριξης (Support Vector Machines), να εργάζονται απευθείας πάνω σε γραφήματα, χωρίς να απαιτείται προηγουμένως να αναπαραστήσουν τα δεδομένα ρητά μέσω διανυσμάτων χαρακτηριστικών. Οι περισσότεροι υπάρχοντες πυρήνες γραφημάτων επικεντρώνονται σε τοπικές ιδιότητες των γραφημάτων και αγνοούν την καθολική τους δομή. Για να αντιμετωπίσουμε αυτό το πρόβλημα, προτείνουμε τη σύγκριση γραφημάτων βάσει των καθολικών τους ιδιοτήτων, όπως αυτά εκφράζονται από τα ιδιοδιανύσματα των πινάκων γειτνίασής τους. Συγκεκριμένα, παρουσιάζουμε δύο αλγορίθμους για τη σύγκριση γραφημάτων οι οποίοι μπορούν να εφαρμοστούν σε γραφήματα των οποίων οι κόμβοι είτε έχουν ετικέτες ή όχι. Οι αλγόριθμοι αυτοί αναπαριστούν κάθε γράφημα ως ένα σύνολο διανυσμάτων τα οποία αντιστοιχούν στις διανυσματικές αναπαραστάσεις των κόμβων τους. Ο πρώτος αλγόριθμος χρησιμοποιεί τη μετρική Earth Mover's Distance για να υπολογίσει την ομοιότητα μεταξύ δύο γραφημάτων. Ωστόσο, το μέτρο ομοιότητας που προκύπτει δεν αντιστοιχεί σε έγκυρη συνάρτηση πυρήνα. Για να αντιμετωπίσουμε αυτό το πρόβλημα, χρησιμοποιούμε μια παραλλαγή των Μηχανών Διανυσμάτων Υποστήριξης για ταξινόμηση όταν η συνάρτηση πυρήνα δεν είναι έγκυρη. Σε αντίθεση με τον πρώτο αλγόριθμο, ο δεύτερος είναι μια έγκυρη συνάρτηση πυρήνα και βασίζεται στον υπάρχων πυρήνα Pyramid Match Kernel. Συγκεκριμένα, ο αλγόριθμος βρίσκει μια κατά προσέγγιση αντιστοιχία μεταξύ των συνόλων διανυσμάτων των δύο γραφημάτων. Οι προτεινόμενες μέθοδοι αξιολογούνται στην ταξινόμηση γραφημάτων όπου χρησιμοποιούνται διάφορα σύνολα δεδομένων από τα πεδία της υπολογιστικής χημείας και της υπολογιστικής βιολογίας. Η απόδοση των προτεινόμενων μεθόδων συγκρίνεται με την απόδοση μεθόδων που βρίσκονται στην αιχμή της τεχνολογίας. Τα αποτελέσματα που προκύπτουν δείχνουν ότι οι προτεινόμενοι αλγόριθμοι σε γενικές γραμμές ξεπερνούν σε απόδοση τις ανταγωνιστικές μεθόδους, ενώ η πολυπλοκότητα του χρόνου υπολογισμού τους παραμένει πολύ ελκυστική. Στο δεύτερο μέρος, εστιάζουμε και πάλι στο σχεδιασμό νέων αλγορίθμων/εργαλείων για το πρόβλημα της ομοιότητας και της ταξινόμησης γραφημάτων. Συγκεκριμένα, ορίζουμε ένα γενικό πλαίσιο για τη βελτίωση της απόδοσης των αλγορίθμων σύγκρισης γραφημάτων. Όπως αναφέρθηκε παραπάνω, οι περισσότερες υπάρχουσες μέθοδοι που μετρούν την ομοιότητα γραφημάτων εστιάζουν κυρίως στις τοπικές ιδιότητες των γραφημάτων, ενώ υπάρχουν και κάποιες μέθοδοι που εστιάζουν κυρίως στις καθολικές τους ιδιότητες. Ωστόσο, ακόμη κι αν δυο γραφήματα φαίνονται πολύ όμοια από τοπική ή καθολική οπτική γωνία, μπορεί να εμφανίζουν πολύ διαφορετική δομή σε διαφορετικές κλίμακες. Ως εκ τούτου, προτείνουμε ένα γενικό πλαίσιο για μέτρηση της ομοιότητας γραφημάτων που λαμβάνει υπόψη τη δομή των γραφημάτων σε πολλαπλές κλίμακες. Το προτεινόμενο πλαίσιο βασίζεται στην k-core αποσύνθεση η οποία είναι ικανή να αποκαλύψει διάφορες τοπολογικές και ιεραρχικές ιδιότητες των γραφημάτων. Συγκεκριμένα, η k-core αποσύνθεση χτίζει μια ιεραρχία ένθετων υπογραφημάτων, καθένα από τα οποία παρουσιάζει ισχυρότερη συνδεσιμότητα σε σχέση με το προηγούμενο. Μετρώντας την ομοιότητα αντίστοιχων με βάση την ιεραρχία υπογραφημάτων και συνδυάζοντας τα αποτελέσματα που προκύπτουν, μπορούμε να κατασκευάσουμε ακριβέστερα μέτρα ομοιότητας γραφημάτων. Εφαρμόζουμε το προτεινόμενο πλαίσιο για να παράγουμε παραλλαγές τεσσάρων δημοφιλών πυρήνων γραφημάτων, του πυρήνα graphlet, του πυρήνα συντομότερων μονοπατιών, του πυρήνα υποδέντρων Weisfeiler-Lehman και του πυρήνα pyramid match. Το πλαίσιο δεν περιορίζεται μόνο σε πυρήνες γραφημάτων, αλλά μπορεί να εφαρμοστεί σε οποιοδήποτε αλγόριθμο σύγκρισης γραφημάτων. Αξιολογούμε το προτεινόμενο πλαίσιο σε διάφορα σύνολα δεδομένων ταξινόμησης γραφημάτων. Τα αποτελέσματα δείχνουν ότι στις περισσότερες περιπτώσεις, χρησιμοποιώντας το προτεινόμενο πλαίσιο επιτυγχάνουμε σημαντικές βελτιώσεις όσον αφορά την ακρίβεια ταξινόμησης, ενώ η αύξηση στο χρόνο υπολογισμού είναι πολύ μικρή. Στο τρίτο μέρος της διατριβής, αντλώντας κίνητρο από την πρόσφατη επιτυχία των βαθέων νευρωνικών δικτύων σε πολλές εφαρμογές, προτείνουμε ένα συνελικτικό νευρωνικό δίκτυο για ταξινόμηση γραφημάτων το οποίο μαθαίνει αναπαραστάσεις οι οποίες καθορίζονται με βάση την επιτελούμενη εργασία. Όπως αναφέρθηκε παραπάνω, οι πυρήνες γραφημάτων έχουν εξελιχθεί σε ένα ιδιαίτερα αποδοτικό και ευρέως χρησιμοποιούμενο εργαλείο για την ταξινόμηση γραφημάτων. Για την ταξινόμηση γραφημάτων, σχεδιάζεται αρχικά ένας πυρήνας γραφημάτων και στη συνέχεια, μια Μηχανή Διανυσμάτων Υποστήριξης πραγματοποιεί την ταξινόμηση με βάση τις αναπαραστάσεις των γραφημάτων όπως αυτές καθορίζονται σιωπηρά από τη συνάρτηση πυρήνα. Η παραπάνω προσέγγιση που αποτελείται από δυο στάδια αποσυνδέει την αναπαράσταση των δεδομένων από τη μάθηση, πράγμα το οποίο είναι μη βέλτιστο. Τα συνελικτικά νευρωνικά δίκτυα έχουν πρόσφατα δείξει μεγάλες δυνατότητες στη μάθηση αναπαραστάσεων των δεδομένων, ωστόσο, τα δίκτυα αυτά δεν μπορούν να χειριστούν ευέλικτους τύπους δεδομένων, όπως τα γραφήματα. Αντιμετωπίζουμε αυτό το πρόβλημα συνδυάζοντας τα συνελικτικά νευρωνικά δίκτυα με πυρήνες γραφημάτων. Η προτεινόμενη προσέγγιση εξάγει αρχικά ένα σύνολο υπογραφημάτων από τα γραφήματα εισόδου. Έπειτα, χρησιμοποιεί πυρήνες γραφημάτων για να προβάλλει αυτά τα υπογραφήματα σε ένα διανυσματικό χώρο. Στη συνέχεια, ένα σύνολο φίλτρων εφαρμόζεται σε αυτά τα διανύσματα, ακολουθούμενα από εργασίες συγκέντρωσης και η έξοδος τροφοδοτείται ακολούθως σε ένα τυπικό νευρωνικό δίκτυο. Η αποτελεσματικότητα της προτεινόμενης προσέγγισης μετρήθηκε στην ταξινόμηση γραφημάτων όπου χρησιμοποιήθηκε ένα σύνολο από δημοφιλή συνόλα δεδομένων. Με ελάχιστη ρύθμιση παραμέτρων, το προτεινόμενο συνελικτικό νευρωνικό δίκτυο κατάφερε να ξεπεράσει σε απόδοση τις υπόλοιπες προσεγγίσεις σε 7 από τα 10 σύνολα δεδομένων. Στο τελευταίο μέρος, διερευνούμε πώς η ομοιότητα και η ταξινόμηση γραφημάτων μπορούν να χρησιμοποιηθούν για την βελτίωση εργασιών ανάλυσης δεδομένων τα οποία δεν διαθέτουν έμφυτη δομή γραφήματος. Αρχικά, εστιάζουμε στα προβλήματα της ομοιότητας και κατηγοριοποίησης κειμένων. Η κατηγοριοποίηση κειμένου είναι μια εργασία μηχανικής μάθησης για την αυτόματη ανάθεση ενός κειμένου σε ένα σύνολο προκαθορισμένων κατηγοριών. Το κλασικό μοντέλο bag-of-words αναπαριστά το κείμενο ως ένα πλήθος από τους όρους του, χωρίς να λαμβάνει υπόψη την εξάρτηση και τη σειρά των λέξεων. Αντιθέτως, προτείνουμε την αναπαράσταση των κειμένων ως γραφήματα όπου οι κορυφές αντιστοιχούν σε όρους που βρίσκονται μέσα στο κείμενο και οι ακμές αντιπροσωπεύουν συνεμφανίσεις μεταξύ των όρων μέσα σε ένα παράθυρο συγκεκριμένου μεγέθους. Στη συνέχεια, για να μετρήσουμε την ομοιότητα μεταξύ δύο εγγράφων, προτείνουμε τη χρήση πυρήνων γραφημάτων. Συγκεκριμένα, χρησιμοποιούμε μια προσέγγιση που βασίζεται στον πυρήνα συντομότερων μονοπατιών. Ο προτεινόμενος πυρήνας γραφημάτων συγκρίνει αποστάσεις συντομότερων μονοπατιών μεταξύ ζευγών κορυφών στα δυο γραφήματα. Ωστόσο, δεν λαμβάνονται υπόψη όλα τα μονοπάτια κάθε γραφήματος, αλλά μόνο εκείνα των οποίων το μήκος είναι το πολύ ίσο με μια παράμετρο που καθορίζεται από τον χρήστη. Για να πραγματοποιηθεί η κατηγοριοποίηση κειμένου, συνδυάζουμε τον προτεινόμενο πυρήνα με μια μια Μηχανή Διανυσμάτων Υποστήριξης. Τα αποτελέσματα στην κατηγοριοποίηση των κειμένων δείχνουν ότι η προτεινόμενη προσέγγιση στις περισσότερες περιπτώσεις ξεπερνά σε απόδοση παραδοσιακές και σύγχρονες τεχνικές, και είναι σε θέση να μετρήσει με μεγαλύτερη ακρίβεια την ομοιότητα δύο κειμένων. Εκτός από προβλήματα ανάλυσης κειμένου, εφαρμόσαμε την ομοιότητα και ταξινόμηση γραφημάτων στο πρόβλημα της ανίχνευσης κακόβουλου λογισμικού. Το πρόβλημα αυτό έχει λάβει σημαντική προσοχή τα τελευταία χρόνια λόγω του εκρηκτικού αριθμού κακόβουλων εφαρμογών που απευθύνονται σε κινητά τηλέφωνα και υπολογιστές χειρός. Προτείνουμε την αναπαράσταση των εφαρμογών ως γραφήματα όπου οι κορυφές αντιστοιχούν σε συναρτήσεις στον κώδικα των εφαρμογών ενώ οι ακμές αντιπροσωπεύουν τις κλήσεις μεταξύ συναρτήσεων. Κάθε κορυφή των γραφημάτων αυτών είναι συσχετισμένη με μια συνεχή ετικέτα (συνεχές διάνυσμα).Για να συγκρίνουμε δύο εφαρμογές, προτείνουμε έναν πυρήνα γραφημάτων που μπορεί να χειριστεί γραφήματα με τέτοιου είδους ετικέτες. Επιπλέον, προτείνουμε μια μέθοδο που μετατρέπει τις ετικέτες αυτές σε διακριτές και επιτρέπει τη χρήση υψηλής απόδοσης αλγορίθμων που έχουν σχεδιαστεί για γραφήματα με διακριτές ετικέτες. Οι προτεινόμενες προσεγγίσεις πετυχαίνουν εξαιρετική απόδοση στην ανίχνευση κακόβουλου λογισμικού, τόσο ως προς το χρόνο εκτέλεσης όσο και ως προς την ακρίβεια ταξινόμησης.