Machine learning on graphs: algorithms and applications

Abstract

Graphs are well-studied structures which are utilized to model entities and their relationships. In recent years, graph-based representations have become ubiquitous in many application domains. For instance, in chemoinformatics graphs are used to capture the structure of molecules, while in natural language processing they are used to represent textual documents. In many applications, we are interested in performing machine learning tasks on graphs such as graph classification and graph clustering. In the past years, the problem of classifying large collections of graphs has become crucial with several important applications. The goal of this thesis is to study and address the challenging problem of graph classification, focusing on both the design of new algorithms and tools, as well as on demonstrating its applicability to domains where traditionally, fundamentally different approaches dominate. In the first part of the thesis, we present two novel algorithms capable of comparing graphs based on their global properties. In recent years, research in graph classification has concentrated mainly on graph kernels. A kernel is a function that takes as input two data objects and outputs a number, with the property that the function is symmetric and positive semidefinite. Kernels can be thought of as measures of similarity between pairs of objects. A graph kernel is a kernel function that measures the similarity between pairs of graphs. The most remarkable property of such methods is that they allow some algorithms such as Support Vector Machines (SVM) to work directly on graphs, without having to explicitly represent them as feature vectors. Most existing graph kernels focus on local properties of graphs and ignore global structure. We propose to compare graphs based on their global properties as these are captured by the eigenvectors of their adjacency matrices. More specifically, we propose two algorithms for both labeled and unlabeled graph comparison. These algorithms represent each graph as a set of vectors corresponding to the embeddings of its vertices. The first algorithm makes use of the Earth Mover’s Distance metric to compute the similarity between two graphs. However, this similarity measure is not a valid kernel. To account for this, we employ an algorithm for SVM classification using indefinite kernels. The second algorithm corresponds to a valid graph kernel and is based on the Pyramid Match kernel. The algorithm finds an approximate correspondence between the sets of vectors of the two graphs. We evaluate the proposed methods on several benchmark datasets for graph classification from the fields of chemoinformatics and bioinformatics, and compare their performance to state-of-the-art graph kernels. Our results indicate that the proposed algorithms outperform the competing methods, while their time complexity remains very attractive. In the second part, we focus again on designing new algorithms/tools for graph similarity and graph classification. Specifically, we define a general framework for improving the performance of graph comparison algorithms. Most existing methods for graph similarity focus mainly either on local or on global properties of graphs. However, even if graphs seem very similar from a local or a global perspective, they may exhibit different structure at different scales. Hence, we propose a general framework for graph similarity which takes into account structure at multiple different scales. The proposed framework is based on the k-core decomposition which is capable of uncovering several topological and hierarchical properties of graphs. Specifically, the k-core decomposition builds a hierarchy of nested subgraphs, each having stronger connectedness properties compared to the previous. By measuring the similarity between the corresponding in the hierarchy subgraphs and combining the results, we can build more accurate measures of graph similarity. We apply the framework to derive variants of four graph kernels, namely graphlet kernel, shortest-path kernel, Weisfeiler-Lehman subtree kernel, and pyramid match graph kernel. The framework is not limited to graph kernels, but can be applied to any algorithm that compares pairs of graphs. The proposed framework is evaluated on several benchmark datasets for graph classification. Our results show that in most cases, the core based kernels achieve significant improvements in terms of classification accuracy over the base kernels, while the added time complexity is very low. In the third part of the thesis, motivated by the recent success of deep neural network architectures, we propose a Convolutional Neural Network (CNN) that automatically learns task-dependent representations for graph-structured data. In the past years, graph kernels have become an efficient and widely-used tool for graph classification. To perform classification, a graph kernel is first designed, and then an SVM classifier is trained based on data representations defined implicitly by the kernel. This two-stage approach decouples data representation from learning, which is suboptimal. CNNs have recently shown great potential in end-to-end representation learning, however, these networks cannot handle irregular data such as graphs. We address this challenge by combining graph kernels with CNNs.The proposed approach first extracts a set of subgraphs from the input graphs.It then uses graph kernels to embed these subgraphs in a feature space. A set of filters is then applied to these patches, followed by pooling operators, and the output is then fed to a standard feedforward neural network. The effectiveness of the proposed approach is clearly demonstrated by the experimental results on a set of standard graph classification datasets. With limited parameter tuning, our approach outperforms state-of-the-art baselines on 7 out of 10 benchmark datasets, and reaches comparable performance elsewhere. In the last part, we investigate how graph similarity and graph classification can be used to enhance analytics tasks on data without inherent graph structure. First, we focus on the problems of document similarity and text categorization. Text categorization corresponds to the supervised learning task of assigning a textual document to a set of predefined categories. In the typical bag-of-words model, the text is represented as a multiset of its terms, disregarding dependence and ordering of the words. Instead, we represent textual documents as statistical graphs whose vertices correspond to unique terms of the document and whose edges represent co-occurrences between the terms within a fixed-size sliding window over the document. Then, in order to measure the similarity between two documents, we propose to use graph kernels. Specifically, we capitalize on the shortest-path graph kernel and we modify it to compare the graph representations of documents. The proposed graph kernel is based on the shortest-path distances between pairs of vertices of the two graphs. However, not all paths of each graph are taken into account, but only those whose length is at most equal to a parameter determined by the user. To perform text categorization, we combine the proposed kernel with an SVM classifier. Our results indicate that the proposed approach outperforms traditional and state-of-the-art techniques and is capable of measuring more accurately the similarity between two documents and hence, to achieve improved performance in text categorization. Besides text mining problems, we employed graph similarity and graph classification to address the problem of malware detection. Malware detection has received significant attention in recent years due to the exploding number of malicious applications targeting smartphones and tablet computers. We represent application programs as graphs where vertices correspond to functions and edges represent calls between functions. Each vertex of the emerging graphs is associated with a continuous label. To compare two programs, we propose a graph kernel which can cope with such continuous node labels. In addition, we propose a method that transforms continuous node labels to discrete and allows the use of existing algorithms designed for graphs with discrete node labels. The proposed approaches show excellent performance in the malware detection task, both in terms of runtime and classification accuracy.

Τα γραφήματα είναι δομές που έχουν μελετηθεί ευρέως και που χρησιμοποιούνται για να μοντελοποιήσουν οντότητες και τις μεταξύ τους σχέσεις. Τα τελευταία χρόνια, οι αναπαραστάσεις δεδομένων ως γραφήματα έχουν διαδοθεί σε μεγάλο βαθμό και χρησιμοποιούνται σε πολλές εφαρμογές. Για παράδειγμα, στην υπολογιστική χημεία, τα γραφήματα χρησιμοποιούνται για την αναπαράσταση μορίων, ενώ στην επεξεργασία φυσικής γλώσσας χρησιμοποιούνται για την αναπαράσταση κειμένων. Σε πολλές εφαρμογές, είναι απαραίτητο να εκτελέσουμε εργασίες μηχανικής μάθησης πάνω σε γραφήματα όπως για παράδειγμα να ταξινομήσουμε γραφήματα ή να ομαδοποιήσουμε γραφήματα. Τα τελευταία χρόνια, το πρόβλημα της ταξινόμησης μεγάλων συλλογών γραφημάτων έχει αποκτήσει ιδιαίτερη σημασία μιάς και αποτελεί τη βάση αρκετών σημαντικών εφαρμογών. Σκοπός της παρούσας διατριβής είναι να μελετήσει και να αντιμετωπίσει το πρόβλημα της ταξινόμησης γραφημάτων, εστιάζοντας τόσο στο σχεδιασμό νέων αλγορίθμων και εργαλείων, όσο και στην εφαρμογή του πρβλήματος σε τομείς όπου κυριαρχούν παραδοσιακά διαφορετικές προσεγγίσεις. Στο πρώτο μέρος της διατριβής παρουσιάζονται δύο νέοι αλγόριθμοι που είναι ικανοί να συγκρίνουν γραφήματα με βάση τις καθολικές τους ιδιότητες.Τα τελευταία χρόνια, η έρευνα στην ταξινόμηση γραφημάτων έχει επικεντρωθεί κυρίως στους πυρήνες γραφημάτων (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 αναπαριστά το κείμενο ως ένα πλήθος από τους όρους του, χωρίς να λαμβάνει υπόψη την εξάρτηση και τη σειρά των λέξεων. Αντιθέτως, προτείνουμε την αναπαράσταση των κειμένων ως γραφήματα όπου οι κορυφές αντιστοιχούν σε όρους που βρίσκονται μέσα στο κείμενο και οι ακμές αντιπροσωπεύουν συνεμφανίσεις μεταξύ των όρων μέσα σε ένα παράθυρο συγκεκριμένου μεγέθους. Στη συνέχεια, για να μετρήσουμε την ομοιότητα μεταξύ δύο εγγράφων, προτείνουμε τη χρήση πυρήνων γραφημάτων. Συγκεκριμένα, χρησιμοποιούμε μια προσέγγιση που βασίζεται στον πυρήνα συντομότερων μονοπατιών. Ο προτεινόμενος πυρήνας γραφημάτων συγκρίνει αποστάσεις συντομότερων μονοπατιών μεταξύ ζευγών κορυφών στα δυο γραφήματα. Ωστόσο, δεν λαμβάνονται υπόψη όλα τα μονοπάτια κάθε γραφήματος, αλλά μόνο εκείνα των οποίων το μήκος είναι το πολύ ίσο με μια παράμετρο που καθορίζεται από τον χρήστη. Για να πραγματοποιηθεί η κατηγοριοποίηση κειμένου, συνδυάζουμε τον προτεινόμενο πυρήνα με μια μια Μηχανή Διανυσμάτων Υποστήριξης. Τα αποτελέσματα στην κατηγοριοποίηση των κειμένων δείχνουν ότι η προτεινόμενη προσέγγιση στις περισσότερες περιπτώσεις ξεπερνά σε απόδοση παραδοσιακές και σύγχρονες τεχνικές, και είναι σε θέση να μετρήσει με μεγαλύτερη ακρίβεια την ομοιότητα δύο κειμένων. Εκτός από προβλήματα ανάλυσης κειμένου, εφαρμόσαμε την ομοιότητα και ταξινόμηση γραφημάτων στο πρόβλημα της ανίχνευσης κακόβουλου λογισμικού. Το πρόβλημα αυτό έχει λάβει σημαντική προσοχή τα τελευταία χρόνια λόγω του εκρηκτικού αριθμού κακόβουλων εφαρμογών που απευθύνονται σε κινητά τηλέφωνα και υπολογιστές χειρός. Προτείνουμε την αναπαράσταση των εφαρμογών ως γραφήματα όπου οι κορυφές αντιστοιχούν σε συναρτήσεις στον κώδικα των εφαρμογών ενώ οι ακμές αντιπροσωπεύουν τις κλήσεις μεταξύ συναρτήσεων. Κάθε κορυφή των γραφημάτων αυτών είναι συσχετισμένη με μια συνεχή ετικέτα (συνεχές διάνυσμα).Για να συγκρίνουμε δύο εφαρμογές, προτείνουμε έναν πυρήνα γραφημάτων που μπορεί να χειριστεί γραφήματα με τέτοιου είδους ετικέτες. Επιπλέον, προτείνουμε μια μέθοδο που μετατρέπει τις ετικέτες αυτές σε διακριτές και επιτρέπει τη χρήση υψηλής απόδοσης αλγορίθμων που έχουν σχεδιαστεί για γραφήματα με διακριτές ετικέτες. Οι προτεινόμενες προσεγγίσεις πετυχαίνουν εξαιρετική απόδοση στην ανίχνευση κακόβουλου λογισμικού, τόσο ως προς το χρόνο εκτέλεσης όσο και ως προς την ακρίβεια ταξινόμησης.