Un graphe est un objet mathématique permettant de représenter des relations entre des entités (appelées noeuds) sous forme d'arêtes. Les graphes sont depuis longtemps un objet d'étude pour différents problèmes allant d'Euler au PageRank en passant par les problèmes de plus courts chemins. Les graphes ont plus récemment trouvé des usages pour l'apprentissage automatique. Avec l'avènement des réseaux sociaux et du web, de plus en plus de données sont représentées sous forme de graphes. Ces graphes sont toujours plus gros, pouvant contenir des milliards de noeuds et arêtes. La conception d'algorithmes efficaces s'avère nécessaire pour permettre l'analyse de ces données.

Cette thèse étudie l'état de l'art et propose de nouveaux algorithmes pour la recherche de communautés et le plongement de noeuds dans des données massives. Par ailleurs, pour faciliter la manipulation de grands graphes et leur appliquer les techniques étudiées, nous proposons Scikit-network, une librairie libre développée en Python dans le cadre de la thèse. Nous nous intéressons également au problème d'annotation de données. Les techniques supervisées d'apprentissage automatique nécessitent des données annotées pour leur entrainement. La qualité de ces données influence directement la qualité des prédictions de ces techniques une fois entrainées. Cependant, obtenir ces données ne peut pas se faire uniquement à l'aide de machines et requiert une intervention humaine que nous cherchons à minimiser.

Les contributions décrites dans le manuscrit ont toutes recours à des graphes. Pour la fouille de graphes et le développement de Scikit-network, les données étudiées sont représentées sous forme de graphes. Pour le problème d'annotation des données, les graphes servent d'outil formel à un raisonnement mathématique. Toutes ces contributions ont des applications dans le domaine de l'apprentissage automatique.

Les contributions logicielles de la thèse sont rassemblées dans Scikit-network. Scikitnetwork est inspirée de la librairie Scikit-learn, qui propose un large éventail d'algorithmes pour l'ap-prentissage automatique sur des données vectorielles. Par analogie, nous rassemblons dans Scikit-network diverses méthodes pour la fouille de données et l'apprentissage automatique sur des graphes. Cette librairie libre fait usage de nombreux outils présents dans l'écosystème du langage Python pour permettre à ses utilisateurs d'analyser des jeux de données massifs tout en offrant une bonne ergonomie. De nombreuses tâches, telles que le calcul de centralités et la classification de noeuds, peuvent être accomplies à l'aide de Scikit-network.

Le manuscrit fait l'état de l'art des techniques de recherche de communautés dans des graphes. Nous distinguons les techniques selon qu'elles sont hiérarchiques ou non. Dans le second cas, nous étudions tout particulièrement la méthode de Louvain et certaines de ses variantes. Nous comparons qualitativement les performances de ces variantes. Nous proposons également une nouvelle variante de la méthode de Louvain visant à en accélérer l'exécution.

Nous nous appuyons sur les techniques de recherche de communautés ainsi décrites pour proposer une nouvelle méthode pour le plongement des noeuds d'un graphe. Nous mesurons la performance de cette méthode en la comparant à d'autres algorithmes issus de l'état de l'art. Nous illustrons également certaines de ses propriétés, notamment en expliquant comment les résultats peuvent être interprétés en fonction des communautés trouvées par l'algorithme de Louvain.

Une autre contribution de la thèse consiste en l'étude d'un problème particulier d'annotation de jeux de données motivé par un cas d'usage industriel. Après avoir introduit le problème en question, sous un formalisme utilisant des graphes, nous caractérisons simplement les solutions optimales. Nous prouvons ensuite que cette famille de solutions optimales partage la même distribution de complexité dont nous étudions le comportement. Nous décrivons également plusieurs variantes possibles du problème étudié et leurs applications.

Chapter 1 Introduction

Motivation

Machine learning gathers algorithms that are designed to "learn" from data, i.e. algorithms that can improve their performance for a given task by themselves. It may be seen as a subfield of artificial intelligence in that it allows computers to emulate some form of reasoning. Machine learning algorithms aim at predicting information about the data they are fed. This data may come in a number of shapes and formats: it can be images of animals, law bills gathered in text corpora or molecule interactions represented by a graph. The applications for machine learning algorithms are equally varied and range from agriculture and medicine to banking and linguistics.

In this thesis, we tackle selected problems in machine learning pertaining to graphs (which are a mathematical representation of interactions between several entities). Graphs have been used in many different ways in the field of machine learning. Among recent developments are graph kernels [START_REF] Vishwanathan | Graph kernels[END_REF], which aim at measuring the similarity between pairs of graphs, and graph neural networks [START_REF] Scarselli | The graph neural network model[END_REF] that make it possible to use neural networks on data represented by graphs. Throughout this thesis, we distinguish cases where graphs are used to model relational data (as seen in Chapters 2, 3 and 4) as opposed to settings where graphs are used as a formal tool regardless of the actual data (as is the case in Chapter 5). In both cases, however, we seek to harness graphs and their properties to improve the performance of machine learning algorithms.

Graphs

A graph is a mathematical object used to represent relations between entities called nodes or vertices. The relations between nodes are represented by pairwise connections between them called edges or links depending on the context. Two nodes linked by an edge are neighbors of one another and referred to as adjacent. The degree of a node is its number of neighbors. Let G = (V, E) denote a graph, where V is the node set and E ⊂ V × V is the Graphs can be found in a wide variety of fields ranging from bioinformatics to social sciences. Depending on the domain under study, graphs may sometimes be called networks. They can be used to represent many different datasets including web graphs where each node is a website and links represent the hyperlinks between them.

There are a number of families of graphs. We describe some of those that are found in this work and illustrate them in Figure 1.1:

• Undirected graphs describe symmetric relations between the nodes. That is ∀i, j ∈ V, if (i, j) ∈ E then (j, i) ∈ E. This is the case of users on Facebook as the friendship link is symmetric.

• Conversely, directed graphs describe relations where the previous implication does not hold for all node pairs. This corresponds to the follower/followee relation on Twitter or hyperlinks on the web. In directed graphs, edges are sometimes called arcs.

We distinguish the source node of an arc from its target node for clarity. Considering an edge (i, j) ∈ E, we say that i is a predecessor of j and that j is a successor of i.

• Bipartite graphs are a subclass of undirected graphs where the node set V is the disjoint union of two sets V 1 and V 2 such that all edges in E have one end in one set and the other end in the other set. Bipartite graphs are used to represent relations between two distinct types of entities such as diseases and their corresponding symptoms or Netflix users and the movies they rate.

In this work, we also consider one natural variant: weighted graphs. In a weighted graph, each edge is assigned a non-negative real number called weight. This allows to further characterize the relative strengths of the connections between the nodes.

We fix some notations that can be found throughout this thesis:

• Unless specified, we note n = |V|, the number of nodes and m = |E|, the number of edges.

• If the graph is unweighted and undirected, d i is the degree of node i ∈ V. If the graph is directed, d + j (resp.d - i ) is the out-degree (resp.in-degree), i.e. the number of edges whose source (resp.target) is i. Then, d + j (resp.d - i ) just corresponds to the number of successors (resp.predecessors) of i. If the graph is weighted, d + j (resp.d - i ) is the sum of the weights of edges whose source (resp.target) is i.

• We note w, the total weight of the graph, that is the sum of the weights of all the edges.

• For readability, we sometimes abbreviate the edge (i, j) into ij.

Graph analysis

In this section, we introduce two research fields centered around the analysis of graphs. While graph theory seeks to describe the properties of graphs as a mathematical object, graph mining is rather aimed at extracting information from datasets that can be represented as a graph. Both fields differ in the methods they use but they do overlap as illustrated by the shortest-path problem which is an historically significant problem from a theoretical standpoint [START_REF] Ahuja | Faster algorithms for the shortest path problem[END_REF]) that has also seen some use in real-world applications [START_REF] Zhang | Six degrees of separation in online society[END_REF] such as social sciences.

Graph theory

Graph theory is concerned with the mathematical properties of graphs. Here, we give a list of some common graph-theoretic problems:

• Graph classes There exist many families of graphs defined by some of their properties. For instance, among those families are planar graphs, which can be drawn without any of their edges intersecting. We give an example of a graph having this property in Figure 1.2. For many of those families, characterizing them [START_REF] Lovász | A characterization of perfect graphs[END_REF][START_REF] Farber | Characterizations of strongly chordal graphs[END_REF] and being able to identify if a graph belongs to some family [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF][START_REF] Hopcroft | Efficient planarity testing[END_REF] is of particular interest. One such class is a focal point of Chapter 5.

Figure 1.2: A planar graph.

• Graph coloring One is interested in finding a coloring of the nodes (i.e. assigning a color to each node of the graph) so that no adjacent nodes have the same color [START_REF] Jensen | Graph coloring problems[END_REF]. While there exists a number of variations of this problem, one of the most well-known results is the four-color theorem [START_REF] Gonthier | Formal proof-the four-color theorem[END_REF] which states that on loopless planar graphs, no more than four colors are required to solve the problem. One simple application of coloring problems occurs when determining if a graph is bipartite or not: a graph is bipartite if, and only if, it has a 2-coloring, each node being colored depending on the node subset it is in (as illustrated in Figure 1.3).

Figure 1.3: 2-coloring of a bipartite graph.

• Route problems Route problems are those that aim at finding a path (sometimes a tree) within a graph that satisfies some conditions such as going through each node exactly once or finding the shortest path between a pair of nodes as illustrated in Figure 1.4. They gather famous problems including that of the seven bridges of Königsberg [START_REF] Euler | The seven bridges of königsberg[END_REF] and the Hamiltonian path problem [START_REF] Gurevich | Expected computation time for hamiltonian path problem[END_REF]. Route problems have many applications in fields such as computer science [START_REF] Li | A survey of network flow applications[END_REF] and transportation [START_REF] Ford | Network flow theory[END_REF][START_REF] Zhan | Shortest path algorithms: an evaluation using real road networks[END_REF].

Figure 1.4: Shortest path (in red) between two nodes.

We now give some graph-theoretical definitions that we will use throughout this work [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF].

• A graph is connected if there is a path between every pair of nodes and disconnected otherwise. A connected component of a graph is a connected subgraph, maximal for the inclusion.

• A u, v-separator is a subset of the node set that, once removed, disconnects the graph so that u and v are in distinct connected components.

• A cycle C is a path C = (u, v, w, . . . , u) from one node to itself of size at least three.

No node other than the first and last can be repeated. A chord of a cycle is an edge connecting two non-consecutive nodes of a cycle. A cycle without a chord is induced or chordless.

• A tree is a connected graph with no cycles.

• A clique of a graph is one of its complete subgraphs.

Graph mining

Graph mining is a collection of techniques designed to find the properties of real-world graphs. It consists of data mining techniques used on graphs [START_REF] Rehman | Graph mining: A survey of graph mining techniques[END_REF]. While this definition hints at some overlap with graph theory, a number of techniques are encountered almost exclusively in a graph mining context. Here, we provide a list of some common graph-mining tasks:

• Node ranking Ranking consists in assigning a score to each node of the graph denoting its importance or centrality. There are many ranking methods [START_REF] Bloch | Centrality measures in networks[END_REF][START_REF] Landherr | A critical review of centrality measures in social networks[END_REF] defining a wide range of measures, some based on random walks in the graph, as illustrated by the PageRank ranking [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] originally designed for web pages; some using solutions to the shortest path problems [START_REF] Okamoto | Ranking of closeness centrality for largescale social networks[END_REF]. An example is given in Figure 1.5. We do not tackle this task in the persent work.

Figure 1.5: Ranking of the nodes using PageRank.

• Node clustering Node clustering, also called community detection, gathers methods that look for significant communities in a graph based on its structure. In particular, a good clustering should group nodes so that they are more connected to their own cluster than the others as seen in Figure 1.6. Node clustering has applications in the Internet of Things [START_REF] Mitra | A survey on clustering techniques for wireless sensor network[END_REF] and for recommendation systems [START_REF] Fortunato | Community detection in graphs[END_REF]. Chapter 3 reviews some clustering methods.

Figure 1.6: Clustering of the nodes using the Louvain method.

• Node embedding While the graph formalism is very well suited for representing relational data, the need may arise to represent each node as a vector, this operation is called embedding the nodes of the graph. For instance, the dimension of the embedding space can be set to a low value compared to the number of nodes for dimensionality reduction. It is also a way to apply machine learning techniques that take vectors as input. We illustrate the embedding task in Figure 1.7. Chapter 4 describes an embedding method.

Figure 1.7: 3-dimensional embedding of the nodes using the singular values decomposition.

Outline

This thesis is organized as follows:

• Chapter 2 introduces Scikit-network, a graph analysis library used in our experiments. It was extensively developed in the framework of this thesis and offers a simple API along with competitive performance at scale.

• Chapter 3 reviews some selected node clustering methods. We describe the flat clustering Louvain method and some of its refinements and some hierarchical clustering algorithms.

• Chapter 4 describes a novel node embedding method. It is based on the Louvain clustering method of the previous chapter to tackle large-scale datasets and offer interpretable results.

• Chapter 5 deals with the problem of dataset labeling. The particular setting under study is derived from a real-world problem. We describe the optimal solution for this setting.

• Chapter 6 concludes this thesis.

Publications

Two articles have been accepted during this thesis:

• Bonald, T., de Lara, N., Lutz, Q., & Charpentier, B. (2020). Scikit-network: Graph Analysis in Python. J. Mach. Learn. Res.,21, Chapter 2

Scikit-network

The Scikit-network package was created in 2018 by Thomas Bonald and Bertrand Charpentier. The work described in this chapter has been carried out jointly with Nathan de Lara and Thomas Bonald. We refer the reader to the package's GitHub insights1 for a rough overview of the respective contributions of the developers. It should be noted however, that a significant portion of the package was developed by several contributors at once (in pair programming fashion) while just one gets to commit to the Git repository. Furthermore, part of the work on the package is not accounted for when looking at the repository only: trying out different features, libraries or continuous integration tools; designing efficient code through careful understanding of scientific articles and learning new skills in software development are all demanding tasks. Overall, it is safe to assume that no one contributor among the core developers had a disproportionate role over the others.

Motivation

Scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] is a machine learning package based on the popular Python language. This package is well-established in today's machine learning community thanks to its versatility, performance and ease of use, making it suitable for both researchers, data scientists and data engineers. Its main assets are the variety of algorithms, the performance of their implementation and their common API. Scikit-network is a Python package inspired by scikit-learn for graph analysis. The sparse nature of real graphs, with up to millions of nodes, prevents their representation as dense matrices and rules out most algorithms of scikit-learn. Scikit-network takes as input a sparse matrix in the CSR format of SciPy and provides state-of-the-art algorithms for ranking, clustering, classifying, embedding and visualizing the nodes of a graph.

The design objectives of Scikit-network are the same as those having made scikit-learn a success: versatility, performance and ease of use. The result is a Python-native package, like NetworkX [START_REF] Hagberg | Exploring network structure, dynamics, and function using networkx[END_REF], that achieves the state-of-the-art performance of iGraph Figure 2.1: Scikit-network logo [START_REF] Csardi | The igraph software package for complex network research[END_REF], graph-tool [START_REF] Peixoto | The graph-tool python library[END_REF] and NetworKit [START_REF] Staudt | Networkit: A tool suite for largescale complex network analysis[END_REF] (see the benchmark in section 2.3.3). Scikit-network uses the same API as Scikit-learn, with algorithms available as classes with the same methods (e.g., fit). It is distributed with the BSD license, with dependencies limited to NumPy [START_REF] Walt | The numpy array: a structure for efficient numerical computation[END_REF] and SciPy [START_REF] Virtanen | SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python[END_REF].

Software Features

The package is organized in modules with consistent API, covering various tasks:

• Data. Module for loading graphs from distant repositories, including Konect [START_REF] Kunegis | KONECT: The Koblenz Network Collection[END_REF], parsing tsv files into graphs, and generating graphs from standard models, like the stochastic block model [START_REF] Airoldi | Mixed membership stochastic blockmodels[END_REF].

• Clustering. Module for clustering graphs, including a soft version that returns a node-cluster membership matrix.

• Hierarchy. Module for the hierarchical clustering of graphs, returning dendrograms in the standard format of SciPy. The module also provides various post-processing algorithms for cutting and compressing dendrograms.

• Embedding. Module for embedding graphs in a space of low dimension. This includes spectral embedding and standard dimension reduction techniques like SVD and GSVD, with key features like regularization.

• Ranking. Module for ranking the nodes of the graph by order of importance. This includes PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] and various centrality scores.

• Classification. Module for classifying the nodes of the graph based on the labels of a few nodes (semi-supervised learning).

• Topology. Module for exploring the structure of the graph: graph traversals, k-core decomposition, etc.

Modules • Path. Module relying on SciPy for shortest-paths problems.

NetworkX iGraph graph-tool NetworKit Data ✓ ✗ ✓ ✓ Clustering ✓ ✓ ✗ ✓ Hierarchy ✗ ✓ ✓ ✗ Embedding ✓ ✗ ✓ ✗ Ranking ✓ ✓ ✓ ✓ Classification ✓ ✗ ✗ ✗ Topology ✓ ✓ ✓ ✓ Path ✓ ✓ ✓ ✓ Link prediction ✓ ✓ ✓ ✓ Visualization ✓ ✓ ✓ ✓
• Link prediction. Module for assigning a probability of existence of an edge to a node pair based on a partial graph.

• Visualization. Module for visualizing graphs and dendrograms in SVG (Scalable Vector Graphics) format. Examples are displayed in Figure 2.2.

These modules are only partially covered by existing graph softwares (see Table 2.1). Another interesting feature of Scikit-network is its ability to work directly on bipartite graphs, represented by their biadjacency matrix.

Practical considerations

Efficient graph representation

There exists multiple ways to represent a graph formally. We compare three of the most common ones:

• Adjacency matrix, a square matrix A ij of size n where A ij is the weight of the edge (i, j) (or 1 for unweighted graphs) if it exists and 0 otherwise.

• Adjacency list, a list of lists where the i-th list contains the neighbors of node i.

• Incidence matrix, a rectangular matrix B ik of shape n × m such that B ik = 1 if, and only if, node i is incident to the k-th edge.

In a more practical sense, the choice of the representation alone is not enough to assess the performance of some common operations such as finding the weight associated with a particular edge or removing a vertex from the graph. The implementation of any of those representations matters. In particular, the chosen data structure determines how well the graph can be manipulated. For example, if one makes a naive implementation of the three representations mentioned above using dense C-like (i.e. contiguous in memory so that indexing is implicit) arrays of size n2 and nm for the adjacency and incidence matrices respectively, and a list of lists for the adjacency list, their performances are as described in Table 2.2.

Notice that the incidence matrix performs worse than both other representations in all cases, it is thus seldom used in practice. However, there is no absolute winner between the adjacency matrix and adjacency list.

To further explore the available data structures, we consider actual graph datasets. One useful feature of the majority of real-world graphs is their sparsity. Indeed, the number of edges m is usually very low compared to the number of possible connections n 2 . Given the results displayed in table 2.2, this would favor adjacency lists as a preferred data structure as they are naturally sparse. Nevertheless, there also exists several sparse matrix formats that one can use to represent adjacency matrices. We compare formats that are available in SciPy's sparse module 2 and compare them to an adjacency list implementation using nested Python dictionaries: Task Adjacency matrix Adjacency list Incidence matrix Memory space • The coordinates (COO) format consists of three arrays row, col and data of size m such that for any 1 ≤ i ≤ m, A row(i),col(i) = data(i) and A jk = 0 otherwise. As with all array-based formats, the addition or deletion of edges is costly as it requires to resize the arrays.

O(n 2 ) O(n + m) O(nm) Check (u, v) ∈ E O(1) O(d u ) O(m) Add node u O(n 2 ) O(1) O(nm) Delete node u O(n 2 ) O(d u d max ) O(nm) Add edge (u, v) O(1) O(1) O(nm) Delete edge (u, v) O(1) O(d max ) O(nm) List neighbors of u O(n) O(1) O(m + nd u )
• The dictionary of keys (DOK) format uses a dictionary where the keys are the edges given as tuples and the associated values are the corresponding weights. Unlike array-based formats, it allows for dynamic changes of the matrix while offering constant average access times to its values. Its downside is the memory space required by its hash table.

• The compressed sparse row (CSR) (respectively compressed sparse column (CSC)) format implicitly indexes the source (resp. target) nodes of every edge but explicitly indexes their target (resp. source) nodes. It consists of three arrays. In the case of the CSR format, two arrays indices and data of size m contain the target nodes and the weights of the edges respectively. The third array indptr has size n + 1 and delimits the successors of each source node. For instance, the neighbors of node i are found in the indices array at positions indptr(i) to indptr(i + 1) which can be computed in constant time. Conversely, in the CSC format, indptr delimits the predecessors of each target node. Additionally, algebraic operations such as matrix/vector dot products are very efficient when using the CSR/CSC format.

• The dictionary of dictionaries (DOD) format is not found in SciPy. It is based on nested Python dictionaries: a main dictionary has nodes as keys and dictionaries as values. Additionally, an index is maintained to allow for the addition and deletion of nodes. Each nested dictionary has the neighbors of the corresponding node as keys and the weights of the associated edges as values. Unlike the DOK format, this makes it possible to have constant-time access to the neighborhood of a node by looking at the keys of the corresponding nested dictionary. This comes at the expense of increased memory requirements due to the numerous hash tables of the nested dictionaries. One notable downside is that this format is ill-suited for dot products.

Each format is illustrated on a toy graph depicted in Figure 2.3. In order to compare all the formats described above, we use each format to store various graphs and gather

row col data 0 1 2 0 2 1 2 0 1 (c) COO matrix (0, 1) → 2 (0, 2) → 1 (2, 0) → 1 (d) DOK matrix indptr indices data 0 1 2 2 1 2 2 0 1 3 3 (e) CSR matrix 0 → (1 → 2; 2 → 1) 1 → ∅ 2 → (0 → 1) 3 → ∅ (f) DOD matrix
Figure 2.3: A graph and its different representations. → denotes the association of a key to a value via a hash function. Edge (0, 2) and its associated weight are also highlighted.

the amount of memory space they require in Table 2.3. We also report the execution times for some common graph operations in Table 2.4 using the WikiVitals graph. In the latter table, the COO format is absent as it does not allow most of the listed tasks to be performed (including slicing). It should also be noted that the tasks under study are by no means exhaustive. In particular, a common downside of all the formats at hand is that they are not suited for extracting subgraphs like dense matrices are.

Graph n m CSR COO DOK DOD WikiSchools 4.10 3 1.10 5 6.10 2 1.10 3 4.10 3 2.10 3 WikiVitals 1.10 4 8.10 5 4.10 3 7.10 3 3.10 4 1.10 4 WikiLinks 3.10 6 7.10 7 3.10 5 6.10 5 2.10 6 1.10 6 In Table 2.4, notice how the DOD format benefits from the efficiency of Python dictionaries and is the overall fastest option for many tasks under study. The CSR format has a similar albeit slightly worse performance, except for listing neighbors and matrix-Task CSR DOK DOD Check (u, v) ∈ E 3.10 -5 2.10 -5 6.10 -6 Add node u 5.10 -5 2.10 -4 2.10 -6 Delete node u 3.10 -3 7.10 1 5.10 -3 Add edge (u, v) 5.10 -3 2.10 -5 6.10 -6 Delete edge (u, v) 1.10 -3 3.10 -5 1.10 -5 List neighbors of u 2.10 -6 4.10 -3 1.10 -4 Matrix-vector product 2.10 -3 2.10 0 1.10 0 vector products, while the DOK format performs significantly worse than either on some tasks. The DOD format is especially well-suited for adding and deleting edges and nodes alike. On these tasks it is about one order of magnitude faster than the CSR and DOK formats except for the deletion of nodes. As found in Table 2.3, the CSR format is the most memory-efficient format especially when compared to its dictionary-based counterparts.

In choosing a format for our experiments, the CSR format is our preferred option because it offers the best memory footprint and is very well-suited for algebraic operations while also having a good performance for selected graph primitives. The CSR format formally represents the adjacency matrix of the graph, however, it also retains a number of characteristics expected from adjacency list and incidence matrix representations. Indeed, like adjacency lists, it makes it possible to access the neighborhood of a node in constant time.

On the other hand, like incidence matrices, it is easy to find if node i is adjacent to the j-th edge provided that the ordering of the edges is that of the indices array.

Guidelines for the package

In designing Scikit-network, we set out a number of goals and features we seeked to achieve. We mention them below and describe how they impact day-to-day work on the package.

Open-source software. The package is hosted on GitHub 3 and is part of SciPy kits aimed at creating open-source scientific software. Its BSD license enables maximum interoperability with other software. Contributions are encouraged and guidelines for contributing are described in the documentation of the package 4 and guidance is provided by the GitHubhosted Wiki.

Sustainable performance. Scikit-network relies on a very limited number of external dependencies for ease of installation and maintenance. Only SciPy and NumPy are required on the user side.

• Many elements from SciPy are used for both high performance and simple code.

The sparse matrix representations allow for efficient manipulation of large graphs as discussed in Chapter 2 while linear algebra solvers are used in many algorithms. Scikit-network also relies on the LinearOperator class for efficient implementation of certain algorithms.

• NumPy arrays are used through SciPy's sparse matrices for memory-efficient computations. NumPy is used throughout the package for the manipulation of arrays. Some inputs and most of the outputs are given in the NumPy array format.

• In order to speed up execution times, Cython [START_REF] Behnel | Cython: The best of both worlds[END_REF] generates C++ files automatically using a Python-like syntax. Thanks to the Python wheel system, no compilation is required from the user on most platforms. Note that Cython has a built-in module for parallel computing on which Scikit-network relies for some algorithms. Otherwise, it uses Python's native multiprocessing.

Note that all three packages are well-established within the Python ecosystem. Their mostly stable APIs make it possible to avoid unnecessary changes to the code.

Code quality and availability. To ensure that the library is bug-free, a number of tests are defined for each new algorithm and feature. Code quality is then assessed by standard code coverage metrics [START_REF] Bacchelli | Expectations, outcomes, and challenges of modern code review[END_REF]: the coverage is the proportion of code lines that are executed when running the tests. Today's coverage is at 99% for the whole package. Note that this coverage metric is a rough one (in particular, it does not denote how relevant tests are). In practice, special attention is given to identifying and testing pathological cases when implementing new features.

As a general rule of thumb, the package should work with the latest versions of its dependencies in order to avoid the use of obsolete features. Requirements are thus kept up to date thanks to IDE assistance. Scikit-network relies on GitHub Actions for continuous integration (i.e. testing and deploying code) and cibuildwheel for deploying on common platforms (i.e. building wheels for each platform so that no compilation is required on the user side). OSX, Windows and most Linux distributions [START_REF] Mcgibbon | A platform tag for portable linux built distributions[END_REF] are supported for Python versions 3.7 and newer.

The amount of work spent ensuring that coverage remains high and that the package is available on all platforms cannot be understated. Documentation. Scikit-network is provided with a complete documentation 4 . The API reference presents the syntax while the tutorials present applications on real graphs. Algorithms are documented with relevant formulas, specifications, examples and references, when relevant. This documentation aims at enabling users to have a quick grasp of the usage of each function. The quality of the documentation is easily as important as that of the code itself as the former is the main enabler for a proper use of the latter.

The documentation is built from structured comments in the code itself and files describing how the documentation is organized. Tutorials are built from Jupyter notebooks which are executed when the documentation is being built. All functions and classes of Scikit-network are documented, most appear in the documentation and all methods have a tutorial attached.

Code readability. The source code follows the stringent PEP8 guidelines. Explicit variable naming and type hints make the code easy to read. The number of object types is kept to a minimum. Those readability guidelines aim at facilitating the review and addition of code to the package. Indeed, it makes it easier to fix faulty code or to repurpose it. In particular, when new contributions are made, it provides a common set of conventions for newcomers while allowing reviewers to provide feedback faster.

Data collection. The package offers multiple ways to fetch data. Some small graphs are embedded in the package itself for testing or teaching purposes. Part of the API makes it possible to fetch data from selected graph databases easily. Both of these options are of particular interest when implementing or benchmarking new algorithms or showcasing existing ones. Parsers are also present to enable users to import their own data and save it in a convenient format for later reuse. Those parsers make it possible to apply the algorithms of Scikit-network on proprietary data.

With this goal of broad data collection in mind, we also introduce the NetSet repository. Although not part of the Scikit-network package, the NetSet5 repository is one of the two databases with a dedicated import function available (the other one being Konect). It is also maintained by the Scikit-network team. It gathers some common networks of the literature such as 20NewsGroup but also some original datasets such as the US Senate, US House of Representatives and French National Assembly graphs. Unlike imports from Konect that require at least an initial parsing of TSV files, importing datasets from the NetSet repository benefits from downloading files in the dedicated NumPy, SciPy and Pickle formats which allows for gains in both memory (and thus download size) and overall runtimes for the import command.

Performance

To show the performance of Scikit-network, we compare the implementation of some representative algorithms with those of the graph softwares of Table 2.1:

• the Louvain clustering algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], with the tolerance parameter set at 10 -3 when available

• PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], the number of iterations is set to 100 when possible (that is for all packages except iGraph)

• HITS [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF] • the spectral embedding (Belkin and Niyogi, 2003) We also give in Table 2.6 the memory usage of each package when loading the graph. Thanks to the CSR format, Scikit-network has a minimal footprint.

Conclusion

We introduced Scikit-network, a Python library for graph analysis. We illustrated how competitive it was compared to other libraries without sacrificing its ease-of-use and described the main guidelines we set when developing it. It should be noted that the performance of Scikit-network does come with one notable string attached: all operations are done in RAM and it is expected that RAM is the limiting factor to what can be achieved with the package. Nevertheless, thanks to the efficient CSR format, even a common laptop can handle large graphs as seen in the experiments. Machines with hundreds of gigabytes of RAM (like the one used in the experiments of Chapter 4), while uncommon, are not unheard of and make it possible to tackle real-world graphs with billions of edges.

In the future, the library could benefit from a new graph format to either overcome some of the downsides of the CSR format mentioned in Chapters 3 and 4 or tackle new problems. For instance, the topic of dynamic graphs (i.e. graphs whose nodes and edges may appear and disappear over time) is of particular interest. Results displayed in Section 2.3.1 then suggest that formats such as the DOD one may be better suited.

Chapter 3

Node clustering

Introduction

Node clustering is a common task in graph mining. It consists in partitioning the node set V of a graph G = (V, E) in such a way that nodes in the same group are closer in some sense than to those in other groups. Each such group is called a cluster or community and clustering is also known as community detection. In this chapter we review different forms of clustering, defined by their outputs:

• flat clustering, where each node is assigned exactly one cluster. In this case, we review selected variations of the Louvain method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], a well-known algorithm for flat node clustering. We compare those and introduce a novel variant.

• hierarchical clustering, where each node is a leaf in a tree designed so that close leaves correspond to close nodes in the original graph.

Node sampling

A natural notion of proximity between nodes is through node sampling. Let A be the adjacency matrix of an undirected graph. Consider the sampling of node pairs through the edges. Each (ordered) node pair (i, j) is then sampled with probability:

s(i, j) = A ij 2w
where w is the total weight of the graph. This is a symmetric joint distribution with marginal distribution:

s(i) = ∑ j∈V s(i, j) = d i 2w
Then, the probability of sampling j given that i is sampled is:

s(j|i) = s(i, j) s(i)
We say that node j is close to node i if the probability of sampling node j given the sampling of node i is much higher than the probability of sampling node j. This yields the following similarity for nodes i and j:

σ(i, j) = s(j|i) s(j) = s(i, j) s(i)s(j)
Note that σ is symmetric. This sampling distribution and the derived similarity are used in the following sections.

Flat clustering

The flat clustering of a graph G is given as a partition of its node set V. Formally, the

clustering of G is (C k ) k∈C such that, ∀k = l, C k ∩ C l = ∅ and k C k = V. Conversely, we define the cluster c i of any node i ∈ V as c i = k if i ∈ C k .
In this section, we will focus on the Louvain method, the modularity functions it optimizes and its variants.

Similarity measures

In order to assess the quality of a clustering, it is useful to compare it to the ground truth of the dataset under study whenever available. This requires to be able to compare any pair of clusterings. While it is trivial to check if two clusterings are equal, quantifying how different they are is more difficult.

To that end, we will go over:

• the Rand index measure defined by [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] • the homogeneity and completeness scores defined by [START_REF] Rosenberg | V-measure: A conditional entropy-based external cluster evaluation measure[END_REF] Note that the choice of those two similarity measures is far from exhaustive [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF][START_REF] Yang | A comparative analysis of community detection algorithms on artificial networks[END_REF].

We denote the ground truth by G and a clustering to which it should be compared by C. We say that i is in class

(resp. cluster) k if i ∈ G k (resp. i ∈ C k ).
Let n be the number of nodes, we pick a random node X and consider the random variables g x and c X , the class and the cluster of X.

Homogeneity and completeness

One way to assess how close C is to G is to check that any cluster corresponds to at most one class. Whenever this is the case, we say that C is homogeneous with respect to G.

Definition 1. C is homogeneous with respect to G, if ∀l, ∃!k, C l ⊂ G k .
Conversely, another way to assess how close C is to G is to check that any class corresponds to at most one cluster. This property is called completeness and is immediately linked with homogeneity by switching the roles of C and G.

Definition 2. C is complete with respect to G, if G is homogeneous with respect to C.
Note that if C is both complete and homogeneous with respect to G, then C and G are identical (up to their numbering).

Rand index

The Rand index is defined as the proportion of node pairs (i, j) whose classes and clusters are either both equal, i.e. c i = c j and g i = g j or different, i.e. c i = c j and g i = g j . By definition, the Rand index is thus bounded by 0 (when C and G do not agree on a single node pair) and 1 (when the two clusterings are identical).

We give a closed formula for the Rand index RI:

Proposition 1. n 2 RI = n 2 + |G| ∑ k=1 |C| ∑ l=1 |G k ∩ C l | 2 - 1 2 |G| ∑ k=1 |G k | 2 + |C| ∑ l=1 |C l | 2
Proof. We use Kroenecker symbols to count pairs where C and G agree:

n 2 RI = ∑ 1≤i<j≤n δ g i g j δ c i c j + (1 -δ g i g j )(1 -δ c i c j ) 2 n 2 RI + n = ∑ 1≤i,j≤n 1 + 2δ g i g j δ c i c j -δ g i g j -δ c i c j Note that ∑ 1≤i,j≤n δ g i g j = ∑ 1≤i,j≤n ∑ |G| k=1 δ g i k δ g j k = ∑ |G| k=1 |G k | 2 .
Using similar reasoning for the two other sums yields:

2 n 2 RI + n = n 2 + 2 |G| ∑ k=1 |C| ∑ l=1 |G k ∩ C l | 2 - |G| ∑ k=1 |G k | 2 - |C| ∑ l=1 |C l | 2
Hence the result.

The Rand index gives an easily interpretable result thanks to a very simple definition. One noticeable downside of the Rand index is that two random clusterings may have a high score. If their number of clusters is high for instance, all but the ( n 2 ) term in Proposition 1 vanish. To correct this issue, one can account for chance by substracting the expected value of the Rand index [START_REF] Hubert | Comparing partitions[END_REF]. This measure is called the adjusted Rand index (ARI).

V-measure Homogeneity translates nicely in terms of entropy as G is then entirely determined by C. Let:

H(g X |c X ) = - |G| ∑ k=1 |C| ∑ l=1 |G k ∩ C l | n log |G k ∩ C l | |C l |
When C is homogeneous with respect to G, H(g X |c X ) = 0. This is normalized so that we have a score between 0 and 1 with 1 being reached whenever there is homogeneity. As H(g X |c X ) is bounded by 0 and H(g X ) (whenever g x and c X are independent), we define the homogeneity score of C with respect to

G as h G (C) = 1 -H(g X |c X )
H(g X ) . Note that the trivial partition where each node is in its own cluster is homogeneous with respect to any partition.

Conversely, we define the completeness score m G (C) of C with respect to G as m G (C) = h C (G). Note that the trivial partition where all nodes are in the same cluster is complete with respect to any partition.

The V-measure score is defined as the harmonic mean of the homogeneity and the completeness scores.

Modularity functions

In this section, we define the different modularity functions used for graph clustering and present some of their properties.

Consider a graph G = (V, E), a probability distribution p over V × V and two probability distributions q r and q c over V (for the rows and columns). A modularity function, given a resolution parameter γ, can be written in its general form as:

Q = ∑ i,j∈V p ij -γq r i q c j δ c i c j (3.1)
The modularity can then be interpreted as the difference between the probability of sampling a node pair inside a cluster using an edge sampling distribution and the probability of sampling the same pair using two node samplings. Maximizing the first term has a trivial solution in which all nodes are in one cluster. On the other hand, minimizing the second term has a trivial solution in which there are as many clusters as there are nodes (i.e. one node per cluster). The modularity is thus a balance between those two competing terms. In the literature, the resolution parameter may be absent, this is equivalent to having γ = 1. Equation (3.1) can be rewritten into an aggregated form by summing cluster by cluster:

Q = ∑ k∈C (P k -γQ k ) (3.2)
where P k = ∑ i,j∈C k p ij is the probability of sampling a pair of nodes in cluster k according to distribution p. Likewise, we define Q k = ∑ i,j∈C k q r i q c j . Note that there exists other modularity functions than the ones we list in this section. In particular, some may not be written in the form of Equation (3.1) [START_REF] Campigotto | A generalized and adaptive method for community detection[END_REF].

Undirected graphs. One of the most simple choices of p, q r and q c for undirected graphs is p ij ∝ ✶ {ij∈E} and q r i , q c i ∝ 1, which gives the following aggregated form:

Q P = ∑ k∈C |E k | m -γ |C k | 2 n 2 (3.3)
where E k is the set of edges between nodes of C k .

We call this function the Potts modularity because of its link to the constant Potts model.

Note that maximizing

Q P is equivalent to maximizing ∑ k∈C |E k | -γ m n 2 |C k | 2 . Traag et al. (2011) suggests using γ ′ = γ m n 2 .
They describe the following aggregated form:

Q T = ∑ k∈C |E k | -γ ′ |C k | 2 (3.4)
This can be interpreted depending on γ ′ . |C k | 2 is the maximum number of edges that can be found within cluster k, for 0 ≤ γ ′ ≤ 1, γ ′ |C k | 2 is the expected number of edges within that cluster and γ ′ is the target density inside each cluster (whereas m n 2 is the mean density for the whole graph). γ denotes how much bigger the intra-cluster density should be compared to the mean density. We typically need γ > 1.

The most common choice of p,q r and q c for undirected graphs is found in [START_REF] Newman | Modularity and community structure in networks[END_REF]. They are set so that p ij ∝ A ij and q r i , q c i ∝ d i (recall that whenever the graph is weighted, d i denotes the sum of the weights of edges incident to node i rather than its degree):

Q N = ∑ i,j∈V A ij 2w -γ d i d j (2w) 2 δ c i c j (3.5)
Note that the latter modularity and that of Equation (3.3) coincide on unweighted regular graphs (i.e. unweighted graphs where all nodes have the same degree). In light of the sampling distribution defined in Section 3.1.1, we rewrite Q N as:

Q N = ∑ i,j∈V (s(i, j) -γs(i)s(j)) δ c i c j
Intuitively, the modularity is high whenever the probability of sampling an edge whose ends are both within a cluster is higher than picking two nodes within that cluster independently. In particular, this is expected when there are many edges within clusters compared to the number of edges between distinct clusters. Alternatively, the aggregate form of Equation (3.5) is:

Q N = ∑ k∈C w k 2w -γ v k 2w 2 with w k = ∑ i,j∈C k A ij and v k = ∑ i∈C k d i , the volume of cluster k. Notice that the first term ∑ k∈C w k
2w is exactly the proportion of the edge weights that is within the clusters. The second term ∑ k∈C v k 2w 2 is minimal when all clusters have the same volume (it is then equal to the inverse of the number of clusters) and maximal when there is only one cluster which has volume v k = 2w (it is then equal to 1).

Directed graphs. The modularity defined in Equation (3.5) is naturally extended to directed graphs. To do so, [START_REF] Dugué | Directed Louvain: maximizing modularity in directed networks[END_REF] suggests

p ij ∝ A ij , q r i ∝ d + i and q c i ∝ d - i : Q D = ∑ i,j∈V A ij 2w -γ d + i d - j (2w) 2 δ c i c j (3.6)
Bipartite graphs. Likewise, in the case of bipartite graphs, [START_REF] Barber | Modularity and community detection in bipartite networks[END_REF] proposed to use

p ij ∝ B ij , q r i ∝ d r i and q c i ∝ d c i where (i, j) ∈ V 1 × V 2
and d r and d c are the degree vectors for the rows and the columns of the biadjacency respectively. This leads to the bimodularity function:

Q B = ∑ i∈V 1 ,j∈V 2 B ij 2w -γ d r i d c j (2w) 2 δ c i c j (3.7) Let A = 0 B 0 0 ∈ M n 1 +n 2 (R)
be the adjacency matrix of the graph, seen as a directed one. The bimodularity on B coincides with the directed modularity defined in Equation (3.6) on A as the in-and out-degree d -and d + of A can be written respectively as 0 d c and d r 0 .

The Newman modularity of Equation 3.5 can also be used on bipartite graphs (without taking the particular structure of the graph into account). The corresponding undirected graph has the following adjacency matrix:

A = 0 B B T 0 ∈ M n 1 +n 2 (R)
Aggregation properties. We now define the aggregation of a graph G = (V, E) along a clustering C. This results in a graph Ĝ = ( V, Ê) where V = {1, . . . , |C|} (i.e., there is one node in the aggregated graph for each cluster in C) and the weight of edge (i,

j) is Âkl = ∑ i,j∈C k ×C l A ij .
Modularity functions are all compatible with aggregation based on a clustering of the graph. The corresponding conservation property is key to the efficiency of the Louvain method described in Section 3.2.3 (general conditions for a good integration with Louvain are discussed in [START_REF] Campigotto | A generalized and adaptive method for community detection[END_REF]). Here, we give a generalization of that property. Recall the homogeneity property defined in Definition 1. Let C and C ′ be two clusterings of a graph, if C ′ is homogeneous with respect to C, C can also be aggregated along C ′ . This results in a partition Ĉ of |C ′ |-sets such that each element in Ĉk corresponds to a cluster of

C ′ that is included in C k . Proposition 2. Given a graph G = (V, E) and two clusterings C and C ′ of G such that C ′ is homogeneous with respect to C, consider the graph G ′ = (V ′ , E ′ ) and the clustering Ĉ of G ′ obtained by aggregating G and C along C ′ . The modularity of clustering C on G is equal to the modularity of Ĉ on G ′ . Proof. Let Y ′ ∈ R n×|C ′ | (resp. Ŷ ∈ R |C ′ |×| Ĉ| ) be the membership matrix for the clustering C ′ (resp. Ĉ), i.e. Y ik = 1 if node i ∈ V is in cluster C ′ k (resp. Ĉk ) and 0 otherwise. Note that the membership matrix Y of C satisfies Y = Y ′ Ŷ. Let A ′ = Y ′T AY ′ be the adjacency matrix of G ′ .
To simplify notations, let d (resp. f ) denote the out-weight (resp.in-weight) vector of A and let w denote the total weight of the graph. We have:

d ′ = A ′ 1 = Y ′T AY ′ 1 = Y ′T d f ′ = A ′T 1 = Y ′T A T Y ′ 1 = Y ′T f w ′ = 1 T A ′ 1 = 1 T Y ′T AY ′ 1 = 1 T A 1 = w Hence, p ′ ij = (Y ′T pY ′
) ij and q r ′ i q c′ j = (Y ′T q r q cT Y ′ ) ij hold for all the probability distributions listed above:

Q(C) = ∑ i,j∈V p ij -γq r i q c j δ c i c j = ∑ i,j∈V p ij -γq r i q c j Y T i Y j = Tr Y T p -γq r q cT Y = Tr ŶT Y ′T p -γq r q cT Y ′ Ŷ = Tr ŶT Y ′T pY ′ -γY ′T q r q cT Y ′ Ŷ = ∑ i,j∈V ′ p ′ ij -γq r ′ i q c′ j ŶT i Ŷj = ∑ i,j∈V ′ p ′ ij -γq r ′ i q c′ j δ ĉi ĉj
Property 2 is used in Section 3.2.4. In particular, Figure 3.1 illustrates two partitions of the nodes such that one (in 3.1b) is homogeneous to the other (in 3.1a) and how the graph and the initial partition are partially aggregated (in 3.1d) along a refined partition.

The following property is an immediate consequence of the former for C = C ′ :

Proposition 3. Given a graph G = (V, E) and a clustering C of G, consider the graph Ĝ = ( V, Ê)
obtained by aggregating along C. The modularity of clustering C on G is equal to the modularity of the trivial partition where each node is in its own cluster on Ĝ.

Proposition 3 is the commonly given conservation property for the Louvain method.

Louvain method

We now describe the Louvain method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] and how the modularity functions described above allow it to be a scalable approach to clustering. When it was first introduced, only the modularity for undirected networks from Equation (3.5) was mentioned. However, the general idea can be applied to any type of objective function that satisfies the aggregation property as described in Proposition 3 and that allows for the variation of its value due to a cluster change to be computed easily.

The Louvain method consists of two phases: optimization and aggregation (described respectively in Algorithms 1 and 2). In Algorithm 1, MOD denotes the modularity function and MOVE(G, C, u, k) denotes the partition of G obtained from C by setting c u to k. In Algorithm 2, MEMBERSHIP(C) is the membership matrix Y for some partition C, i.e. Y iu = 1 if node i is in cluster u under C and 0 otherwise.

The optimization phase consists in visiting all the nodes of the graph repeatedly and moving them to a neighboring community whenever it induces an increase in modularity greater than some tolerance ǫ. The tolerance parameter ǫ is the only one that needs to be set. Empirically, we find that ǫ = 10 -3 offers a reasonable trade-off between the quality of the results and time performance. It is the value that is used in the experiments. It should be noted that the optimization is deterministic up to the order in which the nodes are visited.

After optimization, a partition C which locally optimizes the modularity is obtained. The next step is to aggregate G with respect to C. Once the graph is aggregated, another optimization phase begins and the two phases are repeated until aggregation does not change the graph.

The modularity increases with each local update performed in the optimization phase and remains the same during the aggregation phase according to Proposition 3. As the modularity is upper-bounded, the Louvain method converges towards a local maximum of the modularity.

The efficiency of the Louvain method relies on easily finding the best local cluster for each node (i.e. the cluster that induces the largest increase in modularity). This, in turn, depends on having a simple local update formula for the modularity when node i is moved from cluster c i to c j . The corresponding variation in modularity ∆Q satisfies:

∆Q = ∑ k (∆P k -γ∆Q k ) = (∆P c i -γ∆Q c i ) + ∆P c j -γ∆Q c j
Only clusters c i and c j are affected. Choosing the best target community thus depends on ∆P c j -γ∆Q c j whenever at least one community yields an increase in modularity.

Algorithm 1: OPTIMIZATION

Input: A graph G = (V, E), a tolerance ǫ Output: A partition of V for u ∈ V do C u ← {u} end repeat C ′ ← C for u ∈ V do Q = MOD (G, C) l = argmax v∈N (u) MOD (G, MOVE (G, C, u, c v )) ∆Q ← MOD (G, MOVE (G, C, u, c l )) -Q if ∆Q > ǫ then C ← MOVE (G, C, u, c l ) end until C = C ′ return C Algorithm 2: AGGREGATION Input: The adjacency A of a graph G, a partition C of G Output: The adjacency A ′ of the aggregated graph G ′ Y ← MEMBERSHIP(C) A ′ ← Y T AY return A ′
In the case of Equation (3.1):

∆P c i = 2p ii - ∑ j∈C c i ∩N (i) p ij + p ji ∆P c j = ∑ j ′ ∈C c j ∩N (i) p ij ′ + p j ′ i
where N (i) is the neighborhood of node i. Furthermore, we write

Q k = Q r k Q c k where Q r k = ∑ i∈C k q r
i is the probability of sampling a node in cluster k under q r and similarly for Q c . Then:

∆Q c i = q c i (q r i -Q r c i ) + q r i (q c i -Q c c i ) ∆Q c j = q c i Q r c j + q r i Q c c j
To illustrate how the different modularity functions differ, we run the Louvain method using the modularity functions described in Section 3.2.2 on the WikiVitals dataset. It is built from an extraction of Wikipedia and comprises the adjacency matrix of the hyperlink graph of the extracted articles and a bag-of-words biadjacency of the text in the articles (one node set is the articles, the other is the words they contain). For the biadjacency, a source article and a target word have an edge between them if the former contains the latter, then the weight of the edge is the number of occurences of the word in the article.

We use the V-measure and adjusted Rand scores [START_REF] Rosenberg | V-measure: A conditional entropy-based external cluster evaluation measure[END_REF][START_REF] Hubert | Comparing partitions[END_REF] described in Section 3.2.1. We report the results for the hyperlinks adjacency in Table 3.1 and those for the bag-of-words biadjacency in Table 3.2. We remove the somewhat ambiguous "People" class of the dataset, leaving 10 classes in the ground truth. We find that the Newman, Dugué and Barber modularities offer very similar performance. The Potts modularity does not use the weights of the graph and is expectedly the worst option. This is especially true in the case of the bag-of-words biadjacency where both scores are low.

Leiden refinements

Many variants of the Louvain method have been proposed in recent years [START_REF] De Meo | Generalized louvain method for community detection in large networks[END_REF][START_REF] Bhowmick | A template for parallelizing the louvain method for modularity maximization[END_REF][START_REF] Que | Scalable community detection with the louvain algorithm[END_REF]. Among those, one notable variant called the Leiden algorithm has been proposed [START_REF] Traag | From louvain to leiden: guaranteeing well-connected communities[END_REF]. It consists in a collection of three separate improvements of the original Louvain method:

• The smart local move (SLM) [START_REF] Waltman | A smart local moving algorithm for large-scale modularity-based community detection[END_REF] alters the aggregation phase. After every optimization phase, the Louvain method is run recursively on each subgraph corresponding to a cluster. This yields a new "refined" clustering for each subgraph which is concatenated into a clustering for the whole graph. This clustering is the one that is used to aggregate the graph whereas the original clustering is used to initialize the value of the partition at the start of the next optimization phase. We illustrate this process in Figure 3.1. Note that thanks to Proposition 2, the monotony of the modularity is still guaranteed as the refined clustering is homogeneous with respect to the original clustering. It is clear however that using a singleton partition (i.e. that of step 3.1c) with each node in its own cluster in the aggregated graph would lower the modularity (compared to that of step 3.1d).

• The random local move (RLM) [START_REF] Traag | Faster unfolding of communities: Speeding up the louvain algorithm[END_REF] reduces the number of computations for modularity updates. To do so, for each node visited during the optimization phase, it picks a random neighbor instead of looking at the whole neighborhood. If moving the node under study to this neighbor's community increases the modularity, then it is done. Otherwise, another node is visited.

• The fast local move (FLM) or Louvain Prune [START_REF] Ozaki | A simple acceleration method for the louvain algorithm[END_REF] reduces the number of nodes visited during the optimization phase. Instead of iteratively considering all the nodes of the graph until the modularity does not increase any more, it maintains a queue to which only the neighbors of moved nodes that are in a different community are added.

It should be noted that the Leiden algorithm does not use those improvements in the way they are described by their respective authors.

Additionally, we propose a novel refinement for the Louvain algorithm which we name chained local move (CLM). It aims at speeding up the first optimization phases by reducing the number of modularity increase computations. In order to do so, instead of finding the best possible increase for each node, this is done for one initial node. If the initial node is moved to another community, a neighbor whose community is different from this new community is picked at random. If moving this neighbor to the initial node's new community increases the modularity, it is done and a neighbor of the node moved last is picked. A chain of neighbors is then built from the initial node. This chain ends when moving a node does not increase the modularity or no neighbor can be picked. We give the pseudo-code for the optimization phase of the CLM in Algorithm 3 where RANDOMPOP S picks a node uniformly at random from the set passed as its input and removes it from S.

We compare the benefits of each of the variants in terms of modularity (using the one defined in Equation (3.6)) and time performance. We report the performance of the standard Louvain (as "Baseline") and the variants under study in Tables 3.4, 3.5, 3.6 and 3.7.

Input: A graph G = (V, E), a tolerance ǫ Output: A partition of V for u ∈ V do C u ← {u} end repeat C ′ ← C S ← {1, . . . , |V|} while S = ∅ do u ← POP(S) l = argmax v∈N (u) MOD (G, MOVE (G, C, u, c v )) ∆Q ← MOD (G, MOVE (G, C, u, c l ))-MOD (G, C) while ∆Q > ǫ do C ← MOVE (G, C, u, c l ) u ← RANDOMPOP S ((N (u) ∩ S) \ C c l ) ∆Q ← MOD(G, MOVE(G, C, u, c l ))-MOD (G, C) end end until C = C ′ return C
In each table, we report the best absolute value in bold and otherwise display the relative errors to that value. The experiments are run on a computer running Debian 10 OS and equipped with an AMD Ryzen Threadripper 1950X 16-Core Processor and 128 GB of RAM. We run the experiments on the graphs described in Table 3.3 where the number of classes in the ground truth is given if available (in the results, the 'Wiki-' prefix is dropped for readibility).

Considering the SLM algorithm, we notice that it is consistently the slowest option, sometimes up to three times as slow as the standard method. This poor time performance is due to the costly extraction of many subgraphs for the partition refinement. This operation is slow because of the CSR format described in Chapter 2. It should be noted however, that the SLM algorithm makes up for its speed by returning partitions that have a higher modularity on large datasets. It also offers a good performance in terms of V-measure on smaller ones although not in terms of ARI score.

Looking at the RLM variant, note that it is almost always the fastest option at the cost of decreased modularity values. The time gains are not consistent as illustrated by the Orkut graph where it is noticeably slower than the baseline while giving the worst clustering compared to the other options. Nevertheless, it sometimes offers interesting time gains as seen on the UK Domain dataset where its modularity is close to the baseline. It also performs fairly well in terms of V-measure on smaller datasets but this is not the case in terms of ARI score.

The baseline and the RLM variant in terms of execution times. One exception in our benchmark is the Orkut graph where the FLM variant is even faster than the RLM variant. Unlike the RLM variant, the modularity, V-measure and ARI reached by the FLM algorithm is consistently equal or almost equal to that of the baseline. It is thus a simple way to speed up the Louvain method without noticeable downsides.

The CLM variant appears as an intermediate option between the baseline and the RLM variant in terms of time/modularity trade-off. The modularity of the clusterings it returns are consistently higher than that of the RLM while still lower than that of the baseline. As regards execution times, depending on the dataset at hand, it can be either faster or slower than both the RLM variant and the baseline. It is notably the fastest option on the Orkut and UK Domain datasets and the slowest on the Twitter graph. On smaller datasets, it is close to the baseline in terms of V-measure and the best performer in terms of adjusted Rand score.

Hierarchical clustering

Many graph datasets have a multi-layered community structure. Hierarchical clustering is a set of cluster analysis methods which seeks to build a hierarchy of clusters. Methods for hierarchical clustering generally fall into two categories:

• agglomerative approaches, where each node starts in its own cluster and pairs of clusters are successively merged to obtain just one cluster

• conversely, divisive approaches consist in successive splits of an initial cluster containing all nodes

Dendrograms

Hierarchical clusterings are presented in the form of a tree structure called a dendrogram.

In addition to the tree structure, nodes in the tree have a height attribute (with the leaves being at height 0 and the root having the highest height).

To obtain a flat clustering from a dendrogram, we make a cut of it. For instance, a straight cut with k clusters consists in looking at the graph after the nk first merges (starting from the leaves, in increasing order of height) have been made. An example is given in Figure 3.2 where the cut of the dendrogram in Figure 3.2a corresponds to the flat clustering seen in Figure 3.2b.

Agglomerative approach

We describe the hierarchical clustering method proposed in Bonald et al. (2018a). Consider the similarity defined in Section 3.1.1 on an undirected graph G, a simple agglomerative approach is to find the pair of nodes with the highest similarity and merge them. Iterating this process suffices to build a hierarchical clustering of a graph. We note i ∪ j the result of merging nodes i and j. In order to iterate the merges, we look at how the sampling distribution s and the similarity σ are affected. Let i, j, k ∈ V be distinct:

s(i ∪ j, k) = A ik + A jk 2w = s(i, k) + s(j, k)
and v remains unchanged, so that:

s(i ∪ j) = s(i) + s(j)
Then:

σ(i ∪ j, k) = s(i, k) + s(j, k) (s(i) + s(j))s(k) = s(i) s(i) + s(j) σ(i, k) + s(j) s(i) + s(j) σ(j, k) (3.8)
This equation makes it possible to update the values of σ each time two nodes are merged.

In order to have a complete clustering of the graph, n -1 merge have to be performed. For each merge, the node pair with the highest similarity has to be found, this requires O(m) operations if done naively. However using a walk on the graph to find reciprocating nearest-neighbors suffices to merge two nodes even if this pair does not reach the global maximum in similarity [START_REF] Murtagh | Algorithms for hierarchical clustering: an overview[END_REF]. This is due to one property of the similarity σ whose inverse defines a reducible distance on the node set:

Proposition 4. ∀k = i, j, σ(i ∪ j, k) -1 ≥ min σ(i, k) -1 , σ(j, k) -1
The walk (starting from a random node) then consists in successively visiting the neighbor of the current node that is nearest in terms of similarity. Two nodes can be merged whenever the successor of a node in the walk is also its predecessor. After each merge, the similarity is updated using Equation (3.8). When the whole graph has been merged, the obtained dendrogram is binary and the heights of the merges are defined by the distance σ(i, j) -1 .

In the case of directed graph, the sampling distribution s(i, j) is no longer symmetric. We thus define s + (i) = ∑ j∈V s(i, j) and s -(i) = ∑ j∈V s(j, i), two marginal distributions corresponding to the normalized in and out degrees the nodes. This enables us to define a new symmetric distribution:

t(i, j) = s + (i)s -(j) + s -(i)s + (j)
and a new similarity:

τ(i, j) = s(i, j) + s(j, i) t(i, j)
An equivalent of Equation (3.8) is:

τ(i ∪ j, k) = t(i, k) t(i, k) + t(j, k) τ(i, k) + t(j, k) t(i, k) + t(j, k) τ(j, k)
The distance defined by the inverse of τ(i, j) is also reducible.

Divisive approach

A simple divisive approach for hierarchical clustering consists in recursively applying a flat clustering method. After each time such a method is applied, one can extract subgraphs corresponding to each cluster and start again until each node is in its own cluster. Here, we will consider the Louvain method described in Section 3.2.3. This recursive method is the one described by [START_REF] Bhowmick | Lou-vainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF] where the same hierarchy to build an embedding (see Chapter 4). The dendrogram is not a binary tree in that case. Merge heights are determined by the depth in the recursion (i.e. the first clustering pass is at the root of the dendrogram).

Experiments

We run the agglomerative and divisive approaches on the Karate Club graph as illustrated in Figures 3.3 and 3.4. We make a cut of each dendrogram with 4 clusters. The dendrogram of the agglomerative approach is densely packed at the leaves as the last few merges have a low similarity (i.e. a high distance). On the other hand, the divisive approach has a more spread out shape as the height information is built (somewhat arbitrarily) based on the recursion depth of the flat clustering method.

Notice how, despite having very different dendrograms (as seen in Figures 3.3a and 3.4a), the resulting flat clustering when cutting for 4 clusters is vastly similar (Figures 3.3b and 3.4b).

There are some cases where the data at hand is inherently hierarchical in that its labeling has a tree structure. Hierarchical clustering makes it possible to refine the existing hierarchy in such a situation.

Conclusion

In this chapter, we described some well-established methods for both flat and hierarchical node clustering. In particular, we considered variants of the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] and compared their performances. We also introduced a novel variant, the Chained Local Move (CLM) which aims at speeding up the initial optimization phases of the algorithm. We notice that the variants under study cover a fairly wide spectrum in terms of time performance and modularity. This could prove useful as one can choose a variant depending on the desired time/modularity trade-off.

Further work could focus on further speeding up the costly initial optimization phase of the Louvain algorithm. Indeed, this initial phase is the heaviest in terms of computations as many communities have to be considered for most of the nodes in the standard Louvain. We feel there is still room for improvement in terms of alleviating the cost of those computations.

Chapter 4

Node embedding

Introduction

In the context of network mining, a number of tasks can be performed by exploiting the graph structure of the data under study. Such tasks include the clustering, as illustrated by the Louvain method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], or ranking, as illustrated by PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] and other centrality measures [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF][START_REF] Brandes | A Faster Algorithm for Betweenness Centrality[END_REF], of the nodes of the graph. However, it is also possible to apply other methods that perform the same tasks but operate on vector data by embedding each node of the graph into a vector of R d in a way that preserves some of the properties of the graph. For instance, a "good" embedding of the nodes should make neighbors in the graph closer in terms of distance in R d .

Motivation

There exists many methods for the embedding task [START_REF] Hamilton | Representation learning on graphs: Methods and applications[END_REF], using a variety of techniques ranging from random projections [START_REF] Zhang | Billion-scale network embedding with iterative random projection[END_REF] to skip-gram models [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF]. Some techniques are unsupervised [START_REF] Bhowmick | Lou-vainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF] while others are supervised or semi-supervised [START_REF] Kipf | Semi-Supervised Classification with Graph Convolutional Networks[END_REF]. While most methods put an emphasis on the relevance of the embedding, some also focus on the scalability of the process on large graphs [START_REF] Zhang | Prone: Fast and scalable network representation learning[END_REF].

In this chapter, we introduce a method that builds upon the qualities of the Louvain method for clustering the nodes of a graph [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. This method is:

• scalable, as it adds little to no overhead to the execution of the Louvain clustering method

• mostly parameter-free, as the Louvain method only has one tolerance parameter and we fix the resolution parameter to γ = 1. In particular, there is no need to set the embedding dimension d.

• unsupervised, as the Louvain method is also unsupervised

• interpretable, the underlying clustering makes it possible to describe each axis of the embedding space (see section 4.4.1).

To demonstrate the scalability and the effectiveness of this method, we run experiments against five competing algorithms on large and very large graphs.

Related work

Network embedding methods make use of a large variety of techniques [START_REF] Campigotto | A generalized and adaptive method for community detection[END_REF]. In the recent years, many embedding methods [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF][START_REF] Dong | Metapath2vec: Scalable representation learning for heterogeneous networks[END_REF][START_REF] Keikha | Community aware random walk for network embedding[END_REF] have been derived from techniques taken from the word representation literature like word2vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. These methods usually require a large number of random walks to train the model. As a result, these methods are often too slow to run on large graphs.

Earlier approaches rely on the factorization of the adjacency matrix using matrix factorization results [START_REF] Ou | Asymmetric Transitivity Preserving Graph Embedding[END_REF][START_REF] Abdi | Singular value decomposition (svd) and generalized singular value decomposition[END_REF][START_REF] Huang | Non-negative matrix factorization: A short survey on methods and applications[END_REF]. While these methods are grouped together, their performances vary widely. For instance, Laplacian eigenmaps (Belkin and Niyogi, 2003) are unsuitable for large graphs while factorizations such as the non-negative matrix factorization can tackle large datasets [START_REF] Huang | Non-negative matrix factorization: A short survey on methods and applications[END_REF]. The interpretability of the resulting embedding also varies. For example, another family of factorization approaches are spectral techniques which rely on the eigendecomposition of matrices to learn embeddings [START_REF] Luo | Spectral embedding of graphs[END_REF]. Some of those embeddings can be interpreted using equivalent physical systems [START_REF] Bonald | Weighted spectral embedding of graphs[END_REF].

Unlike spectral approaches that use the global information available in a graph, some learn embeddings by using local information (e.g. by looking at the neighborhood of the nodes) [START_REF] Tang | LINE: Large-scale Information Network Embedding[END_REF]. This is the case of ClusterNE. Using local information often makes it possible to lower the overall complexity for training embeddings, for instance by using negative sampling.

One approach relies on a hierarchical clustering of the nodes [START_REF] Bhowmick | Lou-vainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF], they use the same hard node clustering algorithm as ClusterNE but use it iteratively to generate a hierarchy of the nodes. At each level of this hierarchy, a random vector is drawn for every cluster. Those level representations are then summed to obtain the embedding of each node. In terms of using the Louvain clustering method, their approach and ClusterNE both begin by applying Louvain on the whole graph. However, building the hierarchy calls for numerous other executions of the algorithm while ClusterNE directly builds the embedding from the first execution.

Embedding method

Algorithm

Let G = (V 1 , V 2 , E) be a bipartite graph. Consider the Louvain clustering method with no resolution parameter (i.e. γ = 1) and using the Barber modularity. Assume this method yields k distinct clusters in V 1 and V 2 . Let B ∈ R n×m be the biadjacency of G and Y ∈ R m×k be the column membership matrix for the obtained clustering, i.e. Y iu = 1 if node i ∈ V 2 is in cluster u and 0 otherwise. The embedding matrix for the nodes of V 1 is diag(d) -1 BY where diag(x) is the diagonal matrix whose coefficients are the (x i ) i and d is the degree vector of the nodes of V 1 . Conversely, if X ∈ R n×k is the row membership matrix, then the embedding matrix for the nodes of V 2 is diag( f ) -1 B T X with f , the degree vector of the nodes of V 2 .

For graphs that are not bipartite, one can use the previous method by cloning all the nodes of the graph and connecting each node to the clones of its original neighbors. It is equivalent to looking at the adjacency matrix of the graph as a biadjacency matrix of some bipartite graph.

This method can thus be applied on directed or undirected and weighted or unweighted graphs. It can also be applied on unconnected graphs although it should be noted that one inherent downside of this method is that Louvain yields at least as many clusters as connected components. This means that a graph with many connected components will have a high-dimensional embedding. It is thus more efficient to use this method on connected graphs. In particular, singleton clusters (i.e. clusters made up of one node only) are irrelevant as they contribute little information to the embedding. Those clusters are thus removed to keep the embeddings short. However, this truncation implies that isolated nodes have a zero embedding.

C ←GENERALIZEDLOUVAIN (G, ǫ) s 1 , . . . , s l ←SINGLETONCLUSTERS (C) Y ←MEMBERSHIP (C) d ← A 1 Y ← Y(s 1 , . . . , s l ) E ←diag(d) -1 AY return E
We describe the pseudo code in Algorithm 4 where GENERALIZEDLOUVAIN is the algorithm described in section 3.2.3 with the Barber modularity function from Equation (3.7), SINGLETONCLUSTERS returns the singleton clusters of some partition C (this function is Θ(n) with n the number of nodes of the graph G), MEMBERSHIP returns the membership matrix of a partition and, if M ∈ R n×m and ∀i, a i ∈ {1, . . . , m}, M(a 1 , . . . , a r ) denotes the extracted matrix of R n×r whose columns are the a 1 -th up to a r -th columns of M. This embedding method inherits some properties from the Louvain clustering method:

• Because the number of clusters is not known in advance, the embedding dimension is not known either and needs not be set in advance.

• The algorithm scales as well as the Louvain clustering method on large data as most of the complexity comes from the clustering itself. Just as the clustering of the generalized Louvain is a co-clustering of both node sets, all the embeddings of the nodes from either node set share the same vector space (if one also computes the column embedding of the graph).

Link with soft clustering

The described embedding method can be described not only in terms of the Louvain hard node clustering method described in Chapter 3, but also in terms of a soft clustering derived from the same method. Hard clustering denotes the case where each node is assigned exactly one cluster while soft clustering assigns a vector of probabilities denoting how likely a node is to belong to each cluster [START_REF] Yu | Soft clustering on graphs[END_REF]. Those vectors can be seen as the embeddings of the nodes.

We illustrate this on a simple graph in Figure 4.1. Starting from the hard node clustering of the graph obtained with the Louvain method in Figure 4.1a, we build a probability vector for each node by counting the number of neighbors in each community and normalizing those counts. This gives a soft clustering as seen in Figure 4.1b where each pie chart stands for the probability vector. This soft clustering is directly interpreted as an embedding in R 2 as depicted in Figure 4.1c.

Results

In order to evaluate the performance of the method described in section 4.2, which we will refer to as ClusterNE, we compare it against other embedding methods on two tasks and also compare the time performance of those algorithms. Let d be the embedding dimension, these methods are:

• non-negative matrix factorization (NMF) [START_REF] Huang | Non-negative matrix factorization: A short survey on methods and applications[END_REF]: an approximate matrix factorization method which yields matrices with positive elements from a matrix with positive elements. It is commonly used for dimensionality reduction. To compute this factorization, we set the number of iteration to 200 and the tolerance to 10 -4 .

• singular value decomposition (SVD) [START_REF] Abdi | Singular value decomposition (svd) and generalized singular value decomposition[END_REF] left singular vectors of the adjacency matrix weighted by the corresponding singular values (in descending order).

• RandNE [START_REF] Zhang | Billion-scale network embedding with iterative random projection[END_REF]: a network embedding approach using successive random projections. We set q = 3 and the weights to (0.5, 0.52 , 0.5 3 ).

• ProNE [START_REF] Zhang | Prone: Fast and scalable network representation learning[END_REF]: a network embedding method using spectral propagation to improve the learned embeddings. We set the parameters to k = 10, µ = 0.1, θ = 0.5.

• LouvainNE [START_REF] Bhowmick | Lou-vainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF]): a network embedding algorithm which also relies on the clustering obtained with the Louvain method. This method recursively applies Louvain on the obtained clusters and derives an embedding by picking random vectors. We use their stochastic variant with α = 0.1.

As all these methods require to set d beforehand, we set this dimension to the one obtained after running ClusterNE. We rely on three open-source packages: the non-negative matrix factorization is found in scikit-learn1 ; ProNE is found in nodevectors 2 ; RandNE, Lou-vainNE and the singular value decomposition are found in scikit-network of Chapter 2. Although all those implementations offer an API in Python, they rely on compiled backends but to different degrees. One should thus be careful when comparing their performance as results may differ (especially in terms of time performance) when using other implementations of the same algorithms.

In the experiments, we use publicly-available real-world web graphs. For link prediction and node classification, we use web graphs and graphs extracted from the Wikipedia hyperlink graph detailed in Table 4.1. For time performance, we use extractions of the Web Data Commons hyperlink graph. In each table, we report the best absolute value in bold and otherwise display the relative errors to that value.

Link prediction

The embeddings are expected to make it possible to reconstruct the graph. In order to assess this property, we run a network reconstruction task: we sample some pairs of nodes in the graph (we sample as much edges as non-edges) and compute the cosine similarities of the corresponding embedding vectors to estimate the probability that the nodes are connected in the original graph. We compare these similarities to the actual linked nodes of the graph using the area under the curve (AUC) score [START_REF] Huang | Using auc and accuracy in evaluating learning algorithms[END_REF]

Node classification

Similarly, the embeddings are expected to capture the structure of the graph: we run a node classification task: using a dataset with a known ground truth, we use a supervised learning framework [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF]

Time performance

We also report the execution times of each algorithm on graphs with a number of edges m ranging from 3.10 7 to 8.10 8 . For reference, we use an AMD EPYC 7542 32-Core CPU with 250 gigabytes of RAM. All algorithms are run in a single thread. We set a timeout of 2 hours. The results are reported in table 4.4. The time performance of LouvainNE and the difference to the results displayed in the corresponding publication [START_REF] Bhowmick | Lou-vainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF] can be explained by the choice of the data structure used to represent the graphs: we use a sparse matrix format with a compression along the rows [START_REF] Buluç | Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks[END_REF] as described in Chapter 2 (see Section 2.3.1) which makes extracting subgraphs very costly. However, as our method requires only one execution of the Louvain clustering method whereas LouvainNE iteratively applies the same algorithm, it can be expected that our method will always be faster when using the same tolerance parameter as the first clustering run is common to both methods.

We note that the SVD and ProNE do not scale as well as the NMF and ClusterNE.

m = 3.

Properties

We now go over some relevant properties of the ClusterNE method.

Interpretability

Thanks to the underlying clustering, the embedding of the nodes of a graph obtained with the method described in section 4.2 can be interpreted as the weighted membership matrix of the nodes of the graph for the clustering obtained by Louvain. Intuitively, the embedding of a node denotes how close it is to each cluster.

For example, we embed the nodes of the WikiVitals dataset. We obtain 11 clusters, which we label manually from their closest articles in terms of PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] as given in Table 4 To illustrate the interpretability of the results, we choose two triplets of classes: Biology, Mathematics and Physics on one hand and World, Geography and Asia on the other hand. For each triplet we extract the articles (i.e. nodes) closest to each class in terms of PageRank (personalized by setting the nodes of the corresponding clusters as seeds). We plot the embedding of those articles projected on the 2-dimensional simplex. The color of each point denotes its cluster. Each vertex of the simplex is associated with a class of the chosen triplet as seen in Figure 4.2. We ignore the components of the embedding not associated with a class of the triplet under study.

In the case of Figure 4.2a, we observe that science articles are heavily polarized depending on the field they are related to. This is unlike what can be observed in Figure 4.2b where the clusters appear to be mixed together. In particular, some nodes belonging to the Asia class are very close to the World class. This denotes nodes whose embeddings have a higher component in clusters other than their own. In the clustering, this translates as nodes highly connected to other communities i.e. nodes at the border between communities.

It should also be noted that, as a byproduct of the Louvain clustering, two nodes belonging to two distinct connected components have orthogonal embeddings under ClusterNE. This is due to Louvain yielding at least as many clusters as there are connected components in the graph.

Sparsity of the embedding

Another interesting feature of the ClusterNE method is that it yields sparse embeddings. This is illustrated by Table 4.6 where we report the fraction of entries of each embedding that are equal to zero for all the datasets and embedding methods under study. Methods such as LouvainNE and RandNE which are based on random projections and randomly picked vectors are expectedly dense. Likewise, the SVD and ProNE yield dense embeddings. ClusterNE gives sparse embeddings as the membership matrix Y and the adjacency matrix A are sparse. We thus also expect their dot product to be sparse. The NMF also gives a sparse embedding by construction. Having a sparse embedding makes it possible to use less memory for storing the embedding. It also makes it possible to combine the resulting embedding with other techniques that preserve the sparsity of their inputs.

PolBlogs

Conclusion

In this chapter, we introduced ClusterNE, a node embedding method based on the Louvain clustering method discussed in Chapter 3. We illustrate how it compares to other embedding methods and show that it makes it possible to embed even very large graphs while being interpretable in terms of the underlying clustering.

Future work may use variants of the Louvain algorithm, especially parallelized ones [START_REF] Bhowmick | A template for parallelizing the louvain method for modularity maximization[END_REF] to make it possible to tackle even larger graphs. Creating embedding methods based on other clustering algorithms is also of particular interest. For instance, it may prove useful to design one around a clustering method that allows a number of clusters to be set as one may need to be able to set the dimension of the embedding.

Chapter 5

Dataset labeling

The use-case presented in this chapter was initially proposed to us by Maria-Laura Maag at Nokia. Initial work, made with Élie de Panafieu, consisted in defining the setting described in Section 5.1.2 and establishing the chordal conjecture. Further work, made with Élie de Panafieu, Alex Scott and Maya Stein within the context of the RandNet project1 , focused on proving the results of Section 5.2. Those results have been published at NeurIPS 2021.

Introduction

Motivation and related work

Machine learning algorithms are split into two categories: unsupervised methods and supervised ones. The latter require labelled sets of elements for training from which they learn distinctive features, making it possible to process new items and predict some results for one or several tasks.

However the quality of those results depends heavily on that of the training dataset as well as its quantity [START_REF] Brodley | Identifying mislabeled training data[END_REF]. Acquiring a suitable corpus of items is not a trivial task [START_REF] Nghiem | Aplenty: annotation tool for creating highquality datasets using active and proactive learning[END_REF]. In a general setting, as the purpose of a training set is to obtain a classifier, no classifier is available beforehand to build a training dataset. Thus, the creation of this dataset cannot be carried out automatically. This often means that humans must be involved which may prove time consuming. The need for an efficient human-based scheme for the creation of training data thus naturally arises.

A naive approach to this problem could consist in choosing an unlabelled set of data and having humans look at each item of this set and classify it. This requires:

• that an unlabelled set of data can be selected. As a thorough exploration of such a set is expensive for the reasons described above, it is expected that some elements may be ambiguous.

• that a set of labels has been determined. This is difficult in some cases as this set can be large.

• that the humans know the whole label set. This can also be difficult when this set is large.

To avoid some of the problems that would be induced by this solution, another possibility consists in presenting the experts with pairs of items of the set and asking if the two items should be put in the same category. This addresses the last two issues mentioned above but does not help with poor choices of the initial set of data to be labelled. This setting of pairwise comparisons is explored in this chapter.

This setting closely resembles what can be found in the active clustering literature [START_REF] Xiong | Active Clustering with Model-Based Uncertainty Reduction[END_REF][START_REF] Kim | Semi-Supervised Active Clustering with Weak Oracles[END_REF]. One slight difference is that we seek to find the exact partition of the whole graph while minimizing the number of queries made to the oracle. Most approaches tackling related problems do not aim at finding the exact partition as labeling data is costly.

Recent papers [START_REF] Chien | Hs2: Active learning over hypergraphs with pointwise and pairwise queries[END_REF][START_REF] Mazumdar | Clustering with noisy queries[END_REF] acknowledge that humans prefer pairwise queries over pointwise queries as they are better suited for comparisons. Pairwise queries have been considered in semi-supervised clustering [START_REF] Basu | A probabilistic framework for semisupervised clustering[END_REF][START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF][START_REF] Gribel | Semi-supervised clustering with inaccurate pairwise annotations[END_REF] where they are called must-link and cannot-link constraints. The pairs of vertices linked by those constraints are random in general, but chosen adaptively in active semi-supervised clustering (Basu et al., 2004a). In both cases, the existence of a similarity measure between items is assumed. This is not the case in [START_REF] Eriksson | Active clustering: Robust and efficient hierarchical clustering using adaptively selected similarities[END_REF]; [START_REF] Krishnamurthy | Efficient active algorithms for hierarchical clustering[END_REF], where a hierarchical clustering is built by successively choosing pairs of items and measuring their similarity. There, the trade-off between the number of measurements and the accuracy of the hierarchical clustering is investigated. The difference with the current chapter is that the similarity measure takes real values, while we consider boolean queries, and that their output is a hierarchical clustering, while our clustering is flat.

The approach described in Section 5.2 does not involve supervised techniques. Rather, we investigate a data-agnostic generalization of this pairwise clustering setting. We consider a graph where each node is an item to be labelled in the original dataset. Rather than classifying each node, we seek to unveil the corresponding clustering of the graph (that is, we ignore the label names for the moment). This clustering (or partition) is what we try to find efficiently in this chapter.

In order to unveil the clustering, we suppose we have at our disposal an oracle that, when given a pair of nodes, is able to determine whether those two nodes belong to the same cluster or not. In reality, such queries correspond to questions asked to human experts about pairs of items. We make the strong assumption that the relation unveiled by the oracle is transitive, that is, if the oracle determines that items x and y on one hand, and y and z on the other hand, belong to the same cluster, then, we expect x and z to belong to the same cluster.

We consider the case where the oracle is perfect: it makes no mistakes. We want to characterize the algorithms whose average number of queries to the oracle is minimal.

Setting

The answers of the oracle can be organized in a graph where each element from the item set S is represented by a vertex, and each edge has one of two possible types. Two vertices are linked by a positive edge (resp. negative edge) if the oracle determined the corresponding elements belong (resp. do not belong) to the same part of the set partition. Thus, each past query to the oracle corresponds to an edge.

The positive (resp. negative) graph is the subgraph obtained by keeping only the positive (resp. negative) edges. A positive component is a connected component of the positive graph. The contracted graph is obtained by contracting each positive component to a vertex. The negative edges are then simply referred to as edges.

A set partition discovery algorithm (which we will now refer to as just "an algorithm") inputs a number of elements n and queries the oracle until the secret set partition on n elements is perfectly reconstructed. This final state is easily interpreted in terms of the graph:

Theorem 1. A set partition discovery algorithm can stop if and only if the contracted graph is complete.

Alternatively, this setting can be interpreted in terms of the equivalence relation R on the item set S elements that we seek to unravel. For x, y ∈ S, xRy if, and only if, x and y are in the same class. R is the (uniquely defined) equivalence relation such that the set partition we seek is exactly the quotient set S/R. A set partition discovery algorithm then consists in growing two symmetric binary relations over S 2 , R + (for positive answers) and its "complement" R -(for negative answers). The transitive closure of R + has a quotient set Q. R -induces another binary relation R - Q on Q 2 by: aR - Q b ⇔ ∃(x, y) ∈ a × b, xR -y. The algorithm stops when R - Q spans all pairs of distinct elements of Q and the sought relation R is then the transitive closure of R + .

Let us recall that the average complexity is the average number of queries asked before reconstructing the correct set partition, when this set partition is chosen uniformly at random among all set partitions on n elements.

The complexity will depend on the distribution of the underlying partition. In this chapter, we will deal with the case where the partition is taken uniformly at random among all partitions on a given set. In particular, in this setting, the number of clusters is unknown a priori. In the situations we encountered at Nokia, we found that it may be very hard to get even an estimate of the number of clusters in practice. While it is likely that some partitions can be discarded by having some knowledge about the data at hand, we seek to solve this problem in a general case.

In Figure 5.1, we give an example of how two distinct algorithms unfold starting from the same graph represented as a binary tree. Each node of the tree at depth k is a possible realization of the contracted graph G k after k queries. Starting from the graph G 0 on the left (which is the root of the tree), the dotted line indicates what the next query is. The upper successor is obtained by adding the queried edge, which corresponds to a negative answer. The lower successor is obtained by merging both ends of the queried edge, which Each leaf and the path that leads to it correspond to a different partition of the nodes of the graph. Conversely, each partition that is compatible with the starting graph has a corresponding leaf. The complexity associated with one particular partition for the algorithm under study is the depth of the associated leaf. Then, the average complexity of the algorithm under study is the average depth of the leaves (as we assume that the partitions are picked uniformly at random). Notice how, for Figure 5.1a, that complexity is 3.2+2.3 5 = 12 5 queries on average, while for Figure 5.1b, it amounts to 1.1+3.4 5 = 13 5 . This demonstrates that all algorithms do not have the same average complexity.

In fact, by running numerical simulations, we conjectured that the algorithms that have the best (i.e. lowest) average complexity are those that yield a chordal graph after each query. We define a chordal algorithm as an algorithm where, at each step, the contracted graph is chordal. We prove this conjecture in Section 5.2.

Chordal algorithms

In this section, we characterize optimal algorithms under the assumption that the partition of the set is chosen uniformly at random among all possible partitions.

In the rest of this section, we show that all partition discovery algorithms where the contracted graph is chordal after each step (denoted as chordal partition discovery algorithms or chordal algorithms) incur the same cost as stated in Corollary 1 and that they are the only optimal algorithms in our setting. We drew these properties from observations on small datasets and simulations on random data.

We introduce the following notations: for a graph G = (V, E) let G(uv) = (V, E ∪ {uv}), let G uv be the graph obtained from G by contracting nodes u and v into just one node and let G[A] = (A, {uv|u, v ∈ A}) for A ⊂ V be the subgraph of G induced by A.

Chordal graphs

A graph is chordal if any of its cycles of four or more vertices has a chord. This means that all its induced cycles (i.e. chordless cycles) have length 3, hence chordal graphs are sometimes called triangulated graphs. An example of a chordal graph is given in Figure 5.2. We briefly go over some properties and characterizations of chordal graphs (see [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]).

Figure 5.2: A chordal graph

Recall the definition of a uv-separator for two vertices u, v ∈ V as a subset S of the node set such that removing S leaves u and v in two distinct connected components. A graph is chordal if, and only if, all vertex separators which are minimal (for the inclusion) are cliques (i.e. complete subgraphs of the graph). This means that chordal graphs can be decomposed: the node set V is the union of a clique (a minimal vertex separator) and two subsets A and B such that there are no edges between A and B.

Another characterization of chordal graphs relies on the notion of perfect elimination schemes. We say that a vertex is simplicial if its neighborhood is a clique. Any chordal graph has a simplicial vertex. Note that all the subgraphs of a chordal graph are also chordal. Thus, if one removes a simplicial vertex from a chordal graph, the resulting subgraph will also have a simplicial vertex. By iteratively removing those simplicial vertices, one creates a perfect elimination scheme of the graph which ends when there are no more vertices. Conversely, a graph with a perfect elimination scheme is chordal. This characterization can be used to check if a graph is chordal.

One should note that identifying two adjacent vertices in a chordal graph leaves the graph chordal. This notably simplifies how queries can be chosen in an efficient way (this is further discussed in Section 5.3.1).

Lemma 1. Let G be a chordal graph, for any adjacent vertices u and v, G

uv is chordal. Proof. Assume G uv is not chordal, there is a minimal induced cycle C = (u, p 1 , . . . , p k , u) in G uv , with k ≥ 3. Then consider C ′ = (u, v, p 1 , . . . , p k , u) in G. If C ′ has a chord, it is either (u, p 1 ) or (v, p k ) and (u, p 1 , . . . , p k , u) or (v, p 1 , . . . , p k , v) is an induced cycle of length four or more. Otherwise, C ′ is. In either case, a contradiction.
The following lemma is key for our subsequent work as it states that it is possible to "grow" a chordal graph into a larger chordal graph, i.e., any incomplete chordal graph has at least one non-edge that leaves the graph chordal once added to the edge set.

Lemma 2. Let G be a chordal graph that is not complete. Then G has a non-edge e such that G(e) is chordal.

Proof. Let u be a non-universal vertex of G. Among all non-neighbors of u, choose p 1 such that |N(u) ∩ N(p 1 )| is maximized.

obtain

α ij = ∑ S⊂[n],|S|≥2 E(q ij |C i ∪ C j = S)P(C i ∪ C j = S) = ∑ S⊂[n],|S|≥2 |S| -1 2 2 |S| 2 |S| -2 P(C i ∪ C j = S)
Because clusters cannot be distinguished a priori, all α ij are equal, and by linearity of expectation the expected number of productive queries is

k 2 ∑ S⊂[n],|S|≥2 |S| -1 2 2 |S| 2 |S| -2 P(C i ∪ C j = S)
which is independent from the choice of the algorithm.

Theorem 2. On partitions of size n chosen uniformly at random, an algorithm has minimal average complexity if and only if it is chordal.

Proof. By Lemmas 3 and 8, all algorithms have the same expected number of core queries and productive queries. So the optimal algorithms are the ones with the minimum expected number of excessive queries. By Lemma 5, these are the chordal algorithms.

Cost equivalence of chordal algorithms

Theorem 2 states that optimal algorithms are all the chordal algorithms. A simple corollary of this statement is that all chordal algorithms have the same (minimal) average complexity. This section is devoted to the proof of Corollary 1 which states that the complexity of all chordal algorithms have the same distribution.

The general idea for this theorem is to proceed by induction on the number of nonedges. The base case is trivial as a complete graph allows just one possible partition discovery algorithm which is chordal and necessarily optimal. The inductive step consists in showing that two consecutive queries can be interchanged without impacting the complexity. This is tricky as one has to deal with disjoint cases depending on whether the asked queries leave the graph chordal or not. When the resulting graph is not chordal, we derive some properties on the structure of the graph (depending on whether the queries asked are incident or not). Those structures are described in Lemmas 12 and 13.

Lemma 9. Let G be a chordal graph, let u, v ∈ V be distinct and non-adjacent, and assume G(uv) is chordal. Then N(u) ∩ N(v) is complete and separates u and v (in G).

Proof. Note that N(u) ∩ N(v) is complete, as otherwise there are two non-adjacent vertices x, y ∈ N(u) ∩ N(v), and (u, x, v, y) is an induced cycle in G,resulting in a contradiction. It remains to show that N(u) ∩ N(v) separates u from v. Assume this is not the case, then there is an induced path P = (u, p 1 , ..., p k , v) (with k ≥ 2) that does not intersect 57

K A B u 0 v 0 u 1 v 1 (a) Base case K A B u 0 v u 1 (b) Triangle case

N(u) ∩ N(v).

Adding the edge uv to P, we obtain an induced cycle of length at least 4, a contradiction to G(uv) being chordal.

We now give a characterization of graphs that remain chordal when we add either one of two edges, but not if we add both. We give an illustration in Figure 5.4.

Lemma 10. Let G be a chordal graph and let u

0 , u 1 , v 0 , v 1 ∈ V such that for i = 0, 1, vertices u 0 , u 1 , v i are all distinct, u i v i / ∈ E, and G(u i v i ) is chordal. If G(u 0 v 0 )(u 1 v 1 ) is not chordal, then K := N(u 0 ) ∩ N(u 1 ) ∩ N(v 0 ) ∩ N(v 1 ) is complete, and G -K has two distinct components A and B, such that either u 0 , u 1 ∈ A and v 0 , v 1 ∈ B, or u 0 , v 1 ∈ A and u 1 , v 0 ∈ B. Proof. As G(u 0 v 0 )(u 1 v 1 ) is not chordal, we know that G(u 0 v 0 )(u 1 v 1 ) has an induced cycle C = (u 1 , v 1 , ..., v ℓ-1 , v ℓ , ..., v k , u 1 ), with k ≥ ℓ ≥ 2, where either v ℓ-1 = v 0 and v ℓ = u 0 , or v ℓ-1 = u 0 and v ℓ = v 0 . According to Lemma 9, since G(u i v i ) is chordal, the set K i := N(u i ) ∩ N(v i
) is complete and separates u i and v i in G, for each i ∈ {0, 1}. Since C has at least four vertices, and

K i has neighbors u i , v i , we know that V(C) ∩ K i = ∅, for i = 0, 1. Assume there is a vertex x ∈ K 0 \ K 1 . Then (v 1 , ..., v ℓ-1 , x, v ℓ , ..., v k , u 1 ) is a path in G -K 1 , in contradiction to the fact that K 1 separates u 1 from v 1 . So K 0 ⊆ K 1 ,
and with the help of a symmetric argument we see that K 0 = K 1 . In order to finish the proof it suffices to note that the paths (v 1 , ..., v ℓ-1 ) and (v ℓ , ..., v k ) ensure that there are components A and B as desired.

We now see that a graph that is obtained by assembling two graphs along a complete subgraph is chordal if and only if the two smaller graphs are. This is a partial converse of the fact that all subgraphs of a chordal graph are chordal.

Lemma 11. Let G be a graph, let A, B, K be a partition of V such that G[K] is complete and there are no edges between A and B. Then G is chordal if, and only if G

[A ∪ K] and G[K ∪ B] are both chordal.
Proof. As induced subgraphs of chordal graphs are chordal, we only need to show that if both G[A ∪ K] and G[K ∪ B] are both chordal, then so is G. For this, it suffices to observe So assume there are sets A, B and K as above. By symmetry, we can assume that u 0 , u 1 ∈ A and v 0 , v 1 ∈ B. Consider the automorphism σ of G that maps u 0 to u 1 and v 0 to v 1 while keeping all other vertices fixed. We can now view A 0 as an algorithm in σ(G) that starts with the edge u 1 v 1 . By the induction hypothesis, we conclude that A 1 (for G) has the same distribution as A 0 (for σ(G), and thus also for G).

Corollary 1. On partitions of size n chosen uniformly at random, all chordal algorithms have the same complexity distribution.

Complexity estimates

In this section, we look for the asymptotic mean and standard deviation of chordal algorithms when the item set is large. Let X n denote the number of pairwise queries needed to partition the n-set using any chordal algorithm. We seek to characterize the limit law of X n when n → ∞. In doing so, we obtain exact formulae for the complexity distribution of chordal algorithms for any n. They are found in Corollary 2 and Theorem 6.

q-integers We will encounter q-integers [START_REF] Ernst | The history of q-calculus and a new method[END_REF]. A q-analog is a generalization of a known result where one introduces an additional parameter q such that the original result can be found when q → 1.

q-integers stem from the sum of a geometric sequence, for any non-negative integer n:

n = lim q→1 (1 + q + q c + • • • + q n-1 ) = lim q→1 1 -q n 1 -q
This enables us to define a natural q-analog of any integer n as:

[n] q = 1 + q + • • • + q n-1 = 1 -q n 1 -q .
The q-factorial of the integer n is:

[n] q ! = n ∏ j=1 [j] q .
The q-exponential is defined as:

e q (z) = ∑ n≥0 z n [n] q ! .
The q-Pochhammer symbol is defined as:

(a; q) n = n-1 ∏ k=0 (1 -aq k )
Observe that all q-analogs reduce to their classic counterparts for q = 1. We will need some alternative formulas which we gather in the following proposition for future reference:

Proposition 5. 1. (x; q) n = (x; q) ∞ (xq n ; q) ∞ 2. [n] q ! = (q; q) n (1 -q) n 3. 1 (x; q) ∞ = ∑ n≥0 x n (q; q) n 4. e q (x) = ((1 -q)x; q) -1 ∞ Proof.
1. The result stems from the simplification of the products in the right hand member.

[n]

q ! = Π n j=1 (1 -q j ) Π n j=1 (1 -q) = Π n-1 j=0 (1 -q.q j ) Π n j=1 (1 -q) = (q; q) n (1 -q) n
3. The q-binomial theorem states (see, e.g., Andrews (1986)):

(x; q) -1 ∞ = ∞ ∑ n=0 x n [n] q !(1 -q) n = ∞ ∑ n=0 x n (q; q) n 4. Using the two previous properties: ((1 -q)x; q) -1 ∞ = ∑ n≥0 (1 -q) n x n (q; q) n = ∑ n≥0 x n [n] q !
Universal algorithm We consider the universal algorithm, described (in a recursive fashion) in Algorithm 5 which consists in asking all possible questions related to one element before selecting the next element. QUERY(u, v) returns True if u and v are in the same class and False otherwise. Note that exactly one block of the partition is unveiled at each call of the UNIALG function.

Proposition 6. The universal algorithm is a chordal algorithm.

Proof. Using the notation of Algorithm 5, let us denote node u as the central node of its step. Let C = (u, a 0 , a 1 , . . . , a p , v) be a cycle of length n ≥ 4, a 0 and a p are distinct.Then:

• either a 0 or a p have already been central and a 0 a p is a chord

• otherwise, if say a 0 has not been central, then u and a 1 have been and ua 1 is a chord Thanks to Corollary 1, we can assert that all chordal algorithms will share the asymptotics of the universal one.

Denote the universal algorithm by A, the set of all partitions by P. Let:

P(z, q) = ∑ p∈P q #queries A (p) z |p| |p|!
Algorithm 5: The universal algorithm UNIALG Result: The underlying partition

Input: A set S if S = ∅ then u ← POP(S) B ← {u} for v ∈ S do q ← QUERY(u, v) if q = True then B ← B ∪ {v} end P ← UNIALG(S \ B) return P ∪ {B} end else
return ∅ end with #queries A (p), the number of queries required by the universal algorithm to unveil partition p starting from the graph with |p| nodes and no edges.

Theorem 4. P(z, q) satisfies P(0, q) = 1 and the following differential equation: (z, q) = P(qz, q)e qz

∂ z P
(5.1)

Proof. Let a n,k be the number of partitions over n-sets that require A to ask k queries to be found. Then P can be written:

P(z, q) = ∑ n,k≥0 a n,k q k z n n! (5.2)
We seek an inductive relation for a n,k . To get all partitions on (n + 1)-sets requiring A to make k queries, consider the number m of elements in the same cluster as the first element.

In the first round of queries, where all elements are compared to the first one, n queries are asked and m of them yield a positive result. Then, A behaves exactly as if on a nm set over the remaining elements and all (nm) sets can be reached that way.

From this, we derive:

a n+1,k = n ∑ m=0 n m a n-m,k-n (5.3)
as we are only interested in cases that result in a total number of queries equal to k. Summing Equation (5.3) over n and k so as to find P(z, q) as defined in 5.2, we get: (z, q) = P(qz, q)e qz

∑ n,k≥0 a n+1,k q k z n n! = ∑ n,k≥0 n ∑ m=0 n m a n-m,k-n q k z n n! Setting, n ′ = n -m and k ′ = k -n so that n = n ′ + m and k = k ′ + n ′ + m: ∑ n,k≥0 a n+1,k q k z n n! = ∑ n ′ ,k ′ ,m≥0 a n ′ ,k ′ q k ′ +n ′ +m z n ′ +m n ′ !m! = e qz ∑ n ′ ,k ′ ≥0 a n ′ ,k ′ q k ′ (qz) n ′ n ′ ! ∂ z P
If the set under study is empty, only the empty partition can be found and thus P(0, q) = 1

We now seek to solve Equation (5.1). In particular, we would like to have an explicit expression of a n,k . Let f (z, q) = e q 1-q z be a solution of a similar equation as ∂ z f (z, q) = q 1-q f (z, q) and f (qz, q)e qz = e 1-q+q 1-q qz = f (z, q) so ∂ z f (z, q) = q 1-q f (qz, q)e qz .

Theorem 5. Let Poch(z, a, q) denote the exponential generating function associated to the q-Pochhammer symbol

Poch(z, a, q) = ∑ k≥0 (a; q) k z k k! ,
then the generating function of the universal algorithm complexity is P(z, q) = Pochq 1q z, 1q q , q e q 1-q z

The following corollary derives the complexity distribution of chordal algorithms for any finite number of elements n.

Corollary 2. The generating function for the number of queries of the universal algorithm on n-sets is:

P n (q) = q 1 -q n n ∑ m=0 n m
(-1) m 1q q ; q m Proof of Theorem 5 and Corollary 2. We investigate solutions of the differential equation 5.1 of the form P(z, q) = A(z, q)e q 1-q z . The differential equation on P(z, q) implies the following differential equation for A(z, q) ∂ z A(z, q) + q 1q A(z, q) = A(qz, q). with initial condition A(0, q) = 1. Decomposing A(z, q) as a series in z

A(z, q) = ∑ k≥0 a k (q) z k k! ,
we obtain a recurrence on a k (q):

a k+1 (q) = - q 1 -q a k (q) + q k a k (q) = - q 1 -q 1 -(1 -q)q k-1 a k (q),
with a 0 (q) = 1. We deduce

a k (q) = - q 1 -q k k-1 ∏ j=0 1 - 1 -q q q j = - q 1 -q k 1 -q q ; q k
To conclude the proof of the theorem, we observe that Pochq 1-q z, 1-q q , q e q 1-q z is indeed solution of the differential equation characterizing P(z, q).

To prove the corollary, notice how P n (q) is obtained by computing the Cauchy product of the series A(z, q) and f (z, q) and extracting the coefficient of z n :

P n (q) = n! n ∑ m=0 a m (q) m! 1 (n -m)! q 1 -q n-m = q 1 -q n n ∑ m=0 n m (-1) m 1 -q q ; q m
We provide a second expression for the complexity generating function better suited for an asymptotic analysis as it deals with positive terms only. It is a q-analog of the following classic Dobinski formula for the Bell numbers [START_REF] Flajolet | Analytic combinatorics[END_REF], which counts the number of partitions of size n:

B n = 1 e ∑ m≥0 m n m!
Theorem 6. The generating function of the number of queries used by the universal algorithm on partitions of size n is

P n (q) = 1 e q (1/q) ∑ k≥0 [k] n q [k] q ! q n-k
The sum converges for q > 1/2. Also, log(1 + S(x)) = log ∑ k≥0

x k (k+1)! so that:

log(1 + S(x)) = log 1 + x 2 + x 2 6 + O(x 3 ) = x 2 + x 2 24 + O(x 3 ) Then, [m] n q = 1 -e sm 1 -e s n = m n 1 + S(sm) 1 + S(s) n = m n e n log(1+S(sm))-n log(1+S(s)) .
and

[m] n q = m n exp 1 2 nms + 1 12 nm 2 s 2 2 + O(nm 3 s 3 + ns)
According to [START_REF] Moak | The q-analogue of stirling's formula[END_REF], we have the following q-analog of Stirling's formula when x → ∞ while x log(q) → 0

log(Γ q (x)) = (x -1/2) log([x] q ) + Li 2 (1 -q x ) log(q) + 1 2 log(2π) + o(1)
where Li 2 (z) denotes the Dilogarithm function

Li 2 (z) = ∑ k≥1 z k k 2
We deduce

[m] q ! = [m] q Γ q (m) = [m] q exp (m -1/2) log([m] q ) + Li 2 (1 -q m ) log(q) + 1 2 log(2π) + o(1) = [m] m q exp Li 2 (1 -q m ) log(q) 2π[m] q (1 + o(1))
The first part of the lemma provides

[m] m q = m m exp 1 2 m 2 s + 1 12 m 3 s 2 2 1 + O(m 4 s 3 + ms) .
The Dilogarithm is expanded as

Li 2 (1 -q m ) log(q) = 1 s ∑ k≥1 1 k 2 (-m s (1 + S(m s))) k = -m 1 + 1 4 ms + 1 18 m 2 s 2 2 + O(m s) 3 .
Injecting those past two expansions in the previous one concludes the proof.

Theorem 7. The asymptotic mean E n and standard deviation σ n of the number X n of queries used by the universal algorithm on a partition of size n chosen uniformly at random are

E n = 1 4 (2ζ -1)e 2ζ and σ n = 1 3 3ζ 2 -4ζ + 2 ζ + 1 e 3ζ ,
where ζ is the unique positive solution of

ζe ζ = n. The normalized random variable X ⋆ n = X n -E n σ n
follows in the limit a normalized Gaussian law. Proof. To prove the limit law, we show that the Laplace transform E(e sX ⋆ n ) converges pointwise to the Laplace transform of the normalized Gaussian e s 2 /2 (see e.g., [START_REF] Billingsley | Probability and measure[END_REF]).

We have

E(e sX ⋆ n ) = e -sE n /σ n E(e sX n /σ n ) = e -sE n /σ n B n P n (e s/σ n )
For any fixed real value s, we compute the asymptotics of P n (e s/σ n ). Let q := e s/σ n , so q tends to 1, then

P n (e s/σ n ) = 1 e q (e -s/σ n ) ∑ m≥0 [m] n q [m] q ! e (n-m)s/σ n .
Motivated by the asymptotics from Lemma 14, we rewrite this expression as P n (e s/σ n ) = 1 e q (e -s/σ n ) ∑ m≥0 A n,s (m)e -φ n,s (m) (5.4)

where

A n,s (m) = [m] n q m n exp 1 2 nm s σ n + 1 12 nm 2 (s/σ n ) 2 2 m m e -m exp 1 4 m 2 s σ n + 1 36 m 3 (s/σ n ) 2 2 [m] q ! e (n-m)s/σ n , φ n,s (m) = -n log(m) + m log(m) -m - 1 4 (2n -m)m s σ n - 1 36 (3n -m)m 2 (s/σ n ) 2 2 .
The dominant contribution to the sum comes from integers m close to the minimum of φ n,s (m), so we study this function. The successive derivatives of φ n,s (m) are

φ ′ n,s (m) = - n m + log(m) - 1 2 (n -m) s σ n - 1 12 (2n -m)m (s/σ n ) 2 2 , φ ′′ n,s (m) = n m 2 + 1 m + s 2σ n - 1 6 (n -m) (s/σ n ) 2 2 φ ′′′ n,s (m) = - 2n m 3 - 1 m 2 + (s/σ n ) 2 12
When n is large enough, the second derivative of φ n,s (m) is strictly positive for all m > 0, so the function is convex. It reaches its unique minimum at a value denoted by m(s) and characterized by φ ′ n,s (m(s)) = 0. Injecting the Taylor expansion

m(s) = m 0 + m 1 s σ n + m 2 (s/σ n ) 2 2 + O (s/σ n ) 3
in this equation, extracting the coefficients of the powers of s, we obtain:

     m 0 log(m 0 ) -n = 0 2m 1 (log(m 0 ) + 1) -nm 0 + m 2 0 = 0 m 4 0 + 24m 2 0 m 1 + 12m 0 m 2 (log(m 0 ) + 1) -2 m 3 0 + 6m 0 m 1 n + 12m 2 1 = 0
Hence, by replacing n with ζe ζ :

       m 0 = e ζ m 1 = 1 2 ζ-1 ζ+1 e 2ζ m 2 = 1 3 2ζ 3 -3ζ 2 +2 (ζ+1) 3 e 3ζ
The dominant contribution to the sum defining P n (e s/σ n ) comes from values of m close to m(s). The central part C n is defined as the integers m such that |mm(s)| < c n . A heuristic proposed by [START_REF] Flajolet | Analytic combinatorics[END_REF] is to find c n such that

|φ ′′ n,s (m(s))|c 2 n → +∞ and |φ ′′′ n,s (m(s))|c 3 n → 0.
As n, and thus ζ, tend to infinity, we have:

m(s) ∼ e ζ ∼ n log(n) , |φ ′′ n,s (m(s))| ∼ ζe -ζ ∼ log(n) 2 n , |φ ′′′ n,s (m(s))| ∼ ζe -2ζ ∼ log(n) 3
n 2 , so we choose c n = e 3ζ/5 . We define p(s

) = m 0 + m 1 s σ n + m 2 (s/σ n ) 2 2
and r(s) = Ce -ζ/2 for some constant C. Note that φ ′ n,s (p(s) + r(s)) > 0. Since φ ′ n,s is an increasing function, 0 ≤ m(s)p(s) ≤ r(s) and m(s) = p(s) + O(r(s)). Then for m in C n :

m(s) = e ζ + 1 2 ζ -1 ζ + 1 e 2ζ s σ n + 1 3 2ζ 3 -3ζ 2 + 2 (ζ + 1) 3 e 3ζ (s/σ n ) 2 2 + O(e -ζ/2 ), φ n,s (m) = -(ζ 2 -ζ + 1)e ζ -E n s σ n - s 2 2 + (ζ + 1)e -ζ (m -m(s)) 2 2 + O(e -ζ/4 ), A n,s (m) = 1 √ 2πe ζ (1 + o(1)) .
We chose the values of E n and σ n so that the coefficients in s and s 2 are the ones presented in the above equation. The error term is then obtained using the Lagrange form of the remainder in Taylor's Theorem. We deduce the following asymptotics for the central part of the sum:

∑ m∈C n A n,s (m)e -φ n,s (m) ∼ 1 √ 2πe ζ e (ζ 2 -ζ+1)e ζ +E n s σn + s 2 2 ∑ m∈C n e -(ζ+1)e -ζ (m-m(s)) 2 2 .
Applying the Euler-Maclaurin formula to turn the sum into an integral, we obtain:

∑ m∈C n A n,s (m)e -φ n,s (m) ∼ 1 √ 2πe ζ e (ζ 2 -ζ+1)e ζ +E n s/σ n +s 2 /2 c n -c n e -(ζ+1)e -ζ x 2 2 dx.
After the variable change y = (ζ + 1)e -ζ x, observing that (ζ + 1)e -ζ c n tends to infinity, the integral is approximated as a Gaussian integral and we conclude:

∑ m∈C n A n,s (m)e -φ n,s (m) ∼ 1 √ ζ + 1 e (ζ 2 -ζ+1)e ζ +E n s/σ n +s 2 /2 .
When we compare the asymptotics of the central part to the asymptotics of the Bell numbers (see, e.g. [START_REF] Flajolet | Analytic combinatorics[END_REF])

B n ∼ e (ζ 2 -ζ+1)e ζ -1 √ ζ + 1 ,
we see from Equation (5.4) that, as expected,

e -sE n /σ n B n 1 e q (e -s/σ n ) ∑ m∈C n A n,s (m)e -φ n,s (m) ∼ e s 2 /2 .
Let us now prove that the part of the sum corresponding to m ≤ m(s)c n is negligible compared to the central part. According to Lemma 14, we have:

A n,s (m) = 1 + O(nm 3 /σ 3 n ) 1 + O(m 4 /σ 3 n ) 1 2π[m] q = O(m 8 ). Since φ n,s (m) is convex (for large enough n), we have φ n,s (m) ≥ φ n,s (m(s) -c n ) for all m < m(s) -c n . Since φ n,s (m(s) -c n ) = -(ζ 2 -ζ + 1)e ζ -E n s σ n - s 2 2 + (ζ + 1)e -ζ c 2 n 2 + O(e -ζ/4
) and e -ζ c 2 n tends to infinity as e ζ/5 , we obtain for all m < m(s)c n :

φ n,s (m) ≥ -(ζ 2 -ζ + 1)e ζ -E n s σ n - s 2 2 + Θ(e ζ/5
).

We conclude:

∑ m<m(s)-c n A n,s (m)e -φ n,s (m) ≤ ∑ m<m(s)-c n O(m 8 )e (ζ 2 -ζ+1)e ζ +E n s/σ n +s 2 /2-Θ(exp(ζ/5 ))
≤ e (ζ 2 -ζ+1)e ζ +E n s/σ n +s 2 /2 m(s) 9 e -Θ(exp(ζ/5)) .

Since m(s) ∼ e ζ , this result is exponentially small, with respect to n, compared to the central part. Let us now prove that the part of the sum beyond the central part is negligible as well.

There is a constant C such that for n large enough and any m ≥ Ce 3ζ/2 , we have

- 1 4 (2n -m)m s σ n - 1 36 (3n -m)m 2 (s/σ n ) 2 2 ≥ 0.
In that case, we obtain the simple bound

φ n,s (m) ≥ -n log(m) + m log(m) -m ≥ m -n log(m).
Injecting this bound and A n,s (m) = O(m 8 ) in the sum, we obtain:

∑ m≥Ce 3ζ/2 A n,s (m)e -φ n,s (m) ≤ O(1) ∑ m≥Ce 3ζ/2 m n+8 e -m .
The sum is bounded by an integral and n + 8 integrations by part are applied

∑ m≥Ce 3ζ/2 A n,s (m)e -φ n,s (m) ≤ O(1)(n + 8)!(Ce 3ζ/2 ) n+8 e -C exp(3ζ/2) ≤ O(1)n n (Ce 3ζ/2 ) n+8 e -C exp(3ζ/2) Since n = ζe ζ , we have n n = e O(ζ 2 ) exp(ζ) , so ∑ m≥Ce 3ζ/2 A n,s (m)e -φ n,s (m) ≤ O(1)e -Θ(exp(3ζ/2))
which is negligible compared to the central part of the sum. The last part we consider is

m(s) + c n ≤ m ≤ Ce 3ζ/2 . Since φ n,s (m) is decreasing there and A n,s (m) = O(m 8 ), we have Ce 3ζ/2 ∑ m=m(s)+c n A n,s (m)e -φ n,s (m) = O(e 27ζ/2 )e -φ n,s (m(s)+c n )
As for the case m = m(s)c n , we find

φ n,s (m(s) + c n ) = -(ζ 2 -ζ + 1)e ζ -E n s σ n - s 2 2 + Θ(e ζ/5
) and conclude

Ce 3ζ/2 ∑ m=m(s)+c n A n,s (m)e -φ n,s (m) = e (ζ 2 -ζ+1)e ζ +E n s σn + s 2 2 O(e 27ζ/2 )e -Θ(e ζ/5 ) ,
which is negligible compared to the central part. In conclusion, we have

E(e sX ⋆ n ) = e -sE n /σ n B n P n (e s/σ n ) ∼ ∑ m∈C n A n,s (m)e -φ n,s (m) ∼ e s 2 /2 .
Since the Laplace transform of X ⋆ n converges pointwise to the Laplace transform of the normalized Gaussian law, X ⋆ n converges in distribution to this Gaussian. We can derive a simpler equivalent of E n for large n: Corollary 3. The asymptotic mean E n of the number X n of queries used by the universal algorithm on a partition of size n chosen uniformly at random satisfies E n ∼ n 2 2 log n Proof. ζe ζ = n means that ζ = W(n) where W is the principal branch of the Lambert W function. This in turn means that ζ = log n -log log n + o(log log n) (see e.g. [START_REF] Corless | On the lambertw function[END_REF]). Thus 2ζ -1 ∼ 2 log n and e 2ζ ∼ n 2 log 2 n hence the result.

By comparison with the expression of Corollary 3, an exhaustive algorithm (i.e. one that queries all distinct pairs of elements) has the worst possible performance at ( n 2 ) ∼ n 2 2 queries. This slim 1 log n -margin can be explained by the underlying partition distribution. A partition picked uniformly at random has n log n blocks on average [START_REF] Flajolet | Analytic combinatorics[END_REF] and the number of negative queries is at least that number squared meaning that n 2 log 2 n is a lower bound for E n (as additional negative queries and positive queries remain).

Practical use

We set the theoretical foundations for chordal algorithms optimality in the setting of random partitions. While the results of Theorems 1 and 2 give some strong theoretical guarantees for chordal algorithms, we seek to know how those hold against a more practical setting. Indeed, a number of assumptions made in the setting described in this chapter can be challenged. Additionally, parts of the work done in the previous section can be used to implement a chordal algorithm efficiently.

Considerations for implementations

When implementing any chordal algorithm, one needs to find which queries make it possible to keep the graph chordal at each step. Note that any query that keeps the graph chordal in the event of it being answered negatively also keeps the graph chordal when it is answered positively (see Lemma 1). Indeed, identifying two neighbors in a chordal graph results in a chordal graph. Suitable queries thus consist of non-edges that preserve chordality when added. A naive approach could consist in trial and error, i.e. adding any non-edge and checking that the resulting graph is chordal. Each such test can be performed in linear time in the size of the graph [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]. Alternatively, Lemma 9 makes it possible to rely on the chordality of graph to find a suitable query by checking that the intersection of the neighborhood of two nodes u and v separates them. In the worst case that is also done in linear time.

In a practical situation, it is preferable that several humans can work in parallel on the same item set. In particular, this requires that one can find a suitable query for an available human while some served queries are still pending. This is achievable thanks to the remark made earlier: it suffices to assume that any pending query will receive a negative answer. Thus, by choosing the next suitable query by considering the graph where all pending queries have received a negative answer, one can keep the graph chordal while allowing multiple humans to answer queries simultaneously.

Assistance by data-specific techniques

All the work done in the previous sections of this chapter make no assumption on the nature of the data to be labeled. This enables us to use the very general setting introduced earlier but, in practice, we expect to be able to use ad hoc techniques depending on the data. For instance, if all data items are texts, one could use text classifiers, after a few queries are asked, in order to reduce the number of queries (e.g. by finding positive queries and having the oracle answer them). Indeed, such classifiers and other ad hoc methods make use of additional information that was left aside: that of the data itself. If the data is labeled so that it can be subsequently used to train a supervised classifier, said classifier can be trained and used to predict the class of items as the data is labeled. This falls under the context of active learning which we do not explore here. We evaluate the importance of two distinct features for any algorithm:

• the chordality of the algorithm

• the use of supervised techniques

As classifiers proceed in a pointwise fashion, we proceed as follows: we pick the first edges to query at random until a negative answer is obtained and then train the classifier on the items of the largest connected component of the contracted graph and their corresponding clustering (which is not yet final as some clusters may still be merged); the classifier is then used to predict the cluster of one node outside the largest component and the nonedge between that node and the corresponding node in the contracted graph is queried. When the largest component comprises all the graph, the classifier is not used anymore and queries are picked either at random or according to some chordal strategy. To illustrate this, we run experiments on the well-known 20 News Group dataset. We use two wellknown text classifiers: a linear classifier with stochastic gradient descent (SGD) for training [START_REF] Zadrozny | Transforming classifier scores into accurate multiclass probability estimates[END_REF] and a multinomial naive Bayes (MNB) classifier [START_REF] Christopher | Introduction to information retrieval[END_REF]. We extract an increasing number of elements in the dataset at random. For each such set size, we perform 100 random extractions and average the results of each algorithm. We report the results in Figure 5.5.

In Figures 5.5a and 5.5b, we notice that supervised techniques give a consistent edge over unsupervised approaches be it in the random or chordal context. This is due to the fact that classifiers use the data to find positive edges with a higher probability than unsupervised algorithms. Those positive edges reduce the number of nodes in the contracted graph early on and thus make it possible to reduce the overall number of queries. In Figures 5.5c and 5.5d, one can notice that chordal algorithms have a slight edge over random ones both when combined with classifiers or not. While this was expected for the unsupervised case given the results of Section 5.2, it should be noted that keeping the contracted graph chordal also reduces the number of queries in the supervised case. This is partly explained by the fact that when the whole contracted graph consists of its largest connected component, classifiers no longer play any role so that random and chordal algorithms behave as if they were unsupervised.

The use of supervised techniques yields noticeable but not necessarily significant decreases in the number of queries. While they make it harder to implement a labeling algorithm, it should be noted that they do not incur significant costs in terms of added computation times. Indeed, we expect the number of items to cluster to be small (in the thousands at most) as it would otherwise be impracticable for humans. The classifiers we mention have minimal execution times at that scale and those execution times should thus remain negligible compared to the time spent answering queries by humans. It is also possible to use classifiers in a parallelized fashion, as long as there are items left out of the largest connected component (the reasoning described in Section 5.3.1 still applies).

Imperfect oracle

In Section 5.2, we made the assumption that the oracle did not make any mistake. In a more practical context where the oracle is human, we expect that some mistakes will be made. We discuss how these errors could be handled.

False negatives (when the oracle wrongly answered negatively) are corrected more easily than false positives. For instance, the former can be corrected a posteriori by asking additional questions between positive components which seem close (making it possible to correct a false negative in a few queries). On the other hand, false positives require more redundancy as finding the mislabeled edge in a positive component is cumbersome. To Furthermore, there are many ways to model errors. For instance, one can assume that the overall number of errors will be bounded. Here we investigate, another error model which assumes mistakes are made with a (small) probability p at each query. To help detect inconsistencies in the oracle's answers, we create cycles in the expanded graph. To assess how robust to errors the graphs we create this way are, we rely on the notion of reliability polynomials [START_REF] Page | Reliability polynomials and link importance in networks[END_REF].

The coefficient c i of p i in the reliability polynomial R G (p) of a graph G is the number of ways of disconnecting G by removing i edges. If, for all the edges of G, each is removed with probability p, then R G (p) is the probability the graph is disconnected after the edges are deleted. We want to minimize R G (p). Using the added cycles in the graph, one can detect errors by checking that no cycle contains exactly one negative edge. Finding the smallest such contradictory cycle makes it possible to identify an ambiguous element by recursively splitting the cycle into two. To create such cycles, we build a graph whose reliability polynomial can be estimated.

Let us consider the tree graph G of depth h depicted in Figure 5.6a. We highlight the internal nodes in red and the leaves in blue. We seek to turn the previously described tree into a 2-connected graph. To achieve this, we allow ourselves to add 2 h-1 edges binding the 2 h leaves of the tree. This yields the graph H depicted in Figure 5.6b.

Numbering the leaves in the most simple fashion (from left to right using the representation depicted in Figure 5.6a), we link each leaf with an even index to the next leaf (with the last leaf being connected to the first one). We now consider a graph K built from the previously constructed graph by adding l ∈ 2N nodes of degree 2 on each edge between the internal nodes and l-2 2 nodes on the edges between the internal nodes and the leaves (as depicted in Figure 5.6c). We would like to show that K is optimally robust whenever H is. To prove that, we would like to express R K (p),the reliability polynomial of K, using R H (p).

We need to express the number of ways ci of disconnecting K by removing i edges in terms of c i . Since removing more than one edge between a pair of given nodes of degree 3 always disconnects the graph, we distinguish the cases where more than one edge between any pair of nodes of degree 3 has been removed from the other cases.

Removing at most one edge per segment There are l i c i ways to choose the edges to remove in order to yield no such pair of nodes (from any configuration that disconnects G, many configurations can be derived to disconnect K).

Removing at least two edges on at least one segment On the other hand, the number of ways to remove at least two edges between at least one pair of nodes of degree 3 is

( ml i ) -( m i )l i because ( ml i
) is the number of ways of removing i edges in K (with or without disconnecting it) and ( m i )l i is the number of ways to remove i edges without removing more than one edge between a pair of given nodes of degree 3 (still with no regard as to whether or not the yielded graph is connected).

In the end, both cases make up all the configurations which disconnect K:

ci = c i l i + ml i - m i l i
Thus:

R K (p) = ml ∑ i=0 ci p i = ml ∑ i=0 c i l i p i + ml i p i - m i l i p i R K (p) = R H (l p) + (1 + p) ml -(1 + l p) m
Notice how R K (p) = R H (l p) + o(p) for small p.

We are thus able to correlate the reliability of the graphs H and K. In particular, the parameter l allows one to choose the maximum size of the cycles in the graph thus enabling a trade-off between additional queries and error detection. Also, note that the graph K minus the edges between its leaves (i.e. the blue nodes in Figure 5.6c) can be obtained via a chordal algorithm. Aiming at graphs of the same form thus makes it possible to correct errors while maintaining control over the number of queries.

Conclusion

In this chapter, we introduced a particular case of dataset labeling and characterized its optimal solutions. We first introduced a formal setting based on a graph representation of the labeling. We then proved optimal solutions (on average) consisted of a particular family of algorithms. We proved that the complexity distribution of any two algorithms of this family is the same on any given graph and then gave an approximation of the mean and variance of those distributions when the number of elements to be labeled is large. We also discussed the potential improvements or changes that can be made to both the setting and the algorithms for use in real use-cases.

We previously assumed that the distribution of the underlying partition of the graph is the uniform one. As discussed at the end of Section 5.2.4, optimal solutions offer just a slim 1 log n -gain over the worst case. This is due in part to the fact that, under the uniform model, there are many blocks on average which makes for a high lower bound on the number of queries whatever the algorithm that is used. Indeed, in the experiments of Section 5.3.1, we find that chordal and random algorithms produce close results.

However, it is possible to have at least some information about that partition which biases the distribution. One information that may be found in some particular cases is the number of clusters. Though it is difficult to evaluate in general, when it is possible, the partition is picked from a limited set. Limiting the number of clusters alleviates the lower bound discussed earlier and enables greater improvements when comparing chordal algorithms to random ones. When running experiments with that fixed-size distribution, we find that all chordal algorithms are no longer equivalent and that the clique algorithm seems to reach a minimal number of queries (with the precision that the clique algorithm compares the selected vertex with the largest positive components first). Future work could focus on proving or disproving this conjecture.

Chapter 6

Conclusion and perspectives

In this work, we have tackled a number of problems in graph mining and machine learning.

First, we formally introduced graphs and depicted basic examples for the related yet distinct fields of graph mining and graph theory. We gave an outline of the thesis.

Then, we introduced Scikit-network, an open-source graph analysis library aimed at providing both an API that is consistent with the current Python ecosystem in machine learning packages and a state-of-the-art performance typically only found in C/C++ packages. We gave a sketch of practical considerations for representing graphs. We would like to emphasize that, in addition to the experiments of Chapter 2, results given in Chapters 3 and 4 illustrate the influence of the representation of graphs depending on the operations that have to be performed. In the future, the library could benefit from broader adoption of multi-threaded implementations of some algorithms along with the permanent maintenance efforts required to keep the package up to date. There are also a number of potential additions that could be made to the package such as anomaly detection algorithms.

In Chapter 3, we considered two clustering algorithms, one for flat clustering and one for hierarchical clustering. In the former case, we looked at the Louvain algorithm and its numerous variants. We first considered the various modularity functions present in the literature under a unified setting. We also described some improvements of the Louvain method and illustrated how the implementation of those algorithms (in particular the graph representation they use) has a considerable influence on their time performance. As regards hierarchical clustering, we considered the Paris algorithm and gave some examples of how it can be used with inherently hierarchical data. Future work could be focused on further improvements of the Louvain method, especially of the costly initial optimization phase.

We introduced a simple novel method for embedding the nodes of a graph, be it undirected, directed or bipartite. It is strongly linked to soft clustering as it is based on the formerly introduced Louvain clustering algorithm which enables easy interpretability and scalability. It has the particularity of not allowing the user to set an embedding dimen-sion. Future improvements of this method could make use of the improvements of the Louvain method described in Chapter 3. In particular, those improvements can be aimed at speeding up the algorithm to tackle even larger graphs.

In Chapters 2, 3 and 4, we tackled situations where graphs could be used to model data. In this case, the accuracy of any method is usually measured against some ground truth of the data at hand and its time performance is expectedly dependent on the implementation of the method. Those empiric criteria are thus subjected to a careful understanding of those external factors (i.e. the data at hand and the implementation in use). To that end, making data and information readily available in the form of repositories enables increased reproducibility [START_REF] Baker | Reproducibility crisis[END_REF][START_REF] Pineau | Improving reproducibility in machine learning research: a report from the neurips 2019 reproducibility program[END_REF]. Even then, implementations may differ due to choices made when designing them such as the programming language that was used or the data structures. When proposing a new method, depicting those parameters may seem cumbersome. It is however often necessary as it affects what can be inferred from the experiments.

In Chapter 5 we studied a setting motivated by the construction of labeled datasets for supervised learning. While close to the problems depicted in the active learning literature, we make some strong assumptions that radically alter the approach to that setting. We describe and prove the optimality of a class of algorithms for this setting. In addition to these theoretical results, we provide some numerical experiments closer to real-world considerations. In the future, more of the strong assumptions made to solve the problem at hand could be challenged. With the advent of social networks and the world-wide web, more and more datasets can be represented using graphs. Those graphs are ever bigger, sometimes with billions of edges and billions of nodes. Designing efficient algorithms for analyzing those datasets has thus proven necessary. This thesis reviews the state of the art and introduces new algorithms for the clustering and the embedding of the nodes of massive graphs. Furthermore, in order to facilitate the handling of large graphs and to apply the techniques under study, we introduce Scikit-network, a free and open-source Python library which was developed during the thesis. Many tasks, such as the classification or the ranking of the nodes using centrality measures, can be carried out thanks to Scikit-network. We also tackle the problem of labeling data. Supervised machine learning techniques require labeled data to be trained. The quality of this labeled data has a heavy influence on the quality of the predictions of those techniques once trained. However, building this data cannot be achieved through the sole use of machines and requires human intervention. We study the data labeling problem in a graph-based setting, and we aim at describing the solutions that require as little human intervention as possible. We characterize those solutions and illustrate how they can be applied in real use-cases.

Institut Polytechnique de Paris 91120 Palaiseau, France

  Figure 1.1: Various graphs

Figure 2 . 2 :

 22 Figure 2.2: Visualization of a graph and a dendrogram as SVG images.

  Figure 3.1: Refinement process for the Smart Local Move.

  Figure 3.2: Hierarchical clustering of a graph

  Figure 3.3: Agglomerative approach

  The adjacency matrix A of a graph G = (V, E), a tolerance ǫ Output: An embedding of the nodes of V

  Figure 4.1: Clusterings and embedding of a graph.

Figure 4

 4 Figure 4.2: Visualization of 3-dimensional embeddings of topical Wikipedia articles and of the underlying clustering.

  Figure 5.1: Unfolding of two different algorithms

Figure 5 . 4 :

 54 Figure 5.4: Structure of the graph when adding two edges prevents chordality.

  Figure 5.5: Average number of queries needed over 100 runs as a function of the number of elements. ×: Chordal algorithm, +: Random algorithm; •: Unsupervised; •: SGD; •: MNB

Titre:

  Contributions à base de graphes à l'apprentissage automatique Mots cl és : graphes, apprentissage automatique, annotation de donn ées R ésum é : Un graphe est un objet math ématique permettant de repr ésenter des relations entre des entit és (appel ées noeuds) sous forme d'ar êtes. Les graphes sont depuis longtemps un objet d' étude pour diff érents probl èmes allant d'Euler au PageRank en passant par les probl èmes de plus courts chemins. Les graphes ont plus r écemment trouv é des usages pour l'apprentissage automatique. Avec l'av ènement des r éseaux sociaux et du web, de plus en plus de donn ées sont repr ésent ées sous forme de graphes. Ces graphes sont toujours plus gros, pouvant contenir des milliards de noeuds et ar êtes. La conception d'algorithmes efficaces s'av ère n écessaire pour permettre l'analyse de ces donn ées. Cette th èse étudie l' état de l'art et propose de nouveaux algorithmes pour la recherche de communaut és et le plongement de noeuds dans des donn ées massives. Par ailleurs, pour faciliter la manipulation de grands graphes et leur appliquer les techniques étudi ées, nous proposons Scikit-network, une librairie libre d évelopp ée en Python dans le cadre de la th èse. De nombreuses t âches, telles que le calcul de centralit és et la classification de noeuds, peuvent être accomplies à l'aide de Scikit-network. Nous nous int éressons également au probl ème d'annotation de donn ées. Les techniques supervis ées d'apprentissage automatique n écessitent des donn ées annot ées pour leur entrainement. La qualit é de ces donn ées influence directement la qualit é des pr édictions de ces techniques une fois entrain ées. Cependant, obtenir ces donn ées ne peut pas se faire uniquement à l'aide de machines et requiert une intervention humaine. Nous étudions le probl ème d'annotation, sous un formalisme utilisant des graphes, avec pour but de d écrire les solutions qui limitent cette intervention de fac ¸on optimale. Nous caract érisons ces solutions et illustrons comment elles peuvent être appliqu ées. Title : Graph-based contributions to machine learning Keywords : graphs, machine learning, data labeling Abstract : A graph is a mathematical object that makes it possible to represent relationships (called edges) between entities (called nodes). Graphs have long been a focal point in a number of problems ranging from work by Euler to PageRank and shortestpath problems. In more recent times, graphs have been used for machine learning.

  1. Related to Chapter 2 • Lutz, Q., De Panafieu, E., Stein, M., & Scott, A. (2021). Active clustering for labeling training data. Advances in Neural Information Processing Systems, 34. Related to Chapter 5

Table 2

 2

.1: Overview of graph software features. ✓: Available. ✓: Partially available or slow implementation. ✗: Not available.

Table 2 .

 2 2: Complexities of different representations of a graph. d max is the maximum degree in the graph.

Table 2

 2

.3: Memory usage (in kB) of different formats for various graphs.

Table 2 .

 2 4: Execution times (in seconds) of different formats on the WikiVitals graph.

  FLM variant offers more modest time gains as it is generally placed between the Table3.7: Adjusted Rand score (ARI) of the result and the ground truth.

			n WikiSchools 4.10 3 1.10 5 m WikiVitals 8.10 3 6.10 5 WikiVitals+ 3.10 4 2.10 6 WikiLinks 3.10 6 7.10 7 Orkut 3.10 6 2.10 8 UK Domain 2.10 7 5.10 8 Twitter 4.10 7 1.10 9	# Labels 16 10 10 ----
			Table 3.3: Dataset statistics.
		Schools Vitals Vitals+ Links Orkut UK Domain Twitter
	Baseline SLM RLM	2 3.7 0.03	1.3 2.1 0.15	1.6 2.7 1.02	1.1 3.8 44.79	1.1 1.7 1.4	1.2 ➍ 1.0	1.1 ➍ 1860.45
	FLM	1.3	1.2	1.6	1.0	1.1	1.1	1.1
	CLM	1.7	1.7	1.4	1.3	122.06	72.15	1.1
		Table 3.4: Execution times (in s). ➍: Timeout (> 7200s)
		Schools Vitals Vitals+ Links Orkut UK Domain Twitter
	Baseline SLM RLM	0.396 0.99 0.93	0.468 0.97 0.90	0.522 0.96 0.90	0.98 0.651 0.91	0.99 0.670 0.90	0.985 ➍ 0.99	0.481 ➍ 0.96
	FLM	1.0	1.0	0.522	0.98	0.99	0.985	0.481
	CLM	0.97	0.99	0.522	0.93	0.94	0.99	0.481
		Table 3.5: Modularity of the result. ➍: Timeout (> 7200s)
				Schools Vitals Vitals+
			Baseline	0.91	0.98	0.90
			SLM	0.32	0.94	0.42
			RLM	0.32	0.88	0.98
			FLM	0.91	0.98	0.90
			CLM	0.94	0.52	0.90
		Table 3.6: V-measure score of the result and the ground truth.
				Schools Vitals Vitals+
			Baseline	0.86	0.46	0.93
			SLM	0.90	0.72	0.63
			RLM	0.21	0.50	0.63
			FLM	0.86	0.46	0.93
			CLM	0.21	0.46	0.27

  as reported in Table4.2. We observe that ClusterNE is the second-best performing algorithm with results close to the better-performing ProNE.

		PolBlogs (d = 8) WikiVitals (d = 11) WikiVitals+ (d = 16)
	ClusterNE	0.70	0.98	0.98
	NMF	0.71	0.92	0.97
	SVD	0.74	0.94	0.95
	LouvainNE	0.89	0.80	0.85
	ProNE	0.83	0.93	0.87
	RandNE	0.65	0.89	0.97
	Table 4.2: AUC on the pairwise cosine similarities of the embedding of sampled nodes.

Table 4

 4

		PolBlogs (d = 8) WikiVitals (d = 11) WikiVitals+ (d = 16)
	ClusterNE	0.96	0.86	0.67
	NMF	0.92	0.78	0.56
	SVD	0.92	0.83	0.70
	LouvainNE	0.89	0.68	0.65
	ProNE	0.97	0.63	0.54
	RandNE	0.91	0.81	0.80

to classify the embedding vectors. We supply 100 nodes per class for the training set and use the remaining nodes for validation. We report the accuracy of each algorithm with respect to the ground truth in terms of precision in table 4.3. We observe that ProNE performs best once again with a significant edge over RandNE, ClusterNE and the SVD. .3: Precision of an SVC for the classification of embedding vectors.

Table 4

 4

		10 7 (d = 347) m = 2.10 8 (d = 518) m = 8.10 8 (d = 1215)
	ClusterNE	1.5	1.6	277
	NMF	8	39	1.8
	SVD LouvainNE ProNE	33 ➍ 47	51 ➍ 69	➍
	RandNE	5.1	7.6

.4: Execution times (in seconds). m is the number of edges. ➍: Timeout (> 7200s).

: Memory overflow.

  .5.

		Physics	Asia
	Biology	Mathematics	World	Geography
	(a) Science articles	(b) Humanities articles
	Clusters	Closest articles
	Biology	Taxonomy (biology), Animal, Protein
	World	Bibliothèque nationale de France, United States, Geographic coordinate system
	Europe	Latin, Roman Empire, Greek language
	Society	Marriage, Incest, Adoption
	Media	The New York Times, Encyclopaedia Britannica, Time (magazine)
	Asia	India, Buddhism, Chinese language
	Mathematics	Mathematics, Real number, Function (mathematics)
	Physics	Hydrogen, Oxygen, Kelvin
	Geography	Earth, Atlantic Ocean, Pacific Ocean
	Philosophy	Aristotle, Plato, Age of Enlightenment
	Craftsmanship Jewellery, Weaving, Shoe
	Table 4.5: Clusters and their closest articles in terms of PageRank

See https://github.com/sknetwork-team/scikit-network/graphs/contributors.

https://docs.scipy.org/doc/scipy/reference/sparse.html

See https://github.com/sknetwork-team/scikit-network.

See https://scikit-network.readthedocs.io/en/latest/.

See https://netset.telecom-paris.fr/

https://scikit-learn.org

https://github.com/VHRanger/nodevectors

See https://cordis.europa.eu/project/id/101007705

If G(up 1 ) is not chordal, there is an induced cycle C = (u, p 1 , . . . , p k , u), with k ≥ 3. As p k ∈ N(u) ∩ N(p k-1 ) \ N(p 1 ), our choice of p 1 guarantees that there is a vertex w ∈ N(u) ∩ N(p 1 ) \ N(p k-1 ). Let j be the largest index in {1, . . . , k -2} such that wp j ∈ E. Then, depending on whether the edge wp k is present, either (w, p j , . . . , p k , u, w) or (w, p j , . . . , p k , w) is an induced cycle of length at least 4 in G, a contradiction.

Optimality of chordal algorithms

In this section, we prove that the optimal algorithms are exactly the chordal algorithms.

We define three categories of queries as depicted in Figure 5.3:

• Queries that receive a positive answer are called core queries

• Queries at time t are excessive if they compare vertices x and y that are joined by an induced path in G t on an even number of vertices that alternates between two partition classes

• Queries that are neither core nor excessive are productive

The first two categories are mutually exclusive as excessive queries always receive a negative answer. Thus, each query belongs to exactly one category. We now characterize the overall average complexity by looking at each category.

Lemma 3. For any algorithm and any partition of a set of size n containing k classes, the number of core queries is exactly nk.

Proof. If a query is core, the number of nodes of the contracted graph decreases by exactly one and it is the only case where this number changes. Since the algorithm starts from a graph with n nodes and ends with a graph of k nodes, there has to be nk core queries.

We then look at excessive queries.

Lemma 4. For each non-chordal algorithm, there is an input partition and a time t such that G t has an induced C 4 one of whose edges comes from a negative query in step t -1.

Proof. Since the algorithm is not chordal, for some input partition one of the aggregated graphs G t of the algorithm has an induced cycle C of length at least 4. Consider a realization of G t where the vertices of C are all in distinct partition classes. Then there is a time t ′ when four of the vertices of C form an induced C 4 in G t ′ .

Then, we can prove:

Lemma 5. An algorithm makes no excessive queries if and only if it is chordal.

Proof. By definition, a chordal algorithm has no aggregated graphs with induced cycles of length at least 4. So, since an excessive query, if answered negatively, creates an induced cycle of even length at least 4, chordal algorithms make no excessive queries. Conversely, Lemma 4 ensures that for any non-chordal algorithm, there exists a partition and a contracted graph G t such that G t has an induced C 4 = (t, u, v, w) such that the last asked query was (w, t). There exists a partition for which t and v are in one cluster and u and w are in another one, meaning that (w, t) was an excessive query. Thus for all non-chordal algorithms, there exists a partition for which an excessive query is made.

We now consider productive queries. To that end, we first consider the set P 2 (n) of partitions with at most two blocks and P * 2 (n) = P 2 (n) \ P 1 (n), the set of partitions with exactly two blocks. In this particular subcase, an additional property can be used: if one considers three nodes u, v and w where (u, v) and (v, w) are both negative edges, then, assuming the underlying partition is in P 2 (n), it is known that u and w are in the same block and that v is in the only other block. Intuitively, this corresponds to the fact that "the enemy of my enemy is my friend" applies only when there are two blocks. Lemma 6. The expected number of productive queries made by any algorithm on a random partition from P 2 (n) is exactly n-1 2 .

Proof. We run some algorithm on a partition from P 2 (n) and color each node depending on its cluster. At each t, the connected components of G t are all bipartite graphs (where each of the two node sets corresponds to a cluster in the partition). Every such component can be colored in two ways; thus the number of possible colorings of G t is 2 n com (G t ) where n com denotes the number of connected components of G t .

Let us prove by induction that:

• The 2 n com (G t ) colorings of G t are equally likely.

• If the t-th query joins two components of G t-1 then it is productive with probability half.

The initialization is clear as in G 0 , each node is in its own connected component. Let (u, v) be the query made at the t-th step. If u and v are in the same connected component, the query is excessive and the first induction hypothesis holds.

Let us then consider the case where u and v lie in distinct connected components H u and H v . The four colorings of H u ∪ H v are equally likely and independent from the coloring of the other components of the graph. Then, u and v have the same color with probability 1 2 and the probability that (u, v) is productive is also 1 2 . Depending on the colors of u and v, there are only two possible colorings for H u ∪ H v and they are equally likely. This concludes the induction.

As each query joining two components decreases the number of connected components by exactly one, there are exactly n -1 such queries and by linearity of the expected number of productive queries at each step, the total expected number of productive queries is (n -1)/2.

Lemma 7. The expected number of productive queries made by any algorithm on a random partition

Proof. Let us consider an algorithm and denote its expected number of productive queries by α(n). We pick a partition P uniformly at random from P 2 (n). If P is constant, then the algorithm only makes core queries, in particular, it makes no productive queries. This happens with probability 2 2 n . Conditioning on P being nonconstant is equivalent to picking it uniformly from P * 2 (n). By Lemma 6, we conclude that the expected number of productive queries satisfies:

Hence:

We now use the previous result to prove that all algorithms have the same expected number of productive queries on any random partition picked uniformly from P k (n) (the set of partitions of n-sets into exactly k sets) Lemma 8. All algorithms have the same expected number of productive queries on a random partition from P k (n).

Proof. Fix k and consider a partition of [n] into exactly k sets C 1 , C 2 , . . . , C k . Let α ij denote the expected number of productive queries that compare a vertex from C i with a vertex from C j . For i = j, α ij = 0. We thus assume i = j.

Let q ij be the number of productive queries comparing a vertex from C i with a vertex from C j . (so α ij = E(q ij )) Then, considering the set S = C i ∪ C j , and applying Lemma 7, we that any cycle of G that contains vertices from both A and B has to pass twice through K.

The next two lemmas give a structural characterization of aggregated graphs where consecutive queries cannot easily be interchanged. In order to make their statement easier, let us say that a graph G has a complete separation (A, K, B) if V is the disjoint union of A, B, K so that A = ∅ = B, each of A ∪ K and B ∪ K is complete, and there are no edges from A to B (observe that we allow K to be empty).

The next lemma asserts that, in case the two non-edges to be added prevent chordality when they are both added, there exists a third non-edge which makes can be added to either of the two previous non-edges and leave the graph chordal.

Lemma 12. Let G be a chordal graph that does not have a complete separation. For i = 0, 1 let u i v i be a non-edge of G such that G(u i v i ) is chordal, and G(u 0 v 0 )(u 1 v 1 ) is non-chordal. Then there is a non-edge uv of G such that G(uv) is chordal, and G(u i v i )(uv) is chordal for i = 0, 1.

Proof. Use Lemma 10 to see that the intersection K of the neighborhoods of u 0 , v 0 , u 1 , v 1 is either a clique or empty, and G -K has two connected components A and B such that u 0 , u 1 ∈ A and v 0 , v 1 ∈ B (after possibly changing the roles of u 0 and v 0 ).

As G has no complete separation, and as there are no edges between A and B, one of A ∪ K, B ∪ K has to have a non-edge; because of symmetry we can assume this is A ∪ K. According to Lemma 11, the subgraph of G induced by A ∪ K is chordal. Then, according to Lemma 2, there is also a non-edge uv with u, v ∈ A ∪ K having the additional property that G(uv) is chordal. As K is complete, we can assume that u ∈ A.

If there is no non-edge uv as desired, we have that G(u i v i )(uv) is non-chordal for some i ∈ {0, 1}; by symmetry, let us assume G(u 1 v 1 )(uv) is non-chordal. So, we may apply Lemma 10 to see that the intersection K ′ of the neighborhoods of u, v, u 1 , v 1 is either a clique or empty, and G -K ′ has two connected components A ′ , B ′ such that u, u 1 ∈ A ′ and v, v 1 ∈ B ′ (after possibly changing the roles of u and v). Note that

In particular, v / ∈ K, that is, v ∈ A. So, as v 1 ∈ B, we know that v, v 1 lie in distinct components of G -K. However, we also have that v, v 1 belong to the same component (namely, A) of G -K ′ = G -K, a contradiction. So the desired non-edge uv exists.

Lemma 13. Let G be a chordal graph that does not have a complete separation. Let u

) is non-chordal, and moreover, u 0 u 1 ∈ E. Then there is a non-edge uw of G such that G(uw) is chordal, and G(u i v)(uw) is chordal for i = 0, 1.

Proof. We start by proving that N(u 0 ) ∩ N(v) = N(u 1 ) ∩ N(v). For this assume there is an i ∈ {0, 1} and a vertex x ∈ (N(u

, a contradiction since this graph is chordal. This proves the equality, and we set

Because of Lemma 9, G[K] is complete and separates u 0 , u 1 from v. Since G does not have a complete separation, at least one of G[A ∪ K], G[B ∪ K] is not complete, but by Lemma 11 both are chordal. So by Lemma 2 and, again, Lemma 11, there is a non-edge uw such that G(uw) is chordal. Now, if uw is not as desired, say because G(u 0 v)(uw) is non-chordal, then there is an induced cycle C of length at least 4 going through both uw and u 0 v. However, C has to meet K, which implies C is a triangle, a contradiction.

We will prove a more general result than needed which allows for the algorithm to start with any aggregated graph instead of starting with the empty graph. More precisely, if G is an aggregated graph at time t for some algorithm for an n-set, then we call the restriction of the algorithm to all queries after time t that eventually lead to a realization of G an algorithm starting at G. We define the complexity distribution of this algorithm analogously to our earlier definition. In particular, if G is complete, then the complexity distribution is trivial as no questions are asked with probability 1.

Theorem 3. For any chordal G, all chordal algorithms starting at G have the same complexity distribution.

Proof. We proceed by induction on the number of non-edges of G. Proving the base case is trivial as, starting from a complete graph, the only algorithm has a trivial distribution for its complexity where the only possibility is to ask no questions.

For the induction step assume that for any chordal graph with k or less missing edges, all chordal algorithms have the same complexity distribution, and consider a graph G with k + 1 missing edges. Let A 0 , A 1 be two distinct chordal algorithms for G. If their first queries are the same, say they query the edge e, then by induction we know that for both G e and G(e), the two algorithms have the same distribution if we let them start there. As the distribution for an algorithm starting at G is uniquely obtained from the complexity distributions of the same algorithm starting at G e and at G(e), we see that A 0 and A 1 have the same complexity distribution.

So we can assume that A 0 and A 1 differ in their first queries. Say the first query of A i is u i , v i , for i = 0, 1. Then G(u i v i ) is chordal for i = 0, 1. Note that we can assume that u 0 = u 1 . We will distinguish two cases.

First, let us assume that G(u 0 v 0 )(u 1 v 1 ) is chordal and moreover, if v 0 = v 1 then u 0 u 1 / ∈ E. Then, for i = 0, 1, the edge u i v i can be chosen as the first edge of a chordal algorithm for G(u 1-i v 1-i ) or for G u 1-i v 1-i . As the induction hypothesis applies to G(u 1-i v 1-i ) and to G u 1-i v 1-i , we can assume that u i v i is the second edge in A 1-i . Observe that for each i = 0, 1 after the second query of A i , we arrive at one of the four graphs (G

Thus the complexity distribution of A 0 and A 1 is identical (as is can be computed from the complexity distribution for the algorithms starting at these four graphs). Now, let us assume that either G(u

Then, by Lemmas 12 and 13, we know that either there is an edge uv ∈ E such that G(uv), G(uv)(u 0 v 0 ) and G(uv)(u 1 v 1 ) are chordal, or V can be partitioned into three sets, A, B and K, such that A ∪ K and B ∪ K are complete and K separates A from B. If the former is the case, we can proceed as in the previous paragraph to see that every chordal algorithm starting with u 0 v 0 has the same complexity distribution as any of the chordal algorithms starting with uv (note that such algorithms exist by Lemma 2), which, in turn, has the same complexity distribution as any of the chordal algorithms starting with u 1 v 1 , leading to the desired conclusion.

Proof. Starting from the expression of Corollary 2 and using Proposition 5:

(1q) k (q; q) k .

(1q k ) n (1q) n .q n-k

= 1 e q (1/q) ∑ k≥0

[k] n q

[k] q ! q n-k .

We apply d'Alembert's criteria to find the values of q for which this formal sum converges:

[k+1] q ! q n-k-1

[k] n q

[k] q ! q n-k = 1q q is smaller than 1 when q > 1/2.

Asymptotics Using the expression obtained in Theorem 6, we now seek to find the asymptotic mean and standard deviation of X n for large n. Lemma 14 gathers some expressions of common q-integer derivatives for large n and m0. Theorem 7 gives the asymptotic mean and standard deviation for the universal algorithm. To do so, we prove that the Laplace transform of the random variable X n counting the number of queries converges to that of the desired result. This leads us to using the Laplace method in order to estimate the asymptotics of a sum derived from the previous lemmas.

Lemma 14. As n and m tend to infinity, q = e s , ms and ns tend to 0, we have

[m] n q = m n exp 1 2 nms + 1 12 nm 2 s 2 2 1 + O(nm 3 s 3 + ns)

[m] q ! = m m e -m 2π[m] q exp 1 4 m 2 s + 1 36 m 3 s 2 2 1 + O(m 4 s 3 + ms) + o(1) .

Proof. Let us first introduce the function S(x) = e x -1 x -1. Note that 1 + x(1 + S(x)) = e x .