Théorie spectrale des graphes

En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Matrices décrivant un graphe Matrice d'adjacence Soit un graphe G = (V, E), où V désigne l'ensemble des sommets et E l'ensemble des arêtes. Le graphe possède |V| = n sommets, notés v_1, \cdots, v_n \in V et |E| = m arêtes, notées e_{ij}, v_i \in V, v_j \in V. Chaque élément de la matrice d'adjacence A du graphe G est défini par : a_{ij}=\left{\begin{array}{rl} 1 & \mbox{si } e_{ij}\in E \ 0 & \mbox{sinon.} \end{array}\right. Matrice des degrés et laplacienne La matrice des degrés D

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emerged in recent decades, such as processing the data in a stream, parallel processing, and data compression. The aim of this thesis is to apply these techniques to various important graph theoretical problems. Our contributions can be broadly classified into two categories: spectral graph theory, and maximum matching.Spectral Graph Theory. Spectral sparsification is a technique of rendering an arbitrary graph sparse, while approximately preserving the quadratic form of the Laplacian matrix. In this thesis, we extend the result of (Kapralov et al.), and propose a sketch and corresponding decoding algorithm for constructing a spectral sparsifier from a dynamic stream of edge insertions and deletions. The size of the resulting sparsifier, the size of the sketch, and the decoding time are all nearly linear in the number of vertices, and consequently nearly optimal.The concept of spectral sparsification has recently been generalized to hypergraphs (Soma and Yoshida) -- an analogue of graphs for modeling higher order relationships. As one of the main contributions of the thesis, we prove for the first time the existence of nearly-linear sized spectral sparsifiers for arbitrary hypergraphs, and provide a corresponding nearly-linear time algorithm for constructing them. Through a lower bound construction, we show that our sparsifiers achieve nearly-optimal compression of the hypergraph spectral structure.On the more applied side of spectral graph theory, we present a fully scalable MPC (massively parallel computation) algorithm which is capable of simulating a large number of independent random walks of length L from an arbitrary starting distribution in O(log(L)) rounds.Maximum Matching. We propose a novel randomized composable coreset for the problem of maximum matching, called the matching skeleton. The coreset achieves a 1/2 approximation, while having fewer than n edges.We also propose a new, highly space-efficient variant of a peeling algorithm for maximum matching. With this, we are able to approximate the maximum matching size of a graph to within a constant factor, using a stream of m uniformly random edges (where m is the total number of edges), in as little as O(log^2(n)) space. Conversely, we show that significantly fewer (that is m^(1-Omega(1))) samples do not suffice, even with unlimited space. Finally, we design a Local Computation Algorithm, which implicitly construct a constant-approximate maximum matching in time and space that is nearly linear in the maximum degree.

EPFL2022

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requires a new set of algorithms for computing with extremely constrained resources, i.e., \emph{sublinear algorithms}. Clustering is one of the well-known techniques for solving large-scale optimization problems in a wide variety of domains, including machine learning, data science and graph analysis~\cite{aydin2016distributed, rolnick2016geocuts, gargi2011large}. Efficient sublinear solutions for fundamental graph clustering problems require going well beyond classic techniques. In this thesis, we present an \emph{optimal} sublinear-time algorithm for \textit{testing

k

-clusterability problem}, i.e., quickly determining whether the graph can be partitioned into at most

k

expanders, or is far from any such graph. This is a generalization of a well-studied problem of testing graph expansion. The classic results on testing

k

-clusterability either consider the testing expansion problem (i.e,

k=1

k\geq 2

) \cite{KaleS_SIAMJC11,NachmiasS10}, or address the problem for larger values of

k

under the assumption that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph \cite{CzumajPS_STOC15}. We overcome these barriers by developing novel spectral techniques based on analyzing the spectrum of the Gram matrix ofrandom walk transition probabilities. We complement our algorithm with a matching lower bound on the query complexity of testing

k

-clusterability, which improves upon the long-standing previous lower bound for testing graph expansion.Furthermore, we extend our previous result from the \textit{property testing} framework to an efficient clustering algorithm in the \textit{local computation algorithm} (LCA) model. We focus on a popular variant of graph clustering where the input graph can be partitioned into

k

expanders with outer conductance bounded by

\epsilon

. We construct a small space data structure that allows quickly classifying vertices of

G

according to the cluster they belong to in sublinear time. Our spectral clustering oracle provides

O(\epsilon \log k)

error per cluster for any

\epsilon \ll 1/\log k

. Our main contribution is a sublinear time oracle that provides dot product access to the spectral embedding of the graph. We estimate dot products with high precision using an appropriate linear transformation of the Gram matrix of random walk transition probabilities. Finally, using dot product access to the spectral embedding we design a spectral clustering oracle. At a high level, our approach amounts to hyperplane partitioning in the spectral embedding of the graph but crucially operates on a nested sequence of carefully defined subspaces in the spectral embedding to achieve per cluster recovery guarantees.

EPFL2021

Space-Efficient Representations of Graphs

Jakab Tardos

EPFL2022

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

k

-clusterability problem}, i.e., quickly determining whether the graph can be partitioned into at most

k

expanders, or is far from any such graph. This is a generalization of a well-studied problem of testing graph expansion. The classic results on testing

k

-clusterability either consider the testing expansion problem (i.e,

k=1

k\geq 2

) \cite{KaleS_SIAMJC11,NachmiasS10}, or address the problem for larger values of

k

k

k

expanders with outer conductance bounded by

\epsilon

. We construct a small space data structure that allows quickly classifying vertices of

G

according to the cluster they belong to in sublinear time. Our spectral clustering oracle provides

O(\epsilon \log k)

error per cluster for any

\epsilon \ll 1/\log k

EPFL2021

Théorie spectrale des graphes

Space-Efficient Representations of Graphs

Sublinear Algorithms for Spectral Graph Clustering

Erdos-Ko-Rado theorem for {0, +/- 1}-vectors

Space-Efficient Representations of Graphs

Sublinear Algorithms for Spectral Graph Clustering

Erdos-Ko-Rado theorem for {0, +/- 1}-vectors