Interpretable Stability Bounds for Spectral Graph Filters

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.

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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, ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

Interpretable Stability Bounds for Spectral Graph Filters

Chat with Graph Search

Asynchronous Speedup in Decentralized Optimization

Testing Support Size More Efficiently Than Learning Histograms

Equivariant Neural Architectures for Representing and Generating Graphs

A full characterization of invariant embeddability of unimodular planar graphs

Independence numbers of polyhedral graphs

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

Sharp bounds on enstrophy growth for viscous scalar conservation laws

Adaptive majority problems for restricted query graphs and for weighted sets

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

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

Online Distributed Learning Over Graphs With Multitask Graph-Filter Models

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

Flooding And Diameter In General Weighted Random Graphs

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

Modeling, predicting and mining metabolism at atom-level resolution

Graph Learning with Partial Observations: Role of Degree Concentration

Topological exploration of artificial neuronal network dynamics

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

Efficiently Learning Fourier Sparse Set Functions

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