Concept

Subgraph isomorphism problem

Related publications (28)

Equivariant Neural Architectures for Representing and Generating Graphs

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

EPFL2023

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in r ...

Assoc Computing Machinery2023

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

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

arXiv2023

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Efficient Streaming Subgraph Isomorphism with Graph Neural Networks

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do n ...

ASSOC COMPUTING MACHINERY2021

Holistic, Efficient, and Real-time Cleaning of Heterogeneous Data

Styliani Asimina Giannakopoulou

Data cleaning has become an indispensable part of data analysis due to the increasing amount of dirty data. Data scientists spend most of their time preparing dirty data before it can be used for data analysis. Existing solutions that attempt to automate t ...

EPFL2021

Atomic subgraphs and the statistical mechanics of networks

Sofia Charlotta Olhede

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...

2021

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021

Fast and Accurate Efficient Streaming Subgraph Isomorphism

Karl Aberer, Quoc Viet Hung Nguyen, Chi Thang Duong, Trung-Dung Hoang

2020

How hard is to distinguish graphs with graph neural networks?

Andreas Loukas

A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the maj ...

2020

RAQ: Relationship-Aware Graph Querying in Large Networks

Akhil Arora, Arnab Bhattacharya

The phenomenal growth of graph data from a wide variety of real-world applications has rendered graph querying to be a problem of paramount importance. Traditional techniques use structural as well as node similarities to find matches of a given query grap ...

ASSOC COMPUTING MACHINERY2019

Graph Learning with Partial Observations: Role of Degree Concentration

Ali H. Sayed, Augusto José Rabelo Almeida Santos

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections ...

IEEE2019

Time-resolved analysis of dynamic graphs: an extended Slepian design

Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois, Ibrahim Merad

Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...

SPIE-INT SOC OPTICAL ENGINEERING2019

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash, Osman Emre Dai

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

Graph Reduction with Spectral and Cut Guarantees

Andreas Loukas

Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for g ...

Microtome Publishing2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019