Nikos Petropoulos

Kostis Manikas

Michalis Anagnostakis

Dimitra (Mitsi Vourekas

Keywords: Weisfeiler-Lehman algorithm, graph kernels, regularization, k-support norm, MRI, DTI, 3D shape classification

Medical images have been widely used in modern medicine to depict the anatomy or function for both clinical purposes and for studying normal anatomy. Analyzing medical images efficiently and with high accuracy is a crucial step. The high-dimensionality and the non-linear nature of medical imaging data makes their analysis a difficult and challenging problem. In this thesis, we address the medical image analysis from the viewpoint of statistical learning theory and we concentrate especially on the use of regularization methods and graph representation and comparison.

First, we approach the problem of graph representation and comparison for analyzing medical images. Graphs are a commonly used technique to represent data with inherited structure. Exploiting these data, requires the ability to efficiently compare and represent graphs. Unfortunately, standard solutions to these problems are either NP-hard, hard to parametrize and adapt to the problem at hand or not expressive enough. Graph kernels, which have been introduced in the machine learning community the last decade, are a promising solution to the aforementioned problems.

Despite the significant progress in the design and improvement of graph kernels in the past few years, existing graph kernels focus on either unlabeled or discretely labeled graphs, while efficient and expressive representation and comparison of graphs with complex labels, such as real numbers and high-dimensional vectors, remains an open research problem. We introduce a novel method, the pyramid quantized Weisfeiler-Lehman graph representation to tackle the graph comparison and representation problem for continuous vector labeled graphs. Our algorithm considers statistics of subtree patterns based on the Weisfeiler-Lehman algorithm and uses a pyramid quantization strategy to determine a logarithmic number of discrete labellings. As a result, we approximate a graph representation with continuous or vector valued labels as a sequence of graphs discrete labels with increasing granularity. We evaluate our proposed algorithm on two different tasks with real datasets, on a fMRI analysis task and on the generic problem of 3D shape classification. 9 10 Second, we examine different regularization methods for analyzing medical images, and more specifically MRI data. Regularization methods are a powerful tool for improving the predicted performance and avoid overfitting by introducing additional information to an ill-posed problem, such as the analysis of medical images. Towards this direction, we introduce a novel regularization method, the k-support regularized Support Vector Machine. This algorithm extends the ℓ 1 regularized SVM to a mixed norm of both ℓ 1 and ℓ 2 norms. This enables the use of a correlated sparsity regularization with the power of the SVM framework. We evaluate our novel algorithm in a neuromuscular disease classification task using MRI-based markers. We furthermore explore the importance of diffusion tensor imaging for the discrimination between neuromuscular conditions.

Overall, as graphs are fundamental mathematical objects and regularization methods are widely used to control ill-pose problems, both the pyramid quantized Weisfeiler-Lehman graph representation and the k-support regularized SVM are potentially applicable to a wide range of applications domains in computer vision, analysis of medical images and data mining.

It is a true pleasure for me to thank all the people who made this thesis possible.

First of all, I would like to thank the director of the lab, Nikos Paragios, for giving me the chance to accomplish my PhD thesis at Ecole Centrale Paris and for providing me with the opportunity to meet and collaborate with incredible scientists. This long journey was an incredible experience I will never forget.

I owe my honest and deepest gratitude and respect to my supervisor Matthew Blaschko, both as a professor and as a person. I would like to thank him for all our passionate discussions and brainstorming sessions concerning my thesis and machine learning in general and for all the interesting diverse subjects as well, for all the time he dedicated to explain the tiniest detail to me, for all the meticulous effort to improve every single paper and presentation. Moreover, I feel gratitude for his strong support, his continuous encouragement whenever difficulties arose and for his invaluable guidance and inspiration during the time it took to accomplish this thesis. It was a real privilege and a great pleasure to work with him.

Next, I am grateful to Rafeef Abugharbieh and Georg Langs for their fruitful reviews on my manuscript. They made it a point of honor to comment thoroughly on my work, while being generous with enthusiastic remarks. I also address many thanks to Andreas Bartels, Guillaume Bassez and Gaël Varoquaux for participating in my thesis committee.

It was a privilege to have such well-known researchers evaluating my work.

During my thesis, I had the opportunity to collaborate closely with great scientists. I would like to thank our collaborators from the United States for providing me with the cocaine addiction dataset and for their valuable expertise: Jean Honorio, Dimitris Samaras and Rita Goldstein. A special thanks to Jean Honorio for his insightful comments and for the fruitful discussions we had. I would also like to thank Deux Jean-François, Bassez Guillaume, Sotiras Aristeidis, Rahmouni Alain and Varacca Thibault for the muscle dataset, and Andreas Bartels for providing the free viewing dataset. 6 I would also like to thank all the people I met at Ecole Centrale Paris who made my staying there a wonderful and cheerful experience. First of all, I would like to thank Xiang Bo, my office roomy, for her support and her help, especially for helping find a very cozy place to live in during the last months of my Phd. Then I would like to thank all the people who welcomed me to the MAS-Vision lab, when I arrived in Paris: Aris Sotiras, Olivier Teboul, Loic Simon, Chaohui Wang, Ahmed Besbes, Salma Essafi, Radhouene Neji, Regis Behmo, Fabrice Michel, Nicolas Honnorat and Pierre-Yves Baudin. Also I would like to thank all the people from the CVC lab, who made the lab during the last period of the thesis and the most difficult one a very pleasant place to work in: Evgenios Kornaropoulos, Enzo Ferrante, Punnet Kumar, Siddartha Chandra, Stefan Kinauer, Sarah Parisot, Vivian Fecamp, Stavros Alchatzidis, Haithem Boussaid, Stavros Tsogkas and Gao Lufang. Lastly, I would like to thank all the administration personnel, especially the lab secretaries: Sylvie Dervin -the secretary of MAS-Vision who helped me a lot with the bureaucratic procedure when I entered the Ecole Centrale -as well as Carine Morotti-Delorme and Natalia Leclercq -our CVC lab secretaries who were "life savers" for the lab and whose help for the paperwork of the defense was extremely valuable.

Outside the professional sphere, I would like to thank all my whole family and especially my mother, my father and my brother, who always showed me love and unconditional support to chase my dreams and who I sometimes take for grated and forget to show them how precious they are to me.

There are also some friends that I consider as family and that I would also like to acknowledge. They all supported and helped me, sometimes without even knowing it.

My dear friend Sofia Maschalidi (Sofouko) who stood by me like a rock, always bringing me love, help and support. She will always have my ever lasting love and gratitude. Also I enjoyed the support of many friends who were in Paris: Eirini Papagiakoumou, Dimitris Papadopoulos, Anna Athanasopoulou, Manos Saridakis and Anthi Koskina and their little girls (Eliza, Peggi and Nicole), Dimitra Konsta, Rania Panousi, Lida Kotronaki, Alexandros Giannopoulos, Anestis Charadontis, Yves Piriou and Aline Barazer. It is very important to have close friends to have fun with and enjoy a nice drink or a stroll in Paris.

I also had the support from friends who although they were far away, they were actually really close to me: my ex-roomy Elias Grinias, my old girlfriends Angeliki Siafaka, Eftichia Ioannidou and Ioanna Manoutsoglou, my "pararell" friends : Manos Avgeridis (Manolito) who offered me shelter when I was writing my thesis, Eva Paradissi and Katerina Stavroula with whom I had great summer vacations when I needed them most, Marina Kontara (la Belge), Giorgos Antonopoulos (Jorgito), Petros Stergiou, Tasos

Résumé

Les images médicales ont largement utilisées en médicine moderne afin de représenter l'anatomie ou les fonctions, à la fois dans un objectif cliniques ou d'étude de l'anatomie normale. L'analyse efficace et précise d' images médicales est une étape critique.

La dimensionnalité élévée et le caractère non-linéaire des données d'imagerie médicale rendent leur analyse difficile. Dans cette thèse, nous nous intéressons à l'analyse d'images médicales du point de vue de la théorie statistique de l'appretissage et nous concentrons spécialement sur l'utilisation de méthodes de régularisation et de la représentation et comparaison des graphes. Tout d'abord, nous nous intéressons un problème de représentation et comparaison des graphes pour l'analyse des images médicales et de façon plus générale. Les graphes sont une technique largement utilisée pour la représentation des données ayant une structure héritée. L'exploitation des ces données nécessite la capacité de comparer et représenter efficacement des graphes. Malheureusement, les solutions usuelles à ces problèmes sont soit NP-complets, difficiles à paramétrer et à adapter au problème donnée, soit insuffisamment expressives. Les noyaux sur graphes, introduits à la communauté de l'apprentissage statistique au cours de la dernière décennie, offrent une solution promettante aux problèmes mentionnés ci-dessus.

Malgré le progrès significatif dans le domaine de la conception et amélioration des noyaux sur graphes au cours des dernières années, les noyaux sur graphes existants se concentrent à des graphes non-labellisés ou labellisés de façon dicrète, tandis que la représentation et comparaison efficaces et expressives de graphes avec des labels complexe, comme des nombres réels ou des vecteurs à grande dimension, demeure une problème de recherch ouvert. Nous introduisons une nouvelle méthode, l'algorithme de Weisfeiler-Lehman pyramidal et quantifié (pyramid quantized Weisfeiler-Lehman algorithm), afin d'aborder le problème de la représentation et comparaison des graphes labellisés pqr des vecteurs continus. Notre algorithme considère les statistiques de motifs sous arbre, basé sur l'algorithme Weisfeiler-Lehman ; il utilise une stratégie de quantification pyramidale pour 12 déterminer un nombre logarithmique de labels discrets. Par conséquent, nous approximons une représentation de graphe avec des labels continus ou vecteur, comme une séquence de graphes avec des labels discrèts de plus en plus granulaires. Nous évaluons notre algorithme proposé sur deux tâches différentes et des bases des données réelles : un tâché d'une analyse IRMf et une tâche de problème générique de la classification de formes en trois dimensions.

Ensuite, nous examinons différentes méthodes de régularisation pour analyser les images médicales, et plus spécifiquement des données d'IRM. Les méthodes de régularisation sont un outil puissant pour l'amélioration de la performance prédite et pour éviter le sur-apprentissage via l'introduction d'informations additionelles à un problème mal-posé tel que l'analyse d'images médicales. Dans cette direction, nous introduisons une nouvelle méthode de régularisation, la k-support regularized Support Vector Machine (les machines à vecteurs de support régularisées k-support). Cet algorithme étend la SVM régularisée ℓ 1 à une norme mixte de toutes les deux normes ℓ 1 et ℓ 2 . Ceci permet l'utilisation d'une régularisation parcimonieuse corrélée à la puissance des SVM. Nous évaluons notre original algorithme sur une tâche de classification de maladies neuromusculaires, en utilisant des marqueurs à base de IRM. Par la suite, nous explorons l'importance de l'imagerie du tenseur de diffusion pour la discrimination entre les conditions neuromusculaires.

Globalement, les graphes étqnt des objets mathématiques fondamentaux et les méthodes de régularisation étant largement utilisées pour contrôler des problèmes mal-posés, l' algorithme de Weisfeiler-Lehman pyramidal et quantifié (pyramid quantized Weisfeiler-Lehman algorithm) et la SVM régularisées k-support (k-support regularized SVM), pourraient bien être appliqués sur un grand éventail d'applications dans les domaines de vision artificielle, l'analyse d'images médicales et l'exploration de données.

Mots-clefs : algorithme Weisfeiler-Lehman, noyaux de graphes, régularisation, norme k-support, IRM, IDT, classification de la forme en trois dimensions. The medical imaging field continuously improves as technology evolves providing more accurate and rich information. In order to extract the relevant information and provide it to the physician, analyzing medical images is an essential step in modern medicine.

The high dimensionality and the non-linearity of the data makes medical image analysis a difficult and challenging problem. In this thesis, we approach medical image analysis from the perspective of statistical learning theory [START_REF] Vapnik | The nature of statistical learning theory[END_REF][START_REF] Hastie | The elements of statistical learning : data mining, inference, and prediction[END_REF] and more specifically we focus on the use of graph representation and different regularization methods.

Graphs are a general, powerful, flexible and natural way to mathematically represent complex data with integrated structure. A graph consists of a set of nodes -which 24

Chapter 1 Introduction represents the objects of interest -and a set of edges -which represents the relations between them [START_REF] Diestel | Graph Theory[END_REF][START_REF] Gibbons | Algorithmic Graph Theory[END_REF]. For example, a molecule can be represented as graph by taking the atoms as nodes, while when a pair of atoms is connected with a bond this relationship can be represented with an edge. Extra information, such as the type of the chemical bond in the previous example, can be incorporated into the graph as labels in the edges. Applications involving graph representation are numerous and they occur in a number of different fields. We list below examples from a number of representative fields.

Computer vision and biomedical imaging Graphs have been widely used in computer vision problems over the past decades. There are often used for representing images -either as grid of pixels or as a graph of adjacency regions or segmented partsand for solving problems, such as segmentation [START_REF] Greig | Exact Maximum A Posteriori Estimation for Binary Images[END_REF] or finding correspondences between two images [START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF]. Graphs are also used in biomedical image analysis to represent and model organs, such as the brain [Ng et al., 2012a[START_REF] Rao | Adaptive regularization for image segmentation using local image curvature cues[END_REF], which can potentially be used in diagnosis or studying the human body.

Bioinformatics Advances in technology in the last 15 years allow the generation of vast amount of genome sequences and gene expression levels, as well as the detection of biomolecular interactions. These various data produce various types of graph representations, such as protein-protein interactions [START_REF] Canutescu | A graphtheory algorithm for rapid protein side-chain prediction[END_REF], metabolic pathways [START_REF] Wagner | The genetic graph: a representation for the evolution of procedural knowledge[END_REF], transcriptional pathways and evolutionary relationships [Goldstein, 1979]. A number of interesting questions raise from the analysis of these graphs such as which genes regulate others, how the phenotype is influenced, whether we can we predict the interaction between a pair of proteins based on their structure, etc. These graph representations can contain complex labels and incomplete information making their analysis a challenging task.

Social networks

The wide spread use of internet in more and more domains with more and more people, the augmentation of email exchange, the expand of new means of communications such as blogs, social networks or instant messages, create a vast amount of data that can be represented as graphs. The analysis of these networks is both of scientific and commercial interest. On the one hand, psychologists want to study the complex social dynamics among humans and biologists want to explore the social rules in a group of animals. On the other hand, industries want to analyze these networks for marketing purposes. Detecting influential individuals in a group of people is relevant for marketing, as companies could then focus their advertising efforts on these individuals, which can influence the behavior of the whole group.

Chemoinformatics Chemistry is another domain where graph representation and graph comparison is applied [START_REF] Hapke | Chemoinformatics. a textbook. Auskunft[END_REF]. Finding chemical compounds with a specific property is a common problem in chemistry and pharmacology. A common assumption is that molecules with similar structure share also similar functional properties and as chemical molecules have been widely represented as graph -where atoms represent vertices and bonds represent the edges -so being able to compare graphs and find similarity among them is a crucial problem in chemoinformatics.

On the other hand, regularization, in the fields of machine learning and statistics, refers to the process of introducing additional information in order to solve an ill-posed problem or to prevent overfitting [START_REF] Hastie | The elements of statistical learning : data mining, inference, and prediction[END_REF]. This information usually has the form of a penalty on the complexity of the learned model or restrictions for smoothness.

Regularizers have been extensively used in various problems, among them the reconstruction of PET images [START_REF] Kaufman | PET regularization by envelope guided conjugate gradients[END_REF], image segmentation [START_REF] Woolrich | Mixture models with adaptive spatial regularization for segmentation with an application to FMRI data[END_REF] and classification or regression problems.

In this thesis, we focus on the following tasks: (a) the analysis of fMRI data through the representation as labeled graphs and (b) the analysis of MRI data using regularization methods. Towards this direction, we also introduce two novel learning algorithms, the pyramid quantized Weisfeiler-Lehman graph representation and the k-support regularized SVM.

Statistical learning

Given a set of n paired observations {(x i , y i )} 1≤i≤n ∈ R d × R that is assumed to be independent and identically drawn from the joint distribution p XY , the goal of statistical learning is to learn a function f (x) ∈ F for predicting the output y given the input x.

This prediction function f (x) is built via the evaluation of a loss function L(f (x), y) that penalizes errors in prediction. This leads us to a criterion for choosing f , the risk or generalization error of the prediction function which is defined as:

R(f ) = L(f (x), y)dp XY (x, y), (1.1)
where L is a loss function and p XY is the joint distribution, covering the probability of a label and an input being uncover together. Ideally, we would like to learn a prediction function f that will minimize the risk. However, since the joint probability p XY is unknown, the risk is also unknown. Nonetheless we can approximate the risk R(f ) and empirically calculate it through the given set of paired observation

{(x i , y i )} 1≤i≤n ∈ R d × R,
R(f ) ≈ R(f ) = 1 n n i=1 L(f (x i ), y i ) (1.2)
Equation 1.2 is called the empirical risk and as n → ∞, the empirical risk will approach the true risk, R(f ) → R(f ) and we have statistical consistency for an estimator that returns arg min f ∈F R(f ).

In real datasets we always have finite sample sizes, so choosing a prediction function f ∈ F that minimizes the empirical risk (see Equation 1.2), often leads to overfitting.

This means that the empirical risk R is much lower that the real risk R. One way to avoid overfitting on the training dataset and being able to generalize well on new data is by adding a regularization term λΩ(f ), where f ∈ F is the prediction function we would like to learn, λ is a scalar parameter that controls the degree of regularization and Ω : F → R is a scalar valued function that penalizes the "complexity" of the prediction function. A number of regularizers have been proposed in the literature, among them the Tikhonov regularization [START_REF] Tikhonov | On the stability of inverse problems[END_REF], the LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] and Elastic

Net [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF]. By adding the regularization term to the empirical risk from Equation 1.2 the problem is formulated as follows:

arg min f ∈F λΩ(f ) + 1 n n i=1 L(f (x i ), y i ) (1.3)
For the problem defined in Equation 1.3 in this thesis we examine novel combinations of regularizers and prediction functions for the analysis of medical images. We justify those choices both theoretically and empirically in the following chapters.

Thesis outline

The thesis is organized as follows: we first concentrate on the graph comparison problem and on our proposed method that efficiently compares graphs with continuous or vector labels, the pyramid quantized Weisfeiler-Lehman algorithm. To the best of our knowledge, this is the first method for efficiently comparing graphs with continuous vector labels. In Chapter 2 we start by introducing basic notations and background from graph theory (see Section 2.1) and we then explore the graph comparison problem in detail (see Section 2.2 and Section 2.3). In Chapter 3 we introduce our novel algorithm, the pyramid quantized Weisfeiler-Lehman algorithm. Our algorithm is based on the Weisfeiler-Lehman test of isomorphism, described in Section 3.1, which was recently employed as a graph kernel to compare graphs with discrete labels (see Section 3.2). In order to make use of the efficiency of the Weisfeler-Lehman algorithm and apply it to continuous or vector labeled graphs, in Section 3.3 we present a pyramid quantization strategy and transform the graph representation with continuous or vector valued labels as a sequence of graphs with increasingly granular discrete labels. Finally, we explore different tactics for combining information from the various pyramid quantization levels in Section 3.4.

In Chapter 4 we evaluate our proposed algorithm on two different tasks. The first one, described in Section 4.1, is from the area of fMRI analysis and its objective is to discriminate between cocaine abusers and healthy control subjects. The second one, described in Section 4.2, is from the area of 3D shape classification. In this task, we use two datasets with 3D meshes, one that comes from the medical area, whose objective is to discriminate between healthy and patient subjects that suffer from a neuromuscular dystrophy, while in the second dataset we tackle a multiclass problem of generic object classification.

Apart from the graph comparison problem, in Chapter 5 we explore different regularization methods for analyzing medical images, and more specifically MRI data. In Section 5.1 we present the regularizers under investigation and we also introduce our novel learning algorithm the k-support regularized SVM (see Section 5.1.3.2). In our first experiment in Section 5.2, we investigate the use of regularization methods, the well-known LASSO and Elastic Net and the newly introduced k-support norm with squared loss, in the analysis of fMRI images. In the following Section 5.3, we evaluate our newly introduced learning algorithm, the k-support regularized SVM in the discriminative task of neuromuscular disease classification using features extracted from T1-weighted, T2weighted and diffusion tensor imaging. Although DTI imaging is widely used in neuroimaging studies, it has been recently introduced in the clinical analysis of the calf muscle and we also investigate its significance for neuromuscular classification. Finally, in Chapter 6, we conclude the thesis by summarizing the contributions (Section 6.1) and by offering some future perspectives (Section 6.2).

Published work appearing in this thesis

This thesis contains material, modified or in extended form, from several published articles. We list these publications below, indicating the corresponding sections of this manuscript.

• Katerina Gkirtzou, Jean Honorio, Dimitris Samaras, Rita Goldstein, and Matthew B. In this chapter we explore the graph comparison problem in detail. We first introduce key concepts and notation from graph theory in Section 2.1 and we then review the most related work on the graph comparison problem, which can be classified in the following categories, (a) graph comparison methods (Section 2.2) and (b) graph kernel methods (Section 2.3).

Graph theory basics and notation

In order to understand the importance of graphs and especially the problem of graph comparison, we will need some basic background of graph theory. In this section we will define the terminology and the basic notation that will be used for the rest of the thesis.

Most of the graph-theoretic terminology follows the monograph of Diestel [START_REF] Diestel | Graph Theory[END_REF] or the monograph of Gibbons [START_REF] Gibbons | Algorithmic Graph Theory[END_REF].

Chapter 2 Related work on graph comparison 2.1.1 Directed, undirected and labeled graphs and subgraphs Definition 2.1 (Graph). A graph G is a pair of sets (V, E), where V is the vertex set and its elements are called vertices (also known as nodes or points) and E ⊆ V × V is the edge set which represents a binary relation on V and its elements are called edges (also known as arcs or lines).

The order or size of a graph G is defined as the number of vertices |V |. Graphs are finite, infinite, countable and so on according to their order.

Definition 2.2 (Directed and Undirected graph). A graph G = (V, E) is called directed when the edge set E consists of ordered pairs of vertices, that is (u, v) ∈ E is considered to be directed from u to v and u, v ∈ V . When the edge set E contains unordered pairs , that is (u, v) ∈ E and (v, u) ∈ E are considered to be the same edge ∀u, v ∈ V , it is called undirected. for the directed graph and as lines for the undirected one. When a graph does not contain multiple edges between the same pair of nodes (and of the same direction in a directed graph) as well as self-loops -edges from a vertex to itself -then it is called simple graph. In this thesis, we mainly focus on simple graphs.

A graph can have labels on its nodes and/or on its edges and in this case the graph is called labeled.

Definition 2.3 (Labeled Graph). A labeled graph is defined as a triplet G = (V, E, L),
where V is the vertex set, E is the edge set and L : X → Σ is a function assigning a label from an alphabet Σ to each element of the set X, which can be either V , E or V ∪ E depending on whether only nodes, only edges or both are labeled. A graph with labels on its nodes is called node-labeled, a graph with labels on its edges is called edge-labeled. The most common cases of labeled graphs are the weighted graphs where each edge is associated with a continuous value, also known as weight. Examples of node-labeled, edge-labeled and both node and edge labeled graphs can be seen in Figure 2.2.

Definition 2.4 (Induced subgraph). A graph G ′ = (V ′ , E ′ ) is a subgraph of G = (V, E) if V ′ ⊆ V and E ′ ⊆ E and is denoted as G ′ ⊆ G. Given a set V ′ ⊆ V the subgraph of G that is induced by V ′ is the graph G ′ = (V ′ , E ′ ) where E ′ = {(u, v) ∈ E : u, v ∈ V ′ }.
An example of an induced subgraph can be seen in Figure 2.1(c)

Neighborhood in graphs

Given an edge e = (u, v) ∈ E, we say that e is incident with u or v when u or v is an end-point of the edge e and nodes u, v are said to be adjacent or neighbors. Similarly, when two edges e i = e j share a common node then they are also adjacent.

Chapter 2 Related work on graph comparison Definition 2.5 (Neighborhood and Degree of node). The neighborhood of a vertex v in a graph G, denoted as N (v), is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. The degree of a vertex u, denoted as d(u), is the number of edges incident with u. An example of the neighborhood of a node and its degree can be seen in Figure 2.3. The neighborhood information of a graph is commonly represented as an adjacency matrix, which is defined as follows:

Definition 2.6 (Adjacency matrix). The adjacency matrix A = (A ij ) n×n of a graph G = (V, E) is defined as :

A ij = 1 if (u i , u j ) ∈ E, 0 otherwise (2.1)
where u i and u j are nodes from G.

2.1.3 Walks, paths, cycles, trees, subtrees and subtree patterns Definition 2.7 (Walk, path and cycle). A walk w of length l in a graph G = (V, E) is a sequence of nodes and adjacent edges (v 1 , e 1 , v 2 , e 2 , . . . , e l-1 , v l ) such that

e i = (v i , v i+1 ) ∀i 1 ≤ i ≤ (l -1).
A path is a walk that contains only distinct nodes, while a cycle is a closed walk, where

v 1 = v l .
Sometimes in the literature the walk is also called a path, in that case the path is then called a simple path. Illustrations of a walk, a path and a cycle on a graph can be found in Figure 2.4.

Definition 2.8 (Connected and disconnected graph). A graph G = (V, E) is said to be connected if for every pair of distinct vertices u, v ∈ V there is a path joining them.

A graph that is not connected is referred to as disconnected. The distance between two vertices u, v ∈ V in graph G = (V, E) is length of the shortest path from u to v in G, or ∞ if such path does not exist. Definition 2.9 (Forest, tree and subtree). A graph G when it has no cycles is called acyclic or forest. A connected forest is called tree. A rooted tree is a tree with a specified root vertex v 0 . A subtree is a subgraph of a graph that contains no cycles. When it has also a designated root node is called rooted subtree.

The height of a rooted tree or subtree is the maximum distance between the designated root vertex and any other node in the tree or subtree respectively. Similarly to the way of the notion of walk is extending the notion of path by allowing nodes [Bach, 2008] extended the notion of subtrees to subtree patterns, also known as tree-walks, which can have nodes that are equal. An example of subtree pattern is shown in Figure 2.5.

Graph and subgraph Isomorphism

The first step towards graph comparison is the ability to check whether two graphs are identical or not. The problem of deciding that is called graph isomorphism and is defined as follows:

Definition 2.11 (Graph Isomorphism). Let G = (V, E) and G ′ = (V ′ , E ′ ) be two graphs. We call G and G ′ isomorphic and write G ≃ G ′ , if there exists a bijection shows two graphs which are isomorphic, each being a representation of the well known K 3,3 graph.1 Apart from deciding whether two graphs are identical or not, one could determine whether the graph G contains a subgraph that is isomorphic to G ′ , a problem know as subgraph isomorphism.

φ : V → V ′ with (u, v) ∈ E ⇔ (φ(u), φ(v)) ∈ E ′ ∀u, v ∈ V .
Definition 2.12 (Subgraph Isomorphism). Let G = (V, E) and

G ′ = (V ′ , E ′ ) be two graphs. We call G ′ subgraph isomorphic to G, if there is a subgraph G 0 = (V 0 , E 0 ) ⊆ G : V 0 ⊆ V, E 0 = E ∩ (V 0 × V 0 ) such that exists a bijection φ : V 0 → V ′ with (u, v) ∈ E 0 ⇔ (φ(u), φ(v)) ∈ E ′ ∀u, v ∈ V 0 .

Graph comparison methods

As graphs are rich representations of data with inherited structure, they are consequently a promising tool in many domains, as we have already seen in Section 1.1. A common and challenging problem when dealing with graphs is to be able to compare them and provide a similarity measurement, a problem well-known as graph comparison.

Definition 2.13 (Graph Comparison). Given a set G of graphs, the problem of graph comparison is defined as a function

k : G × G → R such that k(G, G ′ ) for G, G ′ ∈ G quantifies the similarity of G and G ′ .
In this section we review classical approaches to this problem.

Isomorphism-based methods

A first approach towards this problem is to quantify whether two graphs are identical, i.e. isomorphic (see Definition 2.11). This produce a binary similarity measure, which

Chapter 2 Related work on graph comparison equals to 1 when the two graphs are isomorphic, otherwise equals to 0. Despite the fact that this idea of graph isomorphic is intuitive, no efficient algorithm is known for it. The graph isomorphism problem is known to be within NP, but neither a proof of NP-completeness nor a polynomial time algorithm are known [Garey and Johnson, 1979, Chapter 7]. Other similarity measures are based on concepts related to isomorphism, such as subgraph isomorphism or the largest common subgraph. Subgraph isomorphism (see Definition 2.12) is analogous to graph isomorphism but it could be used also when two graphs have different sizes. Unlike, the graph isomorphism problem, the subgraph isomorphism problem has been proven to be NP-complete [Garey and Johnson, 1979, Section 3.2.1]. A similarity measure can also be defined based on the size of the largest common subgraph in two graphs. Unfortunately, also the problem of finding the maximum common subgraph is known to be NP-hard [Garey and Johnson, 1979, Section 3.3].

Graph edit distances

Apart from being computationally expensive, similarity measures based on concepts of isomorphism have another disadvantage. They are too restrictive in the sense that the graphs have to be exactly identical or they should share large identical subgraphs, in order to be consider similar. This is an important problem when we produce graphs from noisy data. More flexible similarity measures that have been proposed in the literature as part of the inexact graph matching problem are similarity measures based on graph edit distances (GED) [START_REF] Gao | A survey of graph edit distance[END_REF]. These GED algorithms are based on the concept of transformation a graph to another one by a finite sequence of graph edit operations, such as node addition or deletion, edge addition or deletion and node or edge relabeling. These operations can have different costs and the similarity measure is defined by the least-cost edit operation sequence. Figure 2.7 illustrates an example of graph edit distance methodology for a pair of node labeled graphs. Unfortunately, finding the optimal cost for a particular application is a hard problem, since it requires solving NP-complete problems as intermediate steps.

Graph kernel methods

As we have seen in Section 2.2 the first approaches proposed to solve the graph comparison problem suffer from intractable computational time, since in the worst case they require exponential runtime, or are hard to parametrize. Another family of approaches, that have been introduced the past few years, come from the statistical learning perspective. This family of approaches, known as Graph Kernels, tackles both the problem ′ a sequence of graph edit operations are applied to transform G to G ′ . More specifically, the first operation is node deletion with its adjacency edges, the second operation is node addition, then edge addition, followed by an edge deletion and a node relabeling.

of graph representation and graph comparison through the exploitation of the graph topology by decomposing the graph into substructures and aggregating statistics over these substructures. This strategy considers a measure of similarity between the graphs as a form of inner product.

Graph kernels are instances of the family of the R-convolution kernels by [START_REF] Haussler | Convolution kernels on discrete structures[END_REF]. R-convolution kernels are a generic way of constructing kernels on a set whose elements are discrete structures such as strings, trees and graphs. The idea is based of decomposing the complex object into discrete structures and compare the respective objects by comparing all pairs of decompositions. Every new decomposition in the graphs would yield a new graph kernel. A first approach would be to decompose the graphs into all possible subgraphs. However, calculating all subgraphs is at least as hard Table 2.1: An overview of the graph kernel methods. From left to right we show the type of subgraphs used, the algorithm, its complexity when that is known and whether the kernel works on unlabeled, discretely, continuous or vector labeled graphs. Note that n is the number of graphs under comparison, v is the maximal number of nodes, e is the maximal number of edges, h is the height of subtree patterns, d is the maximum degree and k is the size of graphlets. Walks [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF]] O(n 2 v 6 ) [START_REF] Mahé | Extensions of marginalized graph kernels[END_REF][START_REF] Vichy | Graph kernels[END_REF] O(n 2 v 3 )

Paths [START_REF] Borgwardt | Shortest-path kernels on graphs[END_REF]] O(n 2 v 4 ) [START_REF] Ralaivola | Graph kernels for chemical informatics[END_REF] Graph lets [START_REF] Horváth | Cyclic pattern kernels for predictive graph mining[END_REF][START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF] O(vd k-1 ) [START_REF] Costa | Fast neighborhood subgraph pairwise distance kernel[END_REF] Subtree Pat-terns [START_REF] Ramon | Graph kernels based on tree patterns for molecules[END_REF]] [START_REF] Mahé | Extensions of marginalized graph kernels[END_REF]Vert, 2009] [Shervashidze et al., 2011] O(nhe + n 2 hv)

O(n 2 v 2 h4 d ) [Bach, 2008] [
as deciding whether two graphs are isomorphic [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF]. As a result, it is necessary to limit the decomposition of the graphs only into specific types of subgraphs that are computable in polynomial time [START_REF] Vichy | Graph kernels[END_REF][START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF].

There are three main categories of graph kernels, graph kernels based on (a) walks [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF] and paths [START_REF] Borgwardt | Shortest-path kernels on graphs[END_REF], (b) small size subgraphs [START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF] and (c) subtree patterns [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF]. Table 2.1 shows a summary of the state of the art of graph kernels grouped per category, while we review extensively each of these categories in the following Sections 2.3.1, 2.3.2 and 2.3.3.

Graph kernels based on walks and paths

Graph kernels based on walks and paths (see Definition 2.7) count the number of matching pairs of walks and paths in two graphs respectively. Different proposed kernels use different methods to compute similarities between walks and paths. For example, Gärtner et al. propose a random walk kernel that counts the number of nodes in the walk which have the same label, which requires O(v 6 ) computational time for a pair of graphs [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF], where v is the number of vertices in the graphs. Vishwanathan in [START_REF] Vichy | Graph kernels[END_REF] reduced the runtime complexity of the random walk kernel for a pair of graphs to O(v 3 ) by restating the problem in terms of Kronecker products. Although, this is an important gain in efficiency, allowing to compute kernel on random walks faster by an order of magnitude, the complexity O(v 3 ) is still too high for many applications. Apart from the computation time, kernels based on random walks have to deal with two extra problems, the tottering problem and the halting problem.

The tottering problem [START_REF] Mahé | Extensions of marginalized graph kernels[END_REF] raises from the fact that walks allow the repetitions of nodes and edges, which means that the same node or edge can contribute repeatedly in the similarity measure. The same can be said for shared cycles or paths as well. Therefore, the similarity score between two graphs can drastically increase, although they two graphs do not share many structural elements. The halting problem [START_REF] Borgwardt | Graph Kernels[END_REF] also arises from the fact that walks allow the repetitions of nodes.

As the repetition of nodes is allowed, the number of walks within a graph is infinitely large. In order to halt the problem, a decaying factor is commonly used to downweight longer walks. The effect of this decaying factor is that longer walks are completely neglected compared to shorter walks.

The marginalized graph kernel [START_REF] Mahé | Extensions of marginalized graph kernels[END_REF] proposed two extensions on the random walk kernels to overcome both the tottering problem and reduce their computation time. They modify the label of each vertex with the use of the Morgan index [START_REF] Morgan | The Generation of a Unique Machine Description for Chemical Structures -A Technique Developed at Chemical Abstracts Service[END_REF], which is defined as

Definition 2.14 (Morgan Index). Given a graph G = (V, E), the Morgan index of order k for node v ∈ V is defined as M k (G, v) = 1 if k = 0 v ′ ∈N (v) M k-1 (v ′ ) otherwise.
(2.2)

Note that the Morgan index of order k for a node v is the number of walks of length k starting at v in that graph G. So incorporating the Morgan index into the label of each vertex, it increases the specificity of labels by adding information with the number of walks staring at that vertex. In addition, they proposed a modification to prevent the walk from coming back to a vertex that was just visited. Another approach based on dynamic programming to speed up the computations of the random walk kernel was proposed in [START_REF] Harchaoui | Image classification with segmentation graph kernels[END_REF], at the cost of considering only walks of fixed size.

[ [START_REF] Borgwardt | Shortest-path kernels on graphs[END_REF] proposed a graph kernel that compares the length of shortest path between pairs of nodes with matching source and sink labels in two graphs, which requires O(v 4 ) complexity time. Ralaivola in [START_REF] Ralaivola | Graph kernels for chemical informatics[END_REF] proposed a specialized graph kernel for chemoinformatics. Their approach is based on molecular fingerprinting techniques and counts labeled paths of length p that can be retrieved by depth-first search from each vertex. This can be an efficient approach for graphs with an average node degree of 2 or 3.

Graph kernels on small size subgraphs

A number of graph kernels have been proposed in the literature that are based on limited size subgraph structures called graphlets. A naive computation of all graphlets of a graph, without considering labels, requires O(v k ) computations, where v is the number of nodes and k is the size of subgraphs, usually k ∈ {3, 4, 5}. Since enumerating all graphlets is prohibitively expensive, even for small k values, [START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF] showed that sampling a fixed number of graphlets suffices to bound the deviation of the empirical estimates of the graphlet distribution from the true distribution and for graphs of degree bounded by d, the exact number of all graphlets of size k can be determined in time O(vd k-1 ). Another kernel is the cyclic pattern kernels [START_REF] Horváth | Cyclic pattern kernels for predictive graph mining[END_REF], which counts pairs of matching cyclic and tree patterns in two graphs. In the general case, the cyclic pattern kernel is NP-hard, but in specific cases the kernel can be computed efficiently. Finally [START_REF] Costa | Fast neighborhood subgraph pairwise distance kernel[END_REF] proposed the neighborhood subgraph pairwise distance kernel, which decomposes a graph into all pairs of neighborhood subgraphs of small radius r at increasing distances d.

Graph kernels on subtree patterns

In 2003, Ramon and Gärtner were the first to introduce a graph kernel based on subtree patterns [START_REF] Ramon | Graph kernels based on tree patterns for molecules[END_REF]]. The Ramon-Gärtner subtree kernel with subtree height h compares all pairs of nodes from two labeled graphs by iteratively comparing their neighborhoods. Although the subtree kernel is more expressive than kernels based on walks, unfortunately it is computationally expensive. For a set of n graphs it requires O(n 2 v 2 h4 d ), where v is the number of nodes, h is the height of subtree patterns considered and d is the maximum node degree in the graph set. Both subtree kernels by Mahé and Vert [Mahé and Vert, 2009] and Bach [Bach, 2008] refine the Ramon-Gärtner subtree kernel for application in chemoinformatics and hand-written digit recognition respectively. In [Mahé and Vert, 2009], Mahé and Vert proposed a new kernel with a parameter to control the complexity of the subtrees used as features to represent the graphs. This parameter allows to smoothly combine graph kernels based on walks and kernels based on subtrees. In [Bach, 2008], Bach proposed a graph kernel that considers α-ary subtrees with most α children per node. Unfortunately, the complexity of both kernels are still exponential in the smoothing and a parameter respectively, and both kernels are feasible on small size graphs only. Recently a new kernel with subtree patterns was introduced by Shervashidze [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF]. The Weisfeiler-Lehman subtree kernel uses the Weisfeiler-Lehman test of isomorphism [START_REF] Weisfeiler | A reduction of a graph to a canonical form and an algebra arising during this reduction[END_REF] to efficiently compute subtree patterns up to height h for discretely labeled graphs.

Chapter 3

The pyramid quantized In this chapter we introduce a novel method, the pyramid quantized Weisfeiler-Lehman graph representation that compares labeled graphs with complex labels. Our method makes use of the efficiency of the Weisfeiler-Lehman kernel [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF] for discrete labels by considering a pyramid quantization strategy that approximates the continuous or vector labeled graphs with a sequence of discretely labeled graphs.

Firstly, we introduce the Weisfeiler-Lehman test of isomorphism, and then we explore how key concepts of the test is used in the framework of the Weisfeiler-Lehman kernel for comparing discrete labeled graphs in Section 3.1 and in Section 3.2, respectively.

Then in Section 3.3 we present our pyramid quantization scheme and we conclude by exploring different strategies for combing the pyramid levels in Section 3.4.

The Weisfeiler-Lehman test of isomorphism

Our proposed algorithm uses the statistics introduced by the Weisfeiler-Lehman kernel, which exploits the key concepts from the Weisfeiler-Lehman test of isomorphism [START_REF] Weisfeiler | A reduction of a graph to a canonical form and an algebra arising during this reduction[END_REF] and more specifically its one dimensional variant. Given

G = (V, E, L), G ′ = (V ′ , E ′ , L ′ ), with discrete labelings L : V → Σ and L ′ : V ′ → Σ over vertices,
where Σ is a vertex label set and the maximum number of iterations h.

1: i ← 0 2: repeat 3: if i = 0 then { Multiset-label initialization } 4: M i (v) := l 0 (v) = L(v).
5:

else if i ≥ 1 then { Multiset-label determination } 6: Assign a multiset-label M i (v) to each node v in G and G ′ which consists of the multiset {l i-1 (u)|u ∈ N (v)}, where N (v) denotes the neighbor set of v. { Sorting each multiset } 7:
Sort the elements in M i (v) in ascending order.

8:

Concatenate the elements in M i (v) into a string s i (v).

9:

Add l i-1 (v) as a prefix to s i (v). { Sorting the set of multisets } 10:
Sort all of the strings s i (v) for all v from G and G ′ in ascending order.

{ Label compression via hashing }

11:

Map each string s i (v) to a new compressed label using a function f : Σ * → Σ such that f (s i (v)) = f (s i (w)) ⇐⇒ s i (v) = s i (w). { Relabeling } 12: Set l i (v) := f (s i (v)
) for all nodes in G and G ′ .

13:

end if

14: i ← i + 1 15: until {l i (v)|v ∈ V } = {l i (v ′ )|v ′ ∈ V ′ } or i > h
two graphs G and G ′ the Weisfeiler-Lehman test of isomorphism determines whether they are isomorphic or not. Algorithm 3.1 provides pseudocode for the one dimensional Weisfeiler-Lehman test of graph isomorphism.

The key idea of the Weisfeiler-Lehman test of graph isomorphism is the construction of augmented node labels from all the neighbor nodes and the compression into new short labels. This process is repeated until either the label sets of the two graphs under comparison differ or the maximum number of iterations has been reached. If the two label sets differ, then the two graphs are non-isomorphic, while if the maximum number of iterations is reached and the two label sets don't differ, then the test was not able to determine that they are not isomorphic. [START_REF] Cai | An optimal lower bound on the number of variables for graph identification[END_REF] provide examples of graphs that cannot be distinguished by this algorithm or its higher-dimensional variants. for all nodes u ∈ V do 3:

for all nodes v ∈ N (u) do 4:

append the pair (G, u) to bucket l i-1 (v).1

5:

end for 6:

s i (u) ← l i-1 (u) 7:
end for 8: end for

9: for k = 1 → |Σ * | do 10: for all (G, u) in bucket k do 11: append k to s i (u) in G 12:
end for 13: end for that all identical strings will be mapped to the same compressed labels, as they occur in blocks. This implementation requires that the alphabet Σ has to be sufficiently large in order for f to be injective. For two graphs G = (V, E) and

G ′ = (V ′ , E ′ ) of order |V | = |V ′ | = v, |Σ| = 2v is sufficient.
Of course any other injective mapping could be used and will give an equivalent result. Finally, it should be noted that in Algorithm 3.1 the same node labeling function l 0 , . . . , l h has been used form both G and G ′ in order not to overlap the notation. The same simplified notation will be used through the chapter assuming without loss of generality that the domain of these functions l 0 , . . . , l h is the set of all nodes in the input graphs. In the case of Algorithm 3.1 the domain is defined

in V ∪ V ′
Complexity The efficiency of the compression of the labels via the hashing scheme described above depends on the complexity of the sorting method. Given the fact that the labels of the graphs are discrete and their cardinality is upper-bounded by |Σ| = 2v, the counting sort algorithm is appropriate for sorting the multisets. The counting sort algorithm has a complexity of O(n + k), where n is the number of elements to be sorted and k the number of buckets. In our case the number of elements to be sorted for the multisets M i (v) (Line 7 in Algorithm 3.1) is in the worst case linear to the maximal number of edges e and if we select a k = O(e), we end up with a complexity of O(e).

Analytical pseudocode for the counting algorithm is provided in Algorithm 3.2. Sorting the resulting strings s i (v) (Line 10 in Algorithm 3.1) is also of time complexity O(e) via the radix sort algorithm. As the Weisfeiler-Lehman test runs in h iterations the total runtime is O(he).

Link with subtree patterns There is a strong link between the compressed labels and subtree patterns (see Definition 2.10). More specifically a compressed label l i (v) corresponds to a subtree pattern rooted at node v of height i. For example, in Figure 3.1 if a node has a new compressed label, 9, this means that there is a subtree pattern of height 1 rooted at this node, where this root node has label 3 and its neighbor nodes have labels 1, 2 and 3 respectively.

The linear Weisfeiler-Lehman subtree kernel

As mentioned above in Section 3.1 the Weisfeiler-Lehman test of graph isomorphism is iterative. For each iteration i, we obtain new compressed labels l i (v) for all nodes v as we have seen in Line 12 in Algorithm 3.1. We emphasize that the labeling is concordant between the graphs under comparison, that means if and only if the nodes in G and G ′ have identical string s i (v), they will get identical new labels l i (v). These compressed labels, i.e. the subtree patterns, have been recently employed in a kernel for graph comparison, the Weisfeiler-Lehman subtree kernel [Shervashidze et al., 2011, Definition 4] which is defined as follows:

Definition 3.1 (The linear Weisfeiler-Lehman subtree kernel). Let G and G ′ be graphs. Define Σ i ⊆ Σ as the set of symbols that occur as node labels at least once in G or G ′ at the end of the i-th iteration of the Weisfeiler-Lehman algorithm. Let Σ 0 be the set of original node labels of G and G ′ . Assume all Σ i are pairwise disjoint. Without loss of generality, assume that every Σ i = {σ i1 , . . . , σ i|Σ i | } is ordered. Define a map

η i : {G, G ′ } × Σ i → N such that η i (G, σ ij ) is the number of occurrences of the letter σ ij in the graph G.
The linear Weisfeiler-Lehman subtree kernel on two graphs G and G ′ with h iterations is defined as

k (h) l-W Lsubtree (G, G ′ ) = φ (h) (G), φ (h) (G ′ ) (3.1)
where

φ (h) (G) = η 0 (G, σ 01 ), . . . , η 0 (G, σ 0|Σ 0 | ), . . . , η h (G, σ h1 ), . . . , η h (G, σ h|Σ h | ) (3.2)
and

φ (h) (G ′ ) = η 0 (G ′ , σ 01 ), . . . , η 0 (G ′ , σ 0|Σ 0 | ), . . . , η h (G ′ , σ h1 ), . . . , η h (G ′ , σ h|Σ h | ) (3.3)
Table 3.1: An example of the linear Weifeiler-Lehman subtree kernel between the two graphs shown in Figure 3.1(a) for subtree patterns up to depth h = 1. The first row shows the labels encountered up to depth h = 1, which contains the original node labels Σ 0 as well as the compressed node labels Σ 1 for the iteration i = 1. The second and the third row contains the histogram over the labels for graph G and G ′ respectively, while the fourth row shows the final kernel value between the given graphs.

Original node labels Σ 0 Compressed node labels Σ 1 Labels {Σ 0 , Σ 1 } = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

φ (1) (G) = (3, 1, 3, 0, 3, 0, 1, 1, 1, 1, 0) φ (1) (G ′ ) = (2, 2, 3, 1, 1, 1, 2, 0, 1, 0, 1) k (1) l-W Lsubtree (G, G ′ ) = φ (h) (G), φ (h) (G ′ ) = 23
Note that the features φ (h) are histograms of the original and compressed labels, i.e. histograms of subtree patterns of depths 0, . . . , h. Table 3.1 shows an example of the linear Weisfeiler-Lehman subtree kernel k

(1) l-W Lsubtree (G, G ′ ) and their respective features φ (1) between the two graph G, G ′ shown in Figure 3.1(a) for subtree patterns up to depth

h = 1.
Complexity A key advantage of these statistics φ (h) (G) is that they are computable in linear time in the number of edges in the graphs and in the depth of the subtree patterns.

More specifically, for n graphs and subtree patterns of depth up to h, the complexity of a joint computation of all statistics over all graphs is O(nhe+n 2 hv), where e is the maximal number of edges, and v the maximal number of vertices [Shervashidze et al., 2011, Theorem 7]. This complexity can be achieved by processing all n graphs simultaneously, meaning conducting the steps of multiset label determination, sorting each multiset, label compression and relabeling of Algorithm 3.1 for all n graphs simultaneously. After we have calculate the φ(h) feature explicitly on each graph G, we can calculate the pairwise inner products efficiently. Moreover the use of an efficient hashing scheme allows the algorithm to enumerate relevant (non-zero) dimensions of an exponentially sized feature space efficiently. In this way, the matching can be done in constant time, and the hash needs only to store patterns present in the graph instances, thereby maintaining constant complexity across iterations. As before, in order for the mapping scheme f to be injective, a sufficiently large label set Σ is required. In the case of n graphs and h iterations, |Σ| = nv(h + 1) suffices.

Memory requirements in practice

The memory requirements of these statistics φ (h) (G) in practice depends on the used learning setting. In the case of an inductive learning setting, where initially a kernel is computed over only the training set of graphs, in order to classify any test graph the explicit mapping scheme f occurred in the training set is required. That means that one needs to maintain record of all the mappings l i (v) = f (s i (v)) for each iteration i and for each distinct s i (v), ending with a O(neh) memory in the worst case. In contrast, if a trasductive setting is used, where the test set is already known, the kernel matrix of the whole date set (both training and testing) can be computed without having to keep the mapping f , minimizing the memory requirements.

In addition to these computational benefits, linear Weisfeiler-Lehman graph kernels have been shown to perform comparably to or better than a number of more computationally complex kernels [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF]. Finally, we note that the linear Weisfeiler-Lehman algorithm at depth 0 computes exactly the bag of words representation commonly used in natural language processing [START_REF] Harris | Distributional structure[END_REF][START_REF] Ko | A study of term weighting schemes using class information for text classification[END_REF] and computer vision [Qiu, Fei-fei, 2005].

The pyramid quantization strategy for continuous labels

The Weisfeiler-Lehman algorithm is efficient precisely because it makes use of a discrete labeling over nodes, which enables an efficient hashing scheme in order to scale linearly in the number of edges and in the height of subtree patterns. A problem occurs when extending this method to continuous vector labeled graphs. To overcome this, we propose a pyramid quantization strategy similar to the one used by [Grauman and Darrell, 2007a,b] to determine a logarithmic number of discrete labelings with increasing granularity for which we run the Weisfeiler-Lehman algorithm. In other words, we approximate a graph representation with continuous valued labels as a sequence of graphs with discrete labels of increasing granularity.

The pyramid quantization strategy

Given a vector labeled graph G = (V, E, L), where L : V → R d is the function assigning a d-dimensional vector label to each vertex, we want to derive a hierarchical decomposition of R d as multi-resolution quantizations. The multi-resolution quantizations will then be used to determine the discrete labeling of increasing granularity. This can be expressed as a two step process, first we construct a quantization function Q (l) : R d → Σ image2 of the set V under L. Note that the single quantization bin for Q (0) is big enough so that all data points from the image of the set V under L receive the same discrete label, while as quantization resolution moves from coarser to finer, we end up with Q (L) that contains quantization bins that are small enough so each unique data point from the image of the set V under L falls into its own quantization bin.

The second step is to compose the quantization function Q (l) with the labeling function L, ∀l ∈ {0, . . . , L}, so we can approximate our initial vector labeled graph G as a sequence of graphs with discrete labels of increasing granularity:

G = (V, E, L) Q (l) • L ≈ G (0) , . . . , G (L) = (V, E, L (0) ), . . . , (V, E, L (L) ) , (3.4)
where

L (l) : V → Σ (l)
0 is defined to be Q (l) • L, and Σ

(l) 0 is the discrete label alphabet for a given level l of quantization. Note that the topology of the graph does not change in the sequence of graphs, only the continuous labels are discretized. To achieve the discretization of the labels, we explore two different strategies for the quantization function: (a) a fixed binning scheme and (b) a data guided one in the following sections.

Fixed Binning

In the fixed binning scheme the quantization function recursively decomposed into quantization resolution, where in each quantization level the bins that partition the space are half the size in all d dimensions of the input space compared to the previous one.

The number of bin of each Q (l) ) is given by r

(l) = D 2 l √ d d
, where D is the number of unique values in the image of the vertex set V under label function L. The fixed binning scheme can be performed efficiently in high dimensions using, e.g. k-d trees [START_REF] Louis | Multidimensional binary search trees used for associative searching[END_REF]. The complexity of the resulting quantization is bounded by

O(d max(v, k)L),
where d is the dimension of the input space, v is the number of vertices to be quantized, k is the maximum histogram index value in a single dimension and L is the number of pyramid levels [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF]. With constraining k ≤ v and ensuring that L is logarithmic in v, we end up with a simplified complexity of O(dv log v).

Data guided binning

The idea of data guided binning is to derive a hierarchical but data-dependent decomposition of the feature space that will encode the multi-dimensional features as multiresolution histograms with non-uniformly shaped bins. The first step in this scheme is to generate the structure of the data guided pyramid hierarchy that will define the bin placements. To achieve this we perform an agglomerative hierarchical clustering on image of the vertex set V under the labeling function L using the Ward's minimum variance method [START_REF] Ward | Hierarchical Grouping to Optimize an Objective Function[END_REF]. 3 Ward's methods minimizes the total within-cluster sum of squares criterion which is defined as follow for two clusters i, j:

d(i, j) = 2n i n j (n i + n j ) x i -x j 2 (3.5)
where n i and n j are the number of elements in clusters i and j, x i and x j are the centroids of clusters i and j and • 2 denotes the Euclidean distance. At the initial step, all clusters are singletons (i.e. clusters containing a single unique point). Then we apply the algorithm recursively and at each step the pair of clusters with minimum between-cluster distance given from Equation 3.5 are merged.

Once the data guided bins have been constructed (i.e. the centroid of each cluster in all L levels has been determined), we can embed each d-dimensional data point c i ∈ R d ∀i to the multi-resolution quantization bins of L levels, where in each level l there are 2 l bins. In order for a point c i to be mapped at the correct bins at the quantization pyramid, we need to compare it to the two appropriate centroids at each l pyramid level using the Euclidean distance and pushed down the hierarchical tree along that branch that is rooted with the closest centroid at each level. At each comparison with the centroids, we also keep a record of a binary bin index p with its path along the quantization pyramid. As the quantization pyramid has L level, in total 2L distances must be computed between a point and the pyramid's bin centroids. Concerning the space requirements, this approach requires O(2

L ) = O(v) d-dimensional feature vectors
to store for all the bin centroids of the hierarchical pyramid, since L is logarithmic in v, and O(L) = O(log 2 v) binary indexes for a set of v feature vectors. Note that the bin centroids are calculated only once using the Ward's method during the training.

Finally, any other hierarchical clustering technique, could also be used without changing the main idea.

In Figure 3.2, we illustrate the difference between the two pyramid quantization strategies defined above for the same 2D space. In Figure 3.2(a) we see that the space is partitioned into uniform-shaped bins, while in Figure 3.2(b) the data themselves determine the partitioning, as a result the bins better decompose the space into clusters.

Chapter In both figures, the left plot contains the coarser resolution level, while the right plot contains the finer one. In Figure 3.2(a) the complex space is carved into uniformly-shaped partitions, while in Figure 3.2(b), the data guide the resulting partition of the complex space. As a result, the bins on the right are better positioned to decompose the space based on the data clusters.

The intersection Weisfeiler-Lehman subtree kernel

Independent of the binning strategy we follow, each graph with vector valued labels after the pyramid quantization step described in Section 3.3.1 is represented as a sequence of graphs with nested quantizations of increasing granularity of discrete labels as described in Equation 3.4. We run the Weifeiler-Lehman algorithm on each graph G (l) of the sequence in order to produce the features φ (l) (h) of subtree patterns up to a given height h.

Definition 3.2 (The intersection Weisfeiler-Lehman subtree kernel).

Let G (l) = (V, E, L (l) ) and G ′(l) = (V ′ , E ′ , L ′ (l)
) be two graphs of the same quantization level l, where l) as the set of symbols that occur as node labels at least once in G (l) or G ′(l) Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation 53 at the end of the i-th iteration of the Weisfeiler-Lehman algorithm. Let Σ (l) 0 be the set of original node labels of G (l) and G ′(l) . Assume all Σ (l) i are pairwise disjoint. Without loss of generality, assume that every Σ

L (l) : V → Σ (l) 0 and L ′ (l) : V ′ → Σ (l) 0 , of two vector labeled graphs G = (V, E, L) and G ′ = (V ′ , E ′ , L ′ ), where L : V → R d and L ′ : V ′ → R d . Define Σ (l) i ⊆ Σ (
(l) i = {σ (l) i1 , . . . , σ (l) i|Σ (l) i | } is ordered. Define a map η i : {G (l) , G ′(l) } × Σ (l) i → N such that η i (G (l) , σ (l) ij ) is the number of occurrences of the letter σ (l) ij in the graph G (l) .
The intersection Weisfeiler-Lehman subtree kernel on two graphs G and G ′ with h iterations is defined as

k (h) i-W Lsubtree (G (l) , G ′(l) ) = I φ (l) (h) (G (l) ), φ (l) (h) (G ′(l) ) (3.6)
where

φ (l) (h) (G (l) ) = η 0 (G (l) , σ (l) 01 ), . . . , η 0 (G (l) , σ (l) 0|Σ (l) 0 | ), . . . , η h (G (l) , σ (l) h1 ), . . . , η h (G (l) , σ (l) h|Σ (l) h | ) φ (l) (h) (G ′(l) ) = η 0 (G ′(l) , σ (l) 01 ), . . . , η 0 (G ′(l) , σ (l) 0|Σ (l) 0 | ), . . . , η h (G ′(l) , σ (l) h1 ), . . . , η h (G ′(l) , σ (l) h|Σ (l) h |
) and

I φ (l) (h) (G (l) ), φ (l) (h) (G ′(l) ) = h i=0 |Σ (l) i | j=1 min η i (G (l) , σ (l) ij ), η i (G ′(l) , σ (l) ij ) (3.7)
Note that the features φ (l) (h) are histograms of the original and compressed labels, i.e. histograms of subtree patterns of depths 0, . . . , h for a given quantization level l, while the intersection Weisfeiler-Lehman subtree kernel counts the overlap of features φ

(l) (h) between two graphs G (l) = (V, E, L (l) ) and G ′(l) = (V ′ , E ′ , L ′ (l)
) which match at the given quantization level l. Note that the intersection Weisfeiler-Lehman kernel for a given binning resolution l is a positive-definite similarity function [START_REF] Odone | Building kernels from binary strings for image matching[END_REF]. 4An example of the quantization step of the pyramid quantized Weisfeiler-Lehman graph representation is illustrated in Figure 3.3. Given the graphs G = (V, E, L), G ′ = (V ′ , E ′ , L ′ ) with continuous vector labels in their nodes, i.e. L : V → R d and L ′ :

V ′ → R d , shown in
G G' [2 5] [3 6] [3 6] [3 7] [1 3] [1 3] [1 3] [3 6] [3 7] [3 6] [2 6] [2 4] [1 3] [1 2]
(a) Initial graphs with multi-dimensional labels.

[

3 6] [3 7] [2 4] [2 5] [2 6] [1 2] [1 3] 2 Labels 4 Labels (b) Hierarchical decomposition of the multi-dimensional space. G G' 1 1 1 1 2 2 2 1 1 1 1 1 2 2
(c) Relabeled graphs of the quantization level 1 with 2 1 = 2 number of discrete labels.

G ′ = (V ′ , E ′ , L ′ ), where L : V → R 2 , L ′ : V ′ → R 2
and the label of each node v is defined as its degree of node d(v) and the summation of the degree of nodes of its neighborhoods

N v , i.e. L(v) = [d(v), u∈Nv d(u)].
G (1) = (V, E, L (1) ) and G ′(1) = (V ′ , E ′ , L ′ (1) ), where L (1) : V → Σ (1) 0 , L ′ (1) : V ′ → Σ
(1) 0

and |Σ

(1) 0 | = 2 is the coarser resolution level l = 1 with two labels, while Figure 3.3(d) shows the two relabeled discretized graphs

G (2) = (V, E, L (2) ) and G ′(2) = (V ′ , E ′ , L ′ (2) ), where L (2) : V → Σ (2) 0 , L ′ (2) : V ′ → Σ
Q (l) • L ≈ l ∈ {1, 2} G (1) , G (2) = (V, E, L (1) ), (V, E, L (2) )
and

G ′ = (V ′ , E ′ , L ′ ) Q (l) •L ′ ≈ l ∈ {1, 2} G ′(1) , G ′(2) = (V ′ , E ′ , L ′ (1) ), (V ′ , E ′ , L ′ (2) )
also shown in Figure 3.3(c) and in Figure 3. 3(d), where

L (l) : V → Σ (l) 0 and L ′ (l) : V ′ → Σ (l) 0 , while |Σ (1)
0 | = 2 is the coarser resolution with two labels and |Σ

(2) 0 | = 4 is the finer resolution with four labels. For each level l of the graph sequence the Weisfeiler-Lehman algorithm is applied to produce the φ (l) (h) (G (l) ), while for each pair {G (l) , G ′(l) } for all quantization levels l the intersection Weisfeiler-Lehman subtree kernel will determine the similarity between the two graphs for that level of quantization.

The monotonicity property of the pyramid quantized Weisfeiler-

Lehman kernel

We may show the following monotonicity property of the pyramid quantized Weisfeiler-Lehman kernel described in Section 3.

∀l, G (l) , G ′(l) I φ l (h) (G (l) ), φ l (h) (G ′(l) ) ≥ I φ l+1 (h) (G (l+1) ), φ l+1 (h) (G ′(l+1) ) , (3.8)
where φ l (h) (G (l) ) is the histogram of subtree patterns of height h computed at pyramid level l, and level l + 1 is more granular.

Proof. We first note that the number of subtree patterns of a given depth, h, of the Weisfeiler-Lehman algorithm is dependent only on the topology of the graph, and not on the graph labeling:

φ l (h) (G (l) ) 1 = v • (h + 1) ∀l (3.9)
where v is the number of vertices in the graphs. We next note that the number of vertex labels is strictly monotonic in the pyramid level, |Σ l | < |Σ l+1 |, and that for each label σ ∈ Σ l at level l, there exist a non-empty set of labels S ⊂ Σ l+1 at level l + 1 such that Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation

L l+1 (u) ∈ S ⇐⇒ L l (u) = σ.
To complete the proof, we observe that

∀G (l) ∀l φ l (h) (G (l) ) 1 = φ l+1 (h) (G (l+1) ) 1 ∧ φ l (h) (G (l) ) 0 < φ l+1 (h) (G (l+1) ) 0 =⇒ ∀G (l) , G ′(l) ∀l I φ l (h) (G (l) ), φ l (h) (G ′(l) ) ≥ I φ l+1 (h) (G (l+1) ), φ l+1 (h) (G ′(l+1) ) , (3.10)
where • 0 is the ℓ 0 pseudo norm.

As the Weisfeiler-Lehman algorithm with h = 0 specializes to the bag of words model, we have as a result that our graph kernel for continuous vector valued node labels strictly generalizes the pyramid match kernel [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF].

Exploring the pyramid quantized Weisfeiler-Lehman features

Given a set of vector labeled graphs

G = {G i = (V i , E i , L i )} 1≤i≤n where L : V → R

The pyramid quantized Weisfeiler-Lehman kernel

Applying the intersection Weisfeiler-Lehman subtree kernel (see Definition 3.2) for each pair of graphs G (l) , G ′(l) for all the pyramid levels from Equation 3.4, we end up with a sequence of intersection Weisfeiler-Lehman kernels for a given height h of subtree patterns :

K (0) (h) (G (0) , G ′(0) ), . . . , K (L) (h) (G (l) , G ′(L) ) (3.11)
where l) ) . Since we have a sequence of Weisfeiler-Lehman kernels from the different quantization levels and taking also into consideration the observation by [START_REF] Gert | A statistical framework for genomic data fusion[END_REF]] that using multiple kernels instead of a single one can enhance the interpretability of a decision function and improve its performance, Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation 57 we would like to combine this sequence of kernels into a single one. A convenient approach is to consider that the kernel K(G, G ′ ) is actually a convex combination of basis kernels:

K (l) (h) (G (l) , G ′(l) ) = I φ (l) (h) (G (l) ), φ (l) (h) (G ′(
K (h) (G, G ′ ) = L l=0 d l K (l) (h) (G (l) , G ′(l) ), with d l ≥ 0, L l=0 d l = 1.
(3.12)

For determining the weights d l we consider two different approaches a automatic way through the framework of multiple kernel learning and another through a fixed weight scheme. Remember that for a single kernel, where {x i , y i } n i=1 is the learning set with x i belongs to some input space X and y i ∈ Y is the target value for pattern x i the solution of the learning problem has the form :

f (x) = n i=1 α i K(x, x i ) + β (3.13)

Multiple kernel learning

The automatic determination of the weights d l of the linear combination of our multiple kernels l) , G ′(l) ) as well as the coefficients α i , β in a single optimization problem is known as the multiple kernel learning (MKL) problem [START_REF] Zien | Multiclass multiple kernel learning[END_REF][START_REF] Sonnenburg | Large scale multiple kernel learning[END_REF][START_REF] Gert | A statistical framework for genomic data fusion[END_REF][START_REF] Rakotomamonjy | Stéphane[END_REF]. The multiple kernel learning approach addresses the problem through a weighted ℓ 2 norm regularization formula. In addition, a ℓ 1 norm is posed as a constraint on the kernel weights a i . This additional constraint encourages sparse set of basis kernels as an inherited property from the ℓ 1 norm. The primal MKL problem is defined as

K (l) (h) (G (
min {f l },β,ξ i ,d l 1 2 L l=0 1 d l ||f l || 2 H l + C n i=1 ξ i s.t. y i L l=0 f l (G (l) i ) + y i β ≥ 1 -ξ i ∀i (3.14) ξ i ≥ 0 ∀i L l=0 d l = 1, d l ≥ 0 ∀l
where each function f l belongs to a different RKHS H l associated with a kernel K (l) (k) . Note that the smaller the d l is, the smoother f l should be. When d l = 0, ||f l || H l is also equal to zero to yield a finite objective value. MKL transforms the problem into a smooth and convex optimization problem and uses a gradient descent approach to solve it.

Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation

Fixed weight kernel

Due to the constraint of the ℓ 1 norm on the weight the multiple kernel learning leads to sparse solutions, which sometimes could result in poor performances when all the pyramid level contain approximately equal important information. In order to overcome this problem we additionally consider a fixed weight scheme for combing the different pyramid levels of the quantized Weisfeiler-Lehman kernel, and more specifically an equal weight. That mean that the final kernel is defined as

K (h) (G, G ′ ) = L l=0 d l K (l) (h) (G (l) , G ′(l) ), where d l = 1 L + 1 .
(3.15)

Visualization

As the pyramid quantized Weisfeiler-Lehman kernel is defined to be a linear combination of the intersections of the histograms of subtree patterns up to a given height h and as the intersection kernel can be considered as a "quasi-linear" kernel [START_REF] Vedaldi | Multiple kernels for object detection[END_REF],

we may use these properties to develop visualizations that approximate the learned discriminant functions. We note that a discriminant function for class c has the form:

f c (G) = b + L l=0 d l j α lj I φ (l) (h) (G (l) j ), φ (l) (h) (G (l) ) ≈ b + L l=0 d l w l , φ (l) (h) (G (l) ) (3.16)
where l indexes the levels of the pyramid and j indexes over the samples in the training set. At each pyramid level l there is exactly one subtree pattern of height h rooted at each vertex of the graph. We may generate for each vertex v a visualization of the function by coloring each vertex by the weight in w i corresponding to the subtree pattern rooted at that node. We may additionally sum the weights over all levels of the Weisfeiler-Lehman iterations. Due to the bias term, b, the visualizations show only the relative contribution of a region of the graph to the discriminant function.

Elastic net on the pyramid quantized Weisfeiler-Lehman subtree features

In order to explore the contribution of each quantized Weisfeiler-Lehman subtree feature l) ) for all the quantized pyramid levels l and for all depths up to depth h, we make use of the statistical estimator Elastic Net, which is described in detail in Section 5.1.2.

φ (l) (h) (G (
We note that the Elastic Net combines ℓ 1 with ℓ 2 regularization in order to appropriately trade off sparsity with a low variance estimator in the case of correlated signals. Formally, Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation

59 if φ (l) (h) (G (l)
i ) is a feature vector of subtree pattern up to height h for a given quantization level l for a graph G i , the elastic net computes β = arg min

β∈R d λ 2 β 2 2 + λ 1 β 1 + 1 n n i=1 β, φ (l) (h) (G (l) i ) -y i 2 , (3.17)
where λ 1 , λ 2 ≥ 0 are scalar regularization parameters. This objective includes the lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] and ridge regression [START_REF] Tikhonov | Solution of incorrectly formulated problems and the regularization method[END_REF] as special cases by setting λ 2 or λ 1 to zero, respectively. We can see this as a tradeoff between the high degree of sparsity achieved by the lasso, and the low variance estimates achieved by ridge regression.

Visualization A number of discriminative learning approaches have been applied to fMRI analysis including the wide spread generalized linear model [Bartels et al., 2007, Bartels andZeki, 2004a], support vector machines [START_REF] Song | Comparative study of svm methods combined with voxel selection for object category classification on fmri data[END_REF][START_REF] Laconte | Support vector machines for temporal classification of block design fmri data[END_REF], independent component analysis [Bartels andZeki, 2004b, 2005] and kernel canonical correlation [Hardoon et al., 2007[START_REF] Blaschko | Augmenting feature-driven fMRI analyses: Semi-supervised learning and resting state activity[END_REF], 2011]. All these methods have to deal with (a) data that lie in a high-dimensional space, with ten of thousands of voxels, (b) a small number of samples, due to the high cost and time consuming nature of the fMRI acquisition procedure, and (c) high levels of noise that arise from different sources, such as system noise and random neural activity. In order to overcome the problem of curse of dimensionality, some approaches select features either by a predefined set of regions of interest (ROIs) using either prior knowledge [START_REF] Demirci | A projection pursuit algorithm to classify individuals using fMRI data: Application to schizophrenia[END_REF][START_REF] Wang | Training fMRI classifiers to discriminate cognitive states across multiple subjects[END_REF], or statistical methods [START_REF] Mitchell | Learning to decode cognitive states from brain images[END_REF][START_REF] Amir | Creating probabilistic maps of the face network in the adolescent brain: A multicentre functional mri study[END_REF] such as a t-test [START_REF] Mitchell | Learning to decode cognitive states from brain images[END_REF], analysis of variance (ANOVA) [START_REF] Cox | fMRI 'brain reading': detecting and classifying distributed patterns of fMRI activity in human visual cortex[END_REF]]. The main disadvantages in the use of ROIs are (a) such regions are frequently defined within a reference space, which raises the issue of misregistrations, (b) in practice people might perform "double dipping" [START_REF] Kriegeskorte | Circular analysis in systems neuroscience: the dangers of double dipping[END_REF] in the data in order to find the set of ROIs and hence significantly skew the results and (c) in the case of absence of prior knowledge they are undefined. Therefore, fully exploratory methods are preferred.

fMRI analysis is particularly suited to sparsity regularization due to the intrinsic high dimensional nature of fMRI data and the expense of collecting large numbers of samples. Moreover, sparsity regularization methods do not require a predefined set of ROIs,

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 63 are fully exploratory and are also mathematical appealing. Previous works that have explored sparsity regularization in fMRI include [START_REF] Carroll | Prediction and interpretation of distributed neural activity with sparse models[END_REF], Ng et al., 2012b].

Although the aforementioned methods perform well in analyzing fMRI data, they treat the fMRI prediction as a linear combination of functions over individual voxels, ignoring either the 3D structure of the brain and they cannot capture potentially complex interactions between voxels. On the other hand, graph-theoretic methods can model such information through the rich representations of networks of data, and are consequently a promising representation for neural populations. The most common use in the fMRI analysis is modeling the network of brain connectivity [START_REF] Supekar | Network analysis of intrinsic functional brain connectivity in alzheimer's disease[END_REF][START_REF] Liu | Disrupted small-world networks in schizophrenia[END_REF], under both healthy conditions (e.g. age-related changes [START_REF] Fair | Functional brain networks develop from a "local to distributed" organization[END_REF][START_REF] Supekar | Development of large-scale functional brain networks in children[END_REF]) and diseases (e.g. Alzheimer's [START_REF] Supekar | Network analysis of intrinsic functional brain connectivity in alzheimer's disease[END_REF] or Schizophrenia [START_REF] Liu | Disrupted small-world networks in schizophrenia[END_REF]), and the network's analysis, including modularity, small-worldness and the existence of highly connected network hubs. Graph kernel methods have also been used in fMRI connectivity graphs for brain decoding [START_REF] Mokhtari | Decoding brain states using backward edge elimination and graph kernels in fMRI connectivity networks[END_REF].

In this section, we approach the fMRI analysis by representing fMRI recordings as graphs, and we use the pyramid quantized Weisfeiler-Lehman graph representation to learn from the interconnections between voxels. Our approach has an enriched capacity to model such dependencies by considering interconnections between voxels which may be functionally important.

The remaining of the section is organized as follows: in Section 4.1.2 we present the data that we use in this study, Section 4.1.3 is dedicated to the methodology, in Section 4.1.4

we show the experimental setting and the results, and we conclude in Section 4.1.5 with a discussion over the obtained results and the perspectives of this work.

Cocaine Addiction Dataset

The cocaine addiction dataset consists of the contrast maps from 16 cocaine addicted individuals and 17 control subjects performing a neuropsychological experiment, called a drug Stroop experiment [START_REF] Goldstein | Anterior cingulate cortex hypoactivations to an emotionally salient task in cocaine addiction[END_REF]. The drug Stroop experiment has a block design, that included six sessions, with each of them having different conditions.

The two varying conditions are the monetary reward (50¢, 25¢ and 0¢) and the cue shown (drug words, neutral words). The session consists of an initial screen displaying the monetary reward and then presenting a sequence of forty words in four different colors (yellow, blue, red or green). The subject was instructed to press one of four buttons matching the color of the word they had just read. The subjects were rewarded for correct performance depending on the monetary condition. The fMRI data were acquired a 4Tesla whole-body Varian/Siemens system. The blood-oxygen-level dependent scans to be discarded to avoid non-equilibrium effects in the fMRI signal). Padding was used to minimize subject motion, which was also monitored immediately after each fMRI run [START_REF] Honorio | Can a single brain region predict a disorder[END_REF].

The subjects that complied to the following requirements: motion < 2mm translation, < 2 • rotation and at least 50% performance in an unrelated task [START_REF] Goldstein | Anterior cingulate cortex hypoactivations to an emotionally salient task in cocaine addiction[END_REF],

where include in this study. The Statistical Parametric Mapping (SPM2) toolbox [START_REF] Friston | Statistical Parametric Mapping: The Analysis of Functional Brain Images[END_REF] was used to preprocess the imaging data and to produce the contrast maps before the analysis with the regularization methods. The preprocessing included a six-parameter rigid body transformation (3 rotations, 3 translations) for image realignment and to correct for head motion, spatially registration to the standard Talairach frame using a voxel size of 3 × 3 × 3mm 3 , an 8mm full-width half-maximum Gaussian kernel to smooth the data in order to reduce the amount of spatial noise as well as the impact of small inaccuracies in the spatial registration across subjects.

In order to compute contrast maps for each subject, experimental condition and session, a general linear model (GLM) with box-car design convolved with a canonical hemodynamic response function (HRF), low-pass filters (HRF) and high-pass filters (cut-off frequency: 1/520s) was used. The GLM contained a single regressor for each of six sessions corresponding to one of three monetary reward conditions (50¢, 25¢, 0¢) and one of two cues (drug words, neutral words). In addition, six motion regressors (3 rotations, 3 translations) were included for all event related tasks. In order to compute a single contrast map for each subject and experimental condition, the contrast maps that were produced by the GLMs (per subject, experimental condition and session) were averaged. After computing these average contrast maps and before using them in our pipeline, grand mean scaling [START_REF] Friston | Statistical Parametric Mapping: The Analysis of Functional Brain Images[END_REF] was applied independently per subject and experimental condition, since scale between different subjects can significantly differ. Note that in our experiments, we use only one image per subject and experimental condition. In this study, we focus on the monetary conditions only, and more specifically the session of 50¢ following [START_REF] Honorio | Can a single brain region predict a disorder[END_REF] and the discriminative task is to classify the subject as cocaine addicted or control.

Chapter Label the nodes of all graphs according to the quantization of the voxel value.

5:

Compute the Weisfeiler-Lehman statistics for the given quantization level over all graphs and aggregate them into the feature vector φ graph (v). 6: end for 7: Compute βgraph from the objective in Equation (5.4) with x graph = φ graph (v).

Methodology

Our approach for fMRI analysis enriches the capacity to model non-linear dependencies between voxels, through the representation of an fMRI recording as a graph. The statistical learning pipeline of our approach can be seen in Algorithm 4.1. In order to make use of a rich graph representation several design choices must be made: (i) the learning algorithm, (ii) the graph construction, (iii) the node labeling and (iv) the graph statistics employed as a feature representation, which we address in the following paragraphs.

Sparsity Regularization As our statistical estimator, we have made use of the Elastic Net (for more details see Section 5.1.2). The Elastic Net combines ℓ 1 with ℓ 2 regularization in order to appropriately trade off sparsity with a low variance estimator in the case of correlated signals. This method is particularly appropriate in fMRI where nearby voxels are likely to be correlated, and regions responsible for a given function or behavior distributed across multiple voxels. Furthermore, it is typical that the majority of voxels in the brain are not discriminative of a specific output. Note that one could use the k-support norm as a regularizer as we consider in a later section of this thesis, but we have used a more established statistical approach in this section. We make use of the Elastic Net twice in our learning pipeline (see Algorithm 4.1). In the first instance, we use the Elastic Net on the raw voxel values to determine a subset of voxels on which we build a graph representation, specifically those with non-zero βlin . Our model selection step has typically chosen approximately 10 3 voxels for this stage. We subsequently compute subgraph statistics over this graph to generate a feature vector, φ graph (v). Finally, we use the Elastic Net on these subgraph statistics in order to determine our final prediction function, with a model selection step to determine appropriate values for λ 1 and λ 2 . We are able to learn in a fully exploratory fashion without restricting our prediction, e.g., to a pre-defined region of interest or a connected component. Overall, we represent fMRI data as graphs over voxels, and compare the resulting graphs with a novel method that combines elements of the Weisfieler-Lehman graph kernel [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF] and the pyramid match kernel [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF], a method that achieves the computational advantages of efficient graph kernels while extending the representation to continuous node labels.

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 67

Results

We use the same experimental setup, a random splitting scheme with 50 trials, to estimate the classification performance of pyramid quantized Weisfeiler-Lehman graph representation and the baseline method on the cocaine addiction dataset. In each trial, a random selection of 80% of the data are used for training, while the remaining 20% are used to estimate the performance.

In Table 4.1 we show the performance of the pyramid quantized Weisfeiler-Lehman graph representation for four different depths of subtree patterns (see Chapter 3). Our approach achieves a mean accuracy of 64.28% for subtree patterns up to depth two. We also compare our proposed technique with three other methods on the same dataset:

(i) Gaussian kernel ridge regression, (ii) the Elastic Net with raw voxels as features, and (iii) the Elastic Net with raw voxels and pyramid quantized Weisfeiler-Lehman subtree features concatenated in a joint feature vector. In Figure 4.1 we show the mean accuracy of the final system and the standard error. Pyramid quantized Weisfeiler-Lehman graph representation outperforms the rest of the methods. With a Wilcoxon signed rank test between the Elastic Net with raw voxels and the pyramid quantized Weisfeiler-Lehman graph representation we determine that our proposed method is statistically significantly better (p = 0.02). Additionally, a reduction of over 14% in classification error is recorded between the Elastic Net on the raw voxels and our method. relationships between voxels. We note, however, that the results in Table 4.1 and in Fig- an important region as our neuroscientist mentioned (for more details see Section 5.2.4).

Intermediate Accuracies

Discussion

Although our method works in an implicitly high dimensional space, we empirically observe that Elastic Net regularization controls the complexity at each stage of the pipeline. The first learning step selects approximately 1100 voxels. Using the pyramid quantized Weifeiler-Lehman graph representation, we generate a feature vector of length 6 × 10 5 , but with a sparsity of ∼ 2%. The second application of Elastic Net selects only ∼ 2K dimensions. In each step, the method retains complexity much lower than a "simple" linear function over tens of thousands of voxels as has been proposed in previous works. Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification Several broad observations are apparent from our quantitative results. From Table 4.1, we note that subtree patterns up to depth two seem to perform best, and that deeper subtree patterns begin to reduce average performance. This indicates that the big-O complexity of the graph representation is only slightly higher than using a simple linear function. The proposed method performs significantly better than the Gaussian kernel ridge regression and the Elastic Net baselines (see Table 4.1 and Figure 4.1). In our final experiment of combining the raw voxel values with the subtree pattern features, we found that performance decreased slightly from that of only considering subtree pattern features.

In this work, we have presented a fully automated, statistically sound method for classification of brain states with graph representations, using the pyramid quantized Weisfeiler-Lehman graph representation. The method was evaluated on a real world dataset and outperformed other machine learning techniques with statistical significance, including kernel ridge regression and the Elastic Net. This validates the primary hypothesis of this work: that the interconnections between voxels can contain additional information about brain structure that is not apparent in a linear function on the raw voxel values.

3D shape classification 4.2.1 Introduction

Three-dimensional objects are extensively used in a numerous areas, such as computer games, biomedical research studies, CAD models and cultural heritage. Examples with applications that use 3D objects can been seen in Figure 4.6. Their widespread incorporation in many areas generates the need to store, classify and retrieve them automatically and efficiently. 3D surface models, also known as 3D shapes, represent a 3D object by a finite set of surface points in 3D space, connected by various geometric entities such as triangles, curved surfaces, etc.

In previous proposed methods, the three-dimensional objects are commonly associated with a 3D descriptor. There are three wide categories of 3D descriptors (a) featurebased methods, (b) view-based methods, and (c) graph-based methods. Feature-based methods represent objects as histograms of statistics of global features [START_REF] Elad | Content based retrieval of vrml objects: an iterative and interactive approach[END_REF][START_REF] Mahmoudi | Three-dimensional point cloud recognition via distributions of geometric distances[END_REF][START_REF] Kokkinos | Intrinsic shape context descriptors for deformable shapes[END_REF], such as volume, moments and geodesic distance, or local features [START_REF] Ha | Mesh saliency[END_REF][START_REF] Castellani | Sparse points matching by combining 3D mesh saliency with statistical descriptors[END_REF], such as curvature and normals. The advantage of feature-based methods is that they are computationally efficient, as they represent a potentially complex 3D object by only a few dimensions. On the other hand, view-based methods use multi-viewpoint projections

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 73

to produce a number of rendered images, the combination of which forms a global object descriptor [START_REF] Ohbuchi | Distance metric learning and feature combination for shape-based 3d model retrieval[END_REF]. Finally, graph-based methods use only the topological properties of the 3D object in its representation, such as Reeb graphs [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3d shapes[END_REF] and skeleton graphs [START_REF] Sundar | Skeleton based shape matching and retrieval[END_REF]. The disadvantage of these methods is that are computationally expensive and can be sensitive to small topological changes.

In our approach, we denote that the 3D surface models can be viewed as graphs G(V, E),

where the finite set of points in the 3D space will represent the vertices V and the connection between two points in order to form triangles or curved surfaces will represent the edges E. This perspective specifies the topology of a graph, but does not explicitly encode relative vertex positions or other geometric properties. Therefore, we extend the notion of the graph to incorporate node labels that encode properties, such as local curvature of the surface. In order to incorporate this representation in a statistical learning framework, we interpret 3D shapes as continuous vector labeled graphs and use the pyramid quantized Weisfeiler-Lehman kernel, introduced in Chapter 3, to learn the classification functions. We overcome the problem of computational inefficiency and oversensitivity to topological changes by representing graphs using statistics of subtree patterns.

The remainder of this section is structured as follows: In Section 4.2.2 we present the two 3D shape datasets, a dataset from medical imaging and a dataset from the semantic shape classification tasks, in Section 4.2.3 we introduce the local features of the 3D shapes that are used as continuous vector labels in their graph representation, in Section 4.2.4

we present an overview of the pipeline strategy used in this problem, in Section 4.2.5 we report the experimental results on two aforementioned datasets and we conclude with a discussion in Section 4.2.6.

3D shapes datasets

We evaluate the pyramid quantized WeisfeThe obtained volumes had a size of 64 × 64 × 20 voxels and a voxel resolution of 3.125mm × 3.125mm × 7mm. T1-and T2-weighted MR images were acquired at the same time. As a consequence, the image volumes are naturally co-registered. iler-Lehman kernel on two 3D surface shape categorization tasks.

In the first task, we address the problem of categorizing shapes extracted from segmented medical images of calf muscle. The discriminative task is to determine the presence or absence of neuromuscular dystrophy. In the second task, we address the problem of semantic shape categorization based on the SHREC 2013 data set.

Neuromuscular Dystrophy Dataset

The neuromuscular dystrophy dataset consists of 41 subjects: 27 are affected by a neuromuscular dystrophy (either facioscapulohumeral muscular dystrophy or myotonic muscular dystrophy type 1), while the remaining 14 subjects are healthy. In a clinical context, this a large sample size. The subjects were imaged in the calf using a 1.5 T MRI scanner. The obtained volumes had a size of 64 × 64 × 20 voxels and a voxel resolution of 3.125mm × 3.125mm × 7mm. An example of the T1-weighted MR images of the calf from a healthy and patient subject can be seen in Figure 4.7. It is not immediately apparent from these images whether zero, one, or both subjects have a neuromuscular dystrophy even to experts; a confirmation is achieved by an invasive muscle biopsy. The T1 weighted MR images were manually segmented by an expert separating 7 important calf muscle groups: 1) soleus (SOL), 2) lateral gastrocnemius (LG), 3) medial gastrocnemius (MG), 4) posterior tibialis (TP), 5) anterior tibialis (AT), 6) extensor digitorum longus (EDL), and 7) peroneous longus (PL). An example of the segmented muscle can be seen in Figure 4.8. It is planned to automate this process in future work. In the meantime, the overall approach provides a strategy to avoid an invasive biopsy.

Each segmented muscle is then transformed into a 3D surface mesh using the itk-snp program.1 Consequently, the exported 3D meshes consist of a huge number of vertices and edges and require a decimation pre-processing step (for more details see in paragraph "Decimation preprocessing" in Section 4.2.2.3 and Figure 4.9). subject, on the left, and a patient, on the right respectively, after the prepocessing procedure of decimation is applied. Finally, we should note that the discriminative task for this dataset is to distinguish between patients of neuromuscular dystrophy and healthy subjects.

SHREC 2013 dataset

The SHREC 2013 dataset was selected from the SHREC 2013 Contest "Large-Scale Partial Shape Retrieval Track Using Simulated Range Images" track. illustrated in Figure 4.12. Finally, we should note that the task is to categorize each object among the 20 different semantic classes using a one-vs-rest approach.

Decimation preprocessing

Both the neuromuscular dystrophy dataset and the SHREC 2013 dataset consist of 3D meshes with a very big number of vertices and edges. For example for the neuromuscular dystrophy dataset for soleus muscle the average number of vertices is 25430 and the average number of edges is 76291, while for the SHREC2013 dataset the average number of vertices is 10446 and the average number of edges is 29920. Since the Weisfeiler-Lehman algorithm is quadratic to the number of edges and linear to number of vertices (see paragraph "Complexity" in Section 3.1), a larger number of vertices and edges

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 81 could make the computation infeasible. For these reasons a decimation preprocessing was performed to simplify the 3D shapes in both datasets. Additionally, in the context of the pyramid Weisfeiler-Lehman graph representation, decimation can be viewed as an important source of regularization. For the neuromuscular dystrophy dataset the 3D meshes were simplified with the decimation algorithm incorporated in the itk-snap program, keeping on average 4308 number of vertices and 13598 number of edges. For the SHREC 2013 dataset the 3D meshes were simplified to 500 faces using the qslim program [Garland andHeckbert, 1997, 1998]

Node Labels' description

As we denoted above, we view the 3D surface meshes as labeled graphs G = (V, E, L),

where L : V → R d is the label function and the label of each vertex is defined as a concatenation of a number of local properties of the 3D surface mesh. In this section we present the local properties used as labels on the vertices.

Curvature

The first attributes we select are the two principal curvatures k 1 and k 2 of each vertex of the 3D surface mesh, which are attached as a 2D continuous vector features. The normal curvature k n of a surface in some direction is defined as the reciprocal of the radius of the circle that best approximates a normal slice of surface in that direction.

Specifically, the normal curvature is defined as

k n = s t k 1 0 0 k 2 s t (4.1)
where k 1 and k 2 are the principal curvatures and s t is the unit-length vector in the local tangent plane that express the principal directions, i.e. the directions in which the normal curvature reaches its minimum and maximum. We estimate the value at each vertex as a weighted average over the principal curvature features of the immediately adjacent triangulated faces [START_REF] Rusinkiewicz | Estimating curvatures and their derivatives on triangle meshes[END_REF]. Examples of the two principal curvatures on each node are shown in Figure 4.13 for a bottle object from the SHREC2013 dataset, while Figure 4.14 shows the minimum curvature feature on the muscle soleus of the calf from the neuromuscular dataset for a patient with a neuromuscular disease and a healthy subject.

Apart from the principal curvatures that are used as node attributes in both datasets, in the SHREC2013 dataset we also used as node attributes local multi-viewpoint rendering features as defined in the following paragraph, but only for the 3D surface mesh structure that is enclosed within a given radius of the current node.

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 83

Multi-viewpoint rendering descriptors

A successful method for 3D shape classification that has been previously proposed, is based on rendering shapes from multiple viewpoints and developing kernels based on these rendered images [START_REF] Ohbuchi | Distance metric learning and feature combination for shape-based 3d model retrieval[END_REF]. We complement our continuous vector labeled graph representation with multi-viewpoint rendering features for the more complicated SHREC 2013 dataset. As we cannot assume a canonical basis for specifying

Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification Algorithm 4.2 The statistical learning pipeline for 3D shape with pyramid quantized Weisfeiler-Lehman kernel.

Require:

Training set of D = {(G ′ i , y i ), i = 1, . . . , n} where G ′ i = (V ′ i , E ′ i ) is a graph. 1: Decimate the graphs G ′ i = (V ′ i , E ′ i ) into G i = (V i , E i ) where |V ′ i | ≤ |V i | and |E ′ i | ≤ |E i |. 2:
Calculate the curvature and/or multi-viewpoint rendering descriptor for each vertex and label the graphs

G i = (V i , E i , L i ), where L i : V i → R d . 3: for each level in the quantization pyramid do 4:
Label the nodes of all graphs according to the data guided quantization of the vector label.

5:

Compute the Weisfeiler-Lehman statistics for the given quantization level over all graphs and calculate the intersection kernel k (h) i-W Lsubtree . 6: end for 7: Combine the kernels k (h) i-W Lsubtree across all levels given a predefine weighted scheme or multiple kernel learning. the 3D coordinates of the surface control points, we use a principal component analysis step to determine one. The multi-viewpoint rendering descriptor for a given vertex on the graph is calculated for a given percentage of the radius on the graph. For comparison, we also develop a multi-viewpoint rendering baseline on the whole graph. Similarly, we use a principal components analysis step to determine a basis. We then render images in these canonical bases and compute (non-)linear kernels. We have explored linear, polynomial of 2nd and 3rd degree and Gaussian kernels. As the third and the second degree polynomial kernel performed best for the muscle and SHREC2013 dataset, respectively, we use these rendering baselines in Section 4.2.5.

Method

As we already mentioned above, we view the 3D surface models as graphs G(V, E), where V is the finite set of points in the 3D space and E is the set of connections between two points in order to form triangles or curved surfaces. We further annotate each vertex using the local features, defined in Section 4.2.3, in order to take advantage of shape's information. Before we incorporate local features as labels on the vertices, we simplify the mesh, as noted in Section 4.2.2.3, due to the large sizes of the graphs.

Since we end up with a continuous vector labeled graphs, we use the pyramid quantized Weisfeiler-Lehman graph representation with a data guided binning scheme (see Section 3.3.1.2) to create subtree statistics over the graphs for comparison. For all the levels of quantization, we calculate the intersection kernel over the previous calculated subtree statistics (see Section 3.3.2), resulting in a number of kernels, one per pyramid level as in Equation 3.11. To combine the kernels from all pyramid levels into one, we The mean accuracy and the mean area under the ROC curve (AUC) on the neuromuscular dystrophy dataset. The compared methods are (left to right) the pyramid quantized Weisfeiler-Lehman kernel (WLpyramid), the pyramid bag of words model (pyramid BoW), the multi-viewpoint rendering images procedure (Rendering) and a combination of the multi-viewpoint rendering procedure with the pyramid quantized Weisfeiler-Lehman kernel (Combined). Note that the chance is 65.5% accuracy.

follow two different approaches, one for each dataset in order to maximize their performance. For the neuromuscular dystrophy dataset we use a equal fixed weight strategy (see Section 3.4.1.2), while for the SHREC 2013 dataset we use a multiple kernel learning approach (see Section 3.4.1.1). An overview of the pipeline for the 3D shape dataset with the pyramid quantized Weisfeiler-Lehman kernel is shown in Algorithm 4.2.

Results

For both datasets we use the same experimental setup, a double cross-validation procedure. The inner 5 fold cross-validation procedure is used for parameter selection, while the outer 10 fold cross-validation procedure is used for evaluating the performance. We only report results from the outer 10 fold cross-validation procedure. We also compare the pyramid quantized Weisfeiler-Lehman kernel with two other methods on both datasets (a) a pyramid bag of words model, which is the pyramid quantized Weisfeiler-Lehman kernel for depth h = 0, and (b) a multi-viewpoint rendering procedure (see details in paragraph "Multi-viewpoint rendering descriptor" in Section 4.2.3.2) following the same experimental setup. We also present the results obtained from the combination of the best multi-viewpoint rendering representation with the best pyramid quantized Weisfeiler-Lehman kernel.

The performance for the neuromuscular dystrophy dataset of the pyramid quantized Weisfeiler-Lehman kernel, as well as the three other methods is shown in Table 4.2 and in Figure 4.15. The performance is evaluated as the mean accuracy and the mean area under the Receiver Operating Characteristic curve (AUC) in Table 4.2 over a 10 fold cross validation procedure. The respective ROC curves can be seen in Figure 4.15. The pyramid quantized Weisfeiler-Lehman kernel outperforms both the pyramid bag of words method and the multi-viewpoint image rendering procedure. The overall best performance is achieved when we combined the pyramid quantized Weisfeiler-Lehman kernel with the multi-viewpoint rendering approach with a mean accuracy of approximately 83% and a mean AUC of 0.6648. The overall best performance is achieved when we combined the pyramid quantized Weisfeiler-Lehman kernel with the multi-viewpoint rendering images with a mean AUC of approximately 0.85 across all 20 classes. A Wilcoxon signed-rank test showed that the combined method performed better than all other methods with high statistical significance (p < 10 -3 ).

We further show the learned weight of the pyramid quantized Weisfeiler-Lehman kernel for the SHREC 2013 dataset in Figure 4.17 The mean area under the curve on the SHREC 2013 dataset over 10 fold cross-validation procedure. The compared methods are (left to right) The pyramid quantized Weisfeiler-Lehman kernel (WLpyramid), the pyramid bag of words model (pyramid BoW), the multi-viewpoint rendering procedure (Rendering) and a combination of the multi-viewpoint rendering procedure with the pyramid quantizes Weisfeiler-Lehman kernel (Combined). The Area under the curve is given for all one-vs-rest classifiers as well as the average across all classifiers. In bold are the one-vs-rest classifier where the combined classifier outperforms the multi-viewpoint rendering procedure.

A Wilcoxon signed-rank test showed that the combined method performed better than all other methods with high statistical significance (p < 10 -3 ).

Discussion

In the neuromuscular dystrophy dataset, the pyramid quantized Weisfeiler-Lehman kernel performs substantially better than both the pyramid Bag of Words approach as well as the multi-viewpoint rendering technique. These techniques clearly contain complementary information as the combined method performs best.

We have further confirmation from the SHREC 2013 dataset that the pyramid quantized Weisfeiler-Lehman kernel contains complementary information to the multi-viewpoint rendering baseline. The combined approach gives the best performance in 13 out of the 20 classes, while never performing worse than the baselines. A Wilcoxon signed-rank test also showed that the combined method performed better than all other methods with high statistical significance (p < 10 -3 ). As shapes are commonly represented by surface meshes, a natural approach is to use these graphs for categorization and retrieval. In this section we have shown two such applications, one on medical image analysis and one on generic 3D shape classification.

The pyramid quantized Weisfeiler-Lehman kernel is a flexible and efficient method for learning from graphs with continuous, vector-valued node labels, such as annotations of local curvature. Furthermore, visualizations of the learned discriminant function is feasible, providing rich information about the discriminative power of each 3D shape.

In this work, we have not directly incorporated any features in our node labels capturing surface reflectance, color, or texture. This is an interesting area for future research.

Learned shape retrieval by discriminative training of a Mahalanobis metric [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] of observations is substantially smaller that the dimensionality of the data. Under these circumstances the use of sparsity regularizers is a powerful tool for improving the predictive performance and avoiding overfitting. The main methods considered here are the LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], the Elastic Net [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF], and the k-support norm [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF]. The former two are frequently applied sparsity regularizers developed in the statistics literature, while the latter is a recently introduced method that is mathematically related to the Elastic Net. A detailed description of these methods are presented in Section 5.1. We then evaluate the performance of these three different regularization methods on a fMRI analysis task in Section 5.2, while in Section 5.3 we evaluate the k-support norm method with the use of two different loss functions over a disease classification problem.

The regularization methods

Regularization, in mathematics and statistics, refers to a process of introducing additional information in order to solve an ill-posed problem or to prevent overfitting. This information is usually of the form of a penalty for complexity, such as restrictions for smoothness or bounds on the vector space norm. For the rest of this chapter, we assume that we have a sample of paired labeled training data (X, Y ) = {(x 1 , y 1 ), . . . , (x n , y n )} ∈ R d × R n where x i is an independent variable and y i is a dependent variable that we would like to be able to predict. All regularization methods can be expressed as follows:

arg min

w∈R d λΩ(w) + L(w, X, Y ) (5.1)
where L(•, •, •) is some loss function, λ > 0 is a scalar parameter controlling the degree of regularization and Ω(•) is a scalar valued function monotonic in a norm of the learned weights w ∈ R d . Sparsity regularization is a key family of priors over linear functions that prevents overfitting, and aids interpretability of the resulting models by retaining a subset of the predictors and discarding the rest in a more continuous framework than typical subset selection procedures. Key to the mathematical understanding of sparsity regularizers is their interpretation as convex relaxations to quantities involving the ℓ 0 norm, which simply counts the number of non-zero elements of a vector.

In the following sections, we examine the well known LASSO and Elastic Net in Section 5.1.1 and in Section 5.1.2 respectively and the newly introduced k-support norm in Section 5.1.3.

Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 99

LASSO

LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] stands for the Least Absolute Shrinkage and Selection Operator and is a regularized version of the ordinary least squared method (OLS). The LASSO is defined by setting as loss function the squared error of the scalar output and as regularization term Ω(•) the ℓ 1 norm of w, so Equation 5.1 is transformed as follows:

arg min

w∈R d λ w 1 + 1 n n i=1 ( w, x i -y i ) 2 (5.2)
where the ℓ 1 norm is defined as the sum of the absolute values of the vector

w 1 = d j=1 w j (5.3)
and has an important interpretation as convex relaxation of the ℓ 0 norm, meaning it is the tightest sparsity norm that retains convexity. Note that as λ increases in Equation 5.2 that will cause more coefficients w j to be exactly zero, providing a more sparse solution.

The LASSO constraint makes the solutions nonlinear in the y i and there is no closed form expression as in least squares. Computing the LASSO solution is a quadratic programming problem and an efficient algorithm for computing the entire path of solutions as λ varies exist -it is a variation of the Least Angle Regression (LAR) called LAR-LASSO -making the LASSO computationally attractive. The LAR can be viewed as a forward stepwise regression where instead of adding one variable at a time, the algorithm adds "as much" of a predictor as it deserves. The idea of LAR is that it identifies variables, called the active set, that are most correlated with the response and moves their coefficients continuously toward the least-squared value. It increases the active set by one variable at the time, but controlling its influence by its coefficient. This process is continued until all variables are in the model, ending at the full least-squares fit. The LAR algorithm has at most min(n -1, d) steps, the same order of computations as a single OLS fit. The LAR-LASSO variation allows a variable to be dropped from the active set of variables if its coefficient hits zero.

Elastic Net

The Elastic Net [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF]] is a regularization and variable selection method that was introduced by Zou and Hastie in 2005. Elastic Net is defined by setting as loss function the squared error of the scalar output and as regularization term Ω(•) a linear combination of the ℓ 1 and squared ℓ 2 norms of w, so Equation 5.1 is transformed as follows:

arg min

w∈R d λ 1 w 1 + λ 2 w 2 2 + 1 n n i=1 ( w, x i -y i ) 2 (5.4)
where the ℓ 1 norm is defined in Equation 5.3 and the squared ℓ 2 norm is defined as

w 2 2 = d j=1
w 2 j .

(5.5)

This objective is a regularized version of the ordinary least squares and includes both ridge regression [START_REF] Tikhonov | Solution of incorrectly formulated problems and the regularization method[END_REF] and LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] as special cases by setting λ 1 or λ 2 to zero, respectively.

It should be noted that the Elastic Net is looser than the convex hull of a norm that combines ℓ 2 regularization with sparsity. Moreover, if there is a group of variables among which the pairwise correlations are very high, the LASSO (see Section 5.1.1)

tends to select only one variable from the group and does not care which one is selected, ending with a higher variance predictor. Elastic Net on the contrary may overcome this disadvantage by selecting multiple variables from a group of correlated ones if that improves the prediction accuracy, assigning approximately equal coefficients to highly correlated variables.

Finally, the Elastic Net retains the computational advantage of the LASSO with the use of a variation of the LAR algorithm, the LAR-EN. The Elastic Net problem can be solved as a LASSO-type one considering the augmented paired data (X * , Y * ) where

X * (n+d)×d = (1 + λ 2 ) -1/2 X √ λ 2 I , Y * (n×d) = Y 0 ,
so Equation 5.4 can be written as:

ŵ * = arg min ŵ * ∈R d λ 1 (1 + λ 2 ) ŵ * 1 + 1 n n+d i=1 ( ŵ * , x * i -y * i ) 2 (5.6)
and the Elastic Net solution [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF] is defined as: ŵ = (1 + λ 2 ) ŵ * .

(5.7)

The LAR-EN algorithm takes advantage of the sparse structure of the augmented data when updating the Cholesky factorization of the active set in each iteration. Moreover, an explicit use of the X * to compute all the quantities of the LAR algorithm can be avoided, by keeping record only the non-zero coefficients and the active set at each LAR-EN step. In the case where d >> n, it is not necessary to run the algorithm to the end.

If the algorithm is stopped after m steps, it requires O(m 3 + dm 2 ) operations.

Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 101

k-support norm

The k-support norm [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF] is a newly introduced regularization penalty that corresponds to the tightest convex relaxation of sparsity combined with the ℓ 2 norm.

The k-support norm given an integer k ∈ {1, . . . , d} can be computed as

w sp k =   k-r-1 i=1 (|w| ↓ i ) 2 + 1 r + 1 d i=k-r |w| ↓ i 2   1 2 (5.8)
where |w| ↓ i is the ith largest element of the vector and r is the unique integer in {0, . . . , k-1} satisfying

|w| ↓ k-r-1 > 1 r + 1 d i=k-r |w| ↓ i ≥ |w| ↓ k-r .
(5.9)

One can see from Equation 5.8 that the norm trades off a squared ℓ 2 penalty for the largest components with an ℓ 1 penalty for the smallest components. Note that means that k-support norm is exactly equivalent to the ℓ 1 norm when k = 1, while when k = d k-support norm is equivalent to the ℓ 2 norm. The k-support norm is exactly the convex hull of that hybrid norm and is closely related to the Elastic Net penalty in that it can be bounded to within a constant factor of the Elastic Net, as Argyriou et al. have shown in [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF].

In this thesis we employ the k-support norm with two different loss functions, the squared loss and Huber-Hinge approximation loss. If we use the Nesterov's accelerated method, which is a first-order proximal algorithm, for optimization as suggested by [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF], an implementation of the k-support penalty requires apart from the definition of the loss function L, also its gradient ∂L ∂w and the Lipschitz constant L for ∂L ∂w .

Squared Loss

The k-support norm was first introduced by Argyriou et al. in [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF] using a squared loss function, which is described as follows:

arg min

w∈R d λ w sp k + Xw -Y 2 .
(5.10)

The gradient of the squared loss function is defined as (5.11) penalizes heavily confident correct classifications and (b) the quadratic penalty is not as robust to label noise as the linear penalty. Note, however, that both loss functions lead to a statistically consistent binary classifier [START_REF] Peter | Convexity, classification, and risk bounds[END_REF].

∂L ∂w = 2X T Xw -2X T Y
5.2 fMRI data analysis with the use of regularization methods

Introduction

In this section we evaluate the three regularization methods presented in Section 5.1, the well-known LASSO and Elastic Net and the newly introduced k-support with squared loss, in analyzing fMRI data. Functional magnetic resonance imaging (fMRI) is a noninvasive modality used for studying brain activity by detecting changes in blood oxygenation and flow, that occur as a response to neural activity. The typically small sample size, which is a result of both the high cost and time consuming nature of the fMRI acquisition procedure, and as well as the high dimensional nature of the data, which consists of tens of thousands of voxels, makes the statistical analysis of fMRI data a challenging task.

A number of approaches have been proposed in the literature for analyzing fMRI data, as we have already seen in Section 4.1.1, including machine learning techniques such as support vector machines, independent component analysis, as well as the use of regions of interest (ROIs). Due to the intrinsic high dimensional nature of fMRI data and the cost of collecting large numbers of samples, fMRI analysis is particularly suited for the sparsity regularization framework. Sparsity regularization methods, apart from being mathematical appealing, they are also fully exploratory and they do not require a predefined set of ROIs. Previous works that have explored sparsity regularization in fMRI include [START_REF] Carroll | Prediction and interpretation of distributed neural activity with sparse models[END_REF], Ng et al., 2012b]. To the best of our knowledge, this study is the first to apply the k-support norm to fMRI analysis.

The remaining of the section is organized as follows: in Section 5.2.2 we present the data that we use in this study, in Section 5.2.3 is dedicated to the experimental setting and results and in Section 5.2.4 concludes the overall section with a discussion over the obtained results and the perspectives of this work.

Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 105

fMRI data description

In order to evaluate the three regularization methods we use two fMRI datasets. The first one, which consists of a healthy subject in a free-viewing framework, is employed for the quantitative evaluation due to its larger sample size, while the second one, which consists of the contrast maps of 16 cocaine addicted subjects and 17 controls, is employed for qualitative evaluation.

Free-viewing dataset

The free-viewing dataset consists of fMRI data of a single session from one human volunteer [Bartels andZeki, 2004b, Bartels et al., 2007]. The session has 350 time slices of 3-dimensional fMRI brain volumes, that was acquired using a Siemens 3T TIM scanner. The time-slices were separated by 3.2 seconds (TR) and each one has a spatial resolution of 46 slices with 64 × 64 pixels of 3 × 3mm, resulting in a spatial resolution of 3×3×3mm. The subject watched one movie, which had labels indicating the continuous content of the movie (i.e. degree of visual contrast, or the degree to which a face was present, etc.). The imaging data were preprocessed using standard procedures using the Statistical Parametric Mapping (SPM5) toolbox before analysis [START_REF] Friston | Statistical Parametric Mapping: The Analysis of Functional Brain Images[END_REF].

This included slice-time correction to compensate for acquisition delays between slices, a spatial realignment to correct for small head-movements, a spatial normalization to the SPM standard brain space (near MNI), and spatial smoothing using a Gaussian filter of 6 mm full width at half maximum (FWHM). Subsequently, images were skull-and-eye stripped and the mean of each time-slice was set to the same value (global scaling). A temporal high-pass filter with a cut-off of 512 seconds was applied, as well as a low-pass filter with the temporal properties of the hemodynamic response function, in order to reduce temporal acquisition noise [START_REF] Blaschko | Augmenting feature-driven fMRI analyses: Semi-supervised learning and resting state activity[END_REF][START_REF] Shelton | Semi-supervised subspace learning and application to human functional magnetic brain resonance imaging data[END_REF].

The label time-series were obtained using two separate methods, using computer frameby-frame analysis of the movie [Bartels et al., 2007], and using subjective ratings averaged across an independent set of five human observers [Bartels and Zeki, 2004b].

The computer-derived labels indicated luminance change over time (temporal contrast), visual motion energy (i.e. the fraction of temporal contrast that can be explained by motion in the movie). The human-derived labels indicated the intensity of subjectively experienced color, and the degree to which faces and human bodies were present in the movie. In prior studies, each of these labels had been shown to correlate with brain activity in particular and distinct sets of areas specialized to process the particular label in question [Bartels andZeki, 2004b, Bartels et al., 2007]. The discriminative task is the prediction of a "Temporal Contrast" variable computed from the content of a movie presented to the subject [START_REF] Blaschko | Semi-supervised kernel canonical correlation analysis with application to human fmri[END_REF].

Cocaine Addiction Dataset

Our dataset [START_REF] Goldstein | Anterior cingulate cortex hypoactivations to an emotionally salient task in cocaine addiction[END_REF] contains an approximately equal number of cocaine addicted individuals and control subjects performing a neuropsychological experiment of block design, called drug Stroop experiment. The experiment consists of an initial screen displaying the monetary reward and then presenting a sequence of forty words in four different colors. The subject was instructed to press one of four buttons matching the color of the word and was rewarded for correct performance. Each subject performs six sessions with two varying conditions, a monetary reward (50¢, 25¢ and 0¢) and the cue shown (drug-related or a neutral word). We focus here on the 50¢ condition based on previous analysis of the data [START_REF] Honorio | Can a single brain region predict a disorder[END_REF]. The data were preprocessed using statistical parametric mapping SPM2 [START_REF] Friston | Statistical parametric maps in functional imaging: A general linear approach[END_REF] and a contrast map for each subject is produced. A detailed description of the preprocessing procedure is presented in Section 4.1.2. Only the subjects that complied to motion < 2mm translation, < 2 • rotation and at least 50% performance of the subject in an unrelated task [START_REF] Goldstein | Anterior cingulate cortex hypoactivations to an emotionally salient task in cocaine addiction[END_REF] were kept. Finally, the task of interest is the classification of a subject as cocaine addicted or control.

Results

The qualitive evaluatation of the different sparse regularization techniques is performed on the free viewing dataset (see Section 5.2.2.1) and their performance is shown in .2: Mean Pearson correlations between the label and prediction on the holdout data over 100 trials for the free-viewing dataset (higher values indicate better performance). Error bars show the standard error of the mean. The LASSO achieves its best performance with a sparsity level substantially lower than the Elastic Net, as it suppresses correlated voxels (Figure 5.2(a)). The k-support norm performs better than the LASSO, Elastic Net, or Laplacian regularization reported in [START_REF] Blaschko | Semi-supervised kernel canonical correlation analysis with application to human fmri[END_REF], and is a promising candidate for sparsity in fMRI analysis ( k-support norm for a range of machine learning problems [START_REF] Argyriou | Sparse prediction with the k-support norm[END_REF], to the best of our knowledge this study is the first to apply the approach to fMRI. 5.3 MRI based markers for neuromuscular disease categorization with k-support norm

Introduction

In this section, we evaluate the k-support norm regularization method with the use of two different loss functions, with the squared loss function and with the Huber-Hinge approximation loss function known as the k-support regularized SVM both described in detail in Section 5.1.3, over the problem of disease classification. More specifically, we are interested in discriminating between two different neuromuscular diseases, the facioscapulohumeral muscular dystrophy (FSH) and the myotonic muscular dystrophy type 1 (DM1). Myopathies are neuromuscular diseases that affect the muscles resulting in functional anomalies including fat infiltration, weakness, atrophy, paralysis, loss in muscle strength, etc. There are a number of procedures available for disease identification, such as electromyogram (EMG) measurement that measure the muscle weakness through its electrical activity, blood tests that can be carried out for a molecular study of the DNA for inherited myopathies with known genes and mutations and of course muscle tissue biopsy. The problem with all these methods is that are invasive or they require prior knowledge of genes and mutation. Overall the area of non-invasive diagnosis could be explored and evolved. Toward this direction, we pursue here a comparatively non-invasive approach based on MR imaging, such as T1 and T2 weighted images and with particular emphasis on Diffusion Tensor Imaging, which has been successfully used in neuroimaging for myopathy categorization. [START_REF] Craig J Galban | Diffusive sensitivity to muscle architecture: a magnetic resonance diffusion tensor imaging study of the human calf[END_REF]. DTI can capture important structural information in the case of the muscle. This is due to the fact that muscles are highly organized structures that present an architecture of elongated myofibers. Because myopathies affect the muscles, one may expect that the diffusion properties in diseased subjects are also altered [START_REF] Qi | Diffusionweighted imaging of inflammatory myopathies: Polymyositis and dermatomyositis[END_REF].

We are interested in verifying that different myopathies alter muscle in distinct ways.

Moreover, we investigate the discriminative power of diffusion and structural MR features in distinguishing between diseases. Figure 5.4 shows the T1-weighted MR images of the two myopathies under investigation. The two images are very similar, making the distinction between them a very challenging task. In order to achieve this goal, we develop a strategy that exploits the rich information that is captured by both structural data (T1-and T2-weighted MR images) and DTI data to fuel state-of-the-art machine learning techniques. The use of high dimensional pattern classification in conjunction with DTI information has been previously investigated [START_REF] Mwa Caan | Shaving diffusion tensor images in discriminant analysis: A study into schizophrenia[END_REF], Wang and Verma, 2008[START_REF] Ingalhalikar | Diffusion based abnormality markers of pathology: Toward learned diagnostic prediction of asd[END_REF]. Nonetheless, it has been mainly applied to distinguish patients from controls in neuroimaging studies. Discriminating between patients poses additional challenges.

The remainder of the section is organized as follows: in Section 5.3.2 we present the data that we use in this study, in Section 5.3.3 is dedicated to the experimental setting and results and in Section 5.3.4 concludes the section with a discussion over the obtained results and the perspectives of this work.

MRI data description

In this study, we use a dataset consisting of twenty five subjects, 10 subjects were affected by FSH and 15 subjects were affected by DM1 [Neji, 2010, Section 4.3.2]. In a clinical context, this is a large sample size. The subjects were imaged in the calf using Table 5.2: Classification mean accuracy (in %± standard error) and the mean area under the curve of the best classifier (ksup-SVM) using both structured and DTI features and the best classifier (ksup-SVM) using only structured features over 1000 trials. Chance is 60%.

Features Used

Accuracy Area Under the Curve Combined T1, T2 and DTI features 77 ± 0.013 0.756 T1 and T2 features 73 ± 0.006 0.697 they do not provide useful information for the distinction of the two diseases, while the ones with non-zero weight are considered more informative.

Toward demonstrating the added value of the DTI features, we compared the performance of the ksup-SVM when trained only on structural data against the ksup-SVM with both structural and DTI features, as presented in the previous paragraph. The same experimental setting as before was used. The results of the comparison are shown in Figure 5.6 and Table 5.2. In this case the ksup-SVM with the structural features achieved a mean AUC of 0.697 and mean accuracy 73%±0.006 a drop of 4% in accuracy.

According to a Wilcoxon signed rank test, this performance is statistically significantly

Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 117 worse than its previous performance using both structured and DTI features (p-value was ≪ 0.05).

Discussion

An analysis of variables selected by the sparsity regularizer (Figure 5.7) gives an indication that discrimination varies across muscles as well as features. Increased muscle volume in AT, EDL, MG, and TP was associated with DM1, while increased volume in PL and SOL was associated with FSH. T1 and T2 signal was consistently positively associated with FSH in the EDL muscle. A broad range of statistics were discriminative for the MG muscle, while discriminative features for most other muscles were comparatively sparse.

While MRI markers, and DTI tensor features in particular, have previously been shown

to differ between disease and control subjects [Qi et al., 2008, Table 2], we are unaware of previous studies that have shown significant ability to discriminate between disease conditions. Indeed, a high-dimensional analysis of MRI based markers was required to achieve non-random performance in this more challenging task. Sparsity regularization appears to be a more important property of the learning algorithm than non-linearity, as evidenced by the comparatively stronger performance of k-support norm regularized SVM or squared error, as compared to a SVM with non-linear kernels or k nearest neighbors (both non-sparse, non-linear algorithms).

In this section, we have presented several novel methodological and clinical developments related to the use of pattern recognition methods in neuromuscular disease classification.

While previous studies have focused on the comparatively easy task of separating disease from healthy subjects, we have approached the more difficult and clinically relevant task of discriminating between diseases. We have shown that a combination of T1-and T2-weighted MR images and Diffusion Tensor Imaging data are discriminative for separating patients with facioscapulohumeral muscular dystrophy and myotonic muscular dystrophy type 1. Our novel machine learning algorithm, the ksup-SVM, is an essential machine learning approach for achieving the best performance, with a mean accuracy of 77% ± 0.013.

Chapter 6 Conclusions to perform comparably to or better than a number of more computationally complex kernels [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF].

In order to take advantage of this efficient scheme when extending to the problem of graph comparison with continuous or vector labels, we propose a pyramid quantization strategy inspired by [START_REF] Grauman | The pyramid match kernel: Efficient learning with sets of features[END_REF] to determine a logarithmic number of discrete labelings. This approximates a graph representation with continuous or vector valued labels as a sequence of graphs with increasingly granular discrete labels.

For each level of quantization, we run the Weisfeiler-Lehman algorithm and get the respective subtree statistics. To construct our pyramid quantization, we recursively partition the label space as seen in Section 3.3.1. In this manner, we have a series of nested vector quantizations of increasing granularity. This can be performed efficiently in high dimensions using, e.g. We evaluate the pyramid quantized Weisfeiler-Lehman graph representation in two different tasks with real datasets, on a fMRI analysis task and on a 3D shape classification one in Chapter 4. In the fMRI analysis task (for more details see Section 4.1), we approach the problem by representing fMRI contrast maps from a cocaine addiction dataset as graphs with continuous labels and we use our quantized Weisfeiler-Lehman pyramid graph representation to compare the respective graphs. Our primary hypothesis is that the interconnections between voxels can contain additional information about the brain structure and the problem under investigation, that could not explored under a linear consideration of the data. Our proposed method validated this hypothesis and outperforms other machine learning techniques that are used in fMRI analysis with statistical significance.

In the evaluation of the pyramid quantized Weisfeiler-Lehman graph representation on the task of 3D shape classification we used two real datasets, one from the medical imaging and one from the semantic shape domain (for more details see Section 4.2).

We view the 3D shape models as graphs, but because the topology would not explicitly encode sufficient geometric properties of the respective shapes, we enrich the graphs with continuous labels on the nodes with local features, such the local curvature of the surface. From both datasets, we conclude that the pyramid quantized Weisfeiler-Lehman

Chapter 6 Conclusions 125 graph representation performs substantially better that the pyramid Bag of Words approach, showing that the spatial structure is important for improving the classification performance. Moreover, the results show that our approach contains complementary information to the multi-viewpoint rendering technique, since the combination of both approaches performs better with statistical significance than each method individually.

Overall, as graphs are fundamental mathematical objects, the pyramid quantized Weisfeiler-Lehman kernel is potentially applicable to a wide range of application domains in computer vision, analysis of medical images or data mining. Finally, source code for the pyramid quantized Weisfeiler-Lehman kernel is publicly available at http://gitorious. org/wlpyramid.

The k-support regularized SVM

In Section 5.1.3.2 we introduced a novel regularized SVM algorithm, the ksup-SVM. This algorithm extends the ℓ 1 regularized SVM and the classical SVM algorithms to a mixed norm case. This enables the use of a correlated sparsity regularizer in the classification setting. We showed that using this technique we substantial improved the performance on a neuromuscular dystrophy classification task (see Section 5.3). Moreover, we showed that features extracted from DTI images provide significant information in the discrimination between neuromuscular conditions, extending the use of DTI beyond its usual application in neuroimaging. Finally, code for the new k-support regularized SVM is publicly available at http://gitorious.org/ksp-svm.

Future perspectives

Despite the big breakthrough in the graph comparison problem with the introduction of graph kernels, it still remains an open problem in the graph community. Especially the design of efficient algorithms for labeled graphs with complex labels, such as continuous, strings or even discrete but non categorical labels. In this thesis, we introduced the pyramid quantized Weisfeiler-Lehman graph representation for comparing graphs with continuous or vector labels, through the discretization of the labeled space and the aggregation of subtree pattern statistics calculated by the Weisfeiler-Lehman algorithm [START_REF] Weisfeiler | A reduction of a graph to a canonical form and an algebra arising during this reduction[END_REF] on the described graphs. Although we were able to compare graphs with continuous or vector labels with linear-time to the number of edges and the depth of subtree patterns, we are discarding information concerning the relation between two labels. For example, consider a graph with discrete labels corresponding to ratings on some scale. Then a label 10 and 12 resemble each other more that label 2

  Binning . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.1.2 Data guided binning . . . . . . . . . . . . . . . . . . . . . 50 3.3.2 The intersection Weisfeiler-Lehman subtree kernel . . . . . . . . . 52 3.3.3 The monotonicity property of the pyramid quantized Weisfeiler-Lehman kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Exploring the pyramid quantized Weisfeiler-Lehman features . . . . . . . 56 3.4.1 The pyramid quantized Weisfeiler-Lehman kernel . . . . . . . . . . 56 3.4.1.1 Multiple kernel learning . . . . . . . . . . . . . . . . . . . 57 3.4.1.2 Fixed weight kernel . . . . . . . . . . . . . . . .

4. 1

 1 Mean accuracy and standard error on the cocaine addiction dataset. . . . 4.2 A heat map representation of the intermediate accuracies per quantized pyramid levels and for four different depths of the subtree patterns. . . . . 4.3 A visualization of the areas of the brain selected by Elastic Net. . . . . . . 4.4 A visualization of the function learned by Elastic net for control and cocaine subjects on raw voxels. . . . . . . . . . . . . . . . . . . . . . . . . 4.5 A visualization of the function learned by the pyramid quantized Weisfeiler-Lehman graph representation applied to control and cocaine addicted subjects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Examples of application that use 3D objects. . . . . . . . . . . . . . . . . 4.7 T1 weighted MR images from a healthy and a patient with neuromuscular dysmorphy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 An example of an T1 weighted MR image with the seven segmented muscles of the calf. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Examples of before and after decimation process on the neuromuscular dystrophy dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Examples before and after the decimation process on the SHREC 2013 dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Examples of the 7 main calf muscles as 3D surface meshes. . . . . . . . . 4.12 Examples for the SHREC 2013 dataset . . . . . . . . . . . . . . . . . . . . 4.13 Example of the two principal curvatures on a bottle object from the SHREC2013 dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.14 Example of the minimum curvature on the muscle soleus of the calf from the neuromusclar dystrophy dataset . . . . . . . . . . . . . . . . . . . . . 4.15 The mean area under the ROC curve for the neuromuscular dystrophy dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 LIST OF FIGURES 4.16 The Receiver Operating Characteristic Curves for all one-vs-rest classifiers of the SHREC2013 dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.17 Example of the learned weights of the pyramid quantized Weisfeiler-Lehman Kernel on a 3D object from the SHREC 2013 dataset for three different subtree depths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.18 Visualization of the learned weights of the pyramid quantized Weisfeiler-Lehman kernel for the SHREC 2013 dataset. . . . . . . . . . . . . . . . . 93 5.1 Squared loss function versus Hinge loss function for two class classification 103 5.2 Mean Pearson correlation in FMRI analysis with regularization methods. 107 5.3 A visualization of the areas of the brain selected by the LASSO and by the k-support norm applied to the cocaine addiction dataset. . . . . . . . 109 5.4 T1-weighted MR images of the calf from the two neuromuscular diseases . 112 5.5 Mean ROC curves on the use of regularization methods for neuromuscular categorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.6 Mean ROC curve over the comparison between structures and DTI features.116 5.7 Boxplot of the weights given to the structural and DTI features of the 7 muscles by the ksup-SVM over 1000 trials . . . . . . . . . . . . . . . . . . 118 List of Tables 2.1 An overview of the graph kernel methods. . . . . . . . . . . . . . . . . . . 3.1 Example of linear Weisfeiler-Lehman subtree kernel . . . . . . . . . . . . . 4.1 Mean accuracy over the hold-out data of 50 trials of the pyramid quantized Weisfeiler-Lehman graph representation for four different subtree pattern depths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The mean accuracy and the mean area under the ROC curve for the neuromuscular dystrophy dataset. . . . . . . . . . . . . . . . . . . . . . . . 4.3 The mean area under the ROC curve for the SHREC 2013 dataset . . . . 5.1 Classification mean accuracy on the use of regularization methods for neuromuscular categorization. . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Classification mean accuracy over the comparison between structures and DTI features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Medical imaging consists of a number of different techniques that create images of the human body showing anatomy or function and are used for clinical purposes, such as diagnosing or monitoring the progression of a disease, or for studying normal anatomy and physiology. Over the years, different modalities of medical imaging have been developed, including (a) x-ray based methods -such as conventional x-rays, computed tomography and mammography -(b) magnetic resonance imaging (MRI) -such as T1weighted images and diffusion tensor imaging -(c) molecular imaging -such as positron emission tomography (PET) -and (d) ultrasound, each with their own advantages and disadvantages. They are widely used in daily clinical routines, due to the fact that are generally non-invasive, relatively fast, allowing to image the human body and providing relevant anatomical or function information to the doctor, while minimizing the patient's discomfort.

Figure

  Figure 2.1: Figure 2.1(a) shows an example of a directed graph with V = {1, 2, 3, 4, 5, 6, 7} and E = {(1, 2), (1, 4), (2, 3), (2, 6), (3, 6), (4, 1), (4, 2), (4, 3), (5, 5), (5, 7)}.Figure 2.1(b) shows an undirected graph similar to the direct graph of Figure 2.1(a).Figure 2.1(c) shows the induced subgraph of the graph from Figure 2.1(a) when V ′ = {1, 2, 4, 5, 7}.

  Figure 2.1: Figure 2.1(a) shows an example of a directed graph with V = {1, 2, 3, 4, 5, 6, 7} and E = {(1, 2), (1, 4), (2, 3), (2, 6), (3, 6), (4, 1), (4, 2), (4, 3), (5, 5), (5, 7)}.Figure 2.1(b) shows an undirected graph similar to the direct graph of Figure 2.1(a).Figure 2.1(c) shows the induced subgraph of the graph from Figure 2.1(a) when V ′ = {1, 2, 4, 5, 7}.

  Figure 2.1: Figure 2.1(a) shows an example of a directed graph with V = {1, 2, 3, 4, 5, 6, 7} and E = {(1, 2), (1, 4), (2, 3), (2, 6), (3, 6), (4, 1), (4, 2), (4, 3), (5, 5), (5, 7)}.Figure 2.1(b) shows an undirected graph similar to the direct graph of Figure 2.1(a).Figure 2.1(c) shows the induced subgraph of the graph from Figure 2.1(a) when V ′ = {1, 2, 4, 5, 7}.

Figure 2

 2 Figure 2.1(a) and Figure 2.1(b) show examples of directed and undirected graphs respectively. The vertices are represented with circles, while edges are represented as arrows

Figure 2 . 2 :

 22 Figure 2.2: Figure 2.2(a) shows a molecule of acetaminophen as an example of nodelabeled graph, Figure 2.2(b) shows a flow network as example of edge-labeled graph, while Figure 2.2(c) shows an abstract map, where nodes represent different cities, edges represent connections between cities and the distance between them is used as edge label, as an example of graph with labels in both nodes and edges.

Figure 2 . 3 :

 23 Figure 2.3: The neighborhood of node f (in red color) is the set of nodes {c, d, e, g} depicted with green color. The degree of this node f is four.

Figure 2 . 4 :

 24 Figure 2.4: On the undirected graphs G shown above we represent with red arrows examples of a walk from node a to node f in Figure 2.4(a), a path from node a to node f in Figure 2.4(b) and a cycle from node a in Figure 2.4(c).

Figure 2 . 5 :

 25 Figure 2.5: On the right is the initial graph and on the left a subtree pattern of height 2 rooted at vertex g, depicted with red color. It should be noted that the repetitions of vertices on the subtree pattern allows the pattern to be cycle-free.

Figure 2 . 6 :

 26 Figure 2.6: Two isomorphic representations of the K 3,3 graph.

Figure

Figure 2 . 7 :

 27 Figure 2.7: Example of the graph edit distances methods. Given two labeled graphs G, G′ a sequence of graph edit operations are applied to transform G to G ′ . More specifically, the first operation is node deletion with its adjacency edges, the second operation is node addition, then edge addition, followed by an edge deletion and a node relabeling.

Weisfeiler

  the problem of graph comparison in detail. The majority of the methods focus on either unlabeled or discretely labeled graphs, while an efficient and expressive representation and comparison of graphs with complex labels, such as real numbers and high-dimensional vectors, remains an open research problem.

44Chapter 3

 3 The pyramid quantized Weisfeiler-Lehman graph representation Algorithm 3.1 The one dimensional Weisfeiler-Lehman test of graph isomorphism Require: Two graphs,

Figure 3 . 1 :

 31 Figure 3.1: An illustration of the computation of the Weisfeiler-Lehman test of graph isomorphism for the iteration i = 1. Note that the label of each node v is its degree of node d(v).

  encode the R d into a quantization of a given resolution |Σ (l) 0 | = 2 l . The quantization function Q (l) is repeated for l ∈ {0, . . . , L} to determine multi-resolutions of increasing granularity, where L = ⌈log 2 D⌉, D ≤ |V | = v is the number of unique values in the Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation

Figure 3 . 2 :

 32 Figure 3.2: An illustration of the two different strategies of quantization of a complex space. Both Figures 3.2(a) and 3.2(b) depict the space partition boundaries for two resolution levels for the same 2D space. In both figures, the left plot contains the coarser resolution level, while the right plot contains the finer one. In Figure3.2(a) the complex space is carved into uniformly-shaped partitions, while in Figure3.2(b), the data guide the resulting partition of the complex space. As a result, the bins on the right are better positioned to decompose the space based on the data clusters.

  Figure 3.3(a), the first step is to determine the hierarchical decomposition of the labeled space given, for example, by the data guided binning strategy. The red and green line in Figure 3.3(b) depict the thresholds for achieving two different quantization resolutions with two and and four discrete labels, respectively. For these two quantization resolutions we end up with a sequence of discretized labels for each 54 Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation

  graphs of the quantization level 2 with 2 2 = 4 number of discrete labels.

Figure 3 . 3 :

 33 Figure 3.3: An illustration of the quantization step of the pyramid quantized Weisfeiler-Lehman graph representation. Figure 3.3(a) shows the two given multidimensional labeled graphs under comparisonG = (V, E, L) and G ′ = (V ′ , E ′ , L ′ ), where L : V → R 2 , L ′ : V ′ → R 2and the label of each node v is defined as its degree of node d(v) and the summation of the degree of nodes of its neighborhoodsN v , i.e. L(v) = [d(v), u∈Nv d(u)]. Figure 3.2(b)shows the hierarchical decomposition of the multi-dimensional labeled space given by the data guided binning strategy (see Section 3.3.1.2). With the green and red line are depicted the thresholds for achieving two different quantization resolutions with two and and four discrete labels respectively. Figure3.3(c) shows the two relabeled discretized graphs G (1) = (V, E, L (1) ) and G ′(1) = (V ′ , E ′ , L ′ (1) ), where L (1) : V → Σ

  Figure 3.3: An illustration of the quantization step of the pyramid quantized Weisfeiler-Lehman graph representation. Figure 3.3(a) shows the two given multidimensional labeled graphs under comparisonG = (V, E, L) and G ′ = (V ′ , E ′ , L ′ ), where L : V → R 2 , L ′ : V ′ → R 2and the label of each node v is defined as its degree of node d(v) and the summation of the degree of nodes of its neighborhoodsN v , i.e. L(v) = [d(v), u∈Nv d(u)]. Figure 3.2(b)shows the hierarchical decomposition of the multi-dimensional labeled space given by the data guided binning strategy (see Section 3.3.1.2). With the green and red line are depicted the thresholds for achieving two different quantization resolutions with two and and four discrete labels respectively. Figure3.3(c) shows the two relabeled discretized graphs G (1) = (V, E, L (1) ) and G ′(1) = (V ′ , E ′ , L ′ (1) ), where L (1) : V → Σ

  0 | = 4 is the finer resolution level l = 2 with four labels. Chapter 3 The pyramid quantized Weisfeiler-Lehman graph representation 55 graph G = (V, E, L)

  3.2 : Theorem 3.3. Monotonicity property of the pyramid quantized Weisfeiler-Lehman kernel with the granularity of the node labeling The Weisfeiler-Lehman algorithm for a given height h of subtree patterns produces histograms whose intersection are monotonically decreasing in the granularity of the graph node labeling:

  d and a classification label Y i for each graph G i , we want to classify them through the information created by the Weisfeiler-Lehman algorithm after the quantization of each the vector labeled graph into a sequence of discrete labeled graphs with increasing granularity as described in Section 3.3. In order to maximize their classification performance and explore better the pyramid quantized Weisfeiler-Lehman features we examine two different approaches, one through the combination of the intersection Weisfeiler-Lehman kernel of the different pyramid levels in Section 3.4.1 and another through the evaluation of each individual subtree pattern φ (l) (h) of the Weisfeiler-Lehman algorithm in Section 3.4.2.

  Visualizations of the learned discriminant functions is easy to obtain when the Elastic Net is employed over the pyramid quantized Weisfeiler-Lehman subtree patterns. Each voxel is associated with a L × h subtree patterns, where L is the number of quantization levels of the label space and h is the height of subtree patterns created by the Weisfeiler-Lehman algorithm, and we just need to sum up their respective weights b i as provided by the Elastic Net. seen in Section 1.1, many problem domains can be naturally represented with graphs. The widespread use of graphs requires the development of efficient methods for representation and comparison. Although many algorithms have been developed the last decades for graph comparison between either unlabeled or discrete labeled graphs, as we have seen in Section 2, the efficient and expressive representation and comparison of graphs with continuous and/or high-dimensional vectors labels remains an open research problem. In Chapter 3 we tackled the graph comparison problem with continuous or high-dimensional vector labels with the introduction of the pyramid quantized Weisfeiler-Lehman graph representation. In this chapter, we evaluate this representation using real data from two different domains. The first evaluation, described in Section 4.1, comes from the fMRI analysis area and its objective is to discriminate between cocaine abusers and healthy control subjects, while in Section 4.2, we use two datasets with 3D shape meshes. For the first dataset the objective is to discriminate between healthy and patients subjects that suffer from a neuromuscular dystrophy, while in the second dataset we tackle the problem of multiclass object classification. 61 4.1 The pyramid quantized Weisfeiler-Lehman graph representation in fMRI analysis 4.1.1 IntroductionIn this section we evaluate the pyramid quantized Weisfeiler-Lehman graph representation in an fMRI data analysis problem. The functional magnetic resonance imaging (fMRI) is a wide spread, non-invasive modality used in the field of neuroimaging that measures brain activity by detecting associated changes in blood flow. The goal of fMRI data analysis is to detect relationships between brain activation and the designed task the subject performs during the scan. Depending on the specifics of the problem under investigation this goal can be translated as different objectives, such as localizing regions of the brain that participate in the specific task, or determining connectivity networks that correspond to brain function or even making predictions about psychological or disease states.

Chapter 4

 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification (BOLD) responses were measured as a function of time using a T2*-weighted single-shot gradient-echo EPI sequence (TE/TR=20/1600ms, 4mm slice thickness, 1mm gap, typically 33 coronal slices, 20cm FOV, 64 × 64 matrix size, 3.1 × 3.1mm in-plane resolution, 90 • flip angle, 200kHz bandwidth with ramp sampling, 128 time points and 4 dummy

Chapter 4

 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification Graph Construction To construct the graph representation, we have made use of k-nearest neighbor graphs on the voxels that were selected by an initial training of the Elastic Net (see Line 1 in Algorithm 4.1). We symmetrize the k-nn relationship by considering the edges to indicate an undirected graph structure. While other models of connectivity are of interest[START_REF] Sporns | Networks of the Brain[END_REF][START_REF] Wee | Enriched white matter connectivity networks for accurate identification of {MCI} patients[END_REF], we have found that the use of k-nearest neighbors to determine the graph topology yields good performance in general. Furthermore, the subtree statistics considered here implicitly account for longer distance connections for sufficiently deep subtree patterns. We set k = 5 in all experiments.Continuous node labels To enrich our graph representations of the fMRI contrast maps, we take advantage of the activation information. At each voxel selected by the Elastic Net for the construction of the graph, we label it with its activation. Since the activation has continuous values, our graph representation is transformed to a continuous labeled graph.Graph statistics Since the fMRI contrast maps are represented as graphs with continuous labels on the vertices, we explore the pyramid quantized Weisfeiler-Lehman graph representation introduced in Chapter 3. We quantized the continuous activation labels with the fixed-binning strategy (see Section 3.3.1.1), ending with a sequence of discretely labeled graphs with increasing granularity. Through the efficient Weisfeiler-Lehman algorithm, we aggregate statistics of subtree patterns of different depth h for all the levels of quantization. Finally, we control the complexity of our prediction while modeling non-linear interactions between voxels by adding a sparsity regularizer (the Elastic Net) over the statistics of subtree patterns (see Line 7 in Algorithm 4.1).

  In order to explore the behavior of the pyramid quantized Weisfeiler-Lehman graph representation for different combinations of quantization and depths of subtree patterns, we estimated the mean accuracies per quantized pyramid level and per subtree pattern depth, as shown in Figure4.2.

Figure 4 . 1 :Figure 4

 414 Figure 4.1: Mean accuracy and standard error on the cocaine addiction dataset. The compared methods are (left to right) Gaussian kernel ridge regression (GKRR), the Elastic Net on raw voxels, pyramid quantized Weisfeiler-Lehman (WLpyramid), and the Elastic Net with a concatenation of the raw voxels and the pyramid quantized Weisfeiler-Lehman features (Combined EN+WL). The horizontal red line indicates chance performance. The pyramid quantized Weisfeiler-Lehman features perform better than Gaussian kernel ridge regression and the Elastic Net on raw voxels with statistical significance.

  ure 4.1 are computed with the concatenation of features computed from all quantization levels, and an appropriate combination of subtree features across all quantization levels and depths of subtree patterns was selected by the Elastic Net.Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 69

Figure 4

 4 Figure 4.3: A visualization of the areas of the brain selected by Elastic Net. The selected regions correspond to areas previously implicated as being related to addiction [Goldstein et al., 2009].

Figure 4 .

 4 Figure 4.3 shows the areas selected by the Elastic Net, while Figure 4.4 and Figure 4.5 show the visualizations of the learned functions for the Elastic Net on raw voxels and the quantized Weisfeiler-Lehman graph representation respectively. Note that Elastic Net on the raw voxels was able to select the rostral anterior cingulate cortex (rostral ACC),

Figure 4 . 4 :

 44 Figure 4.4: A visualization of the function learned by Elastic net for control and cocaine subjects over the raw voxels. The visualization is illustrated over a graph, whose construction is described in Section 4.1.3, just for comparison with Figure 4.5.

Figure 4 . 5 :

 45 Figure 4.5: A visualization of the function learned by the pyramid quantized Weisfeiler-Lehman graph representation applied to control and cocaine addicted subjects.

Figure 4 . 6 :

 46 Figure 4.6: Examples of application that use 3D objects.Figure 4.6(a) show an screenshot from the video game Second life that stimulates a virtual 3D world.Figure 4.6(b) show a screen-shot from the on-line puzzle video game Foldit that uses 3D protein structure to understand how proteins fold for the use of drug development.Figure 4.6(c) shows the Digital Michelangelo project from Standford that aims to digitize cultural artifacts for cataloging, conservation and restoration.

  Figure 4.6: Examples of application that use 3D objects.Figure 4.6(a) show an screenshot from the video game Second life that stimulates a virtual 3D world.Figure 4.6(b) show a screen-shot from the on-line puzzle video game Foldit that uses 3D protein structure to understand how proteins fold for the use of drug development.Figure 4.6(c) shows the Digital Michelangelo project from Standford that aims to digitize cultural artifacts for cataloging, conservation and restoration.

  Figure 4.6: Examples of application that use 3D objects.Figure 4.6(a) show an screenshot from the video game Second life that stimulates a virtual 3D world.Figure 4.6(b) show a screen-shot from the on-line puzzle video game Foldit that uses 3D protein structure to understand how proteins fold for the use of drug development.Figure 4.6(c) shows the Digital Michelangelo project from Standford that aims to digitize cultural artifacts for cataloging, conservation and restoration.

  Figure 4.6: Examples of application that use 3D objects.Figure 4.6(a) show an screenshot from the video game Second life that stimulates a virtual 3D world.Figure 4.6(b) show a screen-shot from the on-line puzzle video game Foldit that uses 3D protein structure to understand how proteins fold for the use of drug development.Figure 4.6(c) shows the Digital Michelangelo project from Standford that aims to digitize cultural artifacts for cataloging, conservation and restoration.

Figure 4 . 7 :

 47 Figure 4.7: T1-weighted MR images of the calf from a healthy and patient subject. On the top, Figure 4.7(a) shows a slice of the MR image from a healthy subject, while on the bottom, Figure 4.7(b) shows a slice of the MR image from a patient with a neuromuscular disease.

Figure 4 . 8 :

 48 Figure 4.8: An example of an T1 weighted MR image with the seven segmented muscles of the calf. Each color represents a single muscle. Yellow represents the anterior tibialis, cyan the extensor digitorum longus, magenta the peroneous longus, white the posterior tibialis, blue the soleus, green the lateral gastrocnemius, and red the edial gastrocnemius. (Figure best viewed in color.)

Figure 4 . 9 :

 49 Figure 4.9: An example from the neuromuscular dystrophy dataset for soleus muscle before and after the decimation pre-processing step. On the left, Figure 4.9(a) shows the soleus muscle before the decimation procedure, while on the right Figure 4.9(b) show the soleus muscle after the decimation procedure.

  Figure 4.11 shows an example of the seven segmented muscles of the calf as 3D surfaces meshes from a healthy Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification (a) Without decimation (b) With decimation

Figure 4 . 10 :

 410 Figure 4.10: An example from the SHREC 2013 dataset for the biped class before and after the decimation pre-processing step. On the left, Figure 4.10(a) shows the biped 3D shape before the decimation procedure. while on the right 4.10(b) shows the shape biped 3D shape after the decimation procedure.

2Figure 4

 4 Figure 4.11: An example of the seven segmented muscles of the calf as 3D surface meshes from a healthy subject on the left and from a patient with neuromuscular disease on the right (continued).

Figure 4 . 11 :

 411 Figure 4.11: An example of the seven segmented muscles of the calf as 3D surface meshes from a healthy subject on the left and from a patient with neuromuscular disease on the right.

Figure 4 . 12 :

 412 Figure 4.12: Examples of each of the 20 classes of the SHREC 2013 dataset after the decimation preprocessing step.

  , keeping on average 350 vertices and 819 edges. Examples of the 3D meshes before and after the decimation process are shown Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification in Figure 4.9 and in Figure 4.10 for the neuromuscular dystrophy dataset and the SHREC 2013 dataset, respectively. Overall, this preprocessing step increases the speed of the algorithm and works also a regularizer on the pyramid quantized Weisfeiler-Lehman graph representation.

Figure 4 .

 4 Figure 4.13: An example of the two principal curvatures on a bottle object from the SHREC2013 dataset in a logarithmic scale. On the left, Figure 4.13(a) shows the minimum curvature, while the Figure 4.13(a) on the right shows the maximum curvature. (Figure best viewed in color.)

Figure 4 . 14 :

 414 Figure 4.14: An example of the minimum curvature on the muscle soleus of the calf from the neuromusclar dystrophy dataset. On the left, Figure 4.14(a) shows the minimum curvature for a patient with a neuromuscular disease, while on the right Figure 4.14(b) shows the minimum curvature for a healthy subject. (Figure best viewed in color.)

Figure 4 . 15 :

 415 Figure 4.15: The mean area under the ROC curve for the neuromuscular dystrophy dataset over 10 fold cross-validation procedure. The compared methods are the pyramid quantized Weisfeiler-Lehman kernel (WLpyramid) in blue, the pyramid bag of words model (pyramid BoW) in magenta, the multi-viewpoint rendering images procedure (Rendering) in red and a combination of the multi-viewpoint rendering procedure with the quantized Weisfeiler-Lehman pyramid kernel (Combined) in green.

  and in Figure 4.18.

  Figure 4.17 shows an example of the learned weights on a 3D object of the bird class for three different subtree depths (h ∈ {0, 1, 2}) of the Weisfeiler-Lehman algorithm, while Figure 4.18 shows the learned weight over all levels of the pyramid quantized Weisfeiler-Lehman kernel for depth h = 1 for all one-vs-rest classifiers. Note that the values of the learned weights increase as the color changes from blue to red. Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 87

Figure 4 .

 4 Figure4.16: The Receiver Operating Characteristic Curves for all one-vs-rest classifiers of the SHREC2013 dataset over a 10 fold cross-validation procedure. In blue is the pyramid quantized Weisfeler-Lehman kernel (WL pyramid Kernel), in magenta a pyramid bag of words approach (Pyramid Bow), in red is the Render Image descriptor (Render Image Baseline) and in green the combination of the pyramid quantized Weisfeler-Lehman kernel with the Render Image descriptor (Combined WL+Render). (Best viewed in color) (continued)

Figure 4 .

 4 Figure4.16: The Receiver Operating Characteristic Curves for all one-vs-rest classifiers of the SHREC2013 dataset over a 10 fold cross-validation procedure. In blue is the pyramid quantized Weisfeler-Lehman kernel (WL pyramid Kernel), in magenta a pyramid bag of words approach (Pyramid Bow), in red is the Render Image descriptor (Render Image Baseline) and in green the combination of the pyramid quantized Weisfeler-Lehman kernel with the Render Image descriptor (Combined WL+Render). (Best viewed in color) (continued)

Figure 4 .

 4 Figure4.16: The Receiver Operating Characteristic Curves for all one-vs-rest classifiers of the SHREC2013 dataset over a 10 fold cross-validation procedure. In blue is the pyramid quantized Weisfeler-Lehman kernel (WL pyramid Kernel), i magenta a pyramid bag of words approach (Pyramid Bow), in red is the Render Image descriptor (Render Image Baseline) and in green the combination of the pyramid quantized Weisfeler-Lehman kernel with the Render Image descriptor (Combined WL+Render). (Best viewed in color) (continued)

Figure 4 .

 4 Figure4.16: The Receiver Operating Characteristic Curves for all one-vs-rest classifiers of the SHREC2013 dataset over a 10 fold cross-validation procedure. In blue is the pyramid quantized Weisfeler-Lehman kernel (WL pyramid Kernel), in magenta a pyramid bag of words approach (Pyramid Bow), in red is the Render Image descriptor (Render Image Baseline) and in green the combination of the pyramid quantized Weisfeler-Lehman kernel with the Render Image descriptor (Combined WL+Render). (Best viewed in color)

-

  Figure 4.17: An example of the learned weights of the pyramid quantized Weisfeiler-Lehman Kernel on a 3D object of the class bird from the SHREC 2013 dataset for three different subtree depths (h ∈ {0, 1, 2}). The values of the learned weights increase as the color changes from blue to red. See Section 3.4.1.3 for details of the visualization. (Figure best viewed in color).

Figure 4 . 18 :

 418 Figure 4.18: Visualization of the learned weights of the pyramid quantized Weisfeiler-Lehman kernel of subtree patterns with depth h = 1 for each vertex on the 3D surface mesh per Class-vs-Rest Classifier for the SHREC2013 dataset. The values of the learned weights increase as the color changes from blue to red. The evaluation of the weight per vertex is derived in Section 3.4.1.3.(Figure best viewed in color.) (continued)

Figure 4 .-

 4 Figure 4.18: Visualization of the learned weights of the pyramid quantized Weisfeiler-Lehman kernel of subtree patterns with depth h = 1 for each vertex on the 3D surface mesh per Class-vs-Rest Classifier for the SHREC2013 dataset. The values of the learned weights increase as the color changes from blue to red. The evaluation of the weight per vertex is derived in Section 3.4.1.3.(Figure best viewed in color.) (continued)

Figure 4 . 18 :

 418 Figure 4.18: Visualization of the learned weights of the pyramid quantized Weisfeiler-Lehman kernel of subtree patterns with depth h = 1 for each vertex on the 3D surface mesh per Class-vs-Rest Classifier for the SHREC2013 dataset. The values of the learned weights increase as the color changes from blue to red. The evaluation of the weight per vertex is derived in Section 3.4.1.3.(Figure best viewed in color.) (continued)

Figure 4 . 18 :

 418 Figure 4.18: Visualization of the learned weights of the pyramid quantized Weisfeiler-Lehman kernel of subtree patterns with depth h = 1 for each vertex on the 3D surface mesh per Class-vs-Rest Classifier for the SHREC2013 dataset. The values of the learned weights increase as the color changes from blue to red. The evaluation of the weight per vertex is derived in Section 3.4.1.3.(Figure best viewed in color.)

  2. The performance is evaluated as the mean correlation over 100 trials of random permutations, where in each trial, 80% of the data are used to train the method, while the remaining 20% are used to evaluate the performance. We evaluate both the Elastic Net and k-support norm for same λ 2 and λ values respectively, where λ, λ 2 ∈ {10 2 , 10 3 , 10 4 , 10 5 , 10 6 }. For the parameter selection a similar inner scheme of random permutations is used. In this inner scheme the 90% of the training data are used to train the method and rest 10% of the training to select the model's parameter over 20 trials of random permutations.In Figure5.2 the performance of the regularization methods is plotted as a function of sparsity. More specifically, Figure5.2(a) shows the mean correlation between LASSO and Elastic Net against the number of non-zero variables (i.e. voxels) that is correlated with the λ parameter in Equation5.2 and with the λ 1 in Equation5.4, while Figure 5.2(b) shows the mean correlation for the k-support norm against different k values -which Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 107

Figure 5

 5 Figure5.2: Mean Pearson correlations between the label and prediction on the holdout data over 100 trials for the free-viewing dataset (higher values indicate better performance). Error bars show the standard error of the mean. The LASSO achieves its best performance with a sparsity level substantially lower than the Elastic Net, as it suppresses correlated voxels (Figure5.2(a)). The k-support norm performs better than the LASSO, Elastic Net, or Laplacian regularization reported in[START_REF] Blaschko | Semi-supervised kernel canonical correlation analysis with application to human fmri[END_REF], and is a promising candidate for sparsity in fMRI analysis (Figure5.2(b)).(Figure best viewed in color.)

  Figure5.2: Mean Pearson correlations between the label and prediction on the holdout data over 100 trials for the free-viewing dataset (higher values indicate better performance). Error bars show the standard error of the mean. The LASSO achieves its best performance with a sparsity level substantially lower than the Elastic Net, as it suppresses correlated voxels (Figure5.2(a)). The k-support norm performs better than the LASSO, Elastic Net, or Laplacian regularization reported in[START_REF] Blaschko | Semi-supervised kernel canonical correlation analysis with application to human fmri[END_REF], and is a promising candidate for sparsity in fMRI analysis (Figure5.2(b)).(Figure best viewed in color.)

  T1 and T2 weighted images are wide used MR images that depict the structure of the human body through the difference in the spin-lattice or T1 relaxation time of various tissues within the body in the former or through the difference in the spin-spin or T2 relaxation time of various tissues in the latter. Both techniques can differentiate fat from water -with water appearing darker and fat brighter on T1 weighted images, while fat shows darker and water lighter in T2 weighed images. Finally, Diffusion Tensor Imaging is an imaging modality that captures the diffusion of water in tissues, and along with it, important structural information. It has been widely used in the study of the connectivity of the human brain [Le Bihan et al., 2001]. Nonetheless, it has also been used in different clinical scenarios. Among them, one may cite the study of the human tongue [Gilbert and Napadow, 2005], the heart muscle [Gilbert and Napadow, Chapter 5 Regularization methods for analyzing Magnetic Resonance Imaging data 111 2005] and the human calf muscle [

  a 1.5 T MRI scanner. The obtained volumes had a size of 64 × 64 × 20 voxels and a voxel resolution of 3.125mm × 3.125mm × 7mm. T1-and T2-weighted MR images were acquired at the same time. As a consequence, the image volumes are naturally coregistered. Diffusion weighted images were acquired using the following parameters: repetition time (T R)=3600ms, echo time (T E)=70ms, slice thickness of 7mm and b value of 700s/mm 2 with 12 gradient directions and 13 repetitions. Considering anisotropic diffusion, diffusion tensors D were estimated with the use of medInria software. features vs Combined T1-T2-DTI features Combined T1-T2-DTI features T1-T2 features

Figure 5 . 6 :

 56 Figure 5.6: Mean ROC curves over 1000 trials. In red is the k-support regularized SVM using features both structured and DTI features, while in blue the k-support regularized SVM using only structured features. Using T1 and T2 weighted features, with the combination of DTI features gives the best performance in discriminating the two neuromuscular diseases (Figure best viewed in color).

  k-d trees, for the fixed-binning scheme or with a hierarchical clustering algorithm for data-guided binning scheme. The complexity of the resulting quantization is bounded by O(d max(|V |, k)L), where d is the dimension of the label space, |V | is the number of vertices to be quantized, k is the maximum histogram index value in a single dimension, and L is the number of pyramid levels [Grauman and Darrell, 2007a]. With an appropriate implementation we may constrain k ≤ |V |, and we may ensure that L is logarithmic in |V |, resulting in a simplified complexity of O(d|V | log |V |).

  . . . . . 58 3.4.1.3 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4.2 Elastic net on the pyramid quantized Weisfeiler-Lehman subtree features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 61 4.1 The pyramid quantized Weisfeiler-Lehman graph representation in fMRI analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Directed and undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Labeled graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Neighborhood and degree of a node. . . . . . . . . . . . . . . . . . . . . . 2.4 Graph walk, path, cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Subtree patterns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Example of the graph edit distance methodology. . . . . . . . . . . . . . .

	List of Figures
	2.1

3.1 Example of Weisfeiler-Lehman test of graph isomorphism . . . . . . . . . 3.2 Examples of the quantization strategies of a continuous space. . . . . . . . 3.3 Example of the quantization step of the pyramid quantized Weisfeiler-Lehman graph representation . . . . . . . . . . . . . . . . . . . . . . . . .

  3 The pyramid quantized Weisfeiler-Lehman graph representation

	2										2
	0										0
	-2										-2
	-4										-4
	-6										-6
	-8										-8
	-10										-10
	-12										-12
	-14										-14
	-16										-16
	-16	-14	-12	-10	-8	-6	-4	-2	0	2	4	-16	-14	-12	-10	-8	-6	-4	-2	0	2	4
										(a) Fixed binning
	2										2
	0										0
	-2										-2
	-4										-4
	-6										-6
	-8										-8
	-10										-10
	-12										-12
	-14										-14
	-16										-16
	-16	-14	-12	-10	-8	-6	-4	-2	0	2	4	-16	-14	-12	-10	-8	-6	-4	-2	0	2	4
										(b) Data guided binning

  4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 65 Algorithm 4.1 The statistical learning pipeline for fMRI analysis with sparse subgraph statistics. Require: Training set D = {(v i , y i ), i = 1, . . . , n}. 1: Compute βlin from the objective in Equation (5.4) with x lin ≡ vec v. 2: Construct k-nearest neighbor graphs for all training samples from the voxels associated with non-zero βlin 3: for each level in the quantization pyramid do

	4:

Table 4 .

 4 1: Mean accuracy over the hold-out data of 50 trials of the pyramid quantized Weisfeiler-Lehman graph representation for four different subtree pattern depths, h ∈ {0, 1, 2, 3}. Maximum performance is achieved with subtree patterns up to depth two.

	Pyramid Quantized Weifeiler-Lehman
	h	0	1	2	3
	Accuracy 54.00% 57.14% 64.28% 63.42%

  Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification 85

		WLpyramid pyramid BoW Rendering Combined
	Accuracy	78.00%	73.00%	75.50%	82.93%
	AUC	0.6410	0.6361	0.6300	0.6648
	Table 4.2:

  Chapter 4 Applications of the pyramid quantized Weisfeiler-Lehman graph representation in neuroimaging and shape classification

	Class	WLpyramid pyramid BoW Rendering Combined
	Bird	0.85	0.83	0.85	0.86
	Bicycle	0.84	0.87	0.90	0.90
	Biped	0.89	0.88	0.99	0.99
	Biplane	0.60	0.63	0.68	0.69
	Bird	0.73	0.73	0.80	0.80
	Bottle	0.76	0.76	0.79	0.80
	Car	0.78	0.79	0.80	0.80
	CellPhone	0.74	0.80	0.88	0.89
	Chair	0.69	0.68	0.70	0.72
	Cup	0.85	0.84	0.88	0.88
	Desklamp	0.80	0.80	0.88	0.89
	Fish	1.00	1.00	1.00	1.00
	Floorlamp	0.80	0.77	0.89	0.89
	Insect	0.64	0.60	0.62	0.66
	Monoplane	0.84	0.82	0.88	0.90
	Mug	0.82	0.82	0.85	0.87
	Phone	0.83	0.74	0.72	0.83
	Quadruped	0.89	0.86	0.97	0.98
	Sofa	0.76	0.75	0.74	0.75
	Wheelchair	0.81	0.79	0.88	0.90
	Average	0.80	0.79	0.84	0.85
	Table 4.3:

The Ki,j is a special family of graphs, known as bipartite graphs, that it is possible to partition the vertices of the graph G into two subsets V1 and V2 such that every edge of G connects a vertex in V1 to a vertex in V2 and i, j is the degree of every vertex in the V1 and V2 respectively.

Note that in the pair (G, u) by G we declare the identifier of the graph G in the graph dataset.

Note that when we are interested in the quantization of the R d given a set of vector labeled graphs G = {Gi = (Vi, Ei, Li)} 1≤i≤n , where Li : Vi → R d , then D is number of unique values in the union of the images of the label functions Li ∀i ∈ {1, . . . , n}.

In practice when the input space is very large, we can randomly select a subset of representative data to perform the agglomerative hierarchical clustering.

We could also use the linear kernel over the subtree patterns, but the histogram intersection kernel has been shown to give better results[START_REF] Odone | Building kernels from binary strings for image matching[END_REF].

(a) Elastic Net on raw voxels -Control (b) Elastic Net on raw voxels -Cocaine

http://www.itksnap.org/pmwiki/pmwiki.php

http://dataset.dcc.uchile.cl/

(d) Anterior Tibialis (e) Extensor Digitorum Longus (f) Peroneous Longus (g) Posterior Tibialis

http://med.inria.fr/

Acknowledgements

For n pairs of discretely labeled graphs, the Weisfeiler-Lehman subtree kernel requires O(nhe + n 2 hv), where e is the maximal number of edges, v is the maximal number of vertices and considers subtree patterns up to height h.

List of Algorithms

Imaging data

Magnetic resonance imaging (MRI) is a widespread medical imaging technique used to visualize internal structures of the body in detail. MRI makes use of the nuclear magnetic resonance (NMR) property to image nuclei of atoms inside the body. The NMR property allows the atomic nuclei in the body to be aligned when powerful magnetic field is applied. Applying different radio frequencies causes the nuclei to produce a rotating magnetic field that is detected by the MRI scanner and this information is recorded to construct the image of the scanned area of the body. Magnetic field gradients cause nuclei at different locations to rotate at different speeds, which allows spatial information to be recovered using Fourier analysis of the measured signal. MRI provides good contrast between the different soft tissues of the body, which makes it especially useful in imaging the brain, muscles, the heart, and cancers compared with other medical imaging techniques such as computed tomography (CT) or X-rays. Unlike CT scans or traditional X-rays, MRI does not use ionizing radiation [START_REF] Berger | Magnetic resonance imaging[END_REF].

In clinical practice, MRI is usually used to distinguish pathological tissue, such as a brain tumor, from normal tissue. There are a number of different types of MRI scans with different properties, but in this thesis we focus our analysis in the following MRI (5.12)

where γ is the largest eigenvalue of X T X. In this case, Equation 5.10 has as special cases the LASSO when k = 1 and the ridge regression when k = d respectively.

Hinge Loss

Since Hinge loss is not differentiable, we apply a Huber approximation to Hinge loss as in [START_REF] Chapelle | Training a support vector machine in the primal[END_REF]. The Huber approximation of the Hinge loss is defined as follows:

where h is a parameter to choose, typically between 0.01 and 0.5 The gradient of the Huber-Hinge approximation loss is defined as : where γ is the largest eigenvalue of X T X, as before. The use of the Huber-Hinge approximation loss with the k-support norm can be described as a close approximation to the following optimization problem: min

which is a modification of the classical Support Vector Machine [START_REF] Cortes | Support-vector networks[END_REF]. This learning algorithm uses the Huber approximation to the Hinge loss, which arbitrarily closely approximates the Hinge loss as h → 0 while retaining differentiability.

Moreover, it employs the k-support norm as a structured sparsity regularizer and we call it the k-support regularized SVM (ksup-SVM) [START_REF] Gkirtzou | Sparse classification with MRI based markers for neuromuscular disease categorization[END_REF]. This approach enables the learning algorithm to select a sparse but correlated subset of discriminative variables. ksup-SVM has two input parameters, the λ > 0 regularization parameter and k ∈ {1, . . . , d}, where d is the dimension of the feature space, the parameter that negatively correlates with the sparsity. The limit cases are the support vector machine (SVM) [START_REF] Cortes | Support-vector networks[END_REF] when k = d and the ℓ 1 regularized SVM [START_REF] Zhu | 1-norm support vector machines[END_REF] when k = 1. The ksup-SVM can be seen as an alternative to the Elastic Net regularized SVM [START_REF] Wang | The doubly regularized support vector machine[END_REF], but with a tighter convex relaxation to correlated sparsity.

Figure 5.1 shows both the squared and the hinge loss as a function of the margin y • f (x) for a two class classification problem in which y ∈ {-1, +1}. It also shows the zero-one misclassification loss, which gives unit penalty for negative margin values and no penalty for all positive ones. The classification rule used here is sign(f (x)), which implies that observations with positive margin y i • f (x i ) > 0 are classified correctly, where those with negative margin y i • f (x i ) < 0 are misclassified. Both the hinge loss and the squared loss can be viewed as continuous and convex upper bounds to the zero-one misclassification loss. The hinge loss penalizes increasingly negative margin values, while it gives no penalty for all positive ones. Squared loss also penalizes increasingly the negative margin values, but for margin values y i • f (x i ) > 1 it increases quadratically, therefore placing increasing influence on observations that are correclty classified with increasing certainty.

Squared loss consequently has two undesirable properties compared with hinge loss (a) it are negative correlated with the number of non-zero coefficients. LASSO achieves a maximum mean correlation of 0.12 for 45 non-zero variables, Elastic Net a maximum mean correlation of 0.1313 for 1950 non-zero variables, while k-support norm a maximum of 0.1398 for k = 200. This is substantially higher than was previously reported result in [START_REF] Blaschko | Semi-supervised kernel canonical correlation analysis with application to human fmri[END_REF]. According to a Wilcoxon signed rank test, the performance of k-support norm is statistically significantly better than the performance of both LASSO and Elastic Net (p-value was ≪ 0.05).

We have additionally visualized the brain regions predicted when applying the LASSO and the k-support norm to the cocaine addiction dataset (see Section 5.2.2.2). For each, we have selected slices through the brain that maximize the sum of the absolute values of the weights predicted by the respective methods. These results are presented in Figure 5.3 and discussed in the following section.

Discussion

The main area of activity shown in Figure 5.3(b) is the rostral anterior cingulate cortex (rostral ACC). It has been shown to be deactivated during the drug Stroop as compared to baseline in cocaine users versus controls even when performance, task interest and engagement are matched between the groups [START_REF] Goldstein | Anterior cingulate cortex hypoactivations to an emotionally salient task in cocaine addiction[END_REF] and that its activity is normalized by oral methylphenidate [START_REF] Rita Z Goldstein | Oral methylphenidate normalizes cingulate activity in cocaine addiction during a salient cognitive task[END_REF]-which similarly to cocaine blocks the dopamine transporters increasing extracellular dopamine-an increase that was associated with lower task-related impulsivity (errors of commission). This region was responsive (showed reduction in drug cue reactivity) to pharmacotherapeutic interventions in cigarette smokers [START_REF] Culbertson | Effect of bupropion treatment on brain activation induced by cigarette-related cues in smokers[END_REF][START_REF] Franklin | Dopamine transporter genotype modulation of neural responses to smoking cues: confirmation in a new cohort[END_REF], and may be a marker of treatment response in other psychopathology (e.g., depression). The LASSO, on the other hand, does not show a meaningful sparsity pattern (see Figure 5.3(a)).

In this section, we have investigated the applicability of sparsity regularizers in fMRI analysis. We have shown that the k-support norm can give better predictive performance than the LASSO and Elastic Net, while having favorable mathematical and computational properties. Furthermore, the brain regions implicated in addiction by the k-support norm coincide with previous results on addiction, indicating that the ksupport norm is additionally useful for generating sparse, but correlated, regions suitable for interpretation in a medical-research setting. In the specific task of cocaine addiction, the k-support norm has implicated the involvement of the rostral ACC, in line with previous studies, while the LASSO did not lead to an interpretable result. We therefore consider the k-support norm as a promising tool for sparsity in fMRI analysis and believe it merits future study. While initial experiments have shown promising results with the The images were segmented by an expert in the following 7 classes/muscle groups: 1) soleus (SOL), 2) lateral gastrocnemius (LG), 3) medial gastrocnemius (MG), 4) posterior tibialis (TP), 5) anterior tibialis (AT), 6) extensor digitorum longus (EDL), and 7) peroneous longus (PL). An example of the segmented muscle can be seen in Figure 4.8. It is planned to automate the segmentation process in future work. In the meantime, the approach provides a strategy to avoid an invasive biopsy. Note that a superset that also contained this dataset were also used in Section 4.2, where 3D shapes of the muscles where extracted by the T1 weighted MR images for a shape classification problem between healthy and patient subjects.

For every anatomical region, we extracted features from both the structural and the diffusion data. From the structural data, we extracted for every muscle: 1) the absolute volume, 2) the mean T1 signal, 3) the mean T2 signal, and 4) the Signal to Noise Ration (SNR). For the diffusion data, we calculated for every muscle the mean values of the following scalar measures:

1. the eigenvalues λ 1 , λ 2 , λ 3 of the diffusion tensor D,

the trace of the diffusion tensor

which is a rotationally independent value and it indicates the average amount of diffusion,

the Fractional Anisotropy

which is also rotationally invariant, as the trace, takes values between 0 and 1 and measures the anisotropy of the tensor. When FA is close to 0 then the tensor is close in shape to a sphere and there are no privileged directions of diffusion, while when FA is close to 1 the tensor is close to the shape of a "cigar", where the long axis of the ellipsoid is likely to correspond to the local fiber orientation, 4. the volume of the tensor D

which is also rotationally invariant,

the linear coefficient

(5.21) and 6. the planar coefficient

Both the linear coefficient and the planar coefficient lie between 0 and 1 and indicate the shape of the diffusion. For example a high value of the linear coefficient indicates a "cigar" shape diffusion, while a high value in the planar coefficient indicates a "flying saucer" diffusion shape.

These scalar measures were estimated with the use of medInria software. The resulted 84 variables were whitened and centered prior to applying the learning algorithms.

Results

In order to better explore the power of k-support norm regularization method with the two different loss functions, we also train a number of supervised learning methods using the same features. More specifically, we examine the k nearest neighbor algorithm [Wang et al., 2008], the support vector machine (SVM) [START_REF] Cortes | Support-vector networks[END_REF] for a number of different kernels. The k nearest neighbor method (knn) is a simple, non-linear classification algorithm that classifies each new subject according to the majority of the labels of the k nearest neighbors, given a specific distance function. We examine the knn algorithm with Euclidean distance and k ∈ {1, 3, 5, 7, 10}. The support vector machine constructs a hyperplane in a high or infinite-dimensional space by maximizing the margin of the different classes, while minimizing the classification error. For the SVM, we examine the following kernel functions, i) linear, ii) polynomial of third degree, and iii) radial basis function (RBF) with a soft-margin parameter C ∈ {10 -3 , 10 0 , 10 3 }. For the k-support regularized squared loss and for the ksup-SVM we examine the following combinations of parameters λ ∈ {1, 10, 1000} and k ∈ {1, 10, 20, 40, 80}.

To approximate the generalization accuracy of the classification methods using the structural and DTI tensor features, we use a random splitting scheme with 1000 trials. In each trial, a random selection of 80% of the data are used to train the methods, while the remaining 20% are used to evaluate their performance.

Figure 5.5 shows the mean ROC curve across all trials, while Table 5.1 gives the mean classification accuracy and area under the curve over 1000 trials. ksup-SVM outperforms the rest of the methods by achieving a mean area under the curve (AUC) of 0.7141 and mean accuracy 77% ± 0.013. The k-support norm regularized squared loss also performs well with a mean AUC of 0.694 and mean accuracy 72% ± 0.006, while knn

The pyramid quantized Weisfeiler-Lehman graph representation

In Chapter 3 we introduced a novel algorithm, the pyramid quantized Weisfeiler-Lehman graph representation that tackles the problem of graph comparison for continuous or vector labeled graphs. To the best of our knowledge this novel algorithm is the first attempt to approach the graph comparison problem with continuous or vector labels. The pyramid quantized Weisfeiler-Lehman graph representation considers statistics of subtree patterns based on the Weisfeiler-Lehman algorithm [START_REF] Weisfeiler | A reduction of a graph to a canonical form and an algebra arising during this reduction[END_REF]],

which has recently been employed in the construction of a graph kernel [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF] for discrete labeled graphs. The key advantage of these subtree statistics, which are tree structures constructed recursively from each node in the graph up to a predefined depth h, is that they are linear-time in the number of edges in the graph.

Moreover, they make use of an efficient hashing scheme in order to only enumerate the relevant (non-zero) dimensions of an exponentially sized feature space. In addition to these computational benefits, Weisfeiler-Lehman graph kernels have been shown

123

Chapter 6 Conclusions and 10. Many applications, such as document classification in data mining or biological network analysis, could benefit more if efficient algorithm that incorporates information concerning the similarity between labels is designed. An other perspective that derives from the previous problem when considering subtree patterns is the graph comparison through inexact matching of the subtree patterns. Solving this problem would benefit applications where graphs tend to be noisy or incomplete or the neighborhood of a node is to big for an exact match.