Taming Subgraph Isomorphism for RDF Query Processing [PDF]
Proceedings of the VLDB Endowment, 2015 RDF data are used to model knowledge in various areas such as life sciences, Semantic Web, bioinformatics, and social graphs. The size of real RDF data reaches billions of triples. This calls for a framework for efficiently processing RDF data. The core function of processing RDF data is subgraph pattern matching.
Jinha Kim +4 more
openalex +5 more sources
The Descriptive Complexity of Subgraph Isomorphism without Numerics [PDF]
Theory of Computing Systems, 2016 20 pages, 2 figures, 1 table. Sections 6 and 7.1 are new.
Oleg Verbitsky, Maksim Zhukovskii
openalex +6 more sources
Experimental Evaluation of Subgraph Isomorphism Solvers [PDF]
Workshop on Graph Based Representations in Pattern Recognition, 2019 Subgraph Isomorphism (SI) is an NP-complete problem which is at the heart of many structural pattern recognition tasks as it involves finding a copy of a pattern graph into a target graph. In the pattern recognition community, the most well-known SI solvers are VF2, VF3, and RI.
Christine Solnon
semanticscholar +3 more sources
SEGCN: a subgraph encoding based graph convolutional network model for social bot detection [PDF]
Scientific ReportsMessage passing neural networks such as graph convolutional networks (GCN) can jointly consider various types of features for social bot detection. However, the expressive power of GCN is upper-bounded by the 1st-order Weisfeiler–Leman isomorphism test ...
Feng Liu +5 more
doaj +2 more sources
DotMotif: an open-source tool for connectome subgraph isomorphism search and graph queries
Scientific Reports, 2020 Recent advances in neuroscience have enabled the exploration of brain structure at the level of individual synaptic connections. These connectomics datasets continue to grow in size and complexity; methods to search for and identify interesting graph ...
Jordan K. Matelsky +6 more
semanticscholar +2 more sources
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism [PDF]
, 2015 Let $H$ be a fixed graph on $n$ vertices. Let $f_H(G) = 1$ iff the input graph $G$ on $n$ vertices contains $H$ as a (not necessarily induced) subgraph. Let $\alpha_H$ denote the cardinality of a maximum independent set of $H$. In this paper we show: \[
Raghav Kulkarni, Supartha Podder
openalex +5 more sources
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [PDF]
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020 While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power
Giorgos Bouritsas +3 more
semanticscholar +1 more source
Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching [PDF]
AAAI Conference on Artificial Intelligence, 2021 Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications.
Xin Liu, Yangqiu Song
semanticscholar +1 more source
A Zero Knowledge Authentication Protocol Based on Novel Heuristic Algorithm of Dense Induced Subgraphs Isomorphism [PDF]
Engineering and Technology Journal, 2015 Graphs provide an useful mathematical tool for modeling various real world phenomena. Dense graphs arise in many places of interest, for instance the internet and social networks to name just two. The density of a graph should be a real number reflecting
N. M. G. Al-Saidi +2 more
doaj +1 more source
PathLAD+: An Improved Exact Algorithm for Subgraph Isomorphism Problem
International Joint Conference on Artificial Intelligence, 2023 The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers design various algorithms for solving SIP.
Yiyuan Wang +3 more
semanticscholar +1 more source