Concept

Coupe (théorie des graphes)

Publications associées (26)

Graph generative deep learning models with an application to circuit topologies

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

EPFL2024

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

Acceleration of graph pattern mining and applications to financial crime

Jovan Blanusa

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

EPFL2023

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

What graph neural networks cannot learn: depth vs width

Andreas Loukas

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attribut ...

2020

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020

An Optimal Space Lower Bound for Approximating MAX-CUT

Mikhail Kapralov

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

ASSOC COMPUTING MACHINERY2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

Efficiently Learning Fourier Sparse Set Functions

Amir Zandieh, Andreas Krause, Mikhail Kapralov

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

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Statistical Physics Methods for Community Detection

Chun Lam Chan

This thesis is devoted to information-theoretic aspects of community detection. The importance of community detection is due to the massive amount of scientific data today that describes relationships between items from a network, e.g., a social network. I ...

EPFL2019

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Approximating Steiner trees and forests with minimum number of Steiner points

Nachshon Cohen

Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies s ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2018

Round Compression for Parallel Matching Algorithms

Slobodan Mitrovic, Aleksander Madry

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...

ASSOC COMPUTING MACHINERY2018

Consistency of Cheeger and Ratio Graph Cuts

Xavier Bresson

This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective fu ...

Microtome Publishing2016

Segmentation of Developing Human Embryo in Time-lapse Microscopy

Mathieu Salzmann

Being able to efficiently segment a developing embryo from background clutter constitutes an important step in automated monitoring of human embryonic cells. State-of-the-art automatic segmentation methods remain ill-suited to handle the complex behavior a ...

IEEE2016

Downsampling of Signals on Graphs Via Maximum Spanning Trees

Quy Ha Nguyen, Minh Do

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approxima ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Fast Partitioning of Vector-Valued Images

Martin Kurt Storath

We propose a fast splitting approach to the classical variational formulation of the image partitioning problem, which is frequently referred to as the Potts or piecewise constant Mumford-Shah model. For vector-valued images, our approach is significantly ...

Siam Publications2014

Unsupervised Texture Segmentation Using Monogenic Curvelets and the Potts Model

Michaël Unser, Martin Kurt Storath

We present a method for the unsupervised segmentation of textured images using Potts functionals, which are a piecewise-constant variant of the Mumford and Shah functionals. We propose a minimization strategy based on the alternating direction method of mu ...

IEEE2014