Publications related to Non-Exponential Variations for Classical Results in First Passage Percolation

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Recovering Static and Time-Varying Communities Using Persistent Edges

Maximilien Claude Robert Dreveton

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Ieee Computer Soc2024

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

EPFL2023

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

The power of adaptivity in source identification with time queries on the path

Patrick Thiran, Gergely Odor, Victor Cyril L Lecomte

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, ...

2022

Figlearn: Filter And Graph Learning Using Optimal Transport

Pascal Frossard, Mireille El Gheche, Matthias Minder, Zahra Farsijani

In many applications, a dataset can be considered as a set of observed signals that live on an unknown underlying graph structure. Some of these signals may be seen as white noise that has been filtered on the graph topology by a graph filter. Hence, the k ...

IEEE2021

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

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

Networks of Ethereum Non-Fungible Tokens: A graph-based analysis of the ERC-721 ecosystem

Marco Mattavelli, Simone Casale Brunet

Non-fungible tokens (NFTs) as a decentralized proof of ownership represent one of the main reasons why Ethereum is a disruptive technology. This paper presents the first systematic study of the interactions occurring in a number of NFT ecosystems. We illus ...

IEEE2021

On the asymptotic behavior of solutions to the Vlasov-Poisson system

Klaus Martin Widmayer

We prove small data modified scattering for the Vlasov-Poisson system in dimension

d=3

using a method inspired from dispersive analysis. In particular, we identify a simple asymptotic dynamic related to the scattering mass. ...

2021

Non-Exponential Variations for Classical Results in First Passage Percolation

Graph Chatbot

Chat with Graph Search

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Recovering Static and Time-Varying Communities Using Persistent Edges

Equivariant Neural Architectures for Representing and Generating Graphs

Maximum Independent Set: Self-Training through Dynamic Programming

The power of adaptivity in source identification with time queries on the path

Figlearn: Filter And Graph Learning Using Optimal Transport

Sequential metric dimension for random graphs

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

Networks of Ethereum Non-Fungible Tokens: A graph-based analysis of the ERC-721 ecosystem

On the asymptotic behavior of solutions to the Vlasov-Poisson system

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

Recovering Static and Time-Varying Communities Using Persistent Edges

Equivariant Neural Architectures for Representing and Generating Graphs

Networks of Ethereum Non-Fungible Tokens: A graph-based analysis of the ERC-721 ecosystem

On the asymptotic behavior of solutions to the Vlasov-Poisson system

Sequential metric dimension for random graphs

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Maximum Independent Set: Self-Training through Dynamic Programming

The power of adaptivity in source identification with time queries on the path

Figlearn: Filter And Graph Learning Using Optimal Transport