Publications associées à The power of adaptivity in source identification with time queries on the path

Publications associées (33)

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Turán Problems for Oriented Graphs

Aliaksandra Novik

A classical Turán problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph H as a subgraph. It is well-known that the chromatic number of H is the graph parameter which describes the asympto ...

2024

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

Lukas Fritz Felix Vogl

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

Uncertainty quantification for Fisher-Kolmogorov equation on graphs with application to patient-specific Alzheimer's disease

Alfio Quarteroni

The Fisher-Kolmogorov equation is a diffusion-reaction PDE that models the accumulation of prionic proteins, which are responsible for many different neurological disorders. The most important and studied misfolded protein in literature is the Amyloid-beta ...

EDP SCIENCES S A2024

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

Aip Publishing2024

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

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

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

Privatized graph federated learning

Ali H. Sayed, Stefan Vlaski, Elsa Rizk

Federated learning is a semi-distributed algorithm, where a server communicates with multiple dispersed clients to learn a global model. The federated architecture is not robust and is sensitive to communication and computational overloads due to its one-m ...

SPRINGER2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Privacy-Preserving Machine Learning on Graphs

Sina Sajadmanesh

Graph Neural Networks (GNNs) have emerged as a powerful tool for learning on graphs, demonstrating exceptional performance in various domains. However, as GNNs become increasingly popular, new challenges arise. One of the most pressing is the need to ensur ...

EPFL2023

Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature rec ...

Association for the Advancement of Artificial Intelligence (AAAI)2023

Discovering Influencers in Opinion Formation Over Social Graphs

Ali H. Sayed, Mert Kayaalp, Valentina Shumovskaia

The adaptive social learning paradigm helps model how networked agents are able to form opinions on a state of nature and track its drifts in a changing environment. In this framework, the agents repeatedly update their beliefs based on private observation ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

A tutorial on graph models for scheduling round-robin sports tournaments

Dominique de Werra

Many sports leagues organize their competitions as round-robin tournaments. This tournament design has a rich mathematical structure that has been studied in the literature over the years. We review some of the main properties and fundamental scheduling me ...

WILEY2023

Graph neural networks for dynamic modeling of roller bearings

Olga Fink, Vinay Sharma

Machine learning has paved the way for the real-time monitoring of complex infrastructure and industrial systems. However, purely data-driven methods have not been able to learn the underlying dynamics and generalize them to operating conditions that have ...

PHM Society2023

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Jana Tabea Cslovjecsek

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Carleton Univ, Dept Mathematics & Statistics2023

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

Mirjana Stojilovic

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...

Los Alamitos2023

Finding Paths for Explainable MOOC Recommendation: A Learner Perspective

Tanja Christina Käser Jacober, Jibril Albachir Frej, Tatjana Nazaretsky

The increasing availability of Massive Open Online Courses (MOOCs) has created a necessity for personalized course recommendation systems. These systems often combine neural networks with Knowledge Graphs (KGs) to achieve richer representations of learners ...

2023

Atomic scale volume and grain boundary diffusion elucidated by in situ STEM

Johann Michler, Xavier Maeder, Laszlo Pethö

Diffusion is one of the most important phenomena studied in science ranging from physics to biology and, in abstract form, even in social sciences. In the field of materials science, diffusion in crystalline solids is of particular interest as it plays a p ...

Nature Portfolio2023

Diffusion timescale conundrum in contact metamorphism: Oxygen isotope and trace element profiles in dolomite

Anders Meibom, Stéphane Laurent Escrig, Lukas Baumgartner

Successful application of diffusion chronometry is based on detailed knowledge of diffusion parameters obtained from laboratory experiments, which also need to be upscaled to be applied to natural samples. While generally applicable, several examples of di ...

PERGAMON-ELSEVIER SCIENCE LTD2023