Publications related to Graph traversal

Privacy-Preserving Machine Learning on Graphs

Graph Neural Networks (GNNs) have emerged as a powerful tool for learning on graphs, demonstrating exceptional performance in various domains. However, as GNNs become increasingly popular, new challenges arise. One of the most pressing is the need to ensur ...

EPFL2023

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

EPFL2023

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

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

Distributed Graph Learning With Smooth Data Priors

Pascal Frossard, Mireille El Gheche, Isabela Cunha Maia Nobre

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

Multilayer Graph Clustering With Optimized Node Embedding

Pascal Frossard, Mireille El Gheche

We are interested in multilayer graph clustering, which aims at dividing the graph nodes into categories or communities. To do so, we propose to learn a clustering-friendly embedding of the graph nodes by solving an optimization problem that involves a fid ...

IEEE2021

NICEpath: Finding metabolic pathways in large networks through atom-conserving substrate-product pairs

Vassily Hatzimanikatis, Jasmin Maria Hafner

Motivation: Finding biosynthetic pathways is essential for metabolic engineering of organisms to produce chemicals, biodegradation prediction of pollutants and drugs, and for the elucidation of bioproduction pathways of secondary metabolites. A key step in ...

OXFORD UNIV PRESS2021

Frequency-Domain Non-intrusive Greedy Model Order Reduction Based on Minimal Rational Approximation

Fabio Nobile, Davide Pradovera

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

SPRINGER INTERNATIONAL PUBLISHING AG2021

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

EPFL2021

How Florist Apprentices Explore Bouquet Designs: Supporting Design Space Exploration for Vocational Students

Pierre Dillenbourg, Kevin Gonyop Kim, Catharine Regina Monika Maria Oertel Genannt Bierbach

Context: Exploring the design space is an important process in a design task. In this study, we considered design space exploration for the learners in vocational education and training (VET). The goal of the study was to investigate how they explore the d ...

2021

MATHICSE Technical Report : Frequency-domain non-intrusive greedy Model Order Reduction based on minimal rational approximation

Fabio Nobile, Davide Pradovera

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

MATHICSE2020

Flooding And Diameter In General Weighted Random Graphs

Thomas Mountford, Jacques Saliba

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, ...

CAMBRIDGE UNIV PRESS2020

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

Slepian Guided Filtering of Graph Signals

Dimitri Nestor Alice Van De Ville, Miljan Petrovic

Joint localization of graph signals in vertex and spectral domain is achieved in Slepian vectors calculated by either maximizing energy concentration (mu) or minimizing modified embedded distance (xi) in the subgraph of interest. On the other hand, graph L ...

SPIE-INT SOC OPTICAL ENGINEERING2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

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

Edge Ordered Turan Problems

Doemoetoer Palvoelgyi, Gábor Tardos, 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

Distributed Diffusion Adaptation Over Graph Signals

Ali H. Sayed, Roula Nassif, Jie Chen

Most works on graph signal processing assume static graph signals, which is a limitation even in comparison to traditional DSP techniques where signals are modeled as sequences that evolve over time. For broader applicability, it is necessary to develop te ...

IEEE2018

Diverse M-Best Solutions by Dynamic Programming

Michaël Unser, Virginie Sophie Uhlmann

Many computer vision pipelines involve dynamic programming primitives such as finding a shortest path or the minimum energy solution in a tree-shaped probabilistic graphical model. In such cases, extracting not merely the best, but the set of M-best soluti ...

Springer2017

When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum

Dimitri Nestor Alice Van De Ville, Maria Giulia Preti, Robin Jonathan Demesmaeker

The study of complex systems greatly benefits from graph models and their analysis. In particular, the eigendecomposition of the graph Laplacian lets emerge properties of global organization from local interactions; e.g., the Fiedler vector has the smalles ...

IEEE Institute of Electrical and Electronics Engineers2017