Pierrick Pierre

Denis

Pierre Bernard

Fré- Déric Peng

François Vous

Chris- Tophe Amaury

Isabelle Jean

Luca

Algiane, François, Nassim Andrea Leo

Mes Amis

Jean

Sami

Thomas

Gui Baptiste

Keywords: systèmes de recommandation, ltrage collaboratif, complétion de matrice de rang faible, modèles probabilistes, espérance-maximisation, réseaux, graphes, parcimonie, comportement en loi de puissance, structure en communautés, méthodes bayésiennes non paramétriques, mesures complètement aléatoires recommender systems, collaborative ltering, low-rank matrix completion, probabilistic models, expectation maximization, networks, graphs, sparsity, power-law behavior, community structure, Bayesian nonparametrics, completely random measures, Markov chain Monte Carlo

A

Résumé : Nous proposons deux nouvelles approches pour les systèmes de recommandation et les réseaux. Dans la première partie, nous donnons d'abord un aperçu sur les systèmes de recommandation avant de nous concentrer sur les approches de rang faible pour la complétion de matrice. En nous appuyant sur une approche probabiliste, nous proposons de nouvelles fonctions de pénalité sur les valeurs singulières de la matrice de rang faible. En exploitant une représentation de modèle de mélange de cette pénalité, nous montrons qu'un ensemble de variables latentes convenablement choisi permet de développer un algorithme espérancemaximisation a n d'obtenir un maximum a posteriori de la matrice de rang faible complétée. L'algorithme résultant est un algorithme à seuillage doux itératif qui adapte de manière itérative les coe cients de réduction associés aux valeurs singulières. L'algorithme est simple à mettre en oeuvre et peut s'adapter à de grandes matrices. Nous fournissons des comparaisons numériques entre notre approche et de récentes alternatives montrant l'intérêt de l'approche proposée pour la complétion de matrice à rang faible. Dans la deuxième partie, nous présentons d'abord quelques prérequis sur l'approche bayésienne non paramétrique et en particulier sur les mesures complètement aléatoires et leur extension multivariée, les mesures complètement aléatoires composées. Nous proposons ensuite un nouveau modèle statistique pour les réseaux parcimonieux qui se structurent en communautés avec chevauchement. Le modèle est basé sur la représentation du graphe comme un processus ponctuel échangeable, et généralise naturellement des modèles probabilistes existants à structure en blocs avec chevauchement au régime parcimonieux. Notre construction s'appuie sur des vecteurs de mesures complètement aléatoires, et possède des paramètres interprétables, chaque noeud étant associé un vecteur représentant son niveau d'a liation à certaines communautés latentes. Nous développons des méthodes pour simuler cette classe de graphes aléatoires, ainsi que pour e ectuer l'inférence a posteriori. Nous montrons que l'approche proposée peut récupérer une structure interprétable à partir de deux réseaux du monde réel et peut gérer des graphes avec des milliers de noeuds et des dizaines de milliers de connections.

Résumé substantiel Introduction Systèmes de recommandation

Au cours des 20 dernières années, les systèmes de recommandation ont suscité un intérêt croissant. Ils sont complémentaires des moteurs de recherche traditionnels pour nous aider à gérer la surcharge d'information à laquelle nous sommes confrontés depuis l'avènement de l'ère numérique. Quel livre lire ? Quel lm regarder ? Quel produit acheter ? Prendre de telles décisions est de moins en moins facile pour un simple être humain, car le nombre d'articles (items) disponibles est en constante augmentation et devient di cile à manipuler. Nous avons tous besoin d'une sorte de ltrage de l'information pour distinguer les articles pertinents des non partinents. Alors que les moteurs de recherche visent à répondre à des requêtes spéci ques posées par un utilisateur (user) qui sait à peu près ce qu'il cherche, les systèmes de recommandation adoptent une approche di érente. Ils tentent d'automatiser l'expérience de la découverte en nous fournissant ce que nous voulons avant que nous le sachions. Un aspect fondamental est que ces recommandations doivent être personnalisées et traduire ainsi une bonne compréhension des préférences de l'utilisateur.

Il n'est pas étonnant que les systèmes de recommandation aient attiré beaucoup d'attention dans les applications commerciales. Il est bien connu que la personnalisation améliore la satisfaction du client et qu'elle est donc un levier pour augmenter les taux de conversion. Les plateformes de commerce électronique comme Amazon.com fournissent une grande diversité de recommandations en ligne telles que « les clients qui ont acheté ce produit ont également acheté » ou des recommandations de co-achat personnalisées basées sur le contenu de votre panier, mais aussi des listes de recommandations envoyées par courriel [START_REF] Linden | Amazon.com recommendations: Item-to-item collaborative ltering[END_REF]. On peut prédendre qu'une grande part de leur succès est liée à la façon dont les recommandations sont intégrées dans presque chaque partie du processus d'achat. Au-delà de la vente de produits, les systèmes de recommandation s'appliquent à un large éventail de domaines, en particulier à tous les types de contenus multimédia : articles de blog/actualité/recherche, favoris, livres, lms, émissions de télévision, musique, etc. ou applications mobiles, entre autres.

En particulier, la recommandation de lms a été popularisée par le prix Net ix [START_REF] Bennett | The Net ix prize[END_REF], un concours organisé par Net ix, une multinationale américaine spécialisée dans la vidéo à la demande. L'objectif était de prédire les notes attribuées aux lms par les utilisateurs, en se basant uniquement sur un ensemble de notes passées, sans aucune autre information sur les utilisateurs ou les lms. En 2009, le grand prix de 1 000 000 $ a été remporté par l'équipe BellKor's Pragmatic Chaos, qui a amélioré de plus de 10 % les performances prédictives de l'algorithme de Net ix [START_REF] Koren | The BellKor solution to the Net ix grand prize[END_REF][START_REF] Piotte | The Pragmatic theory solution to the Net ix grand prize[END_REF]. Le développement des systèmes de recommandation, leur évaluation et leur application à divers problèmes du monde réel est un domaine de recherche très actif. Tout d'abord développés dans le domaine de la recherche d'information, ils sont maintenant à l'intersection de nombreux domaines de vii recherche, dont l'informatique, l'apprentissage automatique (machine learning) et les statistiques.

Les systèmes de recommandation prédisent les préférences des utilisateurs à partir des « données massives » (big data) recueillies sur potentiellement plusieurs millions d'utilisateurs et d'articles. Le « contenu » (au sens large : catégorie, description, etc.) de l'article ainsi que les données démographiques des utilisateurs sont des informations importantes, mais les données les plus précieuses sont le feedback des utilisateurs sur les articles. Ce dernier peut être explicite ou implicite. Le feedback explicite est donné par les utilisateurs sous forme de note ou d'étiquette (tag) qui expriment de manière explicite l'intérêt positif ou négatif de l'utilisateur pour cet article. Les données de ce type sont généralement incomplètes. L'ensemble de toutes les paires utilisateur-article étiquetées sont considérées comme données observées alors que tout le reste est manquant. En revanche, le feedback implicite est recueilli à partir du comportement des utilisateurs tel que leurs clics, pages vues ou les événements d'achat. Ce type de feedback est moins informatif que des notes explicites mais est implicitement lié aux préférences sous-jacentes de l'utilisateur. Un utilisateur est plus susceptible de cliquer ou acheter les articles qu'il aime ; en revanche une absence d'événement est une information plus faible puisque l'utilisateur pourrait simplement ne pas connaître l'existence de l'article. Les données de type implicite sont complètement observées.

Réseaux

L'analyse, la compréhension et la modélisation de réseaux complexes sont étroitement liées au domaine des systèmes de recommandation (Newman, 2003a[START_REF] Newman | Networks: an introduction[END_REF]. Les données de réseau apparaissent dans un large éventail de domaines tels que les réseaux sociaux, les réseaux de collaboration, les réseaux de télécommunication, les réseaux biologiques, les réseaux alimentaires, et sont un moyen utile de représenter les interactions entre des ensembles d'objets. Un réseau peut être représenté par un graphe composé d'un ensemble de noeuds, ou de sommets, avec des connexions, appelées arêtes ou liens, entre eux.

Le plus souvent et à moins d'indication contraire, graphe signi e « graphe simple non orienté ». Un graphe non orienté est un graphe dans lequel les arêtes n'ont pas d'orientation, ce qui signi e que l'arête {i, j} reliant le noeud i au noeud j est identique à l'arête {j, i} et est représentée par une paire non ordonnée. En revanche, les arêtes d'un graphe orienté ont une orientation, c'est-à-dire que les arêtes (i, j) et (j, i) sont distinctes et sont représentées par une paire ordonnée. Dans un multigraphe, par opposition à un graphe simple, on autorise plusieurs arêtes à relier la même paire de noeuds et qu'un noeud soit connecté à lui-même par une boucle.

Un graphe peut être tracé sur le plan en utilisant par exemple des cercles pour les noeuds et des lignes ( échées pour les graphes orientés) entre eux pour les arêtes. Il peut également être représenté par sa matrice d'adjacence ; voir la Figure 1 pour une illustration. La matrice d'adjacence d'un graphe est une matrice carrée (z ij ) où les lignes et les colonnes représentent le même ensemble de noeuds et chaque entrée z ij représente la connexion entre le noeud i et le noeud j. L'entrée z ij est égale à un si i est connecté à j et zéro sinon et la diagonale contient d'éventuelles boucles. La matrice d'adjacence est symétrique si le graphe est non orienté et non symétrique s'il est orienté.

La densité du graphe est la proportion de uns dans la matrice d'adjacence, ou le nombre d'arêtes divisé par le nombre total d'arêtes potentielles. Il s'agit d'une approximation de la probabilité de connexion de deux noeuds aléatoires. La distinction entre les graphes denses et creux n'est pas claire, mais elle peut être dé nie en observant la croissance du nombre d'arêtes par rapport au nombre de noeuds. Nous utiliserons la quali cation de graphe dense lorsque le nombre d'arêtes croît quadratiquement avec le nombre de noeuds, et creux s'il croît sousquadratiquement. De nombreux réseaux du monde réel sont considérés comme creux, c'est par conséquent un aspect important à capturer dans les modèles de réseau.

Pour les graphes simples, le degré d'un noeud est le nombre d'arêtes qui lui sont connectées et par extension le nombre de noeuds qui lui sont adjacents. Une caractéristique importante d'un graphe qui est étroitement liée à la densité est sa distribution des degrés, c'est-à-dire la loi de probabilité du degré d'un noeud aléatoire du graphe Pr(d = k ) pour k ∈ N. Il a été observé que de nombreux réseaux réels présentent une distribution des degrés empirique à queue lourde, c'est-à-dire qu'une grande majorité de noeuds ont un très faible degré, tandis qu'un petit nombre de noeuds, appelés « hubs », ont un degré élevé. Il est intéressant de noter que certains réseaux réels, tels que le World Wide Web, ont une distribution des degrés qui suit approximativement une loi de puissance [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF][START_REF] Clauset | Power-law distributions in empirical data[END_REF] Pr(d = k ) ∝ k -γ où γ > 0 est une constante. Ces réseaux sont quali és de réseaux sans échelle et leur analyse et leur modélisation sont le sujet d'une attention particulière.

Au-delà des propriétés précédentes sur l'échelle globale des réseaux, une autre caractéristique commune des réseaux complexes est la structure communautaire, c'est-à-dire que les noeuds du réseau peuvent être regroupés en ensembles de noeuds (se chevauchant potentiellement) de telle sorte que chaque ensemble de noeuds soit plus densément intra-connecté. Cette propriété est basée sur le principe de l'assortativité, c'est-à-dire que des paires de noeuds sont plus susceptibles d'être connectées si les deux noeuds sont membres des mêmes communautés et moins susceptibles d'être connectées s'ils ne partagent pas les mêmes communautés. La détection des communautés est essentielle pour acquérir une connaissance de la topologie du réseau ainsi que pour la prédiction des liens.

Jusqu'à présent, nous avons considéré des graphes unipartis où des connexions peuvent exister entre tous les noeuds d'un seul et même type. En revanche, un graphe biparti est un graphe dans lequel les noeuds peuvent être divisés en deux ensembles, A et B, de sorte que seules les connexions entre deux noeuds d'ensembles di érents sont autorisées. Les données des systèmes de recommandation peuvent être considérées comme une sorte de réseau biparti non orienté entre deux types de noeuds : les utilisateurs et les articles. Les données de feedback explicite sont considérées comme des pondérations ou des étiquettes sur les arêtes ; voir la Figure 2 pour une illustration. Faire des recommandations correspond alors à prédire des liens dans le réseau biparti.

Comme dans les réseaux simples, les comportements de parcimonie (réseaux creux) et en loi de puissance sont également présents dans les systèmes de recommandation. La plupart des vues, clics ou achats se concentrent généralement sur quelques articles « blockbusters » alors que la grande majorité des articles restants, appartenant à la « longue traîne », ont une très faible popularité. La modélisation de ces comportements est cruciale puisque les systèmes de recommandation sont généralement conçus pour aider à in uencer les ventes sur ces articles issus de la longue traîne et pour proposer à leurs utilisateurs une découverte plus fortuite de nouveaux articles.

Modélisation probabiliste et inférence bayésienne

Bien que diverses approches puissent être envisagées pour les systèmes de recommandation et les réseaux, les contributions de cette thèse s'appuieront sur des modèles probabilistes. Comparativement aux approches plus prototypes, l'avantage des approches fondées sur les modèles est qu'elles sont interprétables et exibles. L'apprentissage d'un tel modèle apporte une ix connaissance sur la manière dont les données sont générées, sur leur structure, et permet la prédiction d'observations futures. Les approches probabilistes considèrent que les données D proviennent d'une loi de probabilité appelée vraisemblance p(D|ϕ) conditionnée à un ensemble de paramètres ϕ ∈ Φ, qui peut représenter e.g. les paramètres d'intérêt de chaque utilisateur pour des facteurs latents comme l'action, la comédie, la sciencection, etc. pour les lms. Cette distribution caractérise tout phénomène aléatoire intrinsèque ou de bruit potentiel en jeu dans la génération et la mesure des données. Nous allons en outre adopter un cadre bayésien [START_REF] Gelman | Bayesian data analysis[END_REF] en supposant que le paramètre lui-même est une variable aléatoire avec une distribution a priori p(ϕ) qui caractérise la croyance ou l'incertitude a priori sur ce paramètre. Dans ce contexte, toute l'information disponible sur le paramètre inconnu ϕ est capturée par la distribution a posteriori qui est donnée par la règle de Bayes p(ϕ |D) = p(D|ϕ)p(ϕ) p(D) ∝ p(D|ϕ)p(ϕ) où la vraisemblance marginale p(D) est une constante qui ne dépend que des données.

Nous nous intéressons à une telle inférence sur le paramètre inconnu ϕ basée sur la distribution a posteriori, mais nous allons encore distinguer deux types d'objectifs. Si nous voulons obtenir une estimation ponctuelle, nous pouvons maximiser la distribution a posteriori et obtenir une estimation du maximum a posteriori (MAP) antérieures. Dans un souci de simplicité, nous allons aussi dériver des cas particuliers dans cette thèse, mais le lecteur doit garder à l'esprit que le cadre proposé est assez général.

En n, la complexité et le passage à l'échelle (scalability) de nos algorithmes sont une préoccupation particulière. Bien que nos expériences se limitent à des ensembles de données d'une échelle raisonnable, nous gardons à l'esprit que dans le contexte de « données massives », la complexité de nos algorithmes doit croître linéairement avec le nombre d'objets (utilisateurs/articles pour les systèmes de recommandations ou noeuds pour les graphes) et le nombre d'évènements observés (notes, étiquettes ou connexions).

La suite de la thèse est divisée en deux parties qui peuvent être lues indépendamment. Chaque partie est composée de deux chapitres où le premier chapitre introduit les prérequis nécessaires ou les travaux préexistant tandis que le deuxième chapitre développe une contribution originale.

I Modèles probabilistes à rang faible pour les systèmes de recommandation

Dans la première partie, nous nous concentrons sur les systèmes de recommandation avec feedback explicite et nous développons une approche probabiliste de factorisation de rang faible.

Le Chapitre 1 introduit le problème de la complétion de matrice pour les systèmes de recommandation. Nous commençons par un aperçu des di érentes approches pour la construction des systèmes de recommandation : le ltrage basé sur le contenu, le ltrage démographique, le ltrage collaboratif et le ltrage hybride. Nous nous concentrons sur l'approche de ltrage collaboratif qui exploite uniquement la matrice incomplète des notations des utilisateurs. Nous fournissons ensuite quelques prérequis sur les méthodes existantes de rang faible pour la complétion de matrice qui supposent essentiellement que la matrice de notes incomplète a une structure de rang faible. L'hypothèse de rang faible a une interprétation simple : chaque utilisateur et article peut être décrit par un petit nombre de caractéristiques latentes et la note de l'utilisateur i pour l'élément j peut être expliquée par la correspondance entre leurs caractéristiques respectives. En particulier nous décrivons l'algorithme Soft-Impute de [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] qui résout un problème convexe régularisé par la norme nucléaire.

Le Chapitre 2 propose une nouvelle classe d'algorithmes de régularisation spectrale adaptative pour la complétion de matrice de rang faible. Il s'agit d'une version étendue de notre publication lors de la conférence NIPS 2013 [START_REF] Todeschini | Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms[END_REF]. Notre approche s'appuie sur de nouvelles fonctions de pénalité sur les valeurs singulières de la matrice de rang faible. L'origine de notre travail consiste à donner une interprétation probabiliste au problème de régularisation par la norme nucléaire où la distribution a priori sur l'ensemble des valeurs singulières peut alors être remplacée par des choix plus exibles. En particulier, un a priori hiérarchique est très utile pour plusieurs raisons. Chaque valeur singulière peut être gouvernée par son propre paramètre de régularisation ce qui est facile à interpréter. Les paramètres sont considérés comme des variables latentes et sont automatiquement adaptés grâce à une distribution a priori au niveau supérieur (hyperprior). Notre construction permet de faire le pont entre la pénalité convexe de la norme nucléaire et la pénalité de rang.

En exploitant une représentation basée sur un modèle de mélange de cette pénalité, nous montrons que le problème résultant peut être facilement décomposé en deux étapes itératives sous la forme d'un algorithme espérance-maximisation (EM) pour obtenir une estimation du xi maximum a posteriori (MAP) de la matrice de rang faible complétée. L'étape E peut être obtenue analytiquement pour une famille de distributions convenablement choisies. L'étape M consiste en une décomposition en valeur singulière à seuillage doux pondéré qui pénalise moins fortement les valeurs singulières supérieures, réduisant ainsi le biais de la règle de seuillage doux uniforme utilisée dans l'algorithme Soft-Impute. Notre algorithme adapte de manière itérative les coe cients de réduction associés aux valeurs singulières. Il est simple à mettre en oeuvre et peut être adapté aux grandes matrices. L'extension aux matrices binaires est également décrite.

Nous fournissons des comparaisons numériques entre notre approche et les alternatives récentes montrant l'intérêt de l'approche proposée pour la complétion de matrice de rang faible. La classe de méthodes proposée fournit de bons résultats par rapport à plusieurs compétiteurs. Bien que le problème d'optimisation associé ne soit pas convexe, nos expériences montrent qu'une initialisation avec l'algorithme Soft-Impute de [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] donne des résultats très satisfaisants. Nous montrons également que les prédictions sont améliorées dans des applications du monde réel. Cependant, dans cette première partie, nous ignorons totalement le feedback implicite donné par la distribution des entrées dans la matrice incomplète.

II Modèles bayésiens non paramétriques pour les réseaux

Dans la deuxième partie, nous nous concentrons sur les réseaux et nous développons une approche bayésienne non paramétrique.

Le Chapitre 3 introduit le contexte nécessaire sur les méthodes bayésiennes non paramétriques (BNP) dans lesquelles le paramètre d'intérêt est de dimension in nie. Ce cadre permet à la complexité du modèle de s'adapter au nombre croissant de données, et de pouvoir découvrir plus de structure ou de motifs lorsque nous observons davantage de données. Il fournit donc un cadre à la fois adaptatif et robuste [START_REF] Müller | Nonparametric Bayesian data analysis[END_REF][START_REF] Orbanz | Bayesian nonparametric models[END_REF]. Une autre caractéristique attrayante des modèles BNP est qu'ils permettent de capturer le comportement en loi de puissance dans les données. D'un point de vue mathématique, les méthodes BNP nécessitent l'élaboration d'une loi a priori sur un espace de dimension in nie, et nous travaillons en général avec des processus stochastiques plutôt que des vecteurs aléatoires. Plus précisément, les outils que nous utiliserons ici sont des mesures complètement aléatoires (CRM) et leurs homologues multivariés, les CRM composées (compound CRMs). Avant d'étudier ces objets plus en détail, nous présentons une brève analyse des processus de Poisson, à partir desquels ils peuvent être construits.

Le Chapitre 4 propose un nouveau modèle statistique pour les réseaux creux en structure communautaire avec chevauchement (sparse networks with overlapping community structure). Ce travail est sur le point d'être soumis à une revue statistique [START_REF] Todeschini | Exchangeable random measures for sparse and modular graphs with overlapping communities[END_REF]. Le modèle est basé sur la représentation du graphe par un processus ponctuel échangeable, et généralise naturellement des modèles probabilistes existants à structure en blocs avec chevauchement au régime creux.

Nous considérons que chaque noeud i est a ecté d'un ensemble de paramètres latents nonnégatifs w ik , k = 1, . . . , p, et que la probabilité que deux noeuds i j se connectent est donnée par Pr(z ij = 1|(w 1 , . . . , w p ) =1,2,... ) = 1 -e -2 p k=1 w ik w jk .

(1)

Ces poids non négatifs peuvent être interprétés comme mesurant le niveau d'a liation du noeud i aux communautés latentes k = 1, . . . , p. Par exemple, dans un réseau d'amitié, ces xii communautés peuvent correspondre à des collègues, à la famille ou à des partenaires sportifs et les poids mesurent le niveau d'a liation d'un individu à chaque communauté. Notez que, puisque les individus peuvent avoir des poids élevés dans di érentes communautés, le modèle peut capturer des communautés qui se chevauchent. La principale contribution de ce chapitre est d'utiliser la probabilité de connexion (1) dans le cadre de processus ponctuels de [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF]. Pour ce faire, nous considérons que les positions et les poids des noeuds (w i1 , . . . , w ip , θ i ) i=1,2,... sont tirés d'un processus ponctuel de Poisson dans R p+1 + avec une mesure moyenne ν donnée. La construction d'un tel processus ponctuel multivarié repose sur des vecteurs de CRMs. En particulier, nous nous appuyons sur les CRM composées (compound CRMs) à la fois souples et analytiquement manipulables récemment introduites par Gri n and [START_REF] Gri N | Compound random measures and their use in Bayesian nonparametrics[END_REF].

Le modèle proposé généralise celui de Caron and Fox (2014) en permettant au modèle de capturer plus de structure dans le réseau, tout en conservant ses principales caractéristiques, et révèle avoir les propriétés suivantes :

• Interprétabilité : chaque noeud reçoit un ensemble de paramètres positifs qui peuvent être interprétés comme mesurant les niveaux d'a liation d'un noeud à des communautés latentes ; une fois que ces paramètres sont appris, ils peuvent être utilisés pour devoiler la structure latente du réseau. • Parcimonie : nous pouvons générer des graphes creux, dont le nombre d'arêtes croît sous-quadratiquement avec le nombre de noeuds. • Echangeabilité : au sens de [START_REF] Kallenberg | Exchangeable random measures in the plane[END_REF]. De plus, nous développons des méthodes pour simuler cette classe de graphes aléatoires, ainsi qu'un algorithme MCMC passant à l'échelle pour l'inférence a posteriori des paramètres latents de communauté et hyperparamètres de ce modèle. Nous fournissons des illustrations de la méthode proposée sur données simulées et sur deux réseaux réels avec un millier de noeuds et des dizaines de milliers d'arêtes : un réseau de citations entre des blogs politiques et un réseau de connexions entre les aéroports américains. Nous montrons que l'approche est capable à la fois de découvrir une structure interprétable dans les données et de capturer les distributions des degrés en loi de puissance. Notre développement se concentre sur des réseaux simples, mais il peut également être appliqué à un graphe biparti qui peut représenter le feedback implicite d'un système de recommandation.

Introduction

I Probabilistic low-rank models for recommender systems

Introduction

We introduce all the subjects covered in this thesis while emphasizing the connections between them. Rather than providing a general bibliographic study, our objective is to motivate our work for a general audience and answer the questions: Why are these topics interesting? What speci c choices have been adopted? All reference to existing research work will be introduced in the subsequent chapters.

Recommender systems

The past 20 years have seen a growing interest for recommender systems. They complement traditional search engines to help us handle the information overload faced since the advent of the digital age. Which book should I read? Which movie should I watch? Which product should I buy? Making such decisions is less and less feasible for a simple human being as the number of available items is constantly growing and becomes unmanageable. We all need some sort of information ltering to discriminate the relevant from the irrelevant. While search engines aim at answering speci c queries asked by the user which roughly knows what she is looking for, recommender systems take on a di erent approach. They try to automate the experience of discovery by providing us what we want before we know it. One fundamental aspect is that those recommendations have to be personalized and thus re ect a good understanding of the user's preferences.

It is not surprising that recommender systems have attracted a lot of attention in commercial applications. It is well known that personalization improves customer satisfaction and is therefore a key to increase conversion rates. E-commerce platforms like Amazon.com provide a variety of on-site recommendations like "customers who bought this item also bought" or personalized co-purchase recommendations based on the content of your cart but also lists of recommendations sent via email [START_REF] Linden | Amazon.com recommendations: Item-to-item collaborative ltering[END_REF]. Arguably a lot of their success has to do with the way recommendations are integrated into nearly every part of the purchasing process. Besides products, recommender systems apply to a wide range of domains, in particular to all types of media content: news/blog/research articles, bookmarks, books, movies, TV shows, music etc. but also locations: restaurants, hotels, etc. or mobile applications among others.

In particular, movies recommendation has been popularized by the Net ix prize [START_REF] Bennett | The Net ix prize[END_REF], a competition held by Net ix, an American multinational company specialized in video on demand. The goal was to predict user ratings for lms, based on previous ratings, without any other information about the users or lms. In 2009, the grand prize of $1, 000, 000 was given to the BellKor's Pragmatic Chaos team which outperformed Net ix's own ratings prediction algorithm by over 10% [START_REF] Koren | The BellKor solution to the Net ix grand prize[END_REF][START_REF] Piotte | The Pragmatic theory solution to the Net ix grand prize[END_REF]. The development of recommender systems, their evaluation and application to diverse real-world problems is a very active research eld. First developed in the eld of information retrieval, they are now at the intersection of a lot of research domains including computer science, machine learning and statistics.

Recommender systems predict user preferences from the "big data" collected over up to several millions of users and items. Item content as well as user demographic data are important but the most valuable data is the feedback from users to items. Users feedback can either be explicit or implicit. Explicit feedback is given by the users in form of rating or label which express positive or negative interest explicitly. This kind of data is generally incomplete. The set of all labeled user-item pairs are considered as observed data and all the rest is missing. In contrast, implicit feedback is collected from the users behavior like clicks, views or purchase events. This kind of feedback is weaker than the explicit ratings but is implicitly related to the underlying preferences of the user. A user is more likely to click or purchase items she likes, however an absence of event is a weaker information as the user might just not know the existence of the item. This kind of implicit data is completely observed.

Networks

Closely related to the eld of recommender systems is the analysis, understanding and modeling of complex network data (Newman, 2003a[START_REF] Newman | Networks: an introduction[END_REF]. Network data arise in a wide range of elds and include social networks, collaboration networks, telecommunication networks, biological networks, food webs and are a useful way of representing interactions between sets of objects. A network can be represented by a graph which is composed of a set of nodes, or vertices, with connections, called edges or links, between them.

A graph can be drawn on the plane using e.g. circles for nodes and lines (arrows for directed graphs) between them for edges. It can also be represented by its adjacency matrix; see Figure 1 for an illustration. The adjacency matrix of a graph is a squared matrix (z ij ) where rows and columns represent the same set of nodes and each entry z ij represents the connection between node i and node j. The entry z ij is one if i is connected to j and zero otherwise and the diagonal contains eventual self-loops. The adjacency matrix is symmetric if the graph is undirected, and not symmetric if it is directed.

The density of the graph is the ratio of ones in the adjacency matrix, or the number of edges divided by the total number of potential edges. It is an approximation of the probability of connection of two random nodes. The distinction between dense and sparse graphs is not clear-cut but it can be de ned by observing the growth of the number of edges compared to the number of nodes. We refer to graphs whose number of edges scales quadratically with the number of nodes as dense, and sparse if it scales sub-quadratically. Many real world networks are considered sparse and this is an important aspect to capture in network models.

For simple graphs, the degree of a node is the number of edges connected to it and by extent the number of nodes adjacent to it. An important characteristic of a graphs which is closely related to the density is its degree distribution, i.e. the probability distribution of the degree d of a random node of the graph Pr(d = k ) for k ∈ N. It has been observed that many real networks exhibit a heavy-tailed empirical degree distribution, i.e. a large majority of nodes have a very low degree but a small number, known as "hubs", have high degree. Notably, some real networks, like e.g. the World Wide Web, have degree distributions that approximately follow a power-law [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF][START_REF] Clauset | Power-law distributions in empirical data[END_REF] Pr

(d = k ) ∝ k -γ
where γ > 0 is a constant. Such networks are called scale-free networks and have attracted particular attention to their analysis and modeling.

Beyond the previous global scale properties of networks, another common characteristic of complex networks is community structure, i.e. nodes of the network can be grouped into (potentially overlapping) sets of nodes such that each set of nodes is more densely connected internally. It is based on the principle of assortativity, saying that pairs of nodes are more likely to be connected if they are both members of the same communities, and less likely to be connected if they do not share communities. Identifying communities is essential in providing insight on the topology of the network as well as performing link prediction.

So far we have considered unipartite graphs where connections can exist between all nodes of a single type. A bipartite graph is a graph in which the set of nodes can be partitioned into two sets, A and B, so that only connections between nodes of di erent sets are allowed. Recommender systems data may be viewed as a particular kind of undirected bipartite network between two types of nodes: users and items. The explicit feedback data is considered as weights or labels of the edges; see Figure 2 for an illustration. Making recommendations corresponds to predicting links in the bipartite network.

As in simple networks, sparsity and power-law behaviors are also present in recommender systems. Most of the views or purchase generally concentrate on a few "blockbuster" items while the large majority of the remaining items, a.k.a. the "long tail", have very low popularity. Capturing these behaviors is crucial since recommender systems are generally designed to help leveraging the sales on these long tail items and to propose their users a more serendipitous discovery of new items.

Probabilistic modeling and Bayesian inference

While a variety of approaches can be considered for recommender systems and networks, the contributions of this thesis will build on probabilistic models. Compared to more prototype approaches, the advantage of model-based approaches is their interpretability and exibility.

Learning such a model provides insights on how the data is generated, how it is structured and allows to predict future observations. Probabilistic approaches consider that the data D arise from some probability distribution called the likelihood

p(D|ϕ)
conditioned on a set of parameters ϕ ∈ Φ, which can represent e.g. the parameters of interest of each user to some latent factors like action, comedy, science ction, etc. for movies. This distribution characterizes any intrinsic random phenomena or potential noise at stake in the generation and measurement of the data. We will further adopt a Bayesian framework [START_REF] Gelman | Bayesian data analysis[END_REF] by assuming that the parameter itself is a random variable with some prior distribution p(ϕ)

which characterizes the prior belief or uncertainty on this parameter. In this context, all the information available on the unknown parameter ϕ is captured by the posterior distribution which is given by the Bayes rule

p(ϕ |D) = p(D|ϕ)p(ϕ) p(D) ∝ p(D|ϕ)p(ϕ)
where the so-called marginal likelihood p(D) is a constant which only depends on the data.

We are interested in such inference on the unknown parameter ϕ based on a posterior distribution but we will further distinguish two kinds of objectives. If we are interested in obtaining a single point estimate, we can maximize the posterior distribution and obtain a maximum a posteriori (MAP) estimate ϕ = arg max ϕ∈Φ p(D|ϕ)p(ϕ).

To solve this problem we generally resort to iterative optimization procedures which start from an initial guess and increase the objective function until convergence. In this thesis, we will derive such an iterative algorithm by exploiting suitably chosen latent variables of the model. Such posterior maximization methods are referred to as "probabilistic" in the literature.

By contrast, "full Bayesian" methods aim at approximating the whole posterior distribution which might be very complex, such as being multimodal. Among other techniques, we can resort to Monte-Carlo simulation. In particular, we are interested in Markov chain Monte Carlo (MCMC) algorithms, whose objective is to generate samples (ϕ (t ) ) t=1,2,... from a Markov chain which admits the target distribution, here p(ϕ |D), as equilibrium distribution.

In Bayesian nonparametrics [START_REF] Hjort | Bayesian nonparametrics[END_REF], the parameter of interest is in nite-dimensional and is treated as a stochastic process rather than a random vector. This framework is particularly interesting for several reasons. The number of objects considered might be very large and constantly growing, therefore it makes sense to consider the limiting case where it tends to in nity. Such a framework has also proved to be elegant and useful to capture the power-law behavior of random phenomena.

In addition, we will be concerned by the exibility of our models. We propose somehow general formulations that encompass various special cases, including previous research contributions. For the sake of simplicity, we will also derive such special cases in this thesis but the reader should keep in mind that the proposed framework is quite general.

Finally, the complexity and scalability of our algorithms is of particular concern. While our experiments restrict to datasets of rather reasonable scale, we keep in mind that in the context of "big data", our algorithms should scale linearly with the number of objects (users, items for recommender systems or nodes for graphs) and the number of observed events (ratings or connections).

Outline of the thesis

The rest of the thesis is divided into two parts that can be read independently. Each part is made of two chapters where the rst chapter introduces the necessary background or preexisting work while the second chapter develops an original contribution.

In the rst part, we concentrate on recommender systems with explicit feedback and we develop a probabilistic low-rank factorization approach.

Chapter 1 introduces the matrix completion problem for recommender systems. We start with an overview of the di erent approaches for building recommender systems with emphasis on the popular collaborative ltering techniques. Then, we provide some background on existing low-rank methods for matrix completion which basically assume that the incomplete ratings matrix has a low-rank structure.

Chapter 2 proposes a novel class of algorithms for low-rank matrix completion that builds on a probabilistic interpretation of the nuclear norm regularization problem. We show in our experiments that our algorithm can outperform existing approaches. This work has been published in the proceedings of the NIPS 2013 international conference [START_REF] Todeschini | Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms[END_REF].

In the second part, we concentrate on networks and develop a Bayesian nonparametric approach.

Chapter 3 introduces the necessary background on Bayesian nonparametrics. After a general review of the Poisson process, we focus on completely random measures (CRMs) and one of their multivariate counterpart, the compound CRMs.

Chapter 4 proposes a novel statistical model for sparse networks with overlapping community structure. It builds on the previously introduced compound CRMs and the posterior inference uses MCMC algorithms. We show in our experiments that our model can capture power-law properties of real-world graphs and that the inferred communities are meaningful. This work is about to be submitted to a statistical journal [START_REF] Todeschini | Exchangeable random measures for sparse and modular graphs with overlapping communities[END_REF].

We nally conclude this thesis by giving a summary of our results and opening up some perspectives.

Part I Probabilistic low-rank models for recommender systems

Chapter 1

Matrix completion for recommender systems

Matrix completion consists in lling an incomplete matrix from a subset of its entries. In Section 1.1 we motivate this problem through the popular application of recommender systems. Section 1.2 gives an overview of the more speci c collaborative ltering approach. Finally Section 1.3 presents the matrix completion problem in rather general terms and reviews the literature on low-rank techniques for solving it.

Recommender systems

Several surveys have already been published on recommender systems [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF][START_REF] Melville | Recommender systems[END_REF][START_REF] Ricci | Introduction to recommender systems handbook[END_REF][START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF][START_REF] Lü | Recommender systems[END_REF][START_REF] Park | A literature review and classi cation of recommender systems research[END_REF][START_REF] Bobadilla | Recommender systems survey[END_REF][START_REF] Shi | Collaborative ltering beyond the user-item matrix: A survey of the state of the art and future challenges[END_REF]. The objective of the latter is to recommend to each user the items that she might like. In this section, we give a brief overview on the subject. After a formal de nition we discuss the challenges encountered when designing such systems and the major approaches that have been proposed in the literature. The reader should refer to the aforementioned surveys for a more detailed overview.

Definition

We consider a set of users I = {1, . . . , m} and a set of items J = {1, . . . , n}. Though in the simplest case, users and items are only represented by their unique identi er, they may possess additional attributes (called side-information, features, covariates or meta-data). We are interested in the explicit feedback context (see the Introduction chapter), where each user provides a rating or label to a (user-speci c) subset of the items. We denote x ij ∈ X the rating given by user i to item j, which can be on a continuous scale (X = R, X = [a, b]) or on a discrete scale (1 to 5 stars: X = {1, . . . , 5}, like/dislike: X = {1, -1}) and X = (x ij ) the m × n incomplete user-item ratings matrix. Let Ω ⊆ I × J be the subset of user-item pairs for which a rating is observed

Ω = {(i, j)|x ij is observed}
and Ω ⊥ = (I × J )\Ω its complementary.

Rating prediction task. The rating prediction task consists in predicting ratings x ij for unobserved user-item pairs (i, j) ∈ Ω ⊥ . A predictor is a function F : I × J -→ X which provides an estimate

x ij = F (i, j)
for all (i, j) ∈ I×J . In the presence of side-information, F might also depend on the attributes of user i and item j. The predictor F is typically learned from the available data using statistical learning methods; see Section 1.1.3.

Top-N recommendation task. A recommender system generally provides its users with personalized lists of items of high interest. A simple strategy is to recommend to each user the list of N most relevant items based on the predicted ratings. Yet, making top-N lists does not necessarily require ratings or scores and it is popular to directly address the ranking task (a.k.a. learning to rank, [START_REF] Burges | Learning to rank using gradient descent[END_REF][START_REF] Liu | Learning to rank for information retrieval[END_REF][START_REF] Rendle | BPR: Bayesian personalized ranking from implicit feedback[END_REF].

Challenges

Recommender systems have to face many challenges and we review the major ones in this section.

Scalability. One of the major challenges is to develop methods that can scale up to millions of users and items of e.g. online retailers like Amazon.com and provide real-time recommendations on a fast changing system.

Sparsity. One important quantity is the density of the m × n matrix X = (x ij ) dens (X ) = |Ω| mn or equivalently its sparsity, 1 -dens (X ). The more missing entries, the higher the sparsity and the more di cult it is to learn user preferences. Users generally rate very few items, thus the matrix X = (x ij ) is generally very sparse. In such a context, it is crucial to avoid over tting, i.e. performing well on past training data but failing to generalize to unobserved data. Yet, for computational complexity reasons, most prediction methods cannot handle large dense matrices and the sparsity must be used as a computational advantage with methods that scale with |Ω| mn.

Cold-start. Most recommender systems have to address cold-start problems [START_REF] Schein | Methods and metrics for cold-start recommendations[END_REF], i.e. facing situations where too few data have been collected to be able to provide reliable predictions. Two typical cold-start problems are the new user problem and the new item problem. How to provide recommendations to a new user who has not rated any or very few items, corresponding to an empty row in the matrix X ? Similarly how to make predictions when a new item is added to the system and has not been rated by enough users? These problems are generally addressed by using additional attributes on either the new user or the new item, that can relate her/it to previously rated ones [START_REF] Lam | Addressing cold-start problem in recommendation systems[END_REF].

Long tail. Let be the frequency of item j in Ω. This corresponds to the number of users having rated item j or the number of entries in j-th column of matrix X . The frequency of an item is also a measure of its popularity. When ranking items by decreasing popularity, typical datasets exhibit a long tail behavior [START_REF] Brynjolfsson | From niches to riches: Anatomy of the long tail[END_REF][START_REF] Elberse | Superstars and underdogs: An examination of the long tail phenomenon in video sales[END_REF][START_REF] Hitt | The long tail: Why the future of business is selling less of more[END_REF], which means that few items are very popular while a majority have very few ratings. This is related to the Pareto principle [START_REF] Brynjolfsson | Goodbye Pareto principle, hello long tail: The e ect of search costs on the concentration of product sales[END_REF] a.k.a. the 80/20 rule of thumb in business: 20% of the most popular items represent 80% of the occurrences while the remaining 80% least popular items represent 20% of the occurrences; see Figure 1.1. One major challenge of recommender systems is to compensate this imbalance, i.e. to make reliable predictions on the long tail items, so as to avoid recommending only the popular items and increase novelty [START_REF] Fleder | Blockbuster culture's next rise or fall: The impact of recommender systems on sales diversity[END_REF].

f j = n i=1 1 (i,j)∈Ω
Evaluation. Finally, evaluating the performance of a recommender system is a complicated task [START_REF] Herlocker | Evaluating collaborative ltering recommender systems[END_REF][START_REF] Breese | Empirical analysis of predictive algorithms for collaborative ltering[END_REF][START_REF] Cremonesi | Performance of recommender algorithms on top-n recommendation tasks[END_REF][START_REF] Shani | Evaluating recommendation systems[END_REF]. Making good recommendations is not trivial and may involve considering criteria beyond relevance like e.g. novelty or diversity [START_REF] Ziegler | Improving recommendation lists through topic diversi cation[END_REF][START_REF] Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF][START_REF] Ge | Beyond accuracy: evaluating recommender systems by coverage and serendipity[END_REF][START_REF] Zhou | Solving the apparent diversity-accuracy dilemma of recommender systems[END_REF][START_REF] Vargas | Rank and relevance in novelty and diversity metrics for recommender systems[END_REF].

Approaches

The di erent approaches have been classi ed according to the source of data they exploit in order to make predictions [START_REF] Resnick | Grouplens: an open architecture for collaborative ltering of netnews[END_REF][START_REF] Shardanand | Social information ltering: algorithms for automating "word of mouth[END_REF][START_REF] Balabanović | Fab: content-based, collaborative recommendation[END_REF][START_REF] Pazzani | A framework for collaborative, content-based and demographic ltering[END_REF]; see Figure 1.2. Originally, recommender systems were seen as an information ltering task: how to lter relevant items from irrelevant ones?

Content-based filtering. Content-based ltering [START_REF] Pazzani | Content-based recommendation systems[END_REF][START_REF] Lops | Content-based recommender systems: State of the art and trends[END_REF] discriminates relevant items based on their content. They recommend to each user sim- ilar items to the ones she has liked in the past. A majority of these approaches concentrate on textual content but the content can be any set of features. New items can get recommended based on their content even if nobody has ever rated them. However, this early ltering approach has strong limitations as it keeps the user in the "bubble", never recommending items too di erent from its historical data.

Demographic-based filtering. Demographic-based ltering [START_REF] Krulwich | Lifestyle nder: Intelligent user pro ling using large-scale demographic data[END_REF] predicts ratings of a speci c user based on the ratings given by similar users based on their demographic attributes like gender, age, occupation, etc. regardless of the content of the items. It can address the new user problem but, like content-based ltering, it keeps the user in a socio-demographic bubble which might not be relevant to its preferences. In the literature, this approach is often considered as some sort of content-based ltering using content about the users.

Collaborative filtering. Collaborative ltering (CF, [START_REF] Goldberg | Using collaborative ltering to weave an information tapestry[END_REF][START_REF] Herlocker | An algorithmic framework for performing collaborative ltering[END_REF] is one of the most successful approaches. Rather than relying on side information, this approach only exploits the user-item ratings matrix. The information is ltered according to other users opinions, regardless of the content or demographic data. This approach is very simple and general as it applies to any kind of item. Though, it generally better captures human behavior than the previous approaches. However, CF su ers from the cold-start problems and requires users and items to have a minimum number of ratings as well as a rather homogeneous dispersion of the entries.

Hybrid filtering. Hybrid ltering approaches take the most of both previous methods by exploiting all available data from content, demographic data and collaborative ratings [START_REF] Balabanović | Fab: content-based, collaborative recommendation[END_REF][START_REF] Basu | Recommendation as classi cation: Using social and content-based information in recommendation[END_REF][START_REF] Melville | Content-boosted collaborative ltering for improved recommendations[END_REF], so as to address cold-start problems. They are very diverse, ranging from combinations of the predictions from the above predictors [START_REF] Claypool | Combining content-based and collaborative lters in an online newspaper[END_REF][START_REF] Good | Combining collaborative ltering with personal agents for better recommendations[END_REF] to single uni ed models [START_REF] Popescul | Probabilistic models for uni ed collaborative and content-based recommendation in sparse-data environments[END_REF]. See the survey of [START_REF] Burke | Hybrid recommender systems: Survey and experiments[END_REF] for an overview on the subject.

Collaborative filtering

In this section, we describe two general classes of CF methods [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative ltering[END_REF]. Memorybased methods operate over the entire collection of observed data (or memory of the system) to make predictions. In contrast, model-based methods use the data to t a parameterized model, which is then used for predictions. Beyond, hybrid methods exploiting both memory and model-based techniques have also been proposed [START_REF] Pennock | Collaborative ltering by personality diagnosis: A hybrid memory-and model-based approach[END_REF][START_REF] Sarwar | Application of dimensionality reduction in recommender system-a case study[END_REF][START_REF] Goldberg | Eigentaste: A constant time collaborative ltering algorithm[END_REF][START_REF] Xue | Scalable collaborative ltering using cluster-based smoothing[END_REF]. The interested reader can refer to several surveys for more details [START_REF] Schafer | Collaborative ltering recommender systems[END_REF][START_REF] Su | A survey of collaborative ltering techniques[END_REF][START_REF] Koren | Advances in collaborative ltering[END_REF].

Memory-based methods

In memory-based methods, the predictor x ij = F (i, j) is a function of the entire collection of observed data. The most popular methods of this class are the neighborhood-based methods [START_REF] Herlocker | An algorithmic framework for performing collaborative ltering[END_REF][START_REF] Herlocker | An empirical analysis of design choices in neighborhood-based collaborative ltering algorithms[END_REF][START_REF] Desrosiers | A comprehensive survey of neighborhood-based recommendation methods[END_REF].

User-based similarity methods. Denote J i = {j |(i, j) ∈ Ω} ⊆ J the set of items rated by user i, then the average observed rating of user i is

x i = 1 |J i | j∈J i x ij .
We generally assume that the predicted rating of user i for item j is a combination of the ratings of other users. More speci cally, consider the following formula using the weighted sum of deviations from their respective mean

x ij = x i + 1 i ∈N i |w (i, i )| i ∈N i w (i, i )(x i j -x i ) (1.1)
where the weights w (i, i ) somehow re ect the similarity or correlation between user i and i where w is a symmetric function. N i ⊆ I\{i} is a neighborhood set containing the k most similar neighbors of user i w.r.t. w. Variations in the aggregation function (1.1) can be introduced but we restrict here to the above formulation. Di erent choices of weighting schemes or similarity functions lead to di erent algorithms. Let J ii = J i ∩ J i be the set of items that both users i and i have rated. Standard similarity metrics include the Pearson's correlation coe cient de ned as

w (i, i ) =          0 if J ii = ∅ j ∈ J ii (x i j -x i )(x i j -x i ) j ∈ J ii (x i j -x i ) 2 j ∈ J ii (x i j -x i ) 2
otherwise.

1.2. Collaborative ltering and the vector cosine similarity de ned (for positive ratings only) as

w (i, i ) =          0 if J ii = ∅ j ∈ J ii x i j x i j j ∈ J ii x 2 i j j ∈ J ii x 2 i j
otherwise.

The complexity of calculating similarities between all users is in O (m 2 ). See e.g. [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative ltering[END_REF] for possible extensions of memory-based methods such as default rating, inverse user frequency or case ampli cation.

Item-based similarity methods. As an alternative to user-based methods which exploit user similarity, [START_REF] Sarwar | Item-based collaborative ltering recommendation algorithms[END_REF] proposed item-based CF. It builds on the same ideas but applied to a transposed matrix X T . Instead of recommending to each user the items liked by similar users, it recommends to each item the users who like similar items. In practice, when the number of users is very large, item-based methods lead to faster online systems, and can lead to improved recommendations [START_REF] Linden | Amazon.com recommendations: Item-to-item collaborative ltering[END_REF][START_REF] Deshpande | Item-based top-n recommendation algorithms[END_REF].

Model-based methods

Model-based methods assume that the predictor is based on a parameterized model F (i, j; θ ) with unknown parameter vector θ . The model must be tted to the observed data in a learning phase before making any predictions. Typically, we want to obtain an estimator of the parameter vector minimizing some objective function

θ = arg min θ L(θ ; X ).
The objective function L captures the tting error on the past data X and possibly some regularization term on θ to penalize the complexity of the model. Regularization is a standard approach to prevent over tting. Over tting generally occurs when a model is excessively complex, such as having too many parameters relative to the number of observations. The objective is to achieve a trade-o between tting the data and reducing the complexity of the solution. Given the estimated parameter vector θ , the model can be used to predict a rating for any user-item pair (i, j) x ij = F (i, j; θ ).

Model-based methods include clustering models [START_REF] Ungar | Clustering methods for collaborative ltering[END_REF][START_REF] Hofmann | Latent class models for collaborative ltering[END_REF], classi cation models [START_REF] Billsus | Learning collaborative information lters[END_REF], regression based models [START_REF] Lemire | Slope one predictors for online rating-based collaborative ltering[END_REF] or restricted Boltzman machines [START_REF] Salakhutdinov | Restricted Boltzmann machines for collaborative ltering[END_REF]. Yet, a recent class of successful model-based CF is the class of latent factor models [START_REF] Hofmann | Latent semantic models for collaborative ltering[END_REF]. They assume that the users and items can be embedded in some low dimensional feature space. Let u i = (u i1 , . . . , u ip ) T ∈ R p be the feature vector of user i and j = ( j1 , . . . , jp ) T ∈ R p be the feature vector of item j. For any user-item pair (i, j), the predictor is a function of the feature vectors

F (i, j; θ ) = F (u i , j ).
The model parameter is θ = (U , V ) where

U = u T 1 . . . u T m and V = T 1 . . . T n
1. Matrix completion for recommender systems denote respectively (resp.) the m × p matrix of user features and the n × p matrix of item features. We then want to estimate

( U , V ) = arg min U ,V L (U , V ; X ) .
Typically, the predictor takes a factorized form F (U , V ) = UV T , i.e. for each user-item pair (i, j), the rating of user i for item j is the dot product between their respective feature vectors

x ij = u T i j = p k=1
u ik jk which measures to which extent those vectors are aligned or "match". In the recommender systems application, factor models have a natural interpretation as it is commonly believed that there is only a small number of factors in uencing the preferences. A wide range of such matrix factorization models have been proposed in the literature [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. More generally, looking for an underlying low-rank representation of the partially observed matrix X has been extensively studied as a low-rank matrix completion task.

Low-rank matrix completion

In this section, we consider the recommendation problem as a matrix completion task and give an overview of low-rank approaches for this task. In the recommender systems literature, these techniques lie in the model-based approaches for collaborative ltering.

Matrix completion

Matrix completion has attracted a lot of attention over the past few years. The objective is to "complete" a matrix of potentially large dimension based on a small (and potentially noisy) subset of its entries [START_REF] Srebro | Maximum-Margin Matrix Factorization[END_REF][START_REF] Candès | Exact matrix completion via convex optimization[END_REF][START_REF] Candès | Matrix completion with noise[END_REF]. Besides recommender systems, applications include image inpainting, where missing pixels in images need to be reconstructed [START_REF] Bertalmio | Image inpainting[END_REF]; imputation of missing data, which is often required as a preprocess for multivariate data analysis [START_REF] Troyanskaya | Missing value estimation methods for dna microarrays[END_REF][START_REF] Donders | Review: a gentle introduction to imputation of missing values[END_REF]; etc.

Recall that X is a m × n matrix whose elements belong to space X and Ω ⊆ {1, . . . , m} × {1, . . . , n} is the subset of its revealed entries (i, j). Following [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF], we introduce the mask operator P Ω (X ) and its complementary P ⊥ Ω (X )

P Ω (X )(i, j) =      x ij if (i, j) ∈ Ω 0 otherwise and P ⊥ Ω (X )(i, j) =      0 if (i, j) ∈ Ω x ij otherwise such that P Ω (X ) + P ⊥ Ω (X ) = X .
We then aim at estimating a complete matrix Z ∈ X m×n minimizing some loss function L over the observed entries of X Z = arg min Z L (P Ω (X ), P Ω (Z )) .

(1.2)

While this framework is quite general, a majority of works have concentrated on real entries (X = R) and the common squared-error or quadratic loss due to its simplicity, convexity and 1.3. Low-rank matrix completion tractability:

L (P Ω (X ), P Ω (Z )) = 1 2σ 2 (i,j)∈Ω x ij -z ij 2 = 1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F (1.3)
where X F = i,j x 2 ij is the Frobenius norm of matrix X and σ 2 > 0. Unless otherwise stated, we are going to concentrate on this particular case as well throughout this section. Though not useful here, we retain the term 1 2σ 2 in the loss function for later convenience. In a typical collaborative ltering application, the problem can be phrased as learning an unknown parameter Z ∈ X m×n with very high dimensionality, based on very few observations. Hence, (1.2) is an ill posed problem which admits in nitely many solutions if X is not nite: any matrix such that P Ω (Z ) = P Ω (X ), i.e. matching the observed entries of X is a solution. We are however interested in solutions that generalize to unobserved entries. For such inference to be meaningful, we assume that the parameter Z lives in a much lower dimensional manifold. To this end, we need to introduce some constraint or prior information on Z .

Low-rank assumption

A simple yet powerful approach is to consider that the matrix Z has a low-rank underlying structure. The rank of a matrix, denoted rank(Z ), is the dimension of the vector space generated by its columns (or rows) and is one of its most fundamental characteristics. This assumption has proved relevant and useful in many real life applications. Projection on low dimensional vector space is standard in exploratory analysis and dimensionality reduction.

Low-rank matrix completion can be addressed by solving the following Frobenius norm minimization problem subject to the non-convex rank constraint minimize

Z 1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F (1.4) s.t. rank(Z ) ≤ p. Singular value decomposition. When X is fully observed, problem (1.4) simpli es to minimize Z 1 2σ 2 X -Z 2 F (1.5) s.t. rank(Z ) ≤ p
for which a global solution can be obtained via the singular value decomposition (SVD).

Let X be a real m ×n matrix and r = min(m, n). In its compact form, the SVD of X is de ned as X = U DV T where • U and V are resp. m × r and n × r real unitary matrices whose columns are resp. left and right singular vectors • and D is a r × r diagonal matrix of nonnegative singular values by decreasing order

d 1 ≥ . . . ≥ d r ≥ 0 D = diag(d 1 , . . . , d r ) := d 1 0 . . . 0 d r . 1. Matrix completion for recommender systems n m                              Z             = p m                              U             × n V T p Figure 1.3: Low-rank matrix factorization.
For unique (non-degenerate) singular values, the associated left and right singular vectors are unique up to simultaneous sign inversion. Despite the rank constraint being non-convex, a global solution of (1.5) is given by the truncated SVD of X , i.e. Z = T p (X ) de ned by:

T p (X ) := U p D p V T p
where D p = diag(d 1 , . . . , d p ) contains the p largest singular values, U p and V p contain the corresponding singular vectors. The rest can be discarded, yielding a rank p matrix.

Unfortunately, for general subsets Ω where X is not fully observed, the rank-constrained problem (1.4) is of little practical use as it remains computationally NP-hard and subject to multiple local optima [START_REF] Srebro | Weighted low-rank approximations[END_REF]. Subsequent literature has focused on simplifying it while conserving low-rank properties.

Matrix factorization

Low-rank matrices can be factorized as the product Z = UV T of a tall m × p matrix U and a thin p × n matrix V T with p min(m, n) as illustrated in Figure 1.3. Matrices which admit such a factorization verify rank(Z ) ≤ p and rank(Z ) = p i U and V are of full rank. Matrix factorization is a class of latent factor model where each row of the matrix is a linear combination of p latent factors with row speci c coe cients. U is considered as the coe cient matrix whose rows represent the extent to which each factor is used. V T is the factor matrix whose rows are the factors.

In general, matrix factorization techniques consider the regularized problem with respect to U and V minimize

U ,V L P Ω (X ), P Ω (UV T ) + pen(U , V )
where pen(U , V ) is a penalty term on the complexity of the solution.

Maximum-margin matrix factorization

In particular, [START_REF] Srebro | Maximum-Margin Matrix Factorization[END_REF] proposed the following regularized problem minimize

U ,V 1 2σ 2 P Ω (X ) -P (UV T ) 2 F + λ 2 U 2 F + V 2 F (1.6)
where λ ≥ 0 is a positive regularization parameter that tunes the trade-o between the loss and the penalty term. Instead of penalizing the rank, we seek a low-norm factorization. This corresponds to constraining the overall importance of the factors instead of their number. In other words, a large number of factors is allowed but only a few are allowed to be very important. Though not strictly low-rank, we expect a solution with a lot of negligible columns of U and V . Rather than the quadratic loss, [START_REF] Srebro | Maximum-Margin Matrix Factorization[END_REF] and [START_REF] Rennie | Fast maximum margin matrix factorization for collaborative prediction[END_REF] have focused on the hinge-loss (used in maximum-margin classi ers and support vector machines) for binary observations and its generalization for discrete ordinal ratings, hence the name maximum-margin matrix factorization (MMMF). Though not jointly convex in U and V , the objective function is fairly simple with easy to compute gradients. Two simple and popular strategies can be used to optimize (1.6) and similar problems.

Stochastic gradient descent. Stochastic gradient descent (SGD) randomly iterates over the set of observed entries x ij for (i, j) ∈ Ω and optimizes the problem with respect to u i and j minimize

u i , j 1 2σ 2 x ij -u T i j 2 + λ 2 u i 2 2 + j 2 2
where • 2 is the 2 norm. In fact, it is not necessary to minimize each intermediate problem but simply to move u i and j in the direction opposite to the local gradient. This strategy is very useful when the data is very sparse or in a streaming data context where observations arrive at random times and we want to continuously update the solution while incorporating new data. Each step decreases the global objective function towards a local minimum. See e.g. [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF] for e cient implementations of SGD for matrix factorization.

Alternating least squares. Observe that when V (resp. U ) is xed, the objective function with respect to U (resp. V ) becomes quadratic so its global minimum can be readily computed.

Using a weighted version of the loss function, let consider the objective function

L(U , V ) = 1 2σ 2 W (X -UV T ) 2 F + λ 2 U 2 F + V 2 F
where W = (w ij ) is an m × n matrix of nite nonnegative weights and is the element-wise or Hadamard product. Note that problem (1.6) is a particular case taking w ij = 1 if (i, j) ∈ Ω and 0 otherwise, so that W selects the revealed entries. Canceling its partial derivative with respect to the vector u i gives

u * i = V T W 2 i V + λσ 2 I -1 V T W 2 i x i
where W i = diag(w i1 , . . . , w in ) and x i = (x i1 , . . . , x in ) T . This is the solution to a regularized weighted linear least squares problem

u * i = arg min u 1 2σ 2 W i (x i -Vu) 2 2 + λ 2 u 2 2 .
The minimizer of L(U , V ) for xed V is given by U * (V ) = (u * 1 , . . . , u * m ) T . This suggests a block coordinate descent optimization process, where we alternate between re-computing U = U * (V ) and V = V * (U ), and each step is guaranteed to lower the value of the objective function. This strategy is known as alternating least squares (ALS). It can be e ciently parallelized as each u i is updated independently of the other rows of U and symmetrically, each j is updated independently of the other rows of V [START_REF] Zhou | Large-scale parallel collaborative ltering for the Net ix prize[END_REF].

Matrix completion for recommender systems

Probabilistic matrix factorization

Building on a probabilistic interpretation, [START_REF] Mnih | Probabilistic matrix factorization[END_REF] have generalized the MMMF to more complex graphical models resulting in the probabilistic matrix factorization (PMF) framework.

First, observe that the solution of the MMMF optimization problem (1.6) can be obtained as the maximum a posteriori (MAP) estimate under the likelihood model

x ij |u i , j ∼ N u T i j , σ 2
for i = 1, . . . , m and j = 1, . . . , n, where N (µ, σ 2 ) is the normal distribution of mean µ and variance σ 2 whose probability density function (pdf) evaluated at

x is N (x; µ, σ 2 ) = 1 σ √ 2π e -1 2 ( x -µ σ )
2 , and under the prior distribution

u ik i.i.d. ∼ N 0, σ 2 U and jk i.i.d. ∼ N 0, σ 2 V (1.7) for i = 1, . . . , m, j = 1, . . . , n and k = 1, . . . , p. It is easy to check that the log-posterior is log p (U , V |P Ω (X )) = C - 1 2σ 2 P Ω (X ) -P Ω (UV T ) 2 F - 1 2σ 2 U U 2 F - 1 2σ 2 V V 2 F (1.8)
where C is a constant that does not depend on the parameters U and V .

Proof.

p (U , V |P Ω (X )) ∝ p (P Ω (X )|U , V ) p(U )p(V ) ∝        (i,j)∈Ω N x ij ; u T i j , σ 2              m i=1 p k=1 N u ik ; 0, σ 2 U              n j=1 p k=1 N jk ; 0, σ 2 V        ∝ (i,j)∈Ω e -1 2σ 2 (xij-u T i j ) 2 m i=1 p k=1 e - u 2 ik 2σ 2 U n j=1 p k=1 e - 2 jk 2σ 2 V ∝ exp        - 1 2σ 2 (i,j)∈Ω x ij -u T i j 2 - 1 2σ 2 U m i=1 p k=1 u 2 ik - 1 2σ 2 V n j=1 p k=1 2 jk       
Maximizing the log-posterior (1.8) is equivalent to minimizing the squared-error objective function with quadratic regularization terms (1.6) where

σ 2 U = σ 2 V = 1 λ .
This suggests a more general framework allowing di erent models of likelihood and prior distributions. In particular, [START_REF] Mnih | Probabilistic matrix factorization[END_REF] consider the likelihood

x ij |u i , j ∼ N (u T i j ), σ 2
where (x ) = 1 1+e -x is the logistic function to account for ordinal ratings scaled in the range [0, 1]. They also consider using priors of the form

p(U |Θ U ) p(V |Θ V ) p(Θ U ) p(Θ V )
with hyperpriors on the parameters Θ U and Θ V as illustrated on Figure 1.4 and maximizing the log-posterior log p (U , V , Θ U , Θ V |P Ω (X )) .

1.3. Low-rank matrix completion

x ij u i j Θ U Θ V σ i = 1, . . . , m j = 1, . . . , n Figure 1.4: Graphical model of the PMF.
In the special MMMF case with spherical priors (1.7) and hyperparameters σ 2 U = σ 2 V = 1 λ , this allows to have the regularization parameter λ chosen automatically. Yet, it is possible to use more sophisticated priors with diagonal or even full covariance matrices as well as adjustable means for the feature vectors.

Nuclear norm regularization

Convexity is a desired property in optimization as it guarantees that any local minimum is global. Convex optimization consists in minimizing a convex objective function over a convex set. Contrary to non-convex problems, convex problems are much easier to solve and to analyze. Thus, many authors have advocated the use of a convex relaxation of the rank constraint of problem (1.4).

When considering vectors, the 1 norm is known to be the convex hull of the counting 0 "norm" and is widely used as a sparsity-promoting regularizer, e.g. for coe cients in regression problems. Likewise for matrices, the rank of Z can be de ned as the 0 "norm" of the vector of singular values d = (d 1 , . . . , d r )

rank(Z ) = d 0 = r i=1 1 d i >0
and the nuclear norm is de ned as the sum of the singular values or 1 norm of d

Z * = d 1 = r i=1 d i .
It is also called the trace norm in the literature as Z * = tr(D) where Z = U DV T is the SVD of Z . Like the 1 norm for the 0 "norm", the nuclear norm is the tightest convex envelope of the rank. Therefore, it has been widely adopted as a convex surrogate to the rank [START_REF] Fazel | Matrix rank minimization with applications[END_REF][START_REF] Candès | Exact matrix completion via convex optimization[END_REF][START_REF] Candès | Matrix completion with noise[END_REF][START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF]

to turn (1.4) into a convex minimization problem minimize Z 1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F + λ Z * .
(1.9)

Note that the rank is no longer constrained but, for high λ, the solution will have many singular values exactly equal to zero, hence reducing its rank.

Matrix completion for recommender systems

Finally, observe that the nuclear norm and the MMMF quadratic penalty are tightly connected by the following relation [START_REF] Srebro | Maximum-Margin Matrix Factorization[END_REF])

Z * = min Z =UV T 1 2 U 2 F + V 2 F .
Complete case. Consider rst that we observe the complete matrix X = (x ij ) of size m × n.

The solution to the convex optimization problem minimize

Z 1 2σ 2 X -Z 2 F + λ Z * (1.10)
is given by a soft-thresholded SVD of X , i.e.

Z = S λσ 2 (X )
where S λ (X ) [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF][START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF].

:= U D λ V T with D λ = diag ((d 1 -λ) + , . . . , (d r -λ) + ), t + := max(t, 0) and X = U DV T is the SVD of X with D = diag (d 1 , . . . , d r ) . Proof. For clarity, note that problem (1.10) is equivalent to minimize Z 1 2 X -Z 2 F + λ Z * with λ = σ 2 λ whose solution is Z = S λ (X ); see
Incomplete case. Using the previous solution for the complete case as a basic ingredient, [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] proposed a completion algorithm called Soft-Impute for solving the nuclear norm regularized minimization (1.9). The algorithm relies on alternatively imputing missing values of X and re-estimating a soft-thresholded SVD of the completed matrix. At every iteration, Soft-Impute decreases the value of the objective function towards its minimum.

The procedure is summarized in Algorithm 1.

Algorithm 1: Soft-Impute algorithm. Initialize Z and repeat until convergence:

• Impute missing values:

X * = P Ω (X ) + P ⊥ Ω (Z ) • Compute Z = S λσ 2 (X * )
The computationally demanding part of Algorithm 1 is S λσ 2 (X * ) which requires calculating a low-rank truncated SVD. [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] suggest several strategies to accelerate the algorithm. For large matrices, one can resort to the PROPACK software [START_REF] Larsen | Lanczos bidiagonalization with partial reorthogonalization[END_REF][START_REF] Larsen | PROPACK-software for large and sparse SVD calculations[END_REF]. This sophisticated linear algebra algorithm can e ciently compute the truncated SVD of a "sparse + low-rank" structured matrix thus handling large matrices. Fortunately, it is easy to see that X * possesses such structure

X * = P Ω (X ) + P ⊥ Ω (Z ) = P Ω (X ) -P Ω (Z ) sparse + Z low-rank .
In practice, at each step, we only need to compute the leading k singular values d i and associated singular vectors such that d i > λσ 2 . Though we do not know their number k, PROPACK computes them sequentially and can therefore be stopped as soon as one of the singular values falls under the threshold. As shown by [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF], every truncated SVD step of the algorithm computes k singular vectors, with complexity of the order O (m + n)k 2 +O (|Ω|k ).

Finally, [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] propose a warm-start strategy to compute an entire regularization path of solutions on a grid of decreasing values λ 1 > λ 2 > . . . > λ K . If successive values are close, their solutions are likely to be close. The Soft-Impute algorithm for λ k is initialized with the slightly higher rank solution obtained with for λ k-1 , thus saving precious computing iterations.

More generally, nuclear norm regularization is a form of spectral regularization [START_REF] Abernethy | A new approach to collaborative ltering: Operator estimation with spectral regularization[END_REF] which considers surrogates of the rank penalty by taking functions over the set of singular values (a.k.a. spectrum) of matrix Z pen

(Z ) = r i=1 f i (d i )
where for i = 1, . . . , r , f i : R + → R + ∪ {+∞} is a non-decreasing penalty function satisfying f i (0) = 0. In particular, the nuclear norm is obtained by taking f i (d i ) = λd i . In Chapter 2, we develop a generalization of the Soft-Impute algorithm to non-convex spectral penalties based on a probabilistic interpretation of problem (1.9).

Chapter 2 Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms

We propose a novel class of algorithms for low-rank matrix completion. Our approach builds on novel penalty functions on the singular values of the low-rank matrix. By exploiting a mixture model representation of this penalty, we show that a suitably chosen set of latent variables enables to derive an expectation-maximization algorithm to obtain a maximum a posteriori estimate of the completed low-rank matrix. The resulting algorithm is an iterative soft-thresholded algorithm which iteratively adapts the shrinkage coe cients associated to the singular values. The algorithm is simple to implement and can scale to large matrices. The extension to binary matrices is also described. We provide numerical comparisons between our approach and recent alternatives showing the interest of the proposed approach for low-rank matrix completion. This chapter is an extended version of our publication at NIPS 2013 conference [START_REF] Todeschini | Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms[END_REF].

Introduction

We want to recover an unknown m × n matrix Z = (z ij ) and we are going to assume that Z can be approximated by a matrix of low-rank Z AB T where A and B are respectively of size m × k and n × k, with k min(m, n). We typically observe a noisy version x ij of some entries (i, j) ∈ Ω where Ω ⊂ {1, . . . , m} × {1, . . . , n}. For (i, j) ∈ Ω

x ij = z ij + ε ij , ε ij i.i.d. ∼ N (0, σ 2 ) (2.1)
where σ 2 > 0. Many authors have advocated the use of a nuclear norm regularization [START_REF] Fazel | Matrix rank minimization with applications[END_REF][START_REF] Candès | Enhancing sparsity by reweighted l1 minimization[END_REF][START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF], yielding the following convex optimization problem minimize

Z 1 2σ 2 (i,j)∈Ω x ij -z ij 2 + λ Z * (2.2)
where λ ≥ 0 and Z * is the nuclear norm of Z , or the sum of the singular values of Z . [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] proposed an iterative algorithm, called Soft-Impute, for solving the nuclear norm regularized minimization (2.2); see Section 1.3.4 of Chapter 1 for further details.

In this chapter, we show that the solution to the objective function (2.2) can be interpreted as a MAP estimate when assuming that the singular values of Z are independent and identically distributed (i.i.d.) from an exponential distribution with rate λ. Using this Bayesian interpretation, we propose alternative concave penalties to the nuclear norm, obtained by considering that the singular values are i.i.d. from a mixture of exponential distributions. We show that this class of penalties bridges the gap between the nuclear norm and the rank penalty, and that a simple expectation-maximization algorithm (EM, see Appendix A.1) can be derived to obtain MAP estimates. The resulting algorithm iteratively adapts the shrinkage coe cients associated to the singular values. It can be seen as the equivalent for matrices of reweighted 1 algorithms [START_REF] Candès | Enhancing sparsity by reweighted l1 minimization[END_REF] for multivariate linear regression. Interestingly, we show that the Soft-Impute algorithm of [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] is obtained as a particular case. We also discuss the extension of our algorithms to binary matrices, building on the same seed of ideas, in Section 2.4. Finally, we provide some empirical evidence of the interest of the proposed approach on simulated and real data.

Complete matrix X

Consider rst that we observe the complete matrix

X = (x ij ) of size m × n. The solution Z to the optimization problem minimize Z 1 2σ 2 X -Z 2 F + λ Z * (2.3)
can be interpreted as the MAP estimate under the likelihood (2.1) and prior

p(Z ) ∝ exp (-λ Z * ) . (2.4)
Assuming Z = U DV T , with D = diag(d 1 , d 2 , . . . , d r ) and r = min(m, n), this can be further decomposed as

p(Z ) = p(U )p(V )p(D)
where we assume a uniform Haar prior distribution on the unitary matrices U and V , and exponential priors on the singular values d i , hence

p(d 1 , . . . , d r ) = r i=1 Exp (d i ; λ)
where Exp (x; λ) = λ exp(-λx ) is the pdf of the exponential distribution of parameter λ evaluated at x. We can easily check (2.4):

Proof.

p(Z ) = p(U )p(V )p(D) ∝ p(D) = r i=1 p(d i ) = r i=1 λ exp(-λd i ) ∝ exp(-λ r i=1 d i ) = exp(-λ Z * ) d 1 d 2 • • • d r -1 d r λ Figure 2.1: Graphical model of the prior p(d 1 , . . . , d r ) = r i=1 p(d i ). γ 1 γ 2 • • • γ r -1 γ r d 1 d 2 • • • d r -1 d r a, b Figure 2.2: Graphical model of the hierarchical prior p(d 1 , . . . , d r ) = r i=1 p(d i |γ i )p(γ i ).
The graphical model of this prior is represented in Figure 2.1. The exponential distribution has a mode at 0, hence favoring sparse solutions.

We propose here alternative penalty/prior distributions, that bridge the gap between the rank and the nuclear norm penalties. Our penalties are based on hierarchical Bayes constructions and the related optimization problems to obtain MAP estimates can be solved by using an EM algorithm. The proposed models can be seen as the equivalent for matrices of the iteratively reweighted lasso algorithms for linear regression [START_REF] Candès | Enhancing sparsity by reweighted l1 minimization[END_REF][START_REF] Cevher | Learning with compressible priors[END_REF][START_REF] Garrigues | Sparse coding models of natural images: Algorithms for e cient inference and learning of higher-order structure[END_REF][START_REF] Lee | A hierarchical Bayesian framework for constructing sparsity-inducing priors[END_REF][START_REF] Armagan | Generalized double Pareto shrinkage[END_REF].

Hierarchical adaptive spectral penalty

We consider the following hierarchical prior for the low-rank matrix Z . We still assume that Z = U DV T , where the unitary matrices U and V are assigned uniform priors and D = diag(d 1 , . . . , d r ). We now assume that each singular value d i has its own regularization parameter γ i .

p(d 1 , . . . , d r |γ 1 , . . . γ r ) = r i=1 p(d i |γ i ) = r i=1 Exp(d i ; γ i ).
We further assume that the regularization parameters are themselves i.i.d. from a gamma distribution

p(γ 1 , . . . , γ r ) = r i=1 p(γ i ) = r i=1 Gamma(γ i ; a, b)
where Gamma(x; a, b) is the pdf of the gamma distribution of parameters a > 0 and b > 0 evaluated at x. The graphical model of this hierarchical prior is represented in Figure 2.2.

The marginal distribution over d i is thus a continuous mixture of exponential distributions (details in Appendix A.2)

p(d i ) = ∞ 0 Exp(d i ; γ i ) Gamma(γ i ; a, b)dγ i = ab a (d i + b) a+1 . (2.5)
It is a Pareto distribution which has heavier tails than the exponential distribution.

pen(Z ) = -log p(Z ) = - r i=1 log p(d i ) = C 1 + (a + 1) r i=1 log(b + d i ) (2.6)
be the penalty induced by the prior p(Z ) where C 1 is a constant term not depending on Z . We call the penalty (2.6) the hierarchical adaptive spectral penalty (HASP). On Figure 2.4 (top) are represented the balls of constant penalties for a symmetric 2 × 2 matrix, for the HASP, nuclear norm and rank penalties. When the matrix is assumed to be diagonal, one recovers respectively the lasso, hierarchical adaptive lasso (HAL, [START_REF] Candès | Enhancing sparsity by reweighted l1 minimization[END_REF][START_REF] Lee | A hierarchical Bayesian framework for constructing sparsity-inducing priors[END_REF] and 0 penalties, as shown on Figure 2.4 (bottom). The penalty (2.6) admits as special cases the nuclear norm penalty λ Z * when a = λb and b → ∞. Another closely related penalty is the log-det heuristic [START_REF] Fazel | Matrix rank minimization with applications[END_REF][START_REF] Fazel | Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices[END_REF] penalty, de ned for a square matrix Z by log det(Z + δI ) where δ is some small regularization constant. Both penalties agree on square matrices when a = b = 0 and δ = 0.

EM algorithm for MAP estimation

Using the exponential mixture representation (2.5), we now show how to derive an EM algorithm to obtain a MAP estimate

Z = arg max Z [log p(X |Z ) + log p(Z )]
i.e. to minimize

L(Z ) = 1 2σ 2 X -Z 2 F + (a + 1) r i=1 log(b + d i ). (2.7)
We use the parameters γ = (γ 1 , . . . , γ r ) as latent variables in the EM algorithm. The E step is obtained by (details in Appendix A.2) where C 2 is a constant term not depending on Z . Hence at each iteration of the EM algorithm, the M step consists in solving the optimization problem minimize

Q (Z , Z * ) = E [log p(X , Z , γ )|Z * , X ] = C 2 - 1 2σ 2 X -Z 2 F - r i=1 E[γ i |d * i ]d i (2.8) (a) Nuclear norm (b) HASP (β = 1) (c) HASP (β = 0.1) (d) Rank penalty (e) 1 norm (f) HAL (β = 1) (g) HAL (β = 0.1) (h) 0 norm
Z 1 2σ 2 X -Z 2 F + r i=1 ω i d i (2.9)
where (details in Appendix A.2)

ω i = E[γ i |d * i ] = ∂ ∂d * i -log p(d * i ) = a + 1 b + d * i .
(2.10) Problem (2.9) is an adaptive nuclear norm regularized optimization problem, with weights ω i . Without loss of generality, assume that

d * 1 ≥ d * 2 ≥ . . . ≥ d * r . It implies that 0 ≤ ω 1 ≤ ω 2 ≤ . . . ≤ ω r .
(2.11)

The above weights will therefore penalize less heavily higher singular values, hence reducing bias. As shown by Gaï as and Lecué (2011) and [START_REF] Chen | Reduced rank regression via adaptive nuclear norm penalization[END_REF], a global optimal solution to Eq. (2.9) under the order constraint (2.11) is given by a weighted soft-thresholded SVD

Z = S σ 2 ω (X ) (2.12) where S ω (X ) = U D ω V T with D ω = diag ( d 1 -ω 1 ) + , . . . , ( d r -ω r ) + , X = U D V T is the SVD of X with D = diag d 1 , . . . , d r and d 1 ≥ d 2 . . . ≥ d r .
Algorithm 2 summarizes the hierarchical adaptive soft-thresholded (HAST) procedure to converge to a local minimum of the objective (2.7). This algorithm admits the soft-thresholded SVD operator as a special case when a = bλ and b = β → ∞. Figure 2.5 shows the thresholding rule applied to the singular values of X for the HAST algorithm (a = b = β, with β = 2 and β = 0.1) and the soft-thresholded SVD for λ = 1. The bias term, which is equal to λ for the nuclear norm, goes to zero as d i goes to in nity.

Algorithm 2: Hierarchical Adaptive Soft-Thresholded (HAST) algorithm for low-rank estimation of complete matrices. Initialize Z (0) . At iteration t ≥ 1

• For i = 1, . . . , r , compute the weights

ω (t ) i = a+1 b+d (t -1) i • Set Z (t ) = S σ 2 ω (t ) (X ) • If L(Z (t -1) )-L(Z (t ) ) L(Z (t -1) ) < ε then return Z = Z (t )
Se ing of the hyperparameters and initialization of the EM algorithm. In the experiments, we have set b = β and a = λβ where λ and β are tuning parameters that can be chosen by cross-validation. As λ is the mean value of the regularization parameter γ i , we initialize the algorithm with the soft-thresholded SVD with parameter σ 2 λ. It is possible to estimate the hyperparameter σ within the EM algorithm. If we assume that

σ 2 ∼ InvGamma(a σ , b σ )
where InvGamma(a, b) is the inverse gamma distribution with shape parameter a > 0 and rate parameter b > 0. Then at each iteration of the algorithm we can maximize w.r.t. σ 2 given Z (t ) in the E step to obtain

σ 2(t ) = a σ + X -Z (t ) 2 F b σ + mn .
In our experiments, we have found the results not very sensitive to the setting of σ , and set it to 1.

i = E[γ i |d * i ] Gamma(γ i ; a, b) = b a Γ(a) γ a-1 i e -bγ i ab a (d i +b) a+1 a+1 b+d * i iGauss (γ i ; δ, µ) = δ √ 2π e δ µ γ -3/2 i e -1 2 (δ 2 γ -1 i +µ 2 γ i ) δ √ µ 2 +2d i e δ (µ- √ µ 2 +2d i ) δ √ µ 2 +2d * i 1 + 1 δ √ µ 2 +2d * i Je reys: ∝ 1/γ i ∝ 1/d i 1/d * i GiG (γ i ; ν, δ, µ) = (µ/δ ) ν 2K ν (δ µ) γ ν-1 i e -1 2 (δ 2 γ -1 i +µ 2 γ i ) δ µ ν K ν (δ µ) K ν +1 δ √ µ 2 +2d i √ µ 2 +2d i ν +1 δ √ µ 2 +2d * i K ν +2 δ √ µ 2 +2d * i K ν +1 δ √ µ 2 +2d * i 2.

Generalization to other mixing distributions

Although we focused on a gamma mixing distribution for its simplicity, it is possible to use other mixing distributions p(γ i ), such as inverse Gaussian or improper Je reys distributions. More generally, one can consider the three parameters generalized inverse Gaussian distribution [START_REF] Barndor -Nielsen | Non-Gaussian Ornstein-Uhlenbeck-based models and some of their uses in nancial economics[END_REF][START_REF] Zhang | EP-GIG priors and applications in Bayesian sparse learning[END_REF][START_REF] Caron | Sparse Bayesian nonparametric regression[END_REF] thus o ering an additional degree of freedom. Its pdf evaluated at

x > 0 is GiG (x; ν, δ, µ) = (µ/δ ) ν 2K ν (δ µ) x ν-1 e -1 2 (δ 2 x -1 +µ 2 x )
It includes as special cases:

• the gamma distribution: ν > 0, δ = 0 • the inverse gamma distribution: ν < 0, µ = 0 • the inverse Gaussian distribution: ν = -1 2

• the Je reys distribution as a limiting case: ν → 0, δ → 0, µ → 0 and its k-th moment is given by

E x k = δ µ K ν+k (δ µ) K ν (δ µ) .
Table 2.1 provides the marginal density p(d i ) and weights ω i depending on the choice of p(γ i ). Details of the general GiG case are given in Appendix A.2. Figure 2.6 shows plots of the marginal density p(d i ) for di erent choices of p(γ i ).

Matrix completion

We now show how the EM algorithm derived in the previous section can be adapted to the case where only a subset of the entries is observed. It relies on imputing missing values, similarly to the EM algorithm for SVD with missing data; see e.g. [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF][START_REF] Srebro | Weighted low-rank approximations[END_REF].

Consider that only a subset Ω ⊂ {1, . . . , m} × {1, . . . , n} of the entries of the matrix X is observed. Assuming the same prior (2.5), the MAP estimate is obtained by minimizing

L(Z ) = 1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F + (a + 1) r i=1 log(b + d i ).
(2.13)

2.3. Matrix completion 0 1 2 3 4 5 d i 0.5 1 1.5 2 2.5 p(d i ) Gamma β = ∞ Gamma β = 0.2 iGauss δ = 0.8 iGauss δ = 0.2 GiG β = 1, δ = 2.5 GiG β = 5, δ = 1 GiG β = 0.01, δ = 0.01 Figure 2.6: Marginal distribution p(d i ) for di erent mixing distributions p(γ i ) with E [γ i ] = 1: Gamma(β, β ), iGauss(δ, δ ) and GiG(ν, δ, β ) where ν is chosen so that E [γ i ] = δ µ K ν +1 (δ β )
K ν (δ β ) = 1; and for di erent values of the parameters β and δ .

We will now derive the EM algorithm, by using latent variables γ and P ⊥ Ω (X ). The E step is given by (details in Appendix A.2)

Q (Z , Z * ) = E log p(P Ω (X ), P ⊥ Ω (X ), Z , γ )|Z * , P Ω (X ) = C 3 - 1 2σ 2 P Ω (X ) + P ⊥ Ω (Z * ) -Z 2 F - r i=1 E[γ i |d * i ]d i (2.14)
where C 3 is a constant term not depending on Z . Hence at each iteration of the algorithm, one needs to minimize

1 2σ 2 X * -Z 2 F + r i=1 ω i d i (2.15)
where ω i = E[γ i |d * i ] and X * = P Ω (X ) + P ⊥ Ω (Z * ) is the observed matrix, completed with entries in Z * . We now have a complete matrix problem. As mentioned in the previous section, the minimum of (2.15) is obtained with a weighted soft-thresholded SVD. Algorithm 3 provides the resulting iterative procedure for matrix completion with the hierarchical adaptive spectral penalty.

Algorithm 3: Hierarchical Adaptive Soft-Impute (HASI) algorithm for matrix completion.

Initialize Z (0) . At iteration t ≥ 1

• For i = 1, . . . , r , compute the weights ω (t ) i = a+1 b+d (t -1) i • Set Z (t ) = S σ 2 ω (t ) P Ω (X ) + P ⊥ Ω (Z (t-1) ) • If L(Z (t -1) )-L(Z (t ) ) L(Z (t -1) ) < ε then return Z = Z (t )
Related algorithms. Algorithm 3 admits the Soft-Impute algorithm of [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] as a special case when a = λb and b = β → ∞. In this case, one obtains at each iteration ω (t ) i = λ for all i. On the contrary, when β < ∞, our algorithm adaptively updates the weights so that to penalize less heavily higher singular values. Some authors have proposed related one-step adaptive spectral penalty algorithms [START_REF] Bach | Consistency of trace norm minimization[END_REF][START_REF] Gaï As | Weighted algorithms for compressed sensing and matrix completion[END_REF][START_REF] Chen | Reduced rank regression via adaptive nuclear norm penalization[END_REF]. However, in these procedures, the weights have to be chosen by some procedure whereas in our case they are iteratively adapted.

Initialization. The objective function (2.13) is in general not convex and di erent initializations may lead to di erent modes. As in the complete case, we suggest to set a = λb and b = β and to initialize the algorithm with the Soft-Impute algorithm with regularization parameter σ 2 λ.

Scaling. Similarly to the Soft-Impute algorithm, the computationally demanding part of Algorithm 3 is S σ 2 ω (t ) P Ω (X ) + P ⊥ Ω (Z (t-1) ) which requires calculating a low-rank truncated SVD. For large matrices, one can resort to the PROPACK algorithm [START_REF] Larsen | Lanczos bidiagonalization with partial reorthogonalization[END_REF][START_REF] Larsen | PROPACK-software for large and sparse SVD calculations[END_REF] as described by [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF]. This sophisticated linear algebra algorithm can e ciently compute the truncated SVD of the "sparse + low-rank" matrix

P Ω (X ) + P ⊥ Ω (Z (t-1) ) = P Ω (X ) -P Ω (Z (t-1) ) sparse + Z (t-1)
low-rank and can thus handle large matrices.

Binary matrix completion

We have considered real valued matrices X . We now show how it is possible to apply the same methodology to binary incomplete matrices Y with entries ij ∈ {-1, 1}. Similarly to [START_REF] Figueiredo | Adaptive sparseness for supervised learning[END_REF], we assume the following probit model

ij |z ij ∼ Ber Φ z ij σ where Ber(p) is the Bernoulli distribution with parameter p ∈ [0, 1] and Φ(x ) = x -∞ φ(u)du is the cumulative distribution function (cdf) of the standard Gaussian distribution with φ(u) = 1 √ 2π e -u 2 2
. The model can be alternatively written using Gaussian latent variables x ij

x ij |z ij ∼ N (z ij , σ 2 ) ij =      +1 if x ij > 0 -1 otherwise.
The objective function

L(Z ) = (i,j)∈Ω 1 + ij 2 log Φ z ij σ + 1 -ij 2 log Φ - z ij σ + pen(Z )
can be locally minimized using an EM algorithm using the variables x ij as additional latent variables. We have (details in Appendix A.2)

E[x ij |P Ω (Y ), Z ] =        z ij + ij σφ z i j σ Φ i j z i j σ if (i, j) ∈ Ω z ij otherwise.
(2.16)

We will now derive the EM algorithm, by using latent variables γ i and X . The E step is given by (details in Appendix A.2)

Q (Z , Z * ) = E [log p(P Ω (Y ), X , Z , γ )|Z * , P Ω (Y )] = C 4 - 1 2σ 2 X * -Z 2 F - r i=1 E[γ i |d * i ]d i (2.17)
where C 4 is a constant term not depending on Z and the matrix X * is de ned as

x * ij =              z * ij + ij σφ z * i j σ Φ i j z * i j σ if (i, j) ∈ Ω z * ij otherwise.
Again, the maximum of the function (2.17) is obtained analytically using a weighted softthresholded SVD on the matrix X * . The HASI-bin procedure is summarized in Algorithm 4.

Algorithm 4: Hierarchical Adaptive Soft-Impute algorithm for binary matrix completion (HASI-bin). Initialize Z (0) . At iteration t ≥ 1

• For i = 1, . . . , r , compute the weights ω (t ) i = a+1 b+d (t -1) i • For (i, j) ∈ Ω, compute x (t ) ij = z (t-1) ij + ij σφ z (t -1) i j σ Φ i j z (t -1) i j σ • Set Z (t ) = S σ 2 ω (t ) P Ω (X (t ) ) + P ⊥ Ω (Z (t-1) ) • If L(Z (t -1) )-L(Z (t ) ) L(Z (t -1) ) < ε then return Z = Z (t )

Experiments

Simulated data

We rst evaluate the performance of the proposed approach on simulated data. Our simulation setting is similar to that of [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF]. We generate Gaussian matrices A and B respectively of size m × q and n × q, q ≤ r so that the matrix Z = AB T is of low rank q. A Gaussian noise of variance σ 2 is then added to the entries of Z to obtain the matrix X . The signal to noise ratio is de ned as SNR = var(Z ) σ 2 . We set m = n = 100 and σ = 1. We run all the algorithms with a precision ϵ = 10 -9 and a maximum number of t max = 200 iterations (initialization included for HASI). In the complete case, we compute the relative squared error between the estimated matrix Z and the true matrix

Z err = Z -Z 2 F Z 2 F
while in the incomplete case, we compute the relative squared error between the test entries

err Ω ⊥ = P ⊥ Ω ( Z ) -P ⊥ Ω (Z ) 2 F P ⊥ Ω (Z ) 2 F .
For the HASP penalty, we set a = λβ and b = β. We compute the solutions over a grid of 50 values of the regularization parameter λ linearly spaced from λ 0 to 0, where λ 0 = P Ω (X ) 2 is the spectral norm or largest singular value of the input matrix X , padded with zeros. This is done for three di erent values β = 1, 10, 100. We use the same grid to obtain the regularization path for the other algorithms.

Complete case. We rst consider that the observed matrix is complete, with SNR = 1 and q = 10. The HAST algorithm 2 is compared to the soft-thresholded (ST) and hardthresholded (HT) SVD. Results are reported in Figure 2.7(a). The HASP penalty provides a bridge/trade-o between the nuclear norm and the rank penalty. For example, value of β = 10 show a minimum at the true rank q = 10 as HT, but with a lower error when the rank is overestimated.

Incomplete case. Then we consider the matrix completion problem, and remove uniformly a given percentage of the entries in X . We compare the HASI algorithm to the Soft-Impute, Soft-Impute+ and Hard-Impute algorithms of [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] and to the MMMF algorithm of [START_REF] Rennie | Fast maximum margin matrix factorization for collaborative prediction[END_REF]; see Chapter 1 for further details on these algorithms. Results, averaged over 50 random replications of the set of observed entries Ω, are reported in Figures 2.7(b-c) for a true rank q = 5, (b) 50% of missing entries and SNR = 1 and (c) 80% of missing entries and SNR = 10. Similar behavior is observed, with the HASI algorithm attaining a minimum at the true rank q = 5.

We then conduct the same experiments, but remove 20% of the observed entries as a validation set to estimate the regularization parameters (λ, β ) for HASI, and λ for the other methods. We estimate Z on the whole observed matrix, and use the unobserved entries as a test set. Results on the test error and estimated ranks over 50 replications are reported in Figure 2.8. For 50% missing entries, HASI is shown to outperform the other methods. For 80% missing entries, HASI and Hard-Impute provide the best performances. In both cases, it is able to recover very accurately the true rank of the matrix.

Collaborative filtering examples

We now compare the di erent methods on several benchmark datasets.

Jester datasets. We rst consider the Jester datasets [START_REF] Goldberg | Eigentaste: A constant time collaborative ltering algorithm[END_REF]. The three datasets1 contain one hundred jokes, with user ratings between -10 and 10. We randomly select two ratings per user as a test set, and two other ratings per user as a validation set to select the parameters λ and β. The results are computed over four values β = 1000, 100, 10, 1. We compare the results of the di erent methods with the normalized mean absolute error (NMAE) which is a popular metric on these datasets 2.9 shows the NMAE in function of the rank. Low values of β exhibit a bimodal behavior with two modes at low rank and full rank. High value β = 1000 is unimodal and outperforms Soft-Impute at any particular rank.

NMAE = 1 card (Ω t est ) (i,j)∈Ω t est |x ij -z ij | max(X ) -min(X )
MovieLens datasets. Second, we conducted the same comparison on two MovieLens datasets3 , which contain ratings of movies by users. We randomly select 20% of the entries as a test set, and the remaining entries are split between a training set (80%) and a validation set (20%). For all the methods, we stop the regularization path as soon as the estimated rank exceeds r max = 100. This is a practical consideration: given that the computations for high ranks demand more time and memory, we are interested in restricting ourselves to low-rank solutions. Table 2.3 presents the results, averaged over 5 replications. For the MovieLens 100k dataset, HASI provides better NMAE than the other methods with a low-rank solution. For the larger MovieLens 1M dataset, the precision, maximum number of iterations and maximum rank are decreased to ϵ = 10 -6 , t max = 100 and r max = 30. On this dataset, MMMF provides the best NMAE at maximum rank. HASI provides the second best performances with a slightly lower rank.

Conclusion

The proposed class of methods has shown to provide good results compared to several alternative low-rank matrix completion methods. It provides a bridge between nuclear norm and rank regularization algorithms. Although the related optimization problem is not convex, experiments show that initializing the algorithm with the Soft-Impute algorithm of [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF] provides very satisfactory results.

While we focus on point estimation in this chapter, it would be of interest to investigate a fully Bayesian approach and derive a Gibbs sampler or variational algorithm to approximate [START_REF] Seeger | Fast variational Bayesian inference for non-conjugate matrix factorization models[END_REF][START_REF] Nakajima | Global analytic solution of fully-observed variational Bayesian matrix factorization[END_REF].

Part II Bayesian nonparametric models for networks

Chapter 3

Background on Bayesian nonparametrics

We introduce the necessary background on Bayesian nonparametrics that will be useful in the next chapters. Instead of giving a complete review on the subject we will focus on particular objects of interest, namely completely random measures (CRMs) and one of their multivariate counterpart, the compound CRMs.

Introduction

First, let emphasize that the "nonparametric" term here does not mean "no parameters" but rather "not parametric", i.e. that we do not assume a parametric model with a xed nite number of parameters. The parameter of interest in a Bayesian nonparametric (BNP) model is in nite-dimensional. This framework allows the complexity of the model to adapt to the growing number of data, and to be able to discover more structure or patterns as we observe more data. It thus provides a framework which is both adaptive and robust [START_REF] Müller | Nonparametric Bayesian data analysis[END_REF][START_REF] Orbanz | Bayesian nonparametric models[END_REF].

Another attractive feature of Bayesian nonparametric models, which will be central to the model for graphs we develop in the next chapter, is that they allow to capture powerlaw behavior in the data. They have been therefore successfully used in natural language processing [START_REF] Teh | A hierarchical Bayesian language model based on Pitman-Yor processes[END_REF], topic models [START_REF] Teh | Indian bu et processes with power-law behavior[END_REF][START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF], natural image processing [START_REF] Sudderth | Shared segmentation of natural scenes using dependent Pitman-Yor processes[END_REF] or network analysis [START_REF] Caron | Bayesian nonparametric models for bipartite graphs[END_REF][START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] where those power-law patterns naturally arise.

A few books have been already published on Bayesian nonparametrics [START_REF] Ghosh | Bayesian Nonparametrics[END_REF][START_REF] Hjort | Bayesian nonparametrics[END_REF]. Popular models include the Dirichlet process and Chinese restaurant process [START_REF] Ferguson | A Bayesian analysis of some nonparametric problems[END_REF][START_REF] Blackwell | Ferguson distributions via Pólya urn schemes[END_REF], for density estimation and clustering, the beta process and the Indian bu et process [START_REF] Hjort | Nonparametric Bayes estimators based on beta processes in models for life history data[END_REF][START_REF] Gri Ths | In nite latent feature models and the Indian bu et process[END_REF][START_REF] Thibaux | Hierarchical beta processes and the Indian bu et process[END_REF], for survival analysis or latent feature modeling, the Gaussian process (O'Hagan and [START_REF] O'hagan | Curve tting and optimal design for prediction[END_REF] for regression or classi cation, the Pòlya tree [START_REF] Lavine | Some aspects of Polya tree distributions for statistical modelling[END_REF][START_REF] Lavine | More aspects of Polya tree distributions for statistical modelling[END_REF] for density estimation.

From a mathematical perspective, BNP methods require the elaboration of prior over an in nite-dimensional space, and we are in general working with stochastic processes instead of random vectors. More speci cally, the tools we will use here are completely random measures and their multivariate counterparts. These objects can be constructed from Poisson processes, for which we give a brief review in the next section.

Poisson point processes and Poisson random measures

The Poisson process is a standard tool in probability to model the positions of points randomly distributed in space; see [START_REF] Kingman | Poisson processes[END_REF]Daley and Vere-Jones, 2008a) for general reviews.

Commonly used in one dimension for representing arrival times, they generalize to higher dimensions, see Figure 3.1 for some examples.

Definition

The characteristic feature of Poisson processes is a property of statistical independence. Let A 1 , A 2 , . . . be some non overlapping subsets of the space. Denote N (A) the number of points falling in a set A. Then the numbers N (A j ) are positive integer-valued statistically independent random variables. More formally, let S ⊆ R d and ν be a measure on S. A Poisson process on the measurable space S with mean measure ν1 is a random countable subset Π of S such that for any disjoint measurable subsets A 1 , A 2 , . . . , A n of S, the random variables N (A 1 ), N (A 2 ), . . . , N (A n ) are independent (complete randomness property) and Poisson distributed (see Appendix B.1) with

N (A i ) ∼ Poisson (ν (A i )) . Speci cally, Π = {x i } i=1,...,N (S ) with x i ∈ S is called Poisson point process while N is a discrete measure, called Poisson random measure, such that N = N (S ) i=1 δ x i and N (A) = N (S ) i=1 δ x i (A)
where δ x is the delta Dirac measure at x; see Figure 3.2 for an illustration. We will use both representations in the rest of the thesis. By de nition of the Poisson distribution, we have

E [N (A)] = ν (A). If ν (A) is nite, Π ∩ A is with probability (w.p.) 1 a nite set, empty if ν (A) = 0. If ν (A) = ∞, Π ∩ A is countably in nite w.p. 1.
In most interesting cases, the mean measure is given in terms of a rate or intensity parameter. This is a positive measurable function ν (.) on S such that ν (dx ) = ν (x )dx and

ν (A) = A ν (x )dx .

Properties

Theorem 1 (Superposition). Let N 1 , N 2 , . . . be a countable collection of independent Poisson random measures on S where, for each i, N i is a Poisson random measure with mean measure ν i . Then their superposition ∞ i=1 N i is a Poisson process with mean measure ∞ i=1 ν i .

Proposition 2 (Thinning). Let Π = {x i } be a Poisson process on S with mean measure ν . Let Π be a new process formed by independently retaining each point x i w.p. p(x i ) or removing it w.p. 1 -p(x i ) where p(.) is a measurable function on S with 0 ≤ p(x ) ≤ 1 for all x. Then Π is a Poisson process with mean measure p(x )ν (dx ).

Theorem 3 (Campbell's Theorem). Let N = i δ x i be a Poisson random measure on S with mean measure ν and let f : S → R be a measurable function, such that

S min (| f (x )|, 1) ν (dx ) < ∞ (3.1)
then the characteristic functional is

E e θ i f (x i ) = e -S (1-e θ f (x ) )ν (dx )
for any complex θ for which the integral on the right converges. Moreover if (3.1) holds, the sum i f (x i ) is absolutely convergent w.p. 1 and we have

E       i f (x i )       = S f (x )ν (dx ) if the integral converges. Remark 4. Condition (3.1) is equivalent to S 1 -e -| f (x )| ν (dx ) < ∞. Laplace functional. A useful characterization of point processes Π = {x i } is via the Laplace functional L[f ] := E e -i f (x i )
where f is a nonnegative bounded measurable function. By Campbell's Theorem we have

L[f ] = e -S (1-e -f (x ) )ν (dx )
For one-dimensional processes, let f (x ) = tx with t > 0 and de ne the so-called Laplace exponent as

ψ (t ) := -log E e -t i x i = S
1 -e -tx ν (dx ).

Simulation

For obvious practical reasons, we will restrict ourselves to the simulation of a nite number of points. Simulating a Poisson process on A when ν (A) is nite can be done using the following strategy:

1. Generate a Poisson number of points N (A) ∼ Poisson (ν (A)).

For

i = 1, . . . , N (A), generate X i ∼ ν (•∩A) ν (A) independently.
Though this strategy always holds, it requires in practice to be able to sample from the probability measure ν (•∩A) ν (A) which might not be always be feasible.

Thinning. Exploiting the thinning property (Proposition 2), we can obtain a Poisson process with mean measure ν (dx ) = ν (x )dx by simulating from a Poisson process whose intensity upper bounds the intensity of interest ν

(x ) ≥ ν (x ) ∀x ∈ A
and such that A (x )dx < ∞. The Shedler-Lewis [START_REF] Lewis | Simulation of nonhomogeneous Poisson processes by thinning[END_REF] thinning strategy is summarized in Algorithm 5. See Figure 3.3 for an illustration. The tighter the envelope intensity , the lesser the rejection rate.

Algorithm 5: Shedler-Lewis thinning algorithm. Set Π = ∅.

1. Simulate Π = { i } from a Poisson process on A with intensity such that (x ) ≥ ν (x ) for each x ∈ A.

2.

Independently for all i, accept i w.p.

ν ( i ) ( i ) and set Π = Π ∪ { i }
Output Π = {x i } as a Poisson process with intensity ν . We need t (s) and the inverse G -1 t (s) to be analytically tractable with G t (∞) < ∞. The adaptive thinning sampling scheme [START_REF] Ogata | On Lewis' simulation method for point processes[END_REF][START_REF] Favaro | MCMC for normalized random measure mixture models[END_REF] sequentially samples the points of the Poisson process and adapts the upper bound. It is summarized in Algorithm 6 and illustrated in Figure 3. [START_REF]1 Size of the networks, number of communities and computational time[END_REF]. The e ciency of this approach depends on the acceptance probability ν (s)/ t (s).

Completely random measures

Completely random measures (CRMs) were introduced by [START_REF] Kingman | Completely random measures[END_REF][START_REF] Kingman | Poisson processes[END_REF] and are now standard tools for constructing exible BNP models; see for example the surveys of [START_REF] Lijoi | Models beyond the Dirichlet process[END_REF] or Daley and Vere-Jones (2008b, Section 10.1). They generalize Poisson random measures with random positive masses instead of unit masses. In this chapter, we are going to restrict ourselves to the R + space.

Algorithm 6: Adaptive thinning algorithm.

Set Π = ∅, t = ε. Iterate until termination:

1. Draw r ∼ Exp(1); 2. if r > G t (∞), terminate; else set t = G -1 t (r );
3. with probability ν (t )/ t (t ), accept sample t and set Π = Π ∪ {t };

4. set t = t and continue.

Output Π = {t i } as a draw from the Poisson process with intensity ν on (ε, ∞).

Definition

More formally, a CRM W on R + is a random measure such that, for any collection of disjoint measurable subsets A 1 , . . . , A n of R + , W (A 1 ), . . . ,W (A n ) are independent. A CRM can be decomposed into a sum of three independent parts: a non-random measure, a countable collection of atoms with random masses at xed locations, and a countable collection of atoms with random masses and random locations. Here, we will only consider CRMs with random masses and random locations, which take the form

W = ∞ i=1 w i δ θ i
where the w i ∈ R + are the masses and θ i ∈ R + are the locations; see Figure 3.5 for an example of realization. The law of W can actually be characterized by a Poisson point process

Π = {(w i , θ i ) i=1,2,... } on R 2
+ with mean measure ν (dw, dθ ). We focus here on the case where the CRM is homogeneous with stationary increments. This implies that the locations θ i are independent of the weights w i and the mean measure decomposes as ν (dw, dθ ) = ρ (dw )λ(dθ ) where λ is the Lebesgue measure and ρ is a Lévy measure on (0, +∞). That is, ρ veri es

∞ 0 (1 -e -w )ρ (dw ) < ∞.
(3.2)

We will write W ∼ CRM(ρ, λ).

Properties

Let α be the number of jumps in [0, α] we have

E [ α ] = ∞ 0 α 0 ρ (dw )λ(dθ ) and the α ∼ Poisson α ∞ 0 ρ (dw ) If ∞ 0 ρ (dw ) =
∞ then there will be almost surely (a.s.) an in nite number of jumps in any interval [0, α] and we refer to the CRM as in nite-activity. Otherwise, it is called nite-activity.

Condition (3.2) guarantees that the total mass W (

[0, α]) = α i=1 w i is nite a.s. for any α < ∞. Note that W (R + ) = ∞ a.s. if ∞ 0 ρ (dw ) > 0. The Laplace functional of W ([0, α]) is E e -tW ([0,α]) = e -αψ (t )
for any t > 0 where

ψ (t ) = ∞ 0 (1 -e -tw )ρ (dw )
is the Laplace exponent.

Let ρ be the tail Lévy intensity de ned as

ρ (x ) = ∞ x ρ (dw ) (3.3)
for x > 0. This function corresponds to the expected number of points (w i , θ i ) such that w i > x and θ i ∈ [0, 1], and its asymptotic properties play an important role in the characterization of the graph properties. The CRM is said to be regularly varying if

ρ (x ) x↓0 ∼ (1/x )x -σ
for σ ∈ (0, 1) where is a slowly varying function s.t. lim t→∞ (at )/ (t ) = 1 for any a > 0.

The equivalence notation f (x

) x↓0 ∼ (x ) is used for lim x→0 f (x ) (x ) = 1.

Generalized gamma process

As a particular case of CRM, we will focus on the generalized gamma process (GGP, [START_REF] Hougaard | Survival models for heterogeneous populations derived from stable distributions[END_REF][START_REF] Brix | Generalized gamma measures and shot-noise Cox processes[END_REF], which has been extensively used in BNP models due to its generality, the interpretability of its parameters and its attractive conjugacy properties [START_REF] James | Poisson process partition calculus with applications to exchangeable models and Bayesian nonparametrics[END_REF][START_REF] Lijoi | Controlling the reinforcement in Bayesian non-parametric mixture models[END_REF][START_REF] Saeedi | Priors over recurrent continuous time processes[END_REF][START_REF] Caron | Bayesian nonparametric models for bipartite graphs[END_REF]Caron et al., 2014). The Lévy measure in this case is ρ (dw ) = ρ (w )dw where

ρ (w ) = 1 Γ(1 -σ ) w -1-σ exp(-wτ ) (3.4)
where the parameters (σ , τ ) verify

σ ∈ (0, 1), τ ≥ 0 or σ ∈ (-∞, 0], τ > 0. (3.5)
The GGP encompasses a wide range of possibilities including nite and in nite-activity cases.

Finite-activity case. When σ < 0 we have ρ

(w ) = -τ σ σ Gamma(w; -σ , τ ) implying ∞ 0 ρ (w )dw = - τ σ σ < ∞.
We then have a nite number of jumps in [0, α] a.s.

α ∼ Poisson -α τ σ σ (3.6)
while for i = 1, . . . , α , the jumps w i are Gamma (-σ , τ ) i.i.d.

Infinite-activity case. When (σ ≥ 0) we have ∞ 0 ρ (w )dw = ∞ and special cases include: • the gamma process: σ = 0, τ > 0 • the stable process: σ ∈ (0, 1), τ = 0 • the inverse-Gaussian process: σ = 1 2 , τ > 0 For σ > 0, the tail Lévy intensity is

ρ (x ) = ∞ x 1 Γ(1 -σ ) w -1-σ exp(-τw )dw =      τ σ Γ(-σ ,τ x ) Γ(1-σ ) if τ > 0 x -σ Γ(1-σ )σ if τ = 0
where Γ(a, x ) is the incomplete gamma function and the CRM is regularly varying with

(1/x ) = 1 σ Γ(1 -σ ) .

Simulation

Using the Poisson process construction, simulating a homogeneous CRM on [0, α] where λ([0, α]) < ∞ is straightforward:

1. Simulate the jumps (w i ) from a Poisson process with mean measure λ([0, α])ρ (dw ).

2. For each i simulate the locations θ i ∼ λ(•) λ([0,α]) . Let now concentrate on the jumps simulation in the case of a tilted truncated GGP, i.e. we want to sample points from a Poisson process with truncated mean measure

ρ ε (dw ) = h(w )w -1-σ e -τw 1 w >ε dw
where h is a positive, decreasing and bounded function, and (τ , σ ) verify either τ ≥ 0 and σ ∈ (0, 1), or τ > 0 and σ ∈ (-1, 0]. Note that this mean measure veri es R + ρ ε (dw ) < ∞ and it includes the (non tilted) truncated GGP by taking h(w ) = 1. We will resort to the adaptive thinning strategy of Algorithm 6 with the following family of adaptive bounds for τ > 0:

t (s) = h(t )t -1-σ exp(-τs) with t (s) > ρ (s) for s > t. We have, G t (s) = s t t (s )ds = h(t ) τ t -1-σ (exp(-τt ) -exp(-τs))
and

G -1 t (r ) = - 1 τ log exp(-τt ) - rτ t -1-σ h(t )
.

For τ = 0, we consider bounds

t (s) = h(t )s -1-σ and we obtain G t (s) = h(t ) σ (t -σ -s -σ ) G -1 t (r ) = t -σ - rσ h(t ) -1/σ
.

The e ciency of this approach depends on the acceptance probability, which is given, for τ > 0, by ρ ε (s)

t (s) = h(s)s -1-σ h(t )t -1-σ < 1 for s > t.

Vectors of CRMs

Multivariate extensions of CRMs have been proposed recently by various authors [START_REF] Epifani | Nonparametric priors for vectors of survival functions[END_REF][START_REF] Leisen | Vectors of two-parameter Poisson-Dirichlet processes[END_REF][START_REF] Leisen | A vector of Dirichlet processes[END_REF][START_REF] Gri N | Comparing distributions by using dependent normalized random-measure mixtures[END_REF][START_REF] Lijoi | Bayesian inference with dependent normalized completely random measures[END_REF]. These models are closely related to Lévy copulas [START_REF] Tankov | Dependence structure of spectrally positive multidimensional Lévy processes[END_REF][START_REF] Cont | Financial modelling with jump processes[END_REF][START_REF] Kallsen | Characterization of dependence of multidimensional Lévy processes using Lévy copulas[END_REF] and multivariate subordinators on cones (Barndor -Nielsen et al., 2001;[START_REF] Skorohod | Random processes with independent increments[END_REF]. We will build in particular on the class of compound completely random measures, proposed by Gri n and [START_REF] Gri N | Compound random measures and their use in Bayesian nonparametrics[END_REF].

Definition

A vector of CRMs (W 1 , . . . ,W p ) on R + is a collection of random measures W k , k = 1, . . . , p, such that, for any collection of disjoint measurable subsets A 1 , . . . , A n of R + , the vectors

W 1 (A 1 ), . . . ,W p (A 1 ) , W 1 (A 2 ), . . . ,W p (A 2 ) ,. . . , W 1 (A n ), . . . ,W p (A n ) are mutually indepen- dent.
We only consider here vectors of CRMs with both random weights and locations. In this case, the measures W k , k = 1, . . . , p, are a.s. discrete and take the form

W k = ∞ i=1 w ik δ θ i .
(3.7)

The law of the vector of CRMs can be characterized by a Poisson point process on R p+1 +

with mean measure ν (dw 1 , . . . , dw p , dθ ). We focus again on homogeneous vectors of CRMs with stationary increments where the mean measure can be written as ν (dw 1 , . . . , dw p , dθ ) = ρ (dw 1 , . . . , dw p )λ(dθ ).

(3.8)

where ρ is a measure on R p + , concentrated on R p + \{0}, which satis es

R p + min 1, p k=1 w k ρ (dw 1 , . . . , dw p ) < ∞. (3.9)
We use the same notation as for (scalar) CRMs and write simply (W 1 , . . . ,W p ) ∼ CRM(ρ, λ).

(3.10)

Properties

A key quantity is the multivariate Laplace exponent de ned by

ψ (t 1 , . . . , t p ) := -log E e -p k =1 t k W k ([0,1]) = R p +
1 -e -p k=1 t k w k ρ (dw 1 , . . . , dw p ).

Note that this quantity involves a p-dimensional integral which may not be analytically computable, and may be expensive to evaluate numerically. As for CRMs, if

R p + ρ (dw 1 , . . . , dw p ) = ∞
then there will be an in nite number of θ i ∈ [0, α] for which k w ik > 0 and the vector of CRMs is called in nite-activity. Otherwise, it is called nite-activity. Note that some (but not all) CRMs may still be marginally nite-activity.

Compound CRMs

The key component is the multivariate Lévy measure ρ in (3.10). Various approaches have been developed for constructing multivariate Lévy measures [START_REF] Tankov | Dependence structure of spectrally positive multidimensional Lévy processes[END_REF][START_REF] Cont | Financial modelling with jump processes[END_REF][START_REF] Kallsen | Characterization of dependence of multidimensional Lévy processes using Lévy copulas[END_REF]Barndor -Nielsen et al., 2001;[START_REF] Skorohod | Random processes with independent increments[END_REF], or more speci cally vectors of CRMs [START_REF] Epifani | Nonparametric priors for vectors of survival functions[END_REF][START_REF] Leisen | Vectors of two-parameter Poisson-Dirichlet processes[END_REF][START_REF] Leisen | A vector of Dirichlet processes[END_REF][START_REF] Gri N | Comparing distributions by using dependent normalized random-measure mixtures[END_REF][START_REF] Lijoi | Bayesian inference with dependent normalized completely random measures[END_REF]. We will consider the following particular form:

ρ (dw 1 , . . . , dw p ) = e -p k=1 γ k w k ∞ 0 w -p 0 F dw 1 w 0 , . . . , dw p w 0 ρ 0 (dw 0 ) (3.11)
where F (dβ 1 , . . . dβ p ) is some score probability distribution on R d + , with moment generating function M (t 1 , . . . , t p ) = E e p k=1 t k β k , ρ 0 is a base Lévy measure on (0, ∞) and γ k ≥ 0 are exponentially tilting parameters for k = 1, . . . , p.

The model de ned by (3.8) and (3.11) is a special case of the compound completely random measure (CCRM) model proposed by Gri n and [START_REF] Gri N | Compound random measures and their use in Bayesian nonparametrics[END_REF]. It admits the following hierarchical construction, which makes interpretability, characterization of the conditionals and analysis of this class of models particularly easy. Let

W 0 = ∞ i=1 w i0 δ θ i ∼ CRM( ρ 0 , λ) (3.12)
where ρ 0 is a measure on (0, ∞) de ned by ρ 0 (dw 0 ) = M (-w 0 γ 1 , . . . , -w 0 γ p )ρ 0 (dw 0 ), and for k = 1, . . . , p and i = 1, 2, . . .

w ik = β ik w i0
where the scores β ik have the following joint distribution

(β i1 , . . . , β ip )|w i0 ind ∼ H (•|w i0 ) (3.13)
with H is an exponentially tilted version of F :

H (dβ 1 , . . . , dβ p |w 0 ) = e -w 0 p k=1 γ k β k F dβ 1 , . . . , dβ p R p + e -w 0 p k=1 γ k β k F d β 1 , . . . , d β p .
Additionally, the set of points (w i0 , β i1 , . . . , β ip ) i=1,2,... is a Poisson point process with mean measure e -w 0 p k=1 γ k β k F (dβ 1 , . . . , dβ p )ρ 0 (dw 0 ).

(3.14)

Dependence between the di erent CRMs is both tuned by the shared scaling parameter w i0 and potential dependency between the scores (β i1 , . . . , β ip ).

The Laplace exponent of (W 1 , . . . ,W p ) is (details in Appendix B.2)

ψ (t 1 , . . . , t p ) = ∞ 0 M -w 0 γ 1:p -M -w 0 (t 1:p + γ 1:p ) ρ 0 (dw 0 ) (3.15)
which only requires evaluating a one-dimensional integral, whatever the number p of components. Let nally denote

κ 0 (n, z) = ∞ 0 w n 0 e -zw 0 ρ 0 (dw 0 )
and

M (m 1 ,...,m p ) (t 1 , . . . , t p ) = E F       p k=1 β m k k e t k β k       = ∂M (t 1 , . . . , t p ) ∂t m 1 1 . . . ∂t m p p .
Specific choices for F and ρ 0 . We now give here speci c choices of score distribution F and base Lévy measure ρ 0 , which lead to scalable inference algorithms. As in (Gri n and Leisen, 2016), we consider that F is a product of independent gamma distributions

F (dβ 1 , . . . , dβ p ) = p k=1 β a k -1 k e -b k β k b a k k Γ(a k ) dβ k (3.16)
where a k > 0,b k > 0, k = 1, . . . , p, with (details in Appendix B.2)

M (t 1 , . . . , t p ) = p k=1 1 - t k b k -a k M (m 1 ,...,m p ) (t 1 , . . . , t p ) = p k=1 Γ(a k + m k ) Γ(a k ) b a k k (b k -t k ) a k +m k (3.17)
which leads to

H (dw 1 , . . . , dw p |w 0 ) ∝ p k=1 w a k -1 k e - b k w k w 0 -γ k w k dw k
which is also a product of gamma distributions. ρ 0 is set to be the mean measure of the jump part of a GGP. Using (3.16) and (3.4), the multivariate Lévy measure has the following analytic form Regarding the Laplace exponent, we obtain

ρ (dw 1 , . . . , dw p ) = 2e -p k=1 γ k w k Γ(1 -σ )       p k=1 w a k -1 k b a k k Γ(a k )       τ p k=1 b k w k -κ 2 K κ 2 τ k b k w k dw 1 . . .
ψ (t 1 , . . . , t p ) = 1 Γ(1 -σ ) ∞ 0       1 - p k=1 1 + w 0 t k b k + w 0 γ k -a k             p k=1 1 + w 0 γ k b k -a k       w -1-σ 0 e -w 0 τ dw 0 (3.18)
which can be evaluated numerically and for σ ∈ (0, 1) we have

κ 0 (n, z) = (z + τ ) -(n-σ ) Γ(n -σ ) Γ(1 -σ ) .

Simulation

The hierarchical construction of compound CRMs suggests an algorithm to simulate a vector of CRMS. We consider the following (truncated) mean measure

ρ ε (dw 1 , . . . , dw p ) = e -p k=1 γ k w k ∞ ε w -p 0 F dw 1 w 0 , . . . , dw p w 0 ρ 0 (dw 0 )
with ε ≥ 0. We can sample from the (truncated) CCRM as follows 1.(a) Sample (w i0 , θ i ) i=1,...,K from a Poisson point process with mean measure ρ 0 (dw 0 )λ(dθ )1 {w 0 >ε,θ ∈[0,α]} .

(b) For i = 1, . . . , K and k = 1, . . . , p, set w ik = β ik w i0 where (β i1 , . . . , β ip )|w i0 is drawn from (3.13).

The truncation level ε is set to 0 for nite-activity CCRMs, and ε > 0 otherwise. How to perform step 1.(a) in the case of a tilted GGP is explained in Section (3.3.4).

Chapter 4

Exchangeable random measures for sparse and modular graphs with overlapping communities

We propose a novel statistical model for sparse networks with overlapping community structure.

The model is based on representing the graph as an exchangeable point process, and naturally generalizes existing probabilistic models with overlapping block-structure to the sparse regime. Our construction builds on vectors of completely random measures, and has interpretable parameters, each node being assigned a vector representing its level of a liation to some latent communities.

We develop methods for simulating this class of random graphs, as well as to perform posterior inference. We show that the proposed approach can recover interpretable structure from two realworld networks and can handle graphs with thousands of nodes and tens of thousands of edges. This work is about to be submitted to a statistical journal [START_REF] Todeschini | Exchangeable random measures for sparse and modular graphs with overlapping communities[END_REF].

Introduction

There has been a growing interest in the analysis, understanding and modeling of network data over the recent years. A network is composed of a set of nodes, or vertices, with connections between them. Network data arise in a wide range of elds, and include social networks, collaboration networks, communication networks, biological networks, food webs and are a useful way of representing interactions between sets of objects. Of particular importance is the elaboration of random graph models, which can capture the salient properties of real-world graphs.

Following the seminal work of [START_REF] Erdös | On random graphs[END_REF], various network models have been proposed; see the overviews of Newman (2003a[START_REF] Newman | Networks: an introduction[END_REF], [START_REF] Kolaczyk | Statistical Analysis of Network Data: Methods and Models[END_REF], [START_REF] Bollobás | Random graphs[END_REF], [START_REF] Goldenberg | A survey of statistical network models[END_REF], [START_REF] Fienberg | A brief history of statistical models for network analysis and open challenges[END_REF] or [START_REF] Jacobs | A uni ed view of generative models for networks: models, methods, opportunities and challenges[END_REF]. In particular, a large body of the literature has concentrated on models that can capture some modular or community structure within the network. The rst statistical network model in this line of research is the popular stochastic block-model [START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Snijders | Estimation and prediction for stochastic blockmodels for graphs with latent block structure[END_REF][START_REF] Nowicki | Estimation and prediction for stochastic blockstructures[END_REF]. The stochastic block-model assumes that each node belongs to one of p latent communities, and the probability of connection between two nodes is given by a p × p connectivity matrix. This model has been extended in various directions, by introducing degree-correction parameters [START_REF] Karrer | Stochastic blockmodels and community structure in networks[END_REF], by allowing the number of communities to grow with the size of the network [START_REF] Kemp | Learning systems of concepts with an in nite relational model[END_REF], or by considering overlapping communities [START_REF] Airoldi | Mixed membership stochastic blockmodels[END_REF][START_REF] Miller | Nonparametric latent feature models for link prediction[END_REF][START_REF] Latouche | Overlapping stochastic block models with application to the French political blogosphere[END_REF][START_REF] Palla | An in nite latent attribute model for network data[END_REF][START_REF] Yang | Overlapping community detection at scale: a nonnegative matrix factorization approach[END_REF]. Stochastic block-models and their extensions have shown to o er a very exible modeling framework, with interpretable parameters, and have been successfully used for the analysis of numerous real-world networks. However, as outlined by [START_REF] Orbanz | Bayesian models of graphs, arrays and other exchangeable random structures[END_REF], when one makes the usual assumption that the ordering of the nodes is irrelevant in the de nition of the statistical network model, the Bayesian probabilistic versions of those models lead to dense networks1 : that means that the number of edges grows quadratically with the number of nodes. This property is rather undesirable, as many real-world networks are believed to be sparse.

Recently, [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] proposed an alternative framework for statistical network modeling. The framework is based on representing the graph as an exchangeable random measure on the plane. More precisely, the nodes are embedded at some location θ i ∈ R + and, for simple graphs, a connection exists between two nodes i and j if there is a point at locations (θ i , θ j ) and (θ j , θ i ). An undirected simple graph is therefore represented by a symmetric point process Z on the plane

Z = i,j z ij δ (θ i ,θ j ) (4.1)
where z ij = z ji = 1 if i and j are connected, 0 otherwise; see Figure 4.1 for an illustration. [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] noted that jointly exchangeable random measures, a notion to be dened in Eq. ( 4.13), admit a representation theorem due to [START_REF] Kallenberg | Exchangeable random measures in the plane[END_REF], providing a general construction for exchangeable random measures hence random graphs represented by such objects. This connection is further explored by [START_REF] Veitch | The class of random graphs arising from exchangeable random measures[END_REF] and [START_REF] Borgs | Sparse exchangeable graphs and their limits via graphon processes[END_REF], who provide a detailed description and extensive theoretical analysis of the associated class of random graphs, which they name Kallenberg exchangeable graphs or graphon processes. Within this class of models, [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] consider in particular the following simple generative model, where two nodes i j connect with probability Pr(z ij = 1|(w ) =1,2,... ) = 1 -e -2w i w j (4.2)

where the (w i , θ i ) i=1,2,... are the points of a Poisson point process on R 2 + . The parameters w i > 0 can be interpreted as sociability parameters. Depending on the properties of the mean measure of the Poisson process, the authors show that it is possible to generate both dense and sparse graphs, with potentially heavy-tailed degree distributions, within this framework. The construction (4.2) is however rather limited in terms of capturing structure in the network. [START_REF] Herlau | Completely random measures for modelling block-structured sparse networks[END_REF] proposed an extension of (4.2), which can accommodate a community structure. More precisely, introducing latent community membership variables c i ∈ {1, . . . , p}, two nodes i j connect with probability

Pr(z ij = 1|(w , c ) =1,2,... , (η k ) 1≤k, ≤p ) = 1 -e -2η c i c j w i w j (4.3)
where the (w i , c i , θ i ) i=1,2,... are the points of a (marked) Poisson point process on R + × {1, . . . , p} × R + and η k are positive random variables parameterizing the strength of interaction between nodes in community k and nodes in community . The model is similar in spirit to the degree-corrected stochastic block-model [START_REF] Karrer | Stochastic blockmodels and community structure in networks[END_REF], but within the point process framework (4.1), and can thus accommodate both sparse and dense networks with community structure. The model of [START_REF] Herlau | Completely random measures for modelling block-structured sparse networks[END_REF] however shares the limitations of the (degree-corrected) stochastic block-model, in the sense that it cannot model overlapping community structures, each node being assigned to a single community; see Latouche et al. ( 2011) and [START_REF] Yang | Overlapping community detection at scale: a nonnegative matrix factorization approach[END_REF] for more discussion along these lines. Other extensions with block structure or mixed membership block structure are also suggested by [START_REF] Borgs | Sparse exchangeable graphs and their limits via graphon processes[END_REF].

In this chapter, we consider that each node i is assigned a set of latent non-negative parameters w ik , k = 1, . . . , p, and that the probability that two nodes i j connect is given by Pr(z ij = 1|(w 1 , . . . , w p ) =1,2,... ) = 1 -e -2 p k=1 w ik w jk . (4.4)

These non-negative weights can be interpreted as measuring the level of a liation of node i to the latent communities k = 1, . . . , p. For example, in a friendship network, these communities can correspond to colleagues, family, or sport partners, and the weights measure the level of a liation of an individual to each community. Note that as individuals can have high weights in di erent communities, the model can capture overlapping communities. The link probability (4.4) builds on a non-negative factorization; it has been used by other authors for network modeling [START_REF] Yang | Overlapping community detection at scale: a nonnegative matrix factorization approach[END_REF][START_REF] Zhou | In nite edge partition models for overlapping community detection and link prediction[END_REF] and is also closely related to the model for multigraphs of [START_REF] Ball | E cient and principled method for detecting communities in networks[END_REF]. The main contribution of this chapter is to use the link probability (4.4) within the point process framework of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF]. To this aim, we consider that the node locations and weights (w i1 , . . . , w ip , θ i ) i=1,2,... are drawn from a Poisson point process on R p+1 + with a given mean measure ν . The construction of such multivariate point process relies on vectors of completely random measures (or equivalently multivariate subordinators). In particular, we build on the exible though tractable construction recently introduced by Gri n and [START_REF] Gri N | Compound random measures and their use in Bayesian nonparametrics[END_REF].

The proposed model generalizes that of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] by allowing the model to capture more structure in the network, while retaining its main features, and is shown to have the following properties:

• Interpretability: each node is assigned a set of positive parameters, which can be interpreted as measuring the levels of a liation of a node to latent communities; once those parameters are learned, they can be used to uncover the latent structure in the network. • Sparsity: we can generate graphs whose number of edges grows sub-quadratically with the number of nodes. • Exchangeability: in the sense of [START_REF] Kallenberg | Exchangeable random measures in the plane[END_REF]. Additionally, we develop a Markov chain Monte Carlo (MCMC) algorithm for posterior inference with this model, and show experiments on two real-world networks with a thousand of nodes and tens of thousands of edges. See Appendix C.2 for some background on MCMC algorithms.

The chapter is organized as follows. The class of random graph models is introduced in Section 4.2. Properties of the class of graphs and simulation are described in Section 4.3. We derive a scalable MCMC algorithm for posterior inference in Section 4.4. In Section 4.5 we provide illustrations of the proposed method on simulated data and on two networks: a network of citations between political blogs and a network of connections between US airports. We show that the approach is able to discover interpretable structure in the data. Representation of an undirected graph via a point process Z . Each node i is embedded in R + at some location θ i and is associated with a set of positive attributes (w i1 , . . . , w ip ). An edge between nodes θ i and θ j is represented by a point at locations (θ i , θ j ) and (θ j , θ i ) in R 2 + .

Sparse graph models with overlapping communities

In this section, we present the statistical model for simple graphs. The construction builds on vectors of completely random measures (CRM, [START_REF] Kingman | Completely random measures[END_REF]. We only provide here the necessary material for the de nition of the network model; please refer to Section 3.3 of Chapter 3 for additional background on vectors of CRMs. The model described in this section can also be extended to bipartite graphs; see Appendix C.4.

General construction using vectors of CRMs

We consider that each node i is embedded at some location θ i ∈ R + , and has some set of positive weights (w i1 , . . . , w ip ) ∈ R p + . The points (w i1 , . . . , w ip , θ i ) i=1,...,∞ can be described using a vector of CRMs (W 1 , . . . ,W p ) with

W k = ∞ i=1 w ik δ θ i , for k = 1, . . . , p (4.5)
and we assume

(W 1 , . . . ,W p ) ∼ CRM(ρ, λ) (4.6)
where λ is the Lebesgue measure and ρ is a measure on R Mimicking the hierarchical construction of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], we introduce integervalued random measures where the n ijk are natural integers. The vector of random measures (D 1 , . . . , D p ) can be interpreted as representing a multiview (a.k.a. multiplex or multi-relational) directed multigraph [START_REF] Verbrugge | Multiplexity in adult friendships[END_REF][START_REF] Salter-Townshend | Latent space models for multiview network data[END_REF], where n ijk represents the number of interactions from node i to node j in the view k; see Figure 4.2 for an illustration. Conditionally on the vector of CRMs, the measures D k are independently drawn from a Poisson process2 with mean measure

D k on R 2 + , k = 1, . . . , p, D k = ∞ i=1 ∞ j=1 n ijk δ (θ i ,θ j ) θ 1 θ 2 θ 3 θ 4 3 1 1 1 2 θ 1 θ 2 θ 3 4 2 1 3 θ 1 θ 2 θ 3 θ 4 (a) (b) (c)
W k × W k D k |(W 1 , . . . ,W p ) ∼ Poisson (W k × W k )
that is, the n ijk are independently Poisson distributed with rate w ik w jk . Finally, the point process Z representing the graph (4.1) is deterministically obtained from (D 1 , . . . , D p ) by setting z ij = 1 if there is at least one directed connection between i and j in any view, and 0 otherwise, therefore z ij = min(1, p k=1 n ijk +n jik ). To sum up, the graph model is described as follows:

W k = ∞ i=1 w ik δ θ i (W 1 , . . . ,W p ) ∼ CRM(ρ, λ) D k = ∞ i=1 ∞ j=1 n ijk δ (θ i ,θ j ) D k | W k ∼ Poisson (W k × W k ) Z = ∞ i=1 ∞ j=1 min(1, p k=1 n ijk + n jik )δ (θ i ,θ j ) . (4.8)
The model construction is illustrated in Figure 4.3. Integrating out the measures D k , k = 1, . . . , p, the construction can be expressed as, for i ≤ j

z ij |(w 1 , . . . , w p ) =1,2,... ∼ Ber(1 -exp(-2 p k=1 w ik w jk )) i j Ber(1 -exp(- p k=1 w 2 ik )) i = j (4.9)
and z ji = z ij ; see Figure 4.1.

Graph Restrictions. Except in trivial cases, we have W k (R + ) = ∞ a.s. and therefore Z (R 2 + ) = ∞ a.s., so the number of points over the plane is in nite a.s. For α > 0, we consider restrictions of the measures W k , k = 1, . . . , p, to the interval [0, α] and of the measures D k and Z to the box [0, α] 2 , and write respectivelyW kα , D kα and Z α these restrictions. Note that condition (4.7) ensures that W kα ([0, α]) < ∞ a.s. hence D kα ([0, α] 2 ) < ∞ and Z α ([0, α] 2 ) < ∞ a.s. As a consequence, for a given α > 0, the model yields a nite number of edges a.s., even though there may be an in nite number of points (w i , θ i ) ∈ R + × [0, α]; see Section 4.3.

Remark 5. The model de ned above can also be used for random multigraphs, where n ij = p k=1 n ijk is the number of directed interactions between i and j. Then we have

n ij |(w 1 , . . . , w p ) =1,2,... ∼ Poisson p k=1 w ik w jk
which is a Poisson non-negative factorization [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF][START_REF] Cemgil | Bayesian inference for nonnegative matrix factorisation models[END_REF][START_REF] Psorakis | Overlapping community detection using Bayesian non-negative matrix factorization[END_REF][START_REF] Ball | E cient and principled method for detecting communities in networks[END_REF][START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF].

The model de ned by Eq. ( 4.9) allows to model networks which exhibit assortativity (Newman, 2003b), meaning that two nodes with similar characteristics (here similar set of weights) are more likely to connect than nodes with dissimilar characteristics. The link function can be generalized to (see e.g. Zhou, 2015) Graph sampled from our particular model with three latent communities, identi ed by colors red, green, blue. For each node, the intensity of each color is proportional to the value of the associated weight in that community. Pure red/green/blue color indicates the node is only strongly a liated to a single community. A mixture of those colors indicates balanced a liations to di erent communities. Graph generated with the software Gephi [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF].

z ij ∼ Ber 1 -exp - p k=1 p =1 η k w ik w j
where η k ≥ 0, in order to be able to capture both assortative and dissortative mixing in the network. In particular, setting larger values o -diagonal than on the diagonal of the matrix (η k ) 1≤k, ≤p allows to capture dissortative mixing. The properties and algorithms for simulation and posterior inference can trivially be extended to this more general case. In order to keep the notations as simple as possible, we focus here on the simpler link function (4.9).

Particular model based on compound CRMs

The key component in our statistical network model is the multivariate Lévy measure ρ in (4.6). As in Section 3.4.3 of Chapter 3, we will in this chapter consider the following particular form:

ρ (dw 1 , . . . , dw p ) = e -p k=1 γ k w k ∞ 0 w -p 0 F dw 1 w 0 , . . . , dw p w 0 ρ 0 (dw 0 ) (4.10)
where F (dβ 1 , . . . dβ p ) is some score probability distribution on R d + , with moment generating function M (t 1 , . . . , t p ), ρ 0 is a base Lévy measure on R + and γ k ≥ 0 are exponentially tilting parameters for k = 1, . . . , p. Dependence between the di erent CRMs is both tuned by the shared scaling parameter w i0 and potential dependency between the scores (β i1 , . . . , β ip ). The hierarchical construction has the following interpretation:

• The weight w i0 is an individual scaling parameter for node i whose distribution is tuned by the base Lévy measure ρ 0 . It can be considered as a degree correction, as often used in network models [START_REF] Karrer | Stochastic blockmodels and community structure in networks[END_REF][START_REF] Zhao | Consistency of community detection in networks under degree-corrected stochastic block models[END_REF][START_REF] Herlau | Completely random measures for modelling block-structured sparse networks[END_REF]. As shown in Section 4.3, ρ 0 tunes the overall sparsity properties of the network.

• The community-related scores β ik tune the level of a liation of node i to community k; this is controlled by both the score distribution F and the tilting coe cients γ k . These parameters tune the overlapping block-structure of the network. An example of such a graph with three communities is displayed in Figure 4.4.

Specific choices for F and ρ 0 . Following Section 3.4.3 of Chapter 3, we will consider that F is a product of independent gamma distributions

F (dβ 1 , . . . , dβ p ) = p k=1 β a k -1 k e -b k β k b a k k Γ(a k ) dβ k (4.11)
and ρ 0 is set to be the mean measure of the jump part of a GGP

ρ 0 (w 0 ) = 1 Γ(1 -σ ) w -1-σ 0 exp(-w 0 τ ). (4.12)
This speci c choice leads to scalable inference algorithms derived in Section 4.4.3.

Properties and simulation

Exchangeability

The point process Z de ned by (4.8) is jointly exchangeable in the sense of [START_REF] Kallenberg | Exchangeable random measures in the plane[END_REF][START_REF] Kallenberg | Probabilistic symmetries and invariance principles[END_REF]. For any h > 0 and any permutation π of N

(Z (A i × A j )) d = (Z (A π (i) × A π (j) )) for (i, j) ∈ N 2 (4.13)
where A i = [h(i -1), hi]. This follows directly from the fact that the vector of CRMs (W 1 , . . . ,W p ) has independent and identically distributed increments, hence

(W 1 (A i ), . . . ,W p (A i )) d = (W 1 (A π (i) ), . . . ,W p (A π (i) )).
The model thus falls into the general representation theorem for exchangeable point processes [START_REF] Kallenberg | Exchangeable random measures in the plane[END_REF].

Sparsity

In this section, following the asymptotic notations of Janson (2011), we derive the sparsity properties of our graph model, rst for the general construction of Section 4.2.1, then for the speci c construction on compound CRMs of Section 4.2.2. Similarly to the notations of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], let Z α be the restriction of Z to the box [0, α] 2 . Let (N α ) α ≥0 and (N (e) α ) α ≥0 be counting processes respectively corresponding to the number of nodes and edges in Z α :

N α = card({θ i ∈ [0, α]|Z ({θ i } × [0, α]) > 0}) N (e) α = Z ({(x, ) ∈ R 2 + |0 ≤ x ≤ ≤ α}).
Note that in the propositions below, we discard the trivial case R p + ρ (dw 1 , . . . , dw p ) = 0 which implies N (e) α = N α = 0 a.s.

General construction. The next proposition characterizes the sparsity properties of the random graph depending on the properties of the Lévy measure ρ. In particular, if

R p + ρ (dw 1 , . . . , dw p ) = ∞
then, for any α > 0, there is a.s. an in nite number of θ i ∈ [0, α] for which k w ik > 0 and the vector of CRMs is called in nite-activity. Otherwise, it is nite-activity.

Proposition 6. Assume that, for any k = 1, . . . , p,

R p + w k ρ (dw 1 , . . . , dw p ) < ∞ (4.14)
Then In this case all CRMs W 0 ,W 1 , . . . ,W p are in nite-activity. Otherwise they are all nite-activity and the vector of CRMs is nite-activity. In the particular case of a CCRM with independent gamma distributed scores (4.11) and generalized gamma process base measure (4.12), the condition (4.15) is satis ed whenever σ ≥ 0. The next proposition characterizes the sparsity of the network depending on the properties of the base Lévy measure ρ 0 .

N (e) α = Θ(N 2 α ) if (W 1 , . . . ,W p ) is nite-activity o(N 2 α ) otherwise a.s. as α tends to ∞.
Proposition 7. Assume that

∞ 0 wρ 0 (dw ) < ∞ (4.16)
and F is not degenerated at 0. Then

N (e) α = Θ(N 2 α ) if ∞ 0 ρ 0 (dw ) < ∞ o(N 2
α ) otherwise a.s. as α tends to ∞. Furthermore, if the tail Lévy intensity ρ 0 de ned by

ρ 0 (x ) = ∞ x ρ 0 (dw ), (4.17)
is a regularly varying function, i.e. ) for σ ∈ (0, 1).

ρ 0 (x ) x -σ (1/x ) -→ 1 as x → 0
for some σ ∈ (0, 1) where is a slowly varying function verifying lim t→∞ (at )/ (t ) = 1 for any a > 0 and lim t→∞ (t ) > 0, then

N (e) α = O (N 2/(1+σ ) α )
a.s. as α tends to ∞. In the particular case of a CCRM with independent gamma distributed scores (4.11) and generalized gamma process base measure (4.12), condition (4.16) is equivalent to having τ > 0. In this case, we therefore have

N (e) α =          Θ(N 2 α ) if σ < 0 o(N 2 α ) if σ ≥ 0 O (N 2/(1+σ ) α ) if σ ∈ (0, 1) a.s. as α tends to ∞.
The proof is given in Appendix C.1. Figure 4.5(a) provides an empirical illustration of Proposition 7 for a CCRM with independent gamma scores and generalized gamma based Lévy measure. Figure 4.5(b) shows empirically that the degree distribution also exhibits a power-law behavior when σ ∈ (0, 1).

Simulation

The point process Z is de ned on the plane. We describe in this section how to sample realizations of restrictions Z α of Z to the box [0, α] 2 . The hierarchical construction given by Eq. (4.8) suggests a direct way to sample from the model: 1. Sample (w i1 , . . . , w ip , θ i ) i=1,2,... from a Poisson process with mean measure ν (dw 1 , . . . , dw p , dθ )1 θ ∈[0,α] .

2. For each pair of points, sample z ij from (4.9).

There are two caveats to this strategy. First, for in nite-activity CRMs, the number of points in R p + × [0, α] is a.s. in nite; even for nite-activity CRMs, it may be so large that it is not practically feasible. We need therefore to resort to an approximation, by sampling from a Poisson process with an approximate mean measure ν ε (dw 1 , . . . , dw p , dθ )1 θ ∈[0,α] = ρ ε (dw 1 , . . . , dw p )λ(dθ )1 θ ∈[0,α] where R p + ρ ε (dw 1 , . . . , dw p ) < ∞ with ε > 0 controlling the level of approximation. The approximation is speci c to the choice of the mean measure, and such an approximation for CCRMs is described in Section 3.4.4 of Chapter 3.

The second caveat is that, for applying Eq. ( 4.9), we need to consider all pairs i ≤ j, which can be computationally problematic. We can instead, similarly to [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], use the hierarchical Poisson construction as follows:

1. Sample (w i1 , . . . , w ip , θ i ) i=1,2,...,K from a Poisson process with mean measure ν ε (dw 1 , . . . , dw p , dθ )

1 θ ∈[0,α] . Let W ε k,α = K i=1
w ik δ θ i be the associated truncated CRMs and W ε * k,α = K i=1 w ik their total masses.

For

k = 1, . . . , p, sample D * k,α |W ε * k,α ∼ Poisson((W ε * k,α ) 2 ). 3. For k = 1, . . . , p, = 1, . . . , D * k,α , j = 1, 2, sample U k j |W ε k,α ind ∼ W ε k,α W ε * k,α . 4. Set D ε k,α = D * k,α
=1 δ U k 1,k 2 . 5. Obtain Z from (D 1 , . . . , D p ) as in (4.8).

Posterior inference

In this section, we describe a MCMC algorithm for posterior inference of the model parameters and hyperparameters in the statistical network model de ned in Section 4.2. We rst describe the data augmentation scheme and characterization of conditionals. We then describe the sampler for a general Lévy measure ρ, and nally derive the sampler for compound CRMs.

Characterization of conditionals and data augmentation

Assume that we have observed a set of connections (z ij ) 1≤i,j≤N α , where N α is the number of nodes with at least one connection. We aim at inferring the positive parameters (w i1 , . . . , w ip ) i=1,...,N α associated to the nodes with at least one connection. We also want to estimate the positive parameters associated to the other nodes with no connection. The number of such nodes may be large, and even in nite for in nite-activity CRMs; but under our model, these parameters are only identi able through their sum, denoted (w * 1 , . . . , w * p ). Note that the node locations θ i are not likelihood identi able, and we will not try to infer them. We assume that there is a set of unknown hyperparameters ϕ of the mean intensity ρ, with prior p(ϕ). We assume that the Lévy measure ρ is absolutely continuous with respect to the Lebesgue measure on R d , and write simply ρ (dw 1 , . . . , dw p ; ϕ) = ρ (w 1 , . . . , w p ; ϕ)dw 1 . . . dw p . The parameter α is also assumed to be unknown, with some prior α ∼ Gamma(a α , b α ) with a α > 0, b α > 0. We therefore aim at approximating p (w 1k , . . . ,

w N α k , w * k ) k=1,...,p , ϕ, α |(z ij ) 1≤i,j≤N α .
As a rst step, we characterize the conditional distribution of the restricted vector of CRMs (W 1α , . . . ,W pα ) given the restricted measures (D 1α , . . . , D pα ). Proposition 8 below extends Theorem 12 of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF] to the multivariate setting.

Proposition 8. Let (θ 1 , . . . , θ N α ), N α ≥ 0 be the support points of (D 1α , . . . , D pα ), with

D kα = 1≤i,j≤N α n ijk δ (θ i ,θ j ) .
The conditional distribution of (W 1α , . . . ,W pα ) given (D 1α , . . . , D pα ) is equivalent to the distribution of

W 1 + N α i=1 w i1 δ θ i , . . . , W p + N α i=1 w ip δ θ i
where ( W 1 , . . . , W p ) is a vector of discrete random measures, which depends on (D 1α , . . . , D pα ) only through the total masses

w * k = W k ([0, α]).
The set of weights (w ik ) i=1,...,N α ;k=1,...,p and (w * k ) k=1,...,p are dependent, with joint conditional distribution

p (w 1k , . . . , w N α k , w * k ) k=1,...,p |(n ijk ) 1≤i,j≤N α ;k=1,...,p , ϕ, α ∝       N α i=1 p k=1 w m ik ik       e -p k=1 (w * k + Nα i=1 w ik ) 2       N α i=1 ρ (w i1 , . . . , w ip ; ϕ)       α N α * α (w * 1 , . . . , w * p ; ϕ) (4.18)
where m ik = N α j=1 n ijk + n jik and * α (w * 1 , . . . , w * p ; ϕ) is the pdf of the random vector (W 1 ([0, α]), . . . ,W p ([0, α])) w.r.t. the reference measure λ(dw * 1 , ..., dw * p ) + δ 0 p (dw * 1 , ..., dw * p ) where λ is the Lebesgue measure and 0 p is the p-dimensional zero vector.

The proof can be straightforwardly adapted from that of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], or from Proposition 5.2 of James (2014) and is omitted here. It builds on other posterior characterizations in Bayesian nonparametric models [START_REF] Prünster | Random probability measures derived from increasing additive processes and their application to Bayesian statistics[END_REF][START_REF] James | Poisson process partition calculus with applications to exchangeable models and Bayesian nonparametrics[END_REF][START_REF] James | Bayesian Poisson process partition calculus with an application to Bayesian Lévy moving averages[END_REF][START_REF] James | Posterior analysis for normalized random measures with independent increments[END_REF].

Data augmentation. Similarly to [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], we introduce latent count variables

n ijk = n ijk + n jik with ( n ij1 , . . . , n ijp )|w, z ∼      δ (0,...,0) if z ij = 0 tPoisson(2w i1 w j1 , . . . , 2w ip w jp ) if z ij = 1, i j n ij1 2 , . . . , n ijp 2 |w, z ∼ tPoisson(w 2 i1 , . . . , w 2 ip ) if z ij = 1, i = j (4.19)
where tPoisson(λ 1 , . . . , λ p ) is the multivariate Poisson distribution truncated at zero, whose probability mass function (pmf) is tPoisson(x 1 , . . .

x p ; λ 1 , . . . , λ p ) = p k=1 Poisson(x k ; λ k ) 1 -exp(- p k=1 x k λ k ) 1 p k=1 x k >0 .
One can sample from this distribution by rst sampling x = p k=1 x k from a zero-truncated Poisson distribution with rate p k=1 λ k , and then

(x 1 , . . . , x p )|(λ 1 , . . . , λ p ), x ∼ Multinomial x, λ 1 λ k , . . . λ p λ k .

MCMC algorithm: General construction

Using the data augmentation scheme together with the posterior characterization (4.18), we can derive the following MCMC sampler, which uses Metropolis-Hastings (MH) and Hamiltonian Monte Carlo (HMC) updates within a Gibbs sampler, and iterates as described in Algorithm 7. See Appendix C.2 for some background on MCMC algorithms.

Algorithm 7: MCMC sampler for posterior inference. At each iteration, 1. Update the latent variables given the rest using (4.19).

2. Update (w i1 , . . . , w ip ), i = 1, . . . ,N α given the rest using MH or HMC.

3. Update hyperparameters (ϕ, α ) and total masses (w * 1 , . . . , w * p ) given the rest using MH.

In general, if the Lévy intensity ρ can be evaluated pointwise, one can use a MH update for step 2, but it would scale poorly with the number of nodes. Alternatively, if the Lévy intensity ρ is di erentiable, one can use a HMC update [START_REF] Duane | Hybrid Monte Carlo[END_REF][START_REF] Neal | MCMC using Hamiltonian dynamics[END_REF].

The challenging part of the Algorithm 7 is Step 3. From Eq. ( 4.18) we have

p((w * k ) k=1,...,p , ϕ, α |rest) ∝ p(ϕ)p(α )e -p k=1 (w * k + Nα i=1 w ik ) 2       N α i=1 ρ (w i1 , . . . , w ip ; ϕ)       α N α * α (w * 1 , . . . , w * p ; ϕ).
This conditional distribution is not of standard form and involves the multivariate pdf * α (w * 1 , . . . , w * p ) of the random vector (W 1 ([0, α]), . . . ,W p ([0, α])) for which there is typically no analytic expression. All is available is its Laplace transform, which is given by

E e -p k=1 t k W k ([0,α]) = e -αψ (t 1 ,...,t p ;ϕ)
where

ψ (t 1 , . . . , t p ; ϕ) = R p + 1 -e -p k=1 t k w k ρ (dw 1 , . . . , dw p ; ϕ) (4.20)
is the multivariate Laplace exponent, which involves a p-dimensional integral. We propose to use a Metropolis-Hastings step, with proposal q w * 1:p , ϕ, α |w * 1:p , ϕ, α = q w * 1:p |w * 1:p , ϕ, α × q ϕ |ϕ × q α |α, ϕ, w * 1:p where q α |α, ϕ, w * 1:p = Gamma α; a α + N α , b α + ψ λ 1 , . . . , λ p ; ϕ and the proposal for w * 1:p is an exponentially tilted version of * α q w * 1:p |w * 1:p , ϕ = e -p k=1 λ k w * k * α w 1 , . . . , w p ; ϕ e -αψ (λ 1 ,...,λ p ; ϕ) (4.21) where λ k = w * k + 2 N α i=1 w ik and q ϕ |ϕ can be freely speci ed by the user. This leads to the following acceptance rate

r = p ϕ q ϕ | ϕ p(ϕ)q ϕ |ϕ        N α i=1 ρ w i1 , . . . , w ip ; ϕ ρ w i1 , . . . , w ip ; ϕ               b α + ψ λ 1 , . . . , λ p ; ϕ b α + ψ λ 1 , . . . , λ p ; ϕ        a α +N α e p k=1 [w 2 * k -w 2 * k ]
where λ k = w * k +2 N α i=1 w ik . This acceptance rate involves evaluating the multivariate Laplace exponent (4.20).

In the general case, the MCMC algorithm 7 thus requires to be able to Regarding point (c), the random variable with pdf (4.21) has the same distribution as the random vector W 1 ([0, α]), . . . ,W p ([0, α]) where (W 1 , . . . ,W p ) ∼ CRM(ρ , λ) with ρ is an exponentially tilted version of ρ ρ (w 1 , . . . , w p ) = e -k λ k w k ρ (w 1 , . . . , w p ).

By considering an approximate tilted intensity ρ ε (w 1 , . . . , w p ), one can approximately sample from (4.21) by simulating points from a Poisson process with mean measure α ρ ε (w 1 , . . . , w p ) and summing them up. Note that in practice, we can only sample a nite number of points and we might thus need further approximation; see Section (4.4.3).

MCMC algorithm: Construction based on CCRMs

The hierarchical construction of CCRMs enables to derive a certain number of simpli cations in the algorithm described in the previous section. Using the construction w ik = β ik w i0 where the points (w i0 , β i1 , . . . , β ip ) i=1,2,... have Lévy measure (3.14), we aim at approximating the posterior p (w 10 , . . . , w N α 0 ), (β 1k , . . . ,

β N α k , w * k ) k=1,...,p , ϕ, α |(z ij ) 1≤i,j≤N α . (4.22)
Conditionally on the latent count variables de ned in (4.19), we have the following conditional characterization, similar to (4.18)

p (w 10 , . . . , w N α 0 ), (β 1k , . . . , β N α k , w * k ) k=1,...,p |(n ijk ) 1≤i,j≤N α ;k=1,...,p , ϕ, α ∝       N α i=1 w m i i0 p k=1 β m ik ik       e -p k=1 (w * k + Nα i=1 w ik ) 2 -Nα i=1 w i0 ( p k=1 γ k β ik ) ×       N α i=1 f (β i1 , . . . , β ip ; ϕ)ρ 0 (w i0 ; ϕ)       α N α * α (w * 1 , . . . , w * p ; ϕ) (4.23)
where m i = p k=1 m ik and f and ρ 0 are resp. the density of F and intensity of ρ 0 with respect to the Lebesgue measure. If f and ρ 0 are di erentiable, one can use a HMC update for Step 1 of Algorithm 7; see details in Appendix (C.3).

Regarding

Step 2 of Algorithm 7, the Laplace exponent can be evaluated numerically using (3.18). We then need to sample total masses (w * 1 , . . . , w * p ) from (4.21), and this can be done by simulating points (w i0 , β i1 , . . . , β ip ) i=1,2,... from a Poisson process with exponentially tilted Lévy intensity αe -w 0 p k=1 (γ k +λ k )β k f (β 1 , . . . , β p )ρ 0 (w 0 ) (4.24)

and summing up the weights w * k = i=1,2,... w i0 β ik for k = 1, . . . , p. For in nite-activity CRMs, this is not feasible, and we suggest to resort to the approximation of [START_REF] Cohen | Gaussian approximation of multivariate Lévy processes with applications to simulation of tempered stable processes[END_REF].

More precisely, we write

(w * 1 , . . . , w * p ) = X ε + X ε
where the random vectors

X ε ∈ R p + and X ε ∈ R p + are de ned as X ε = i |w i0 <ε w i0 (β i1 , . . . , β ip ) and X ε = i |w i0 >ε w i0 (β i1 , . . . , β ip ).
We can sample a realization of the random vector X ε exactly by simulating the points of a Poisson process with mean intensity

αe -w 0 p k=1 (γ k +λ k )β k f (β 1 , . . . , β p )ρ 0 (w 0 )1 w 0 >ε .
See Section 3.4.4 of Chapter 3 for details. The positive random vector X ε is approximated by a truncated Gaussian random vector with mean µ ε and variance Σ ε such that

µ ε = α R p + w 1:p ρ ε (dw 1 , . . . , dw p ) Σ ε = α R p + w 1:p w T 1:p ρ ε (dw 1 , . . . , dw p )
where

ρ ε (dw 1 , . . . , dw p ) = e -p k =1 (γ k +λ k )w k ε 0 w -p 0 F
dw 1 w 0 , . . . , dw p w 0 ρ 0 (dw 0 ).

Note that µ ε and Σ ε can both be expressed as one-dimensional integrals using the gradient and Hessian of the moment generating function M of F . Theorem 9 in Appendix C.5, which is an adaptation of the results of [START_REF] Cohen | Gaussian approximation of multivariate Lévy processes with applications to simulation of tempered stable processes[END_REF] to CCRM, gives the conditions on the parameters of CCRM under which

Σ -1/2 ε (X ε -µ ε ) d → N (0, I p ) as ε → 0
and thus the approximation is asymptotically valid. The Gaussian approximation is in particular asymptotically valid for the CCRM de ned by (4.11) and ( 4.12) when σ ∈ (0, 1), hence is valid for all in nite-activity cases except σ = 0. Note that due to the Gaussian approximation in the proposal distribution for (w * 1 , . . . , w * ), Algorithm 7 does not actually admit the posterior distribution (4.22) as invariant distribution, and is an approximation of an exact MCMC algorithm targeting this distribution. We observe in the experimental section that this approximation provides very reasonable results for the examples considered.

In Appendix (C.3), we provide more details on the MCMC algorithm when F and ρ 0 take the form (4.11) and (4.12).

Experiments

Simulated data

We rst study the convergence of the MCMC algorithm on synthetic data simulated from the CCRM based graph model described in Section 4.2 where F and ρ 0 take the form (4.11) and (4.12). We generate an undirected graph with p = 2 communities and parameters α = 200,

σ = 0.2, τ = 1, b k = b = 1 p , a k = a = 0.2 and γ k = γ = 0.
The sampled graph has 1121 nodes and 6090 edges. For the inference, we consider that b and γ are known and we assume a vague prior Gamma(0.01, 0.01) on the unknown parameters α and ϕ = (1 -σ , τ , a). We run 3 parallel MCMC chains with di erent initial values. Each chain starts with 10,000 iterations using our model with only one community where the scores β are xed to 1, which is equivalent to the model of [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF]. We then run 200,000 iterations using our model with p communities. We use ε = 10 -3 as a truncation level for simulating w * 1:p and L = 10 leapfrog steps for the HMC. The step sizes of both the HMC and the random walk MH on (log(1 -σ ), log τ , log a) are adapted during the rst 50,000 iterations so as to target acceptance ratios of 0.65 and 0.23 respectively. The computations take around 2h20 using Matlab on a standard desktop computer. Trace plots of the parameters log α, σ , τ , a and w * = 1 p p k=1 w * k and histograms based on the last 50,000 iterations are given in Figures 4.6 and 4.7. Posterior samples clearly converge around the sampled value. Choosing a threshold value ϵ 10 -3 does not lead to any noticeable change in the MCMC histograms, suggesting that the target distribution of our approximate MCMC is very close to the posterior distribution of interest.

Our model is able to accurately recover the mean parameters of both low and high degree nodes and to provide reasonable credible intervals, as shown in Figure 4.8(a-b) left. By generating 5000 graphs from the posterior predictive we assess that our model ts the empirical power-law degree distribution of the sparse generated graph as shown in Figure 4.8(c) left. We demonstrate the interest of our nonparametric approach by comparing these results to the ones obtained with the parametric version of our model. To achieve this, we x w * k = 0 and force the model to lie in the nite-activity domain by assuming σ ∈ (-∞, 0) and using the prior distribution -σ ∼ Gamma(0.01, 0.01). Note that in this case, the model is equivalent to that of [START_REF] Zhou | In nite edge partition models for overlapping community detection and link prediction[END_REF]. As shown in Figure 4.8(a-b) right, the parametric model is able to recover the mean parameters of nodes with high degrees, and credible intervals are similar to that obtained with the full model; however, it fails to provide reasonable credible intervals for nodes with low degree. In addition, as shown in Figure 4.8(c) right, the posterior predictive degree distribution does not t the data, illustrating the inability of this parametric model to capture power-law behavior.

Real-world graphs

We now apply our methods to learn the latent communities of two real-world undirected simple graphs. The rst network to be considered, the polblogs network [START_REF] Adamic | The political blogosphere and the 2004 US election: divided they blog[END_REF], is the network of the American political blogosphere in February 2005 3 . Two blogs are considered as connected if there is at least one hyperlink from one blog to the other. Additional information on the political leaning of each blog (left/right) is also available. The second network, named USairport, is the network of connections between US airports in 2010 4 .

The sizes of the di erent networks are given in Table 4.1. We consider γ k = 0 is known and we assume a vague prior Gamma(0.01, 0.01) on the unknown parameters α, 1 -σ , τ , a k and b k . We take p = 2 communities for polblogs and p = 4 communities for USairport. We run 3 parallel MCMC chains, each with 10,000 + 200,000 iterations, using the same procedure as used for the simulated data; see Section 4.5.1. Computation times are reported in Table 4.1.

The simulation of w * 1:p requires more computational time when σ ≥ 0 (in nite-activity case). This explain the larger computation times for USairport compared to polblogs.

We interpret the communities based on the minimum Bayes risk point estimate where the cost function is a permutation-invariant absolute loss on the weights w = (w ik ) i=1,...,N α ;k=1,...,p . Let S p be the set of permutations of {1, . . . , p} and consider the cost function

C w, w = min π ∈S p       p k=1 N α i=1 w iπ (k ) -w ik + p k=1 w * π (k ) -w * k      
whose evaluation requires solving a combinatorial optimization problem in O p 3 using the Hungarian method. We therefore want to solve w = arg min 4.10 also shows the weight associated to each of the two community alongside the true left/right class for each blog. The two learned communities, which can be interpreted as "Liberal" and "Conservative", clearly recover the political leaning of the blogs. Figure 4.12 shows the adjacency matrices obtained by reordering the nodes by community membership, where each node is assigned to the community whose weight is maximum, clearly showing the block-structure of this network. The obtained clustering yields a 93.95% accuracy when compared to the ground truth classi cation. Figure 4.11(a) shows the relative community proportions for a subset of the blogs. dailykos.com and washingtonmonthly.com are clearly described as liberal while blogsforbush.com, instapundit.com and drudgereport.com are clearly conservative. Other more moderate blogs such as danieldrezner.com/blog and andrewsullivan.com have more balanced values in both communities. Figure 4.9(a) shows that the posterior predictive degree distribution provides a good t to the data.

For USairport, the four learned communities can also be easily interpreted, as seen in Table 4.3 and Figure 4.13. The rst community, labeled "Hub", represents highly connected airports with no preferred location, while the three others, labeled "East", "West" and "Alaska", are communities based on the location of the airport. In Figure 4.11(b), we can see that some airports have a strong level of a liation in a single community: New York and Miami for "Hub", Charleston/Dunbar and Knoxville for "East", Dallas for "West" and Bethel and Anchorage for "Alaska". Other airports have signi cant weights in di erent communities: Detroit and San Francisco are hubs with strong regional connections, Nashville and Minneapolis share a signi cant number of connections with both East and West of the USA. Anchorage has a signi cant "Hub" weight, while most airports in Alaska are disconnected from the rest of the world as can be seen in Figure 4.12(b). "Alaska" appears as a separate block while substantial overlaps are observed between the "Hub", "East" and "West" communities. Figure 4.9(b) shows that the posterior predictive degree distribution also provides a good t to the data. blogspot.com nicoladellarciprete.blogs.com noguru.tblog.com nomayo.mu.nu nonboxthinking.blogspot.com nykola.com o4tom.blogspot.com officesmileman.com ofthemind.blogspot.com ogresview.blogspot.com okieonthelam.com oldfashionedwhippersnapper.blogspot.com onthewire.blogspot.com opiniontimes.blogspot.com opiniontimes.com oppb.com orthogonian.blogspot.com outsidethebeltway.com pajamaeditors.blogspot.com pajamahadin.com pajamajournalist.blogspot.com palominas.blogspot.com papadoc.net/pinkflamingobar.html pardonmyenglish.com patrickmcclarty.blogspot.com patrickruffini.com patriot-paradox.com patriotblog.com patriotism101.blogspot.com patriotsforbush.com patterico.com pejmanesque.com pennsylvanianinexile.blogspot.com perryvsworld.blogspot.com philomathean.blogs.com piano-tuning.net/blog poeticvalues.blogspot.com poliblogger.com polipundit.com politicalanimals.blogspot.com politicaldogs.org politicalmusings.net politicalpie.modblog.com politicaltracker.com politicaltracker.com/blog/weblog.php politicalvicesquad.blogspot.com poorjustin.blogspot.com poweragerambleson.blogspot.com powerlineblog.com powerpundit.com powervacuum.org presidentreagan.info/discussion professorbainbridge.com prolifeblogs.com propagandamachine.blogspot.com prosandcons.us punditguy.com punditz.journalspace.com qoae.net quante.blogspot.com quibbles-n-bits.com quimundus.modblog.com quimundus.squarespace.com r21online.com r2korn.blogdrive.com rabner.blogspot.com radioequalizer.blogspot.com raincrossblog.com randomjottings.net rant.st ratherbiased.com/news rathergate.com realclearpolitics.com realordeal.blogspot.com rebrand-democrat.txfx.net reckersau.blogspot.com redmindbluestate.blogspot.com rednyc.blogspot.com redstate.org redstatealliance.blogspot.com reggiescorner.blogspot.com regimechangeiran.com renpro.kwcom.net reporterette.com republog.net respublica2004.blogspot.com retiredwarrant.blogdrive.com revone.net/jarhead rfburnhertz.net/rf_blog richmar.blogspot.com right-thinking.com rightmoment.blogspot.com rightonred.net rightperspective.net rightrainbow.com rightstate.blogspot.com rightvoices.com rightwingbastardo.blogspot.com rightwingbob.com rightwingdude.squarespace.com rightwingjournal.blogspot.com rightwingnews.com rightwingthinking.blogspot.com rightwingtroll.blogspot.com rightword.blogspot.com riteturnonly.blogspot.com robbernard.com robertp17.blogspot.com rockpaperscissor.blogspot.com rockpaperscissors.blogs.com rogerlsimon.com romeocat.typepad.com blogspot.com shakingspears.blogspot.com shallows.blogspot.com sharpeblog.cybercatholics.com shortfatcorporal.blogspot.com sickofliberals.blogspot.com sinfactor.blogspot.com sistertoldjah.com sixmeatbuffet.com slantpoint.com slingsnarrows.erudite-absurdity.com slipofthepen.blogspot.com slowplay.com slublog.blogspot.com smarthomeschool.com smashingzero.blogspot.com smellyduck.blogspot.com sneakeasysjoint.com sondrak.com soundingthetrumpet.blogspot.com southernappeal.blogspot.com southernrightwingextremist.blogspot.com southernwatch.blogspot.com spreadingunderstanding.blogspot.com spydrzweb.blogspot.com squiggler.braveblog.com stan-istan.blogspot.com stealthebandwagon.blogspot.com stillmanvalley.org/aoo stix1972.blogspot.com stmonk.blogspot.com stolenthunder.blogspot.com strategicintelligence.blogspot.com streetlog.typepad.com summation.net sweetgrrrl.blogspot.com swfwithattitude.blogspot.com swiftreport.blogs.com tagorda.com talesofawanderingmind.blogspot.com talkshowamerica.blogspot.com techievampire.net/wppol techtrend.com/blog/taranicole templeofjennifer.com/blog tepid-observer.blogspot.com texasbug.blogspot.com thatliberalmedia.com the-torch.com theamericanmind.com thebloghill.blogspot.com thecommonvirtue.com theconservativezone.com thecrankfiles.blogspot.com thedailygoodnews.com thedispatch.blogspot.com thedonovan.com theglitteringeye.com thejessefactor.blogspot.com thelastword.blogdrive.com theliberalslies.blogspot.com themeofabsence.com theneo-progressive.blogspot.com thenudnikfile.blogspot.com thepatriette.com thepaytons.org/essays/considerettes thepoliticalanimal.com thepoliticalteen.net therightblog.blogspot.com therightcoast.blogspot.com therightwingconspiracy.org therinsecycle.com therostra.blogspot.com thesakeofargument.com thespoonsexperience.com thetarpit.blogspot.com thetemplarpundit.blogspot.com theunderscore.blogspot.com theurbangrind.blogspot.com thevaticanofliberalism.com thinkingright.us thisliberal.com thomasgalvin.blogspot.com thomaswharry.com timblair.net timblair.spleenville.com tokenyoungconservative.blogspot.com tom-hanna.org toneofvoice.blogspot.com totels.com/bush04 townhall.com/clog truebluegal.blogspot.com truthlaidbear.com truthliesandcommonsense.blogspot.com truthprobe.blogspot.com tseytlin.blogspot.com tsrightdominion.blogspot.com tuckereskew.typepad.com twentyfirstcenturyrepublican.blogspot.com txfx.net unconventionalwisdom.typepad.com undercaffeinated.com underscorebleach.net/content/jotsheet unfetteredmusings.blogspot.com unusualhabits.blogspot.com usdlaw.blogspot.com variousorthodoxies.com victorhanson.com viewfromaheight.blogspot.com viewfromtonka.blogspot.com viewpointjournal.com vikingpundit.blogspot.com virginiapolitics.blogspot.com vodkapundit.com volokh.com warriorscreed.000k3.com watchandwait.blogspot.com watdanook.blogspot.com web.utk.edu/~agroves wehavesomeplanes.blogspot.com whatsakyer.blogspot.com wholewheatblogger.com wildweasel.blog-city.com williamwebbdotorg.blogspot.com winceandnod.blogspot.com windingroad.typepad.com com 12thharmonic.com/wordpress 750volts.blogspot.com 95theses.blogspot.com abbadabbaduo.blogspot.com aboutpolitics.blogspot.com achingandspinning.blogspot.com ackackack.com adamtalib.blogspot.com adviceforlefty.blogspot.com agonist.org aintnobaddude.com ajbenjaminjr.blogspot.com alicublog.blogspot.com allanjenkins.typepad.com allspinzone.blogspot.com alphapredator.com/wdtgw.htm alternateworlds.blogspot.com althippo.blogspot.com alvintostig.typepad.com americablog.blogspot.com americablog.org americanmuslim.blogs.com americanpolitics.com americansforbayh.blogspot.com amleft.blogspot.com amliberal.com/blog amptoons.com/blog anarchyxero.robfindlay.org andifeelfine.blogspot.com andymatic.com angrybear.blogspot.com angrydesi.typepad.com angryfinger.org angryhomo.blogspot.com annatopia.com/home.html anoldsoul.blogspot.com anonymoussources.blogspot.com answerguy.blogspot.com anybodybutbushyall.blogspot.com anywhichway.net arancaytar.blogspot.com archpundit.com arkansastonight.com askhoudari.blogspot.com astroturf.uni.cc atease.blogspot.com atrios.blogspot.com atrios.blogspot.com/ awards5.tripod.com/tarasblog b-patton.blogspot.com bakshi.us/redskunk barkingdingo.blogspot.com bartcop.com battleground-wisconsin.blogspot.com battlegroundstates.blogspot.com beastsbelly.blogspot.com bentcorner.blogspot.com bettyblog.com billmon.org billsrants.blogspot.com blog.dccc.org blog.dennisfox.net blog.glinka.com blog.johnkerry.com blog.kenlan.net blog.mintruth.com blog.veggiedude.com blog01.kintera.com/dnccblog blog01.kintera.com/emilysblog bloganonymous.com blogforamerica.com blogforarizona.com blogfreeordie.blogspot.com blogitics.com blogs.salon.com/0002874 blogs.salon.com/0003364 blogslut.com blosteam.blogspot.com bluegrassroots.blogspot.com bluelemur.com blueoregon.com bluestateredstate.blogspot.com bodyandsoul.typepad.com boffo.typepad.com boloboffin.blogspot.com bopnews.com boston.com com dneiwert.blogspot.com dogfight04.typepad.com dohiyimir.typepad.com dolphinsdock.com/blog donkey2004.blogspot.com donspoliticalblog.blogspot.com duckdaotsu.blogspot.com dystopia.blog-city.com eastbaykerry.com elayneriggs.blogspot.com elderbearden.blogspot.com electablog.com elemming2.blogspot.com elissa.typepad.com eltcamerica.blogspot.com emergingdemocraticmajority.com emergingdemocraticmajorityweblog.com/donkeyrising emptyisform.com endthenightmare.blogspot.com enemykombatant.blogspot.com ergio.blogspot.com estropundit.blogspot.com etherealgirl.blogspot.com fafblog.blogspot.com com hotflashreport.com howienfriends.blogspot.com hugozoom.blogspot.com ibe.blogspot.com ibrutus.com iddybud.blogspot.com idiosyncratictendencies.com idlehandsmag.com/yellowdog04 iflipflop.com ignatz.blogspot.com ihatepatrobertson.com ilovecynics.com insanepreschoolmom.blogspot.com interestingtimes.blogspot.com interestingtimes.typepad.com ironmouth.com irregulartimes.com/blogger.html islanddave.blogspot.com itlookslikethis.blogeasy.com ivotedforgeorge.com iwantmycountryback.org j-bradford-delong.net/movable_type jadbury.com jadbury.com/blog jadedreality.blogspot.com jameswolcott.com janm.blogspot.com jbcougar.blogspot.com jdeeth.blogspot.com jeremybrendan.blogspot.com jetage.blogspot.com jewssansfrontieres.blogspot.com jimgilliam.com jimtreacher.com jinkythecat.blogspot.com jmbzine.com joebrent.blogspot.com john.hoke.org johnmccrory.com johnnynobody.blogspot.com journals.aol.com/breuvers/madashellnotgoingtotakeitanymore juancole.com julietterossant.com/superchefblog/superchefblog.html juliusblog.blogspot.com justmark.com karlhenderson.blogspot.com karmicsoup.blogspot.com kcdems.blogspot.com kensain.com kerryforpresident2008.blogspot.com kicktheleftist.blogspot.com kiosan.blogharbor.com kippsblog.com kurtkk.blogspot.com kydem.blogspot.com lastdaysoftherepublic.fatoprofugus.net lawdork.blogspot.com leanleft.com left2right.typepad.com lefterer.com lefti.blogspot.com leftinthereign.blogspot.com leftthought.blogspot.com lefttimes.com leftwingnation.com lendmesomesugar.blogs.com/shut_up_already lennonreport.blogspot.com leonards-digest.blogspot.com liberalangst.org liberalavenger.com liberaleric.blogspot.com liberaloasis.com liberalreview.blogspot.com liberalthunderdome.blogspot.com lightupthedarkness.org lightupthedarkness.org/blog/default.asp limericksavant.blogspot.com liquidlist.com livejournal.com/users/hoptkov livejournal.com/users/jmhm loadedmouth.com lorenjavier.blogspot.com loud-liberal.blogspot.com loveamericahatebush.com lowrentrat.blogdrive.com ltobs.blogspot.com ludis.blogspot.com ludovicspeaks.typepad.com ludovicspeaks.typepad.com/real_deal madkane.com/notable.html maggiespants.co.uk mahablog.com marcbrazeau.blogspot.com margaretcho.com/blog/blog.htm margieburns.com markadams.blogdrive.com markarkleiman.com markschmitt.typepad.com/decembrist markwarnerforpresident2008.blogspot.com maruthecrankpot.blogspot.com massachusetts-liberal.com mathewgross.com mathewgross.com/blog matthewyglesias.com maultasch.us maxspeak.org/mt mayflowerhill.blogspot.com mcwil.blogspot.com meanspirit.blogspot.com meateatingleftist.com mediajunkie.com/edgewise mediaprima.com/nv1962 messengerpuppet.com/blog metropol47.blogspot.com michael124.blogspot.com michaelberube.com michaelphillips.blogspot.com mickikrimmel.com/redcarpet midguard.blogspot.com minagahet.blogspot.com mirocat.com misschin.bloggage.com mixtersmix.blogspot.com montages.blogspot.com moxiegrrrl.com mrleft.org msnbc.msn.com/id/3449870 mstabile.blogspot.com mydd.com myleftbrain.com myleftthoughts.blogspot.com mysterypollster.com/main nastyboys.blogspot.com nathancallahan.com nathannewman.org/log nationalreview.com/frum/frum-diary.asp ndnblog.org nearouterheaven.blogspot.com nebursworld.blogspot.com needlenose.com nerofiddled.blogspot.com netpolitik.blogspot.com netweed.com/postmodernanarchist newappeal.blogspot.com newdemocrat.blogdrive.com newdonkey.com newleftblogs.blogspot.com nielsenhayden.com/electrolite nielsenhayden.com/makinglight njfordemocracy.org node707.com nofearoffreedom.blogspot.com nomoremister.blogspot.com norbizness.com noseyonline.com nosmallplans.com/rants notbush.com notgeniuses.com nycitystoop.com obamablog.com obsidianwings.blogs.com oddhours.blogspot.com offthekuff.com/mt oipp.blogspot.com oliverwillis.com one38.org openeyesmemo.com orient-lodge.com ospolitics.org oxblog.blogspot.com pacdaily.com pacificviews.org pandagon.net parabasis.typepad.com patriotboy.blogspot.com pattymurray.com/blog.php paulchasman.com peacegarden.blogspot.com penheaded.blogspot.com pennywit.com/drupal permanentred.com peskytherat.com/pesky phillybri.blogspot.com philoponia.blogspot.com philosophers-stone.blogspot.com philvbblog.blogspot.com phoblographer.com pinkofeministhellcat.typepad.com/pinko_feminist_hellcat planetdave.com/blogs.php3?mid=1 politicalmonitor.us/blog politicalstrategy.org politicalthought.net politicalwire.com politics.feedster.com politicswithrichard.blogspot.com polizeros.com pollsterseek.blogspot.com polstate.com portapulpit.com praguewriter.typepad.com presidentboxer.blogspot.com prestoncaldwellblog.blogspot.com profgoose.blogspot.com progressiveink.com progressivesociety.com/blog proponentofreason.blogspot.com prospect.org/weblog pudentilla.blogspot.com punditician.blogspot.com purplestates.blogspot.com qando.net question-dean.blogspot.com radgeek.com radikal_papi.pitas.com radio.weblogs.com/0131587/categories/flush raedinthemiddle.blogspot.com reachm.com/amstreet readingpost.com realitybasednation.com red-harvest.blogspot.com religiousleft.blogspot.com republicoft.typepad.com resistoppression.blogspot.com restoreamerica.blogspot.com retrogrouch.net rhetoricrhythm.blogspot.com righthandthief.blogspot.com rising-hegemon.blogspot.com risinghegemon.blogspot.com rittenhouse.blogspot.com riverbendblog.blogspot.com roadtosurfdom.com robot-invasion.com robschumacher.blogspot.com rogerailes.blogspot.com rooksrant.com rowhouselogic.com roxanne.typepad.com rudepundit.blogspot.com ruminatethis.com s88172659.onlinehome.us/spockosbrain.html sadlyno.com saveoursenate.blogspot.com sccdp.org/blog.php schadelmann.com scoobiedavis.blogspot.com scottcsmith.net scripting.com scrutinyhooligans.blogspot.com seeingtheforest.com seetheforest.blogspot.com sethdmichaels.com shakespearessister.blogspot.com shamelessantagonist.blogspot.com sharedthought.com/weblog shininglight.us shoegal.modblog.com shotofpolitics.blogspot.com shrillblog.blogspot.com simbaud.blogspot.com simplyappalling.blogspot.com smirkingchimp.com smithersmpls.com snunes.blogspot.com someonetakethewheel.blogspot.com soonerthought.com southknoxbubba.net/skblog spacedog26.blogspot.com spectatorsport.blogspot.com stagefour.typepad.com/commonprejudice stalinism.com/shot-by-both-sides stcfoundation.blogspot.com stephenbates.com/yellowdoggereldemocrat stevecopy.blogharbor.com stevegilliard.blogspot.com steveguy.me.uk stevemacek.blogspot.com stillfighting.blogspot.com stitt.blogspot.com strangedoctrines.typepad.com strangesemantics.blogspot.com suburbanguerrilla.blogspot.com swamiuptown.com swingstateproject.com takebackthemedia.com talkingpointsmemo.com talkleft.com tallone.org tbogg.blogspot.com teenageenthusiast.blogspot.com tesibria.typepad.com/democracy_is_coming thatcoloredfellasweblog.bloghorn.com thatgoodnight.com the-goddess.org the-hamster.com theaggpro.blogspot.com theagitator.blogspot.com theangryliberal.blogspot.com theantibush.org theapologist.blogspot.com theblogwarrior.blogspot.com theblueview.blogspot.com thecarpetbaggerreport.com thecore4.com thefulcrum.blogspot.com theleftcoaster.com thelonedem.com thelucideye.blogspot.com thepeach.blogspot.com thepoorman.net theradiomansays.blogspot.com therogueangel.com/blog thesnooter.blogspot.com thetalentshow.org thetalkingdog.com thewashingtonnote.com theworldaroundyou.com thewritewing.blogspot.com theyetimn.blogspot.com thingsasitis.net think2004.com thinkingrocks.blogspot.com thirdredeye.blogspot.com thislousytshirt.net thismodernworld.com thomasblog.typepad.com/bloggg thunewatch.squarespace.com tinylittledots.com tobyemden.blogspot.com tomburka.com tomcoburnisabigfatjerk.blogspot.com tomherod.blogspot.com toteota.blogspot.com trainorphans.org translucence.org travalex.blogspot.com tristero.blogspot.com trueconservative.typepad.com truedemocrat.blogspot.com turnpikefeminist.com turnspit.com uberdude.blogspot.com uggabugga.blogspot.com unodemocrats.com/blog upper-left.blogspot.com urbandemocracy.blogspot.com urbanecoinc.com/wordpress1 usademocrazy.blogspot.com usliberals.about.com vernsblog.thegillfamily.us:8180 virginiaprogressive.blogspot.com vocis.com

Conclusion

We rst take a few steps back to recap the important ideas that were developed in this thesis. Our point is to emphasize that the proposed frameworks are simple, elegant and exible. In the end, we open up some perspectives.

Summary

In Part 1, we have focused on recommender systems with explicit feedback. After an overview on the di erent approaches: content-based, demographic-based, collaborative and hybrid ltering, we have concentrated on the collaborative ltering approach which solely exploits the incomplete user-item ratings matrix. To solve this problem, we have proposed an adaptive spectral regularization algorithm for low-rank matrix completion. The low-rank assumption has a simple interpretation: each user and item can be described by a small set of latent features and the rating of user i for item j can be explained by the matching between their associated features. The origin of our work is to give a probabilistic interpretation to the nuclear norm regularized problem where the prior distribution on the set of singular values can now be replaced by more exible choices. In particular, a hierarchical prior is very useful for several reasons. Each singular value can be governed by its own regularization parameter which is easy to interpret. The parameters are considered as latent variables and are automatically adapted thanks to a top-level prior distribution. Our construction allows to bridge the gap between the convex nuclear norm penalty and the rank penalty. The resulting problem can be easily decomposed into two iterative steps using an EM algorithm. The E step can be obtained analytically for a family of suitably chosen distributions. The M step consists in a weighted soft-thresholded singular value decomposition which penalizes less heavily the higher singular values, hence reducing the bias of the soft-thresholding rule. We have also shown evidence that the predictions are improved in real-world applications, despite the non convexity of our penalty. However, in this rst part, we totally ignored the implicit feedback given by the distribution of the entries in the incomplete matrix.

In Part 2, we have focused on proposing a novel class of network models. Our development concentrates on simple networks but it can also be applied to a bipartite graph which can represent implicit feedback of a recommender system. Our objective was to capture the sparsity and power-law behavior as well as to obtain an interpretable structure of the network. To this aim, we resort to a Bayesian nonparametric approach which is recent in the eld of network modeling. The graph is represented as an exchangeable point process and the nodes are considered as realizations of a completely random measure. As such, the model can encompass a sparse regime when the completely random measure is in nite-activity. We furthermore allow an overlapping community structure by using a multivariate random measure. Similarly to low-rank models for recommender systems, we suppose that each node i can be described by a small set of latent features which are here nonnegative parameters indicating the degrees of a liation of the node to the latent communities. In particular, our construction builds on compound completely random measure and we propose a suitable choice of base measure and score distribution. This choice allows us to derive a scalable Markov chain Monte Carlo algorithm to perform posterior inference on both the feature parameters and their hyperparameters. Our experiments show that the model is able to capture the power-law degree distributions of real-world graphs as well as to discover a meaningful community structure.

Perspectives

In this thesis, we have developed methods which solely exploit explicit feedback of recommender systems or the connections of networks. However, in many cases, additional information is available and the models can be extended in several directions.

First, the objects of interest (users, items or nodes) generally come with metadata like genre, age, location or textual content. In the recommender systems literature, several hybrid ltering models have been proposed to exploit these attributes and circumvent the cold-start problems. For instance, by placing priors on user and item factor matrices which depend on corresponding side information [START_REF] Agarwal | Regression-based latent factor models[END_REF][START_REF] Park | Hierarchical Bayesian matrix factorization with side information[END_REF][START_REF] Kim | Scalable variational Bayesian matrix factorization with side information[END_REF], or by treating these observed features similarly to the latent ones [START_REF] Porteous | Bayesian matrix factorization with side information and Dirichlet process mixtures[END_REF]. Other models include the content-based Poisson factorization of [START_REF] Gopalan | Content-based recommendations with Poisson factorization[END_REF] which combines a topic model with collaborative ltering in a single uni ed Bayesian model. Also note the model of [START_REF] Menon | A log-linear model with latent features for dyadic prediction[END_REF] for dyadic data which includes networks and recommender systems and allows to incorporate side information.

Another direction of extension is to consider recommender systems and networks as dynamic systems where ratings and connections can change over time. Therefore, it is important to build models which take this evolution into account; see e.g. the survey of [START_REF] Campos | Time-aware recommender systems: a comprehensive survey and analysis of existing evaluation protocols[END_REF] on time-aware recommender systems. Like [START_REF] Palla | Bayesian nonparametrics for sparse dynamic networks[END_REF], we can extend our sparse network model with overlapping communities by supposing that the latent a liation parameters are governed by a time-varying vector of completely random measures.

The time-aware recommender systems can also be treated as a particular cases of contextaware recommender systems [START_REF] Adomavicius | Context-aware recommender systems[END_REF] where a given context is associated to each observed user-item pair. In this case, the data is no longer represented by a matrix but by a 3-way tensor where the third dimension is the context. In this regard, a lot of works now concentrate on the problem of tensor factorization [START_REF] Karatzoglou | Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative ltering[END_REF][START_REF] Pragarauskas | Temporal collaborative ltering with bayesian probabilistic tensor factorization[END_REF] and low-rank tensor completion [START_REF] Gandy | Tensor completion and low-n-rank tensor recovery via convex optimization[END_REF][START_REF] Liu | Tensor completion for estimating missing values in visual data[END_REF] and we believe our approach could be extended in that direction.

Lastly, it would be interesting to investigate the properties of the novel class of network models that we proposed, e.g. its clustering coe cient among others. In addition, the number of latent communities is here considered xed but it should ideally be learned from the data. This point remains to be studied more deeply.

• Todeschini, A. and Caron, F. (2015). Approche bayésienne non paramétrique pour la factorisation de matrice binaire à faible rang avec loi de puissance. 47èmes Journées de Statistique de la SFDS, Rennes. • Todeschini, A. and Genuer, R. (2015). Compétitions d'apprentissage automatique avec le package R rchallenge. 47èmes Journées de Statistique de la SFDS, Rennes.

Invited talks in international conferences A.1. Expectation-maximization algorithm

ϕ (t ) ϕ (t+1) ϕ L(ϕ; X ) G (ϕ, ϕ (t ) ) Figure A.1: M-step of the EM algorithm: maximizing the auxiliary function G (ϕ, ϕ (t ) ) ≤ L(ϕ; X ) w.r.t. ϕ guarantees that L(ϕ (t+1) ; X ) ≥ L(ϕ (t ) ; X ) where ϕ (t+1) = arg max ϕ G (ϕ, ϕ (t ) ). Proof. First prove that Q (ϕ, ϕ * ) = L(ϕ; X ) + H (ϕ, ϕ * ): Q (ϕ, ϕ * ) = E Z [L(ϕ; X , Z )|X , ϕ * ] = E Z [log p(X |ϕ) + log p(Z |X , ϕ)|X , ϕ * ] = log p(X |ϕ) + E Z [log p(Z |X , ϕ)|X , ϕ * ] = L(ϕ; X ) + H (ϕ, ϕ * )
and trivially obtain G (ϕ * , ϕ * ) = L(ϕ * ; X ). Then use Jensen's inequality to show that G minorizes L:

G (ϕ, ϕ * ) -L(ϕ; X ) = Q (ϕ, ϕ * ) -H (ϕ * , ϕ * ) -L(ϕ; X ) = L(ϕ; X ) + H (ϕ, ϕ * ) -H (ϕ * , ϕ * ) -L(ϕ; X ) = H (ϕ, ϕ * ) -H (ϕ * , ϕ * ) = E Z [log p(Z |X , ϕ)|X , ϕ * ] -E Z [log p(Z |X , ϕ * )|X , ϕ * ] = E Z log p(Z |X , ϕ) p(Z |X , ϕ * ) |X , ϕ * ≤ log E Z p(Z |X , ϕ) p(Z |X , ϕ * ) |X , ϕ * ≤ log Z p(Z |X , ϕ) p(Z |X , ϕ * ) p(Z |X , ϕ * )dZ ≤ log Z p(Z |X , ϕ)dZ ≤ 0
Maximizing the auxiliary function G w.r.t. ϕ (or equivalently maximizing Q), which is a lower bound for L, increases the likelihood at each iteration as illustrated in

A.2 Proofs

Proof of Eq. (2.5).

p(d i ) = ∞ 0 Exp(d i ; γ i ) Gamma(γ i ; a, b)dγ i = ∞ 0 γ i exp(-γ i d i ) b a Γ(a) γ a-1 i exp(-bγ i )dγ i = b a Γ(a) ∞ 0 γ a i exp(-(d i + b)γ i )dγ i = b a Γ(a) Γ(a + 1) (d i + b) a+1 = ab a (d i + b) a+1
Proof of Eq. (2.8).

Q (Z , Z * ) = E [log p(X , Z , γ )|Z * , X ] = E [log (p(X |Z )p(Z |γ )p(γ )) |Z * , X ] = C 2 + log p(X |Z ) + E [log p(Z |γ )|Z * ] = C 2 - 1 2σ 2 X -Z 2 F + r i=1 E log p(d i |γ i )|d * i = C 2 - 1 2σ 2 X -Z 2 F - r i=1 E γ i d i |d * i = C 2 - 1 2σ 2 X -Z 2 F - r i=1 E γ i |d * i d i
where C 2 , C 2 and C 2 are constant terms not depending on Z .

A.2. Proofs

Proof of Eq. (2.10).

ω * i = E[γ i |d * i ] = ∞ 0 γ i p(γ i |d * i )dγ i = ∞ 0 γ i p(d * i |γ i )p(γ i )dγ i p(d * i ) = ∞ 0 γ i γ i exp(-γ i d * i )p(γ i )dγ i p(d * i ) = -∂ ∂d * i ∞ 0 γ i exp(-γ i d * i )p(γ i )dγ i p(d * i ) = ∂ ∂d * i -log p(d * i ) = ∂ ∂d * i pen(d * i )
Proof of Eq. (2.14).

Q (Z , Z * ) = E log p(P Ω (X ), P ⊥ Ω (X ), Z , γ )|Z * , P Ω (X )

= C 3 -1 2σ 2 E P Ω (X ) + P ⊥ Ω (X ) -Z = C 3 -1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F + E P ⊥ Ω (X ) -P ⊥ Ω (Z )

2 F |Z * , P Ω (X ) - r i=1 E[γ i |d * i ]d i = C 3 - 1 2σ 2 P Ω (X ) -P Ω (Z ) 2 F + P ⊥ Ω (Z * ) -P ⊥ Ω (Z ) 2 F - r i=1 E[γ i |d * i ]d i = C 3 - 1 2σ 2 P Ω (X ) + P ⊥ Ω (Z * ) -Z 2 F - r i=1 E[γ i |d * i ]d i
where C 3 and C 3 are constant terms not depending on Z .

Proof of Eq. (2.16). Note that when (i, j) ∈ Ω, x ij |z ij , ij follows a truncated normal distribution, right-truncated at zero if ij = -1 and left-truncated at zero if ij = 1. We derive the case ij = -1 below and the derivation for ij = 1 is similar.

E[x ij |z ij , ij = -1] = 0 -∞ x φ
x-z i j σ σ Φ -

z i j σ dx = 1 Φ - z i j σ - z i j σ -∞ (z ij + σu)φ (u) du = 1 Φ - z i j σ       z ij - z i j σ -∞ φ (u) du + σ - z i j σ -∞ uφ (u) du       = 1 Φ - z i j σ       z ij Φ - z ij σ + σ - z i j σ -∞ u √ 2π e -u 2 2 du       = z ij + σ -1 √ 2π e -u 2 2 - z i j σ -∞ Φ - z i j σ = z ij + σ [-φ(u)] - z i j σ -∞ Φ - z i j σ = z ij - σφ z i j σ Φ - z i j σ
Proof of Eq. (2.17

= C 4 - 1 2σ 2 E X -Z 2 F |Z * , P Ω (Y ) - r i=1 E[γ i |d * i ]d i = C 4 - 1 2σ 2 E [X |Z * , P Ω (Y )] -Z 2 F - r i=1 E[γ i |d * i ]d i = C 4 - 1 2σ 2 X * -Z 2 F - r i=1 E[γ i |d * i ]d i
where C 4 is a constant term not depending on Z and the matrix X * is de ned as Proof of (3.17).

x * ij =              z * ij + ij σφ z * i j σ Φ i j z * i j σ if (i, j) ∈ Ω z * ij otherwise.
(µ) µ ∈ [0, ∞) x ∈ N µ x e -µ x! E [X ] = µ, Var [X ] = µ N (µ, σ 2 ) µ ∈ R, σ > 0 x ∈ R 1 σ √ 2π e -1 2 ( x -µ σ ) 2 E [X ] = µ, Var [X ] = σ 2 Lognormal(µ, σ 2 ) µ ∈ R, σ > 0 x > 0 1 xσ √ 2π e -1 2 log x -µ σ 2 log(X ) ∼ N (µ, σ 2 ) iGauss(δ, γ ) δ > 0, γ > 0 x > 0 δe δγ √ 2π x -3 2 e -1 2 (δ 2 x -1 +γ 2 x ) E [X ] = δ γ ,
M (m 1 ,...,m p ) (t 1 , . . . , t p ) = The intractable high dimensional integral is therefore approximated by a simple nite sum.

MCMC algorithms. MCMC is a class of algorithms where the samples are generated from a Markov chain ϕ (1) → ϕ (2) → . . . → ϕ (t ) → ϕ (t+1) → . . . which explores the space Φ and should admit the target distribution π (ϕ) as equilibrium distribution, what can be ensured by verifying the detailed balance condition.

Once equilibrium is reached, the generated samples will serve as a Monte Carlo approximation of the target. In practice, the "burn-in" samples are discarded and the chain is thinned to mitigate autocorrelation.

Metropolis-Hastings algorithm. The Metropolis-Hastings algorithm (MH, [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF][START_REF] Hastings | Monte Carlo sampling methods using Markov chains and their applications[END_REF] is the most popular MCMC method. At each iteration t, it samples a new candidate value ϕ from a proposal distribution q(•|ϕ (t-1) ) and accepts or reject it with acceptance rate α = min 1, π ( ϕ)q( ϕ |ϕ (t-1) )

π (ϕ (t-1) )q(ϕ (t-1) | ϕ) .

The procedure is summarized in Algorithm 8. Initialize ϕ (0) . Then, at iteration t = 1, 2, . . .

• Sample a candidate from the proposal distribution ϕ ∼ q(•|ϕ (t-1) ).

• Compute the acceptance rate α (t ) = min 1, π ( ϕ)q(ϕ (t-1) | ϕ) π (ϕ (t-1) )q( ϕ |ϕ (t-1) ) .

• Sample u (t ) ∼ U (0, 1).

-If u (t ) < α (t ) , accept the candidate and set ϕ (t ) = ϕ otherwise, reject it and set ϕ (t ) = ϕ (t-1) .

In the simplest case, the proposal is a symmetric kernel such that q( ϕ |ϕ) = q(ϕ | ϕ) and the acceptance rate simpli es to α = min 1, π ( ϕ) π (ϕ (t -1) ) . We see that the algorithm always accepts a candidate which increases the target, while a candidate which decreases the target is not automatically rejected but is given a chance to be accepted which is proportional to the ratio.

The e ciency of the algorithm depends on the choice of the proposal distribution. A common practice in MH algorithms is to use random-walk proposals which blindly explore the state-space using local moves with a certain exploration stepsize. This might result in slow convergence and auto-correlated samples.

Gibbs sampler. Consider a d-dimensional variable ϕ = (ϕ 1 , . . . , ϕ d ). The Gibbs sampler algorithm [START_REF] Geman | Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images[END_REF] Algorithm 9: Gibbs sampling algorithm. Initialize ϕ (0) . Then, at iteration t = 1, 2, . . ., for k = 1, . . . , d

• Sample the k-th component of ϕ from its full conditional distribution

ϕ (t ) k ∼ π ϕ k |ϕ (t ) -k
where ϕ (t ) -k = ϕ (t ) 1 , . . . , ϕ (t ) k-1 , ϕ (t-1) k+1 , . . . , ϕ (t-1) d .

This algorithm is particularly useful when the target distribution comes from a graphical model, which generally allows to simplify the full conditional distributions by taking into account local dependencies. Instead of depending on all the remaining variables, each component only depends on its children and parents in the graph. The Gibbs sampler can also be viewed as a special case of MH algorithm with a particular choice of proposal distribution such that the acceptance rate is 1. However note that, especially when a full conditional does not have any closed-form expression, it is possible to use other proposal distributions and perform a step of MH within the Gibbs sampler. Finally, when the components are highly correlated, conditioning on all the other components might be too restrictive and the Gibbs sampling strategy will have a very slow exploration.

Hamiltonian Monte Carlo. Hamiltonian systems are represented by a d-dimensional position vector q, and a d-dimensional momentum vector p (mass times velocity in physical systems) and their evolution is governed by the Hamiltonian equations

dq k dt = ∂H ∂p k dp k dt = - ∂H ∂q k
Algorithm 10: Hamiltonian Monte Carlo algorithm with M = I d , using L leapfrog steps with a stepsize of ε. For simplicity of exposure, we omit indices k = 1, . . . , d.

Initialize the state q (0) . Then, at iteration t = 1, 2, . . .

• Sample new momentum variables

p ∼ N (0 d , I d ) .

• Simulate L leapfrog steps of the discretized Hamiltonian dynamics via q (0) = q (t-1) p (0) = pε 2 U (q (t-1) )

and for = 1, . . . , L -1 q ( ) = q ( -1) + ε p ( -1) p ( ) = p ( -1) -εU ( q ( ) )

and nally set q = q (L-1) + ε p (L-1) p = -p (L-1) -ε 2 U ( q) .

• Compute the acceptance rate α (t ) = min 1, e U (q (t -1) )-U ( q)+K (p)-K ( p) .

• Sample u (t ) ∼ U (0, 1).

-If u (t ) < α (t ) , accept the candidate and set q (t ) = q otherwise, reject it and set q (t ) = q (t-1) .

Step 2: Update (w i1 , . . . , w ip ), i = 1, . . . , N α given the rest using HMC. We use a HMC update for w i0 , β i1 , . . . , β ip i=1,...,N α via an augmented system with momentum variables p = p i0 , p i1 , . . . , p ip i=1,...,N α . See [START_REF] Neal | MCMC using Hamiltonian dynamics[END_REF] for an overview. Let L ≥ 1 be the number of leapfrog steps and ε > 0 the stepsize. For conciseness, let denote q = log w i0 , log β i1 , . . . , log β ip i=1,...,N α , U (q) the negative log-posterior + terms not depending on w 0 or β and U (q) = -∇ q log p (q|rest) q its gradient with components for i = 1, . . . , N α U i0 (q) = ∂U (q) d (log

U (q) = -log p (q|rest) = -       N α i=1 (m i -σ ) log w i0 -τw i0       -      
w i0 ) = -m i + σ + w i0        τ + 2 p k=1 β ik w * k + N α j=1 w j0 β jk        U ik (q) = ∂U (q) d (log β ik ) = -m ik -a k + β ik        b k + 2w i0 w * k + N α j=1 w j0 β jk        , k = 1, . . . , p.
The algorithm proceeds by rst sampling momentum variables as p ∼ N 0, I N α ×(p+1) .

The Hamiltonian proposal is obtained by the following leapfrog algorithm (for simplicity of exposure, we omit indices i = 1, . . . , N α and k = 1, . . . , p). Simulate L steps of the discretized Hamiltonian via

q (0) = q p (0) = p - ε 2 U (q)
and for = 1, . . . , L -1 q ( ) = q ( -1) + ε p ( -1) p ( ) = p ( -1) -εU ( q ( ) )

and nally set q = q (L-1) + ε p (L-1) p = -p (L-1) -ε 2 U ( q) .

Accept the proposal q, p with probability min(1, r ) where For simple graphs (without self-loops), the gradient components are We use a MH step with proposal distribution q( α, ϕ, w * 1:p |α, ϕ, w * 1:p ) = q( σ |σ )q( τ |τ )

U i0 (q) = -m i -σ + w i0        τ + 2
      p k=1 q( a k |a k )q( b k |b k )q( γ k |γ k )       × q( α | ϕ,
( γ k -γ k ) ×       Γ(1 -σ ) Γ(1 -σ ) p k=1 b a k k Γ(a k ) b a k k Γ( a k )       N α       N α i=1 w σ -σ i0             p k=1 N α i=1 β a k -a k ik       × e -( τ -τ ) Nα i=1 w i0 - p k=1 ( b k -b k ) Nα i=1 β ik - p k=1 ( w 2 * k -w 2 * k ) .
Choice of the proposal for (w * 1 , . . . , w * p ). Note that in the general case, the density p(w * 1:p |α, ϕ) = * α (w * 1:p ; ϕ) does not admit any analytic expression. We therefore use a speci c proposal based on exponential tilting of * α (w * 1:p ; ϕ) that alleviates the need to evaluate this pdf in the MH ratio. where U is the uniform distribution on the unit sphere S p-1 . Then if ρ 0 is a regularly varying Lévy measure with exponent σ ∈ (0, 1), i.e. For w 0 ∈ (0, ε ), we have κb ε w 0 ≥ κb ε ε = ε -σ /2 (1/ε ) > κ 2 ε -σ /4 for ε small enough as t δ (t ) → 0 for any δ > 0 as t → ∞. So for ε small enough

I ε > ε 0 β 1:p >κ 2 ε -σ /4

C.6 Technical lemmas

Proposition 10. Let ν be a Lévy measure de ned by Eq. (3.8) and (4.10) and ψ be its multivariate Laplace exponent. Assume that ρ 0 is a regularly varying function with exponent σ ∈ (0, 1):

ρ 0 x↓0 ∼ x -σ (1/x ).
C.6. Technical lemmas Then ψ is (multivariate) regularly varying [START_REF] Resnick | Extreme values, regular variation and point processes[END_REF], with exponent σ . More precisely, for any (x 1 , . . . (1 -e -cw )ρ (dw ) < ∞ for any c > 0. Lemma 12. [START_REF] Gnedin | Notes on the occupancy problem with in nitely many boxes: general asymptotics and power laws[END_REF][START_REF] Bingham | Regular variation[END_REF]. Let ρ be a Lévy measure with regularly varying tail Lévy intensity

3. 1

 1 Examples of one-dimensional and two-dimensional Poisson processes. . . . . 3.2 Example of a Poisson random measure on [0, 1]. . . . . . . . . . . . . . . . . . 3.3 Illustration of the thinning strategy. . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Illustration of the adaptive thinning strategy. . . . . . . . . . . . . . . . . . . . 3.5 Example of a CRM on [0, 1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Representation of an undirected graph via a point process Z . . . . . . . . . . . 4.2 An example of the restriction on [0, 1] 2 of the two atomic measures D 1 and D 2 , the corresponding multiview directed multigraphs and corresponding undirected graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 An example of the product measuresW k ×W k , a draw of the directed multigraph measures D k | W k and corresponding undirected measure Z . . . . . . . . . . . 4.4 Graph sampled from our particular model with three latent communities. . . . 4.5 Empirical analysis of the properties of CCRM based graphs. . . . . . . . . . . 4.6 MCMC trace plots and histograms of parameters log α, σ and τ . . . . . . . . .

Figure 1 :

 1 Figure 1: Network: example of connections between objects represented (a) as an undirected simple graph and (b) as a symmetric adjacency matrix.

Figure 2 :

 2 Figure 2: Recommender system: example of ratings given by users to items represented (a) as a labeled bipartite graph and (b) as a matrix. Like/dislikes are represented as (a) blue/red solid lines and (b) blue/red thumbs up/down. Missing data are represented by (a) dotted lines and (b) exclamation marks.

Figure 1 . 1 :

 11 Figure 1.1: Popularity of items in decreasing order. (a) Stars of movies in the MovieLens-1M dataset available online at http://www.grouplens.org/node/73. (b) Sales of a french e-commerce website by category of product. On the left (blue), the popular items represent 80% of the total stars/sales. On the right (red), the long tail items represent 20% of the total stars/sales.

Figure 1 . 2 :

 12 Figure 1.2: Recommender systems approaches with emphasis on collaborative ltering methods.

Figure 2 . 3 :

 23 Figure 2.3: Marginal distribution p(d i ) with a = b = β for di erent values of the parameter β. The distribution becomes more concentrated around zero with heavier tails as β decreases. The case β → ∞ corresponds to an exponential distribution with unit rate.

Figure 2 . 4 :

 24 Figure 2.4: Top: manifold of constant penalty, for a symmetric 2 × 2 matrix Z = [x, ; , z] for (a) the nuclear norm, (b-c) hierarchical adaptive spectral penalty with a = b = β (b) β = 1 and (c) β = 0.1, and (d) the rank penalty. Bottom: contour of constant penalty for a diagonal matrix [x, 0; 0, z], where one recovers the classical (e) lasso, (f-g) hierarchical lasso and (h) 0 penalties.

Figure 2 . 5 :

 25 Figure 2.5: Thresholding rules on the singular values d i of X for the soft thresholding rule (λ = 1), and hierarchical adaptive soft thresholding algorithm with a = b = β.

Figure 2 . 7 :

 27 Figure 2.7: Test error w.r.t. the rank obtained by varying the value of the regularization parameter λ. Results on simulated data are given for (a) a rank 10 complete matrix with SNR=1, (b) a rank 5 matrix with 50% missing entries and SNR=1 and (c) a rank 5 matrix with 80% missing entries and SNR=10.

Figure 2 . 8 :

 28 Figure 2.8: Boxplots of the test errors (left) and ranks (right) obtained over 50 replications on simulated data with true rank q = 5 and (a) 50% missing entries with SNR=1 and (b) 80% missing entries with SNR=10.

Figure 2

 2 Figure 2.9: NMAE on the test set of the (a) Jester 1, (b) Jester 2 and (c) Jester 3 datasets w.r.t. the rank obtained by varying the value of the regularization parameter λ.

Figure 3 . 1 :

 31 Figure 3.1: Examples of (a) one-dimensional and (b) two-dimensional Poisson processes.

Figure 3 . 2 :

 32 Figure 3.2: Example of a Poisson random measure on [0, 1].

Figure 3 . 4 :

 34 Figure 3.3: Illustration of the thinning strategy. ν (s)

Figure 3 . 5 :

 35 Figure 3.5: Example of a CRM on [0, 1].

  dw p where κ = σ + p k=1 a k and K is the modi ed Bessel function of the second kind.

  Figure 4.1: Representation of an undirected graph via a point process Z . Each node i is embedded in R + at some location θ i and is associated with a set of positive attributes (w i1 , . . . , w ip ). An edge between nodes θ i and θ j is represented by a point at locations (θ i , θ j ) and (θ j , θ i ) in R 2+ .

  (dw 1 , . . . , dw p ) < ∞.(4.7)

Figure 4 . 2 :

 42 Figure 4.2: An example of (a) the restriction on [0, 1] 2 of the two atomic measures D 1 and D 2 , (b) the corresponding multiview directed multigraphs (top: view 1; bottom: view 2) and (c) corresponding undirected graph.

Figure 4 . 3 :

 43 Figure 4.3: An example, for p = 2, of (a) the product measures W k × W k , (b) a draw of the directed multigraph measures D k | W k ∼ Poisson(W k × W k ) and (c) corresponding undirected measure Z = ∞ i=1

Figure 4

 4 Figure 4.4: Graph sampled from our particular model with three latent communities, identi ed by colors red, green, blue. For each node, the intensity of each color is proportional to the value of the associated weight in that community. Pure red/green/blue color indicates the node is only strongly a liated to a single community. A mixture of those colors indicates balanced a liations to di erent communities. Graph generated with the software Gephi[START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF].

  The proof is given in Appendix C.1.Construction based on CCRMs. For the CCRM Lévy measure (4.10), the sparsity properties are solely tuned by the base Lévy measure ρ 0 . Ignoring trivial degenerate cases for the score distribution F , it is easily shown that the CCRM model de ned by (4.10) is in niteactivity i the Lévy measure ρ 0 veri es

Figure 4 . 5 :

 45 Figure 4.5: Empirical analysis of the properties of CCRM based graphs generated with parameters p = 2, τ = 1, a k = 0.2, b k = 1 p and averaging over various α. (a) Number of edges versus the number of nodes and (b) degree distributions on a log-log scale for various σ : one nite-activity CCRM (σ = -0.5) and three in nite-activity CCRMs (σ = 0.2, σ = 0.5 and σ = 0.8). In (a) we note growth at a rate Θ(N 2 α ) for σ = -0.5 and O (N 2/(1+σ ) α

  (a) evaluate pointwise the Lévy intensity ρ, and potentially di erentiate it, (b) evaluate pointwise the Laplace exponent (4.20) and (c) sample from the exponentially tilted distribution (4.21).

  (t ) , w and w(t ) t=1,...,N are from the MCMC output. For simplicity, we limit the search of w to the set of MCMC samples and nally obtain w = arg min w ∈{w (1) ,...,w(N )

4 .Figure 4 . 6 :Figure 4 . 7 :

 44647 Figure 4.6: MCMC trace plots (left) and histograms (right) of parameters (a) log α, (b) σ and (c) τ for a graph generated with parameters p = 2, α = 200, σ = 0.2, τ = 1, b = 1 p , a = 0.2 and γ = 0.

Figure 4 . 8 :

 48 Figure 4.8: 95% posterior credible intervals and true values of (a) the mean parameters w i = 1 p p k=1 w ik of the 50 nodes with highest degree and (b) the log mean parameters log w i of the 50 nodes with lowest degree. (c) Empirical degree distribution and 95% posterior predictive credible interval. Results obtained for a graph generated with parameters p = 2, α = 200, σ = 0.2, τ = 1, b = 1 p , a = 0.2 and γ = 0, by inferring (left) an in nite-activity model with w * k ≥ 0 and σ < 1 and (right) a nite-activity model with w * k = 0 and σ < 0.

Figure 4 . 9 :

 49 Figure 4.9: Empirical degree distribution (red) and posterior predictive (blue) of the (a) polblogs and (b) USairport networks.

Figure 4 .

 4 Figure 4.11: Relative values of the weights in each community for a subset of the nodes of the (a) polblogs and (b) USairport networks.

Figure 4 .

 4 Figure 4.12: Adjacency matrices of the (a) polblogs and (b) USairport networks, reordered by associating each node to the community where it has the highest weight.

Figure 4 .

 4 Figure 4.13: Map of the USairport network. Pie charts represent the estimated feature weights of each airport. The size of the circles scale with the degree of the node.

  Figure A.1.

2 F

 2

  ).Q (Z , Z * ) = E [log p(P Ω (Y ), X , Z , γ )|Z * , P Ω (Y )] = E [log (p(P Ω (Y ), X |Z )p(Z |γ )p(γ )) |Z * , P Ω (Y )]

  Multinomial n, (w 1 , . . . , w p ) n ∈ N, w k ∈ [0

0 M

 0 γ k w ke -p k=1 (t k +γ k )w k w k =1 γ k β ke -w 0 p k=1 (t k +γ k )β k F dβ 1 , . . . , dβ p ρ 0 (dw 0 ) = ∞ -w 0 γ 1:p -M -w 0 (t 1:p + γ 1:p ) ρ 0 (dw 0 )

  t k ) a k +m k C.2. Background on MCMC methods which is generally complex and high dimensional. The samples can be used to approximate the target distribution and given a function h(ϕ), one can approximate integrals of the form Φ h(ϕ)π (ϕ)dϕ = E[h(ϕ)]

Algorithm 8 :

 8 Metropolis-Hastings algorithm. U[a, b] with a ∈ R and b ∈ R denotes the uniform distribution on interval [a, b].

  cycles through the d components by sampling each one of them from their full conditional distributionπ (ϕ k |ϕ -k ) = π (ϕ) π (ϕ)dϕ k , k = 1, . . . , di.e. the distribution of the k-th component of ϕ conditioning on all the remaining components ϕ -k = (ϕ 1 , . . . , ϕ k-1 , ϕ k+1 , . . . , ϕ d ). The procedure is summarized in Algorithm 9.

  + a k ) log β ik -b k β ik

  r = p log w 0 , log β |rest p (log w 0 , log β |rest)

  q) = -m ik -a k + β ik Update hyperparameters (ϕ, α ) and total masses (w * 1 , . . . , w * p ) given the rest using MH. The hyperparameter of the mean measureρ is ϕ = (σ , τ , a 1:p , b 1:p , γ 1:p ). Consider the prior distribution p(α, ϕ, w * 1:p ) = p(α )p(σ )p(τ ) ) = Gamma (α; a α , b α ) , p(1 -σ ) = Gamma (1 -σ ; a σ , b σ ) , p(τ ) = Gamma (a τ , b τ ) and for k = 1, . . . , p p(a k ) = Gamma (a k ; a a , b a ) , p(b k ) = Gamma (b k ; a b , b b ) , p(γ k ) = Gamma γ k ; a γ , b γ .

  w * 1:p )q( w * 1:p | α, ϕ, w * 1:p ).whereq( σ |σ ) = Lognormal 1 -σ ; log(1 -σ ), σ 2 σ q( τ |τ ) = Lognormal τ ; log τ , σ 2 τ q( a k |a k ) = Lognormal a k ; log a k , σ 2 a , k = 1, . . . , p q( b k |b k ) = Lognormal b k ; log b k , σ 2 b , k = 1, . . . , p q( γ k |γ k ) = Lognormal γ k ; log γ k , σ 2 γ , k = 1, . . . , p q( α | ϕ, w * ) = Gamma α; a α + N α , b α + ψ ϕ λ 1:p q( w * | α, ϕ, w * ) = * α w * ; ϕ λ where λ k = w * k + 2 N αi=1 w ik and ϕ λ = σ , τ , a 1:p , b 1:p , γ 1:p + λ 1:p ; see below for more details on the choices of proposal distributions for w * and α.We accept the proposal α, ϕ, w * 1:p with probability min (1, r ) withr = r × b α + ψ ϕ λ 1:p b α + ψ ϕ λ 1:p a α +N α where λ k = w * k + 2 N α i=1 σ ( σ -σ )-b τ ( τ -τ )-b a p k=1 ( a k -a k )-b b p k=1 ( b k -b k )-b γ p k=1

jk 2 ×jk 2 × 2 α 4 .

 2224 The conditional distribution p(w * 1:p |n, w, α, ϕ) ∝ e -p k=1 w * k + Nα j=1 w * α (w * 1:p ; ϕ) ∝ e -p k=1 w * k + Nα j=1 w jk w * k × * α (w * 1:p ; ϕ) (C.1)is not tractable, i.e. we can not calculate its normalizing constant nor sample from it. As a proposal distribution, we use an exponential tiltingq( w * 1:p | α, ϕ, w * 1:p ) ∝ e -p k=1 λ k w * k * α (w * 1:p ; ϕ)with λ k ≥ 0, k = 1, . . . p, for which we can calculate the normalizing constante -p k=1 λ k w * k * α ( w * ; ϕ)dw * 1:p = e -αψ ϕ (λ 1:p ) .We nally obtain the proposal distributionq w * 1:p | α, ϕ, w * 1:p = e -p k=1 λ k w * k * α ( w * ; ϕ) e -αψ ϕ (λ1:p ) = * α w * ; ϕ λwhere ϕ λ = σ , τ , a 1:p , b 1:p , γ 1:p + λ 1:p . In practice, taking λ k = 2N α w k + w * k yields a fair approximation of (C.1) ase -p k=1 (2N α w k + w * k ) w * k e -p k=1 (2N α w k +w * k ) w * k . (C.2)Choice of the proposal for α. The conditional distributionp α |(n ijk ) 1≤i,j≤N α ;k=1,...,p , (w i1 , . . . , w ip ) i=1,...,N α , w * 1:p , ϕ ∝ p(α )p (w i1 , . . . , w ip ) i=1,...,N α , w * 1:p |(n ijk ) 1≤i,j≤N α ;k=1,...,p , α, ϕ ∝ α a α -1 e -b α α × e -p k=1 w * k + Nα j=1 w α N α × * α w * 1:p ; ϕ × terms not depending on α or w * 1:p ∝ α a α +N α -1 e -b α α × e -p k=1 w * k +2Nα j=1 w jk w * k × * α w * 1:p ; ϕ × terms not depending on α or w * 1:p is not tractable. Now marginalizing out w * 1:p we have p α |(n ijk ) 1≤i,j≤N α ;k=1,...,p , (w i1 , . . . , w ip ) i=1,...,N α , ϕ∝ α N α +a α -1 e -b α α e -p k=1 w * k +2 Nα j=1 w jk w * k * α w * 1:p ; ϕ dw * 1:p .We again resort to the same approximation (C.2) to obtain the proposal distributionq( α | ϕ, w * 1:p ) ∝ α a α +N α -1 e -b α α e -αψ ϕ (λ1:p ) = Gamma α; a α + N α , b α + ψ ϕ λ 1:p .Alternatively (e.g. every two iterations) we can use a random walk proposal q( α |α ) = Lognormal α; log α, σ and obtain the following acceptance rater = r × α α a α +N α e -b α ( α-α )-αψ ϕ (λ1:p )+αψϕ λ 1:p .Finite activity parametric model. As a special case of our model, consider a parametric version with a nite-activity CRM (σ < 0) where all the nodes are observed and have at least one connection, implying w * k = 0 for k = 1, . . . , p. For simplicity, let also restrict to the case γ k = 0 for k = 1, . . . , p. From (3.6) we haveN α |α, ϕ ∼ Poissonατ σ σ and therefore α |N α , ϕ ∼ Gamma a α + N α , b α -τ σ σ since p(α |N α , ϕ) ∝ p(N α |α, ϕ)p(α ) ∝ -ατ σ σ N α e α τ σ σ N α ! α a α -1 e -b α α ∝ α a α +N α -1 e -(b α -τ σ σ )α .2. Update w i0 |rest ∼ Gamma m i -σ , τ + β ik |rest ∼ Gamma a k + m ik , b k + w i0 Update (w * 1 , . . . , w * p )|rest. 5. Update the latent variables n ijk |rest. 6. Repeat steps 1-4 to update (α , ϕ ), (w 10 , . . . , w N α 0 ), (β 1k , . . . , β N α k ) k=1,...,p and (w * 1 , . . . , w * p ). C.5 Gaussian approximation of the sum of small jumps Theorem 9. Consider the multivariate random variable X ε ∈ R p + with moment generating functionE[e -t T X ε ] = exp -α R p + 1 -e -p k=1 t k w k ρ ε (dw 1 , . . . , dw p )where α > 0 and ρ ε (dw 1 , . . . , dw p ) = e -p k=1 γ k w k dw 0 ) with ε > 0, ρ 0 is a Lévy measure on R + and F is a probability distribution on R p + with density f verifying ∞ 0 f (zu 1 , . . . , zu p )dz > 0 U -almost everywhere R p + β 1:p 2 f (β 1 , . . . , β p )dβ 1:p < ∞

  ε (dw 1 , . . . , dw p ) Σ ε = α R p + ww T ρ ε (dw 1 , . . . , dw p )Now consider, for any κ > 0, w 0 p k=1 γ k β k f (β 1 , . . . , β k ) ρ 0 (dw 0 )dβ 1:p .

  w 0 p k=1 γ k β k f (β 1 , . . . , β k ) ρ 0 (dw 0 )dβ 1:p 0 (dw 0 ) ∼ σ 2-σ b 2 ε when ε → 0, we conclude that lim ε→0 I ε = lim ε→0 σ 2 -σ β 1:p >κ 2 ε -σ /4 β 1:p 2 f (β 1 , . . . , β k ) dβ 1:p = 0p ρ ε (dw 1 , . . . , dw p ) 1:p e -w 0 p k=1 γ k β k ρ 0 (dw 0 ) f (β 1 , . . . , β p )dβ 1:p ∼ αE[β 1:p ] σ 1 -σ ε 1-σ (1/ε ) as ε → σ (1/ε ) as ε → 0using the dominated convergence theorem and lemmas 11 and 12.

11

  x p ) ∈ (0, ∞) p , we haveψ (tx 1 , . . . , tx p ) = R p + 1 -e -t p k=1 x k w k ν (dw 1 , . . . , dw p ) t↑∞ ∼ t σ Γ(1 -σ ) (te -t p k=1 x k w k ν (dw 1 , . . . , dw p ) -e -t p k=1 x k w k ν (dw 1 , . . . , dw p ) = R p + f (β 1 , . . . , β p ) ∞ 0 1 -e -w 0 t p k=1 x k β k e -w 0 p k=1 γ k β k ρ 0 (dw 0 )dβ 1:p which gives, using Lemmas 11, 12, and the dominated convergence theorem ψ (tx 1 , . . . , tx p ) t↑∞ ∼ t σ Γ(1 -σ )

  where σ ∈ (0, 1) and is a slowly varying function (at in nity). Then (C.8) is equivalent to e -tw )ρ (dw )t↑∞ ∼ Γ(1 -σ )t σ (t )for any k ≥ 1.

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Complete matrix X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Hierarchical adaptive spectral penalty . . . . . . . . . . . . . . . . . . 2.2.2 EM algorithm for MAP estimation . . . . . . . . . . . . . . . . . . . . 2.2.3 Generalization to other mixing distributions . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Poisson point processes and Poisson random measures . . . . . . . . . . . . . 3.2.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Completely random measures . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Generalized gamma process . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Vectors of CRMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . of connections between objects represented as an undirected simple graph and as a symmetric adjacency matrix. . . . . . . . . . . . 2 Recommender system: example of ratings given by users to items represented as a labeled bipartite graph and as a matrix. . . . . . . . . . . . . . . . . . . . . 1.1 Popularity of items in decreasing order. . . . . . . . . . . . . . . . . . . . . . . Low-rank matrix factorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Graphical model of the PMF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Graphical model of the prior. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Graphical model of the hierarchical prior. . . . . . . . . . . . . . . . . . . . . . 2.3 Marginal distribution for di erent values of the parameter β. . . . . . . . . . . Marginal distribution for Gamma, iGauss and GiG mixing distributions. . . . . 2.7 Test error w.r.t. the rank on simulated data. . . . . . . . . . . . . . . . . . . . . 2.8 Boxplots of the test errors and ranks on simulated data. . . . . . . . . . . . . . 2.9 NMAE on the test set of the Jester datasets w.r.t. the rank. . . . . . . . . . . .

	2 Probabilistic low-rank matrix completion with adaptive spectral regulariza-tion algorithms 3 Background on Bayesian nonparametrics 3.1 List of Figures 2.1 II Bayesian nonparametric models for networks 1 Network: example

1 Matrix completion for recommender systems 1.1 Recommender systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Collaborative ltering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Memory-based methods . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Model-based methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Low-rank matrix completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Matrix completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Low-rank assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Matrix factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Nuclear norm regularization . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Matrix completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Binary matrix completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Simulated data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Collaborative ltering examples . . . . . . . . . . . . . . . . . . . . . . xv CONTENTS 2.6 3.4.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Compound CRMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Exchangeable random measures for sparse and modular graphs with overlapping communities 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Sparse graph models with overlapping communities . . . . . . . . . . . . . . . 4.2.1 General construction using vectors of CRMs . . . . . . . . . . . . . . . 4.2.2 Particular model based on compound CRMs . . . . . . . . . . . . . . . 4.3 Properties and simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Exchangeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Posterior inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Characterization of conditionals and data augmentation . . . . . . . . 4.4.2 MCMC algorithm: General construction . . . . . . . . . . . . . . . . . 4.4.3 MCMC algorithm: Construction based on CCRMs . . . . . . . . . . . . 4.5 4.5.1 Simulated data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Real-world graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion List of works Bibliography A Appendices of Chapter 2 A.1 Expectation-maximization algorithm . . . . . . . . . . . . . . . . . . . . . . . A.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Recommender systems approaches with emphasis on collaborative ltering methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 2.4 Manifold of constant penalty, for a symmetric matrix Z = [x, ; , z] for the nuclear norm, HASP, and rank penalties. Contour of constant penalty for the classical lasso, hierarchical lasso and 0 penalties. . . . . . . . . . . . . . . . . 2.5 Thresholding rules on the singular values for the soft thresholding rule and the HAST algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6

  4.7 MCMC trace plots and histograms of parameters a and w * . . . . . . . . . . . . xix 4.8 95% posterior credible intervals and true values of the mean parameters of the 50 nodes with highest degree, the log mean parameters of the 50 nodes with lowest degree and the degree distribution. . . . . . . . . . . . . . . . . . . . . 73 4.9 Empirical degree distribution and posterior predictive of the polblogs and USairport networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.10 Level of a liation of each blog of the polblogs network to the communities identi ed as Liberal and Conservative. . . . . . . . . . . . . . . . . . . . . . . 74 4.11 Relative values of the weights in each community for a subset of the nodes of the polblogs and USairport networks. . . . . . . . . . . . . . . . . . . . . . . . 75 4.12 Adjacency matrices of the polblogs and USairport networks. . . . . . . . . . . 75 4.13 Map of the USairport network with pie charts of the airports estimated feature weights. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 A.1 M-step of the EM algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Impute algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Hierarchical Adaptive Soft-Thresholded (HAST) algorithm for low-rank estimation of complete matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Hierarchical Adaptive Soft-Impute (HASI) algorithm for matrix completion. . .

	List of Algorithms Nomenclature
	1 Acronyms and abbreviations cdf cumulative distribution function i.i.d. independent and identically distributed pdf probability density function pmf probability mass function a.k.a. also known as a.s. almost surely ALS Alternating least squares BNP Bayesian nonparametric CCRM Compound CRM CF Collaborative ltering CRM Completely random measure EM Expectation-maximization GGP Generalized gamma process GiG Generalized inverse Gaussian HMC Hamiltonian Monte Carlo i if and only if MAP Maximum a posteriori MAP maximum a posteriori MCMC Markov chain Monte Carlo MH Metropolis-Hastings MLE Maximum likelihood estimator MMMF Maximum-margin matrix factorization NMAE Normalized mean absolute error PMF Probabilistic matrix factorization resp. respectively s.t. subject to SGD Stochastic gradient descent SVD Singular value decomposition w.p. with probability Soft-xxiii w.r.t. with respect to

4 Hierarchical Adaptive Soft-Impute algorithm for binary matrix completion (HASIbin). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Shedler-Lewis thinning algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . 6 Adaptive thinning algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 MCMC sampler for posterior inference. . . . . . . . . . . . . . . . . . . . . . . . 8 Metropolis-Hastings algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Gibbs sampling algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Hamiltonian Monte Carlo algorithm. . . . . . . . . . . . . . . . . . . . . . . . .

Table 2 .

 2 1: Expressions of various mixing densities and associated weights. K ν denotes the modi ed Bessel function of the third kind.

	Mixing density p(γ i )	Marginal density p(d

i ) Weights ω

Table 2 . 2 :

 22 Results on the Jester datasets. test is the test set. The mean number of iterations for Soft-Impute, Hard-Impute and HASI (initialization included) algorithms are respectively 9, 76 and 76. Computations for the HASI algorithm take approximately 5 hours on a standard computer 2 . The results, averaged over 10 replications (with almost no variability observed), are presented in Table2.2. The HASI algorithm provides very good performance on the di erent Jester datasets, with lower NMAE than the other methods. Figure

		Jester 1	Jester 2	Jester 3
		24983 × 100	23500 × 100	24938 × 100
		27.5% miss.	27.3% miss.	75.3% miss.
	Method	NMAE Rank NMAE Rank NMAE Rank
	MMMF	0.161	95	0.162	96	0.183	58
	Soft Imp	0.161	100	0.162	100	0.184	78
	Soft Imp+ 0.169	14	0.171	11	0.184	33
	Hard Imp 0.158	7	0.159	6	0.181	4
	HASI	0.153	100	0.153	100	0.174	30
	where Ω

Table 2 . 3 :

 23 Results on the MovieLens datasets.

		MovieLens 100k MovieLens 1M
		943 × 1682	6040 × 3952
		93.7% miss.	95.8% miss.
	Method	NMAE Rank	NMAE Rank
	MMMF	0.195	50	0.169	30
	Soft Imp	0.197	156	0.176	30
	Soft Imp+ 0.197	108	0.189	30
	Hard Imp 0.190	7	0.175	8
	HASI	0.187	35	0.172	27
	the posterior distribution, and compare to other full Bayesian approaches to matrix comple-
	tion

Table 4 . 1 :

 41 Size of the networks, number of communities and computational time.

	Name	Nb nodes Nb edges Nb communities p Time
	polblogs	1224	16,715	2	30m
	USairport 1574	17,215	4	2h20m

Table 4 . 2 :

 42 Nodes with highest weight in each community for the polblogs network. Blog URLs are followed by known political leaning: (L) for left-wing and (R) for right-wing.

	Community 1: "Liberal"	Community 2: "Conservative"
	dailykos.com (L)	instapundit.com (R)
	atrios.blogspot.com (L)	blogsforbush.com (R)
	talkingpointsmemo.com (L)	powerlineblog.com (R)
	washingtonmonthly.com (L)	drudgereport.com (R)
	liberaloasis.com (L)	littlegreenfootballs.com/weblog (R)
	talkleft.com (L)	michellemalkin.com (R)
	digbysblog.blogspot.com (L)	lashawnbarber.com (R)
	newleftblogs.blogspot.com (L)

wizbangblog.com (R) politicalstrategy.org

(L)

hughhewitt.com (R) juancole.com

(L)

truthlaidbear.com (R)

Table 4 .

 4 3: Nodes with highest weights in each community for the USairport network.

	Community 1:	Community 2:	Community 3:	Community 4:
	"Hub"	"East"	"West"	"Alaska"
	New York, NY	Atlanta, GA	Denver, CO	Anchorage, AK
	Miami, FL	Detroit, MI	Las Vegas, NV	Fairbanks, AK
	Los Angeles, CA	Chicago, IL	Los Angeles, CA	Bethel, AK
	Newark, NJ	Washington, DC	Burbank, CA	Nome, AK
	Washington, DC	Nashville, TN	Phoenix, AZ	Galena, AK
	Atlanta, GA	Cleveland, OH	Salt Lake City, UT	King Salmon, AK
	Boston, MA	Birmingham, AL	Seattle, WA	Kotzebue, AK
	Fort Lauderdale, FL	Philadelphia, PA	San Francisco, CA	St. Mary's, AK
	Chicago, IL	Indianapolis, IN	Dallas/Fort Worth, TX	Chevak, AK
	Houston, TX	Charlotte, NC	Ontario, CA	Unalakleet, AK

Table 4 .

 4 2 reports the nodes with highest weights in each community for the polblogs network. Figure

  .com 95theses.blogspot.com abbadabbaduo.blogspot.com aboutpolitics.blogspot.com achingandspinning.blogspot.com ackackack.com adamtalib.blogspot.com adviceforlefty.blogspot.com agonist.org aintnobaddude.com ajbenjaminjr.blogspot.com alicublog.blogspot.com allanjenkins.typepad.com allspinzone.blogspot.com alphapredator.com/wdtgw.htm alternateworlds.blogspot.com althippo.blogspot.com alvintostig.typepad.com -patton.blogspot.com bakshi.us/redskunk barkingdingo.blogspot.com bartcop.com battleground-wisconsin.blogspot.com battlegroundstates.blogspot.com beastsbelly.blogspot.com bentcorner.blogspot.com bettyblog.com .com grassrootsnation.com greaterdemocracy.org greendogdemocrat.blogspot.com gregpalast.com grupo-utopia.com/blog/isou hal9000report.blogdrive.com hategun.com hellafaded.blogspot.com hellskitchennyc.blogspot.com hereswhatsleft.typepad.com hereswhatsleft.typepad.com/home higherpieproductions.com home.att.net/~gentle.reader home.earthlink.net/~fsrhine home.earthlink.net/~kevin.omeara home.houston.rr.com/skeptical homepage.mac.com/elisa_camahort/ibloghotflashesfromthecampaigntrail.blogspot.com hotflashreport.com howienfriends.blogspot.com hugozoom.blogspot.com ibe.blogspot.com ibrutus.com iddybud.blogspot.com idiosyncratictendencies.com idlehandsmag.com/yellowdog04 iflipflop.com ignatz.blogspot.com ihatepatrobertson.com ilovecynics.com insanepreschoolmom.blogspot.com interestingtimes.blogspot.com interestingtimes.typepad.com ironmouth.com irregulartimes.com/blogger.html islanddave.blogspot.com itlookslikethis.blogeasy.com ivotedforgeorge.com iwantmycountryback.org j-bradford-delong.net/movable_type jadbury.com jadbury.com/blog jadedreality.blogspot.com jameswolcott.com janm.blogspot.com jbcougar.blogspot.com jdeeth.blogspot.com jeremybrendan.blogspot.com jetage.blogspot.com jewssansfrontieres.blogspot.com jimgilliam.com jimtreacher.com jinkythecat.blogspot.com jmbzine.com joebrent.blogspot.com john.hoke.org johnmccrory.com johnnynobody.blogspot.com journals.aol.com/breuvers/madashellnotgoingtotakeitanymore juancole.com julietterossant.com/superchefblog/superchefblog.html juliusblog.blogspot.com justmark.com karlhenderson.blogspot.com karmicsoup.blogspot.com kcdems.blogspot.com kensain.com kerryforpresident2008.blogspot.com kicktheleftist.blogspot.com kiosan.blogharbor.com kippsblog.com kurtkk.blogspot.com kydem.blogspot.com lastdaysoftherepublic.fatoprofugus.net lawdork.blogspot.com leanleft.com left2right.typepad.com lefterer.com lefti.blogspot.com leftinthereign.blogspot.com leftthought.blogspot.com lefttimes.com leftwingnation.com lendmesomesugar.blogs.com/shut_up_already lennonreport.blogspot.com leonards-digest.blogspot.com liberalangst.org liberalavenger.com liberaleric.blogspot.com liberaloasis.com liberalreview.blogspot.com liberalthunderdome.blogspot.com lightupthedarkness.org lightupthedarkness.org/blog/default.asp limericksavant.blogspot.com liquidlist.com livejournal.com/users/hoptkov livejournal.com/users/jmhm loadedmouth.com lorenjavier.blogspot.com loud-liberal.blogspot.com loveamericahatebush.com lowrentrat.blogdrive.com ltobs.blogspot.com ludis.blogspot.com ludovicspeaks.typepad.com ludovicspeaks.typepad.com/real_deal .com mcwil.blogspot.com meanspirit.blogspot.com meateatingleftist.com mediajunkie.com/edgewise mediaprima.com/nv1962 messengerpuppet.com/blog metropol47.blogspot.com michael124.blogspot.com michaelberube.com michaelphillips.blogspot.com mickikrimmel.com/redcarpet midguard.blogspot.com minagahet.blogspot.com mirocat.com misschin.bloggage.com mixtersmix.blogspot.com montages.blogspot.com moxiegrrrl.com mrleft.org .php paulchasman.com peacegarden.blogspot.com penheaded.blogspot.com pennywit.com/drupal permanentred.com peskytherat.com/pesky phillybri.blogspot.com philoponia.blogspot.com philosophers-stone.blogspot.com philvbblog.blogspot.com phoblographer..com tesibria.typepad.com/democracy_is_coming thatcoloredfellasweblog.bloghorn.com thatgoodnight.com the-goddess.org the-hamster.com theaggpro.blogspot.com theagitator.blogspot.com theangryliberal.blogspot.com theantibush.org theapologist.blogspot.com theblogwarrior.blogspot.com theblueview.blogspot.com thecarpetbaggerreport.com thecore4.com thefulcrum.blogspot.com .blogspot.com theyetimn.blogspot.com thingsasitis.net think2004.com thinkingrocks.blogspot.com thirdredeye.blogspot.com thislousytshirt.net thismodernworld.com thomasblog.typepad.com/bloggg thunewatch.squarespace.com tinylittledots.com tobyemden.blogspot.com tomburka.com tomcoburnisabigfatjerk.blogspot.com tomherod.blogspot.com toteota.blogspot.com trainorphans.org translucence.org travalex.blogspot.com tristero.blogspot.com trueconservative.typepad.com truedemocrat.blogspot.com turnpikefeminist.com turnspit.com uberdude.blogspot.com uggabugga.blogspot.com unodemocrats.com/blog upper-left.blogspot.com urbandemocracy.blogspot.com urbanecoinc.com/wordpress1 usademocrazy.blogspot.com usliberals.about.com vernsblog.thegillfamily.us:8180 virginiaprogressive.blogspot.com vocis.com/frank waitingfordorothy.blogspot.com .com absurd-canadian.blogspot.com ace.mu.nu aceoftrumpblog.blogspot.com acepilots.com/mt acertainslantoflight.blogspot.com achicknamedmarzi.com activistchat.com/blogiran adeimantus.blogspot.com alamodispatches.blogspot.com alamonation.blogspot.com alarmingnews.com aldaron.modblog.com aldaynet.org alexpelan.blogspot.com alittlemoretotheright.com all-encompassingly.com allahpundit.com allthingsmark.com alphapatriot.com althouse.blogspot.com americanchronicle.blogspot.com americandigest.org americandinosaur.blogspot.com americanfuture.typepad.com americankernel.com americanreport.blogspot.com americanthinker.com americanwarmonger.blogspot.com americanworldview.tripod.com/weltansblog amigo13.blogspot.com amradio.blogspot.com andrewsullivan.com andrightlyso.blogspot.com angrychineseblogger.blog-city.com angrygwn.blogspot.com anncoulter.org annika.mu.nu anothervrwc.blogspot.com antijohnkerry.blogspot.com antiprotester.blogspot.com apologiesdemanded.blogspot.com arkanssouri.blogspot.com armchairgeneralist.typepad.com asmallvictory.net asmodeus-space.com/weblog/blog/index.php astrosoup.blogspot.com athena.blogs.com awideawake.blogspot.com ayerdis.com/rants.php babytrollblog.com baldilocks.typepad.com balloon-juice.com bamapachyderm.blogspot.com batr.net batr.org/commentary.html beautifulatrocities.com beefalwayswins.blogspot.com beldar.blogs.com/beldarblog bellusbellum.info belmontclub.blogspot.com bensgtusmc.com bensworld.patriotforum.org bernardmoon.blogspot.com betsyspage.blogspot.com bidinotto.journalspace.com bigfatroid.blogspot.com bigjourney.blogspot.com billhobbs.com billrice.org billroggio.com/easongate bitheads.blogspot.com bittersweetme.net/blog/index.php bkennelly.com/vox blackmanforbush.blogspot.com blindmindseye.com blithered.blogspot.com blog.nam.org blog.ncsweb.us blog.so-amazing.net blog.willrobinson47.com bloghogger.blogspot.com blogicus.com blogodob.blogspot.com blogsagainsthillary.com blogsforbush.com blogsofwar.com blogspirator.blogspot.com blubberhollow.com/blog blue6golf.blogspot.com bluegoldfish.blogs.com/surface bluestates.blogspot.com bobhayes.net boottotheskull.com borgardblog.blogspot.com brainshavings.com brianscott.blogspot.com brutallyhonest.org buckeyepundit.blogspot.com bullmooserepublicans.com/blog bushblog.us c-pol.blogspot.com californiaconservatives4truth.blogspot.com calirep.blogspot.com calpoly.edu/~doleary/blog.htm captainsquartersblog.com/mt catscape.com cayankee.blogs.com cbcbcbcb.blogspot.com ccs178.com cdharris.net cecile.squarespace.com celluloid-wisdom.com/pw celluloid-wisdom.com/pw/ centinel.blogspot.com chadster.capitalfocus.org chainik_hocker.blogspot.com charlesking.blogspot.com chiefsblog.blogspot.com chrenkoff.blogspot.com christian-patriot.blogspot.com civilcommotion.com claycalhoun.com claytoncorner.blogspot.com clubforgrowth.org/blog cmillertime.blogspot.com coffee.ondragonswing.com commonsenserunswild.typepad.com confederateyankee.blogspot.com conservativeblogger.com conservativecat.com conservativedialysis.com conservativeeyes.blogspot.com conservativelife.com/blog conservativenation.us conservativeobserver.blogspot.com conservativepolitics.blogspot.com conservativepunk.com conservativepush.blogspot.com conservativeresponse.com conservativerevolution.com conservativezone.blogspot.com coxandforkum.com cptnwinky.com crankybastard.blogspot.com crankyneocon.com/crankyneocon cubanstories.blogspot.com cybermenace.blogspot.com cynicalnation.com d-42.com daddypundit.blogspot.com dadougster.blogspot.com dailypundit.com dailyrecycler.com/blog daisycutter.blogspot.com dalythoughts.com danieldrezner.com/blog danzfamily.com dartblog.com datingrepublicans.com deadcantrant.com/blog deanesmay.com deansjournal.blogspot.com decision08.blogspot.com denbeste.nu depressedlonelybored.typepad.com deserttusk.blogspot.com devildawg.blogspot.com dgci.net diggersrealm.com/mt dilusionl.blogspot.com diplomadic.blogspot.com discerningtexan.blogspot.com discountblogger.com disintegrator.blogspot.com dissectleft.blogspot.com dizzy-girl.net/index.php dmobley.blogspot.com dogwooddreams.com/serendipity donaldsensing.com downtownlad.blogspot.com drudgereport.com drumwaster.com drunkensamurai.blogspot.com dummocrats.com dynamist.com/weblog economicswithaface.com/weblog eeg3.com ejectejecteject.com electionprojection.com electricvenom.com elevendayempire.com/movabletype emilythedog.blogspot.com erickohn.com erikack.blogspot.com etalkinghead.com evangelicaloutpost.com everythingiknowiswrong.com evilpundit.com fearfulsymmetry.blogspot.com firstdownpolitics.com franklog.com fraterslibertas.com freedomofthought.com freerepublic.com fringeblog.com fritzs-thoughts.blogspot.com gaypatriot.blogspot.com gccpundit.blogspot.com gcruse.typepad.com georgewbush.com gerberatetra.blogspot.com gevkaffeegal.typepad.com/the_alliance ghostofaflea.com gindy.blogspot.com gmscorner.blogspot.com godubya.com gopandcollege.blogspot.com gopandthecity.blogspot.com gopbloggers.org gopinsight.com gotdesign.blogspot.com greatestjeneration.com grownups.blogspot.com gullyborg.typepad.com happyhomeschooler.blog-city.com hasidicgentile.org hathaby.net/weblog.php headland.blogspot.com healingiraq.blogspot.com heavylifting.blogspot.com hectorvex.blogspot.com henerd.com hiddennook.blogspot.com hillcountryviews.blogspot.com hipublican.com hobsonschoice.us holecard.blogspot.com home.earthlink.net/~techservant home.midsouth.rr.com/joefish homespunbloggers.blogspot.com homicidalmaniak.com horologium.net hughhewitt.com iamaugustus.blogspot.com ikilledcheguevara.blogspot.com imao.us imprescindibile.ilcannocchiale.it incite1.blogspot.com indcjournal.com indepundit.com instapundit.com interested-participant.blogspot.com inthebullpen.com iowageek.blogspot.com iraqthemodel.blogspot.com isdl.blogspot.com isdl.weblogs.us itscomedowntothis.blogspot.com itznewstome.blogspot.com jacklewis.net janegalt.net jchristopherfeng.com jeffblanco.blogdrive.com jewishworldreview.com jg-spot.blogspot.com jihadwatch.org jlynnsmith30.blogspot.com joatmoaf.typepad.com/i_love_jet_noise joepublicus.blogspot.com johnkerrymustlose.com johnnbrown.blogspot.com jokerstotheright.blogspot.com joshferguson.blogspot.com journals.aol.com/lily990016/pissoffliberals journals.aol.com/mark24609/myblog jperspective.com jquinton.com jrogg.blogspot.com juntoboys.blogspot.com justalkin.us kalblog.com kausfiles.com keithy1028.bravejournal.com kellipundit.blogspot.com kenshepherd.blogspot.com kevincourser.blogspot.com kimdutoit.com/dr/weblog.php king-of-fools.com kitchennetwork.blogspot.com la4israel.org/wordpress ladymac.com lahargis.blogspot.com larsonreport.com lashawnbarber.blogspot.com lashawnbarber.com laughatliberals.com laughingwolf.net lawguy.blogspot.com valuerightnews.blogspot.com leftcoastconservative.blogspot.com legendgames.net/myblog.asp libertarianjackass.blogspot.com littlegreenfootballs.com/weblog littlegreenfootballs.com/weblog/weblog.php littletinylies.com livejournal.com/users/bambenek livinginbabylon.blogspot.com lonewacko.com loosecoin.blogspot.com lt-smash.us lucianne.com luxeword.com madanthony.org made4theinternet.blogspot.com madtechspeaks.blogspot.com magnificentfreedom.us manifestcontent.net mantic.squarespace.com mariestwocents.blogspot.com markheimonen.blogspot.com marknicodemo.blogspot.com marksteyn.com martinipundit.com martydee.com/poligov matthewstinson.com/blog mattresspolice.com maybeithinktoomuch.com mdcbowen.org/cobb meckz.net mementomoron.blogspot.com messopotamian.blogspot.com metallicity.com/mb.asp mhking.mu.nu michaeltotten.com michellemalkin.com midwestrightwingers.blogspot.com mikesamerica.blogspot.com millers_time.typepad.com mindspring.com/~gsb3/blogger.html mobile.blogcastlive.com moorewatch.com mostlycajun.com motgs.com mtvirtus.blogspot.com mudandphud.blogspot.com mudvillegazette.com musicfromthebluelight.com/b mwilliams.info my2cent.blogspot.com myaisling.blogspot.com mycatharsis.com mydamascusroad.blogspot.com myechochamber.blogspot.com mypetjawa.mu.nu nashvilletruth.blogspot.com nationalbird.net nationalcenter.org/blog.html nationalnewsregister.com/modules/wordpress nationalreview.com/thecorner nationalreview.com/thecorner/corner.asp neoconservatives.blogspot.com neoconswatch.blogspot.com neonbrainiac.nu/mt/blog nerepublican.blogspot.com neverwrongnever.blogspot.com newcounterculture.com/log newsbloggers.blogspot.com newsjungle.blogspot.com newsnik.com nicedoggie.net nickiegoomba.

		Liberal
	4	dailykos.com
		atrios.blogspot.com
		talkingpointsmemo.com
	2	washingtonmonthly.com
	0	100monkeystyping.com 12thharmonic.com/wordpress 750volts.blogspotamericablog.blogspot.com americablog.org americanmuslim.blogs.com americanpolitics.com americansforbayh.blogspot.com amleft.blogspot.com amliberal.com/blog amptoons.com/blog anarchyxero.robfindlay.org andifeelfine.blogspot.com andymatic.com angrybear.blogspot.com angrydesi.typepad.com angryfinger.org angryhomo.blogspot.com annatopia.com/home.html anoldsoul.blogspot.com anonymoussources.blogspot.com answerguy.blogspot.com anybodybutbushyall.blogspot.com anywhichway.net arancaytar.blogspot.com archpundit.com arkansastonight.com askhoudari.blogspot.com astroturf.uni.cc atease.blogspot.com atrios.blogspot.com/ awards5.tripod.com/tarasblog bbillmon.org billsrants.blogspot.com blog.dccc.org blog.dennisfox.net blog.glinka.com blog.johnkerry.com blog.kenlan.net blog.mintruth.com blog.veggiedude.com blog01.kintera.com/dnccblog blog01.kintera.com/emilysblog bloganonymous.com blogforamerica.com blogforarizona.com blogfreeordie.blogspot.com blogitics.com blogs.salon.com/0002874 blogs.salon.com/0003364 blogslut.com blosteam.com collegedems.com/blog conniptions.net conservativessuck.blogspot.com contrapositive.blogspot.com corrente.blogspot.com counterspin.blogspot.com crankylittleblog.blogspot.com criticalviewer.com crookedtimber.org crooksandliars.com dailyblatt.blogspot.com dailyhowler.com dailywarnews.blogspot.com damntheman.net dashnier.blogspot.com davidsirota.com dawnofnewamerica.blogspot.com deathpenaltyusa.blogspot.com debunker.net dedspace.blogspot.com delraysteve.com/blog demagogue.blogspot.com demleft.blogspot.com democraticunderground.com democratreport.blogspot.com democrats.org/blog democratvoice.org dems2000.net dems2004.org/blog denisdekat.com dewar.journalspace.com digbysblog.blogspot.com digestiblenews.blogspot.com digital-democrat.blogspot.com digitaljay.blogspot.com dimmykarras.blogspot.com dir.salon.com/topics/joe_conason/index.html discourse.net diypolitics.blogdrive.com dneiwert.blogspot.com dogfight04.typepad.com dohiyimir.typepad.com dolphinsdock.com/blog donkey2004.blogspot.com donspoliticalblog.blogspot.com duckdaotsu.blogspot.com dystopia.blog-city.com eastbaykerry.com elayneriggs.blogspot.com elderbearden.blogspot.com electablog.com elemming2.blogspot.com elissa.typepad.com eltcamerica.blogspot.com emergingdemocraticmajority.com emergingdemocraticmajorityweblog.com/donkeyrising emptyisform.com endthenightmare.blogspot.com enemykombatant.blogspot.com ergio.blogspot.com estropundit.blogspot.com etherealgirl.blogspot.com fafblog.blogspot.com fairshot.org farleft.blogspot.com fiercepoet.com flagrancy.net folkbum.blogspot.com forewarned.blogspot.com frederickclarkson.com fromtheroots.org fuckthisblog.blogspot.com gadflyer.com garbage-house.com georgewbuy.blogspot.com gisleson.com/blog global-equality.org/news/blog/index.shtml goose3five.blogspot.com grassrootsmom.blogspotmadkane.com/notable.html maggiespants.co.uk mahablog.com marcbrazeau.blogspot.com margaretcho.com/blog/blog.htm margieburns.com markadams.blogdrive.com markarkleiman.com markschmitt.typepad.com/decembrist markwarnerforpresident2008.blogspot.com maruthecrankpot.blogspot.com massachusetts-liberal.com mathewgross.com mathewgross.com/blog matthewyglesias.com maultasch.us maxspeak.org/mt mayflowerhill.blogspotmsnbc.msn.com/id/3449870 mstabile.blogspot.com mydd.com myleftbrain.com myleftthoughts.blogspot.com mysterypollster.com/main nastyboys.blogspot.com nathancallahan.com nathannewman.org/log nationalreview.com/frum/frum-diary.asp ndnblog.org nearouterheaven.blogspot.com nebursworld.blogspot.com needlenose.com nerofiddled.blogspot.com netpolitik.blogspot.com netweed.com/postmodernanarchist newappeal.blogspot.com newdemocrat.blogdrive.com newdonkey.com newleftblogs.blogspot.com nielsenhayden.com/electrolite nielsenhayden.com/makinglight njfordemocracy.org node707.com nofearoffreedom.blogspot.com nomoremister.blogspot.com norbizness.com noseyonline.com nosmallplans.com/rants notbush.com notgeniuses.com nycitystoop.com obamablog.com obsidianwings.blogs.com oddhours.blogspot.com offthekuff.com/mt oipp.blogspot.com oliverwillis.com one38.org openeyesmemo.com orient-lodge.com ospolitics.org oxblog.blogspot.com pacdaily.com pacificviews.org pandagon.net parabasis.typepad.com patriotboy.blogspot.com pattymurray.com/blogcom pinkofeministhellcat.typepad.com/pinko_feminist_hellcat planetdave.com/blogs.php3?mid=1 politicalmonitor.us/blog politicalstrategy.org politicalthought.net politicalwire.com politics.com risinghegemon.blogspot.com rittenhouse.blogspot.com riverbendblog.blogspot.com roadtosurfdom.com robot-invasion.com robschumacher.blogspot.com rogerailes.blogspot.com rooksrant.com rowhouselogic.com roxanne.typepad.com rudepundit.blogspot.com ruminatethis.com s88172659.onlinehome.us/spockosbrain.html sadlyno.com saveoursenate.blogspot.com sccdp.org/blog.php schadelmann.com scoobiedavis.blogspot.com scottcsmith.net scripting.com scrutinyhooligans.blogspot.com seeingtheforest.com seetheforest.blogspot.com sethdmichaels.com shakespearessister.blogspot.com shamelessantagonist.blogspot.com sharedthought.com/weblog shininglight.us shoegal.modblog.com shotofpolitics.blogspot.com shrillblog.blogspot.com simbaud.blogspot.com simplyappalling.blogspot.com smirkingchimp.com smithersmpls.com snunes.blogspot.com someonetakethewheel.blogspot.com soonerthought.com southknoxbubba.net/skblog spacedog26.blogspot.com spectatorsport.blogspot.com stagefour.typepad.com/commonprejudice stalinism.com/shot-by-both-sides stcfoundation.blogspot.com stephenbates.com/yellowdoggereldemocrat stevecopy.blogharbor.com stevegilliard.blogspot.com steveguy.me.uk stevemacek.blogspot.com stillfighting.blogspot.com stitt.blogspot.com strangedoctrines.typepad.com strangesemantics.blogspot.com suburbanguerrilla.blogspot.com swamiuptown.com swingstateproject.com takebackthemedia.com talkleft.com tallone.org tbogg.blogspot.com teenageenthusiast.blogspottheleftcoaster.com thelonedem.com thelucideye.blogspot.com thepeach.blogspot.com thepoorman.net theradiomansays.blogspot.com therogueangel.com/blog thesnooter.blogspot.com thetalentshow.org thetalkingdog.com thewashingtonnote.com theworldaroundyou.com thewritewingwampum.wabanaki.net warandpiece.com watchingthewatchers.org waveflux.net weblogs.bakshi.us/redskunk whopundit.blogspot.com whoviating.blogspot.com whyareweback.blogspot.com winnegar.blog-city.com winthewest.blogspot.com woneffe.typepad.com xnerg.blogspot.com yglesias.typepad.com/matthew wonkette.com worldonfire.typepad.com/world_on_fire wpblog.ohpinion.com wsrblood.typepad.com/wiserblog wtpm.blogspot.com x-pollen.com/many/blog.html yarsrevenge.blogspot.com yoder.ru younglibs.com a100wwe.blogspot
		Left

blogspot.com bluegrassroots.blogspot.com bluelemur.com blueoregon.com bluestateredstate.blogspot.com bodyandsoul.typepad.com boffo.typepad.com boloboffin.blogspot.com bopnews.com boston.com

/news/blogs/dnc bowles2004.com/weblog boycottsbg.com bradcarson.com/blog bradfriedman.com/bradblog brilliantatbreakfast.blogspot.com browncross.com/usualsuspects btcnews.com/btcnews bullmooseblog.com burntorangereport.com bushlies.net/pages/10/index.htm bushmisunderestimated.blogspot.com busybusybusy.com buzzmachine.com carpetblogger.com cbaker.org/blog cemonitor.blogspot.com centerpiece.blogspot.com changeforamerica.com/blog charleypatton.blogspot.com charlineandjamie.com/dotnetweb01a/blogdisplay.aspx?logname=jamie&

#38;logcatid=48 chepooka.com chiron.typepad.com churchofcriticalthinking.com clarified.blogspot.com claudialong.com/blog cleancutkid.feedster.com politicswithrichard.blogspot.com polizeros.com pollsterseek.blogspot.com polstate.com portapulpit.com praguewriter.typepad.com presidentboxer.blogspot.com prestoncaldwellblog.blogspot.com profgoose.blogspot.com progressiveink.com progressivesociety.com/blog proponentofreason.blogspot.com prospect.org/weblog pudentilla.blogspot.com punditician.blogspot.com purplestates.blogspot.com qando.net question-dean.blogspot.com radgeek.com radikal_papi.pitas.com radio.weblogs.com/0131587/categories/flush raedinthemiddle.blogspot.com reachm.com/amstreet readingpost.com realitybasednation.com red-harvest.blogspot.com religiousleft.blogspot.com republicoft.typepad.com resistoppression.blogspot.com restoreamerica.blogspot.com retrogrouch.net rhetoricrhythm.blogspot.com righthandthief.blogspot.com rising-hegemon.blogspot.

  ron-james.com/blog rosenblog.com roseoftheknights.com/yank/pride.html roughstock.blogspot.com ryanshead.com samizdata.net/blog sarcasticsoutherner.blogspot.com sayanythingblog.com scha-den-freu-de.blogspot.com scrappleface.com scrawlville.com sebourn.com/weblog section-31.blogspot.com secureliberty.org/ sedenteanimo.com selfish-souls.com/blog sgtstryker.com shadydowns.

  windsofchange.net wizbangblog.com writehouse.us writingcompany.blogs.com/this_isnt_writing_its_typ xanga.com/lockjawtheogre xtremerightwing.net youngconservative.blogspot.com zebrax.blogs.com zeke01.blogspot.com zeke01.typepad.com zeph1z.tripod.com/blog

		Right
		Conservative
	2
	1
	0	100monkeystyping.

  /news/blogs/dnc bowles2004.com/weblog boycottsbg.com bradcarson.com/blog bradfriedman.com/bradblog brilliantatbreakfast.blogspot.com browncross.com/usualsuspects btcnews.com/btcnews bullmooseblog.com burntorangereport.com bushlies.net/pages/10/index.htmbushmisunderestimated.blogspot.com busybusybusy.com buzzmachine.com carpetblogger.com cbaker.org/blog cemonitor.blogspot.com centerpiece.blogspot.com changeforamerica.com/blog charleypatton.blogspot.com charlineandjamie.com/dotnetweb01a/blogdisplay.aspx?logname=jamie&logcatid=48 chepooka.com chiron.typepad.com churchofcriticalthinking.com clarified.blogspot.com claudialong.com/blog cleancutkid.com collegedems.com/blog conniptions.net conservativessuck.blogspot.com contrapositive.blogspot.com corrente.blogspot.com counterspin.blogspot.com crankylittleblog.blogspot.com criticalviewer.com crookedtimber.org crooksandliars.com dailyblatt.blogspot.com dailyhowler.com dailykos.com dailywarnews.blogspot.com damntheman.net dashnier.blogspot.com davidsirota.com dawnofnewamerica.blogspot.com deathpenaltyusa.blogspot.com debunker.net dedspace.blogspot.com delraysteve.com/blog demagogue.blogspot.com demleft.blogspot.com democraticunderground.com democratreport.blogspot.com democrats.org/blog democratvoice.org dems2000.net dems2004.org/blog denisdekat.com dewar.journalspace.com digbysblog.blogspot.com digestiblenews.blogspot.com digital-democrat.blogspot.com digitaljay.blogspot.com dimmykarras.blogspot.com dir.salon.com/topics/joe_conason/index.html discourse.net diypolitics.blogdrive.

  fairshot.org farleft.blogspot.com fiercepoet.com flagrancy.net folkbum.blogspot.com forewarned.blogspot.com frederickclarkson.com fromtheroots.org fuckthisblog.blogspot.com gadflyer.com garbage-house.com georgewbuy.blogspot.com gisleson.com/blog global-equality.org/news/blog/index.shtml goose3five.blogspot.com grassrootsmom.blogspot.com grassrootsnation.com greaterdemocracy.org greendogdemocrat.blogspot.com gregpalast.com grupo-utopia.com/blog/isou hal9000report.blogdrive.com hategun.com hellafaded.blogspot.com hellskitchennyc.blogspot.com hereswhatsleft.typepad.com hereswhatsleft.typepad.com/home higherpieproductions.com home.att.net/~gentle.reader home.earthlink.net/~fsrhine home.earthlink.net/~kevin.omeara home.houston.rr.com/skeptical homepage.mac.com/elisa_camahort/iblog hotflashesfromthecampaigntrail.blogspot.

  /frank waitingfordorothy.blogspot.com wampum.wabanaki.net warandpiece.com washingtonmonthly.com watchingthewatchers.org waveflux.net weblogs.bakshi.us/redskunk whopundit.blogspot.com whoviating.blogspot.com whyareweback.blogspot.com winnegar.blog-city.com winthewest.blogspot.com woneffe.typepad.com wonkette.com worldonfire.typepad.com/world_on_fire wpblog.ohpinion.com wsrblood.typepad.com/wiserblog wtpm.blogspot.com x-pollen.com/many/blog.html xnerg.blogspot.com yarsrevenge.blogspot.com yglesias.typepad.com/matthew yoder.ru younglibs.com .blogspot.com prosandcons.us punditguy.com punditz.journalspace.com qoae.net quante.blogspot.com quibbles-n-bits.com quimundus.modblog.com quimundus.squarespace.com r21online.com r2korn.blogdrive.com rabner.blogspot.com radioequalizer.blogspot.com raincrossblog.com randomjottings.net rant.st ratherbiased.com/news rathergate.com realclearpolitics.com realordeal.blogspot.com rebrand-democrat.txfx.net reckersau.blogspot.com redmindbluestate.blogspot.com rednyc.blogspot.com redstate.org redstatealliance.blogspot.com reggiescorner.blogspot.com regimechangeiran.com renpro.kwcom.net reporterette.com republog.net respublica2004.blogspot.com retiredwarrant.blogdrive.com revone.net/jarhead rfburnhertz.net/rf_blog richmar.blogspot.com right-thinking.com rightmoment.blogspot.com rightonred.net rightperspective.net rightrainbow.com rightstate.blogspot.com rightvoices.com rightwingbastardo.blogspot.com rightwingbob.com rightwingdude.squarespace.com rightwingjournal.blogspot.com Level of a liation of each blog of the polblogs network to the communities identi ed as "Liberal" (top) and "Conservative" (bottom). The names of the blogs are grouped according to the left-right wing ground truth. Left-wing blogs are represented in blue on the left, right-wing blogs in red on the right.

	dailykos.com (L) atrios.blogspot.com (L)	Liberal Conservative	New York, NY Miami, FL	Hub East West
	washingtonmonthly.com (L)		Detroit, MI	Alaska
	wonkette.com (L)		Knoxville, TN
	democraticunderground.com (L)		Lansing, MI
	iwantmycountryback.org (L)		Nashville, TN
	andrewsullivan.com (R)		Minneapolis, MN
	danieldrezner.com/blog (R)		Dallas, TX
	tagorda.com (R)		Seattle, WA
	drudgereport.com (R)		San Francisco, CA
	instapundit.com (R)		Anchorage, AK
	Left (a) polblogs Figure 4.10: blogsforbush.com (R)	a100wwe.blogspot.com absurd-canadian.blogspot.com ace.mu.nu aceoftrumpblog.blogspot.com acepilots.com/mt acertainslantoflight.blogspot.com achicknamedmarzi.com activistchat.com/blogiran adeimantus.blogspot.com alamodispatches.blogspot.com alamonation.blogspot.com alarmingnews.com aldaron.modblog.com aldaynet.org alexpelan.blogspot.com alittlemoretotheright.com all-encompassingly.com allahpundit.com allthingsmark.com alphapatriot.com althouse.blogspot.com americanchronicle.blogspot.com americandigest.org americandinosaur.blogspot.com americanfuture.typepad.com americankernel.com americanreport.blogspot.com americanthinker.com americanwarmonger.blogspot.com americanworldview.tripod.com/weltansblog amigo13.blogspot.com amradio.blogspot.com andrewsullivan.com andrightlyso.blogspot.com angrychineseblogger.blog-city.com angrygwn.blogspot.com anncoulter.org annika.mu.nu anothervrwc.blogspot.com antijohnkerry.blogspot.com antiprotester.blogspot.com apologiesdemanded.blogspot.com arkanssouri.blogspot.com armchairgeneralist.typepad.com asmallvictory.net asmodeus-space.com/weblog/blog/index.php astrosoup.blogspot.com athena.blogs.com awideawake.blogspot.com ayerdis.com/rants.php babytrollblog.com baldilocks.typepad.com balloon-juice.com bamapachyderm.blogspot.com batr.net batr.org/commentary.html beautifulatrocities.com beefalwayswins.blogspot.com beldar.blogs.com/beldarblog bellusbellum.info belmontclub.blogspot.com bensgtusmc.com bensworld.patriotforum.org bernardmoon.blogspot.com betsyspage.blogspot.com bidinotto.journalspace.com bigfatroid.blogspot.com bigjourney.blogspot.com billhobbs.com billrice.org billroggio.com/easongate bitheads.blogspot.com bittersweetme.net/blog/index.php bkennelly.com/vox blackmanforbush.blogspot.com blindmindseye.com blithered.blogspot.com blog.nam.org blog.ncsweb.us blog.so-amazing.net blog.willrobinson47.com bloghogger.blogspot.com blogicus.com blogodob.blogspot.com blogsagainsthillary.com blogsforbush.com blogsofwar.com blogspirator.blogspot.com blubberhollow.com/blog blue6golf.blogspot.com bluegoldfish.blogs.com/surface bluestates.blogspot.com bobhayes.net boottotheskull.com borgardblog.blogspot.com brainshavings.com brianscott.blogspot.com brutallyhonest.org buckeyepundit.blogspot.com bullmooserepublicans.com/blog bushblog.us c-pol.blogspot.com californiaconservatives4truth.blogspot.com calirep.blogspot.com calpoly.edu/~doleary/blog.htm captainsquartersblog.com/mt catscape.com cayankee.blogs.com cbcbcbcb.blogspot.com ccs178.com cdharris.net cecile.squarespace.com celluloid-wisdom.com/pw celluloid-wisdom.com/pw/ centinel.blogspot.com chadster.capitalfocus.org chainik_hocker.blogspot.com charlesking.blogspot.com chiefsblog.blogspot.com chrenkoff.blogspot.com christian-patriot.blogspot.com civilcommotion.com claycalhoun.com claytoncorner.blogspot.com clubforgrowth.org/blog cmillertime.blogspot.com coffee.ondragonswing.com commonsenserunswild.typepad.com confederateyankee.blogspot.com conservativeblogger.com conservativecat.com conservativedialysis.com conservativeeyes.blogspot.com conservativelife.com/blog conservativenation.us conservativeobserver.blogspot.com conservativepolitics.blogspot.com conservativepunk.com conservativepush.blogspot.com conservativeresponse.com conservativerevolution.com conservativezone.blogspot.com coxandforkum.com cptnwinky.com crankybastard.blogspot.com crankyneocon.com/crankyneocon cubanstories.blogspot.com cybermenace.blogspot.com cynicalnation.com d-42.com daddypundit.blogspot.com dadougster.blogspot.com dailypundit.com dailyrecycler.com/blog daisycutter.blogspot.com dalythoughts.com danieldrezner.com/blog danzfamily.com dartblog.com datingrepublicans.com deadcantrant.com/blog deanesmay.com deansjournal.blogspot.com decision08.blogspot.com denbeste.nu depressedlonelybored.typepad.com deserttusk.blogspot.com devildawg.blogspot.com dgci.net diggersrealm.com/mt dilusionl.blogspot.com diplomadic.blogspot.com discerningtexan.blogspot.com discountblogger.com disintegrator.blogspot.com dissectleft.blogspot.com dizzy-girl.net/index.php dmobley.blogspot.com dogwooddreams.com/serendipity donaldsensing.com downtownlad.blogspot.com drudgereport.com drumwaster.com drunkensamurai.blogspot.com dummocrats.com dynamist.com/weblog economicswithaface.com/weblog eeg3.com ejectejecteject.com electionprojection.com electricvenom.com elevendayempire.com/movabletype emilythedog.blogspot.com erickohn.com erikack.blogspot.com etalkinghead.com evangelicaloutpost.com everythingiknowiswrong.com evilpundit.com fearfulsymmetry.blogspot.com firstdownpolitics.com franklog.com fraterslibertas.com freedomofthought.com freerepublic.com fringeblog.com fritzs-thoughts.blogspot.com gaypatriot.blogspot.com gccpundit.blogspot.com gcruse.typepad.com georgewbush.com gerberatetra.blogspot.com gevkaffeegal.typepad.com/the_alliance ghostofaflea.com gindy.blogspot.com gmscorner.blogspot.com godubya.com gopandcollege.blogspot.com gopandthecity.blogspot.com gopbloggers.org gopinsight.com gotdesign.blogspot.com greatestjeneration.com grownups.blogspot.com gullyborg.typepad.com happyhomeschooler.blog-city.com hasidicgentile.org hathaby.net/weblog.php headland.blogspot.com healingiraq.blogspot.com heavylifting.blogspot.com hectorvex.blogspot.com henerd.com hiddennook.blogspot.com hillcountryviews.blogspot.com hipublican.com hobsonschoice.us holecard.blogspot.com home.earthlink.net/~techservant home.midsouth.rr.com/joefish homespunbloggers.blogspot.com homicidalmaniak.com horologium.net hughhewitt.com iamaugustus.blogspot.com ikilledcheguevara.blogspot.com imao.us imprescindibile.ilcannocchiale.it incite1.blogspot.com indcjournal.com indepundit.com instapundit.com interested-participant.blogspot.com inthebullpen.com iowageek.blogspot.com iraqthemodel.blogspot.com isdl.blogspot.com isdl.weblogs.us itscomedowntothis.blogspot.com itznewstome.blogspot.com jacklewis.net janegalt.net jchristopherfeng.com jeffblanco.blogdrive.com jewishworldreview.com jg-spot.blogspot.com jihadwatch.org jlynnsmith30.blogspot.com joatmoaf.typepad.com/i_love_jet_noise joepublicus.blogspot.com johnkerrymustlose.com johnnbrown.blogspot.com jokerstotheright.blogspot.com joshferguson.blogspot.com journals.aol.com/lily990016/pissoffliberals journals.aol.com/mark24609/myblog jperspective.com jquinton.com jrogg.blogspot.com juntoboys.blogspot.com justalkin.us kalblog.com kausfiles.com keithy1028.bravejournal.com kellipundit.blogspot.com kenshepherd.blogspot.com kevincourser.blogspot.com kimdutoit.com/dr/weblog.php king-of-fools.com kitchennetwork.blogspot.com la4israel.org/wordpress ladymac.com lahargis.blogspot.com larsonreport.com lashawnbarber.blogspot.com lashawnbarber.com laughatliberals.com laughingwolf.net lawguy.blogspot.com valuerightnews.blogspot.com leftcoastconservative.blogspot.com legendgames.net/myblog.asp libertarianjackass.blogspot.com littlegreenfootballs.com/weblog littlegreenfootballs.com/weblog/weblog.php littletinylies.com livejournal.com/users/bambenek livinginbabylon.blogspot.com lonewacko.com loosecoin.blogspot.com lt-smash.us lucianne.com luxeword.com madanthony.org made4theinternet.blogspot.com madtechspeaks.blogspot.com magnificentfreedom.us manifestcontent.net mantic.squarespace.com mariestwocents.blogspot.com markheimonen.blogspot.com marknicodemo.blogspot.com marksteyn.com martinipundit.com martydee.com/poligov matthewstinson.com/blog mattresspolice.com maybeithinktoomuch.com mdcbowen.org/cobb meckz.net mementomoron.blogspot.com messopotamian.blogspot.com metallicity.com/mb.asp mhking.mu.nu michaeltotten.com michellemalkin.com midwestrightwingers.blogspot.com mikesamerica.blogspot.com millers_time.typepad.com mindspring.com/~gsb3/blogger.html mobile.blogcastlive.com moorewatch.com mostlycajun.com motgs.com mtvirtus.blogspot.com mudandphud.blogspot.com mudvillegazette.com musicfromthebluelight.com/b mwilliams.info my2cent.blogspot.com myaisling.blogspot.com mycatharsis.com mydamascusroad.blogspot.com myechochamber.blogspot.com mypetjawa.mu.nu nashvilletruth.blogspot.com nationalbird.net nationalcenter.org/blog.html nationalnewsregister.com/modules/wordpress nationalreview.com/thecorner nationalreview.com/thecorner/corner.asp neoconservatives.blogspot.com neoconswatch.blogspot.com neonbrainiac.nu/mt/blog nerepublican.blogspot.com neverwrongnever.blogspot.com newcounterculture.com/log newsbloggers.blogspot.com newsjungle.blogspot.com newsnik.com nicedoggie.net nickiegoomba.blogspot.com nicoladellarciprete.blogs.com noguru.tblog.com nomayo.mu.nu nonboxthinking.blogspot.com nykola.com o4tom.blogspot.com officesmileman.com ofthemind.blogspot.com ogresview.blogspot.com okieonthelam.com oldfashionedwhippersnapper.blogspot.com onthewire.blogspot.com opiniontimes.blogspot.com opiniontimes.com oppb.com orthogonian.blogspot.com outsidethebeltway.com pajamaeditors.blogspot.com pajamahadin.com pajamajournalist.blogspot.com palominas.blogspot.com papadoc.net/pinkflamingobar.html pardonmyenglish.com patrickmcclarty.blogspot.com patrickruffini.com patriot-paradox.com patriotblog.com patriotism101.blogspot.com patriotsforbush.com patterico.com pejmanesque.com pennsylvanianinexile.blogspot.com perryvsworld.blogspot.com philomathean.blogs.com piano-tuning.net/blog poeticvalues.blogspot.com poliblogger.com polipundit.com politicalanimals.blogspot.com politicaldogs.org politicalmusings.net politicalpie.modblog.com politicaltracker.com politicaltracker.com/blog/weblog.php politicalvicesquad.blogspot.com poorjustin.blogspot.com poweragerambleson.blogspot.com powerlineblog.com powerpundit.com powervacuum.org presidentreagan.info/discussion professorbainbridge.com prolifeblogs.com propagandamachinerightwingnews.com rightwingthinking.blogspot.com rightwingtroll.blogspot.com rightword.blogspot.com riteturnonly.blogspot.com robbernard.com robertp17.blogspot.com rockpaperscissor.blogspot.com rockpaperscissors.blogs.com rogerlsimon.com romeocat.typepad.com ron-james.com/blog rosenblog.com roseoftheknights.com/yank/pride.html roughstock.blogspot.com ryanshead.com samizdata.net/blog sarcasticsoutherner.blogspot.com sayanythingblog.com scha-den-freu-de.blogspot.com scrappleface.com scrawlville.com sebourn.com/weblog section-31.blogspot.com secureliberty.org/ sedenteanimo.com selfish-souls.com/blog sgtstryker.com shadydowns.blogspot.com shakingspears.blogspot.com shallows.blogspot.com sharpeblog.cybercatholics.com shortfatcorporal.blogspot.com sickofliberals.blogspot.com sinfactor.blogspot.com sistertoldjah.com sixmeatbuffet.com slantpoint.com slingsnarrows.erudite-absurdity.com slipofthepen.blogspot.com slowplay.com slublog.blogspot.com smarthomeschool.com smashingzero.blogspot.com smellyduck.blogspot.com sneakeasysjoint.com sondrak.com soundingthetrumpet.blogspot.com southernappeal.blogspot.com southernrightwingextremist.blogspot.com southernwatch.blogspot.com spreadingunderstanding.blogspot.com spydrzweb.blogspot.com squiggler.braveblog.com stan-istan.blogspot.com stealthebandwagon.blogspot.com stillmanvalley.org/aoo stix1972.blogspot.com stmonk.blogspot.com stolenthunder.blogspot.com strategicintelligence.blogspot.com streetlog.typepad.com summation.net sweetgrrrl.blogspot.com swfwithattitude.blogspot.com swiftreport.blogs.com tagorda.com talesofawanderingmind.blogspot.com talkshowamerica.blogspot.com techievampire.net/wppol techtrend.com/blog/taranicole templeofjennifer.com/blog tepid-observer.blogspot.com texasbug.blogspot.com thatliberalmedia.com the-torch.com theamericanmind.com thebloghill.blogspot.com thecommonvirtue.com theconservativezone.com thecrankfiles.blogspot.com thedailygoodnews.com thedispatch.blogspot.com thedonovan.com theglitteringeye.com thejessefactor.blogspot.com thelastword.blogdrive.com theliberalslies.blogspot.com themeofabsence.com theneo-progressive.blogspot.com thenudnikfile.blogspot.com thepatriette.com thepaytons.org/essays/considerettes thepoliticalanimal.com thepoliticalteen.net therightblog.blogspot.com therightcoast.blogspot.com therightwingconspiracy.org therinsecycle.com therostra.blogspot.com thesakeofargument.com thespoonsexperience.com thetarpit.blogspot.com thetemplarpundit.blogspot.com theunderscore.blogspot.com theurbangrind.blogspot.com thevaticanofliberalism.com thinkingright.us thisliberal.com thomasgalvin.blogspot.com thomaswharry.com timblair.net timblair.spleenville.com tokenyoungconservative.blogspot.com tom-hanna.org toneofvoice.blogspot.com totels.com/bush04 townhall.com/clog truebluegal.blogspot.com truthlaidbear.com truthliesandcommonsense.blogspot.com truthprobe.blogspot.com tseytlin.blogspot.com tsrightdominion.blogspot.com tuckereskew.typepad.com twentyfirstcenturyrepublican.blogspot.com txfx.net unconventionalwisdom.typepad.com undercaffeinated.com underscorebleach.net/content/jotsheet unfetteredmusings.blogspot.com unusualhabits.blogspot.com usdlaw.blogspot.com variousorthodoxies.com victorhanson.com viewfromaheight.blogspot.com viewfromtonka.blogspot.com viewpointjournal.com vikingpundit.blogspot.com virginiapolitics.blogspot.com vodkapundit.com volokh.com warriorscreed.000k3.com watchandwait.blogspot.com watdanook.blogspot.com web.utk.edu/~agroves wehavesomeplanes.blogspot.com whatsakyer.blogspot.com wholewheatblogger.com wildweasel.blog-city.com williamwebbdotorg.blogspot.com winceandnod.blogspot.com windingroad.typepad.com windsofchange.net wizbangblog.com writehouse.us writingcompany.blogs.com/this_isnt_writing_its_typ xanga.com/lockjawtheogre xtremerightwing.net youngconservative.blogspot.com zebrax.blogs.com zeke01.blogspot.com zeke01.typepad.com zeph1z.tripod.com/blog Right Bethel, AK (b) USairport

  Todeschini, A. and Caron, F. HASI: Hierarchical adaptive Soft-Impute [Matlab package]. URL https://github.com/adrtod/hasi. • Todeschini, A. and Genuer, R. rchallenge: A simple data science challenge system using R Markdown and Dropbox [R package]. URL

	• Todeschini, A. (2014). Recent developments in software for MCMC. MCMSki IV, Cha-
	monix.
	• Todeschini, A. (2014). Biips software: inference in Bayesian graphical models with se-
	quential Monte Carlo methods. COMPSTAT, Geneva.
	• Todeschini, A. (2015). Biips: software for Bayesian inference with interacting particle
	systems. BAYES 2015, Basel.
	So ware

•

Todeschini, A., Caron, F, Fuentes, M., Legrand, P. and Del Moral, P. (2014)

. Biips: Software for Bayesian inference with interacting particle systems [C++ library, Matlab/Octave and R package]. URL https://biips.github.io/. • https://adrtod.github.io/ rchallenge.

  Table B.1: Discrete and continuous probability distributions. K ν denotes the modi ed Bessel function of the third kind.B.2 ProofsProof of (3.15). ψ (t 1 , . . . , t p ) = -e -p k=1 t k w k ρ (dw 1 , . . . , dw p )

	R p + 1 = + R p 1 -e -p k=1 t k w k e -p k=1 γ k w k

ϕ = arg max ϕ∈Φ p(D|ϕ)p(ϕ).Pour résoudre ce problème, nous avons généralement recours à des procédures d'optimisation itératives qui partent d'une approximation initiale et augmentent la fonction objectif jusqu'à convergence. Dans cette thèse, nous allons dériver un tel algorithme itératif en exploitant des variables latentes du modèle convenablement choisies. Ces méthodes de maximisation a posteriori sont appelées « probabilistes » dans la littérature.En revanche, les méthodes « bayésiennes complètes » visent à approcher toute la distribution a posteriori, qui peut être très complexe, multimodale par exemple. Parmi d'autres techniques, nous pouvons recourir à la simulation Monte-Carlo. En particulier, nous nous intéressons aux algorithmes de Monte-Carlo par chaîne de Markov (MCMC), dont l'objectif est de générer des échantillons (ϕ(t ) t=1,2,... ) à partir d'une chaîne de Markov qui admet la distribution cible, ici p(ϕ |D), comme distribution d'équilibre.Dans les modèles bayésiens non paramétriques[START_REF] Hjort | Bayesian nonparametrics[END_REF], le paramètre d'intérêt est de dimension in nie et est traité comme un processus stochastique plutôt que comme un vecteur aléatoire. Ce cadre est particulièrement intéressant pour plusieurs raisons. Le nombre d'objets considérés peut être très grand et en constante augmentation, il est donc logique de considérer le cas limite où il tend vers l'in ni. Un tel cadre s'est également avéré être élégant et utile pour capturer le comportement en loi de puissance des phénomènes aléatoires.En outre, nous serons attentifs à la exibilité de nos modèles. Nous proposons des formulations générales qui incluent divers cas particuliers, y compris des contributions de recherche x

Jester datasets can be downloaded from the URL http://goldberg.berkeley.edu/jester-data/.

Our Matlab implementation is available online at the URL https://github.com/adrtod/hasi.

MovieLens datasets can be downloaded from the URL http://www.grouplens.org/node/73.

Note that we consider a generalized de nition of a Poisson process, where the mean measure is allowed to have atoms; see e.g.Daley and Vere-Jones (2008a, Section

2.4).

We refer to graphs whose number of edges scales quadratically with the number of nodes as dense, and sparse if it scales sub-quadratically.

Note that we consider a generalized de nition of a Poisson process, where the mean measure is allowed to have atoms; see e.g.Daley and Vere-Jones (2008a, Section 2.4).

http://www.cise.ufl.edu/research/sparse/matrices/Newman/polblogs

http://www.transtats.bts.gov/DL _ SelectFields.asp?Table_ ID=292

Remerciements

List of Tables

List of works

Preprints • Todeschini, A., Caron, F, Fuentes, M., Legrand, P. and Del Moral, P. (2014). Biips: software for Bayesian inference with interacting particle systems. arXiv:1412.3779. [START_REF] Todeschini | Exchangeable random measures for sparse and modular graphs with overlapping communities[END_REF]. Exchangeable random measures for sparse and modular graphs with overlapping communities. arXiv:1602.02114.

Technical reports

• Todeschini, A., [START_REF] Todeschini | Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms[END_REF]. Contrat Inria -Evollis. Elaboration et validation d'un système de recommandation bayésien. Lot 1 : Etude bibliographique. • Todeschini, A., Caron, F. and Chavent, M. (2014). Contrat Inria -Evollis. Elaboration et validation d'un système de recommandation bayésien. Lot 2 : Analyse statique. • Todeschini, A., Caron, F. and Chavent, M. (2015). Contrat Inria -Evollis. Elaboration et validation d'un système de recommandation bayésien. Lot 4 : Analyse statique avec métadonnées.

International conferences and workshops with proceedings

• Todeschini, A., [START_REF] Todeschini | Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms[END_REF]. Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms. Neural Information Processing Systems (NIPS 2013), Lake Tahoe. • Minvielle, P., Todeschini, A., Caron, F. and Del Moral, P. (2014). Particle MCMC for Bayesian microwave control. 4th International Workshop on New Computational Methods for Inverse Problems (NCMIP 2014).

National conferences and workshops

• Todeschini, A., Caron, F. and Chavent, M. (2014). Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms. Statlearn 2014, Paris (Poster). • Todeschini, A., Caron, F. and Chavent, M. (2014). Complétion de matrice de rang faible probabiliste à l'aide d'algorithmes de régularisation spectrale adaptatifs. 46èmes Journées de Statistique de la SFDS, Lille. • Todeschini, A. (2014). Biips software: inference in Bayesian graphical models with sequential Monte Carlo methods. Rencontres AppliBUGS, Montpellier (Invited talk).

Appendices

Appendix A

Appendices of Chapter 2

A.1 Expectation-maximization algorithm

Consider a statistical model with unknown parameter vector ϕ ∈ Φ, a set of observed variables X ∈ X and a set of latent (unobserved) variables Z ∈ Z along with the complete log-likelihood function L(ϕ; X , Z ) = log p(X , Z |ϕ). The maximum likelihood estimator (MLE) of ϕ is determined by the log-marginal likelihood of the observed data L(ϕ; X ) = log p(X |ϕ) where

which might be intractable. The EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF][START_REF] Wu | On the convergence properties of the EM algorithm[END_REF]) is an iterative procedure to nd a (local) maximum likelihood estimate ϕ. After initializing ϕ (0) , the procedure alternates between two steps at each iteration t ≥ 0:

• Expectation (E) step: determine the expected value of the log-likelihood function w.r.t. the conditional distribution of Z given X and the current estimate of the parameter

• Maximization (M) step: nd the parameter that maximizes this quantity

The procedure can be directly applied to maximize a penalized likelihood or a posterior distribution taking L(ϕ; X ) = log p(X |ϕ) + log p(ϕ). Like many optimization procedures, the EM algorithm increases the value of the likelihood at each iteration and converges to a stationary point which may either be a saddle point or a local maximum. For di cult problems, the solution highly depends on initial conditions. It might be necessary to repeat the procedure with di erent initializations to nd a global maximum. Sometimes it may not be feasible to perform the M-step. A generalized EM (GEM) procedure chooses ϕ (t+1) such that t ) , ϕ (t ) ) without necessarily maximizing Q. EM is therefore a special case of GEM.

To see why it works, let further de ne

The EM algorithm can be viewed as a special case of minorize-maximization strategy (MM) with auxiliary function

Regarding the weights w i , observe that

which can be easily checked by identi cation

and thus obtain the following expression

Appendix C

Appendices of Chapter 4

C.1 Proofs of Propositions 6 and 7

The proof follows the lines of the sparsity proof in [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], and we only provide a sketch of it. First, as Z is a jointly exchangeable point process verifying (4.13) and under the moment condition (4.14), it follows from the law of large numbers that

Finite-activity case. If the vector of CRMs is nite-activity, the jump locations arise from an homogeneous Poisson process with nite rate, and N α = Θ(α ) a.s. It follows that

Infinite-activity case. Consider now the in nite-activity case. Following [START_REF] Caron | Sparse graphs using exchangeable random measures[END_REF], one can lower bound the node counting process N α by a counting process N α which is conditionally Poisson with mean measure λ(S 1 α )ψ (W 1 (S 2 α ), . . . ,W p (S 2 α )) where

in the in nite-activity case, it follows that N α = Ω(α ) a.s., and therefore

Finally, for compound CRMs with regularly varying ρ 0 with exponent σ , Proposition 10 in Appendix C.6 implies that ψ (W 1 (S 2 α ), . . . ,W p (S 2 α )) = Θ(α σ ) a.s. hence N α = ω (α 1+σ ) a.s. and

C.2 Background on MCMC methods

In this appendix, we introduce the basics of MCMC simulation. See the introductions of [START_REF] Gilks | Introducing Markov chain Monte Carlo[END_REF] and [START_REF] Andrieu | An introduction to MCMC for machine learning[END_REF] or the book of [START_REF] Gilks | Markov chain Monte Carlo[END_REF] for more details.

The Monte Carlo principle. Consider a random variable of interest ϕ ∈ Φ. The basic idea of Monte Carlo methods is to generate i.i.d. samples {ϕ (i) } i=1,...,n from a target distribution π (ϕ), for k = 1, . . . , d. The Hamiltonian function, H (q, p), corresponds to the total energy of the system and is generally of the form

where U (q) is called the potential energy and K (p) is called the kinetic energy. For instance, Hamiltonian equations can describe the movement of a puck on a smooth hilly surface without friction.

The idea of Hamiltonian Monte Carlo (HMC, [START_REF] Duane | Hybrid Monte Carlo[END_REF][START_REF] Neal | MCMC using Hamiltonian dynamics[END_REF] is, with the help of arti cial momentum variables, to move the Markov chain according to Hamiltonian dynamics by exploiting the shape of the target distribution. Contrary to the random-walk approach, this allows distant moves while retaining high acceptance rates for a faster exploration of high dimensional spaces.

The position q is our variable of interest ϕ and the potential energy

is de ned as the negative log-probability density of the target distribution. The momentum variables are arti cially introduced with multivariate Gaussian distribution

where M is a d ×d symmetric positive-de nite matrix (which is typically diagonal, and is often a scalar multiple of the identity matrix). The kinetic energy

is de ned as the negative log-probability density of the Gaussian distribution (up to an additive constant). Each iteration of the HMC algorithm has two steps. In the rst step, new values for the momentum variables are randomly drawn from their Gaussian distribution, independently of the current values of the position variables. In the second step, a Metropolis update is performed, using Hamiltonian dynamics of a certain time length to propose a new state.

In practice, Hamilton's equations are approximated by discretizing time, using some small stepsize ε, and the leapfrog discretization scheme is commonly used for stability reasons. This only requires to be able to compute the gradient of the potential energy

The procedure is summarized in Algorithm 10.

C.3 Details of the MCMC algorithm

In this appendix we provide more details for the steps of Algorithm (7) in the case of CCRMs with F and ρ 0 taking the form (4.11) and (4.12).

We then use the full conditional as a proposal distribution for α

and the MH acceptance rate becomes

C.4 Bipartite networks

It is possible to use a construction similar to that of Section 4.2 to model bipartite graphs, and extend the model of [START_REF] Caron | Bayesian nonparametric models for bipartite graphs[END_REF]. A bipartite graph is a graph with two types of nodes, where only connections between nodes of di erent types are allowed. Nodes of the rst type are embedded at locations θ i ∈ R + , and nodes of the second type at location θ j ∈ R + . The bipartite graph will be represented by a (non-symmetric) point process

where z ij = 1 if there is an edge between node i of type 1 and node j of type 2.

Statistical Model. We consider the model W 1 , . . . ,W p ∼ CRM(ρ, λ) W 1 , . . . ,W p ∼ CRM(ρ , λ)

and z ij = min(1, p k=1 n ijk ).

Posterior inference. We derive here the inference algorithm when (W 1 , . . . ,W p ) and (W 1 , . . . ,W p ) are compound CRMs with F and ρ 0 taking the form (4.11) and (4.12). Assume that we observe a set of connections z = (z ij ) i=1,...,N α ;j=1,...N α . We introduce latent variables n ijk , for 1

We want to approximate p((w 10 , . . . w N α 0 ), (β 1k , . . . , β N α k , w * k ) k=1,...,p , (w 10 , . . . , w N α 0 ), (β 1k , . . . , β N α k , w * k ) k=1,...,p , ϕ, α, ϕ , α |z).

where β is distributed from F .

Proof. We write the model in spherical form. Let r = w 2 k and u k = w k r for k = 1, . . . , p -1. The determinant of the Jacobian is

where

w 0 ρ 0 (dw 0 )dr and U (du) = 1 u p du 1:p is the uniform distribution on the unit sphere S p-1 . In order to apply Theorem 2.4 of [START_REF] Cohen | Gaussian approximation of multivariate Lévy processes with applications to simulation of tempered stable processes[END_REF] (see also [START_REF] Asmussen | Approximations of small jumps of Lévy processes with a view towards simulation[END_REF], we need to show that there exists a function b ε : (0, 1] → (0, +∞) such that