Athens University Economics and Business (AUEB)
Machine learning on graphs: algorithms and applications
Abstract
dc:descriptionGraphs 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.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Nikolentzos, Ioannis
- Νικολέντζος, Ιωάννης
Subjects
dc:subject × 8Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/42338