Graph-Based Semi-Supervised Learning (G-SSL) exploits labeled data along with the structure of unlabelled data to build better classifiers. This classification paradigm has received considerable attention since modern applications allow to collect large amounts of unlabelled but structured data, naturally encoded by a graph, in a relatively easy and inexpensive manner, while tagged data is expensive to obtain. However, despite its great success, the performance of G-SSL can still be improved, particularly in cases of graph topologies with unclear clusters, or unbalanced data settings, that this dissertation aims to address.

The main contribution of this dissertation is a novel algorithm for G-SSL coined as the L -PageRank method: a generalization of the PageRank-based G-SSL by using (nonnecessarily integers) powers of the combinatorial Laplacian matrix L ( > 0). The theoretical analysis of L -PageRank is divided in two regimes. In the regime < 1, we show that L -PageRank extends the standard PageRank algorithm to adopt the dynamics of Lévy processes: where random walkers are now allowed to perform long-distant jumps in a single step. In the regime > 1, we show that L -PageRank operates on signed graphs: where nodes belonging to one same class are more likely to share positive edges while nodes from different classes are more likely to be connected with negative edges. Our main theoretical contribution is to show that L -PageRank is guaranteed to outperform the standard PageRank method if is properly chosen. By means of numerical experimentations we point the existence of an optimal value maximizing performance, for which a method for its automatic estimation is devised and assessed. The practical evaluation of L -PageRank on synthetic and real-world datasets commonly used for classification shows that (i) in the regime < 1, L -PageRank can leverage the Lévy flight random walkers to enhance the detection of classes with complex local structures, such as hubs or sub-clusters; and (ii) in regime > 1, due to the signed graphs enhancing the separability of the data, L -PageRank can significantly improve classification performance and also override the issue of unbalanced labelled data.

To increase the value of L -PageRank, we investigate fast and efficient implementations that avoid the costly matrix inversion step demanded by its closed form solution. Towards this goal, by leveraging results from the field of Graph Signal Processing, we derive extensions of Power Iteration and Gauss-Southwell, successful algorithms for efficient computation of the standard PageRank algorithm, to L -PageRank. Moreover, the dynamic versions of Power Iteration and Gauss-Southwell, which can update the solution of standard PageRank in sub-linear time complexity when the graph evolves or new data arrive, are also extended to L -PageRank. III

This dissertation is the result of three years of work carried at the Dante team of the LIP laboratory from the ENS Lyon. During these three fruitful years, many people have directly or indirectly contributed to the realization of this dissertation, whom I would like to thank.

First and foremost, I would like to thank my thesis advisors: Paulo Gonçalves and Patrice Abry. To you both, thank you for welcoming me to your group. I can not be as grateful as with you for giving me the opportunity to live this wonderful experience. Thank you for helping me in an endless list of things that made my PhD possible. From getting an apartment, going through obtaining funding for me, up to supporting me in my desire of doing an international visit to EPFL, you have been as supportive as someone can be. I would also like to thank you for your great academic influence. Many thanks for showing me how to become a researcher, for all those endless meetings where you would push me to go beyond my boundaries, and for inviting me to take part in numerous important projects and collaborations. I would like to thank all my collaborators. A big thanks to Sarah de Nigris and Konstantin Avrachenkov for all the discussions and joint work on Lévy flights. Many thanks to Romain Fontugne for the discussions and joint work on Internet routing. I am also grateful to Pierre Vandergheynst, Benjamin Ricaud and Andreas Loukas for hosting me at the LTS2 group from EPFL and for all the discussions on evolving graph data and updating methods.

I also thank all the members of my jury for the keen interest they have shown in reviewing this thesis work. I thank the CONACyT and the Labex Milyon for the financial support. I would also like to thank all the people from the Dante team. In particular, I thank Gaëtan, Samuel, Jacob, Marija, Mohammed, Hadrien, Sébastien, and Mikhail for all the passionate discussions and good memories.

Last but not least, I thank all my family and friends from the bottom of my heart. Especially, I would like to thank Nadine for the emotional support. I La principale contribution de cette thèse est une extension des méthodes de G-SSL classiques, qui nous a conduit à une approche originale, appelée L -PageRank. L'idée que nous avons développée consiste à élever la matrice combinatoire Laplacienne de graphequi est au centre de la méthode PageRank -à des puissances (non nécessairement entières) L ( > 0). L'analyse théorique de notre proposition nécessite alors de considérer deux régimes conceptuellement distincts. Pour le cas dit fractionnaire, où 0 < < 1, nous montrons que L -PageRank généralise le concept de marches aléatoires qui sous-tend l'algorithme de PageRank standard à des dynamiques de marches plus riches, tels que les vols de Lévy. Ces derniers permettent aux marcheurs aléatoires d'atteindre des noeuds du graphes, distants de leur position courante, en un seul saut, accélérant ainsi la diffusion des étiquettes à travers les noeuds d'une même classe. L'autre régime que nous avons étudié correspond aux valeur de > 1. Contrairement au cas précédent, L introduit ici des poids négatifs sur les liens, rendant la méthode ininterprétable en termes de matrices de probabilité de transition. Nous avons alors montré que L -PageRank effectue une classification sur un nouveau graphe signé, où les noeuds appartenant à une même classe ont une plus grande probabilité d'être connectés via des liens positifs, alors que des noeuds de classes différentes sont plus susceptibles d'être connectés par des liens pondérés négativement. La principale contribution théorique de notre travail est de garantir que L -PageRank atteint des performances de classification supérieures à celles de PageRank standard, dès lors que le paramètre est correctement sélectionné. Expérimentalement donc, nous vérifions l'existence d'une puissance optimale qui max-V R ÉSUM É imise les performances de L -PageRank. Puis, nous proposons une routine empirique opérationnelle qui permet de déterminer à partir du graphe des données et des étiquettes disponibles, la valeur optimale de la puissance .

Pour illustrer les améliorations apportées par les méthodes proposées, nous avons testé L -PageRank sur un grand nombre de jeux de données, couramment utilisées pour évaluer les performances des classifieurs semi-supervisés. Les résultats obtenus montrent que: (i) dans le rgime 0 < < 1, les vols de Lévy permettent à L -PageRank de mieux identifier les classes prsentant des structures locales complexes, telles que des hubs ou des sous-groupes;

(ii) avec > 1, les graphes signés accentuent significativement la séparabilité des classes, ce qui permet en particulier aux L -PageRank de répondre plus efficacement au problème du déséquilibre du nombre de données étiquetées par classes.

Les contributions de ce travail de thèse sont également d'ordre algorithmique.

Un autre avantage des méthodes d'apprentissage semi-supervisé sur graphe est de fournir une solution explicite au problème de classification. Cependant, les expressions analytiques de ces solutions impliquent toutes, quel que soit L -PageRank choisi, une inversion matricielle coûteuse, mal adaptée aux grands jeux de données. Nous avons donc développé des implémentations efficaces de L -PageRank, qui s'appuient sur des résultats obtenus en traitement du signal sur graphes. Comme cela avait déjà été fait pour PageRank standard, nous utilisons des méthodes d'approximation de type Power Iteration et Gauss-Southwell, pour obtenir des solutions numériques de L -PageRank capables de passer à l'échelle. Enfin, nous nous intéressons au contexte de l'apprentissage évolutif sur graphes, où, soit la strucuture de graphe change au cours du temps, soit les données arrivent séquentiellement. Dans les deux cas, il faut pouvoir intégrer ces évolutions à la classification, sans avoir à re-calculer intégralement la solution à chaque pas de temps. Nous avons alors développé des algorithmes dynamiques incrémentaux en complexité sous-linéaire, permettant de calculer la solution de L -PageRank au fil de l'eau.

Dans la dernière partie de cette thèse, nous traitons deux applications originales de G-SSL dans le contexte du routage Internet. Tout d'abord, nous utilisons PageRank standard pour fournir une caractérisation inédite de la portée de l'influence des zombies Boarder Gate Protocol (BGP). Ces derniers sont des routeurs qui ont conservé les chemins vers certains préfixes ayant déjà disparu du réseau Internet. En mesurant l'état d'un groupe restreint de systèmes autonomes (AS), nous montrons que PageRank permet de prédire l'état des routeurs dans d'autres AS, sur lesquels nous n'avons aucune mesure. La précision atteinte est alors de 97% pour les AS avec routeurs zombies et 99 % pour les AS n'ayant que des routeurs à jour. Les résultats fournis par cette classification G-SSL nous permettent ensuite de caractériser le domaine d'influence des zombies BGP. Dans une deuxime application, nous abordons le problème de l'identification des systèmes autonomes (AS) connectés par des liens inter-AS, et ce, uniquement à partir du réseau d'adresses IP et des registres publics d'AS. Des expériences à partir de mesures traceroute d'Internet montrent que seuls les L -PageRank, avec > 1, permettent de résoudre cette tâche sans erreur, alors même lorsqu'on ne dispose pas d'exemples étiquetés par l'expert, pour la totalité des AS (i.e., des classes).

VI R ÉSUM É

List of Tables Personalized Pagerank vector with parameter ↵ and seed y in evolved graph arma ⇢, (y) ARMA filter with coefficients ⇢, and seed y arma ⇢, (y) ARMA filter with coefficients ⇢, and seed y in evolved graph XVI SYMBOLS

Introduction

Data have a fundamental role in society. It can be argued that one important reason for the progress of civilization is that we have leveraged data to take better decisions. For instance, the deep understanding of the data output by medical tests has allowed doctors to make more precise diagnoses and to better identify optimal treatments. It is thanks to weather records and CO2 measurements that we now better understand the impact that our carbon footprint has on climate change. Also, evolutionary theory by natural selection, which is one of the major breakthroughs in human history, was devised from data collected from birds.

In today's world, data are more important than ever. They are involved in almost any human related activity. From listening to music records, to trade in goods, passing through medical examinations, up to sharing photos on internet. All these activities generate massive amounts of data which, due to technological progress, we can now store and effortlessly access. If we have historically used few available data to better solve problems, then the monumental amount of data at our disposal nowadays is a gold mine to devise a better world.

Over the years, the machine learning and the signal processing communities have proposed numerous data classification techniques to better organize and understand the large mass of data arising from the big data trend. Classification refers to the task of grouping data instances according to some properties they have in common. For example, given a set of documents, classification can consist in separating them by topic. From a set of bank transactions, classification may aim to group those who correspond to a fraud. From a set of emails, it consists in identifying those that are spam. It can also be the categorisation of music files according to genre, instruments, or language. The list of possible data applications is endless and classifiers constitute one of the essential tools to capitalize on them.

Yet, one fundamental question that arises is why state-of-the-art classifiers, which have been shown to categorize pet images with even better accuracy than humans [START_REF] He | Deep residual learning for image recognition[END_REF], have had negligible impact in important areas such as medicine [2], despite an estimated 1.7 billion users of healthcare applications [START_REF] Bonoto | Efficacy of mobile apps to support the care of patients with diabetes mellitus: a systematic review and meta-analysis of randomized controlled trials[END_REF] and a market of roughly 600 million wearable medical devices [4] generating data? The answer is that classifiers need to learn: a process that involves discerning what are the determining features that make two points share a class (or not) after seeing large amounts of data instances annotated with their true label. The issue is that annotated data do not follow the big data trend, instead they remain scarce in numerous application domains, such as medicine, in which the process of hand-labelling INTRODUCTION data usually requires from the intervention of human experts and the use of specialized devices. In this context, it is certainly unfeasible that medical experts can tag an amount of examples equivalent to the 1.28 million annotated images needed by the classifier of [START_REF] He | Deep residual learning for image recognition[END_REF] to attain such reliable predictions. This lack of sufficient labelled data necessary to make supervised classifiers trustworthy has caused most of the data that we continue to collect to remain unanalyzed.

How to draw reliable inferences when the labelled data is insufficient? This fundamental question is the fuelling force of the modern classification paradigm known as semisupervised learning on graphs (G-SSL). In G-SSL, classifiers not only learn from annotated examples but also from unlabelled data. This gives them the ability to take advantage of the big data trend and the power to deliver reliable inferences even from limited amounts of labelled data. The idea of learning from unlabelled data is not new to G-SSL, as previous approaches under the umbrella of unsupervised learning have noticed that raw data posses structural patterns informative of its class nature, yet unsupervised approaches have failed to have much impact since they require extensive intervention from human experts to judge if the patterns they find are beneficial in some manner. G-SSL revisits those ideas and uses the structure of unlabelled data to enrich the labelled data. To attain a synergy between these two sources of information, G-SSL represents the data by means of a similarity graph. Graphs are a powerful tool to represent and capture the structure of datasets because the usually high-dimensional datapoints become simple vertices and the similarity between datapoints is encoded by edges linking those vertices. In this context, G-SSL essentially amounts to transform the usual classification problem into one in which a graph has some of its nodes labelled and one aims to find the label for the remainders.

Yet since the class nature of the data is implicit in the graph, this one allies with the labelled data to deliver reliable inferences.

To illustrate how G-SSL can draw reliable predictions by learning from both the structure of data and few annotated examples, let us give a simple illustrating example in Figure 1.

Let us assume that Figure 1a represents a dataset with three classes where a few points have been hand-labelled (red, blue, magenta) and the rest are raw data that we aim to classify (grey). By themselves, the labelled points are simply too few to learn something from them, however the grey datapoints have a structure reminiscent of the class nature of the data. This extra information is key in G-SSL which builds a similarity graph to encode for it, as shown in Figure 1b. This is where the G-SSL inference problem is reached: given a graph with some labelled nodes, one aims to predict the class label for the remainder of nodes. To solve it, the graph structure and the annotated nodes operate together by successively propagating the labels to adjacent nodes in the graph until all nodes have inherited a class. As it can be seen in Figure 1c, despite having few annotated examples, G-SSL is able to enrich this information with the graph structure to deliver reliable inferences. INTRODUCTION Nevertheless, G-SSL is still not perfect. Indeed, the state-of-the-art results indicate that when the labelled data are limited, G-SSL gives accurate classifications only under rather simple data conditions: such as when the structure of classes is well defined (separable) and without complex local structures like multiple sub-classes constituting one larger class. In this regard, if the data increases in complexity, then G-SSL may require significantly more tagged examples to remain reliable. For example, the authors of [START_REF] Avrachenkov | Classification of content and users in bittorrent by semi-supervised learning methods[END_REF] employed the stateof-the-art G-SSL method [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] to classify 1, 126, 670 internet users according to the topic of videos they downloaded. Their results show that if 500 labelled points per class are used, G-SSL attains a classification error of 10%, which may be sufficient to draw conclusions, but if one uses 5 labelled points per class, then the error grows to 37%, which is now too large to be beneficial. This lack of reliability in challenging data settings has caused G-SSL to continue to be mainly employed in applications where some miss-classifications can be tolerated, such as text categorization [START_REF] Subramanya | Soft-supervised learning for text classification[END_REF], or handwritten digit recognition [START_REF] Cecotti | Active graph based semi-supervised learning using image matching: application to handwritten digit recognition[END_REF]. Furthermore, it explains why it has not been seriously considered in other types of application domains such as medicine [2].

In addition, recent theoretical results [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] indicate that G-SSL methods produce biased outputs when the ratio of class size and number of annotated examples is not the same for all classes. This certainly harms the trustability of G-SSL classifiers because the size of classes cannot be known a priori and it is against the G-SSL philosophy that, in order to make a classifier reliable, one would need to discard tagged data that may have been expensive to collect. Indeed, it is unfortunate that for large datasets consisting of thousands of classes, G-SSL demands to collect labelled data in a balanced way for each and every class, or otherwise the classifier will either be biased or will missclassify an entire class whose label was never collected.

INTRODUCTION

How can we improve G-SSL to address the limitations listed above?

To address this question, the main contribution of this dissertation consists of a new method for G-SSL referred to as the L -PageRank G-SSL. Elaborating on [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF], L -PageRank introduces a new degree of freedom into the G-SSL problem: , which, for a chosen value, changes the topology of the data and makes L -PageRank solve the G-SSL problem in the new topology. The following summary of characteristics of L -PageRank highlights the significance that our contribution brings to G-SSL:

1. L -PageRank is theoretically guaranteed to deliver more reliable classifications than the state-of-the-art PageRank method [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] if is properly chosen.

2. L -PageRank overrides the issue of unbalanced sets of labelled points

In addition:

• L -PageRank provides an algorithm for the automatic estimation of the optimal to maximize performance

• L -PageRank addresses better complicated data structures, such as graphs with unclear clusters or classes with sub-clusters structures or hubs

• L -PageRank is tailor-made to classify data via sweep-cuts [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF], implying that it does not necessarily need labelled points of all classes to operate: it can be run with labelled points of just one class and returns the nodes belonging to such class.

• L -PageRank can be efficiently computed and fastly updated to classify new data or evolving graph structures

• L -PageRank has been empirically assessed on extensive datasets commonly used for classification, showing significant improvements over the state-of-the-art PageRank method.

The thesis is organised as follows:

Chapter 1: In this chapter, we present fundamental background in graph theory, random walk theory and an introduction to the emerging field of Graph Signal Processing, fields upon which the thesis is built. The chapter also serves to introduce definitions and notations used throughout the thesis.

Chapter 2: This chapter starts with a thorough tour of the field of G-SSL. Then, we provide our fist contribution.

INTRODUCTION

Then, we point that such results imply that G-SSL methods suffer from biased outputs when facing unbalanced labelled sets. We introduce another line of works indicating that G-SSL is ill-posed when the data grows infinitely large. Proposed solutions are reviewed and special emphasis is given to the approach of [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] that proposes the use iterations of the Laplacian kernel to amend the issue.

The second part introduces G-SSL from the perspective of graph partitioning. We review partition problems and revisit results originally developed in the context of local clustering [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Andersen | Using pagerank to locally partition a graph[END_REF][START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF] showing that the PageRank algorithm, in conjunction with a technique called the sweep-cut, can be used to partition the graph into clusters of small Cheeger ratio. We contribute pointing that the results of [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Andersen | Using pagerank to locally partition a graph[END_REF][START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF], can be re-interpreted in the context of G-SSL. Moreover, we show that the idea of taking sweeps can be directly applied to G-SSL, embedding it with a larger degree of flexibility in which only the tagged points of a class are needed to run G-SSL and find the nodes belonging to such class. Lastly, we highlight that those results serve to explain better the success of the PageRank-based G-SSL method of [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF].

Chapter 3: This chapter describes the core contribution of this thesis: the L -PageRank method, a generalization of PageRank to (non-necessarily integers) -th powers of the combinatorial Laplacian matrix L ( > 0). For our developments, the chapter commences revisiting the Laplacian powers, already considered in [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], as a means to improve G-SSL.

The key difference between our approach and the one in [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] is that [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] interprets the Laplacian powers as a Sobolev regulariser, while in our approach we show that the L operator, for every fixed value, generates a new graph. These new graphs, which we refer to as the L -graphs, reweight the links of the original structure and create edges between originally far-distant nodes. Thus, our generalized L -PageRank formulation is an extension of PageRank to operate on the L -graphs (for = 1 our algorithm then reduces to the standard PageRank algorithm). To analyse L -PageRank, we show that two regimes arise: (i) < 1: leading to random walk transition matrices encoding for Lévy processes; and (ii) > 1: leading to signed graphs where edges can be positive or negative.

Regime < 1: we show that our L -PageRank extends the regular PageRank algorithm to incorporate Lévy flight random walkers instead of the regular random walkers. The Lévy flight random walkers can jump between far-distant nodes in the graph in a single step, contrary to the regular random walkers that can only transition to adjacent neighbours. We show that the improved capacity of the Lévy walkers to explore the graph can improve the classifications of graphs with trapping regions, like strong hubs, or sub-cluster structures, that tend to harm the significance of the functions learned by the regular PageRank algorithm.

Regime > 1: we show that, albeit no longer modelled by random walkers because of the graph being signed, L -PageRank remains a well behaved diffusion process. Then, we extend the definition of a cluster to L -graphs: we say that a cluster in a signed graph is a group of nodes whose members strongly agree (positive edges) and that strongly disagree with members of other clusters (negative edges). We provide a generalization of the Cheeger ratio to assess clusters in the signed L -graphs and show that, similar to the regular PageRank method that can partition graphs into clusters of small Cheeger ratio,

INTRODUCTION

L -PageRank is a tool to partition L -graphs into clusters of small generalized Cheeger ratio. This result implies that if a L -graph increases the separability of the data, then it is easier for L -PageRank to classify the data. In other words, we theoretically show that if the ground truth class under search has a smaller Cheeger ratio in a L -graph than in the initial graph ( = 1), then we can more accurately identify it with L -PageRank using the sweep-cut technique. By means of numerical investigations, we point the existence of an optimal value that maximizes performance. Therefore, we propose an algorithm that allows to estimate the optimal directly from the initial graph and the labeled points. Lastly, we demonstrate the classification improvements permitted by L -PageRank on several real world datasets commonly used in classification, as well as the relevance of the estimation procedure for the optimal tuning. Particularly, our results demonstrate that L -PageRank can: (i) significantly improve classification performance; and (ii) amend the issue of unbalanced labelled data.

Chapter 4: This chapter investigates fast and efficient implementations for our propositions in Chapter 3 and represents our third contribution. We start reviewing highly successful algorithms for efficient PageRank computation: power iteration [START_REF] Jeh | Scaling personalized web search[END_REF][START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] and Gauss-Southwell [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Berkhin | Bookmark-coloring algorithm for personalized pagerank computing[END_REF], but that rely on the Markov chain structure of PageRank and cannot be directly used in our propositions. Then, we show that our L -PageRank method can be framed in the context of graph filters, allowing us to use techniques from the field of Graph Signal Processing to efficiently implement graph filters: ARMA filters [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF] and Chebyshev polynomials [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF]. We then show that by using the ARMA filter structure, we can derive extensions of the power iteration and Gauss-Southwell algorithms to compute L -PageRank. Part of the strong success of power iteration and the Gauss-Southwell methods for standard PageRank computation is that they possess dynamic versions [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] that can update the PageRank solution in sub-linear time when the graph evolves. Therefore, we elaborate on the ARMA-based extensions of those algorithms derived in the first part of the chapter to obtain dynamic extensions of the algorithms of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] that permit to update L -PageRank in sub-linear time.

Chapter 5: This chapter uses G-SSL to address issues in Internet routing. It represents our fourth contribution. The chapter starts using G-SSL to provide the first characterization of BGP zombies under BGP protocol. Then, it employs G-SSL to address the challenge of inferring topologies of autonomous systems from networks of IP addresses.

In the first part of the chapter, we use G-SSL to provide the first characterization of the scope of BGP zombies. For this characterization, we perform measurements of the Internet in a controlled environment during three periods that span across one year an a half. Our measurements track the state of a restricted set of routers, where we occasionally observe some of them maintaining a route towards a prefix that has withdrawn the Internet more than 1.5 hours ago. To assess if this anomaly occurs in isolation or at a large scale, every time it is detected in our measurements we use G-SSL to predict which autonomous systems, other than the ones over we have measurements, also have affected routers. We show that the standard PageRank algorithm detects affected autonomous systems with 97% accuracy and non-affected ones with 99% accuracy, according to a validation set constructed from tracerout measurements of the Internet. The G-SSL predictions are then used to characterize the scope of affected autonomous systems, with our results indicating INTRODUCTION that, on average, 10% (IPv4) and 17% (IPv6) of the monitored autonomous systems are affected when the issue appears in our measurements.

In the second part of the chapter, we use G-SSL to solve the issue of inferring the topology of autonomous systems from the network of IP addresses. We perform tracerout measurements of the Internet and build a graph of IP addresses from them. Then, from publicly available ASNs registered for the IP addresses of the graph, we show that various labelled datasets with varying degrees of confidence can be constructed. We study the advantages/disadvantages of the various types of semi-supervision proposed, which offer a trade-off between amount of annotated examples and how much we can trust them. Our results show that, for the studied dataset, L -PageRank with = 2 can solve this inference task with no errors, contrary to standard PageRank which always miss-classifies data.

Chapter 6: This chapter concludes the work and discusses future directions.

Chapter 1 Preliminaries

Graph theory

Graph theory is an important area of discrete mathematics with a long history dating back to the 18th century [START_REF] Hayes | Computing science: Graph theory in practice: Part i[END_REF]. It focuses on the study of graphs: mathematical objects that represent pair-wise interactions between elements. Graphs were initially used to solve combinatorial problems [START_REF] Harris | Combinatorics and graph theory[END_REF], although the technological developments from the last century have given rise to numerous modern systems that can be effectively modelled by graphs.

Examples of such systems range from the Internet [START_REF] Albert | Internet: Diameter of the world-wide web[END_REF], social networks [START_REF] Scott | Social network analysis[END_REF], financial systems [START_REF] Gai | Contagion in financial networks[END_REF], healthcare [START_REF] Wang | Application of network analysis on healthcare[END_REF], protein networks [START_REF] Rual | Towards a proteome-scale map of the human protein-protein interaction network[END_REF], smart grids [START_REF] Zhang | Convergence analysis of the incremental cost consensus algorithm under different communication network topologies in a smart grid[END_REF], communication systems [START_REF] Costantine | The analysis of a reconfigurable antenna with a rotating feed using graph models[END_REF], or sensor networks [START_REF] Krishnamachari | The impact of data aggregation in wireless sensor networks[END_REF], to name a few. Indeed, the list of applications, and the systems themselves, evolve every day, and, accordingly, the complexity of the questions they give rise to. To address such questions, it is crucial to better understand the data generated by these systems and graph theory provides the fundamental building block towards developing better data processing tools capable of taking into account the complex interconnected nature of these systems.

Graphs are made of two fundamental ingredients: a set of nodes (also referred to as vertices) and a set of edges linking these nodes. From here, variants can be devised: the edges may code for strength through a weight coefficient or may have a direction. In this thesis, we will only consider networks that are undirected, with positively weighted edges, and without self-loops (a link connecting a vertex with itself), unless otherwise stated. While this restriction leaves out various networks of major interest, the tradeoff is that it allows a much more amenable mathematical treatment while still covering the majority of modern applications.

A graph is denoted by the triplet G(V, E,w).B yV, we refer to the set of vertices, which we assume of carnality

V = N .B yE ⊂ V × V, we denote the set of edges, in which a connected pair u, v ∈ V, denoted u ∼ v, implies both (u, v) ∈ E and (v, u) ∈ E. A graph is labeled as sparse if E = O(N ).
Lastly, w ∶ E → R + is a function that assigns a real positive weight to edges.

The adjacency matrix of the graph is an important matrix condensing all the information from the triplet G(V, E,w). Without loss of generality, assume that each node in the graph is assigned an arbitrary and unique index from 1 to N . Then, is is defined as follows:

1.2. GRAPH DATA Definition 1. The graph adjacency matrix is the matrix W ∈ R N ×N with elements given by

W uv = w(u, v) u ∼ v, 0 otherwise. (1.1)
Note that since we assumed undirected edges the adjacency matrix is symmetric. Moreover, the no-self loops condition implies that the diagonal of W is full of zeros.

The degree matrix is another important matrix which encodes for the degrees of nodes. The latter are a measure of how strong are the connections towards a node. Both are defined as follows:

Definition 2. Let u ∈ V be an arbitrary node. The degree of u, denoted d u , is given as

d u = v W uv (1.2)
Definition 3. The graph degree matrix is the diagonal matrix D ∈ R N ×N with elements given by D uu = d u Graphs do not live in euclidean spaces, therefore we cannot compute distances between nodes using euclidean approaches. However, graphs possess an intrinsic metric usually referred to as the shortest path distance or the geodesic distance between nodes. Let the sequence In this work, we will extensively work with groups of nodes. We will refer to such groups via the set notation S ⊆ V.F u r t h e r ,l e t S denote the indicator function of S, so that ( S ) u = 1i fu ∈ S and ( S ) u = 0 otherwise. As illustrated in our next definition, the indicator function notation will allow us to write most operations involving sets in matrix form.

(v 1 ,v 2 ,...,v k ) ∈ V × V ×⋅⋅⋅×V,w i t hv i ∼ v i+1 , v 1 = u and v k = v,
The volume of a set is a quantity that assesses how many connections reach the nodes in the set. It is defined as follows:

Definition 5. Let S ⊆ V. The volume of S is given by

vol(S) = u∈S d u = T S D S (1.3)
When we refer to the volume of the entire graph it will be denoted by vol(G).

Graph data 1.2.1 Graph models

As discussed above, numerous graphs can naturally arise in several real world applications. However, one has hardly any control over these graphs. It is thus important to rely on graph generative models that, on the one hand, allow to vary properties under investigation by means of tunable parameters, and, on the other hand, have matrix representations with amenable theoretical properties. This subsection introduces graph models that will be employed throughout this work.

Cyclic graph

The ring graph is a 1-dimensional regular lattice with periodic boundary conditions. If we label the graph vertices from 1 to N , then the defining property of ring graphs is that the shortest path distance between nodes satisfies

∆ uv = u -v if u -v = 0, 1,...,N 2, N -u -v if u -v = N 2 + 1,...,N, (1.4)
where ⋅ is the floor function. As a result, the adjacency matrix of ring graphs has the following circulant form: W uv = 1i fv = u + 1 or v = u -1, and W uv = 0 otherwise. It is well known that circulant matrices have amenable mathematical properties. Two of the most important are [START_REF] Gray | Toeplitz and circulant matrices: A review[END_REF]: (i) they are diagonalized by the discrete Fourier transform; and (ii) they can be interpreted as a convolution operator on cyclic groups of N elements.

The planted partition model

The planted partition model is an important generative model for random graphs. It is tailored to generate graphs having a community structure. A community (also referred to as a cluster in this work) denotes a group of nodes satisfying: (i) nodes in the group are strongly connected between them; and (ii) nodes in the group are poorly connected towards the rest of nodes in the graph. The planted partition model allows to control the degree of attachment between nodes within and between communities. Thus, it widely used for benchmarking tasks that involve communities.

To construct the planted partition, let the set of nodes be split into two disjoint subsets S 1 and S 2 as V = S 1 ∪ S 2 ,w i t hS 1 ∩ S 2 = . Further, let two parameters p in and p out denote the probabilities of within-cluster connections and between-cluster connections.

Then, for every possible pair, u ∈ S i and v ∈ S j , u ≠ v, an unweighted edge is drawn between u and v with probability p in if i = j, or with probability p out if i ≠ j.

It is clear that if S 1 = S 2 and p in > p out are both satisfied, then S 1 and S 2 should form separate communities. Yet, due to the probabilistic approach, nodes from S 1 can still end up more connected to nodes from S 2 than to the rest of nodes in S 1 (depending on how much bigger is p in than p out ). Thus, the clustering task in the planted partition is: for a given realization of the model, one must recover the true partitioning, i.e. which nodes belonged initially to S 1 and which ones to S 2 .

The planted partition has been subject of extensive theoretical studies [START_REF] Condon | Algorithms for graph partitioning on the planted partition model[END_REF][START_REF] Ghoshdastidar | Consistency of spectral partitioning of uniform hypergraphs under planted partition model[END_REF][START_REF] Tsourakakis | Streaming graph partitioning in the planted partition model[END_REF]. An important result due to Mossel et al. [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF] demonstrates the existence of a detectability transition above which any unsupervised algorithm is unable to detect communities positively correlated with the true partition. To state their result, let S 1 = S 2 = n and let

C out = (p out )(n) and C in = (p in )(n -1)
be the mean number of within cluster and without cluster connections of a node, respectively. The mean degree of a node is thus given by

C avg = C in + C out .
Theorem 1 ([40]). Consider a planted partition model. Then, as n → ∞, it is possible to recover a cluster that is positively correlated with the true partition, in an unsupervised manner, if

(C in -C out ) 2 > 2(C in + C out )
, and impossible otherwise.

CHAPTER 1. PRELIMINARIES 1.3. RANDOM WALKS ON GRAPHS
Before proceeding, it is important to define a metric to assess the similarity between datapoints. Various possibilities exist: correlations, inverse of the euclidean distance, kernel functions, etc. In this work, we will employ the so-called radial basis function (RBF).

It is defined as follows: let u, v ∈ R m be two data points in an m-dimensional vector space and let be a width parameter. The similarity between u and v is thus given as

sim(u, v) = exp - u -v 2 2 2
(1.5)

✏-neighborhood graph construction

In the ✏-neighborhood graph construction approach, the adjacency matrix of the graph is constructed employing the following rule

W uv = sim(u, v) if sim(u, v) ≤ ✏, 0 otherwise, (1.6)
This is the most natural approach to capture the structure of manifolds as they seem euclidean in local regions. However, the tuning of ✏ is critical and there are not clear insights on how to choose this parameter in practice. Indeed, a bad choice of ✏ can easily lead to disconnected vertices.

K-nearest neighbor graph construction

In the K-nearest neighbor graph construction approach, the adjacency matrix is computed as

W uv = sim(u, v) if v is within the K most similar points of u, 0 otherwise, (1.7)
Note that this approach solves the problem of disconnected nodes. However, in practice, the tuning of K is crucial and its selection remains an open question. Normally, choosing it around K = 10 tends to give good results. Finally, observe that u may be in the K closest neighbors of v, but the converse may not be true. Thus, each time we set W uv = sim(u, v), we must also set W vu = sim(u, v).

Random walks on graphs

Now that we have seen that numerous problems can be modelled by graphs, we focus on tools to analyse graphs. A simple, yet powerful approach to analyse graphs is to navigate the graph and to compute statistics about it. This is the underlying mechanism of a random walk on a graph. The random walk process operates as follows: a walker is located at a node u at a specific time t, then it selects one node from its neighbors with probability proportional to the strength of their connection, and moves to this node at time step t+1. While simple, the statistics of this process, in the limit of infinite number of realizations, yield a very useful model for diffusion on graphs, upon which several precise statements can be made. Indeed, this modeling capacity of random walks has been used to characterise: users surfing the web by clicking hyperlinks between sites [START_REF] Langville | Google's PageRank and beyond: The science of search engine rankings[END_REF]; a disease CHAPTER 1. PRELIMINARIES

RANDOM WALKS ON GRAPHS

propagating in a population [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF]; or fake news being spread and influencing political preferences [START_REF] Ribeiro | everything i disagree with is# fakenews[END_REF]. Further, walkers have also leveraged to solve graph problems such as graph clustering [START_REF] Pons | Computing communities in large networks using random walks[END_REF], graph coloring [START_REF] Wei | Accelerating random walks[END_REF], graph critical point [START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF], or minimum spanning tree [START_REF] Neumann | Ant colony optimization and the minimum spanning tree problem[END_REF].

In math terms, a discrete time random walk on a graph is a discrete time Markov chain with state space given by the vertices of the graph. The transition probabilities of the chain are encoded by the so-called transition probability matrix of the walk defined as follows:

Definition 6. The transition probability matrix of a random walk is the matrix P ∈ R N ×N with elements given by

P uv = W uv d u , (1.8)
where P uv denotes the probability of a walker at node u moving to a node v in the following step.

Observe that P can be computed in matrix form as P = D -1 W . Also, since the walker always moves to a neighbor, P is right stochastic, i.e. P uv ∈ [0, 1] with ∑ v P uv = 1, or, equivalently in matrix form, the all ones vector, denoted , is a right eigenvector of P with eigenvalue one: P = .

Note that, since an individual walker is not sufficient to derive statistics, one must work with the ensemble probabilities from an infinite number of walk realizations instead. Let t denote the probability vector whose u-th entry, ( t ) u , encodes the probability of finding the walker at node u at time t. Then, the probability of finding the walker at node v at time t + 1 is given by

( t+1 ) v = u ( t ) u P uv .
(1.9)

In matrix form, this can be computed for all nodes as T t+1 = T t P . Clearly, this recursive relation can be iterated to compute the distribution of the random walks at any time t by only knowing the distribution of its starting point. Thus, we have that the t-step distribution of the random walk, with starting distribution 0 , is given as

T t = T 0 P t . (1.10)
It is important to highlight that Eq. (1.10) admits an interpretation as a diffusion process on the graph. This is, consider the entries of 0 to represent some amount of 'heat' or 'liquid' placed on the nodes of the graph. Then, the vector t represents the state of having diffused this quantity, through the graph vertices, for t-steps via the random walkers. Let us clarify on what we intend by means of the simple example in Figure 1.2. In it, a unit mass of 'heat' is placed at node 1 at t = 0 (green node / top plot). Then, random walk steps are applied and, at each time step, the heat diffuses to its adjacent vertices (first step: blue/middle; second step: red/bottom). Observe that, due to ∑ u ( t ) u = 1 for all t, the process is mass preserving, implying that there is no creation or dissipation of 'heat'. Thus, effectively just propagating the mass at each time step. Due to this duality, when we refer to the probability of finding a walker at a node or to the mass diffused by walkers to a node, both expressions will be indistinct.

In the limit of infinite time steps, irrespective of the initial condition 0 , if the graph 14 CHAPTER 1. PRELIMINARIES 1.4. GRAPH SIGNAL PROCESSING data, standard data processing tools must be able to incorporate the irregular nature of the domain in which the data lives. For this reason, the field of graph signal processing (GSP) has emerged with the objective of extending traditional data processing tools (and to develop new approaches) to treat and analyse data supported on irregular domains. This section gives an overview of the field of GSP.

Graph signals

If the data supported on the graph vertices is represented by numerical values, then the concept of signal from classical signal processing can be generalised to arbitrary graphs.

Definition 7. A graph signal f is defined as the mapping f ∶ V → R.
Graph signals are represented by column vectors, where the u-th element of f , denoted f u , represents the signal value at node u.

Therefore, the focal point of GSP is to process graph signals in a similar manner as we process time series or images in classical signal processing. Towards this aim, numerous efforts have been done to extend operations that are the cornerstone of classical signal processing to the graph setting. These include: filtering [START_REF] Chen | Signal inpainting on graphs via total variation minimization[END_REF][START_REF] Arvanitis | Feature preserving mesh denoising based on graph spectral processing[END_REF][START_REF] Onuki | Graph signal denoising via trilateral filter on graph spectral domain[END_REF], prediction [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF][START_REF] Marques | Stationary graph processes and spectral estimation[END_REF], inpainting [START_REF] Chen | Distributed algorithm for graph signal inpainting[END_REF][START_REF] Chen | Signal inpainting on graphs via total variation minimization[END_REF], subsampling [START_REF] Narang | Signal processing techniques for interpolation in graph structured data[END_REF][START_REF] Tsitsvero | Signals on graphs: Uncertainty principle and sampling[END_REF], multi-resolution anaysis [START_REF] Perraudin | Stationary signal processing on graphs[END_REF][START_REF] Tremblay | Graph wavelets for multiscale community mining[END_REF], compression [START_REF] Rizkallah | Graph-based transforms for predictive light field compression based on super-pixels[END_REF][START_REF] Zhang | Point cloud attribute compression with graph transform[END_REF], or classification [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF][START_REF] Zhang | An end-to-end deep learning architecture for graph classification[END_REF][START_REF] Avrachenkov | Classification of content and users in bittorrent by semi-supervised learning methods[END_REF].

Spectral theory

In classical signal processing, one of the fundamental operations to analyse a signal is to decompose it into its fundamental frequencies. As natural signals tend to be generated by multiple phenomena of diverse oscillating nature, the frequency analysis of a signal allows to isolate and enhance, extract, or suppress any source of interest. Therefore, it is of interest to extend such operation to graph signals. For it, the field of GSP has shown that the framework of spectral graph theory, which studies how the eigenvalues and eigenvectors of the matrix representations of graphs relate to graph properties, can be leveraged to develop a frequency analysis of graph signals.

The most fundamental decomposition of this form in classical signal processing is given by the Fourier transform. The Fourier transform of the continuous time signal f (t) is given by f

(⇠) = ∞ -∞ f (t)e -2⇡it⇠ dt. (1.13)
The inverse Fourier transform of f (⇠) is given by

f (t) = ∞ -∞ f (⇠)e 2⇡it⇠ d⇠. (1.14)
Thus, the inverse Fourier transform corresponds to an expansion of a signal in terms of complex exponentials, where the argument (2⇡⇠) determines the frequency of oscillation of such functions. Observe how this basis also corresponds to the eigenfunctions of the 1-D Laplace operator -@ 2 @t 2 e 2⇡it⇠ = (2⇡⇠) Building upon this observation, a graph Fourier transform can thus also be defined as expanding a graph signal in terms of the eigenfunctions of a Laplace operator defined on graphs. Thus, calling for a definition of the Laplace operator on graphs. Now, since the Laplace operator is a differential operator, various possible definitions of graph signal differentiation and graph Laplacians arise.

Laplacian definitions on graphs

Option 1: The combinatorial graph Laplacian. In this Laplacian definition, one departs from defining a differentiation operator on a graph signal f as

(df )(u, v) = √ W uv (f u - f u ).
Observe how the resulting derivative lives on the graph edges. Thus, to revert to functions supported on nodes, the adjoint of d is needed. The adjoint operator of d, denoted d * , acts on a function H defined on the graph edges as

(d * H) u = ∑ v∼u √ W uv (H(v, u) - H(u, v)).
In [START_REF] Elmoataz | Nonlocal Discrete Regularization on Weighted Graphs: A Framework for Image and Manifold Processing[END_REF], these definitions of differentiation were shown to be consistent with the continuous definitions of the derivative of a function. Thus, they can be employed to define the Laplace operator on graphs. As the Laplacian is the adjoint of the difference operator, we obtain the following important definition: Definition 8. The combinatorial Laplacian operator of a graph, denoted L, acting on the graph signal f and evaluated in a node u is given by

(Lf ) u = d * (df (u, v)) = v∼u W uv (f u -f v ). (1.16)
Observe how this Laplacian definition effectively permits to incorporate information about the domain of f into the analysis of f .T h i si s ,i fu and v share a strong link, then any small difference between f u and f v will drastically impact (Lf ) u , while if their connection is weak, then differences are less important.

The combinatorial Laplacian operator can be expressed in matrix form as follows:

Definition 9. The combinatorial Laplacian matrix is the matrix L ∈ R N ×N given by

L = D -W (1.17)
One important asset of this matrix representation is that the quadratic form of L, also called the Dirichlet energy form, gives a measure of the global regularity, or smoothness, of a graph signal with respect to its supporting domain. It is given by

f T Lf = (u,v)∈E W uv (f u -f v ) 2 . (1.18)
Thus, if f is the constant function, i.e. it is completely smooth, the Dirichlet form return a value equal to zero, and, as f becomes more oscillating, the value of the form increases accordingly.

Option 2: The random walk Laplacian. A second approach to define differentiation of graph signals is by comparing the signal value of a node with respect the mean value in its vicinity.

CHAPTER 1. PRELIMINARIES

(L rw f ) u = f u - v∼u P uv f v . (1.19)
The random walk Laplacian operator can be represented in matrix form as follows:

Definition 11. The random walk Laplacian matrix is the matrix L rw ∈ R N ×N given by

L rw = I -P = D -1 L (1.20)
Thus, the random walk Laplacian matrix is indeed a degree normalised version of the combinatorial Laplacian matrix. However, this normalization makes this operator nonsymmetric, what makes it hard to derive an equivalent of Eq. (1.18) for L rw .

Option 3: The symmetric normalized Laplacian. The last approach to define differentiation of graph signals is by comparing the signal value of a node with respect to a degree-normalized mean value of its vicinity.

Definition 12. The normalized Laplacian of a graph, denoted L n , acting on the graph signal f and evaluated in a node u is given by

(L n f ) u = f u - v∼u √ d u √ d v P uv f v . (1.21)
Observe that, in matrix form, this operator is a similar transformation of L rw and is a symmetric normalization of L.

Definition 13. The normalized Laplacian matrix is the matrix L n ∈ R N ×N given by

L n = I -D 1 2 PD -1 2 = D -1 2 LD -1 2 (1.22)
Thus, the relationship in Eq. (1.22) implies that a quadratic form with L n leads to the following graph signal smoothness metric

f T L n f = (u,v)∈E W uv f u √ d u - f v √ d v 2 . (1.23)
It is important to observe that, under this metric, the constant function f is no longer considered the smoothest function on the graph as compared to L. Thus, the choice of the Laplacian kernel plays a key role on the way regularity of graph signals is assessed.

The graph Fourier transform

Now that the Laplacian operator on graphs has been introduced, the graph Fourier transform can be defined. Let L denote any of the Laplace operators defined above. Then, L admits an spectral decomposition of the form

L = QΛQ -1 , (1.24)
where the columns of Q ∈ R N ×N conform the right eigenvectors, the rows of Q -1 ∈ R N ×N are the left eigenvectors, and Λ ∈ R N ×N refers to a diagonal matrix of eigenvalues of L.

The graph Fourier transform (GFT) is defined as the projection of the graph signal onto the eigenfunctions of the Laplacian as follows:

f = Q -1 f. (1.25)
Further, the transformation is invertible:

Definition 15. The inverse graph Fourier transform of f is given by

f = Q f. (1.26)
It is important to stress that in the cases of L = L and L = L n , the symmetry of the operator implies a complete set of orthonormal vectors, thus

Q -1 = Q T .
We now give a discussion on how relevant it is to decompose a graph signal into the bases given by these Laplacian operators. For it, without loss of generality, assume that the eigenvalues of L are labeled and sorted according to their value, such that 1 ≤ 2 ≤ ⋅⋅⋅≤ N , and q k denotes the eigenvector associated to k .

The case of L. Let the eigenvalue problem for L be stated in terms of the Rayleigh quotient. This is, the eigenvalue k and the eigenvector q k of L are defined as the pair satisfying

k = inf q k q T k Lq k q T k q k s.t. q k ⊥ span{q 1 ,...,q k-1 } (1.27)
Eq. (1.27) shows that the magnitude of the eigenvalues of L are proportional to the smoothness of their corresponding eigenvectors when measured via the Dirichlet energy form of L (see Eq. (1.18)). Thus, q k can be interpreted as the smoothest possible function that lives in the orthogonal of span{q 1 ,...,q k-1 }. This implies that the eigenvectors of L are in effect a sensible basis to decompose graph signals since eigenfunctions associated to small eigenvalues will capture the non-oscillating phenomena and the ones associated to larger eigenvalues will capture variations in the signal.

As a last note, we remark that Eq. (1.27) also shows that the eigenvalues L are always real non-negative satisfying 1 = 0, and if the graph has c disconnected components, then the multiplicity of the zero eigenvalue is equal to c.

The cases of L n and L rw . These operators are similar, thus they share the same set of eigenvalues. Further, their eigenvectors are equal up to a rotation, i.e. if q k denotes an eigenvector of L n ,t h e nq ′ k = D -1 2 q k and q ′′ k = D 1 2 q k are the right a left eigenvectors of L rw , respectively. As with L, the eigenvalue problem for these operators can also be expressed via the Rayleigh quotient. Doing it highlights that the eigenfunctions of these operators also capture oscillatory phenomena, though the basis given by L n motivates smoothness through the quadratic form in Eq. (1.23), while the one of L rw does it via the Dirichlet form of Eq. (1.18). In precise terms, let q ′ k = D -1 2 q k (we show for the right eigenvectors of 1.4. GRAPH SIGNAL PROCESSING L rw ), then we have

k = inf q k q T k L n q k q T k q k s.t. q k ⊥ span{q 1 ,...,q k-1 }, = inf q k q T k D -1 2 LD -1 2 q k q T k q k s.t. q k ⊥ span{q 1 ,...,q k-1 } = inf q ′ k q ′ k T Lq ′ k q ′ k T Dq ′ k s.t. q ′ k ⊥ span{Dq ′ 1 ,...,Dq ′ k-1 }. (1.28)
Lastly, these equations imply that both L n and L rw , have non-negative real eigenvalues, with 1 = 0, and if the graph has c disconnected components, then the multiplicity of the zero eigenvalue is equal to c.

Graph filters

In classical signal processing, filtering is the process of suppressing the contribution of specific frequencies in the signal expansion. The filtering process can be done either by multiplying the transfer function of the filter with the frequency representation of the signal or by performing a convolution between the filter and the signal in the time domain. In the case of graphs, filters can also be defined, though only through the spectral domain as the convolution operation on graphs is not well defined (it is not clear what it means to shift a graph signal). In [START_REF] Shuman | The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[END_REF], the following definition of a graph filter is given:

Definition 16.
A graph filter H is an operator determined by the mapping i → h( i ).

In the spectral domain it is represented by the matrix Ĥ and acts on the GFT of a graph signal as Applying the definitions of the GFT and the inverse GFT shows that the filter can be expressed in the vertex domain as

H(f ) = h( 1 ) f1 h( 2 ) f2 ... h( N ) fN = h( 1 ) 00
H(f ) = Q H(f ) = Qh( )Q -1 f = h(L)f. (1.30)
Since any function of a matrix is a function on its eigenvalues, this last expression shows that any graph filter is a function on the graph Laplacian. As it will be detailed in Chapter 4, this turns out key to derive efficient implementations of graph filters.

The heat equation

The combinatorial graph Laplacian offers an alternative approach to random walks for diffusion on graphs. This is achieved by means of the heat equation with L as operator. It reads as follows: @f @t = -Lf. By means of its Taylor expansion, it can be shown that Eq. (1.32) corresponds to a mass preserving process. This is,

T f = T f 0 -t T Lf 0 + t 2 2! T L 2 f 0 - t 3 3! T L 3 f 0 + ... = T f 0 . (1.33)
Thus, Eq. (1.32) effectively determines the state of the system after having diffused the initial mass f 0 during a time t. Indeed, we clarify that the restriction to L is because it is the only Laplacian where mass preservation can be shown for all t.

Similar to the random walk case, irrespective of the initial condition, this diffusion process converges to a predictable stationary state at t → ∞. However, while the walk converges to the distribution of nodes' degrees, this process converges to a constant function. This can be seen by reverting to the spectral domain, where we have that f = Qe -tΛ Q T f 0 ,w h e r e e -tΛ is a diagonal matrix with entries [e -tΛ ] uu = e -t u . Clearly, as t → ∞, all the eigenmodes vanish but the one associated to 1 = 0, leading to f = q 1 q T 1 f 0 , which is constant on all the nodes in the graph.

Lastly, it can be shown that the rate of convergence of this diffusion process is controlled by 2 . This is because e -t 2 is the last eigenmode to vanish and it vanishes faster the larger it is 2 , thus showing again the importance of the first non-trivial eigenvalue in how fast a diffusion process is.

Chapter 2

Graph-Based Semi-Supervised Learning

Introduction

In the last few years, numerous modern systems have become capable to generate massive amounts of data at a very small cost. Thus, substantially increasing the amount of data that can be readily accessed. However, despite all these data being a rich source of information, classical machine learning approaches can still learn little about it. On the one hand, supervised learning approaches require extensive amounts of labeled data to learn. This is problematic as the process of labelling data requires from both human intervention and specialised devices, thus it is susceptible to errors and prohibitively expensive to acquire at a large scale. On the other hand, unsupervised learning procedures are capable to leverage the structure of the data to learn. Nevertheless, when the data increases in complexity, it becomes too penalizing for them to overlook the valuable source of information given by the limited yet available labeled examples. As a synergy of these two approaches, semi-supervised learning procedures have recently emerged.

The goal of semi-supervised learning is to learn from both the structure of the data and the labelled examples. In early works, the structure of the data was incorporated to the learning problem via probabilistic approaches [START_REF] Zhu | Introduction to semi-supervised learning[END_REF]. However, more recent works have shown that it is more effective to encode for the data structure using graphs [START_REF] Subramanya | Graph-based semi-supervised learning[END_REF]. As a result, the paradigm of graph-based semi-supervised learning (G-SSL) has attracted considerable attention. Indeed, while G-SSL was motivated for classification of structured euclidean data, the large amount of datasets found today as graphs (e.g. the Internet) motivate G-SSL on their own. G-SSL has been applied in numerous contexts, setting the state of the art in tasks such as classification of BitTorrent contents and users [START_REF] Avrachenkov | Classification of content and users in bittorrent by semi-supervised learning methods[END_REF], text categorization [START_REF] Subramanya | Soft-supervised learning for text classification[END_REF], medical diagnosis [START_REF] Zhao | Compact graph based semi-supervised learning for medical diagnosis in alzheimers disease[END_REF], visual tracking [START_REF] Hu | Semi-supervised tensor-based graph embedding learning and its application to visual discriminant tracking[END_REF], handwritten recognition [START_REF] Cecotti | Active graph based semi-supervised learning using image matching: application to handwritten digit recognition[END_REF], or classification of hyperspectral images [START_REF] Morsier | Kernel low-rank and sparse graph for unsupervised and semi-supervised classification of hyperspectral images[END_REF], to name a few. G-SSL operates under the assumption that similar points should be of the same class, so that the network structure and the labelled points can be exploited as follows: the category of the labelled nodes is propagated to their neighbors, then continues propagating to nodes further away until all nodes have inherited a class. Notice how, in this way, G-SSL is able to take full advantage of even very limited amounts of labelled points. To better highlight the potential of this learning philosophy, let us consider the example from Fig. 2.1. In Fig. 2.1a, we display a realization of the two moons data set, a classic toy example of structured data. In it, the learning task consists in detecting if a point belongs to the upper or the lower moon. To solve the task, we only dispose of a couple of labelled points per moon and the unlabelled data. Fig. 2.1b shows the result obtained by using a popular supervised classifier [START_REF] Suykens | Least squares support vector machine classifiers[END_REF]. Clearly, it can be seen that the amount of labelled data is insufficient for it to learn. Now, as a way to capture the structure of the data, we build a graph from it. In Fig. 2.1c, we display the result of applying an unsupervised graph clustering method [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. Notably, the incorporation of the graph structure can significantly improve the learning accuracy, albeit using only the graph structure is not sufficient to deliver a perfect result. Lastly, Fig. 2.1d shows the result of applying a G-SSL method [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF]. As it can be seen, G-SSL is able to leverage the key information contained in the labelled and unlabelled points to deliver a reliable result.

In this Chapter, we give a thorough tour of the field of G-SSL, which will be the main topic of this dissertation. Traditionally, G-SSL is posed as an optimization problem under regularization constraint. As a result, most of the literature on GSSL, from books [START_REF] Subramanya | Graph-based semi-supervised learning[END_REF][START_REF] Bengio | Label Propagation and Quadratic Criterion[END_REF] to recent PhD works [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF][START_REF] Mai | Methods of random matrix for large dimensional statistical learning[END_REF], have focussed on leveraging the optimization problem to propose novel and more performing objective functions. In this chapter, we will also approach G-SSL from the perspective of graph partitioning. Consequently, we devote two sections to introduce G-SSL: one covering the classical optimization perspective and the other deriving G-SSL from the point of view of graph partitioning. This alternative perspective proves instrumental to: (i) embed G-SSL with a larger degree of flexibility in which only the tagged points of a class are needed to run G-SSL and find the nodes belonging to such class; and (ii) understand better the success of the PageRank-based G-SSL algorithm proposed in [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF]. More precisely, Section 2.2 covers G-SSL from the perspective of Tikhonov regularization. In it, we introduce popular G-SSL approaches [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF][START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF][START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF] and the generalized optimization framework from [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] that encompasses most of these methods in a unified optimization framework. Special emphasis is given to the interpretation given by [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] in terms of competing random walks driving the classification process. Lastly, we cover recent methods [START_REF] Mai | Revisiting and improving semi-supervised learning: A large dimensional approach[END_REF][START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] addressing an issue highlighted in [START_REF] Nadler | Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data[END_REF] indicating that traditional G-SSL approaches fail to operate in the limit of infinite unlabelled data. In Section 2.3, we introduce G-SSL from the point of view of graph partitioning. We show that G-SSL can be cast as a binary clustering problem. Therefore, we introduce cut problems on graphs tailored for clustering. Since these cut problems are unfeasible to solve exactly, we cover results showing that efficient approximations can be obtained, in an unsupervised manner, via spectral clustering [START_REF] Chung | Spectral graph theory[END_REF], or, in a semi-supervised manner, via random walks [START_REF] Lovász | The mixing rate of markov chains, an isoperimetric inequality, and computing the volume[END_REF][START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF] and PageRank [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Andersen | Using pagerank to locally partition a graph[END_REF][START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF]. Section 2.4 discusses issues in G-SSL methods.

From Tikhonov regularization to G-SSL

Consider a weighted undirected graph G(V, E,w) and assume that each element of V belongs to one of K possible classes. Further, assume that the ground truth class is known for a fraction of vertices V L ⊂ V. Thus, the G-SSL task is to classify the points in the complement of V L .

To solve the problem, G-SSL methods employ the so-called smoothness assumption: strongly connected nodes in the graph should be of the same class. This assumption motivates from the observation that, in the euclidean case, the decision boundary of classifiers usually lies in low density regions, indicating that it is much more likely that two data points in a dense region belong to the same class. As a result, when data points are mapped into a graph, those large density regions translate into strongly connected groups of nodes, thus motivating the smoothness assumption.

Algorithmically, G-SSL methods incorporate the smoothness assumption by casting the problem as one in which one searches for smooth functions on the graph that are consistent with the labelled data. In the literature, there are are deluge of G-SSL propositions following this rationale [START_REF] Xiaojin | Learning from labeled and unlabeled data with label propagation[END_REF][START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF][START_REF] Szummer | Partially labeled classification with markov random walks[END_REF][START_REF] Belkin | Using manifold stucture for partially labeled classification[END_REF][START_REF] Baluja | Video suggestion and discovery for youtube: taking random walks through the view graph[END_REF][START_REF] Talukdar | New regularized algorithms for transductive learning[END_REF][START_REF] Orbach | Graph-based transduction with confidence[END_REF][START_REF] Subramanya | Semi-supervised learning with measure propagation[END_REF]. However, four formulations stand out as the most performing, influential and widely used: [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF][START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF][START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF]. We detail these four propositions next.

Before proceeding, we define two important matrices. First, let Y ∈ R N ×K denote a matrix of labelled points. Note that V L can be written as

V L = V 1 ∪ V 2 ∪⋅⋅⋅∪V K ,w h e r eV k
denotes the set of nodes tagged in class k. Thus, given that V k ≠ 0 for all k,t h ee n t r i e s of Y are given as

Y uk = 1 u ∈ V k , 0 otherwise. ( 2

The unnormalized Laplacian G-SSL

One of the simplest G-SSL propositions was introduced in [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF]. Despite its simplicity, this method is the building block for the more involved and performing propositions, thus it constitutes a reference method in the G-SSL literature. The method proposes to find the classification functions by solving an optimization problem with the following objective function: arg min

F * k F T * k LF * k + µ (F * k -Y * k ) T (F * k -Y * k ) . (2.
2)

The interpretation of problem (2.2) is straightforward: the left term searches for smooth classification functions, while the right term constraints the search space by penalizing solutions that deviate from the initial labelling, and the regularization parameter µ > 0 offers a trade-off between these two terms.

Since the objective function in (2.2) is a mixture of a positive semi-definite quadratic form and an `2 norm, then the problem is convex. As a result, the classification functions can be found in closed form as

F * k = µ (L + µI) -1 Y * k . (2.3)
Finally, once the classification functions have been computed, node u is assigned to the class k satisfying:

F uk ≥ F uk ′ ∀ k ′ ≠ k (2.4)
Thus, this method basically operates assigning large function values to nodes strongly connected to the labelled points and then let the function smoothly decay toward zero as we move farther away from the labels. Then, each node has K function values assigned to it and inherits the class that assigns to it the larger value. It is clear that special care must be given to the selection of µ: µ → 0 implies only considering the smoothness term in (2.2) whose minimizer is the constant function and from whom Eq. (2.4) would not be able to do any decision.

The normalized Laplacian-based G-SSL

In [START_REF] Zhou | Learning with local and global consistency[END_REF], the authors propose the normalized Laplacian-based G-SSL as a variation of the unnormalized Laplacian G-SSL. We observe that problem (2.2) measures smoothness via the Dirichlet form of L, thus the most natural change is to use the Dirichlet form of L n instead. The work of [START_REF] Zhou | Learning with local and global consistency[END_REF] adopts this change, defining the classification functions as the solution to: arg min

F * k F T * k L n F * k + µ (F * k -Y * k ) T (F * k -Y * k ) (2.5)
Following similar arguments as for the unnormalized Laplacian approach, problem (2.5) is convex with closed form solution given by

F * k = µ (L n + µI) -1 Y * k . (2.6)

FROM TIKHONOV REGULARIZATION TO G-SSL

Lastly, node u is assigned to the class k according to the same rule of Eq. (2.4).

The standard Laplacian-based G-SSL

In [START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF], the so-called standard Laplacian G-SSL was proposed. This work introduces the idea that labelled points should have different importance depending on which node they are. More precisely, it is assumed in [START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF] that a labelled point in a node of large degree (e.g. a hub) is more informative than a labelled point in a node of small degree (e.g. an outlier), thus the objective function should be more penalizing if the classification function does not fit well labelled points in large degree nodes. As a result, [START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF] proposes the following optimization problem:

arg min

F * k F T * k LF * k + µ (F * k -Y * k ) T D (F * k -Y * k ) (2.7)
As we can see, this change is implemented by simply tweaking the norm in the fidelity term from ⋅, ⋅ to ⋅, ⋅ D . Moreover, the name of standard Laplacian comes from the fact that this formulation reverts to the the standard smoothness metric using L.

Since ⋅, ⋅ D defines a proper inner product, problem (2.7) remains convex. Therefore, its solution can be expressed in closed form as

F * k = µ (L rw + µI) -1 Y * k . (2.8)
Notably, by comparing the solutions of the unnormalized Laplacian approach (Eq. (2.3)), the normalized Laplacian (Eq. (2.6)), and the standard Laplacian (Eq. (2.8)), it can be seen that the three Laplacian propositions covered in Chapter 1 appear as the fuelling force for each of these methods. Indeed, the their only difference is the election of the Laplacian kernel under consideration.

Lastly, we recall that a node u is assigned to the class k that satisfies Eq. (2.4).

The PageRank-based G-SSL

Building upon similar ideas, [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] proposes the PageRank-based G-SSL. This work proposes to tweak both the fitting term and the smoothness term. Concerning the fitting term, the converse to the standard Laplacian is assumed: namely, labelled points in nodes of small degree are more important than labelled points in nodes of large degrees. On the other hand, the smoothness term is normalized to impose a stronger regularity constraint between nodes having small degree. Precisely, the PageRank-based G-SSL is defined as the solution to [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF]:

arg min F * k F T * k D -1 LD -1 F * k + µ (F * k -Y * k ) T D -1 (F * k -Y * k ) . (2.9)
Observe that problem (2.9) defines a new smoothness metric:

F T * k D -1 LD -1 F * k = (u,v)∈E W uv F uk d u - F vk d v 2 . (2.10) CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING 2.2. FROM TIKHONOV REGULARIZATION TO G-SSL
Clearly, this metric and data fidelity term combine to favour nodes of small degree by both fitting better their labelled points and enforcing more regular functions on them. Now, since D is a non-negative matrix, both terms in the objective function remain positive for all F * k and all Y * k . Thus, implying that problem (2.9) is convex with closed form solution given as

F * k = µ L T rw + µI -1 Y * k . (2.11)
The name of the method stems from the fact that, by doing a change of variable, then Eq. (2.11) can be shown to be equivalent to the personalized PageRank vector from [START_REF] Haveliwala | Topic-sensitive pagerank[END_REF]. This will be made precise below.

Lastly, [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] also proposes to assign node u to the class k satisfying to Eq. (2.4).

The generalized optimization framework for G-SSL

In the series of works: [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF][START_REF] Avrachenkov | On the choice of kernel and labelled data in semi-supervised learning methods[END_REF][START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF], a unified optimization framework for G-SSL is proposed. In these works, the following optimization formula is given:

arg min F * k F T * k D -1 LD -1 F * k + µ (F * k -Y * k ) T D 2 -1 (F * k -Y * k ) (2.12)
As it can be seen, these works tweak the optimization problem by incorporating a new parameter . The remarkable feature is that, by properly choosing this parameter, then one can recover as particular cases some of the methods introduced above. More precisely, by setting = 1, objective (2.12) reduces to the standard Laplacian approach; = 12r ecovers the Normalized Laplacian; and = 0 leads to the PageRank optimization problem.

Notably, [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] shows that the solution of this optimization problem can be cast in a unique random walk framework that helps to highlight some differences between G-SSL methods. Precisely, since the real powers of the degree matrix remain a positive semi-definite matrix, the objective above is convex with closed form solution given by

F * k = µ D -LD -1 + µI -1 Y * k . (2.13)
Then, by making the change of variable ↵ = 1(1 + µ), Eq. (2.13) can be rewritten as

F T * k = (1 -↵)Y T * k ∞ k=0 ↵ k (D PD -) k (2.14)
Eq. (2.14) allows to interpret G-SSL methods as a random walk process. This is, for the PageRank case ( = 0), F uk is proportional to the expected number of visits made by random walkers to node u when they start from the labelled points of class k and, at each step, they diffuse to a neighbor with probability ↵ or restart to the starting point with probability 1 -↵. On the other hand, the standard Laplacian ( = 1) implies that F uk is proportional to the number of visits made by walkers to the labelled points of class k when they start at node u and, at each step, they diffuse to a neighbor with probability ↵ or restart to the starting point with probability 1 -↵.

This interpretation of G-SSL as a random walk process was exploited in [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] to derive the following theorem explaining the classification:

Theorem 2. [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] Let pr vu denote the probability that a random walk reaches node u before restarting to node v. Also, let unlabelled node u be assigned to the class k according to the rule: argmax k F uk . Then, u is assigned to the class k that satisfies the inequality

v∈V k d v pr vu ≥ w∈V k ′ d w pr wu , ∀k ′ ≠ k (2.15)
This theorem was used in [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF] to demonstrate that PageRank is the only method that provides stable classifications when ↵ → 1( µ → 0). This is, when ↵ → 1 we have that pr → 1, hence the inequality is controlled by the degree of the labelled points. Thus, if the classes have unbalanced densities, standard Laplacian and Normalized Laplacian easily assign all points into a single class, while PageRank can still give a meaningful classification. Moreover, the inequality implies that if the labelled points all have equal degrees, then all classification methods perform equality.

Furthermore, in [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF], all the G-SSL propositions stemming from the generalized optimization framework have been extensively compared on synthetic and real datasets (les miserables, planted partition, Wikipedia, P2P traffic), and their results indicate that the PageRank-based method is the superior approach in terms of scalability, stability, robustness to classes of different densities, and performance.

Fitting on the labels vs fitting on the graph

In the G-SSL literature, there are two philosophies to fit the labelled data. In the first, which is the one we have considered thus far and considered in [START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF][START_REF] Avrachenkov | On the choice of kernel and labelled data in semi-supervised learning methods[END_REF][START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF], the fitting term acts on all the vertices of the graph. In the second approach, considered in [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF][START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF][START_REF] Bengio | Label Propagation and Quadratic Criterion[END_REF], the fitting term only acts on the labelled vertices. In this subsection, we discuss their differences as we have not seen a discussion in the literature (only [START_REF] Bengio | Label Propagation and Quadratic Criterion[END_REF] briefly points this difference).

To simplify notations, let us denote f = F * k and y = Y * k . Also, for simplicity, we elaborate on the unnormalized Laplacian approach (see Sec. 2.2.1), yet keep in mind that our discussion applies to all the G-SSL methods presented above.

Penalty 1: In this case, one fits over all the nodes in the graph as follows

L 1 = µ (f -y) T (f -y) = µ u∈V (f u -y u ) 2 (2.16)
Penality 2: In this case, one only fits over the labelled data as follows

L 2 = µ (f -y) T I V L (f -y) = µ u∈V L (f u -y u ) 2 (2.17)
Despite looking minor, this change has important implications. We list some of them:

L 1 enforces a stronger regularization. Note that L 1 = L 2 + ∑ u∈V c L f 2 u
.T h u s ,L 1 enforces a stronger regularization by trying to keep the norm of f as small as possible L 1 leads to a graph filter and L 2 to a non-convolutive matrix. Let us cast the G-SSL solution given by both objective functions in a unique expression as f = µ(L+µI) -1 Iy,

CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING

where I = I or I = I V L depending on whether L 1 or L 2 is chosen, respectively. In the former, we have that (L + µI) -1 = Q(Λ + µI) -1 Q T , which clearly corresponds to a graph filter with response h(Λ) = 1(Λ + µ). For the latter, the matrix I V L is not diagonalizable under Q,t h u s(L + µI V L ) -1 is a non-convolutive filter in the sense of [START_REF] Girault | Signal Processing on Graphs-Contributions to an Emerging Field[END_REF].

L 1 defines an invertible kernel while L 2 requires extra regularization. From the graph filter interpretation above, we observe that the role of µI is to shift the spectrum of L, which makes the matrix (L + µI) -1 always invertible. For the case of L 2 ,i t cannot be guaranteed that µI V L shifts the zero eigenvalue of L,t h u s(L + µI V L ) -1 may not be invertible. In [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], the authors propose to solve the problem in the orthogonal to the null space of L (thus working with the pseudo-inverse). Most other works address the issue by adding an extra regularization term as

L ′ 2 = L 2 + ✏ ∑ u∈V c L f 2 u
.T h u s ,t h e y make it resemble L 1 . As a result, the G-SSL kernel given as (L + µI V L + ✏I) -1 ,w h i c h is always invertible. We are not aware of a comparison between these two approaches, though empirical experience suggest that the latter is more stable. However, such solution introduces a new parameter and there are no insights on how to tune it.

L 2 allows to assign infinite confidence to the labelled data (µ → ∞). Consider the case of letting µ → ∞. For L 2 , this could be interpreted as forcing first f u = y u for all u ∈ V L and then minimize

f T Lf . Let f = [f l ; f u ], y = [y l ; y u ] and L = [L ll ,L lu ; L ul ,L uu ] be a split of f , y and L into their labelled and unlabelled parts. By forcing f = [y l ,f u ],t h e n minimization of f T Lf leads to f u = -L -1
uu L ul y l , which is doable upon invertibility of L uu . On the other hand, if we set µ → ∞ in L 1 , then we pull down towards zero the norm of f (see item 1 above) and hence no learning occurs.

L 1 allows a random walk interpretation for some methods. As shown by theorem 2 above, when using L 1 the classification result can be interpreted in terms of competing random walks. These type of conclusions cannot be attained under L 2 as important properties, such as mass preservation, are not satisfied.

Due to the close connection with graph signal processing, the improved stability, and the diffusion properties, in this work we will only consider G-SSL under penalty terms of the type L 1 .

The limit of infinite unlabelled data

Let N data points (x u , u ∈ 1,...,N) be drawn from a smooth probability distribution p(x) on a compact manifold Ω ⊂ R N of intrinsic dimension d. Now, assume that a similarity graph is built by means of the Guassian kernel W uv = exp(-xu-xv ). Further, assume that a constant amount of labelled data is given V L = c. We are interested in the behavior of G-SSL when N → ∞.

Intuition says that the more data we collect, the better our knowledge of p(x) will be, and G-SSL methods will profit more from it. However, it was found in [START_REF] Nadler | Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data[END_REF] that when d ≥ 2, → 0 and N → ∞, G-SSL methods are plagued by the so-called curse of dimensionality. More precisely, [START_REF] Nadler | Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data[END_REF] elaborates on the unnormalized Laplacian (see Sec. 2.2.1) to show that, independently of µ, problem (2.2) can be minimized by 'spiky' functions that per-30 CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING 2.2. FROM TIKHONOV REGULARIZATION TO G-SSL fectly fit the labelled data and are constant everywhere else in the graph. In other words, it is possible to minimize the G-SSL objective with discontinuous functions that do not generalize to unlabelled data. The authors coin this problem to the first order gradient not being restrictive enough in large dimensions, causing the solution space to be too large.

Namely, the regularizer converges to f T Lf → ∫ Ω ∇f (x)p 2 (x)dx when N → ∞.T h u s , since dx has a rather small volume in large dimensions, the integral can still be close to zero even when ∇f (x) → ∞.

The iterated Laplacian G-SSL

As a solution to the aforementioned problem, the authors of [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] proposed a novel regularization approach based on Laplacian iterations. The underlying idea of this work is to restrict the solution space of G-SSL to just continuous functions. Towards this aim, [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] proposes to use, as smoothness penalty, the m-th order Sobolev semi-norm of f instead of the standard Dirichlet form. To induce such property, the authors iterate the Laplacian operator m times in the quadratic form as follows:

arg min f f T L m f + µ(f -y) T (f -y) . (2.18)
The effectiveness of this regularizer follows from the fact that, when N → ∞, the regularizer satisfies:

f T L m f = Ω f (x)∆ m f (x)dx = u m u fu 2 . (2.19)
Thus, pulling down f T L m f implies searching in the space of m-times continuously differentiable functions (the Sobolev space of order m). Moreover, the authors show that such space corresponds to a reproducing kernel Hilbert space iff 2m > d.T h u s ,s h o w i n g that, under such condition, problem (2.18) can provide an effective solution to the curse of dimensionality.

It is important to stress that regularizer f T L m f is not only interesting from the perspective of infinite data. Indeed, in the finite case, the spectral representation of the regularizer allows a nice interpretation in terms of the high order statistical moments of the energy spectral density of f . More precisely, since L is a self-adjoint operator, Riez-Markov representation theorem implies that

f T L m f = u m u fu 2 = m d⌧ f (2.20)
where

⌧ f ( ) = ∑ N u=1 fu 2 ( -u
) is a unique positive Borel measure assigned to each frequency. Clearly, expression (2.20) corresponds to the m-th moment of the set with respect to the measure ⌧ f . In other words, analogous to probabilities assigned to a random variable, the coefficients ⌧ f ( u ) = fu 2 assign a measure to each frequency u and hence regularizer f T L m f computes the m-th moment of the shape ⌧ f with support . To give a concrete example, consider a band pass graph signal f whose energy spectral density ⌧ f is displayed in Figure 2.2. Then, we compute the quadratic form f T Lf and observe in Fig 2 .2a that, indeed, its value corresponds to the first moment of the energy spectral density f (vertical line). Now, we compute f T L 2 f and show, in Figure 2.2b, that it effectively delivers the second raw moment of the energy spectral density f , from which CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING we extract and display the variance by the vertical lines. This observation allows to give a new interpretation to optimization problem (2.18). Namely, while it still searches for functions that fit the labels, for high order m values the quadratic term no longer aims for solutions with minimum mean frequency, but also discriminates parameters such as the spread the frequency content. This interpretation also explains why regularizer f T L 2 f has empirically shown superior performance to f T Lf [START_REF] Belkin | Regularization and semi-supervised learning on large graphs[END_REF][START_REF] Hu | A graph theoretical regression model for brain connectivity learning of alzheimer's disease[END_REF][START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF]: minimization of the second raw moment always implies minimization of the first, but also of the variance.

It is trivial to show that the solution to problem (2.18) can be given in closed form as

f = µ (L m + µI) -1 y (2.21)
From Eq. (2.21) one can easily see that this G-SSL method corresponds to high-order low pass graph filter. Namely, by taking the spectral decomposition of L, we have that f = µ m +µ ŷ. Thus, the effect of m is indeed to further penalize frequencies ( > 1) and to soften the effect in frequencies ( < 1).

As all the G-SSL propositions suffer from the curse of dimensionality problem, [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] proposes to replace L with any of the other Laplacian kernels, i.e L n , L rw , or L T rw , so as to generalize this framework towards the other more performing G-SSL propositions.

Lastly, we recall that one of the main drawbacks of this approach is that there are no insights on how to choose m in practice.

The re-centered kernel G-SSL

A related approach has been proposed in a series of works [START_REF] Mai | The counterintuitive mechanism of graph-based semisupervised learning in the big data regime[END_REF][START_REF] Mai | Revisiting and improving semi-supervised learning: A large dimensional approach[END_REF][START_REF] Mai | Methods of random matrix for large dimensional statistical learning[END_REF]. These works study the more ambitious regime in which both N → ∞ and d → ∞ at the same rate. As part of their results, the authors demonstrate that, in this regime, W uv →  for all u and v. Thus, the data structure gets hidden as small 'perturbations' in the adjacency matrix. By relying on advanced techniques from random matrix theory, the authors show, on a gaussian mixture model, that by taking the Taylor series around ,t h e nar e -c e n t e r i n g tweak of the G-SSL kernel is sufficient to amend the aforementioned problem and recover

-f T Kf + µ(f -y) T (f -y) (2.22)
where K = PWP and

P = I -1 N T .
It is important to note that PWP = 0, hence this new matrix K can be interpreted as a new adjacency matrix of a new graph, where the degree of nodes is zero (hence the name of re-centering). Clearly, doing so implies creation of positive and negatives entries in K which can make the problem above non-convex, though this does not pose an issue as the fitting term implicitly constraints the norm of f . It is also important to stress that despite K being the adjacency matrix of a new graph, such graph codes for the same pair-wise similarities as the involved transformation only implies a translation of the data in the feature space. [START_REF] Mai | Methods of random matrix for large dimensional statistical learning[END_REF] gives a rigorous theoretical justification of why such translation step solves the curse of dimensionality. Those results are beyond the scope of this work, nonetheless, an intuitive explanation can be given as follows: since K has a null degree matrix, then its associated Dirichlet form satisfies

-f T Kf = ∑ (u,v)∈E K u,v (f u -f v ) 2 ≤
0, which, when minimized, the non-informative 'flat' function caused by the curse of dimensionality now becomes the least favoured solution as it achieves the upper bound.

Illustrating example

To illustrate this phenomena, we replicate the experiment of [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] and show how these two methods solve the issue. We generate datapoints from a mixture of two gaussians in R 20 , where 1 = 2 = 1, and µ 1 = -1.5, µ 2 = 1.5 on the first dimension, and µ 1 = µ 2 = 0i n the remaining dimensions. A complete graph is constructed with similarities computed according to the RBF (see Eq. (1.5)) with 2 = 20. One labelled point per class is chosen, and, since we are in a binary setting, we set them to +1 and -1 in a single vector of labels y. We draw 300 points for each gaussian and the task is to recover the two gaussians (left is class +1, right is -1). In Fig. 2.3a, we display the results of applying the normalized Laplacian method on this data set. The points correspond to the classification function CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING 2.3. FROM GRAPH PARTITIONING TO G-SSL of the unlabelled data projected into the first dimension (the one where we shifted the means). As it can be seen, the normalized Laplacian method suffers from the curse of dimensionality, retrieving a flat solution that is completely offset towards one side of the decision boundary. In Fig. 2.3b, we display the result obtained with the Iterated Laplacian approach. Here, we simply iterate the normalized Laplacian from the experiment of Fig. 2.3a for 32 times. Clearly, the Laplacian iterations correct the offset and learn a smooth function f that is consistent with the two gaussians. Lastly, in Fig. 2.3c, we display the result of applying the re-centerd kernel method. It can be seen that it is also able to alleviate the curse of dimensionality, though it displays a higher variance with respect to the iterated Laplacian. As a last remark, we highlight that the tuning µ in the re-centered kernel approach is (i) critical: a bad selection leads the method to not perform at all; (ii) narrow: the range of values where the method performs can be too restricted; and (iii) unstable: this region could significantly vary between different realizations of the gaussians or by increasing the amount of data.

From graph partitioning to G-SSL

In this section, we introduce G-SSL from the perspective of graph partitioning. In graphs, a ground truth class is represented by a group of vertices in the graph. Let us denote such group by S gt ⊂ V. Thus, in graphs, the classification challenge corresponds to finding the binary partition of the graph nodes as:

V = S gt ∪ S c gt . (2.23)
According to the smoothness assumption (see page [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF], if the data is structured, then S gt should form a cluster. Thus, the classification problem can be posed as a clustering one.

As a result, we can use techniques to identify clusters on graphs to find a proxy V = Ŝgt ∪ Ŝc gt .

In the graph literature, numerous techniques have been proposed to find clusters. Since the standard definition of a cluster, i.e. a group of nodes strongly connected internally and weakly connected externally, is not very precise about when a group of nodes can be considered as a cluster and when it cannot, a deluge of clustering methods have been proposed, such as clique searching [START_REF] Fortunato | Community detection in graphs[END_REF], minimum common neighbours [START_REF] Seidman | Network structure and minimum degree[END_REF], maximum modularity [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], or minimum cuts [START_REF] Stoer | A simple min-cut algorithm[END_REF], to name a few. In this work, we concentrate on the minimum cut approaches, that we detail in the next section.

Cut problems on graphs

Min-cut

Since clusters must be poorly connected, one of the simplest approaches to find clusters is to find two sets that have the least possible amount of connections between them. This is the rationale of the min-cut problem [START_REF] Elias | A note on the maximum flow through a network[END_REF], which retrieves as a cluster, the partition minimizing the following objective:

arg min S u∈S v∈S c W uv (2.24)
Despite this opimization problem being solvable in polynomial time [START_REF] Stoer | A simple min-cut algorithm[END_REF], only under mild conditions it leads to satisfactory partitions. Its main issue is that it is extremely prone

34 CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING 2.3. FROM GRAPH PARTITIONING TO G-SSL
to outliers: take an isolated node connected by a single edge with the rest of the graph, then it minimizes objective (2.24).

Ratio-cut

To amend to the min-cut outlier problem, the ratio-cut was proposed in [START_REF] Wei | Towards efficient hierarchical designs by ratio cut partitioning[END_REF]. The ratiocut adds a constraint to penalize small partitions as follows:

arg min

S ∑ u∈S ∑ v∈S c W uv S S c (2.25)
Clearly, this objective should retrieve much consistent clusters, as these should not only be poorly connected between them but also should have similar sizes. However, this objective function still has some limitations. The most notorious is that it overlooks the internal connectivity of sets. Therefore, as long as two sets have similar between-cluster connections and are of similar sizes, it is indifferent for this objective function that one of them may be more strongly connected internally than the other, indicating that it delineates a better cluster.

Normalized cut

The normalized cut was proposed in [START_REF] Shi | Normalized cuts and image segmentation[END_REF] as an improved alternative to the ratio-cut. To capture better whether a group of nodes is a cluster, the normalized cut proposes a new metric which counts the ratio of external and internal connections of this group of nodes. This metric is usually refereed to as the Cheeger ratio of a set, or the conductance of a set. It is formally defined as follows:

Definition 17. Let S ⊆ V be an arbitrary set of nodes. The Cheeger ratio, or conductance, of S is defined as:

h S = ∑ u∈S ∑ v∈S c W uv min{vol(S), vol(S c )} . (2.26)
By definition, the Cheeger ratio satisfies h S ∈ [0, 1] and we have that h S = h S c .F u rthermore, it is clear that the more a group of nodes forms a clear cluster, the smaller its Cheeger ratio. Thus, if we aim to find clusters we must search for sets of small Cheeger ratio. This is precisely the rationale of the normalized cut problem, which aims to find the partition with smallest Cheeger ratio:

arg min S {h S } . (2.27)
The normalized cut problem has been shown to be NP-complete [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. However, one can efficiently approximate its solution, in an unsupervised manner, by leveraging the spectral properties of graphs, or in a semi-supervised manner, by running a diffusion process on the graph. These relaxations are the subject of our next subsections.

Partitioning via spectral clustering

Let us start by introducing the relaxation via spectral clustering. This approach is unsupervised in nature as it fully relies on the spectral properties of graphs. The basis of this relaxation is the Cheeger inequality, a mathematical result that relates the minimum CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING

FROM GRAPH PARTITIONING TO G-SSL

Algorithm 1 Sweep-cut procedure for partitioning a graph from a vector Input: a real valued vector f Output: a binary partition V = Ŝgt ∪ Ŝc gt 1) Let v 1 ,...,v N be a rearrangement of the vertices in descending order, so that the permutation vector q satisfies

q v i = f v i d v i ≥ q v i+1 = f v i+1 d v i+1
2) Let S j = {v 1 ,...,v j } be the set of vertices indexed by the first j largest elements of q 3) Let (f ) = min j h S j 4) Retrieve Ŝgt = S j for the set S j achieving (f ) value attained by the normalized cut objective and the eigenvalues of the graph.

We start defining the Cheeger constant of the graph:

h G = min S h S = min S T S L S T S D S , (2.28)
where the last term follows from h S = h S c . The hard constraint of searching on the space of indicator functions can be relaxed to searching on the space of real-valued functions ( S ≈ g ∈ R N ). By implementing this change, we obtain that h G ≈ min g (g T Lg)(g T Dg).

Notably, this expression corresponds to eigenvalue problem of L rw (see page 20), thus relaxing the problem implies converting it into an eigenvalue one. However, as it is, the relaxation is useless for clustering purposes since it assumes that h G ≈ 1 = 0, and therefore g = q 1 = . A better supposition is that

h G ≈ 2 = min g⊥D g T Lg g T Dg , (2.29)
whose solution is given by the second smallest eigenvector of L rw . This eigenvector is commonly referred to as the Fiedler vector [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Fiedler | Algebraic connectivity of graphs[END_REF]. Then, the Cheeger inequality essentially amounts to define a way to partition the graph from the Fiedler vector, and, if (g) denotes the Cheeger ratio of such partition, then the inequality bounds how far are 2 , h G and (g). In precise terms, to retrieve a partition from the Fiedler vector, we introduce the sweep-cut technique in Algorithm 1. Then, the Cheeger inequality reads as follows:

Theorem 3. [START_REF] Chung | Spectral graph theory[END_REF] Let g ′ = Dg where D refers to the degree matrix, and let (g ′ ) be the Cheeger ratio of the partition obtained by applying a sweep-cut on g ′ . Then, h G , 2 ,a n d (g ′ ) are related as follows:

2h G ≥ 2 ≥ (g ′ ) 2 2 ≥ h 2 G 2 .
(2.30)

The Sweep-cut procedure reduces the exponential search to a linear search. Moreover, theorem 3 implies that the partition retrieved by the sweep is granted to have a Cheeger ratio that is within a quadratic factor of the optimum. While this bound is not very tight, if h G is very small then the partition retrieved by the method is likely to be a good cluster as it correponds to a small Cheeger ratio. Moreover, we recall that this lower bound guarantee is still an open problem for most other graph partitioning methods relying on the Fiedler vector, such as the popular approaches based on k-means [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Partitioning via random walks for G-SSL

Diffusion processes can also be used to find, in a semi-supervised manner, partitions with small Cheeger ratio. The rationale is the following: assume that S is a set of small Cheeger ratio (may not necessarily be the smallest), thus if a diffusion process is started within S, then it should be hard for such diffusion process to escape S as it is poorly connected with the rest of the graph. As a result, by looking at the nodes in which the diffusion process spent most of the time we should be able to identify a good approximation of S. There are two important things to remark: (i) the methodology assumes starting a diffusion process inside the set under search, thus semi-supervision plays a key role; and (ii) for the set S to display a confinement of diffusion processes, it is not necessary that it possesses the smallest Cheeger ratio in the entire graph. This highlights that diffusion-based techniques bring more flexibility allowing to find partitions with small Cheeger ratio but not necessarily the smallest (as spectral clustering does), yet we recall that if the diffusion is started within the set of smallest Cheeger ratio, then the diffusion processes will also display the confinement phenomenon and can be used to approximate the normalized cut.

In this subsection, we introduce results showing that random walks are one of the basic diffusion processes that can be used to implement these ideas. This is, if a random walk is started within a set of small Cheeger ratio, then it should get trapped for a long time within the set, meaning that if one picks the nodes with largest random walk probability as a partition, then this partition should have small Cheeger ratio.

We introduce the following result from [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF], which formalizes the fact that random walks cannot not escape clusters easily.

Proposition 1. [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF] Let S ⊂ V be an arbitrary set of nodes. Let u ∈ S be a labelled point selected with probability proportional to its degree in S, i.e. d u vol(S). Further, let (in) t

(S) denote the probability that a lazy random walk starting from u stays entirely in S after t steps. Then, for all t ≥ 0, we have

E (in) t (S) ≥ 1 -t h S 2 (2.31)
This proposition shows that smallest the Cheeger ratio of a set, the higher the probability that a walker that started inside the set remains within the set. Then, if we look at the random walk probability vector, we should identify large scores in the nodes indexing S and small scores in the nodes of S c .

The next result we introduce states that if such mass concentration phenomenon is present on the t-step random walk probability vector t , then applying the sweep-cut procedure on all the probability vectors up to t steps is guaranteed to retrieve a partition with small Cheeger ratio. Let us recall that the notation t (S) = ∑ u∈S ( t ) u means sum of entries in the nodes indexing S. Thus, we have [START_REF] Lovász | The mixing rate of markov chains, an isoperimetric inequality, and computing the volume[END_REF][START_REF] Chung | Four proofs for the Cheeger inequality and graph partition algorithms[END_REF]:

Lemma 1. [79, 103] Let S ⊂ V
where t = inf t ′ ( t ′ ) for all t ′ ≤ t and u ∈ V.
This lemma says that if the probability of finding a walker in a set S after t steps is much larger than the probability of finding the walker in the set in the stationary state, then applying a sweep-cut on all the probability vectors 0 ... t up to step t implies finding a partition with small Cheeger ratio. Clearly, Proposition 1 and Lemma 1 complement each other to demonstrate that if a set S has small Cheeger ratio, then diffusing random walks and applying sweeps will find a good proxy of S.

It is important to stress that the selection of t is critical and can significantly vary between graphs. For small t, walkers may not visit enough all the members of the set under search, which harms the sweep. Thus, it is better to let t grow so that the walk closely mixes. However, doing so can greatly increase the complexity of the method, as it is necessary to perform too many sweeps.

Partitioning via PageRank for G-SSL

PageRank is another diffusion-based algorithm that can be used to identify clusters with small Cheeger ratio. Its numerous theoretical studies [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Andersen | Using pagerank to locally partition a graph[END_REF][START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF][START_REF] Chung | Pagerank as a discrete green?s function[END_REF][START_REF] Tsiatas | Diffusion and Clustering on Large Graphs[END_REF], applications [START_REF] Avrachenkov | Pagerank based clustering of hypertext document collections[END_REF][START_REF] Chung | Distributing antidote using pagerank vectors[END_REF][START_REF] Graham | Finding and visualizing graph clusters using pagerank optimization[END_REF][START_REF] Chung | Multi-commodity allocation for dynamic demands using pagerank vectors[END_REF] and implementations [START_REF] Chung | Dirichlet pagerank and trust-based ranking algorithms[END_REF][START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Broder | Efficient pagerank approximation via graph aggregation[END_REF][START_REF] Chung | A sharp pagerank algorithm with applications to edge ranking and graph sparsification[END_REF] have made of PageRank a state-of-the-art clustering algorithm. In Sec 2.2.4, we introduced PageRank as a solution to a Thikhonov regularization problem and briefly discussed the interpretation of PageRank as random walk process. In this subsection, we deepen into this diffusion interpretation and introduce results which show that this diffusion process can more simply identify clusters in the graph.

Let us recall that, given a distribution, y, the PagerRank vector can be expressed as f = µ L T rw + µI -1 y. Further, by doing a small change of variable ↵ = 1(1 + µ),t h e n the PageRank vector can be cast as the solution to the fixed point equation: f T = (1 -↵)y T + ↵f T P . Thus, PageRank can be interpreted as the equilibrium state of a process that, at each step, with probability ↵ does a random walk step, or with probability (1 -↵) revisits the starting distribution y. Clearly, given proper normalization of y, the PageRank score at a particular node is equal to the probability of finding a walker, at equilibrium, at this node. Notably, this equilibrium state is the result of a well-behaved diffusion process on the graph as stated by the following Lemma [START_REF] Tsiatas | Diffusion and Clustering on Large Graphs[END_REF]:

Lemma 2.
[105] Let f denote the personalized PageRank vector with personalization vector y. Then f satisfies the following properties 1. mass preservation:

∑ u∈V f u = ∑ u∈V y u 2. stationarity: f = ⇡ if y = ⇡ 3. limit behavior: f → ⇡ as µ → 0 and f → y as µ → ∞
Lemma 2 is important as it shows that PageRank is well behaved diffusion process propagating the initial mass y, through the graph, with a diffusion rate controlled by the parameter µ.

In [START_REF] Andersen | Using pagerank to locally partition a graph[END_REF], it is shown that the behavior of this diffusion process is tightly related to the cluster structure of graphs. This connection between PageRank and clustering is quantified in the following result.

Lemma 3. [START_REF] Andersen | Using pagerank to locally partition a graph[END_REF] Let S ⊂ V be an arbitrary set with vol(S) ≤ vol(G)2. For a labeled point placed at a node u ∈ S selected with probability proportional to its degree in S, i.e. d u vol(S), the PageRank satisfies

E[f (S c )] ≤ h S µ . (2.33)
This lemma implies that if we apply PageRank diffusion from the labelled points of a set S and it has a small h S , then the probability of finding a walker outside S is small and the nodes with largest PageRank value should index S.

The works of [START_REF] Andersen | Using pagerank to locally partition a graph[END_REF] and [START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF] formalize the notion that a high concentration of PageRank mass implies a good cut. The former shows that a set with small Cheeger ratio can be found by looking for regions of high concentration of PageRank mass. The latter improves that result, showing that such set can be found more easily by looking for a sharp drop in the sorted PageRank scores. More precisely, the result of [START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF] shows that, when doing a sweep of the PageRank vector, if there is a sharp drop in rank at the set S j ,t h e nt h es e t S j has small Cheeger ratio.

Lemma 4. [START_REF] Andersen | Detecting sharp drops in pagerank and a simplified local partitioning algorithm[END_REF] Let h ∈ (0, 1), j be any index in [1,N] and ↵ ∈ (0, 1] denote the PageRank restarting probability. Let C(S j ,S c j ) = ∑ u∈S j ∑ v∈S c j W uv be the numerator of the Cheeger ratio. Then, S j satisfies one of the following: (a) C(S j ,S c j ) < 2hvol(S j ); or (b) there is some index k > j such that vol(S k ) ≥ vol(S j )(1 + h) and q k ≥ q j -↵hvol(S j )

In other words, this lemma implies that either S j has a small Cheeger ratio, or there is no sharp drop at q j (recall that q is the permutation vector in the sweep-cut).

Illustrating example

To have a better grasp on these results, we give an illustrating example. In Fig. 2.4a, we display a simple synthetic dataset generated from a mixture of three gaussians in R 2 and a graph build from the data. In this case S gt corresponds to one of the gaussians and y is given by the red nodes. We index the vertices such that S gt consists of the first 200 nodes. In Fig. 2.4b, we display the PageRank vector with initial condition y.I n accordance to Lemma 3, we can observe that the PageRank vector concentrates a large amount of mass in the nodes indexing S gt , thus effectively revealing it. Now, in Fig. 2.4c, we display the degree-normalized scores sorted in decreasing order, where we note that a sharp drop appears. According to Lemma 4, if the sorted scores display a sharp drop in rank, then the set associated to this rank is granted to have small Cheeger ratio. As it can be seen in Fig 2 .4d, the set with smallest Cheeger ratio from the sweep coincides with the sharp drop. Finally, we output this set as our partition Ŝgt .S i n c e Ŝgt has a small Cheeger ratio, then, by definition, it is a good cluster and hence a good approximation of S gt as confirmed in Fig. 2.4e. again and show the results in Fig. 2.5d. Clearly, perturbing the data completely disrupts the eigenvectors of the Laplacian, causing the spectral clustering approach to retrieve poor partitions. On the other hand, the PageRank method displays robustness by still retrieving a very accurate partition.

CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING

Open problems

In this section, we highlight some open problems in G-SSL.

The problem of extending sweeps beyond PageRank. Section 2.2 introduced G-SSL methods that rely on comparing classification functions to classify data. One of such methods relied on comparing PageRank vectors. In Section 2.3, we boosted G-SSL with more flexibility by showing that, by doing a sweep, we only needed a single PageRank vector to find a binary partition and classify a targeted class. Therefore, we can readily extrapolate this idea to the other G-SSL propositions and boost them with extra flexibility by doing sweeps on their classification functions. However, this is not straightforward as the relationship between these other G-SSL proposition and the graph topology remains an open problem. Indeed, it is not even clear if there is any. 1 Thus, it cannot be given guarantees that doing a sweep on such approaches will lead to a meaningful classification.

The problem of graphs with unclear (fuzzy) clusters. By revisiting Lemma 3, it can be seen that if S gt has a small h Sgt , then the PageRank method is bound to accurately detect S gt . In other words, if the ground truth class under search designates a strongly disconnected cluster, then it is a set that PageRank can eventually easily detect.

Clearly, the Lemma also indicates the cases in which PageRank cannot operate. Namely, as h Sgt increases, then the Lemma implies that the random walkers escape S gt more easily and, as a result, the PageRank vector will not display the confinement of the information necessary for the sweep to deliver a reliable result. Thus, not very well delineated clusters pose a big challenge for PageRank.

The problem of unbalanced number of labelled points: Theorem 2 highlights an important issue affecting the G-SSL methods that arise from the generalized optimization framework. Precisely, by looking at the inequality, it can be seen that the summations depend on the cardinality of labelled points. Thus, cases of unbalanced number of labeled points can potentially bias the classification, causing unlabelled nodes prone to be assigned to the class with more labelled data. It is important to stress that preprocessing the data to even the labelled points is not a solution. Take for instance the case of two classes, one 10 times larger than the other and accordingly with 10 more labeled points. Despite starting with unbalanced labels, the problem and the inequality in Theorem 2 are balanced because, even if we have ten more units of mass to diffuse, we have ten times more nodes to reach. Thus, normalization of labelled data is only valid if classes are assumed of the same size. Notably, for the PageRank case, classifying the data using sweeps provides a solution to this problem as the behavior of the sweep is independent of the number of labelled points. Thus, we can do a multi-class classification by doing a sweep on the PageRank vector for each class and combining results. However, while this solves the unbalanced labelled data issue (and embeds topological guarantees on the multi-class output), the price to pay is that some nodes may be assigned into more than one class or to none.

The problem of hubs: The classification functions for various G-SSL can be interpreted in terms of random walks exploring the graph. Thus, the effectiveness of such approaches is based on walkers being able to visit enough the nodes under search. However, graphs with hubs or regions more densely connected than their surroundings may cause walkers to be trapped in such regions for a large time, harming the exploration capabilities of walkers and degrading the qualities of the classification functions. Therefore, graphs with a hub-like structure pose challenges to G-SSL.

better why, in general, the PageRank method performed extremely well and outperformed the other G-SSL propositions in the comparisons done in [START_REF] Sokol | Graph-based semi-supervised learning methods and quick detection of central nodes[END_REF].

Chapter 3

L γ -PageRank for Semi-Supervised Learning

Introduction

In Chapter 2, numerous G-SSL proposition were introduced. It was shown that in terms of flexibility, stability and theoretical understanding, the PageRank method arises as the state-of-the-art approach for G-SSL. However, various issues can still degrade the performance of PageRank, that we aim to address in this chapter.

In the face of such challenging settings, it is natural to try to enhance the performance of PageRank by embedding it with stronger regularity properties. As proposed by [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], such effect can be attained by iterating the random walk Laplacian in the PageRank solution.

However, an issue with such approach is that it causes most of the PageRank properties to be lost. Namely, there is no known optimization problem having such expression as a solution and it is unclear if it can be given diffusion properties that can be related to the graph topology, implying that one cannot derive guarantees that a sweep still leads to a meaningful partition. Thus, due to the lack of insights on the properties and qualities of the partitions retrieved by this approach, it is hard to build upon and to address the issues listed in Chapter 2.

In this chapter, we revisit the Laplacian powers as a means to improve G-SSL and to address the aforementioned problems. We propose a novel generalization of PageRank by using (non necessarily integers) powers of the combinatorial Laplacian matrix L ( > 0). We coin this generalization as the L -PageRank method and it constitutes the main contribution of this dissertation. In contradistinction to an iterated PageRank [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF], our L -PageRank: (i) enables us to have an explicit closed form expression of the underlying optimization problem; (ii) permits a diffusion and a topological interpretation; (iii) allows us to use the regime of fractional ; and (iv) gives us insights on how to optimally tune to maximize performance.

In our formulation, the key ingredient is a reinterpretation of the L operator. Precisely, while [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] interprets the Laplacian powers as a Sobolev norm regularizer, in our approach we show that, for every fixed value, a new graph is generated. These emerging graphs, which we refer to as the L -graphs, reweight the links of the original structure and create

INTRODUCTION

edges between originally far-distant nodes. Thus, our generalized L -PageRank procedure is an extension of PageRank to operate on the L -graphs. To analyse our algorithm, we show that two regimes of L -graphs arise: (i) the regime of < 1: in this regime, the L -graphs make emerge the so-called Lévy flight random walk, i.e. walkers that, with small probability, can jump between far-distant nodes in a single step; and (ii) the regime > 1: here, the L -graphs give rise to signed graphs, i.e. graphs with positive and negative edges. Notably, both regimes carry the potential to improve G-SSL. On the one hand, the capacity of the Lévy walkers to jump far away can be convenient in settings in which the significance of the learned functions degrades due to normal random walkers getting stuck for too long in undesired graph regions, like strong hubs. On the other hand, the emergence of positive and negative edges bear the potential to enhance clustering as the signed edges introduce what can be seen as agreements (positive edges) or disagreements (negative edges) between nodes, allowing us to revamp clusters as groups of nodes agreeing between them and disagreeing with the rest of the graph. Thus, throughout the chapter we investigate the potential of these L -graphs to better delineate targeted ground truth class S gt . Our results are the following:

Regime

< 1: our analysis shows that, in this regime, our L -PageRank procedure corresponds to an extension of the regular PageRank algorithm that is now driven by Lévy processes. Since such extension consists in applying the regular PageRank algorithm to a L -topology, then, by proving that the latter is always undirected with positively weighted edges, we guarantee that the full frame of theoretical results given in Chapter 2 directly applies to our setting. Through numerical experimentations, we demonstrate that the non-local nature of the Lévy random walkers can be useful to overcome skewed graphs with trapping regions and to enhance the detection of classes with sub-cluster structures.

Regime > 1: we theoretically show that, while not necessarily modelled by random walkers, our L -PageRank method remains a well behaved diffusion process propagating labelled data on the signed L -graphs (still, preserving the PageRank properties). Thus, we extend the Cheeger ratio definition to L -graphs and prove that if there is a L -graph in which S gt has a smaller Cheeger ratio (w.r.t the standard case of = 1), then we can more accurately identify it with our generalized L -PageRank procedure using the sweepcut technique. By means of numerical investigations, we point the existence of an optimal value that maximizes performance. Thus, we propose an algorithm that allows to estimate the optimal directly from the initial graph and the labeled points. Lastly, we demonstrate the classification improvements permitted by L -PageRank on several real world datasets commonly used in classification, as well as the relevance of the estimation procedure for the optimal tuning. Such results demonstrate that our L -PageRank can significantly increase classification performance and also amend the issue of unbalanced labelled data.

The chapter is organized as follows. Section 3.2 introduces L -graphs. Section 3.3 defines L -PageRank and derives its solution. Section 3.4 analyses our algorithm in the regime < 1: Section 3.4.1 shows that L -PageRank is an extension of standard PageRank to Lévy processes; Section 3.4.2 evaluates the classification benefits brought by the incorporation of the Lévy processes. Section 3.5 analyses our algorithm in the regime > 1: Section 3.5.1 analyses its clustering capabilities; Section 3.5.2 discusses the existence of 3.2. THE L -GRAPHS an optimal and its estimation; Section 3.5.3 evaluates L -PageRank and the algorithm for the optimal estimation in practice. Section 3.6 discusses differences between L -PageRank and iterated Laplacian [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF] and compares them in practice. Section 3.7 extends the generalized G-SSL framework of [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] to L -graphs and numerically demonstrates that the new topologies can also enhance the other G-SSL propositions.

The L -graphs

In this contribution, we propose to change the graph topology in which the problem is solved as a means to improve classification. We evoke such change by considering powers of the Laplacian matrix, noting that the L operator, for > 0, generates a new graph for every fixed value. More precisely, by exploiting the Laplacian definition, we define the L -graphs as follows:

Definition 18. Given a > 0,t h eL -graph with adjacency matrix W and degree matrix D is given as

L = QΛ Q T = D -W , (3.1
)

where [D ] uu = [L ] uu ,a n d[W ] uv = -[L ] uv ,w i t hu ≠ v.
It can easily be shown that the L -graphs satisfy the Laplacian property:

Lemma 5. For al l > 0,t h eL -graphs satisfy the Laplacian property:

[D ] uu = v [W ] uv . (3.2)
Proof. Follows trivially from the fact that, for all , we have that L = 0.

We now highlight that the L -graphs possess two operational regimes: one in which the emanating graphs are undirected positively weighted graphs ( ≤ 1); and another in which the emerging topologies are undirected signed graphs ( > 1). Precisely, let us expand the L operator in its binomial series as follows:

L = (D -W ) = D 12 D 12 -D 12 D -12 WD -12 D 12 = D 2 I -D -12 WD -12 D 2 = D 2 I -D -12 WD -12 + ( -1) 2 (-D -12 WD -12 ) 2 - ( -1)( -2) 6 (D -12 WD -12 ) 3 + D 2 . (3.3)
Then, we can see that: (i) for 0 < ≤ 1, the infinite sum within the squared brackets entails non-positive off-diagonal terms in L , thus implying that W codes for an undirected graph with positive edges; and (ii) for > 1, the off-diagonal terms can entail positive entries, meaning that W codes for an undirected signed graph. Now, while graphs with only positive edges can be considered as particular cases of signed graphs, numerous useful CHAPTER 3. L -PAGERANK FOR SEMI-SUPERVISED LEARNING results developed for the former have not yet been extended to the latter, which remains widely unexplored. Thus, it is better to treat each regime independently.

The remarkable aspect about the L -graphs is that the topologies emerging from both regimes carry the potential to improve classification.

Regime of γ < 1

As described above, in this regime, the L -graphs make emerge positively weighted graphs. Thus, we can compute a stochastic transition matrix from these graphs as P = D -1 W .

In [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and lévy flights[END_REF], the following result is given concerning P :

Theorem 4 ( [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and lévy flights[END_REF]). Consider an infinitely large 1-D regular lattice with periodic boundary conditions. Then, as 0 and 1, we have

[P ] uv ∼ ∆ -(2 +1) uv (3.4)
This theorem says that, on very large rings, the associated L -graphs make emerge transition matrices that allow random walkers to jump between any pair of nodes in the graph with a probability that is a power law of their distance. Thus, while in the initial ring a walker can only transition to its adjacent neighbors, in the L -topologies the walkers can also jump farther away with small probability. In other words, the L -graphs make emerge the so-called Lévy flight random walk [START_REF] Riascos | Long-range navigation on complex networks using lévy random walks[END_REF]. To the best of our understanding, this is the only analytic result developed for the topologies emanating from fractional Laplacian matrices, thus it remains to be theoretically proven that such result extends to arbitrary networks. Nonetheless, extensive numerical evidence suggest that this same behavior extends to arbitrary networks [START_REF] Riascos | Fractional dynamics on networks: Emergence of anomalous diffusion and lévy flights[END_REF]. In Figure 3.1, we illustrate how the Lévy flights arises on a K-NN graph build from the swiss-roll dataset (Figure 3.1a), the lollipop graph (Figure 3.1b), and the planted partition (Figure 3.1c).

Clearly, the new dynamics of these more volatile random walkers entail an improved capacity to explore the graph. Particularly, their ability to jump far away can allow to more 3.3. THE L -PAGERANK METHOD

The L -PageRank method

In this section, we introduce our main contribution: the L -PageRank G-SSL, a generalization of PageRank that operates on the L -graphs.

Departing from the optimization problem in Eq. (2.9) (see page 27), we revamp PageRank to operate on the L -topology as follows:

Definition 19. The L -PageRank G-SSL is defined as the solution to the optimization problem: arg min

f f T D -1 L D -1 f + µ(f -y) T D -1 (f -y) . (3.5)
Since this proposition is designed to operate on both unsigned and signed graphs, we must take care that it is a well-behaved object. In the following Lemma, we show that, for all > 0, problem (3.5) is convex and its solution can be found in closed form.

Lemma 6. Let > 0. Then, problem (3.5) is convex with closed form solution given as:

f = µ L D -1 + µI -1 y. (3.6)
The proof of this Lemma is deferred to Appendix 3.A.

Now that we have shown that, for all , our formulation is a well-posed problem, we proceed to study its theoretical properties and clustering capabilities. Thus, since we showed in Section 3.2 that these topologies, for ≤ 1, are positively weighted undirected graphs, then it is clear that analysis given for regular PageRank in Chapter 2 directly applies to our setting. As a result, by using the change of variable ↵ = 1(1 + µ), we can recast our L -PageRank solution as:

f T = (1 -↵) ∞ k=0 ↵ k y T P k . (3.7)
Hence, our contribution is that Eq. (3.7) corresponds to a generalization of the PageRank algorithm to the Lévy process encoded by P . This leads our L -PageRank formulation to admit the following interpretation: the L -PageRank vector at node u is proportional to the expected number of visits made by Lévy random walkers to node u, when, at each step, they decide to either continue the walk with probability ↵, or revisit the starting point with probability (1 -↵).

Clearly, having the ability to tune the dynamics of the walkers through the parameter can be useful to enhance, in some cases, our learned functions f .

3.4. ANALYSIS OF < 1: L ÉVY FLIGHTS FOR CLASSIFICATION degree of freedom allows to now, for all ↵, get node (5) assigned to the correct class. However, the walkers are still not diffusive enough to get node (6) correctly classified. Thus, we increase the diffusion capacity of the walkers even more by further reducing = 0.01. As it can be seen in Figure 3.7, we can now obtain, irrespective of ↵, the desired partition. This example illustrates how the added degree of freedom allows us to override an skewed graph setting which standard PageRank is not able to cope with. Enhanced detection of graphs with sub-community structures Experimental setup and goals. In this experiment, our goal is to illustrate that our L -PageRank can also help to more easily indentify classes with sub-cluster structures.

Our experimental setup is as follows. We consider two graphs in which the target set S gt has internal sub clusters (see Figure 3.8). On the one hand, we generate data from a SBM with three clusters (V = S 1 ∪ S 2 ∪ S 3 ) and define S gt = S 1 ∪ S 2 , so that the partition to find is V = S gt ∪ S Results and discussion. Figure 3.9 displays the performance of L -PageRank on the classification of the two graphs from Figure 3.8. Observe how, in both cases, the standard PageRank algorithm is not able to accurately recover S gt despite it having a small Cheeger ratio. This is because, in both graphs, our diffusion starts inside another set of small Cheeger ratio, thus, as implied by the results from Chapter 2, it is hard for the diffusion process to escape such cluster and cover all S gt . Now, let us note how the introduction of helps to improve the detection of S gt . Clearly, this is because the long-jump 3.5. ANALYSIS OF > 1: SIGNED GRAPHS FOR CLASSIFICATION be used to find clusters in the L -graphs.

For our analysis, it is useful to first extend some of the graph topological definitions to the L -graphs. Namely, let vol (S) = ∑ u∈S [D ] uu denote the generalized volume of S. Let ⇡ denote a generalized stationary distribution with entries given by (⇡

) u = [D ] uu vol (G). It is important to stress that [D ] uu = ∑ k k Q 2 uk ≥ 0.
Thus, for all > 0, the generalized volume and the generalized stationary distribution are non-negative quantities.

Another important topological definition introduced in Chapter 2 was the Cheeger ratio metric. Clearly, it cannot longer be employed to assess the presence of clusters in the L -graphs as it lacks the ability to account for the sign of edges. Thus, we generalize the Cheeger ratio definition to the new graphs as follows.

Definition 20. For a set of nodes S ⊆ V , the generalized Cheeger ratio, or generalized conductance, of S is defined as: Lemma 7 shows that, for a given L -graph, sets of small generalized Cheeger ratio are bound to have strong between-cluster disagreements and strong within-cluster agreements as well as small between-cluster agreements and small within-cluster disagreements, thus coinciding with our definition of clusters in signed graphs. In other words, to find clusters in the L -graphs, we should look for sets of small generalized Cheeger ratio. Now, we show that, while not necessarily modelled by random walkers, our L -PageRank remains a well-behaved diffusion process having ⇡ as stationary state and diffusion rate controlled by the µ parameter. 1. mass preservation:

∑ u∈V f u = ∑ u∈V y u 2. stationarity: f = ⇡ if y = ⇡ 3. limit behavior: f → ⇡ as µ → 0 and f → y as µ → ∞
The proof of this Lemma is deferred to Appendix 3.C.

Our next results shows that it is hard for such diffusion process to escape clusters in the L -graphs. Lemma 9. Let > 0 and let S ⊂ V be an arbitrary set with vol (S) ≤ vol (G)2.F o ra labeled point placed at node u ∈ S with probability proportional to its generalized degree in S, i.e.

[Dγ ]uu volγ (S) , L -PageRank satisfies:

E [f (S c )] ≤ h ( ) S µ . (3.9)
The proof of this Lemma is deferred to Appendix 3.D Lemma 9 admits a similar interpretation as Lemma 3 (see page 39). Namely, if L -PageRank is applied to the labeled points of some set S with small h ( ) S , then diffusion is confined to S and the score values outside of S are expected to be small. Thus, by looking at the nodes with largest score values we should be able to retrieve a good estimation of S. Now, let us note that if such score concentration phenomenon takes place, then a sharp drop must appear after sorting the L -PageRank scores in descending order. We will use the following lemma to show that if a sharp drop is present, then the sweep cut procedure applied on the L -PageRank vector retrieves a partition Ŝ that has small h ( ) Ŝ .

Lemma 10. Let q denote the permutation vector and S j denote the set associated to q j obtained by applying the sweep-cut procedure on the L -PageRank vector. Then, the partition V = S j ∪ S c j satisfies the inequality:

A ( ) out (S j )2 - (q j -q j+1 ) (q 1 -q N ) -D ( ) out (S j )2 (q j -q j+1 ) (q 1 -q N ) -1 ≥ µ (y(S j ) -f (S j )) (q 1 -q n ) ≥ A ( ) out (S j )2 (q j -q j+1 ) (q 1 -q N ) -1 -D ( ) out (S j )2 - (q j -q j+1 ) (q 1 -q N ) . (3.10)
The proof of this Lemma is deferred to Appendix 3.E.

To show that this Lemma implies a good partition if a sharp drop is present, let us depart noticing that out (S j ) is not much larger than D ( ) out (S j ). In the inequality (3.10), we have two cases in which (q j -q j+1 )(q 1 -q N ) ≈ 1: (i) q is approximately constant; and (ii) q has a drop that satisfies q j ≈ q 1 and q j+1 ≈ q N .T h e former can only occur if f → ⇡ and clearly no cluster can be retrieved from that vector, as confirmed by the inequality growing unbounded. The latter case is what we coin as having a sharp drop between q j and q j+1 . In such case, the inequality is controlled by the difference y(S j ) -f (S j ) which, due to the mass preserving property and the assumption that q j+1 ≈ q N , should be small. Thus, granting that A ( ) out (S j ) is not much larger than D ( ) out (S j ) and S j has a small h ( )

u∈S j v∈S c j [W ] uv = A ( ) out (S j ) -D ( ) out (S j ) ≥ 0. ( 3
S j .
Discussion. The previous results show that L -PageRank is a sensible tool to find clusters in the L -graphs, i.e. groups of nodes with small generalized Cheeger ratio. Thus, revisiting the classification case in which we target group of nodes S gt , we have that the smaller the value of h ( ) Sgt ,t h eb e t t e rt h eL -PageRank method can recover it. This observation, in addition to noting that standard PageRank emerges as the particular case of = 1, indicate that we should be able to enhance the performance of G-SSL in the detection of S gt by finding the graph, i.e. the value, in which h ( )

Sgt < h (1)
Sgt .

The selection of γ

Case of = 2: analytic study In Section 3.2.2, it was argued that the topology emerging from L 2 places a negatively weighted link between nodes at a 2-hop distance, thus carrying the potential to place a big amount of disagreements between clusters that may enhance their separability. Our next result formalizes this claim, demonstrating that, on assortative graphs from the Planted Partition model, it is expected that the L 2 -graph improves the generalized Cheeger ratio.

Sgt = 2E h (1) Sgt 2 , (2)
where E h

(1)

Sgt = p out (p in + p out ).
The proof of this Theorem is deferred to Appendix 3.F.

Corollary 1. If p in ≥ p out , then E h (2)
Sgt ≤ E h

Sgt ≤ h (1) Sgt is that D Sgt ≥ max u∈Sgt v∈S c gt W uv + max w∈S c gt `∈Sgt W w`. (3.13)
The proof of this Proposition is deferred to Appendix 3.H Proposition 2 points in the same direction as Theorem 5, saying that graphs having a cluster structure are bound to benefit from L 2 . Concretely, the first term on the right hand side of the inequality searches, among all the nodes of S gt , the one that has the maximum number of connections towards S c gt . The second term does the reverse for the nodes of S c gt . Hence, asking for the nodes of S gt to have, on average, more connections than the maximum possible boundary implies that S gt should have a cluster structure.

An algorithm for the optimal selection of

Numerical experiments show that increasing can further decrease the generalized Cheeger ratio up to a point where it starts increasing. We show an example of this phenomenon in Figure 3.10a, displaying the evolution of h ( ) Sgt as a function of when S gt corresponds to a digit of the MNIST dataset. From Figure 3.10a, it is evident that an optimal value appears:

* = arg min h ( ) Sgt . (3.14)
Hence, this raises the question of how to find such value. Clearly, since the behavior of h

( )
Sgt depends on S gt , in practice, taking the derivative or performing a greedy search to find * cannot be employed since S gt is unknown. A second question that arises is whether such optimal value changes drastically or smoothly with changes in S gt . To address it, we perform the following test: for a given S gt (same MNIST digit), we remove some percentage of the nodes in S gt and record the optimal value on subsets of S gt . More precisely, recall that h ( )

Sgt = T
Sgt L Sgt T Sgt D Sgt , hence we randomly select some percentage of the entries indexing S gt in Sgt , set them to zero and obtain a new indicator function indexing a subset of S gt . Mean results are evaluated in the original curve and displayed in Figure 3.10b. As it can be seen, the figure suggest that it is not necessary to know S gt to find a proxy ˆ of * , it suffices to know a subset of S gt .

Based on the insights from our last experiment, we propose Algorithm 2 for the estimation of * . The rationale of the algorithm is to exploit the labeled points and the initial graph to find a proxy Ŝ of S gt on which we can compute the estimate. The procedure consists in letting walkers started from the label points, run for a number of steps that is determined by the maximum geodesic distance between the labels. This allows walkers to explore S gt without having the chance to go far from it. Then, after running the walk, we list the nodes in descending order according to the probability of finding a walk at a node. We take the first element on the list (the one where it is more likely to find a walker), add it to Ŝ and remove it from the list, so that the former second element becomes the first in the listing. We repeat the procedure until the probability of finding a walker in the nodes conforming Ŝ is 0.7.

Output:ˆ Compute ∆ uv ∀ u, v ∈ V Sgt . Set k = max u,v {∆ uv } Set = yy 1
Run a k-step walk with seed : x T = T P k Reorder the vertices as v 1 , ,v N , so that

x v i ≥ x v i+1 for i = 1 ∶ N do if ∑ i j=1 x v j < 0.7 then Set ( Ŝ ) v i = 1 else Set ( Ŝ ) v i = 0 end if end for Compute h ( ) Ŝ = T Ŝ L γ Ŝ T Ŝ Dγ Ŝ ∀ Return ˆ = arg min h ( ) Ŝ .
In Table 3.1, we evaluate the performance of Algorithm 2 on the estimation of * for all the digits of the MNIST. The graph construction guidelines are given in Section 3.5.3 (Real world datasets). For the test, 500 realizations of labeled points and a grid of ranging from 1 to 7 with a resolution of 0.2 were used. The first row displays, as * ,t h e value of (from the input range) attaining the minimum generalized Cheeger ratio. The second row displays the performance of the algorithm when estimating such value. The last three rows show the value of the generalized Cheeger ratio evaluated at * ,ˆ and = 1, respectively. As it can be seen, our estimator finds values of ˆ whose Cheeger ratios are: (i) significantly smaller than those of = 1; and (ii) close to the optimal. CHAPTER 3. L -PAGERANK FOR SEMI-SUPERVISED LEARNING 57

Numerical experiments

Planted Partition

Experimental setup and goals. In the following experiment, we show that L -PageRank can increase the performance of G-SSL as the graph approaches the Planted Partition detectability transition. In Chapter 1, we covered results indicating that the Planted Partition possesses a detectability threshold above which unsupervised methods are unable to retrieve a meaningful clustering (see Theorem 1 in page 11). As for G-SSL, the work in [START_REF] Zhang | Phase transitions in semisupervised clustering of sparse networks[END_REF] shows that such threshold can be overcome when a fraction of labeled points is introduced to the task. Nonetheless, the performance of G-SSL drastically degrades when approaching the detectability transition.

The experimental setup is the following: for a given C out C in , a realization of the Planted Partition is drawn with n = 500 and C avg = 3. Then, 1% of labeled points are sampled at random and the L -PageRank method is applied for different values of µ lying on a discrete grid. The clusters are determined via a sweep-cut procedure, and the best performance is retained. The whole procedure is repeated for 10 different realizations of the labeled points. Finally, all the preceding steps are repeated for 100 graph realizations. Performance is assessed in terms of the Matthews Correlation Coefficient (MCC).

Results and discussion.

S becomes large. Then, we observe that the introduction of allows to decrease h ( ) Sgt , which, accordingly, enhances the clustering performance. Furthermore, the figure verifies that the smaller the value of h

Real world datasets

Experimental setup and goals. In our following experiment, we assesses the performance of L -PageRank and Algorithm 2 on real world datasets.

The experimental setup is as follows: graphs are built connecting the K-Nearest Neighbors (KNN) with distances computed via the Gaussian kernel, so that the weight between points x u and x v is given by W uv = exp{-x u -x v 2 2 2 }. For each class, 2% of labeled points are randomly selected, L -PageRank is applied for a grid of µ values, partitions are retrieved via the sweep-cut, and the best performance, assessed in terms of MCC, is retained. Such procedure is repeated for 100 realization of labeled points, except for the MNIST on which 30 realizations only are employed. In all cases, classes are balanced in size and the graph construction parameters are selected to provide a good distribution of weights as follows: (a) MNIST [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]: Images of handwritten digits (1 to 9). From the entire dataset, 200 images of each digit are selected and used to build the graph with KNN = 10 and = 10 4 ; (b) Gender Images [START_REF] Hond | Distinctive descriptions for face processing[END_REF]: Images of male and female subjects for gender recognition. From the entire dataset, 200 images of each gender are selected and used to build the graph with KNN = 60 and = 10 4 . The large value of KNN is to avoid disconnected components; (c) BBC articles [START_REF] Greene | Practical solutions to the problem of diagonal dominance in kernel document clustering[END_REF]: Word frequency attributes from news media articles. From the entire dataset, 200 business and 200 entertainment articles are used to build the graph with KNN = 5 and = 50; and (d) Phoneme [119]: Five attributes to discern nasal sounds from oral sounds. From the entire dataset, 200 oral and 200 nasal sounds are used to build the graph with KNN = 10 and = 2.

Results and discussion. Table 3.2 shows the performance of L -PageRank on the classification of the real world datasets. Clearly, the introduction of can significantly improve performance and, in general, the estimation ˆ performs close to the optimal value * . It can be seen that some datasets are more sensitive to than others. For instance, in the BBC articles we observe that a small change in , going from = 1t o * = 1.1, increases performance, and going further to ˆ = 1.3 and = 2 significantly worsens the classification. On the other hand, the MNIST dataset is less sensitive to , obtaining similar performances with larger variations in . Results and discussion. Table 3.3 displays the performance L -PageRank in the presence of unbalanced labeled data. It is important to stress that, in this framework, a unique value of is used to retrieve all the clusters at the same time, precluding the notion of an optimal as defined in Section 3.5.2. However, one value of seems to perform better, we denote it as = Best. As it can be seen, the introduction of helps to significantly improve the classification performance in the presence of the unbalanced labeled data.

CHAPTER 3. L -PAGERANK FOR SEMI-SUPERVISED LEARNING

The generalized Cheeger ratio: necessary but not sufficient Experimental setup and goals. Our theoretical results indicate that, for a target S gt , the smaller the value of h ( ) Sgt , then the easier it is for our L -PageRank algorithm to detect S gt . In our next experiment, we show that having a small h ( ) Sgt is a necessary condition but not sufficient. This is because the Cheeger ratio only counts a ratio of external and internal connections of a group of nodes, but it does not consider how such connections are distributed. Thus, while a set S gt may have a small Cheeger ratio, the distribution of its connections may not be favorable for information to properly diffuse.

The experimental setup is as follows: we create a graph from the SBM with three clusters: Results and discussion. Figure 3.12 displays the performance of L -PageRank at recovering S gt as its internal connectivity varies through the ratio C 12 C 11 . As it can be seen from Figure 3.12b, despite C 12 C 11 varying, the Cheeger ratio of S gt remains constant. Indeed, we can observe that the L -topologies can help to further reduce h ( ) Sgt . However, as shown in Figure 3.12a, the Cheeger ratio of S gt is not the only factor involved in its detection since for small values of C 12 C 11 we cannot detect S gt accurately while for larger values the performance significantly improves. Clearly, this is because the internal sub-cluster structure of S gt , in the regime of small C 12 C 11 , makes it hard to correctly diffuse information. Thus, as displayed by Fig 3 .12c, we need to increase the internal connectivity fo S gt to enhance the recovery of S gt . 1

V = S 1 ∪ S 2 ∪ S

Differences with Iterated Laplacian

In this section, we highlight some differences between our L -PageRank and the generalization obtained by iterating the random walk Laplacian in the PageRank solution as proposed in [START_REF] Zhou | Semi-supervised learning by higher order regularization[END_REF].

Let us start emphasising the differences between the closed form solutions

• L -PageRank: f = µ L D -1 + µI -1 y. (3.15)
• Iterated PageRank:

f = µ LD -1 m + µI -1 y. (3.16)
Thus, we can see that the contrast lies on the operators L D -1 and LD -1 m : the former corresponds to the random walk Laplacian of a L -graph, while latter is high order version of the random walk Laplacian of the initial graph. By reverting to the spectral domain, we can more clearly highlight the differences between both operators. Let L D

-1 = Q Λ Q -1 , 3.6. DIFFERENCES WITH ITERATED LAPLACIAN then we have that LD -1 m = Q 1 Λ m 1 Q -1
1 . Thus, when comparing both methods with respect to the standard PageRank, we have that our L -PageRank formulation changes both the spectrum and eigenvectors, while, in the Iterated Laplacian case, the eigenvectors are left unchanged. Clearly, relating Q to Q 1 and Λ to Λ 1 is not a trivial task. Numerical evidence suggests that Λ ≈ Λ 1 only for small but that Q and Q 1 can significantly differ. Thus, we leave the formal link between the output of both methods as an open problem. In practice, these spectral difference translate into the following differences between both methods:

1. There is no known optimization problem having the Iterated PageRank as a solution. The experimental setup is as follows: a graph from the MNIST dataset is build using the guidelines given in Section 3.5.3 (Real world datasets). Then, one labelled point per class is sampled at random and both methods are applied, in the multi-class setting, for a grid of µ values and Laplacian powers in the range = m = 1,...,5. Accuracy, assessed by MCC, is computed for each class and then the scores of all classe are combined to obtain a global one. The configuration that leads to the best global score is retained. Lastly, the whole procedure is repeated for 30 different realizations of labelled points.

Results and discussion. Table 3.4 displays the performance of both L -PageRank and Iterated PageRank in the classification of the digits from the MNIST dataset. We observe that, in both cases, the extra degree of freedom allows to enhance the classification performance but that L -PageRank achieves the best overall performance. Indeed, for both methods the sweet spot is attained at = m = 3, but the accuracy differences are due to L -PageRank being capable to double the improvements given by the iterated Laplacian in digits 1 and 2, while the iterated Laplacian does better in digits 7 and 9 but only by one unit. Now, for other and m, L -PageRank performs better for = m = 2 and worse for = m = 5. The drop at = 5i sd u et ot h eL 5 -graph permitting to much better recover digit 2 but at the price of degrading the detection of the other digits, particularly digit 6.

DIFFERENCES WITH ITERATED LAPLACIAN

Solving the curse of flatness

Experimental setup and goals. In Chapter 2, it was pointed that, in the limit of infinite unlabelled data, G-SSL methods suffer from the so-called curse of flatness (see Section 2.2.7, page 30). Indeed, it was shown there that the Iterated Laplacian G-SSL was proposed to amend such issue. In our following experiment, we show that our L -PageRank is not suited to address the curse of flatness.

Our experimental setup is as follows: we replicate the experiment given in Section 2.2.7 (see page 33).

Results and discussion. Clearly, our formulation is not able to cope with the curse of dimensionality issue. We presume that this is because Λ and Λ 1 significantly differ for large , meaning that the L -PageRank vector does not carry Sobolev regularites.

Extending the generalized optimization framework to L -graphs

In this section, we show that the generalized optimization framework for G-SSL [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] (see page 28) can also be readily extended to the L -graphs and incorporate their benefits.

Let us depart from optimization problem (2.12) and extend it to the L -graphs as follows: arg min

f f T D -1 L D -1 f + µ (f -y) T D 2 -1 (f -y) (3.17)
Thus, we observe that by properly choosing , we can recover the L extension of the three popular methods. Namely, by choosing = 1 we obtain the L -Standard Laplacian method; = 12 leads to the L -Normalized Laplacian G-SSL; and = 0 reduces to our L -PageRank. Now, since the -th power of a positive diagonal matrix remains positive, then the same argumentation used in the proof of Lemma 6 can be applied to problem (3.17) to show that, for all , it is convex and its solution can be given in closed form as

f = µ D -L D -1 + µI -1 y. (3.18)
Then, by making the change of variable ↵ = 1(1 + µ), we can recast Eq. (3.18) as Our experimental setup is as follows: two cases are considered (i) balanced labelled points; and (ii) unbalanced labelled points. For the experiments, we follow the same graphs and guidelines used for the experiments in Section 3.5.3. The only variation we use is that, for the experiment with balanced labels, we consider 2% of labelled points in both classes.

f T = (1 -↵)y T ∞ k=0 ↵ k D P D - k (3.
As classification method we employ the L -Normalized Laplacian ( = 12).

Results and discussion. Table 3.5 displays the classification performance of L -Normalized Laplacian in the classification of various real world datasets in the presence of both balanced labelled points and unbalanced labelled points. As it can be seen, the introduction of helps to (i) get moderate increments in performance in the case of balanced labels; and (ii) significantly improve the performance when facing unbalanced labelled datasets.

Appendix: technical proofs

3.A Proof of Lemma 6

Proof. It suffices to show the positive semi-definiteness of the functional and to apply the first order optimality condition. Let f = Q T D -1 f . Then, the left term satisfies

∑ j j f 2 j ≥ 0. It can be shown that [D ] uu = ∑ j Q 2 uj j ≥ 0 granting the right term satisfies ∑ u (f u -y u ) 2 [D ] uu ≥ 0. Now,
computing the derivative of the functional with respect to f and equaling to 0 leads to: L D -1 f + µ(fy) = 0. The lemma is proved after isolating f .

3.B Proof of Lemma 7

Proof. For an arbitrary and fixed > 0, let S denote an arbitrary set of vol

(S) ≤ vol (G)2. Let r = (A ( ) out (S) -D ( ) out (S))(A ( ) in (S) -D ( ) in (S)).
It is easy to show that h ( ) S = r(r + 1), which is monotonically increasing with r.T h u s ,t h es e tS that minimizes r also minimizes h

( ) S .

3.C Proof of Lemma 8

Proof. From the demonstration of Lemma [START_REF] Subramanya | Soft-supervised learning for text classification[END_REF] we have that L D -1 f + µ(fy) = 0. Then, T L D -1 + µ T f = µ T y.S i n c e T L = 0 we have that T f = T y,p r o v i n g( i ). We prove property (iii ) using the same expression. We only develop the case µ → 0 since the case µ → ∞ follows the same steps: taking lim µ→0 L D -1 f + µ(fy) = 0 leads to L D -1 f = 0, whose solution is proportional to ⇡ = D vol (G). Lastly, we prove (ii ) by noting that the operator L D -1 has a positive real spectrum as it is similar to D -12 L D -12 which is positive semi-definite. Thus, we can use the inverse Laplace transform of the resolvent showing that T S c f can be interpreted as E [f (S c )] when labels are selected with probability proportional to their generalized degree in S. Using the fact that

(L D -1 + µI) -1 = ∫ ∞ 0 e -t e -tL γ D -1 γ µ dt,
L D -1 + µI -1 L D -1 + µI = I, (3.21)
we express

f = I - 1 µ L D -1 + 1 µ L D -1 L D -1 + µI -1 L D -1 y. (3.22)
The upper bound is thus obtained by substituting y and summing over S. Employing property (i ) from Lemma 8 finishes the proof.

3.E Proof of Lemma 10

Proof. We only show the proof of the lower bound as the upper bound follows a similar derivation. We recast Eq. ( 6) as L D -1 f = µ (yf ).T h u s ,t h es e tS j satisfies:

µ ((y(S j ) -f (S j )) = T S j L D -1 f = T S j L q = u∈S j ,v∈S c j [W ] uv (q u -q v ) = u∈S j ,v∈S c j W + uv (q u -q v ) - u∈S j ,v∈S c j W -uv (q u -q v ) + u∈S j ,v∈S c j W + uv (q j -q j+1 ) - u∈S j ,v∈S c j W + uv (q j -q j+1 ) + u∈S j ,v∈S c j W -uv (q j -q j+1 ) - u∈S j ,v∈S c j W -uv (q j -q j+1 ) ≥ (q j -q j+1 )2A ( ) out (S j ) + D ( ) out (S j ) -(q 1 -q N )2D ( ) out (S j ) + A ( ) out (S j ) . (3.24)
Re-ordering terms finishes the proof.

3.F Proof of Theorem 5

Proof S as follows [START_REF] Rice | A stochastic version of the price equation reveals the interplay of deterministic and stochastic processes in evolution[END_REF]:

E h (1) S = E T S L S vol(S) = E T S L S E [vol(S)] + ∞ i=1 (-1) i E[ T S L S ] i vol(S) + T S L S , i vol(S) E [vol(S)] i+1 = E T S L S E [vol(S)] + ∞ i=1 (-1) i E T S L S (vol(S) -E[vol(S)]) i E[vol(S)] i+1 = E T S L S E [vol(S)] + ∞ i=1 (-1) i E T S L S E[

vol(S)] vol(S) E[vol(S)]

-

1 i = E T S L S E [vol(S)] + ∞ i=1 (-1) i c i , (3.26)
where

a, i b = E (a -E[a])(b -E[b]) i . The fact that vol(S) < 2E [vol(S)
] and the monotonicity of the expected value imply that the sequence ∑ i c i decreases monotonically. Also, it can be shown that its dominant term: c 1 = O(n -2 ). Replacing the expectations and evaluating the limit leads to: Thus, we cast:

E h (2) S = E T S L 2 S vol 2 (S) = E T S L 2 S E [vol 2 (S)] + ∞ i=1 (-1) i E T S L 2 S E[vol 2 (S)] vol 2 (S) E[vol 2 (S)] -1 i = E T S L 2 S E [vol 2 (S)] + ∞ i=1 (-1) i c (2) i . ( 3

3.G Proof of Corollary 1

Proof. Let p in = p out +✏ and assume that h

(1)

S ≥ h (2)
S .T h u sp out (p in +p out ) ≥ 2(p out (p in + p out )) 2 , which can be further simplified to 1 ≥ 2p out (2p out + ✏). We observe that such expression holds for ✏ ≥ 0 and equality occurs when ✏ = 0.

3.H Proof of Proposition 2

Proof. We search a condition on S that permits

W uw + max `∈S c v∈S W `v = vol(S) S -max u∈S w∈S c W uw + max `∈S c v∈S W `v , (3.30)
where we have used Lehmers and Holders inequalities and that Fast and efficient implementations

T S L 2 S = ∑ u∈S (∑ w∈S c W uw ) 2 + ∑ `∈S c (∑ v∈S W `v) 2 .

Introduction

In Chapter 3, we extended PageRank and other popular G-SSL propositions to powers of Laplacian matrices. We showed that our extensions permit to significantly enhance the performance and flexibility of G-SSL. Moreover, it was proven that our methods enjoy from a well-behaved solution expressed in closed form. However, a strong limitation of our closed form expressions is that they require to perform matrix inversion, meaning that they can be prohibitively expensive (or even unfeasible) to calculate in large scale contexts. Clearly, this arises as a serious drawback of G-SSL since numerous modern systems foster applications involving thousands or millions of dimensions. Let us take the web graph as an example: it has 60 × 10 12 web-sites and it evolves at a rate of 600 × 10 3 new pages created every second [START_REF] Zhan | Fast incremental pagerank on dynamic networks[END_REF]. Thus, despite their remarkable performance, the value of our G-SSL propositions remains limited if they cannot be used to address such important applications. In order to bring us a step closer towards this goal, in this chapter we investigate computationally efficient implementations that can better cope with such large scale rapidly evolving scenarios.

In terms of efficient implementations, the standard PageRank algorithm constitutes the state of the art approach. This is because, as we discussed in Chapter 2, standard PageRank possesses a random walk interpretation that numerous works have exploited to derive efficient ways to compute PageRank vectors [START_REF] Haveliwala | Efficient computation of pagerank[END_REF][START_REF] Fujiwara | Efficient personalized pagerank with accuracy assurance[END_REF][START_REF] Bahmani | Fast personalized pagerank on mapreduce[END_REF][START_REF] Broder | Efficient pagerank approximation via graph aggregation[END_REF][START_REF] Fogaras | Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments[END_REF]. Among these, three highly successful algorithms, practically employed in networks involving millions of vertices and billions of edges, arise: (a) Power iteration [START_REF] Jeh | Scaling personalized web search[END_REF][START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]; (b) Monte-Carlo simulation [START_REF] Avrachenkov | Monte carlo methods in pagerank computation: When one iteration is sufficient[END_REF]; and (c) Gauss-Southwell method [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Berkhin | Bookmark-coloring algorithm for personalized pagerank computing[END_REF]. Power iteration is the fundamental approach for efficient PageRank computing. It consists on iterating the PageRank fixed point equation until convergence. Due to its recursive nature, it allows to efficiently compute PageRank vectors via matrix-vector products, thus allowing a distributed implementation with a cost proportional to the number of edges in the graph. Monte-Carlo simulation runs individual random walkers and then estimates the entries of the PageRank vector according to the frequency of visits made to nodes by the walkers. It has the advantage of being easily parallelizable and it has been reported to give good estimates from only a few iterations. The Gauss-Southwell method is a fast approach to compute approximate PageRank vectors. It employs two vectors: the approximate PageRank vector and a residual vector coding for the error in the approximation. Then, it pushes mass from the 4.1. INTRODUCTION residual vector into the approximate PageRank vector iteratively until the residual vector diminishes below certain threshold. Albeit the algorithm is centralized, it is inexpensive to compute with a running time that is independent of the size of the graph.

The success of these algorithms also lies in that they have been effectively adapted to more efficiently cope with evolving graph structures. Let us stress that, in real world applications, it is common that sensors constantly collect new data, users in social networks continuously make new followers/friends or join/leave the network, or articles in citation networks become more or less influential as time passes by. Thus, to classify all these new data, or to adapt the class of a given node to a new state of the network, one needs to constantly re-compute the output of G-SSL. Evidently, doing this at a fast pace can simply be too computationally demanding to be practical. Notably, the works of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Bahmani | Fast incremental and personalized pagerank[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] have shown that, when the graph changes smoothly, it is wasteful to discard an existing PageRank vector in order to compute a new one. Instead, such works show that the algorithms introduced above can be adapted to update an already existing PageRank vector in sublinear time. Their key observation is that changes in the graph tend to only affect the entries of the PageRank vector that lie close to where the change happened. Thus, implying that one only needs to update the entries of the PageRank vector in the local vicinity of a change. To have an idea on the practical gains given by these works, [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] is able to update PageRank vectors in a web graph of 105 million vertices and 3.7 billion edges in only 3 microseconds, which is more than 10000 faster than doing full re-computation via the power method. Clearly, we aim to attain such efficient implementations to the remainder of G-SSL methods, particularly the ones proposed in this work. However, it is not straightforward to apply these algorithms beyond the PageRank case as they heavily rely on its Markov chain structure, which, we recall, our L -based extensions do not possess.

In this chapter, we leverage results from the field of Graph Signal Processing (GSP) to derive extensions of the aforementioned algorithms to the general family of G-SSL methods. Towards this goal, we exploit the fact that, despite not necessarily having a Markov chain structure, the G-SSL methods considered in this work do have an interpretation in terms of graph filters. Concerning the latter, the field of GSP has developed a solid toolbox that allows to efficiently compute the output of graph filters. In particular, there are two main approaches: the Chebyshev polynomials [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF] and the autoregressive moving average (ARMA) filters [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF]. In the former, one approximates the graph filter response by means of a truncated polynomial of the graph operator. In the latter, the transfer function of the filter is implemented by means of a recursive formula that converges as long as the filter poles lie within a stability region. Both approaches are very appealing as they permit distributed implementations with a cost proportional to the number of edges.

The ARMA recursions are particularly relevant four us, as our main contribution from this chapter is to show that they permit an extension of the algorithms from [START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] to the general G-SSL setting. In principle, if one directly uses the definition of ARMA filters to implement the G-SSL frequency response, then the ARMA filters only serve to implement G-SSL for a narrow regime of values of the µ parameter. Thus, by mirroring [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF], we do a shifting of the operator's domain and show that by doing this, then the region of stability can be extended to all µ > 0, leading us to obtain a recursive formula that extends the power method to the general G-SSL setting. By elaborating on this ARMA recursive formula, we then extend the Gauss-Southwell method of [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF] to general

STATE-OF-THE-ART APPROACHES FOR PAGERANK COMPUTATION

G-SSL procedures. Lastly, in the second part of the chapter, we use these results to extend the updating algorithms of [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] to the general family of G-SSL propositions. In addition to extending these important algorithms, in this chapter we study other efficient approaches. Concerning the polynomial representations of G-SSL covered in the first part of the chapter, we propose and assess the effectiveness of a novel representation based on Greens functions that also leads to an efficient and distributed algorithm. With respect to the update algorithms, we propose a novel promising approach based on neural networks to more effectively solve the update problem.

State-of-the-art approaches for PageRank computation

In this section, we recall the state of the art approaches of [START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF][START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] to efficiently compute PageRank vectors, that we aim to extend to the more general G-SSL propositions. To simplify notations, let us denote by pr ↵ (y) the personalized PageRank vector of restarting probability ↵ and initial condition y.

PageRank on static networks

Power iteration

In Section 2.3.4 (see page 38), it was shown that PageRank can be cast as the solution to the fixed point: pr

↵ (y) = (1 -↵)y + ↵P T pr ↵ (y) (4.1)
Note that Eq. (4.1) corresponds to an eigenvector problem. This can be seen by rewriting it as pr ↵ (y) = (1 -↵)y T + ↵P T pr ↵ (y). The matrix in squared brackets is normally referred to as the Google matrix, thus it can be seen that PageRank corresponds to the eigenvector with eigenvalue 1 of the Google matrix. If P is irreducible, then such matrix codes for a Markov chain with a stationary state, meaning that it only posses one eigenvalue lying in its spectral circle and hence the PageRank vector can be found via the power method. This latter is defined through the recursive formula [START_REF] Jeh | Scaling personalized web search[END_REF][START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]:

p (t) = (1 -↵)y + ↵P T p (t-1) , (4.2)
where p (t) denotes the PageRank estimation at iteration t. This recursion is very efficient to implement as to obtain the new iteration one simply needs to: (i) perform a (usually sparse) matrix-vector product; (ii) re-scale the resulting vector; and (iii) add the (re-scaled) labelled points. Thus, the cost of the algorithm is determined by the matrix-vector step and the number of iterations until convergence. Concerning the latter, it is not hard to show that the following relationship holds:

pr ↵ (y) -p (t) ∞ ≤ ↵pr ↵ (y) -p (t-1) ∞ ≤ ↵ t pr ↵ (y) -p (0) ∞ (4.3)
This inequality says that the power method converges in exact arithmetic and it has an asymptotic convergence rate determined by ↵ t → 0. As a result, if the algorithm requires from K iterations to converge, then its running time is O(KE). Importantly, this procedure allows a distributed implementation given in Algorithm 3.

STATE-OF-THE-ART APPROACHES FOR PAGERANK COMPUTATION

Algorithm 4 [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF] Approximate PageRank vectors via Gauss-Southwell method Input: P , p (0) , and ✏ Output: Approximate PageRank vector p and its residual r r

(0) = (1 -↵)y -I -↵P T p (0) t=0 while r (t) ∞ > ✏ do u = arg max u (r (t) ) u p (t+1) = p (t) + (r (t) ) u u r (t+1) = r (t) -(r (t) ) u u + ↵P T (r (t)
) u u t ++ end while Return p = p (t) and r = r (t) drastically change, then the G-SSL solution should be relatively stable, implying that there may be better alternatives than re-computing from scratch the PageRank vector every time a change occurs. In this section we present adaptations of the algorithms introduced above that allow to perform efficient local updates to the PageRank vector.

To proceed, consider two graphs: G(V, E,W) and an evolved version of such graph given as G( Ṽ, Ẽ, W ). Moreover, let P = D -1 W and P = D-1 W denote the transition matrices of G and G, respectively. To have consistent sized matrices, let nodes joining/leaving the network be modelled as isolated nodes that get connected/disconnected. By definition, we set these isolated nodes with zero rows and columns in P and P . Please note that by adding rows full of zeros to P we do not change the convergence of the chain as this only adds adds eigenvalues equal to zero and preserves the unique eigenvalue in the spectral circle. Now, we present the following result from [START_REF] Ipsen | Mathematical properties and analysis of google?s pagerank[END_REF], saying that if a small change in the graph occurs, then the PageRank vector should not drastically change. Lemma 12 ([128]). Let pr ↵ (y) and pr ↵ (y) denote the Pagerank vectors on G and G, respectively. Then, we have that

pr ↵ (y) -pr ↵ (y) ∞ ≤ ↵ 1 -↵ P -P ∞ (4.7)
In addition to this result, it is important to stress that changes only reflect locally in the perturbation. To have a grasp on this, let us illustrate such phenomenon in Figure 4.1.

In the figure, we display the Minnesota graph (a well known toy graph) and we show the effect that adding a new node has on the PageRank vector. More precisely, in the left figure, we show (in red) the new node joining the graph. Then, in the right plot, we show the difference between the PageRank vectors from the initial graph and the evolved graph.

As it can be seen, the differences only appear in the region surrounding the arriving node. The implication of this observation is that one can keep the same scores in the PageRank vector for nodes that are far from the perturbation, hence avoiding the need to spend computational resources to re-estimate the score of such vertices, and then one only needs to compute the new scores for the nodes encircling the change. Algorithm 5 [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] Local PageRank updating via power iteration Input: ↵,p r ↵ (y), P , P .

CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS

Output: pr ↵ (y).

r = ↵[ P T -P T ]pr ↵ (y) Compute pr ↵ (r) via the power method Return pr ↵ (y) = pr ↵ (y) + pr ↵ (r)(1 -↵)
1-hop vicinity of the perturbed nodes. Hence, since pr ↵ (r) entails starting a diffusion process from the initial condition r, then one can interpret Eq. (4.8) as r containing the information for an update and pr ↵ (r) as a way to diffuse this update in G, starting from the perturbed nodes and then propagating it to nodes farther away. Since pr ↵ (r) can be computed by means of the power method, then one can control the scope of propagation for an update depending on the number of iterations used in the algorithm. This is, if one uses K iterations to estimate pr ↵ (r), then the update is propagated to nodes in a K-hop vicinity from the perturbations. This provides significant computational benefits as one only needs to explore the graph within this K-hop region to get the new PageRank vector, implying that (i) the algorithm has sublinear complexity; and (ii) if, at most, there are M edges are contained in the K-hop vicinity of a node that changed, and c changes occur, then the cost of the update is bounded by O(cKM ). If one uses large values of K, then one gets better approximations, yet one may end up exploring most of the graph while getting negligible practical benefits. Thus, the goal is find a good tradeoff between accuracy and complexity. The procedure proposed in [START_REF] Yoon | Fast and accurate random walk with restart on dynamic graphs with guarantees[END_REF] is summarized in Algorithm 5.

Local updating via Gauss Southwell

In [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF], the authors extended the Gauss Southwell method to perform efficient updates to approximate PageRank vectors. The underlying idea of their approach is to also use warm restarts for the Gauss-Southwell method. In precise terms, if the restart parameter and initial condition do not change, and the Gauss-Southwell method, for graph G, outputs p and r as an approximate PageRank vector and its residual, respectively, then [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] proposes Apply Gauss-Southwell on p(0) and r(0) , store result in p and r

Return p and r to use, for graph G, the following initialization (still, preserving Eq. (4.4)):

p(0) = p (4.10) r(0) = r + ↵[ P T -P T ]p (4.11)
The method proposed in [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] is shown in Algorithm 6. By definition, r ∞ < ✏ and, as discussed above, the term ↵[ P T -P T ]p is non-zero everywhere but in the 1-hop vicinity of the perturbed nodes. As a result, only few entries in r(0) can surpass the tolerance threshold, having the implication that with only a few push operations the algorithm will drive these entries below the threshold again. Thus, the algorithm is extremely efficient in practice. However, since r(0) may now have positive or negative entries, deriving theoretical bounds on the running time of Algorithm 6 significantly complexifies. The authors of [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] give two results in this regard: one using amortized analysis and another in expected value sense. For the former, [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] shows that Algorithm 6 is amortized by O(1✏).W i t h respect to the latter, [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF] shows that if m edges are randomly and sequentially inserted, then, in expected value, it takes O(log(m)✏) iterations for Algorithm 6 to converge.

Fast and efficient implementations of G-SSL on static graphs

In this section, we derive extensions of the algorithms from Section 4.2.1 to the general family of G-SSL propositions. Moreover, we explore other distributed approaches for efficient G-SSL computation. Let us commence clarifying that we cannot replace P by P in the algorithms above and use them to implement our L -PageRank method. This is because P , for > 1, is no longer a stochastic matrix, implying that its spectral radius is larger than 1 and the recursive Eq. (4.1) diverges. Thus, other alternatives must be sought.

A better alternative consist in noticing that all the G-SSL methods presented in this PhD work can be expressed in a general linear system form:

Rf + µf = µy, (4.12)
where R ∈ R N ×N denotes a generalized reference operator. Thus, the choice of R determines the G-SSL method under consideration. Table 4.1 lists possible values of R.

Consider the spectral representation of R and the definition of the Graph Fourier Transform (GFT) given in Chapter 1. Then, we have that the solution to the linear system above can be expressed as fu = µ This equation shows that the u-th frequency component of f corresponds to a re-scaling of the u-th frequency component of y according to the transfer function h(Λ) = µ µ+Λ .I n other words, Eq. (4.13) shows that G-SSL methods correspond to a low-pass graph filter in which the labelled points constitute the signal to be filtered and the regularization parameter µ determines the cut-off frequency of the filter.

R L γ D -1 γ D -1 2 γ L γ D -1 2 γ D -1 γ L γ (LD -1 ) m -PWP with P = I -1 N T
Classical results from matrix theory say that any function on the spectrum of a matrix is a function of the matrix itself. Therefore, implying that if h(Λ) is approximated through a polynomial function: h(Λ) ≈ ∑ K t=0 c t Λ t , then such approximation can be expressed in the vertex domain as

h(Λ) = h(R) ≈ ∑ K t=0 c t R t .
The assets of this rewriting is that the filter output is then expressed as

f = K t=0 c t R t y, (4.14)
which can be computed recursively, in a distributed manner, and with cost O(KE).

Thus, the question that arises is how to find the best set of coefficients for such polynomial. In the GSP literature, there are two state-of-the-art approaches to approximate filter functions via polynomials: (i) the Chebyshev polynomials; and (ii) the ARMA recursions. In this section, we leverage them to efficiently implement G-SSL. In particular, we show that the ARMA recursions imply a direct extension of the algorithms from Section 4.2. In addition, we derive a novel polynomial representation based on the Greens function and explore its feasibility.

Generalized implementation via Chebyshev polynomials

In [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF], the Chebyshev polynomials for graph filter approximation were proposed. Such work proposes to approximate the filter function h(Λ) by the following truncated series, which has been shown to be optimal in the ∞-norm sense [START_REF] Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF][START_REF] Tremblay | Design of graph filters and filterbanks[END_REF]:

h(Λ) ≈ 1 2 c 0 + K t=1 c t Tt (Λ), for Λ ∈ [0, max ] , (4.15)
where Input at node u: max , y u , µ, R uv ∀ v ∼ u, K, and {c t ∶ t = 0,...,K}.

Tt (Λ) = 1,t = 0 Λ-,t = 1 2 Λ-Tt-1 -Tt-2 ,t ≥ 2 . ( 4
Output at node u:

f (K) u ( T0 (R)y) u = y u Transmit y u to all neighbours v ∼ u Transmit y v from all neighbours v ∼ u ( T1 (R)y) u = ∑ v={v∼u}∪u 1 R uv y v -y u for t = 2 ∶ K do Transmit ( Tt-1 (R)y) u to all neighbours v ∼ u Receive ( Tt-1 (R)y) v from all neighbors v ∼ u ( Tt (R)y) u = ∑ v={v∼u}∪u 2 ( Tt-1 (R)y) v -2( Tt-1 (R)y) u -( Tt-2 (R)y) v end for Return f (K) u = 1 2 c 0 y u + ∑ K t=1 c t ( Tt (R)y) u
Then, in the vertex domain, we obtain the following K-term approximation of G-SSL

f (K) = 1 2 c 0 y + K t=1 c t Tt (R)y (4.17)
It can be seen from Eqs. (4.16) and (4.17) that to implement this approximation one needs to know max and K. We recall max can be efficiently estimated, for instance via the Lanczos method [START_REF] Parlett | On estimating the largest eigenvalue with the lanczos algorithm[END_REF]. With respect to the choice of K there are not clear insights on how to choose it to attain a target approximation error. This is because it is hard to derive the asymptotic convergence rate of the series from its coefficient formula. Thus, in practice, the selection of K remains a design problem. We summarize the distributed implementation of G-SSL via Chebyshev polynomials in Algorithm 7.

Generalized implementation via Greens functions

In this subsection, we contribute with a novel polynomial expansion of G-SSL based on the Greens function that leads to an efficient and distributed algorithm.

Let us commence by identifying Eq. (4.12) as a discrete Helmholtz equation in which µ acts as the diffusion rate and the labels, y, take the role of an external forcing as an inhomogeneous term. Then, we retrieve this PDE Green's function by means of the inverse Laplace transform of the resolvent (R + µI) -1 . Doing so allows us to express G-SSL in an integral form as

f = ∞ 0 µe -µ⌧ e -⌧ R yd ⌧ . (4.18)
For the family of G-SSL methods under consideration the spectrum of R is positive real granting convergence of the transformation. The only exception is the Re-centered Kernel method which may present negative eigenvalues and µ > -0 must be considered for convergence. Eq. (4.18) represents a novel approach to represent the G-SSL label propagation process: the integrand tracks the state of the system after the initial mass distribution y 82 CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS 4.3. FAST AND EFFICIENT IMPLEMENTATIONS OF G-SSL ON STATIC GRAPHS has diffused during a (continuous) time ⌧ via an exponentially distributed weighted heat kernel. Then, we can use this expression to obtain a polynomial representation of G-SSL by using the Taylor expansion as follows:

f = ∞ 0 e -⌧ ∞ t=0 (-1) t ⌧ t R t µ t t! yd ⌧ (4.19) = ∞ t=0 (-1) t µ t t! ∞ 0 ⌧ t e -⌧ d⌧ R t y (4.20) = ∞ t=0 (-1) t µ t t! Γ(t + 1)R t y (4.21) = ∞ t=0 (-1) t µ t R t y (4.22)
We recognize in Eq. (4.19) an alternating sequence that monotonically converges to zero in the case of µ > max . Hence, if f (K) denotes the approximation obtained by truncating the series to K terms, we have that, for µ > max , this representation is guaranteed to satisfy

f -f (K) ≤ 1 µ K+1 R K+1 y. (4.23)
In the case of µ ≤ max , a truncation via Eq. (4. [START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF]) is not longer practical as it corresponds to a divergent sequence. However, we can still obtain a polynomial representation in such regime, although the procedure is more intricate. To clarify, let us give a step back to Eq. (4.18). In it, when ⌧ → ∞, we have that e -⌧ Rµ → 0. Thus, when we try to use a truncated Taylor expansion as an approximating function, the error grows unbounded as ⌧ → ∞ since any alternating and non-monotonically convergent polynomial of fixed degree never goes to 0 at t → ∞, instead they go to either +∞ or -∞. Nonetheless, Taylor's theorem does guarantee that a polynomial of K-terms will be able to approximate a function e -z as long as this is restricted to disc of radius z f centred at z = 0. Thus, this observation says that, on the regime µ < max , with a finite number of terms we can still approximate our label propagation process as long as it is up to a maximal time ⌧ f . Then, for this regime, we consider the following approximation of G-SSL

f (K) = ⌧ f 0 e -⌧ K t=0 (-1) t ⌧ t R t µt! yd ⌧ (4.24) = K t=0 (-1) t µ t t! ⌧ f 0 ⌧ t e -⌧ d⌧ R t y (4.25) = K t=0 (-1) t µ t t! (t + 1,⌧ f )R t y, (4.26)
where (⋅, ⋅) refers to the incomplete gamma function. Clearly, the more time we run our diffusion process, the better the accuracy of our approximation, but at the cost of more terms needed in the polynomial. To address the question of given a number of terms K, what is maximum disc radius z f so that we can approximate e -z f with an error at most ✏,l e tT K (z

) = ∑ K t=0 (-1) k z k k! and R K (z) = e -z -T K (z).
The approximation error is bounded by R K (z) ≤ z K+1 (K + 1)!, thus we can estimate z f by considering the equation, z K+1 (K + 1)! = ✏, and solving it for z. The solution can be derived as follows: CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS 4.3. FAST AND EFFICIENT IMPLEMENTATIONS OF G-SSL ON STATIC GRAPHS function. Then, the ARMA recursion in Eq. (4.28) converges linearly to the following frequency response on the spectrum of R:

h(Λ) = r Λ -p ; subject to p > max (4.29)
Let us start clarifying that the symmetry assumption on R used in Theorem 6 is to ensure that R has real spectrum. Thus, Theorem 6 still holds for our non-symmetric operators R as long as they possess real spectrum. Having made this clarification, we now observe that, by direct analogy with Eq. (4.13), Theorem 6 can be readily used to implement the frequency response of G-SSL by choosing r = µ and p = -µ and, accordingly, = -1 µ and ⇢ = 1. Hence, leading to a recursive implementation of G-SSL given as

p (t) = y + 1 µ Rp (t-1) . (4.30)
However, an issue with Eq. (4.30) is that its stability region, determined by the condition p > max , implies that the recursion only converges if µ > max , which is too penalizing for G-SSL. For this reason, we now revert to a shifting of the domain of R (as done by the Chebyshev method) and show that by doing this transformation, then the stability region of G-SSL can be extended to all µ > 0.

More precisely, let us consider the mapping Λ → max 2 (s + 1),w h e r es ∈ [-1, 1], that shifts the spectrum of the operator R. Then, we shift the filter to this new domain by applying this transformation to the G-SSL transfer function:

h(Λ) = µ Λ + µ = µ ( max 2)(s + 1) + µ = 2µ max s + 1 + (2µ max ) = r s -p = h(s) (4.31)
where r = 2µ max is the new residue, p = -[(2µ max ) + 1] is a new pole, and s refers to the spectrum of the shifted operator S = (2 max )R -I. Now, for these values of p and r we obtain the following ARMA coefficients: = -( max )(2µ + max ) and ⇢ = (2µ)(2µ + max ). Thus, leading to the following ARMA implementation of G-SSL:

p (t) = 2µ 2µ + max y - max 2µ + max Sp (t-1) . (4.32)
To see that this recursion now converges for all µ > 0, we have that the spectrum of S is bounded between [-1,1], leading to the stability constraint: max (2µ + max ) < 1, which holds for all µ > 0. As a result, Eq. (4.32) corresponds to an extension of the power method to the general family of G-SSL algorithms. We detail its distributed implementation in Algorithm 9.

Let us now determine the asymptotic convergence rate of Algorithm 9 and show that, remarkably, using it to compute the standard PageRank algorithm implies faster convergence than the classical power method (see Algorithm 3 from Section 4.2).

Lemma 13. Let arma ⇢, (y) denote the steady state of Eq. (4.32). Then, the output of Algorithm 9 satisfies

arma ⇢, (y) -p (K) ≤ max 2µ + max K S K arma ⇢, (y) -p (0) (4.33)

CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS

• Ranking error: metric that counts the fraction of nodes that do not rank in the same spot in the true G-SSL solution and in the approximation vector. The metric is computed by first sorting the entries from both the true G-SSL solution and the approximation vector, so as to obtain the relative ranking of nodes in the graph, and then by counting the fraction of nodes that rank differently in both vectors. This metric motivates from the observation that G-SSL essentially amounts to compare how one node ranks with respect to the rest, meaning that the output of an approximation algorithm may be far from the ground truth in the `2-norm sense, while still preserving the same relative ranking of nodes, thus constituting a reliable approximation.

• Sweep error: metric that assesses to what extend a partition obtained by doing a sweep on the ground truth G-SSL solution differs from the one obtained by doing a sweep on the approximation vector. For the metric, the similarity between partitions is assessed by MCC.

• Multi-class error: metric that assesses to what extend a classification obtained on a set of ground truth G-SSL solutions (multi-class approach) differs from the classification obtained deciding on approximation vectors output by the algorithms above. For the metric, the similarity between classifications is assessed by MCC.

• Number of iterations (Gauss-Southwell only): strictly speaking, this is not an error metric but it complements the error metrics when the Gauss-Southwell method is employed. This is because, for the Gauss-Southwell, a parameter ✏ is set so that the algorithm stops when r ∞ ≤ ✏. Therefore, it is important to: (i) assess the influence that µ, ✏ and have on the number of iterations taken by the algorithm to finish; and (ii) verify, to what extend, Algorithm 4 and Algorithm 10 vary in their running times as they involve different update equations.

ARMA vs random walks for standard PageRank computation

Experimental setup and goals. In this experiment, we assess the benefits the ARMAbased extensions of the Power iteration and Gauss Southwell (Algorithms 9 and 10, respectively) over their random walk-based counterparts (Algorithm 3 and 4, respectively). As implied by our Lemma 13, for standard PageRank computation, the ARMA-based version of the power method should imply an improvement in convergence rate over the random walk-based approach. Therefore, we aim to quantify if such improvements are significant.

The experimental setup is as follows: we generate data from the planted partition model with parameters C avg = 20, C in = 18, C out = 2, N = 1000. Then, 1% of labelled points is randomly sampled. The ground truth classification function is computed through MATLAB backslash operator and it consists of the PageRank with parameter µ = 0.1(↵ ≈ 0.9). Then, we apply Algorithm 9 (ARMA-based power iteration) and Algorithm 3 (Walk-based power iteration) under the same complexity (K) and report the error in their approximations using the metrics defined above. The whole procedure is repeated for 20 data realizations. In addition, this same procedure is employed to compare Algorithm 10 (ARMA-based Gauss-Southwell) and Algorithm 4 (Walk-based Gauss-Southwell). For these algorithms, the approximation errors are compared under a common input error tolerance ✏.

Results and discussion. As implied by Lemma 13, this figure displays that Algorithm 9 has a faster convergence rate than Algorithm 3. After K = 100 iterations, Algorithm 9 shows improvements of roughly 2 orders of magnitude over Algorithm 3, which translates into an improved ranking of nodes (second plot from left to right). Surprisingly, this faster convergence rate and improved node ranking do not reflect as improvements in the sweep error or the multi-class error. Indeed, the last two figures on the right show that, for small K, a sweep on the random walk-based approximation implies a slightly smaller error over doing a sweep on the ARMA-based approximation. Despite these minor differences, it is important to stress the G-SSL decision rules display robustness to inaccuracies on the classification function as, already from small K values, the sweep error and the multi-class error are small. In this figure, we observe that the ARMA-based Gauss-Southwell method also displays an improvement over the random walk-based version of the algorithm. In this case, the benefits are more evident after ✏ < 10 -3 , as, for this regime, Algorithm 10 terminates in less iterations than Algorithm 4 while attaining less `2-norm error and more accurate rankings. Remarkably, the sweep error is already very small from rather large values of ✏.T h i sm a yb ed u et ot h e simple graph model that we are considering, where there is only one clear partition of small Cheeger ratio, hence it is should be doable for the sweep to find this true partition despite the inaccurate functions. However, the multi-class error displays high values for large values of ✏ and only after ✏ < 10 -3 the true partition is always obtained.

Comparison of methods for L -PageRank and influence of parameters

Experimental setup and goals. In our next experiment, by using L -PageRank as the base method, our goal is to compare the approximation accuracy of Algorithms 7 -10 and to assess the impact that changes in µ and have on these algorithms, so as to determine the best approach to implement our L -PageRank.

The experimental setup is as follows: we replicate the setup of the previous experiment.

To define our ground truth classification functions, we consider L -PageRank for the following parameter combinations: (i) = 1,µ = 5; (ii) = 1,µ = 0.1; (iii) = 5,µ = 5; (iv) = 5,µ = 0.1. We stress that these values have been carefully chosen: for setting (i) we have that µ = 5 > max , thus implying that the Greens function method (Algorithm 8) operates in the region where it is guaranteed to converge; setting (ii) allows us to compare with the previous experiment; setting (iii) allows us to see the impact of increasing (w.r.t. (i)), moreover, = 5 is a common value where the planted partition starts to display a saturation plateau on its Cheeger ratio, hence it is related to the optimal . Lastly, setting (iv) allows to see the impact of either decreasing µ (w.r.t (iii)), or to increase (w.r.t (ii)). Algorithm 9). In the figure array, rows correspond to error metrics and columns correspond to a combination of ( ,µ). It is clear from the figure that the Chebyshev approach outperforms the other methods by several orders of magnitude. Indeed, in every test, the Chebyshev approach is able min-CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS imize the ranking error, sweep error and multi-class error in a maximum of roughly 30 iterations. This remarkable performance seems to be a consequence of its much lower sensitivity to changes in and µ than the other approximation methods. Precisely, let us consider = 1,µ = 5 as a baseline setting, since all methods tend to converge to the true G-SSL solution in only a few iterations for this setting. Then, by increasing (third column), we see that the Greens function method severely decreases performance. Even though the ARMA recursion remains relatively insensitive to changes in ,w h e nt h eµ parameter decreases it drastically worsens performance (second column). On the contrary, the Chebyshev approach cases remains performing remarkably well despite the parameter variations. In this figure, we observe that the Gauss-Southwell, as its based on the ARMA recursion, is also sensitive to variations in ,µ. Namely, as we increase , we increase the number of iterations and the `2 error. Then, if µ is further decreased these quantities increase even more. Interestingly, the figures from the sweep error and multi-class error suggest that the introduction of implies to more quickly converge towards the true partitions.

Results and discussion.

Fast updating of G-SSL on evolving networks

In this section, we address the updating problem for the general G-SSL case. From the experiments of the last section, it may seem that the value of our ARMA-based extensions is limited when they are compared to the Chebyshev approach. However, one critical feature that the ARMA-based algorithms possess that is missing on the Chebyshev method is the possibility to employ warm restarts. Let us show in Figure 4.7 the effect of using a warm restart on the ARMA recursion versus using the Chebyshev method (from scratch) when one node joins the graph. For the plot, we employ one of the planted partition graphs from the experiments in Section 4.3.5 and use L 2 -PageRank with µ = 0.01 as the base G-SSL method. As it can be seen, due to the very accurate initial guess, the ARMA recursion now outperforms the Chebyshev method by several orders of magnitude. Moreover, as we will show in this section, the ARMA-based methods allows to cast the update problem in a local manner, thus permitting sub-linear time algorithms, contrary to the Chebyshev method which, even though it converges extremely fast, remains a global method that needs to see all the graph to operate.

Local G-SSL updating via the power method

In this subsection, we use the ARMA recursion from Eq. (4.32) to extend the local update method of Algorithm 5 to the general family of G-SSL methods. To proceed, let us denote the steady state of Eq. (4.32) for the initial graph G by arma ⇢, (y) and for the evolved graph G by arma ⇢, (y). We assume that the initial condition y and the set of ARMA coefficients ⇢, are the same for both G and G. Thus, we leverage the warm restarts p(0) = arma ⇢, (y) to show the following:

The proof of this Lemma is deferred to Appendix 4.C.

This Lemma generalizes the local update rule of Eq. (4.8) to the general G-SSL setting. Namely, it says that to update the G-SSL solution, then one needs to solve another G-SSL problem, but that this new one is much more efficient to compute since the initial distribution r is local in the perturbation. Hence, by computing arma ⇢, (r) via the power method, we can control the scope of the update according to the number of terms used in the approximation. Namely, if one uses K-terms, then one propagates the update in a K-hop vicinity, leading to a method with cost bounded by O(cKM ) if, at most, there are M edges are contained in the K-hop vicinity of a node that changed, and c changes occur. We detail our proposed local update procedure in Algorithm 11.

We now show that the convergence rate of Algorithm 11 is the same of Algorithm 9 and that the cost of the algorithm is proportional to the update needed. The proof of this Lemma is deferred to Appendix 4.D.

The implications of this lemma are twofold. On the one hand, it points in the same direction as Lemma 12, saying that the norm of the update is bounded by the norm of the perturbation (encoded by 1 ⇢ arma ⇢, (r)). On the other hand, since 1 ⇢ arma ⇢, (r)

Updating via neural networks

In this subsection, we present a novel and promising approach to solve the update problem which consists on using neural networks. The idea we propose to investigate is the following: if we pay the price of computing the true G-SSL solution for some sequence of graphs, can we feed into a neural network the previous G-SSL solution, the perturbation, and the evolved G-SSL solution (from our training set), so that the network can learn the necessary mapping to update the G-SSL solution for future graphs not seen during training?

The Multi-Layer Perceptron

Neural networks are computational models that draw inspiration from biological brain networks. In a neural network, individual processing units, called neurons, receive information from other neurons, process that information, and output information that is used by other neurons to repeat this task. There are several variants of neural networks, but one of the most popular is the multilayer perceptron (MLP). In this model, neurons are organized in layers, and there are always, at least, three of them. The input layer, the hidden layer(s), and the output layer. Neurons from the input layer send information to the ones in the hidden layer, these to the successive hidden layers, until the information reaches the output layer. Each neuron from a layer is connected to each neuron in the next layer and each connection possess a real-valued coefficient reflecting the importance if this connection. Under certain assumptions, this type of models are known to be universal approximators, meaning that they are bound to realize any mapping between vector spaces. Thus, if a mapping from R l to R m is desired, then the input layer must have l neurons and the output layer m neurons. The hidden layers can have distinct number of neurons and their number is a design choice.

If we let the information output from each of the neurons in layer k be encoded by the vector h (k) , the value of the MLP at layer k is described by the equation

h (k) = (W (k) h (k-1) + ✓ (k) ), (4.45)
where (⋅) is a non-linear activation function, W (k) ∈ R j k-1 ,j k ,w i t hj k being the number of neurons in layer k, is a weight matrix encoding the strength of connections between layers k -1 and k, and ✓ (k) is an offset parameter. Popular choices of (⋅) are: (i) sigmoid, (ii) softmax, (iii) tanh, or (iv) ReLU. Each one of them has strengths and drawbacks and their selection is a design choice. For a more thorough discussion on activation functions we refer the reader to [START_REF] Jain | Artificial neural networks: A tutorial[END_REF].

Neural networks are trained to learn. In math terms, training means adjusting the values of the weight matrices within layers so that we fit the transformation for a subset of datapoints for which we know their value in R l and corresponding image in R m . Thus, for the pair (x ∈ R l ,z ∈ R m ), x is fed into the network which outputs h out (the output layer) as an estimate of z. Then, a loss function is employed to assess how much the network fits the training data and consequently adjust the weights of the network. The most common approach to adjust the weights is by means of the back-propagation algorithm. In it, the 96 CHAPTER 4. FAST AND EFFICIENT IMPLEMENTATIONS 4.4. FAST UPDATING OF G-SSL ON EVOLVING NETWORKS weight between neurons i and j is updated according to the rule

w (new) ij = w (old) ij -⇣ @Loss @w ij , (4.46)
where ⇣ is the learning rate. By using the chain rule, Eq. (4.46) can be expressed in terms of the layers between the output layer and w ij and the update 'back-propagated', hence the name.

As mentioned above, MLPs are used to learn mapping between euclidean vector spaces. However, numerous research efforts have been recently made to leverage the power of neural networks to solve graph problems [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Wu | Simplifying graph convolutional networks[END_REF][START_REF] Niepert | Learning convolutional neural networks for graphs[END_REF][START_REF] Li | Gated graph sequence neural networks[END_REF]]. Yet, due to its irregular nature, graph data poses a challenge for neural networks. The traditional approach to adapt neural networks to graph data consists on creating a latent space for the vertices by assigning them a feature vector, thus 'embedding' the graph vertices into an euclidean representation. Moreover, a popular approach consists on using graph convolutional layers, which basically consist on using graph filters in between regular layers of the MLP (see [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] for details) so as to use the graph structure as a guide to perform linear combinations of the euclidean representation of the data.

The MLP for the updating problem

In this work, we consider MLP's for the following problem: let {G t ∶ t = 1, 2,...,t max } denote a sequence of graphs. Let f t = h(G t ,y t ) be a transformation applied on the graph signal y = y 1 = y 2 = ⋅⋅⋅ = y tmax in graph G t . The transformation is the same for all the graphs in the sequence. Now, if the changes between G t and G t+1 are small, then the functions f t and f t+1 should be similar. Thus, the question we address is the following: by training the network with the mapping (updates) f t → f t+1 for all t up to t train ,t h e n , if the changes in the graph follow a pattern, can the network learn the distribution of this pattern so that it can perform the updates for future graph changes f t → f t+1 with t > t train ?

In contradistinction with the Graph Convolutional Network (GCN) architecture from [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], or its simplification [START_REF] Wu | Simplifying graph convolutional networks[END_REF], which rely on the use of convolutional layers to incorporate graph information, in this work we propose to use the pure and simpler MLP (no convolutional layers) to solve this task. The reasons for this choice are: (i) the GCN is more challenging to train than the simpler MLP; (ii) in the GCN, one needs to see the entire graph in between its layers (thus constantly having to load it into memory); and (iii) it appears to be more intricate to encode the information about graph changes in a GCN that in our simpler, yet motivated by our theoretical results from this chapter, model. More precisely, in this chapter, we have seen that when one uses the warm restarts, the ARMA recursions allow to encode the necessary update to be performed by means of projecting a previous G-SSL solution onto the matrix [ R -R],w h i c hi st h e nd i ff u s e d .

Based on this observation, we claim that if we diffuse f t in both G t+1 and G t for up to a given number of steps k, then the resulting diffusion vector in G t+1 will differ from the diffusion vector on G t proportional to the change between G t+1 and G t in a k-hop vicinity from where the diffusion starts. Hence, is a means to encode for the perturbation and the G-SSL solution. In precise terms, we propose to use the following embedding of the graph 4.4. FAST UPDATING OF G-SSL ON EVOLVING NETWORKS vertices into a latent euclidean space (feature vector of 2k + 1e n t r i e s ) :

features of node u = (f t ) u , (Rf t ) u , (R 2 f t ) u , , (R k f t ) u Diffusion on Gt , ( Rf t ) u , ( R2 f t ) u , , ( Rk f t ) u Diffusion on G t+1
Then, we propose to feed this vector into a multi-layer perceptron with 2k + 1 neurons in the input layer (feature vector), 1 neuron in the output layer (updated G-SSL value) and 50 neurons in a hidden layer with ReLU activations. As it can be seen, the feature vector is straightforward to compute in a recursive manner. Moreover, once the features are computed, our model acts individually on nodes, thus it can easily scale to massive graphs as it is highly paralellizable and bound to be trained on any graphic card. Indeed, our model calls for a local (sublinear) extension in which one only computes the feature entries for nodes surrounding the perturbations and then the training is performed on this much smaller subset of data. How to extend the feature vector to effectively code for changes in the graph locally is one of our immediate future research directions.

Numerical experiments

A Python toolbox for evolutionary stochastic block model

To alleviate the challenge of collecting graph evolving data, we contribute with a Python 3 class that allows to easily generate a temporal sequence of graphs from the Stochastic Block Model (SBM). The toolbox can be found in the Github repository: [136] For this toolbox, we developed a class that initially generates a standard SBM realization and then creates the temporal sequence by recursively perturbing this initial graph according to the following user tunable parameters: In addition, our class facilitates G-SSL as any object drawn from the class possess the following attributes: (i) the sequence of graphs; (ii) what is the time index for each graph in the sequence; (i) the corresponding graph matrices (adjacency matrix, degree matrix, transition matrix, shifted operator, etc) for each graph in the sequence; (iii) the exact Pagerank or L -PageRank vector for each graph in the sequence (for an initial user defined distribution y and parameter µ); and (iv) quick access to the cluster membership of each node.

The expected number of nodes joining and leaving are drawn according to a Poisson trial. Moreover, to allow to treat G-SSL in the dynamic setting (which assumes common initial distribution), labelled points cannot leave the graph. Further, when a node adheres to the graph it links to members of its cluster following the SBM class membership probabilities. Concerning the arising edges, these can appear between any pair of nodes just respecting the probability of within class or between class. In addition, new edges can superpose with existing ones, just increasing their weight by one. With respect to G-SSL operators, to satisfy equal ARMA coefficients for the entire graph sequence, we assume an upper bound on max of 10 for the generalized operator R of L -PageRank. Yet, these parameters are easy to adapt for specific settings. Lastly, we stress that our toolbox only uses standard Python libraries (networkx and numpy) so that it can easily be combined with other libraries.

Impact of local updating algorithms

Experimental setup and goals. In this experiment, we aim to assess the benefits given by the local updating algorithms derived in this section.

The experimental setup is as follows: we take the same graph model from the experiments of Section 4. C in (25N ); (f) probability of a link disappearing between classes: C out (25N ).D e s p i t e these low rates, almost 40% of the nodes in the graph are affected between snapshots due to the small-world nature of the planted partition. Moreover, we stress that by making this selection of parameters, the class structure of the SBM is respected. We consider the L 2 -PageRank vector with µ = 0.01 as the base G-SSL method. We highlight that since we have a closed form expression for the elements of degree matrix D 2 of the L 2 -graph, then taking matrix vector products with the L 2 -PageRank operator R = L 2 D -1 2 can be done by re-scaling the input vector by

[D 2 ] uu = [L 2 ] uu = D 2 uu + ∑ v W 2
uv , and then apply the Laplacian matrix twice to such vector. Thus, we compute the exact L 2 -PageRank for each graph realization and use the update algorithms introduced above (Algorithm 11 and Algorithm 12) as a means to update such vectors and predict the L 2 -PageRank vector for the following graph realization. In addition, we apply the Chebyshev approach from scratch in each graph. To assess the benefits of the local update algorithms, we track the approximation accuracy given by these algorithms as a function of the number of basic operations that they have performed and report the mean value over the 20 graph Results and discussion. Figure 4.8 displays the approximation accuracy of the local update algorithms (Algorithm 11 and Algorithm 12) and the Chebyshev method (Algorithm 7) as a function of the number of basic operations they have performed in the task of updating an L 2 -PageRank vector. As it can be seen, when addressing changes in the graph, the local updating approaches developed in this chapter offer a much better solution than the Chebyshev approach. Indeed, due to the small world nature of the SBM, for this graph model the local property is less influential as compared to other graphs. Nonetheless, since the changes are small and the local methods are just a rewriting of the warm restarts, we can still clearly see that these approaches provide significant savings in computational power. For instance, in our experiment, it takes around 10 million operations for the Chebyshev approach to attain a similar amount of error as not performing any update, while the local power method after 10 million operations is close to two orders of magnitude below the no-update error. Moreover, if the graph increases in size, then these differences between the local and the Chebyshev method become more dramatic as the latter remains global and always starts from scratch. Lastly, we note that the Power method tends to perform better than the Gauss-Southwell. This observation is consistent with the observations made in [START_REF] Ohsaka | Efficient pagerank tracking in evolving networks[END_REF], where the power method also leads to better accuracy, although, in such work it was not acknowledge that the power method could also be recasted locally.

Updating a sequence of graphs

Experimental setup and goals In this experiment, we aim to assess the feasibility of using the neural network to update a sequence of graphs.

The experimental setup is as follows: we generate a sequence of 170 graphs with our dynamic SBM python class. From these, the first 20 graphs are used as our training set and the remainder 150 snapshots are used for the test set. The graphs follow simple parameters: p in = 0.5, p out = 0.05, N = 200, the expected number of nodes joining/leaving is 1, the probabilities of edges appearing/disappearing within a class is p in 20 and the probability of nodes appearing/disappearing between classes is p out 20. Then, we train the network to learn both standard PageRank updates and L 2 -PageRank updates with µ = 0.1. Then, we train the network to learn both PageRank updates and L 2 -PageRank updates. For standard PageRank we use R = P as the operator used to compute the features. For L 2 -PageRank the natural choice is R = L 2 D -1

2 . Yet, interestingly, we have experienced that, although not being Markovian, using R = P 2 = D -1 2 W 2 tends to give better results in practice, thus we use this choice for our experiment. In both cases we use features up to k = 3 hops. To train the network, we use the Pytorch model of the MLP via the ADAM optimizer with learning rate equal to 1e-6 for PageRank and 5e-5 for L 2 -PageRank. Since our goal is to overfit the distribution of the updates, then we let the network overfit its training set until an early stop condition of 10 consecutive loss evaluations increasing is met. To stabilize the training, we use a weight decay of 5e-9. For the evaluation set, we split the scores from the 20 graphs constituting the training set into 20 epochs and each epoch is randomly splitted for training and evaluating. Then, as baseline, we compare with the power iteration with warm restarts under the same complexity: i.e., if to compute the features we use k-hops, leading to a vector of 2k-matrix-vector products, then we use power iteration with 2k steps. Lastly, we stress that in both algorithms we use their predictions at time t as the new input for the predictions at time t + 1, meaning that we aim for the the method that accumulates less error.

Results and discussion. Figure 4.9 shows the approximation error attained by the neural network (proposed) versus using analytic updates via the power method with warm restart (analytic) in the problem of updating the G-SSL solution for a sequence of 150 graphs when both approaches are employed under the same complexity. As it can be seen, the network is able to cope better with changes by keeping a smaller error for both PageRank and L -based PageRank as the sequence of graphs progresses. While this example is simple, these results are encouraging and point in the direction that our proposition for feature vector is pertinent. Moreover, they open the door to further investigate our model with more challenging data and network architectures and also cast it in sub-linear complexity.

4.D Proof of Lemma 16

Proof. From Eq. 4, by truncating computation of arma ⇢, (r) to K terms, we have that

p (∞) -p(K) = ∞ t=0 t St r - K t=0 t St r (4.68) = ∞ t=K+1 t St r (4.69) = ∞ i=0 i+K+1 Si+K+1 r (4.70) = K+1 SK+1 ∞ i=0 i Si r (4.71) = K+1 SK+1 1 ⇢ arma ⇢, (r) (4.72) ≤ K+1 SK+1 1 ⇢ arma ⇢, (r) (4.73)
Chapter 5

G-SSL for Internet routing

Introduction

The main goal of G-SSL is to help solve real world problems. Towards this aim, this Chapter uses G-SSL to address current issues in the context of Internet routing under Border Gateway Protocol (BGP).

BGP is the routing protocol that drives the Internet. It makes the exchange of information between entities connected to the Internet to be as efficiently as possible. For example, when a user introduces the address of a site in a web browser, a domain name system (DNS) server retrieves the IP address of the website, and then BGP determines what is the optimal route that the data packets need to go through in order to fetch the website's information from the host IP.

In more precise terms, the Internet is a network of autonomous systems (ASes), where an AS refers to a collection of IP prefixes (groups of IP addresses) that is administrated by a single organization (usually an Internet service provider). In this context, the main goal of BGP is to exchange information between ASes so that they become aware of what sequence of ASes needs to be traversed to reach a target IP prefix. To achieve this, when an AS has a new prefix, the AS advertises the new prefix to its adjacent ASes by means of an update message that is communicated through BGP speakers. This update message is received by the adjacent ASes which append to it their Autonomous System Number (ASN) before retransmitting the message to further adjacent ASes. This process is successively repeated until all ASes have received the message, giving them the information about the sequence of ASes that needs to be followed to reach the aforementioned prefix. Since there may be various paths to reach the prefix, the key feature of BGP is that it discards routes containing loops and only preserves the most efficient path according to some policies agreed between ASes [START_REF] Stewart | BGP4: inter-domain routing in the Internet[END_REF].

BGP has established as a protocol of utmost importance, bringing order to the way in which information travels in the Internet. However, despite its great success, issues affecting it and the Internet traffic controlled by it arise in practice, which, due to the large scale and rapidly evolving nature of the web, are difficult to measure and characterize. Next, we detail two of such issues:

INTRODUCTION

Issue of BGP zombies: when a prefix withdraws from the Internet, the origin AS stops announcing it, expecting that the remainder of ASes become aware that the prefix is unreachable anymore so that they remove it from the their routers' tables. Normally, a large sequence of exchanges between BGP speakers needs to occur before an IP prefix is fully removed. Such long process is because an AS ignores if a route has ceased from being announced due to some malfunction occurring in the path towards the prefix, or because the prefix has been withdrawn at the origin AS. Therefore, in an attempt to maintain connections alive, an AS searches in its routing tables for the best alternative path towards the prefix and communicates this new path to the other ASes. At a next round, the AS realizes that such path is also invalid and searches for another alternative. Only when the AS runs out of alternative paths is when it removes the prefix and transmits the withdrawal of it. Theoretically, this withdrawal process always ends with the prefix being removed from the routing tables of all BGP routers. Yet, in practice, network operators occasionally report issues where routers get stuck in the withdrawal process and maintain routes towards IP prefixes that have been withdrawn by their origin network. This failure, normally refereed to as stuck routes or zombie routes, is relatively unknown outside network operator circles and is not well understood despite it being a source of confusion and a burden to troubleshoot and clean by network operators.

Issue of IP to AS mapping: internet traffic may display, in practice, congestion due to a mismatch between installed capacity and demand [START_REF] Dhamdhere | Inferring persistent interdomain congestion[END_REF], vulnerable nodes to DDoS attacks [START_REF] Kang | Routing bottlenecks in the internet: Causes, exploits, and countermeasures[END_REF], or abnormal traffic changes due to facilities outages [START_REF] Milolidakis | Detecting network disruptions at colocation facilities[END_REF]. These issues are normally visible, and characterizable, from traceroute measurements of the Internet: paths of IP addresses accompanied by transit delay measurements made on data packets that try to reach a host IP. Yet, a limitation for the understanding of these problems and, consequently, for taking action on them, is that such issues normally affect routers lying at the boundaries between ASes (in inter-AS links), implying that the tracerout measurements, which lack information about ASes, do not provide the entire picture to address these issues. Therefore, the design of techniques that allow to infer the AS topology from traceroute measurements is of prime interest. The main difficulty is that, while one can map an IP address to its corresponding IP prefix and then retrieve the publicly registered ASN for that prefix, such procedure fails for inter-AS links. The reason is that a link from the internet always needs to have two IP addresses from the same prefix, which enforces ASes to agree on which IP they will use for their inter-AS links, resulting in one of the ASes having to use an IP from the other AS. Therefore, if we blindly map IP prefixes to ASNs, then routers at the ASes boundaries, which are the ones of interest, can get incorrectly mapped. In the literature, two main techniques exist to address the IP to ASN mapping challenge: [START_REF] Marder | Map-it: Multipass accurate passive inferences from traceroute[END_REF] and [START_REF] Luckie | Bdrmap: Inference of borders between ip networks[END_REF]. The recent proposition of [START_REF] Marder | Pushing the boundaries with bdrmapit: Mapping router ownership at internet scale[END_REF] merges both techniques to enhance accuracy. However, we stress that [START_REF] Marder | Pushing the boundaries with bdrmapit: Mapping router ownership at internet scale[END_REF] is notoriously difficult to use in practice: first, it requires Alias resolution and AS relationships, which are extremely hard to compute and error-prone; second, it assumes that the user has control over multiple remote vantage points spread-out over the Internet. To put into context the cost of such method, the Center for Applied Internet Data Analysis (CAIDA), which currently maintains such project, is restrained to retrieve results from it only every six months due to its high cost. As a result, better solutions must be sought.

In this chapter, we propose to use G-SSL to address the problems listed above. The chapter is divided in two parts: first, Section 5.2 characterizes the scope of zombie outbreaks in BGP using G-SSL, then Section 5.3 shows that G-SSL is an effective tool to identify the AS topology from the network of IP addresses. More precisely, Section 5.2 provides the first characterization of BGP zombies. Our study employs a controlled setting using RIS routing beacons and RIS peers, which permit to track routing tables at numerous ASes for prefixes announced and withdrawn at predetermined intervals. From the RIS measurements, we construct an expertized dataset that we fed into G-SSL to infer the state of ASes not measured by RIS peers. By constructing a validation set from tracerout measurements, we show that the standard PageRank algorithm possesses the sufficient predictive power to solve this inference task in almost exact accuracy, therefore there is no need to revert to L -PageRank. Lastly, we use the inferences given by G-SSL to characterize the scope of zombie outbreaks, with our results showing that these are likely to be of considerable size if they appear in transit networks with large AS hegemony. Section 5.3 shows that L -PageRank is an effective tool to solve the IP to AS mapping challenge. To show it, we perform tracerout measurements and build a graph from them. Then, from publicly available ASNs, we construct labelled datasets with varying degrees of confidence: strict, loose, weighted. We study the advantages/disadvantages of these three types of semi-supervision, which offer a trade-off between amount of annotated examples and how much we can trust them. Our results show that, for the studied dataset, L -PageRank with = 2 can solve this inference task with no errors, contrary to standard PageRank which always miss-classifies data.

5.2 G-SSL to characterize the scope of BGP zombies

Experimental setup

Our goal is to characterize the scope of zombie propagation in a controlled setting. To setup terminology, we refer to a BGP zombie as an active Routing Information Base (RIB) entry for a prefix that has been withdrawn by its origin network, meaning that it is not reachable anymore. By zombie ASes and zombie peers we refer to ASes and BGP peers, respectively, whose routers have BGP zombies. We refer to all zombies that correspond to a same prefix and appear during the same two-hour time window as a zombie outbreak.

The outbreak size is the number of zombie ASes in an outbreak.

To observe BGP zombies one must withdraw an IP prefix from its origin AS and assess whether or not it has been withdrawn from the routing tables of other ASes. To characterize zombie emergence, we use a controlled environment via RIPE's Routing Information Service (RIS) BGP beacons [START_REF] Mao | Bgp beacons[END_REF] and BGP data repository [145]. RIS BGP beacons are specifically designed to study Internet inter-domain routing. They consist of a set of IP prefixes (IPv4 and IPv6) that are announced and withdrawn at predetermined time intervals. More precisely, they are announced every day at 00:00, 04:00, 08:00, 12:00, 16:00, and 20:00 UTC and withdrawn two-hours after their announcement at 02:00, 06:00, 10:00, 14:00, 18:00, and 22:00 UTC, respectively. For this study, we employ 27 beacon prefixes (13 IPv4 and 14 IPv6) announced from Europe, U.S.A, Russia, Japan, and Brazil. In addition to beacons, RIS provides data collectors which archive the RIBs and BGP update messages from numerous ASes peering with Internet eXchange Points (IXP). By using the archives from the RIS collectors, the appearance of BGP zombies can be tracked CHAPTER 5. G-SSL FOR INTERNET ROUTING Table 5.1: Measurement periods and number of detected outbreaks for the 27 monitored beacons.

G-SSL to identify zombies

From the RIS collectors, one can only detect zombies appearing in ASes peering with the RIS. In this subsection, we show that G-SSL can accurately infer zombies for the remainder of ASes.

Towards this goal, we retrieve, for each outbreak, the AS path of zombie entries and the last valid path for peers that have correctly withdrawn the beacon. Then, we construct a graph in which the ASes represent nodes and consecutive ASes in the AS paths get connected by an edge. Figure 5.1 illustrates the resulting graph for an outbreak occurring for beacon 84.205.71.0/24 on September 9th 2017 between 22:00 and 00:00. The green nodes represent RIS peers that have correctly withdrawn the prefix at 22:00. The red nodes represent zombie peers observed from 22:00 to 00:00. The grey nodes represent ASes that are not peering with RIS collectors, hence no observations are available for these ASes, albeit they appear in the collected AS paths.

As it can be seen from Figure 5.1, the RIS measurements do not reveal if the grey nodes are part of the zombie outbreak or not. Therefore, G-SSL arises as a tool that is tailormade to infer the state of such ASes. For this reason, we propose to employ G-SSL with the result from the RIS collectors as the expertized data: i.e., ASes that correctly withdraw the beacon (green nodes) constitute the annotated examples of one class, and the observed zombies (red nodes) constitute the annotated examples of a second class. To perform the inferences, we use as G-SSL method the standard PageRank algorithm ( = 1) in the multi-class setting (as it will be shown in our evaluation below, there is no need to increase the complexity of the task by including the extra degree of freedom ,s i n c e standard PageRank solves this inference task with almost exact precision). In addition, to systematically detect the scope of each zombie outbreak, we automatically tune the regularization parameter of G-SSL, µ, by means of a leave-one-out cross validation procedure: from the set of documented vertices, one element, per class, is selected as a labeled As mentioned in the Introduction, the main challenge in inferring ASes from the network if IP addresses is that, albeit one can recover the publicly available ASN for the prefixes conforming the network, such IP to ASN mapping is misleading for routers at the boundaries of ASes. Yet, such mapping remains correct for intra-AS routers and for some of the routers at the boundaries. Therefore, we propose to use this information as the expertized data for G-SSL, which we then employ to estimate the true AS for all the nodes in the graph. The possibility to retrieve the public ASN for IP prefixes gives us the flexibility to construct labelled datasets with the following varying degrees of confidence:

• Strict expert: a node is labelled to belong to AS X if all of its neighbors are mapped to AS X via the IP prefix to ASN mapping. As a result, only intra-AS nodes get labelled, but we can be confident that the AS assigned to the annotated examples is the correct one.

• Loose expert: all nodes are labelled via the IP prefix to ASN mapping. This implies that some of our labelled examples are incorrect (for some nodes at the boundaries of ASes).

• Weighted expert: a node is labelled with the ASes obtained for its own IP and the ASes for the IPs of its neighboring nodes. Therefore, a node may have multiple labels if its own IP prefix to ASN mapping is different from the IP prefix to ASN mapping of its neighbors. If a labelled point normally has a unit weight in G-SSL, then the weighted expert divides the unit weight into the multiple labels it assigns to a node.

In this work, we assess the advantages/drawbacks that each of type of semi-supervision brings when solving the task. Figure 5.5 displays the graph arising from our traceroute measurements and the annotations given by the experts to vertices. To easy identification and reference to the graph, we refer to nodes in the graph by means of an ID written in blue. Green, magenta and brown colored text encode annotations by experts and the true AS of nodes. Green and magenta, together, coincide with the true AS of nodes. Green alone constitutes the annotations given the strict expert and magenta stands for the nodes not annotated by the strict expert. The loose expert tags all nodes, albeit some are incorrect. In this context, green and brown, together, constitute the annotations given by loose expert. Notice that brown tags are sometimes incorrect (this can be seen by comparing them with magenta). The annotations given by the weighted expert are difficult to represent in the figure, they will be made precise below.

For the experiments, we compare the standard PageRank algorithm and L -PageRank with = 2. Let us highlight that this task is tailor-made to be addressed with the topology arising from L 2 . The nodes that we aim to accurately classify lie at the boundaries of ASes. These nodes always have the same class of their 1-hop intra-AS neighbours (nodes for which we know their true AS label) and always have a different class of nodes that lie at 2-hop distance from them, which correspond to the intra-AS nodes of the other ASes (nodes for which we also know their true AS label). Therefore, if we use the L

Results and discussion

Classification using strict experts

In Table 5.3, we report the classification given by PageRank and L -PageRank ( = 2) in the estimation of the ASes from the IP network displayed in Figure 5.5 when the labelled data is given by the strict expert. The table reports the best classification attained by each method for a grid of µ values. Green cells refer to correct inferences and red cells to incorrect inferences. Cells having n.a. indicate that the node is not assigned to any class by G-SSL. Cells having more than one AS tag indicate the node was assigned to more than one class by G-SSL. unclassified, leaving open the possibility that another class whose label was not collected exists. On the contrary, doing sweeps on the standard PageRank method ( = 1) leads to various errors. First, it retrieves some classes with numerous incorrect ASes, leading to 58% of nodes to be assigned into more than one class. One of such multiple classes is always the correct one, yet, in practice, there is no way to remove the ambiguity arising from two classes being assigned to a node, thus counting as a miss-classification. In addition, standard PageRank is not able to realize that nodes with IDs: 8,9,22 all belong to a missing class (AS4), incorrectly assigning them to class AS1.

To have a better grasp on why standard PageRank is prone to miss-classify the data and why L -PageRank delivers such reliable inferences, let us show next the sorting of nodes attained by the classification functions (degree-normalized PageRank vectors) of both methods when they are computed using the labelled points of AS1:

Sorting by standard PageRank ( = 1):

q = [12, 11 , 16, 10, AS1 9, 22, 8, AS4 7, 15, 6, 14, 17, 23, 26, 27, 28, 29, 25, 18, 20, 19, 21, 24, 5, AS3 13, 4, 3, 2, 1 AS2 ]
Sorting by L -PageRank ( = 2):

q = [

]

Please recall that this sorting step is key in the sweep-cut partitioning procedure (see Algorithm 1 in Section 2.3, page 36): the first element in the listing defines a set, the first and second elements define a second set, this is done successively until N sets are collected, and upon which Cheeger ratios are computed and the set one with smallest is returned as the G-SSL classification. Thus, we can see that standard PageRank retrieves a classification function that accurately places the nodes belonging to AS1 at the begining, but just right next to them it places the nodes of AS4. If we observe in detail the graph from Figure 5.5, we can see that, while nodes of AS1 (IDs: 12,11,16,10) define a cluster with small Cheeger ratio, the nodes of AS1 together with those of AS4 (IDs:8,9,22) define an even better cluster that is more balanced and has a smaller Cheeger ratio. Hence, the sweep retrieves AS1 ∪ AS4 as a partition, which results in the the miss-classification of the nodes of AS4. On the other hand, if we look at the sorting given by L -Pagerank with = 2, we note the nodes of AS1 are placed correctly at the beginning, then, next to AS1, we see the nodes of AS3, and the nodes of AS4 have now been deferred to the tail of the sorting. Therefore, the partition AS1 ∪ AS4 is no longer among the possible partitions. Indeed, when we consider any mixture of AS1 with the nodes of AS3, such sets never define a cluster of small Cheeger ratio. The only possible set of small Cheeger ratio in the search space is AS4, hence it is accurately retrieved. Clearly, the effect of placing AS4 at the tail of the sorting is due to the emergence of negative edges between the nodes Now, let us focus on the performance obtained by classifying the data using the multi-class approach. Table 5.3 shows that both standard PageRank and L -PageRank accurately classify all nodes of AS1, AS2 and AS3, but they miss-classify the nodes of AS4. As discussed above, one of the drawbacks of the multi-class approach is that it always assigns a class to nodes, forcing us to collect annotated examples of all classes to avoid entire classes from being miss-classified, which, in this example, is what happens with the nodes of AS4.

For a more fair and complete comparison, we display in Figure 5.6 the performance accuracy of classifications given by the sweep-cuts (individually, for each class) as a function of the G-SSL regularization parameter µ. Figure 5.9a, does the same for the multi-class classification. From these figures, we observe that the standard PageRank algorithm is, in general, not very sensitive to changes in µ. On the other hand, = 2 displays more sensitivity to variations in µ, implying that efforts must be employed for its optimal selection. Despite the need for its tuning, the figure indicates that L -PageRank has a superior performance for a not so narrow regime of µ values.

Classification using loose experts

Table 5.4 reports the classification obtained by standard PageRank and L -PageRank ( = 2) in the estimation of the ASes from the IP network displayed in Figure 5.5 when the labelled data is given by the loose expert. The table reports the best classification attained by each method for a grid of µ values. Green cells refer to correct inferences and red cells to incorrect inferences. Cells having more than one AS tag indicate that the node was assigned to more than one class by G-SSL.

The table indicates that the introduction of the additional (non-necessarily reliable) labelled points, which make expertized data for AS4 available, allows L -PageRank, in the multi-class setting, to achieve a perfect a classification result, and, in the sweep-cut setting, to only fail in the assignment of one single node. Indeed, it can be seen that the sole node for which the sweep-cut fails (ID: 10) is due to it being incorrectly annotated by the loose expert. Nevertheless, it is remarkable that the multi-class approach profits from the loose experts and is able to relabel all the nodes incorrectly labelled into their correct class. Concerning the standard PageRank algorithm, we can see that it does not really takes advantage from the loose experts. On the one hand side, the two nodes incorrectly labelled by the expert (ID: 8,10) are the ones where PageRank fails (multi-class approach), hence lacks the ability that L -PageRank has of to relabeling data into their correct class.

On the other hand, we see that the loose expert worsens, with respect to the strict expert, the classification via sweep-cuts as we see an increment of nodes assigned into more than one class from 58% to 82%.

Lastly, we display in Figure 5.7 the accuracy of classifications given by the sweep-cuts (individually, for each class) as a function of the G-SSL regularization parameter µ.I n Figure 5.9b, we display the same for the multi-class classification approach. These figures still verify that the standard PageRank algorithm tends to not display changes in its performance with changes in µ. In the case of = 2, it can be seen that for the sweep on the labels of AS4, more care needs to be taken in the tuning of µ with respect to other ASes. On the multi-class setting, = 2 attains perfect accuracy but the regime of µ values that Classification using weighted experts Table 5.5 reports the classification obtained by standard PageRank and L -PageRank ( = 2) in the estimation of the ASes from the IP network displayed in Figure 5.5 when the labelled data is given by the weighted expert. The table reports the annotations given by the weighted expert and the weight assigned to each labelled example. The table reports the best classification attained by each method for a grid of µ values. Green cells refer to correct inferences and red cells to incorrect inferences. Cells having more than one AS tag indicate that the node was assigned to more than one class by G-SSL.

The table indicates that L -PageRank ( = 2) still outperforms standard PageRank, yet the weighted expert does not permit L -PageRank to attain predictions without errors. Indeed, the weighted expert worsens the performance of L -PageRank with respect to the loose expert. For instance, the classification via sweep-cuts now increases the number of nodes assigned to more than one class. We note that such miss-classifications arise from the sweep for AS4, which detects all the nodes from AS1 as being of class AS4. The error is due to unreliable annotated examples of AS4, in which the weighted expert incorrectly says that 3 out of the 4 nodes belonging to AS1 are of class AS4. This illustrates the limits of G-SSL to errors in annotated data. It is remarkable that L -PageRank, in the multi-class approach, is able to override most of the incorrectly labelled points by just failing to accurately detect the AS of one node (ID: 10). Standard PageRank displays no difference between the loose expert and the weighted expert. The number of nodes assigned to more than one class via sweeps-cuts remains in 58%, and the multi-class approach still miss-classifies the same two vertices (IDs: 8,10).

The accuracy of classifications given by the sweep-cuts (individually, for each class) as a function of the G-SSL regularization parameter µ is shown in Chapter 6

Conclusions Summary

In this thesis we started with the aim of addressing some of the limitations of G-SSL, which tends to only be reliable under simple data settings. Towards this aim, in Chapter 1, we recalled essential results from graph theory, random walk theory and graph signal processing. Special emphasis was given to the diffusion aspect of random walkers and the heat equation. Moreover, graph signals were introduced and motivations for the different definitions of Laplacian matrices were given along with their implications on the definition and impact on the graph Fourier transform. It was also highlighted that these results permit to extend the concept of filter from signal processing to graph signals.

In chapter 2, we gave a thorough review of the field of G-SSL that we believe was missing.

In the first part, we covered the traditional approach to G-SSL as a Tikhonov regularization problem. We reviewed the different structural forcing proposed in the literature and discussed their motivations and relationships. From the reviewed methods, it was argued that the PageRank algorithm is the most performing proposition, yet it suffers from biased outputs when the labelled data is unbalanced. We covered works showing that G-SSL suffers from the curse of dimensionality issue when the unlabelled data grows infinitely large.

We introduced results indicating that the source of the issue is the Laplacian kernel and we gave special emphasis to the solution based on Laplacian iterations as it was a source of motivation for this work. In the second part of Chapter 2, we pointed that G-SSL can also be addressed from the perspective of graph partitioning. We introduced graph-cut problems and stressed that they are unfeasible to solve exactly, but that can be relaxed by G-SSL. Then, we revisited and re-interpreted results originally developed in the context of local graph clustering to show that the PageRank method, in the G-SSL framework, can also be used to confine diffusion processes and reveal clusters in the graph. Then, it was stressed that the so-called sweep-cut technique complements those results and impacts G-SSL overriding the need to collect balanced labelled points for all classes by allowing to find them individually.

Chapter 3 proposed our main contribution: the L -PageRank G-SSL method, an extension of PageRank based on (non-necessarily integers) powers of the (combinatorial) Laplacian matrix. The analysis given in the Chapter shows that the added degree of freedom offers more versatility than standard PageRank, providing the potential to address some of the limitations of G-SSL. Precisely, we showed that when clusters are obtained via the sweep-cut procedure, L -PageRank can significantly outperform standard PageRank. Furthermore, we showed that the multi-class approach also benefits from our proposition, as our method significantly overrides the issue of unbalanced labelled data. These improvements were possible due to a novel interpretation we did of the L operator, in which we showed that for each value of , it gives rise to new graphs with the potential to improve G-SSL. We showed that two regimes of new graphs appear: (i) < 1i nw h i c h graphs of positive edges are created and (ii) > 1 that leads to signed graphs. Concerning the regime < 1, we showed that our L -PageRank corresponds to an extension of the regular PageRank algorithm to Lévy processes, in which random walkers are given the ability to perform long-distant jumps in a single step. We showed by means of numerical experimentation that the Lévy flights can improve the classification functions when the data presents complex local structures. Concerning the regime of > 1, we showed that the richness of such graphs comes from the sign of edges, allowing to code for similarities but also to emphasize dissemblance between nodes in the graph. Thus, while 2 nodes can only be disconnected on the initial graph, they can 'repulse' themselves in these topologies. Notably, we have shown that there is an optimal graph (related to an optimal ) on which the classification will lead to a maximal performance. We proposed a simple yet efficient algorithm to estimate the optimal and hence determine the best topology for analyzing a given dataset.

Chapter 4 investigated fast and efficient implementations that avoid the costly matrix inversion demanded by G-SSL methods. We contributed with an extension of the successful algorithms of power iteration and Gauss-Southwel, state-of-the-art methods for fast PageRank computation, to L -PageRank. Moreover, we extended the dynamic versions of such algorithms to L -PageRank, allowing us to update the solution of L -PageRank when facing evolving graph structures at a much smaller cost than re-computing the solution from scratch every time the graph changes. These extensions were possible because L -PageRank was shown to be a low pass graph signal filter, for which the field of Graph Sinal Processing had proposed efficient implementations via ARMA recursions and Chebyshev polynomials. We elaborated on the ARMA recursions to extend the aforementioned algorithms. Our assessment showed that, while the Chebyshev polynomials remain the most effective approach to compute the solution of L -PageRank from scratch, they do not have the key feature of the ARMA-based algorithms: the warm restart, which proves instrumental to accelerate the computation of L -PageRank by several orders of magnitude when the graph evolves. In addition, we explored the feasibility of using neural networks to solve the update problem. We addressed the question that if we show a sequence of graphs with their exact G-SSL solutions to a neural network, then can this learn the mapping to update the G-SSL solution when the graph evolves? We proposed a procedure to encode for graph changes as features living on the graph vertices that are later used to train a Multi-Layer Perception. Our preliminary results indicate that the neural network bears the potential to effectively update the solution of G-SSL as it was able to outperform the analytic ARMA expression for an equal computational complexity.

Chapter 5 used G-SSL to address current issues in Internet routing. We used G-SSL to provide the first characterization of BGP zombies. Then, we used G-SSL to solve the IP to AS mapping challenge. For our characterization of zombies, our study spans for over a year and a half of data collected in a controlled setting via RIS beacons and RIS 124 CHAPTER 6. CONCLUSIONS collectors. From RIS collectors we tracked zombie outbreaks and constructed a set of annotated examples that were fed into G-SSL to predict the scope of outbreaks beyond RIS peers. G-SSL (std. PageRank) inferred zombie ASes with 97% accuracy and normal ASes with 99% accuracy according to a validation dataset build from tracerout measurements. G-SSL inferences were used to then characterize the scope of zombie outbreaks. Results indicate that oubreaks affect, on average, 10% (IPv4) and 17% (IPv6) of the total ASes in our dataset. Moreover, we found that the scope of outbreaks is related to the importance of transit networks affected. Then, we used L -PageRank to solve the IP to AS mapping challenge. We built a graph from tracerout measruements and constructed labelled datasets using the publicly available ASNs with varying degrees of reliability. We showed that standard PageRank always miss-classified data, while L -PageRank ( = 2) can solve the task without errors. We showed that a strict expert may be very reliable but may not collect annotated examples from all classes. In such cases, we showed that sweep-cuts offer the best solution to classify data, allowing to leave unclassified nodes whose label was not collected. Then, we showed that when the expert is unreliable, classifying data in the multi-class setting can override incorrect labelled points, while sweep-cuts are likely to assign nodes to more than one class.

Future research

The procedures proposed in this work open various research directions. The first of them would be the extension of other standard clustering tools, such as Unsupervised Learning via Spectral Clustering, to exploit the richer L topologies proposed in this work. Indeed, the potential attained by the L -graphs to be applied in other contexts calls for a more in-depth study on what determines their optimal topology. We gave initial results indicating why = 2, which creates negative edges between two-hop distant nodes, normally constitutes a reliable topology, yet larger values minimize the Cheeger ratio even more before it starts increasing. This lack of insights on what topological properties determine the optimal opens a research direction. In the same line of the optimal topology, improvements over our algorithm for the optimal estimation of should also be sought. For instance, our algorithm has to find a set via random walks with an empirically chosen threshold of 0.7, which is far from being optimal. In addition, we recall that the notion of optimal remains valid only for the sweep-cut partition technique and that insights on what determines the optimal for the multi-class approach are missing. Another calling research direction is the interplay between and in the generalized optimization framework. It may be interesting to see if such framework can lead to novel partition algorithms that find clusters with other metrics more significant than the Cheeger ratio. Still, on the parameter side, we stress that G-SSL also depends on the selection of the µ parameter for which we lack insights on how to optimally tune. It may be interesting to see if one can address the optimal µ tuning from the results on the sweep-cut, suggesting that one may chose the best µ as the one that leads to the sharpest drop in the sorted scores. In a different direction, we showed that G-SSL as a diffusion process is driven by a Helmholtz PDE equation. Therefore, it is calling to explore if other diffusion processes driven by other master equations can be more meaningful for certain applications. Indeed, still on the diffusion side, it is an open problem to see if the L -PageRank, for the regime > 1, can be given an interpretation as random walkers operating on signed graphs. Lastly, we recall that a fundamental open problem in G-SSL is the relationship between the other G-SSL propositions covered in this thesis with the graph topology and if the sweeps can CHAPTER 6. CONCLUSIONS be reliably extended to them.

From the algorithmic side, we have left various open problems that call for immediate further research. The principal is the efficient computation of the L -graphs. The fact that L -PageRank requires to re normalize by the generalized degree matrix D implies that one needs to estimate the latter via recursive matrix-matrix products. We showed that = 2 overrides this issue because it has a closed form expression consisting on information only from the one-hop vicinity of nodes, however, for larger powers one needs information from far-distant nodes. One possible way to amend the issue can be to find closed form expressions for D ( ∈ Z) and then design distributed techniques so that each node collects the necessary information to compute D . Indeed, another concern is that we are not aware of any way to estimate the L -graphs for fractional powers without relying on eigendecompositions. This challenges pave the way to explore other approaches beyond the closed form solutions to compute G-SSL. At the end, G-SSL is just a function on the graph vertices that is estimated from the labelled points according to some optimization problem, thus it may be worth exploring other approaches to reach such function, such as neural networks. Concerning neural networks, we have proposed one to solve the update problem and, while the idea is delivering promising results, it still operates at the entire graph level. Thus, it calls for a local extension that allows to obtain sublinear complexity in order to be competitive with the ARMA-based updating algorithms. Indeed, it would be of utmost importance to find a way to recast the Chebyshev method in a way that it can use warm restarts due to its high efficiency.

Concerning our characerization of BGP zombies, the immediate work to perform is to verify how much our results are reminiscent of what occurs in wild. It is important to assess if detection of zombies in the wild demands to go beyond the standard PageRank algorithm. In such case, L -PageRank arises as a natural method to consider. With respect to the IP to AS mapping problem, the immediate research direction is to extrapolate our experiments to a larger dataset as we only provided a proof of concept in a small of graph of 29 IP addresses. Larger datasets may better reveal differences/advantages of the various experts and may better expose the limits of using = 2( w h i c hw es t u c kt o it due to its easy interpretation and excellent results in our dataset). In such case, we must consider other values and also assess the relevance our algorithm for the automatic estimation of the optimal in such real world scenario.

3. 1

 1 Evaluation of Algorithm 2 on the MNIST Dataset . . . . . . . . . . . . . . . 3.2 Performance of L -PageRank real world datasets . . . . . . . . . . . . . . . . 3.3 Performance of L -PageRank on unbalanced labelled data . . . . . . . . . . 3.4 Comparison of L -PageRank and Iterated PageRank on the MNIST dataset 3.5 Performance of L -Normalized Laplacian on real world datasets . . . . . . . 4.1 Possible choices for reference operators in G-SSL. . . . . . . . . . . . . . . . 5.1 Measurement periods and number of detected outbreaks for the 27 monitored beacons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Top 5 affected transit ASes in IPv4 and IPv6. . . . . . . . . . . . . . . . . . 5.3 Best classification attained by G-SSL using labels of the strict expert for IP to AS mapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Best classification attained by G-SSL using labels of the loose expert for IP to AS mapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Best classification attained by G-SSL using labels of the weighted expert for IP to AS mapping. . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Within cluster agreements of set S in L -graph A ( ) out (S) Between cluster agreements of set S in L -graph D ( ) in (S) Within cluster disagreements of set S in L -graph D ( ) out (S) Between cluster disagreements of set S in L -graph vol (S) Volume of set S in L -graph ⇡ Stationary distribution in L -graph G Evolved graph R Reference operator of G-SSL XV SYMBOLS pr ↵ (y) Personalized Pagerank vector with parameter ↵ and seed y pr ↵ (y)

INTRODUCTION

Figure 1 :

 1 Figure 1: Illustration of the G-SSL classification process

Definition 4 .

 4 denote a path of k -1 edges between u and v. The shortest path distance is defined as follows: The shortest path between u, v ∈ V, denoted by ∆ uv , is the path between u and v with the minimum number of edges.

4 .

 4 GRAPH SIGNAL PROCESSINGLet f 0 denote an initial heat distribution. Then, it is easy to see that the solution to Eq. (1.31) is given as f = e -tL f 0 (1.32)

  graph-based unsupervised learning (d) graph-based semi-supervised learning

Figure 2 . 1 :

 21 Figure 2.1: The need for graph-based semi-supervised learning.

2. 2 .

 2 FROM TIKHONOV REGULARIZATION TO G-SSL (a) Mean (b) Variance

Figure 2 . 2 :

 22 Figure 2.2: Interpretation of f T L m f as the m-th raw moment of the energy spectral density of f .

32 CHAPTER 2 .

 2 GRAPH-BASED SEMI-SUPERVISED LEARNING 2.2. FROM TIKHONOV REGULARIZATION TO G-SSL (a) Normalized Laplacian (b) Iterated Normalized Laplacian (c) Re-centered kernel

Figure 2 . 3 :

 23 Figure 2.3: Illustration of the curse of dimensionality issue in G-SSL and proposed solutions. The horizontal axis represents the spacial dimension of the data and the vertical axis represents the function value learned by G-SSL

  (a) Planted Partition Cavg = 8 (b) Planted Partition Cavg = 3 (c) MNIST 3vs8 (d) MNIST 3vs8 with noise

Figure 2 . 5 :

 25 Figure 2.5: Comparing sweeps on the Fiedler vector (unsupervised) and the PageRank vector (semi-supervised) on both the Planted Partition and digits 3vs8 from the MNIST dataset.

Figure 3 . 1 :

 31 Figure 3.1: Mean transition probabilities arising in the matrix P = D -1 W as a function of the initial geodesic distance between nodes. We recall that [P 1 ] uv = 0i f∆ uv > 1.

3. 4

 4 Analysis of γ < 1: Lévy flights for classification 3.4.1 Lévy flight driven PageRank Let us note that our L -PageRank solution in Eq. (3.6) corresponds to the regular PageRank expression but in which the initial graph has been replaced by one of the L -topologies.

Figure 3 . 4 :

 34 Figure 3.4: Classification with = 1 in balanced setting (w l = w r = 1). For all ↵, standard PageRank correctly partitions the graph between nodes (6) and[START_REF] Hu | Semi-supervised tensor-based graph embedding learning and its application to visual discriminant tracking[END_REF].

Figure 3 . 5 :

 35 Figure 3.5: Classification with = 1i nas k e w e ds e t t i n g( w l = 10, w r = 1). Due to walkers getting trapped in the hub, nodes (5) and (6) are now always incorrectly assigned.

Figure 3 . 6 :Figure 3 . 7 :

 3637 Figure 3.6: Classification with = 0.1i nas k e w e ds e t t i n g( w l = 10, w r = 1). The Lévy walkers escape the hub more often, correctly assigning node (5). Yet, node (6) is still not enough visited, getting incorrectly assigned.

  3 .W es e tS 1 = S 2 = 0.5 × S 3 = 150. The mean degrees are set as C 33 = 7.6, C 23 = C 13 = 0.4, C 11 = C 22 = 7.3, and C 12 = C 21 = 0.3 (leading to p 12 = p 21 = 0.002 which is bigger than p 13 = p 23 = 0.0013). This way, the mean degree of nodes in S gt are equal to the mean degrees of nodes in S 3 . Moreover, we grant that, despite various clusters arising, V = S gt ∪ S 3 is the optimal partition (the one with smallest Cheeger ratio). An adjacency matrix drawn from this model is shown in Figure3.8a. On the other hand, we consider a K-NN graph drawn from a mixture of gaussians. We first generate 300 data points from a mixture of three Gaussians in R 2 ,w h e r eµ 1 = [0, 0], µ 2 = [-2, 2], µ 3 = [-2, -2] and 1 = 2 = 3 = 0.3. Secondly, we generate a single more spreaded gaussian of 300 points with µ 4 = [4, 0] and 4 = [1.5]. Then, we build a graph from this data using K = 30 and = 2. Due to the closeness in space and the balance of the cut, we consider the three smaller gaussians as S gt . The resulting graph from one realization of data is displayed in Figure3.8b. Then, to classify the data, one labelled point is sampled at random from S gt and the L -PageRank method (via sweep) is applied for different values of the ↵ parameter lying on a discrete grid covering the range ↵ ∈ [0.01, 0.99].T h e procedure is repeated for 50 data realizations on both datasets. Performance is assessed in terms of the Matthews Correlation Coefficient (MCC), which we recall that a value of 1 implies perfect agreement with the true partition and 0 a random decision.

∑

  u∈S ∑ v∈S c [W ] uv min (vol (S),vol (S c )) . (3.8) Please note that this generalization of the Cheeger ratio is mathematically sound: (i) first, it is a non-negative quantity since ∑ u∈S ∑ v∈S c [W ] uv = T S L S ≥ 0; and (ii) the set S attaining the minimum value coincides with a sensible clustering. To show the latter, let us split the edges in W according to their sign as W = W + + W -. Now, let us consider the following definitions: • Let A ( ) in (S) = ∑ u∈S ∑ w∈S W + uw be the sum of agreements within S • Let A ( ) out (S) = ∑ u∈S ∑ v∈S c W + uv be the agreements between S and S c • Let D ( ) in (S) = ∑ u∈S ∑ w∈S W -uw be the disagreements within S • Let D ( ) out (S) = ∑ u∈S ∑ v∈S c W -uv the disagreements between S and S c Then, we state the following lemma. Lemma 7. Let S * = arg min S h ( ) S ∀S s.t. vol (S) ≤ vol (G)2. Then, S * is the set that attains the best balance of: • Maximal D ( ) out (S * ) and A ( ) in (S * ); • Minimal D ( ) in (S * ) and A ( ) out (S * ). The proof of this Lemma is deferred to Appendix 3.B.

3. 5 .

 5 ANALYSIS OF > 1: SIGNED GRAPHS FOR CLASSIFICATION Lemma 8. Let > 0.T h e L -PageRank solution in Eq. (3.6) satisfies the following properties:

.11) 54 CHAPTER 3 .

 543 L -PAGERANK FOR SEMI-SUPERVISED LEARNING 3.5. ANALYSIS OF > 1: SIGNED GRAPHS FOR CLASSIFICATION Thus, the generalized Cheeger ratio of S j is small if A ( )

Theorem 5 .

 5 Consider a Planted Partition model of parameters (p in , p out ) and cluster sizes S gt = S c gt = n. Then, as n → ∞ we have that E h

( 1 )

 1 Sgt , with equality occurring in the case p in = p out . The proof of this Corollary is deferred to the Appendix 3.G Theorem 5 and Corollary 1 open the door to investigate, on arbitrary graphs, in which cases the L 2 -graph improves the generalized Cheeger ratio of a set. In the next Proposition, we provide a sufficient condition in which the L 2 -graph improves the generalized Cheeger ratio a set. CHAPTER 3. L -PAGERANK FOR SEMI-SUPERVISED LEARNING Proposition 2. Let D Sgt denote the mean degree of S gt . A sufficient condition on S gt so that h (2)

Figure 3 . 10 :

 310 Figure 3.10: Generalized Cheeger ratio of S gt as a function of . Percentages in (b) represent a fraction of nodes randomly chosen from S gt and removed from S gt . For the plot, S gt is a digit of the MNIST dataset

Figure 3 .

 3 11 displays the performance of L -PageRank at recovering the Planted Partition as a function of the ratio C out C in . As it can be seen, standard PageRank ( = 1) performs poorly when the configuration approaches the phase transition (referred by the vertical line) since h

  the better the L -PageRank recovers the true partition (left plot). It is important to remark that, for this experiment, while = 2 shows good improvements, larger values of keep improving h ( ) S , until it reaches a saturation plateau, designating a region of optimal values ( ≥ 6).

Figure 3 . 11 :

 311 Figure 3.11: Improved detection of the Planted Partition.

Figure 3 . 12 :

 312 Figure 3.12: Classification performance as we vary the internal structure of S gt through the ratio C 12 C 11 while keeping constant the Cheeger ratio of S gt .

2 .

 2 It is unclear if Iterated PageRank can be related to the equilibrium state of a diffusion process 3. It is unclear if Iterated PageRank can be related to the graph topology 4. There are not guarantees that doing a sweep on the Iterated PageRank still leads to a meaningful clustering 5. Iterated PageRank is not defined in the regime of fractional powers. 6. There are no insights on how to optimally tune m for the Iterated PageRank 7. L -PageRank cannot be related to a Sobolev norm regularization 3.6.1 Numerical comparison Performance on real world data Experimental setup and goals. In this experiment, we aim to compare the performance between both L -PageRank and Iterated PageRank when classifying the MNIST.

Figure 3 .

 3 13 displays the classification functions of L -PageRank and the Iterated PageRank when applied on data that suffers from the curse of flatness. Since Iterated PageRank is designed to embed Sobolev regularity onto the PageRank vector, then it is able to overcome the curse of flatness and provide meaningful classification functions as shown by Figure 3.13a. Now, in Figures 3.13band 3.13c, we display the L -PageRank vector with = 32 and = 62, respectively.

3. 7 .Figure 3 . 13 :

 7313 Figure 3.13: Comparison of L -PageRank and Iterated PageRank for the curse of flatness. The horizontal axis represents the spacial dimension of the data and the verticalaxis represents the function value learned by G-SSL

  which, after using its Taylor expansion, allows to rewrite the L -PageRank solution as f = ∑ ∞ k=0 (-1) k µ k L D -1 k y.I fy = ⇡ , the previous equation is only non-zero for k = 0, proving (ii ).

3.D Proof of Lemma 9 Proof.

 9 Let y = D S vol (S). Using Eq. (3.6) we can see that T S c f = u∈S [D ] uu vol (S) T S c µ L D -1 + µI

.

  Let n = S. For u, v ∈ S and w ∈ S c the Planted Partition satisfies ∑ v W uv ∼ B(n -1,p in ) and ∑ w W uw ∼ B(n, p out ). The key step in the proof is to show that, in the 70 CHAPTER 3. L -PAGERANK FOR SEMI-SUPERVISED LEARNING 3.F. PROOF OF THEOREM 5 limit n → ∞, E h (S)] , and the same for h (2) S . By application of the Chebyshev inequality we have that Pr(d u -E [d u ] ≥ E [d u ]) ≤ var(d u ) var(d u ) + E [d u ] 2 = O(n -1 ). (3.25) Thus, in the limit of n → ∞ we can establish the inequality d u < 2E [d u ] and further that vol(S) < 2E [vol(S)]. This latter allows to express E h (1)

S

  ] follows a similar derivation. Since [D 2 ] uu = d 2 u + d u ,t h eJ e n s e n inequality implies that [D 2 ] uu < 2E [[D 2 ] uu ] and consequently that vol 2 (S) < 2E [vol 2 (S)].

. 28 ) 1 =CHAPTER 3 .

 2813 Let the random variable O u = ∑ w∈S c W uw . Then we have that T S L 2 S = 2 ∑ u∈S (O u ) 2 . This fact, in addition to vol 2 (S) = ∑ u∈S d 2 u + d u , allow to show that the sequence ∑ i c O(n -1 ). Replacing the expectations and evaluating the limit leads to: L -PAGERANK FOR SEMI-SUPERVISED LEARNING 3.G. PROOF OF COROLLARY 1

  Thus, it is sufficient that S satisfies:

Figure 4 . 2 :

 42 Figure 4.2: Normalized approximation in the power method when doing computation from scratch or by using the warm restarts. For the test, we use the same Minessota graph example from Figure 4.1.

CHAPTER 4 .

 4 FAST AND EFFICIENT IMPLEMENTATIONS 4.3. FAST AND EFFICIENT IMPLEMENTATIONS OF G-SSL ON STATIC GRAPHS Algorithm 6 [25] Local PageRank updating via Gauss-Southwell Input: ↵, P , P , p and r. Output: Updated PageRank vector p and updated residual r. p(0) = p r(0) = r + ↵[ P T -P T ]p

  FAST AND EFFICIENT IMPLEMENTATIONS 4.3. FAST AND EFFICIENT IMPLEMENTATIONS OF G-SSL ON STATIC GRAPHS Method L γ -PageRank L γ -Norm. Lap. L γ -Std. Lap. Iter. PageRank Recenterd kernel

. 16 )

 16 and = max 2, c t = 2 ⇡ ∫ ⇡ 0 cos(t✓)h( (cos(✓) + 1))d✓. 4.3. FAST AND EFFICIENT IMPLEMENTATIONS OF G-SSL ON STATIC GRAPHS Algorithm 7 [23] Distributed computation of G-SSL via Chebyshev polynomials

Figure 4 . 3 :

 43 comparison of Algorithm 3 and Algorithm 9.

Figure 4 . 4 :

 44 Figure 4.4: comparison of Algorithm 4 and Algorithm 10.In this figure, we observe that the ARMA-based Gauss-Southwell method also displays an improvement over the random walk-based version of the algorithm. In this case, the benefits are more evident after ✏ < 10 -3 , as, for this regime, Algorithm 10 terminates in less iterations than Algorithm 4 while attaining less `2-norm error and more accurate rankings. Remarkably, the sweep error is already very small from rather large values of ✏.T h i sm a yb ed u et ot h e simple graph model that we are considering, where there is only one clear partition of small Cheeger ratio, hence it is should be doable for the sweep to find this true partition despite the inaccurate functions. However, the multi-class error displays high values for large values of ✏ and only after ✏ < 10 -3 the true partition is always obtained.

Figure 4 . 5 :

 45 comparison of distributed algorithms: (i) Chebyshev (Algorithm 7); (ii) Greens function (Algorithm 8); and (iii) ARMA-recursions (

Figure 4 . 3 :

 43 Figure 4.3: Comparison of Algorithm 3 (Random walk-based power iteration) vs Algorithm 9 (ARMA-based power iteration).

Figure 4 . 6 :

 46 Figure 4.6: sensitivity of Algorithm 10 to µ and . In this figure, we observe that the Gauss-Southwell, as its based on the ARMA recursion, is also sensitive to variations in ,µ. Namely, as we increase , we increase the number of iterations and the `2 error. Then, if µ is further decreased these quantities increase even more. Interestingly, the figures from the sweep error and multi-class error suggest that the introduction of implies to more quickly converge towards the true partitions.

4. 3 .

 3 Figure 4.4: Comparison of Algorithm 4 (Random walk-based Gauss-Southwell) vs Algorithm 10 (ARMA-based Gauss-Southwell)

  (a) γ = 1,µ = 5 (b) γ = 1,µ = 0.1 (c) γ = 5,µ = 5 (d) γ = 5,µ = 0.1 (e) γ = 1,µ = 5 (f) γ = 1,µ = 0.1 (g) γ = 5,µ = 5 (h) γ = 5,µ = 0.1 (i) γ = 1,µ = 5 (j) γ = 1,µ = 0.1 (k) γ = 5,µ = 5 (l) γ = 5,µ = 0.1 (m) γ = 1,µ = 5 (n) γ = 1,µ = 0.1 (o) γ = 5,µ = 5 (p) γ = 5,µ = 0.1

Figure 4 . 5 :Figure 4 . 6 :

 4546 Figure 4.5: Comparison of distributed algorithms: (i) Chebyshev (Algorithm 7); (ii) Greens function (Algorithm 8); and (iii) ARMA-recursions (Algorithm 9). In the figure array, rows correspond to error metrics and columns correspond to a combination of ( ,µ).

Figure 4 . 7 :

 47 Figure 4.7: Effect of using a warm restart on the ARMA recursion versus computing from scratch via the Chebyshev approach when one node joins the graph.

Lemma 16 .

 16 Let K-terms be used in the estimation of arma ⇢, (r) in Algorithm 11 and p(K) denote the output of Algorithm 11 under such truncation. Then, the output of Algorithm 11 satisfies arma ⇢, (y) -p(K) ≤ K+1 SK+1 1 ⇢ arma ⇢, (r) (4.39)

  (a) expected number of nodes joining; (b) expected number of nodes leaving; (c) probability of a link appearing inside classes; (d) probability of a link appearing between classes; (e) probability of a link disappearing inside classes; (f) probability of a link disappearing between classes.

Figure 4 . 8 :

 48 Figure 4.8: Approximation accuracy of the local algorithms (Algorithm 11 and Algorithm 12) and the Chebyshev method (Algorithm 7) as the number of fundamental operations they have performed in the task of updating an L 2 -PageRank vector

  3.5, i.e., we use C avg = 20, C in = 18, C out = 2, N = 1000. Then, 1% of labelled points is sampled at random and our dynamic SBM Python 3 class is used to make evolve the graph for 20 time steps. We use the following evolutionary parameters: (a) expected number of nodes joining: 1; (b) expected number of nodes leaving: 1; (c) probability of a link appearing inside classes: C in (25N ); (d) probability of a link appearing between classes: C out (25N ); (e) probability of a link disappearing inside classes:

Figure 4 . 9 :

 49 Figure 4.9: Updating via neural network (proposed) versus the analytic updates via the power method with warm restart (analytic)

106 CHAPTER 5 .

 5 G-SSL FOR INTERNET ROUTING 5.2. G-SSL TO CHARACTERIZE THE SCOPE OF BGP ZOMBIES

108 CHAPTER 5 .

 5 G-SSL FOR INTERNET ROUTING 5.3. L -PAGERANK FOR IP TO AS MAPPING multiple paths of IP addresses collected from the traceroutes.

116 CHAPTER 5 .Figure 5 . 6 :

 556 Figure 5.6: Classification accuracy of each AS as a function of µ using sweep-cuts on the annotated examples of the strict expert. No annotated examples are available for AS4.

118 CHAPTER 5 .Figure 5 . 7 :

 557 Figure 5.7: Classification accuracy of each AS as a function of µ using sweep-cuts on the annotated examples of the loose expert.

Figure 5 . 8 .Table 5 . 5 :

 5855 Figure 5.9c reports the same for the multi-class approach. The figures indicate that, for the weighted expert, standard PageRank remains not very sensitive to µ and L -PageRank is more sensitive, but displays a superior performance for a wide range of µ values. CHAPTER 5. G-SSL FOR INTERNET ROUTING Best classification attained by G-SSL using the weighted expert labelled data.The table reports the annotations given by the expert and their weights. Green cells refer to correct inferences and red cells to incorrect inferences. Cells with more than one tag indicate that G-SSL assigns the node to more than one class.

Figure 5 . 8 :

 58 Figure 5.8: Classification accuracy of each AS as a function of µ using sweep-cuts on the annotated examples of the weighted expert.

Figure 5 . 9 :

 59 Figure 5.9: Classification accuracy of all ASes as a function of µ using the multi-class approach.

  . . . . .

	Symbols
	G	Weighted undirected graph
	W	Graph adjacency matrix
	D	Graph degree matrix
	vol(S)	Volume of set S
	∆ uv	Geodesic distance between nodes u and v
	P	Transition probability matrix
	t	t-th step distribution of a random walk
	⇡	Stationary distribution of a random walk
	L	-th Laplacian power
	f	G-SSL solution
	y	vector of labelled points
	f (S)	Sum of f in the set S
	f	Graph Fourier Transform of f
	L	Combinatorial Laplacian matrix
	L n	Normalized Laplacian matrix
	L rw	Random walk Laplacian matrix
	Λ	Laplacian spectrum
	h(Λ)	Graph filter
	V L	Set of labelled points
	µ	regularization parameter of G-SSL
	↵	Restart probability
	S gt	Ground truth class
	h S	Cheeger ratio of S
	q	Permutation vector
	W	L -graph adjacency matrix
	D	L -graph degree matrix
	P	L -graph transition matrix
	h
		XIII

  The random walk Laplacian of a graph, denoted L rw , acting on the graph signal f and evaluated in a node u is given by

	1.4. GRAPH SIGNAL PROCESSING
	Definition 10.

  The graph Fourier transform of a graph signal f , denoted f , is given by

	1.4. GRAPH SIGNAL PROCESSING
	Definition 14.
	18	CHAPTER 1. PRELIMINARIES

  ∈ R N ×K denote a classification matrix. The k-th column of F , denoted F * k , is referred to as the classification function of class k. The goal of G-SSL algorithms is first to estimate the scores of the classification matrix F given the matrix of labelled points Y , and then, interpret entry F uk as how likely it is that node u belongs to class k, upon which a final classification decision is made.

	.1) CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING 2.2. FROM TIKHONOV REGULARIZATION TO G-SSL And second, let F

Table 3 .

 3 3: Performance on unbalanced labelled data: each cell reports MCC, 95% confidence interval (parenthesis) and the value of [squared brackets].drawn at random: 2% from one class and 6% from the other. Lastly, L -PageRank, in the multi-class setting, is applied for a grid of µ values and the best performance, assessed by MCC, is recorded. For the planted partition, the procedure is repeated over 15 realizations of the labeled points and for 100 graph realizations. For the other datasets, 100 realizations of labeled points are employed.

Table 3 .

 3

4: Performance of both L -PageRank and Iterated PageRank on the MNIST dataset (multi-class setting): each cell reports MCC and the 95% confidence interval (parenthesis).

Table 3 . 5

 35

: Performance of L -Normalized Laplacian: each cell reports MCC, 95% confidence interval (parenthesis) and the value of [squared brackets].

Table 4 .

 4

1: Possible choices for reference operators in G-SSL.

  4.C. PROOF OF LEMMA 154.C Proof of Lemma 15Proof. Let us depart with a warm restart on the ARMA recursion as follows:

	p(1) = ⇢y + S p(0) = ⇢y + Sarma ⇢, (y) = arma ⇢, (y) -Sarma ⇢, (y) + Sarma ⇢, (y) = arma ⇢, (y) + S -S arma ⇢, (y)	(4.55) (4.56) (4.57) (4.58)
	= arma ⇢, (y) + r				(4.59)
	Then, for the second iteration we have: p(2) = ⇢y + S p(1) = ⇢y + S arma ⇢, (y) + r = arma ⇢, (y) -Sarma ⇢, (y) + S arma ⇢, (y) + r = arma ⇢, (y) + S -S arma ⇢, (y) + Sr = ⇢y + Sarma ⇢, (y) + Sr = arma ⇢, (y) + r + Sr	(4.60) (4.61) (4.62) (4.63) (4.64) (4.65)
	By successive applications of this procedure, we have that
	p(∞) = arma ⇢, (y) +	∞	t St r	(4.66)
		t=0
	= arma ⇢, (y) +	1 ⇢	arma ⇢, (r)	(4.67)

Table 5 .

 5 3: Best classification attained by G-SSL using the strict expert labelled data. No labelled data is available for AS4. Green cells refer to correct inferences and red cells to incorrect inferences. Cells having n.a. indicate that the node is not assigned to any class by G-SSL. Cells with more than one tag indicate that G-SSL assigns the node to more than one class.

Table 5 .

 5 for AS4, therefore G-SSL does not know about the existence of such class and can be prone to assign nodes of AS4 (IDs: 8,9,22) to one of the other classes. Notably, L -PageRank with = 2 and the sweep-cuts (designed to identify classes individually), classify the data in a way that all the nodes belonging to either AS1, AS2, or AS3 are assigned into their correct class, and nodes belonging to AS4 (IDs: 8,9,22) are left

3 indicates that, for the strict expert, L -PageRank ( = 2) with sweep-cuts delivers the best possible prediction permitted by the labelled data. Notice that we lack CHAPTER 5. G-SSL FOR INTERNET ROUTING annotated examples

  12, 16, 11, 10,

		5, 6, 14, 19, 20, 21, 26, 17, 18, 23, 24, 25, 27, 28, 29, 7, 15,	1, 2, 3, 13, 4,	8, 9, 22
	AS1	AS3	AS2	AS4

Table 5 .

 5 4: Best classification attained by G-SSL using the loose expert labelled data. Green cells refer to correct inferences and red cells to incorrect inferences. Cells with more than one tag indicate that G-SSL assigns the node to more than one class.

CHAPTER 2. GRAPH-BASED SEMI-SUPERVISED LEARNING

In turn, this lack of topological insights for most G-SSL propositions, in conjunction with the results indicating that the PageRank vectors have the natural tendency to reveal clusters, may help understand CHAPTER

GRAPH-BASED SEMI-SUPERVISED LEARNING

This phenomenon was pointed in our experiments from Section 3.4.2, where it was shown that the Lévy flight can override, to some extend, such sub-cluster structures.

Acknowledgements CHAPTER 6. CONCLUSIONS Bibliography

It is important to stress that, thus far, we have assumed possession of the proper tuning of the diffusion rate (µ) that attains the best results. However, when working with real data, clusters may have intricate local structures, e.g. sub-clusters, that play an important role in the way information diffuses, and that can make more difficult the finding of the optimal diffusion rate µ. As a result, two clusters may have equal Cheeger ratios but one of them being harder to find if its local structure is complex (this will be made more clear in our last experiment from this section). Digit 8 poses an example of this phenomenon, where the mean performance for ˆ is slightly better than that of * . This anomaly can be explained as an aftereffect of using a finite grid on µ: for some realization of labeled points, the best performance for * falls in a region not covered by the grid.

Unbalanced labelled data

Experimental setup and goals. In Chapter 2, it was shown that an implication of Theorem 2 (see page 29) is that PageRank, in the multi-class setting (where multiple classification functions are compared instead of doing sweeps), suffers from biased outputs when operating on unbalanced labelled datasets. Thus, in our next experiment, we aim to show that L -PageRank, adapted to the multi-class setting, can improve the performance of G-SSL in the presence of unbalanced labelled data.

The experimental setup is as follows: graphs with two balanced classes (in size) are built using the datasets from the preceding experiments. The parameters of the graphs' construction follow the guidelines detailed in our experiment above. For the Planted Partition, the configuration is n = 200, C avg = 3, C out = 0.1. Then, unbalanced labelled points are Algorithm 3 [START_REF] Jeh | Scaling personalized web search[END_REF][START_REF] Maehara | Computing personalized pagerank quickly by exploiting graph structures[END_REF][START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] Distributed computation of PageRank via the Power method Input at node u: y u , ↵, P vu ∀ v ∼ u, K, and p (0) . Output at node u:

The Gauss-Southwell method

The Gauss-Southwell algorithm [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF][START_REF] Berkhin | Bookmark-coloring algorithm for personalized pagerank computing[END_REF] is an iterative method that efficiently computes approximate PageRank vectors. In this algorithm two vectors are used: (i) p: an approximate PageRank vector; and (ii) r: a residual vector coding for the difference between pr ↵ (y) and p. The method initiates with an initial guess p (0) and then, at iteration t,t h e algorithm transfers mass from r (t-1) into p (t) such that the following invariant is preserved:

Hence, the goal of the algorithm is to minimize the residual as that implies that p converges to the PageRank vector. Let us assume that, at iteration t, the largest entry of r (t) corresponds to vertex u. Then, the state of the algorithm at iteration t + 1i sd e t e r m i n e d by the following set of update equations:

This procedure is repeated until all entries from the residual vector diminish below some threshold value ✏. The whole procedure is detailed in Algorithm 4.

Algorithm 4 is extremely efficient to implement as the update equations only imply addition and re-scaling of vectors. To see it, recall that ↵P T r (t-1) u u corresponds to a re-scaling the u-th column of P T by the scalar ↵r

. Hence, cost of the algorithm is determined by the number of iterations required until convergence. Naturally, such number of iterations depends on the desired accuracy, as stated by the following result:

This Lemma implies that cost of the Gauss-Southwell algorithm is O(r (0) 1 ((1 -↵)✏), which is independent of the number of edges in the graph.

Updating PageRank on dynamic networks

In the introduction of this Chapter, we pointed that graphs arising in real world applications are not only massive but also dynamic. Intuition says that if the graph does not

Algorithm 8 Distributed computation of G-SSL via Greens functions

Input at node u: y u ,µ, max ,K,✏, and

using

Stirling's approximation. To estimate ⌧ f from z f , we note that z f = ⌧ f max µ,h e n c e leading to the result that for K terms we can run our diffusion process until

The distributed implementation of this algorithm is summarized in Algorithm 8.

Generalized implementation via ARMA recursions

In this subsection, we contribute with an extension of the Algorithms from Section 4.2) by using the ARMA filters. The ARMA graph filters, introduced in [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF], are a type of filter characterized for being able to implement filter functions with rational frequency response. They are defined by the following recursive formula: 1) . (4.28)

In [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF], it is shown that when this recursive formula converges, then it defines a filter in the spectral domain of R with input y: [START_REF] Isufi | Autoregressive moving average graph filtering[END_REF]). Let R be a symmetric operator and max denote its spectral radius bound. Further, let r = -⇢ be a residue and p = 1 denote a pole of a rational transfer

Algorithm 9 Distributed computation of G-SSL via the Power method

Input at node u: y u , µ, R uv ∀ {v ∼ u} ∪ u, K, p (0) and max .

Output at node u: p

The proof of this Lemma is deferred to Appendix 4.A

We have that the spectrum of S lies within the unit circle, implying that when K grows, S K converges to a rank one matrix. As a result, S K converges to a constant value that has a negligible role on the asymptotic convergence rate, making this determined by (i) max 2µ+ max K → 0; and (ii) how accurate is the initial guess. Now, we compare Algorithm 9 with Algorithm 3 for computation of standard PageRank. We have that the latter has a convergence rate determined by ↵ K = 1 µ+1 K → 0, while the one of the former can be recast as max2 µ+ max2 K → 0. This implies that Algorithm 9 converges faster if max 2 < 1, which is always true as standard PageRank is driven by the random walk Laplacian R = LD -1 , which, as mentioned in Chapter 1, it always has a max smaller than 2 (unless the graph is bipartite).

Generalized implementation via Gauss-Southwell method

In this subsection, we leverage the ARMA recursion from Eq. (4.32) to contribute with an extension of the Gauss-Southwell algorithm to the general family of G-SSL methods. In precise terms, by analogy with standard Gauss-Southwell method (see Algorithm 4 in Section 4.2), we propose to have two vectors: an approximate G-SSL vector p and its residual vector r, so that, at each iteration t, the algorithm satisfies the following invariant:

Hence, the main goal of our proposition remains to drive r towards zero as that implies that p converges to the G-SSL solution. In the following, we extrapolate the update equations from the standard Gauss-Southwell to the ARMA case and show that they preserve the invariant (4.34).

Lemma 14. Assume that, at iteration t, the largest entry of r (t) corresponds to vertex u.

Algorithm 10 Approximate G-SSL computation via Gauss-Southwell method

Input: µ, R, p (0) , ✏, and max Output: Approximate G-SSL solution p and its residual r ⇢ = (2µ)(2µ

Then, the following set of update equations satisfy, for all t, the invariant of Eq. (4.34):

where

The proof of this Lemma is deferred to Appendix 4.B.

Algorithm 10 summarizes our extension of the Gauss-Southwell algorithm to general family of G-SSL methods. Now, we stress that the general nature of R and arma ⇢, (y),whic h can code for a signed graph and a vector of negative entries, respectively, make notoriously hard to theoretically bound the running time of Algorithm 10. Indeed, it is not even straightforward to guarantee that r (t+1) ∞ ≤ r (t) ∞ as, in theory, r

u may be negative and the vector Rr (t) u u may have positive and negative entries. We stress that despite this theoretical challenge, in practice, we have experienced that the update equations satisfy r (t+1) ∞ ≤ r (t) ∞ for all t, implying that the algorithm always terminates. We leave the formal analysis on the time complexity of Algorithm 10 as an open problem.

Numerical assessment

In this subsection, we assess the approximation algorithms presented above. We present two experiments: in the first, we compare our ARMA-based methods (Algorithm 9 and 10) versus their random walk-based counterparts (Algorithms 3 and 4) by noting that standard PageRank arises as a particular case of our generalized approaches; in our second experiment, by using our L -PageRank as base method, we compare the approximation quality of Algorithms 7 -10 and assess the sensitivity of these algorithms to variations in µ and . To assess the quality of the approximations, we employ the following error metrics:

• `2-norm error: standard metric to compute the relative distance between two vectors. Apply Gauss-Southwell on p(0) and r(0) , store result in p and r

Return p and r denotes the update, the Lemma implies that the convergence rate of the algorithm is determined by (i) the size of the update; and (ii) the rate at which K+1 = max 2µ+ max K+1 → 0, which is the same of Algorithm 11.

Local G-SSL updating via Gauss-Southwell

We now finalize our extension of algorithms by revamping the Gauss-Southwell method to perform local updates to the G-SSL solution. In analogy with Algorithm 6, we embed the local update property by means of the warm restarts. Namely, let p and r denote the approximate G-SSL solution and residual vector, respectively, output by the Gauss-Southwell algorithm for graph G. Then, under the assumption that the initial condition y and the set of ARMA coefficients ⇢, do not change, we use p as the initial guess p(0) when running the Gauss-Southwell for G. In math terms, we use the following initial state of the algorithm p(0) = p We identify this residual to be local on the perturbations, thus implying that only a few entries of r can be triggered beyond the threshold. As a result, with only a few iterations the Gauss-Southwell will drive these entries below the threshold again. We summarize the procedure for local G-SSL updating via the Gauss-Southwell method in Algorithm 12.

Appendix: technical proofs Taking the norm finishes the proof.

4.B Proof of Lemma 14

Proof. By induction, for t = 0w eh a v e : r (0) = ⇢y -(I -S)p (0) = (I -S)arma ⇢, (y) -p (0) (4.51)

Then, by isolating arma ⇢, (y), we obtain: arma ⇢, (y) = p (0) + (I -S) -1 r (0) = p (0) + 1 ⇢ arma ⇢, (r (0) ) (4.52)

Now, suppose that arma ⇢, (y) = p (t) + 1 ⇢ arma ⇢, (r (t) ) holds for some t. Then, for t + 1w e have: r (t+1) = r (t) -(I -S) r (t) u u = r (t) -(I -S)p (t+1) -p (t) (4.53)

The proof finishes by re-arranging terms 1 ⇢ arma ⇢, (r (t+1) ) + p (t+1) = 1 ⇢ arma ⇢, (r (t) ) + p (t) = arma ⇢, (y). (4.54)