Publication

Space-Efficient Representations of Graphs

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

Scaling a Reliable Distributed System

Alexandre David Olivier Maurer

We consider the problem of reliably connecting an arbitrarily large set of computers (nodes) with communication channels. Reliability means here the ability, for any two nodes, to remain connected (i.e., their ability to communicate) with probability at le ...

LPD EPFL2016

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

Pierre Vandergheynst, Xavier Bresson, Rodrigo Cerqueira Gonzalez Pena

We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion ker- nel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot ...

Ieee2016

From data to structures

Vasilis Kalofolias

Weighted undirected graphs are a simple, yet powerful way to encode structure in data. A first question we need to address regarding such graphs is how to use them effectively to enhance machine learning problems. A second but more important question is ho ...

EPFL2016

Graph-based compression of dynamic 3D point cloud sequences

Pascal Frossard

This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames are similar, motion estimation is key to effective compression of th ...

Institute of Electrical and Electronics Engineers2016

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

Multilinear Low-Rank Tensors on Graphs & Applications

Pierre Vandergheynst, Nauman Shahid, Francesco Grassi

We propose a new framework for the analysis of low- rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank S ...

2016

Low-Rank Matrices on Graphs: Generalized Recovery & Applications

Pierre Vandergheynst, Nathanaël Perraudin, Nauman Shahid

Many real world datasets subsume a linear or non-linear low-rank structure in a very low-dimensional space. Unfortunately, one often has very little or no information about the geometry of the space, resulting in a highly under-determined recovery problem. ...

2016

Song Recommendation with Non-Negative Matrix Factorization and Graph Total Variation

Pierre Vandergheynst, Kirell Maël Benzi, Xavier Bresson, Vasilis Kalofolias

This work formulates a novel song recommender system as a matrix completion problem that benefits from collaborative filtering through Non-negative Matrix Factorization (NMF) and content-based filtering via total variation (TV) on graphs. The graphs encode ...

Ieee2016

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016