Publication

The Sketching Complexity of Graph and Hypergraph Counting

Publications associées (29)

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Carleton Univ, Dept Mathematics & Statistics2023

Beyond Spectral Gap: The Role of the Topology in Decentralized Learning

Martin Jaggi, Thijs Vogels, Hadrien Hendrikx

In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. In the decentralized setting, in which workers commu ...

Microtome Publishing2023

Network Alignment With Holistic Embeddings

Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong

Network alignment is the task of identifying topologically and semantically similar nodes across (two) different networks. It plays an important role in various applications ranging from social network analysis to bioinformatic network interactions. Howeve ...

IEEE COMPUTER SOC2023

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

Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport

Isabel Haasler, Axel Ringh, Yiqiang Chen

In this work, we develop a new framework for dynamic network flow pro-blems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where t ...

2023

Acceleration of graph pattern mining and applications to financial crime

Jovan Blanusa

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

EPFL2023

Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature rec ...

Association for the Advancement of Artificial Intelligence (AAAI)2023

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Daniel Gatica-Perez, Sina Sajadmanesh

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...

Usenix Assoc2023

The Sketching Complexity of Graph and Hypergraph Counting

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Beyond Spectral Gap: The Role of the Topology in Decentralized Learning

Network Alignment With Holistic Embeddings

Metastability of the Potts Ferromagnet on Random Regular Graphs

Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport

Acceleration of graph pattern mining and applications to financial crime

Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Graph Chatbot

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Beyond Spectral Gap: The Role of the Topology in Decentralized Learning

Network Alignment With Holistic Embeddings

Privatized graph federated learning

Metastability of the Potts Ferromagnet on Random Regular Graphs

Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport

Acceleration of graph pattern mining and applications to financial crime

Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Privatized graph federated learning