Saturated simple and k-simple topological graphs

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (31)

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Saber Salehkaleybar, Negar Kiyavash, Ehsan Mokhtarian

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...

2023

Graph signal processing tailored for subgraph focus and community structure

Miljan Petrovic

Community structure in graph-modeled data appears in a range of disciplines that comprise network science. Its importance relies on the influence it bears on other properties of graphs such as resilience, or prediction of missing connections. Nevertheless, ...

EPFL2022

Graph Representation Learning with Optimal Transport: Analysis and Applications

Effrosyni Simou

In several machine learning settings, the data of interest are well described by graphs. Examples include data pertaining to transportation networks or social networks. Further, biological data, such as proteins or molecules, lend themselves well to graph- ...

EPFL2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

Distributed Graph Learning With Smooth Data Priors

Pascal Frossard, Isabela Cunha Maia Nobre, Mireille El Gheche

Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that live ...

IEEE2022

Incompleteness of graph neural networks for points clouds in three dimensions

Michele Ceriotti, Sergey Pozdnyakov

Graph neural networks (GNN) are very popular methods in machine learning and have been applied very successfully to the prediction of the properties of molecules and materials. First-order GNNs are well known to be incomplete, i.e. there exist graphs that ...

IOP Publishing Ltd2022

A Topological characterisation of Weisfeiler-Leman equivalence classes

Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguish ...

2022

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

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

Deep MinCut: Learning Node Embeddings by Detecting Communities

Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong, Trung-Dung Hoang

We present Deep MinCut (DMC), an unsupervised approach to learn node embeddings for graph -structured data. It derives node representations based on their membership in communities. As such, the embeddings directly provide insights into the graph structure ...

ELSEVIER SCI LTD2022

Page 2 sur 2