Concept

Dense graph

Related publications (189)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

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 ...

2023

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 ...

Oxford2023

Nature vs. Nurture: Feature vs. Structure for Graph Neural Networks

Karl Aberer, Thành Tâm Nguyên, Chi Thang Duong

Graph neural networks take node features and graph structure as input to build representations for nodes and graphs. While there are a lot of focus on GNN models, understanding the impact of node features and graph structure to GNN performance has received ...

ELSEVIER2022

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

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

The micro-world of cographs

Dominique de Werra

Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of ...

ELSEVIER2022

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

Gossip algorithms and their accelerated versions have been studied exclusively in discrete time on graphs. In this work, we take a different approach and consider the scaling limit of gossip algorithms in both large graphs and large number of iterations. T ...

OXFORD UNIV PRESS2022

Graph Embedding for Retrieval

Chi Thang Duong

Information retrieval (IR) systems such as search engines are important for people to find what they need among the tremendous amount of data available in their organization or on the Internet. These IR systems enable users to search in a large data collec ...

EPFL2022