Publications related to Algebraic graph theory

Space-Efficient Representations of Graphs

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

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

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

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

Pascal Frossard, Chenglin Li, Xing Gao

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

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

Modeling, predicting and mining metabolism at atom-level resolution

Jasmin Maria Hafner

Living organisms can catalyze many thousands of biochemical reactions that they use to convert energy and matter, which provides them with the essentials for life. The sum of these chemical reactions happening in an organism is called metabo-lism. Understa ...

EPFL2020

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

AMER MATHEMATICAL SOC2019

Cutting Materials in Half: A Graph Theory Approach for Generating Crystal Surfaces and Its Prediction of 2D Zeolites

Berend Smit, Peter George Boyd, Senja Dominique Barthel, Matthew David Witman

Scientific interest in two-dimensional (2D) materials, ranging from graphene and other single layer materials to atomically thin crystals, is quickly increasing for a large variety of technological applications. While in silico design approaches have made ...

2018

Graph Signal Processing Of Human Brain Imaging Data

Dimitri Nestor Alice Van De Ville, Thomas William Arthur Bolton

Modern neuroimaging techniques offer disctinct views on brain structure and function. Data acquired using these techniques can be analyzed in terms of its network structure to identify organizing principles at the systems level. Graph representations are f ...

IEEE2018

Conditional expanding bounds for two-variable functions over finite valuation rings

Van Thang Pham

In this paper, we use methods from spectral graph theory to obtain some results on the sum-product problem over finite valuation rings R of order q(r) which generalize recent results given by Hegyvari and Hennecart (2013). More precisely, we prove that, fo ...

Academic Press Ltd- Elsevier Science Ltd2017

Everything You Always Wanted to Know about Multicore Graph Processing but Were Afraid to Ask

Willy Zwaenepoel, Baptiste Joseph Eustache Lepers, Jasmina Malicevic

Graph processing systems are used in a wide variety of fields, ranging from biology to social networks, and a large number of such systems have been described in the recent literature. We perform a systematic comparison of various techniques proposed to sp ...

USENIX Association2017

Filtering Random Graph Processes Over Random Time-Varying Graphs

Andreas Loukas

Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity i ...

Institute of Electrical and Electronics Engineers2017

Isogeny graphs of ordinary abelian varieties

Dimitar Petkov Jetchev, Benjamin Pierre Charles Wesolowski, Ernest Hunter Brooks

Fix a prime number l. Graphs of isogenies of degree a power of l are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse gr ...

Springer Heidelberg2017

Scalable Low-rank Matrix and Tensor Decomposition on Graphs

Nauman Shahid

In many signal processing, machine learning and computer vision applications, one often has to deal with high dimensional and big datasets such as images, videos, web content, etc. The data can come in various forms, such as univariate or multivariate time ...

EPFL2017

Source Localization on Graphs via l1 Recovery and Spectral Graph Theory

Pierre Vandergheynst, Xavier Bresson, Rodrigo Cerqueira Gonzalez Pena

We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion ker- nel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot ...

Ieee2016

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Pierre Vandergheynst, Xavier Bresson, Michaël Defferrard

In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or wor ...

2016

Multilinear Low-Rank Tensors on Graphs & Applications

Pierre Vandergheynst, Nauman Shahid, Francesco Grassi

We propose a new framework for the analysis of low- rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank S ...

2016

Distributed Graph-based Convoy Control for Networked Intelligent Vehicles

Alcherio Martinoli, Ali Marjovi, Milos Vasic, Joseph Chadi Benoit Lemaitre

This paper presents an approach for formation control of multi-lane vehicular convoys in highways. We extend a Laplacian graph-based, distributed control law such that networked intelligent vehicles can join or leave the formation dynamically without jeopa ...

IEEE2015

Wavelets on graphs via spectral graph theory

Pierre Vandergheynst, Rémi Gribonval

We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral deco ...

Elsevier2011