Publication

The micro-world of cographs

Related publications (32)

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

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

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

Karl Aberer, Quoc Viet Hung Nguyen, 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

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

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

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

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

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 Neural Networks With Lifting-Based Adaptive Graph Wavelets

Pascal Frossard, Chenglin Li, Mingxing Xu

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

Tree-cotree decomposition of isogeometric mortared spaces in H(curl) on multi-patch domains

Rafael Vazquez Hernandez, Bernard Kapidani

When applying isogeometric analysis to engineering problems, one often deals with multi-patch spline spaces that have incompatible discretisations, e.g. in the case of moving objects. In such cases mortaring has been shown to be advantageous. This contribu ...

2022