Author name cluster

Stratis Limnios

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

ECAI Conference 2024 Conference Paper

SaGess: A Sampling Graph Denoising Diffusion Model for Scalable Graph Generation

Stratis Limnios
Praveen Selvaraj
Mihai Cucuringu
Carsten Maple
Gesine Reinert
Andrew Elliott

Denoising diffusion generative models are state-of-the-art methods for generating synthetic images that have also proved successful in tabular and graph synthetic data generation. However, their computational complexity has limited the application of these techniques to graph data, focusing usually on smaller graphs, such as those used in molecular modeling. In this paper, we propose SaGess, a discrete denoising diffusion approach, which is able to generate large real-world networks. Through a generalized divide-and-conquer framework, SaGess overcomes the scaling limitations of the diffusion model DiGress, by sampling a covering of subgraphs of the initial graph, training a DiGress module, and finally reconstructing a synthetic graph using the subgraphs that have been generated using the DiGress module. We evaluate the quality of the synthetic data sets against several competitor methods by comparing graph statistics between the original and synthetic samples, as well as evaluating the utility of the synthetic data set produced by using it to train a task-driven model, namely link prediction. In our experiments, SaGess outperforms most of the one-shot state-of-the-art graph generating methods by a significant factor, both on the graph metrics and on the link prediction task.

Details

TCS Journal 2020 Journal Article

Edge degeneracy: Algorithmic and structural results

Stratis Limnios
Christophe Paul
Joanny Perret
Dimitrios M. Thilikos

We consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edges to block and right after the robber is obliged to move to another vertex traversing at most s unblocked edges (s can be seen as the speed of the robber). Both parts have complete knowledge of the opponent's moves and the cops win when they occupy all edges incident to the robbers position. We introduce the capture cost on G against a robber of speed s. This defines a hierarchy of invariants, namely δ e 1, δ e 2, …, δ e ∞, where δ e ∞ is an edge-analogue of the admissibility graph invariant, namely the edge-admissibility of a graph. We prove that the problem asking whether δ e s ( G ) ≤ k, is polynomially solvable when s ∈ { 1, 2, 3, ∞ } while, otherwise, it is NP-complete. Our main result is a structural theorem for graphs of bounded edge-admissibility. We prove that every graph of edge-admissibility at most k can be constructed using ( ≤ k ) -edge-sums, starting from graphs whose all vertices, except possibly from one, have degree at most k. Our structural result is approximately tight in the sense that graphs generated by this construction always have edge-admissibility at most 2 k − 1. Our proofs are based on a precise structural characterization of the graphs that do not contain θ r as an immersion, where θ r is the graph on two vertices and r parallel edges.

Details DOI

JMLR Journal 2020 Journal Article

GraKeL: A Graph Kernel Library in Python

Giannis Siglidis
Giannis Nikolentzos
Stratis Limnios
Christos Giatsidis
Konstantinos Skianis
Michalis Vazirgiannis

The problem of accurately measuring the similarity between graphs is at the core of many applications in a variety of disciplines. Graph kernels have recently emerged as a promising approach to this problem. There are now many kernels, each focusing on different structural aspects of graphs. Here, we present GraKeL, a library that unifies several graph kernels into a common framework. The library is written in Python and adheres to the scikit-learn interface. It is simple to use and can be naturally combined with scikit-learn's modules to build a complete machine learning pipeline for tasks such as graph classification and clustering. The code is BSD licensed and is available at: https://github.com/ysig/GraKeL. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2020. ( edit, beta )

PDF Details

IJCAI Conference 2018 Conference Paper

A Degeneracy Framework for Graph Similarity

Giannis Nikolentzos
Polykarpos Meladianos
Stratis Limnios
Michalis Vazirgiannis

The problem of accurately measuring the similarity between graphs is at the core of many applications in a variety of disciplines. Most existing methods for graph similarity focus either on local or on global properties of graphs. However, even if graphs seem very similar from a local or a global perspective, they may exhibit different structure at different scales. In this paper, we present a general framework for graph similarity which takes into account structure at multiple different scales. The proposed framework capitalizes on the well-known k-core decomposition of graphs in order to build a hierarchy of nested subgraphs. We apply the framework to derive variants of four graph kernels, namely graphlet kernel, shortest-path kernel, Weisfeiler-Lehman subtree kernel, and pyramid match graph kernel. The framework is not limited to graph kernels, but can be applied to any graph comparison algorithm. The proposed framework is evaluated on several benchmark datasets for graph classification. In most cases, the core-based kernels achieve significant improvements in terms of classification accuracy over the base kernels, while their time complexity remains very attractive.

PDF Details