Concept

Extremal graph theory

Related publications (31)

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Thành Tâm Nguyên, Quoc Viet Hung Nguyen, 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

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

Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold

Emmanuel Abbé

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succe ...

INST MATHEMATICAL STATISTICS-IMS2023

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Graph Neural Networks With Lifting-Based Adaptive Graph Wavelets

Pascal Frossard

Spectral-based graph neural networks (SGNNs) have been attracting increasing attention in graph representation learning. However, existing SGNNs are limited in implementing graph filters with rigid transforms and cannot adapt to signals residing on graphs ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

iPool--Information-Based Pooling in Hierarchical Graph Neural Networks

Pascal Frossard

With the advent of data science, the analysis of network or graph data has become a very timely research problem. A variety of recent works have been proposed to generalize neural networks to graphs, either from a spectral graph theory or a spatial perspec ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Intra- and inter-hemispheric structural connectome in agenesis of the corpus callosum

Dimitri Nestor Alice Van De Ville, Lorena Gonçalves de Alcântara e Freitas Krikler, Vanessa Siffredi

Agenesis of the corpus callosum (AgCC) is a congenital brain malformation characterized by the complete or partial failure to develop the corpus callosum. Despite missing the largest white matter bundle connecting the left and right hemispheres of the brai ...

2021

Computational pipeline to probe NaV1.7 gain-of-function variants in neuropathic painful syndromes

Stefano Zamuner

Applications of machine learning and graph theory techniques to neuroscience have witnessed an increased interest in the last decade due to the large data availability and unprecedented technology developments. Their employment to investigate the effect of ...

NATURE RESEARCH2020

Testing for Equivalence of Network Distribution Using Subgraph Counts

Sofia Charlotta Olhede

We consider that a network is an observation, and a collection of observed networks forms a sample. In this setting, we provide methods to test whether all observations in a network sample are drawn from a specified model. We achieve this by deriving the j ...

AMER STATISTICAL ASSOC2020

Graph Coarsening with Preserved Spectral Properties

Andreas Loukas

In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences betwee ...

ADDISON-WESLEY PUBL CO2020

Simple Realizability of Complete Abstract Topological Graphs Simplified

Jan Kyncl

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

SPRINGER2020

Experiments with the Markoff Surface

Matthew De Courcy-Ireland

We confirm, for the primes up to 3000, the conjecture of Bourgain-Gamburd-Sarnak and Baragar on strong approximation for the Markoff surface modulo primes. For primes congruent to 3 modulo 4, we find data suggesting that some natural graphs constructed fro ...

TAYLOR & FRANCIS INC2022

The Schur-Erdos problem for sesmi-algebraic colorings

János Pach

We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type resul ...

HEBREW UNIV MAGNES PRESS2020

Incidences Between Planes Over Finite Fields

Van Thang Pham

In this note, we use methods from spectral graph theory to obtain bounds on the number of incidences between k-planes and h-planes in F-q(d), which generalizes a recent result given by Bennett, Iosevich, and Pakianathan (2014). More precisely, we prove tha ...

American Mathematical Society (AMS)2019

Time-resolved analysis of dynamic graphs: an extended Slepian design

Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois

Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...

SPIE-INT SOC OPTICAL ENGINEERING2019

Edge Ordered Turan Problems

Doemoetoer Palvoelgyi, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

COMENIUS UNIV2019

Learning Approach to Delineation of Curvilinear Structures in 2D and 3D Images

Agata Justyna Mosinska

Detection of curvilinear structures has long been of interest due to its wide range of applications. Large amounts of imaging data could be readily used in many fields, but it is practically not possible to analyze them manually. Hence, the need for automa ...

EPFL2019

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

Related publications (31)