Publication
Degree-constrained edge partitioning in graphs arising from discrete tomography
Related publications (283)
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 ...
EPFL2022SPECTRE: 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 RESEARCH2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar
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 ...
2022On 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 ...
2022Generalised Implicit Neural Representations
We consider the problem of learning implicit neural representations (INRs) for signals on non-Euclidean domains. In the Euclidean case, INRs are trained on a discrete sampling of a signal over a regular lattice. Here, we assume that the continuous signal e ...
2022Incompleteness 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 Ltd2022Planted matching problems on random hypergraphs
Lenka Zdeborová, Anshul Toshniwal, Gabriele Sicuro
We consider the problem of inferring a matching hidden in a weighted random k-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matchin ...
2022Annihilation Filter Approach For Estimating Graph Dynamics From Diffusion Processes
Pascal Frossard, Arun Venkitaraman
We propose an approach for estimating graph diffusion processes using annihilation filters from a finite set of observations of the diffusion process made at regular intervals. Our approach is based on the key observation that a graph diffusion process can ...
IEEE2022Representing graphs through data with learning and optimal transport
Graphs offer a simple yet meaningful representation of relationships between data. Thisrepresentation is often used in machine learning algorithms in order to incorporate structuralor geometric information about data. However, it can also be used in an inv ...
EPFL2021