The Consistent Labeling Problem: Part II Haralick, Robert M.; Shapiro, Linda G.
IEEE transactions on pattern analysis and machine intelligence
PAMI-2, Issue:
3
Journal Article
Peer reviewed
In this second part of a two-part paper, we explore the power and complexity of the g=fKP and g=vKP class of look-ahead operators which can be used to speed up the tree search in the consistent ...labeling problem. For a specified K and P we show that the fixedpoint power of g=fKP and g=vKP is the same, that g=fKP+1 is at least as powerful as g=fKP, and that g=vK+1p is at least as powerful at g=fKP. Finally, we define a minimal compatibility relation and show how the standard tree search procedure for finding all the consistent labelings is quicker for a minimal relation. This leads to the concept of grading the complexity of compatibility relations according to how much look-ahead work it requires to reduce them to minimal relations and suggests that the reason look-ahead operators, such as Waltz filtering, work so well is that the compatibility relations used in practice are not very complex and are reducible to minimal or near minimal relations by a g=fKP or g=vKP look-ahead operator with small value for parameter P.
Subgraph Isomorphism
is a fundamental problem in graph data processing. Most existing subgraph isomorphism algorithms are based on a backtracking framework which computes the solutions by ...incrementally matching all query vertices to candidate data vertices. However, we observe that extensive duplicate computation exists in these algorithms, and such duplicate computation can be avoided by exploiting relationships between data vertices. Motivated by this, we propose a novel approach,
BoostIso
, to reduce duplicate computation. Our extensive experiments with real datasets show that, after integrating our approach, most existing subgraph isomorphism algorithms can be speeded up significantly, especially for some graphs with intensive vertex relationships, where the improvement can be up to several orders of magnitude.
•We propose SLF, a parallel approach for subgraph isomorphism algorithm based on tree searching.•We propose some strategies to reduce the sharing frequency and time spent sharing.•We analyze the ...parallelization overhead of SLF and previous methods.•The parallelization overhead of SLF is lower than previous methods’.
Subgraph isomorphism is one of the most important graph query operations. Existing subgraph isomorphic parallelization methods suffer from redundant sharing or fine-grained parallelism. SLF, a parallel approach for subgraph isomorphism algorithm based on tree-search, is proposed in this paper. In SLF, threads are prevented from sharing tasks blindly by an “Ask for Sharing” mechanism. The “Low-depth Priority Sharing” rule filters out unnecessary sharing, which reduces the number of sharing. The context of shared tasks is represented by embedding, which reduces the time and memory usage of sharing. We prove that the parallelization overhead of SLF is smaller than that of previous method. The experimental results show that SLF achieves higher speedup and efficiency than state-of-the-art parallelization methods.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Graphs have been used in different fields of research for performing structural analysis of various systems. In order to compare the structure of two systems, the correspondence between their graphs ...has to be verified. The problem of graph matching, especially subgraph isomorphism (SI), has been well studied in case of static graphs. However, many applications require incorporating temporal information, making the corresponding graphs dynamic. In this paper, we apply SI to detect dynamic patterns in dynamic graphs. We propose an algorithm for induced SI to detect all the matchings for a given pattern graph while considering snapshot-based representation of dynamic graphs and taking into account the chronological order of these snapshots. This is the novelty of the proposed approach since the existing state-of-the-art algorithms model dynamic graphs using an aggregated model with time-stamped edges. To the best of our knowledge, there does not exist another approach which considers snapshot-based representation of dynamic pattern and dynamic target graphs for this problem. We discussed the time complexity of our algorithm and tested its performance while comparing it with two existing algorithms using the real-world datasets. It was found that our algorithm is the second best overall in terms of the execution time. The results are promising given the fact that the choice of dynamic graph model affects the algorithmic design for solving the problem of SI. For the applications where aggregated model of dynamic graphs is not applicable and snapshot-based representation is indispensable, our algorithm can be directly applied as opposed to the existing ones.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
For p∈N, a coloring λ of the vertices of a graph G is p-centered if for every connected subgraph H of G, either H receives more than p colors under λ or there is a color that appears exactly once in ...H. Centered colorings play an important role in the theory of sparse graph classes introduced by Nešetřil and Ossona de Mendez 31,32, as they structurally characterize classes of bounded expansion — one of the key sparsity notions in this theory. More precisely, a class of graphs C has bounded expansion if and only if there is a function f:N→N such that every graph G∈C for every p∈N admits a p-centered coloring with at most f(p) colors. Unfortunately, known proofs for the existence of such colorings yield large upper bounds on the function f governing the number of colors needed, even for as simple classes as planar graphs. In this paper, we prove that every Kt-minor-free graph admits a p-centered coloring with O(pg(t)) colors for some function g. In the special case that the graph is embeddable in a fixed surface Σ we show that it admits a p-centered coloring with O(p19) colors, with the degree of the polynomial independent of the genus of Σ. This provides the first polynomial upper bounds on the number of colors needed in p-centered colorings of graphs drawn from proper minor-closed classes, which answers an open problem posed by Dvořák 1. As an algorithmic application, we use our main result to prove that if C is a fixed proper minor-closed class of graphs, then given graphs H and G, on p and n vertices, respectively, where G∈C, it can be decided whether H is a subgraph of G in time 2O(plogp)⋅nO(1) and space nO(1).
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
•We provide a non-trivial correction of an error in our previous work on subgraph isomorphism search over compressed graphs.•We provide experiments that verify that the effectiveness of our original ...approach is little affected by this correction.•We provide additional experiments that demonstrate the respective performance gains caused by the compression and the filtering steps, which are missing in the original paper.
We present a revised filtering process that corrects an error in our previous work on subgraph isomorphism search over compressed graphs. We provide additional experiments to test the contribution of the compression itself and the candidate filtering to the performance of four representative backtracking-based subgraph isomorphism search algorithms.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Graph databases are flexible NoSQL databases used to efficiently store and query complex and big data. One of the most difficult problems in graph databases is the problem of subgraph isomorphism, ...which involves finding a matching pattern in a given graph. Subgraph isomorphism algorithms generally encounter problems in the efficient processing of complex queries based on a lack of pruning methods and the use of a matching order. In this study, we present a new subgraph isomorphism approach based on the best-first search design strategy and name it BF-BigGraph. Our approach includes a machine learning technique to efficiently find the best matching order for various complex queries. The parameters we used in our approach as heuristics to improve the performance of complex queries on graph-based NoSQL databases are database volatility, database size, type of query, and the size of the query. We utilized the Random Forest machine learning method to narrow candidate nodes to a higher level of search and effectively reduce the search space for efficient querying and retrieval. We compared BF-BigGraph with state-of-the-art approaches, namely BB-Graph, Neo4j’s Cypher, DualIso, GraphQL, TurboIso, and VF3 using publicly available databases including undirected graphs; WorldCup, Pokec, Youtube, and a big graph database of a real demographic application (a population database) with approximately 70 million nodes of a big directed graph. The performance results of our approach for different types of complex queries on all these databases are significantly better in terms of computation time and required memory than other competing approaches in the literature.
•Introducing an efficient subgraph isomorphism method using best-first design strategy.•Approach uses random forest and centrality for diverse queries.•Evaluated on databases up to 70 million nodes, considering node size, volatility, and query type.•The approach was tested on databases from 45KB to 70M nodes.•BF-BigGraph showed superior efficiency in time and memory use.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
This paper presents a largely improved version of the VF2 algorithm for the Subgraph Isomorphism Problem. The improvements are twofold. Firstly, it is based on a new approach for determining the ...matching order of the nodes, and secondly, more efficient — nevertheless easier to compute — cutting rules are proposed. They together reduce the search space significantly.
In addition to the usual Subgraph Isomorphism Problem, the paper also presents specialized algorithms for the Induced Subgraph Isomorphism and for the Graph Isomorphism Problems.
Finally, an extensive experimental evaluation is provided using a wide range of inputs, including both real-life biological and chemical datasets and standard randomly generated graph series. The results show major and consistent running time improvements over the other known methods.
The C++ implementations of the algorithms are available open-source as part of the LEMON graph and network optimization library.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem—one of a very few problems in NP that is neither known to be solvable in polynomial ...time nor NP-complete—and two related Subgraph Isomorphism Problems that are NP-hard. Experimental results on two QUBO formulations of the Graph Isomorphism Problem suggest that our direct formulation is more practical than the others with respect to running on the D-Wave architecture.
•An efficient direct QUBO objective function F for the Graph Isomorphism Problem is proposed.•An efficient QUBO objective function F for the Graph Isomorphism Problem via reduction to the Clique Problem is proposed.•The above constructions have been extended for the (Induced) Subgraph Isomorphism Problem(s).•Experimental results comparing the efficiency of the QUBO formulations is pesented.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
