Publications associées à Interpretable Stability Bounds for Spectral Graph Filters

Publications associées (21)

Asynchronous Speedup in Decentralized Optimization

In decentralized optimization, nodes of a communication network each possess a local objective function, and communicate using gossip-based methods in order to minimize the average of these per-node functions. While synchronous algorithms are heavily impac ...

2025

Testing Support Size More Efficiently Than Learning Histograms

Nathaniel Idein Harms

Consider two problems about an unknown probability distribution 𝑝: (1) How many samples from 𝑝 are required to test if 𝑝 is supported on 𝑛 elements or not? Specifically, given samples from 𝑝, determine whether it is supported on at most 𝑛 elements, or it i ...

ACM2025

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

EPFL2023

A full characterization of invariant embeddability of unimodular planar graphs

Laszlo Marton Toth

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using ...

WILEY2023

Independence numbers of polyhedral graphs

Sébastien Yann Gaspoz, Riccardo Walter Maffucci

A polyhedral graph is a 3-connected planar graph. We find the least possible order p(k, a) of a polyhedral graph containing a k-independent set of size a for all positive integers k and a. In the case k =1 and a even, we prove that the extremal graphs are ...

Elsevier Science Inc2023

Beyond Spectral Gap: The Role of the Topology in Decentralized Learning

Martin Jaggi, Thijs Vogels, Hadrien Hendrikx

In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. In the decentralized setting, in which workers commu ...

Microtome Publishing2023

Sharp bounds on enstrophy growth for viscous scalar conservation laws

Nicola De Nitti

We prove sharp bounds on the enstrophy growth in viscous scalar conservation laws. The upper bound is, up to a prefactor, the enstrophy created by the steepest viscous shock admissible by the L infinity and total variation bounds and viscosity. This answer ...

Iop Publishing Ltd2023

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Ill-posedness of the quasilinear wave equation in the space 𝐻7/4(ln𝐻)−𝛽in ℝ2+1

Gaspard Ohlmann

We are interested in the well posedness of quasilinear partial differential equations of order two. Motivated by the study of the Einstein equation in relativity theory, there are a number of works dedicated to the local well-posedness issue for the quasil ...

EPFL2021

Online Distributed Learning Over Graphs With Multitask Graph-Filter Models

Ali H. Sayed, Roula Nassif

In this article, we are interested in adaptive and distributed estimation of graph filters from streaming data. We formulate this problem as a consensus estimation problem over graphs, which can be addressed with diffusion LMS strategies. Most popular grap ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Dimitri Nestor Alice Van De Ville, Thomas William Arthur Bolton, Raphaël Pierre Liégeois, Miljan Petrovic

The emerging field of graph signal processing (GSP) allows one to transpose classical signal processing operations (e.g., filtering) to signals on graphs. The GSP framework is generally built upon the graph Laplacian, which plays a crucial role in studying ...

2020

Flooding And Diameter In General Weighted Random Graphs

Thomas Mountford, Jacques Saliba

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, ...

CAMBRIDGE UNIV PRESS2020

Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison

David Shuman

A major line of work in graph signal processing [2] during the past 10 years has been to design new transform methods that account for the underlying graph structure to identify and exploit structure in data residing on a connected, weighted, undirected gr ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Modeling, predicting and mining metabolism at atom-level resolution

Jasmin Maria Hafner

Living organisms can catalyze many thousands of biochemical reactions that they use to convert energy and matter, which provides them with the essentials for life. The sum of these chemical reactions happening in an organism is called metabo-lism. Understa ...

EPFL2020

Graph Learning with Partial Observations: Role of Degree Concentration

Ali H. Sayed, Augusto José Rabelo Almeida Santos

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections ...

IEEE2019

Topological exploration of artificial neuronal network dynamics

Kathryn Hess Bellwald, Gard Spreemann

One of the paramount challenges in neuroscience is to understand the dynamics of individual neurons and how they give rise to network dynamics when interconnected. Historically, researchers have resorted to graph theory, statistics, and statistical mechani ...

2019

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

Matthias Grossglauser, Negar Kiyavash

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

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

Size Optimization of MIGs with an Application to QCA and STMG Technologies

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Heinz Riener, Eleonora Testa

Majority-inverter graphs (MIGs) are a logic representation with remarkable algebraic and Boolean properties that enable efficient logic optimizations beyond the capabilities of traditional logic representations. Further, since many nano-emerging technologi ...

ASSOC COMPUTING MACHINERY2018