Publications related to Wavelets on Graphs via Spectral Graph Theory

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

Time-resolved analysis of dynamic graphs: an extended Slepian design

Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois, Ibrahim Merad

Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...

SPIE-INT SOC OPTICAL ENGINEERING2019

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash, Osman Emre Dai

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

Asyrnptotics for the Turan number of Berge-K-2,K-t

Abhishek Methuku

Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. Let F be a family of graphs. The Turan number of the family Berge-F is the maximum possible number of edges in an r-uniform hyp ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Pierre Vandergheynst, Benjamin Ricaud, Nicolas Tremblay

The legacy of Joseph Fourier in science is vast, especially thanks to the essential tool that the Fourier transform is. The flexibility of this analysis, its computational efficiency and the physical interpretation it offers makes it a cornerstone in many ...

ELSEVIER FRANCE-EDITIONS SCIENTIFIQUES MEDICALES ELSEVIER2019

Efficiently Learning Fourier Sparse Set Functions

Andreas Krause, Mikhail Kapralov, Amir Zandieh

Learning set functions is a key challenge arising in many domains, ranging from sketching graphs to black-box optimization with discrete parameters. In this paper we consider the problem of efficiently learning set functions that are defined over a ground ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Subadditivity Beyond Trees and the Chi-Squared Mutual Information

Emmanuel Abbé, Enric Boix Adsera

Evans et al. [1] proved the subadditivity of the mutual information in the broadcasting on tree model with binary vertex labels and symmetric edge channels. They raised the question of whether such subadditivity extends to loopy graphs in some appropriate ...

IEEE2019

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

GOT: An Optimal Transport framework for Graph comparison

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Giovanni Chierchia

We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Wavelets on Graphs via Spectral Graph Theory

Graph Chatbot

Chat with Graph Search

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Time-resolved analysis of dynamic graphs: an extended Slepian design

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Asyrnptotics for the Turan number of Berge-K-2,K-t

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Efficiently Learning Fourier Sparse Set Functions

Subadditivity Beyond Trees and the Chi-Squared Mutual Information

Thrackles: An improved upper bound

GOT: An Optimal Transport framework for Graph comparison

Incidences Between Planes Over Finite Fields

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Thrackles: An improved upper bound

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Time-resolved analysis of dynamic graphs: an extended Slepian design

Efficiently Learning Fourier Sparse Set Functions

GOT: An Optimal Transport framework for Graph comparison

Incidences Between Planes Over Finite Fields

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Subadditivity Beyond Trees and the Chi-Squared Mutual Information

Asyrnptotics for the Turan number of Berge-K-2,K-t