Publications associées à Thrackles: An improved upper bound

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

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Rom Pinchasi

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Electronic Journal Of Combinatorics2024

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

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

Network-based kinetic models: Emergence of a statistical description of the graph topology

Matteo Raviola

In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interact ...

Cambridge Univ Press2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

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

Mirjana Stojilovic, Guanglei Zhou

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

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Daniel Gatica-Perez, Sina Sajadmanesh

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...

Usenix Assoc2023

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

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

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

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Thanh Trung Huynh

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023

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

Graph-based approximate message passing iterations

Raphaël Jean Berthier

Approximate message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing ...

OXFORD UNIV PRESS2023

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Anne-Florence Raphaëlle Bitbol, Alia Abbara

Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, ev ...

Oxford Univ Press2023

Discovering Influencers in Opinion Formation Over Social Graphs

Ali H. Sayed, Mert Kayaalp, Valentina Shumovskaia, Mert Cemri

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

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

DiGress: Discrete Denoising diffusion for graph generation

Pascal Frossard, Volkan Cevher, Igor Krawczuk, Clément Arthur Yvon Vignac, Bohan Wang

This work introduces DiGress, a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. Our model utilizes a discrete diffusion process that progressively edits graphs with noise, through the process of adding or ...

2023

Metastability of the Potts Ferromagnet on Random Regular Graphs

Jean Bernoulli Ravelomanana

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...

SPRINGER2023

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