Publications related to Incidence matrix

Frustrated magnets in the limit of infinite dimensions: Dynamics and disorder-free glass transition

We study the statistical mechanics and the equilibrium dynamics of a system of classical Heisenberg spins with frustrated interactions on a d -dimensional simple hypercubic lattice, in the limit of infinite dimensionality d -> infinity . In the analysis we ...

Amer Physical Soc2024

Dispatch-aware Optimal Planning of Active Distribution Networks including Energy Storage Systems

Ji Hyun Yi

The thesis develops a planning framework for ADNs to achieve their dispatchability by means of ESS allocation while ensuring a reliable and secure operation of ADNs. Second, the framework is extended to include grid reinforcements and ESSs planning. Finall ...

EPFL2023

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

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

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

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

Online Distributed Learning Over Graphs With Multitask Graph-Filter Models

Ali H. Sayed, Roula Nassif

In this article, we are interested in adaptive and distributed estimation of graph filters from streaming data. We formulate this problem as a consensus estimation problem over graphs, which can be addressed with diffusion LMS strategies. Most popular grap ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

GOT: An Optimal Transport framework for Graph comparison

Pascal Frossard, Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia

We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

A Preconditioned Graph Diffusion LMS for Adaptive Graph Signal Processing

Ali H. Sayed, Roula Nassif

Graph filters, defined as polynomial functions of a graph-shift operator (GSO), play a key role in signal processing over graphs. In this work, we are interested in the adaptive and distributed estimation of graph filter coefficients from streaming graph s ...

IEEE COMPUTER SOC2018

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

From data to structures : graph learning under smoothness assumptions and applications in data science

Vasilis Kalofolias

Weighted undirected graphs are a simple, yet powerful way to encode structure in data. A first question we need to address regarding such graphs is how to use them effectively to enhance machine learning problems. A second but more important question is ho ...

EPFL2016

On sums of graph eigenvalues

Joachim Stubbe

We use two variational techniques to prove upper bounds for sums of the lowest several eigenvalues of matrices associated with finite, simple, combinatorial graphs. These include estimates for the adjacency matrix of a graph and for both the standard combi ...

Elsevier Science Inc2014

Learning Parametric Dictionaries for Signals on Graphs

Pascal Frossard, Ntorina Thanou, David Shuman

In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties – the ability to adapt to specific signal data and a fast implementation of the dictionary. To sparsely represent signals residing on wei ...

Institute of Electrical and Electronics Engineers2014

Parametric dictionary learning for graph signals

Pascal Frossard, Ntorina Thanou, David Shuman

We propose a parametric dictionary learning algorithm to design structured dictionaries that sparsely represent graph signals. We incorporate the graph structure by forcing the learned dictionaries to be concatenations of subdictionaries that are polynomia ...

2013

Identification of genetic determinants and pharmacological modulators of mitochondrial function

Pénélope Andreux

Increased life expectancy goes hand in hand with a higher incidence of age-related diseases that affect the nervous and metabolic systems, such as type 2 diabetes, cancer, Parkinson’s and Alzheimer’s disease. These complex diseases are a product of the com ...

EPFL2013

Clustering with Multi-Layer Graphs: A Spectral Perspective

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address ...

Institute of Electrical and Electronics Engineers2012

Whole-brain structural connectivity in temporal lobe epilepsy: a Diffusion Spectrum Imaging study

Jean-Philippe Thiran, Alessandra Griffa, Alessandro Daducci, Alia Lemkaddem, François Lazeyras

Introduction: Medial Temporal Lobe Epilepsy (mTLE) with hippocampal sclerosis is the most frequent cause of drug-resistant focal epilepsy in adults. These patients suffer from widespread subtle white matter abnormalities and abnormal functional connectivit ...

2012

A Game Theoretic Approach to Expander-based Compressive Sensing

Volkan Cevher, Sina Jafarpour

We consider the following expander-based compressive sensing (e-CS) problem: Given Φ ∈ ℝM×N (M

IEEE2011

A lower bound for algebraic connectivity based on the connection-graph-stability method

Martin Hasler, Ali Ajdari Rad, Mahdi Jalili

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously publish ...

Elsevier2011