2 %% Copyright 2007, 2008, 2009 Elsevier Ltd
4 %% This file is part of the 'Elsarticle Bundle'.
5 %% ---------------------------------------------
7 %% It may be distributed under the conditions of the LaTeX Project Public
8 %% License, either version 1.2 of this license or (at your option) any
9 %% later version. The latest version of this license is in
10 %% http://www.latex-project.org/lppl.txt
11 %% and version 1.2 or later is part of all distributions of LaTeX
12 %% version 1999/12/01 or later.
14 %% The list of all files belonging to the 'Elsarticle Bundle' is
15 %% given in the file `manifest.txt'.
18 %% Template article for Elsevier's document class `elsarticle'
19 %% with numbered style bibliographic references
22 \documentclass[preprint,12pt]{elsarticle}
24 %% Use the option review to obtain double line spacing
25 %% \documentclass[authoryear,preprint,review,12pt]{elsarticle}
27 %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
28 %% for a journal layout:
29 %% \documentclass[final,1p,times]{elsarticle}
30 %% \documentclass[final,1p,times,twocolumn]{elsarticle}
31 %% \documentclass[final,3p,times]{elsarticle}
32 %% \documentclass[final,3p,times,twocolumn]{elsarticle}
33 %% \documentclass[final,5p,times]{elsarticle}
34 %% \documentclass[final,5p,times,twocolumn]{elsarticle}
36 %% For including figures, graphicx.sty has been loaded in
37 %% elsarticle.cls. If you prefer to use the old commands
38 %% please give \usepackage{epsfig}
40 %% The amssymb package provides various useful mathematical symbols
42 %% The amsthm package provides extended theorem environments
43 %% \usepackage{amsthm}
45 %% The lineno packages adds line numbers. Start line numbering with
46 %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
47 %% for the whole article with \linenumbers.
48 %% \usepackage{lineno}
51 %% \usepackage[pdftex]{graphicx}
54 \pgfplotsset{width=9cm}
55 \pgfplotsset{compat=1.8}
58 \usepackage{subcaption}
60 \usepackage{algorithm}
61 \usepackage{algpseudocode}
64 \usepackage{amsthm,amssymb}
65 \renewcommand{\qedsymbol}{\rule{0.7em}{0.7em}}
67 \newtheorem{theorem}{Theorem}[subsection]
68 \newtheorem{corollary}{Corollary}[theorem]
69 \newtheorem{claim}[theorem]{Claim}
71 \newtheorem{definition}{Definition}[subsection]
72 \newtheorem{notation}{Notation}[subsection]
73 \newtheorem{example}{Example}[subsection]
74 \usetikzlibrary{decorations.markings}
75 \let\oldproofname=\proofname
76 %% \renewcommand{\proofname}{\rm\bf{Proof:}}
78 \captionsetup{font=normalsize}
80 \journal{Discrete Applied Mathematics}
86 %% Title, authors and addresses
88 %% use the tnoteref command within \title for footnotes;
89 %% use the tnotetext command for theassociated footnote;
90 %% use the fnref command within \author or \address for footnotes;
91 %% use the fntext command for theassociated footnote;
92 %% use the corref command within \author for corresponding author footnotes;
93 %% use the cortext command for theassociated footnote;
94 %% use the ead command for the email address,
95 %% and the form \ead[url] for the home page:
96 %% \title{Title\tnoteref{label1}}
97 %% \tnotetext[label1]{}
98 %% \author{Name\corref{cor1}\fnref{label2}}
99 %% \ead{email address}
100 %% \ead[url]{home page}
103 %% \address{Address\fnref{label3}}
106 \title{Improved Algorithms for Matching Biological Graphs}
108 %% use optional labels to link authors explicitly to addresses:
109 %% \author[label1,label2]{}
110 %% \address[label1]{}
111 %% \address[label2]{}
113 \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}
115 \address{Dept of Operations Research, ELTE}
118 Subgraph isomorphism is a well-known NP-Complete problem, while its
119 special case, the graph isomorphism problem is one of the few problems
120 in NP neither known to be in P nor NP-Complete. Their appearance in
121 many fields of application such as pattern analysis, computer vision
122 questions and the analysis of chemical and biological systems has
123 fostered the design of various algorithms for handling special graph
126 The idea of using state space representation and checking some
127 conditions in each state to prune the search tree has made the VF2
128 algorithm one of the state of the art graph matching algorithms for
129 more than a decade. Recently, biological questions of ever increasing
130 importance have required more efficient, specialized algorithms.
132 This paper presents VF2++, a new algorithm based on the original VF2,
133 which runs significantly faster on most test cases and performs
134 especially well on special graph classes stemming from biological
135 questions. VF2++ handles graphs of thousands of nodes in practically
136 near linear time including preprocessing. Not only is it an improved
137 version of VF2, but in fact, it is by far the fastest existing
138 algorithm regarding biological graphs.
140 The reason for VF2++' superiority over VF2 is twofold. Firstly, taking
141 into account the structure and the node labeling of the graph, VF2++
142 determines a state order in which most of the unfruitful branches of
143 the search space can be pruned immediately. Secondly, introducing more
144 efficient - nevertheless still easier to compute - cutting rules
145 reduces the chance of going astray even further.
147 In addition to the usual subgraph isomorphism, specialized versions
148 for induced subgraph isomorphism and for graph isomorphism are
149 presented. VF2++ has gained a runtime improvement of one order of
150 magnitude respecting induced subgraph isomorphism and a better
151 asymptotical behaviour in the case of graph isomorphism problem.
153 After having provided the description of VF2++, in order to evaluate
154 its effectiveness, an extensive comparison to the contemporary other
155 algorithms is shown, using a wide range of inputs, including both real
156 life biological and chemical datasets and standard randomly generated
159 The work was motivated and sponsored by QuantumBio Inc., and all the
160 developed algorithms are available as the part of the open source
161 LEMON graph and network optimization library
162 (http://lemon.cs.elte.hu).
166 %% keywords here, in the form: keyword \sep keyword
168 %% PACS codes here, in the form: \PACS code \sep code
170 %% MSC codes here, in the form: \MSC code \sep code
171 %% or \MSC[2008] code \sep code (2000 is the default)
180 \section{Introduction}
183 In the last decades, combinatorial structures, and especially graphs
184 have been considered with ever increasing interest, and applied to the
185 solution of several new and revised questions. The expressiveness,
186 the simplicity and the studiedness of graphs make them practical for
187 modelling and appear constantly in several seemingly independent
188 fields. Bioinformatics and chemistry are amongst the most relevant
189 and most important fields.
191 Complex biological systems arise from the interaction and cooperation
192 of plenty of molecular components. Getting acquainted with such
193 systems at the molecular level has primary importance, since
194 protein-protein interaction, DNA-protein interaction, metabolic
195 interaction, transcription factor binding, neuronal networks, and
196 hormone signaling networks can be understood only this way.
198 For instance, a molecular structure can be considered as a graph,
199 whose nodes correspond to atoms and whose edges to chemical bonds. The
200 secondary structure of a protein can also be represented as a graph,
201 where nodes are associated with aminoacids and the edges with hydrogen
202 bonds. The nodes are often whole molecular components and the edges
203 represent some relationships among them. The similarity and
204 dissimilarity of objects corresponding to nodes are incorporated to
205 the model by \emph{node labels}. Many other chemical and biological
206 structures can easily be modeled in a similar way. Understanding such
207 networks basically requires finding specific subgraphs, which can not
208 avoid the application of graph matching algorithms.
210 Finally, let some of the other real-world fields related to some
211 variants of graph matching be briefly mentioned: pattern recognition
212 and machine vision \cite{HorstBunkeApplications}, symbol recognition
213 \cite{CordellaVentoSymbolRecognition}, face identification
214 \cite{JianzhuangYongFaceIdentification}. \\
216 Subgraph and induced subgraph matching problems are known to be
217 NP-Complete\cite{SubgraphNPC}, while the graph isomorphism problem is
218 one of the few problems in NP neither known to be in P nor
219 NP-Complete. Although polynomial time isomorphism algorithms are known
220 for various graph classes, like trees and planar
221 graphs\cite{PlanarGraphIso}, bounded valence
222 graphs\cite{BondedDegGraphIso}, interval graphs\cite{IntervalGraphIso}
223 or permutation graphs\cite{PermGraphIso}.
225 In the following, some algorithms based on other approaches are
226 summarized, which do not need any restrictions on the graphs. However,
227 an overall polynomial behaviour is not expectable from such an
228 alternative, it may often have good performance, even on a graph class
229 for which polynomial algorithm is known. Note that this summary
230 containing only exact matching algorithms is far not complete, neither
231 does it cover all the recent algorithms.
233 The first practically usable approach was due to
234 Ullmann\cite{Ullmann} which is a commonly used depth-first
235 search based algorithm with a complex heuristic for reducing the
236 number of visited states. A major problem is its $\Theta(n^3)$ space
237 complexity, which makes it impractical in the case of big sparse
240 In a recent paper, Ullmann\cite{UllmannBit} presents an
241 improved version of this algorithm based on a bit-vector solution for
242 the binary Constraint Satisfaction Problem.
244 The Nauty algorithm\cite{Nauty} transforms the two graphs to
245 a canonical form before starting to check for the isomorphism. It has
246 been considered as one of the fastest graph isomorphism algorithms,
247 although graph categories were shown in which it takes exponentially
248 many steps. This algorithm handles only the graph isomorphism problem.
250 The \emph{LAD} algorithm\cite{Lad} uses a depth-first search
251 strategy and formulates the matching as a Constraint Satisfaction
252 Problem to prune the search tree. The constraints are that the mapping
253 has to be injective and edge-preserving, hence it is possible to
254 handle new matching types as well.
256 The \textbf{RI} algorithm\cite{RI} and its variations are based on a
257 state space representation. After reordering the nodes of the graphs,
258 it uses some fast executable heuristic checks without using any
259 complex pruning rules. It seems to run really efficiently on graphs
260 coming from biology, and won the International Contest on Pattern
261 Search in Biological Databases\cite{Content}.
263 The currently most commonly used algorithm is the
264 \textbf{VF2}\cite{VF2}, the improved version of VF\cite{VF}, which was
265 designed for solving pattern matching and computer vision problems,
266 and has been one of the best overall algorithms for more than a
267 decade. Although, it can't be up to new specialized algorithms, it is
268 still widely used due to its simplicity and space efficiency. VF2 uses
269 a state space representation and checks some conditions in each state
270 to prune the search tree.
272 Our first graph matching algorithm was the first version of VF2 which
273 recognizes the significance of the node ordering, more opportunities
274 to increase the cutting efficiency and reduce its computational
275 complexity. This project was initiated and sponsored by QuantumBio
276 Inc.\cite{QUANTUMBIO} and the implementation --- along with a source
277 code --- has been published as a part of LEMON\cite{LEMON} open source
280 This paper introduces \textbf{VF2++}, a new further improved algorithm
281 for the graph and (induced)subgraph isomorphism problem, which uses
282 efficient cutting rules and determines a node order in which VF2 runs
283 significantly faster on practical inputs.
285 Meanwhile, another variant called \textbf{VF2 Plus}\cite{VF2Plus} has
286 been published. It is considered to be as efficient as the RI
287 algorithm and has a strictly better behavior on large graphs. The
288 main idea of VF2 Plus is to precompute a heuristic node order of the
289 small graph, in which the VF2 works more efficiently.
291 \section{Problem Statement}
292 This section provides a detailed description of the problems to be
294 \subsection{Definitions}
296 Throughout the paper $G_{small}=(V_{small}, E_{small})$ and
297 $G_{large}=(V_{large}, E_{large})$ denote two undirected graphs.
298 \begin{definition}\label{sec:ismorphic}
299 $G_{small}$ and $G_{large}$ are \textbf{isomorphic} if $\exists M:
300 V_{small} \longrightarrow V_{large}$ bijection, for which the
303 $\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow
304 (M(u),M(v))\in{E_{large}}$
307 For the sake of simplicity in this paper subgraphs and induced
308 subgraphs are defined in a more general way than usual:
310 $G_{small}$ is a \textbf{subgraph} of $G_{large}$ if $\exists I:
311 V_{small}\longrightarrow V_{large}$ injection, for which the
314 $\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Rightarrow (I(u),I(v))\in E_{large}$
319 $G_{small}$ is an \textbf{induced subgraph} of $G_{large}$ if $\exists
320 I: V_{small}\longrightarrow V_{large}$ injection, for which the
323 $\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow
324 (I(u),I(v))\in E_{large}$
329 $lab: (V_{small}\cup V_{large}) \longrightarrow K$ is a \textbf{node
330 label function}, where K is an arbitrary set. The elements in K
331 are the \textbf{node labels}. Two nodes, u and v are said to be
332 \textbf{equivalent}, if $lab(u)=lab(v)$.
335 When node labels are also given, the matched nodes must have the same
336 labels. For example, the node labeled isomorphism is phrased by
338 $G_{small}$ and $G_{large}$ are \textbf{isomorphic by the node label
339 function lab} if $\exists M: V_{small} \longrightarrow V_{large}$
340 bijection, for which the following is true:
342 $(\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow
343 (M(u),M(v))\in{E_{large}})$ and $(\forall u\in{V_{small}} :
348 The other two definitions can be extended in the same way.
350 Note that edge label function can be defined similarly to node label
351 function, and all the definitions can be extended with additional
352 conditions, but it is out of the scope of this work.
354 The equivalence of two nodes is usually defined by another relation,
355 $\\R\subseteq (V_{small}\cup V_{large})^2$. This overlaps with the
356 definition given above if R is an equivalence relation, which does not
357 mean restriction in biological and chemical applications.
359 \subsection{Common problems}\label{sec:CommProb}
361 The focus of this paper is on two extensively studied topics, the
362 subgraph isomorphism and its variations. However, the following
363 problems also appear in many applications.
365 The \textbf{subgraph matching problem} is the following: is
366 $G_{small}$ isomorphic to any subgraph of $G_{large}$ by a given node
369 The \textbf{induced subgraph matching problem} asks the same about the
370 existence of an induced subgraph.
372 The \textbf{graph isomorphism problem} can be defined as induced
373 subgraph matching problem where the sizes of the two graphs are equal.
375 In addition to existence, it may be needed to show such a subgraph, or
376 it may be necessary to list all of them.
378 It should be noted that some authors misleadingly refer to the term
379 \emph{subgraph isomorphism problem} as an \emph{induced subgraph
380 isomorphism problem}.
382 The following sections give the descriptions of VF2, VF2++, VF2 Plus
383 and a particular comparison.
385 \section{The VF2 Algorithm}
386 This algorithm is the basis of both the VF2++ and the VF2 Plus. VF2
387 is able to handle all the variations mentioned in Section
388 \ref{sec:CommProb}. Although it can also handle directed graphs,
389 for the sake of simplicity, only the undirected case will be
393 \subsection{Common notations}
394 \indent Assume $G_{small}$ is searched in $G_{large}$. The following
395 definitions and notations will be used throughout the whole paper.
397 A set $M\subseteq V_{small}\times V_{large}$ is called
398 \textbf{mapping}, if no node of $V_{small}$ or of $V_{large}$ appears
399 in more than one pair in M. That is, M uniquely associates some of
400 the nodes in $V_{small}$ with some nodes of $V_{large}$ and vice
405 Mapping $M$ \textbf{covers} a node v, if there exists a pair in M, which
410 A mapping $M$ is $\mathbf{whole\ mapping}$, if $M$ covers all the
411 nodes in $V_{small}$.
415 Let $\mathbf{M_{small}(s)} := \{u\in V_{small} : \exists v\in
416 V_{large}: (u,v)\in M(s)\}$ and $\mathbf{M_{large}(s)} := \{v\in
417 V_{large} : \exists u\in V_{small}: (u,v)\in M(s)\}$.
421 Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$, if such a node
422 exist, otherwise $\mathbf{Pair(M,v)}$ is undefined. For a mapping $M$
423 and $v\in V_{small}\cup V_{large}$.
426 Note that if $\mathbf{Pair(M,v)}$ exists, then it is unique
428 The definitions of the isomorphism types can be rephrased on the
429 existence of a special whole mapping $M$, since it represents a
430 bijection. For example
432 $M\subseteq V_{small}\times V_{large}$ represents an induced subgraph
433 isomorphism $\Leftrightarrow$ $M$ is whole mapping and $\forall u,v
434 \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow
435 (Pair(M,u),Pair(M,v))\in E_{large}$.
438 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type
439 which can be substituted by any of $\mathbf{ISO}$, $\mathbf{SUB}$
443 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a
444 \textbf{consistency function by } $\mathbf{PT}$, if the following
445 holds. If there exists whole mapping $W$ of type $PT$ for which
446 $M\subseteq W$, then $Cons_{PT}(M)$ is true.
450 Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a
451 \textbf{cutting function by } $\mathbf{PT}$, if the following
452 holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a
453 whole mapping $W$ of type $PT$.
457 $M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if
458 $Cons_{PT}(M)$ is true.
461 $Cons_{PT}$ and $Cut_{PT}$ will often be used in the following form.
463 Let $\mathbf{Cons_{PT}(p, M)}:=Cons_{PT}(M\cup\{p\})$ and
464 $\mathbf{Cut_{PT}(p, M)}:=Cut_{PT}(M\cup\{p\})$, where
465 $p\in{V_{small}\!\times\!V_{large}}$ and $M\cup\{p\}$ is mapping.
468 $Cons_{PT}$ will be used to check the consistency of the already
469 covered nodes, while $Cut_{PT}$ is for looking ahead to recognize if
470 no whole consistent mapping can contain the current mapping.
472 \subsection{Overview of the algorithm}
473 VF2 uses a state space representation of mappings, $Cons_{PT}$ for
474 excluding inconsistency with the problem type and $Cut_{PT}$ for
475 pruning the search tree. Each state $s$ of the matching process can
476 be associated with a mapping $M(s)$.
478 Algorithm~\ref{alg:VF2Pseu} is a high level description of
479 the VF2 matching algorithm.
483 \algtext*{EndIf}%ne nyomtasson end if-et
485 \algtext*{EndProcedure}%ne nyomtasson ..
486 \caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu}
487 \begin{algorithmic}[1]
489 \Procedure{VF2}{State $s$, ProblemType $PT$} \If{$M(s$) covers
490 $V_{small}$} \State Output($M(s)$) \Else
492 \State Compute the set $P(s)$ of the pairs candidate for inclusion
493 in $M(s)$ \ForAll{$p\in{P(s)}$} \If{Cons$_{PT}$($p, M(s)$) $\wedge$
494 $\neg$Cut$_{PT}$($p, M(s)$)} \State Compute the nascent state
495 $\tilde{s}$ by adding $p$ to $M(s)$ \State \textbf{call}
496 VF2($\tilde{s}$, $PT$) \EndIf \EndFor \EndIf \EndProcedure
501 The initial state $s_0$ is associated with $M(s_0)=\emptyset$, i.e. it
502 starts with an empty mapping.
504 For each state $s$, the algorithm computes $P(s)$, the set of
505 candidate node pairs for adding to the current state $s$.
507 For each pair $p$ in $P(s)$, $Cons_{PT}(p,M(s))$ and
508 $Cut_{PT}(p,M(s))$ are evaluated. If $Cons_{PT}(p,M(s))$ is true and
509 $Cut_{PT}(p,M(s))$ is false, the successor state $\tilde{s}=s\cup
510 \{p\}$ is computed, and the whole process is recursively applied to
511 $\tilde{s}$. Otherwise, $\tilde{s}$ is not consistent by $PT$ or it
512 can be proved that $s$ can not be extended to a whole mapping.
514 In order to make sure of the correctness, see
516 Through consistent mappings, only consistent whole mappings can be
517 reached, and all of the whole mappings are reachable through
521 Note that a state may be reached in many different ways, since the
522 order of insertions into M does not influence the nascent mapping. In
523 fact, the number of different ways which lead to the same state can be
524 exponentially large. If $G_{small}$ and $G_{large}$ are circles with n
525 nodes and n different node labels, there exists exactly one graph
526 isomorphism between them, but it will be reached in $n!$ different
529 However, one may observe
532 \label{claim:claimTotOrd}
533 Let $\prec$ an arbitrary total ordering relation on $V_{small}$. If
534 the algorithm ignores each $p=(u,v) \in P(s)$, for which
536 $\exists (\hat{u},\hat{v})\in P(s): \hat{u} \prec u$,
538 then no state can be reached more than ones and each state associated
539 with a whole mapping remains reachable.
542 Note that the cornerstone of the improvements to VF2 is a proper
543 choice of a total ordering.
545 \subsection{The candidate set P(s)}
546 \label{candidateComputingVF2}
547 Let $P(s)$ be the set of the candidate pairs for inclusion in $M(s)$.
550 Let $\mathbf{T_{small}(s)}:=\{u \in V_{small} : u$ is not covered by
551 $M(s)\wedge\exists \tilde{u}\in{V_{small}: (u,\tilde{u})\in E_{small}}
552 \wedge \tilde{u}$ is covered by $M(s)\}$, and
553 \\ $\mathbf{T_{large}(s)}\!:=\!\{v \in\!V_{large}\!:\!v$ is not
555 $M(s)\wedge\!\exists\tilde{v}\!\in\!{V_{large}\!:\!(v,\tilde{v})\in\!E_{large}}
556 \wedge \tilde{v}$ is covered by $M(s)\}$
559 The set $P(s)$ includes the pairs of uncovered neighbours of covered
560 nodes and if there is not such a node pair, all the pairs containing
561 two uncovered nodes are added. Formally, let
565 T_{small}(s)\times T_{large}(s)&\hspace{-0.15cm}\text{if }
566 T_{small}(s)\!\neq\!\emptyset\!\wedge\!T_{large}(s)\!\neq
567 \emptyset,\\ (V_{small}\!\setminus\!M_{small}(s))\!\times\!(V_{large}\!\setminus\!M_{large}(s))
568 &\hspace{-0.15cm}otherwise.
572 \subsection{Consistency}
573 This section defines the consistency functions for the different
574 problem types mentioned in Section~\ref{sec:CommProb}.
576 Let $\mathbf{\Gamma_{small} (u)}:=\{\tilde{u}\in V_{small} :
577 (u,\tilde{u})\in E_{small}\}$\\ Let $\mathbf{\Gamma_{large}
578 (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$
580 Suppose $p=(u,v)$, where $u\in V_{small}$ and $v\in V_{large}$, $s$ is
581 a state of the matching procedure, $M(s)$ is consistent mapping by
582 $PT$ and $lab(u)=lab(v)$. $Cons_{PT}(p,M(s))$ checks whether
583 including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.
585 \subsubsection{Induced subgraph isomorphism}
586 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow
587 (\forall \tilde{u}\in M_{small}: (u,\tilde{u})\in E_{small}
588 \Leftrightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.\newline The
589 following formulation gives an efficient way of calculating
592 $Cons_{IND}((u,v),M(s)):=(\forall \tilde{v}\in \Gamma_{large}(v)
593 \ \cap\ M_{large}(s):\\(Pair(M(s),\tilde{v}),u)\in E_{small})\wedge
594 (\forall \tilde{u}\in \Gamma_{small}(u)
595 \ \cap\ M_{small}(s):(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a
596 consistency function in the case of $IND$.
599 \subsubsection{Graph isomorphism}
600 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $ISO$
601 $\Leftrightarrow$ $M(s)\cup \{(u,v)\}$ is a consistent mapping by
604 $Cons_{ISO}((u,v),M(s))$ is a consistency function by $ISO$ if and
605 only if it is a consistency function by $IND$.
607 \subsubsection{Subgraph isomorphism}
608 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $SUB$ $\Leftrightarrow
609 (\forall \tilde{u}\in M_{small}:\\(u,\tilde{u})\in E_{small}
610 \Rightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.
612 The following formulation gives an efficient way of calculating
615 $Cons_{SUB}((u,v),M(s)):= (\forall \tilde{u}\in \Gamma_{small}(u)
616 \ \cap\ M_{small}(s):\\(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a
617 consistency function by $SUB$.
620 \subsection{Cutting rules}
621 $Cut_{PT}(p,M(s))$ is defined by a collection of efficiently
622 verifiable conditions. The requirement is that $Cut_{PT}(p,M(s))$ can
623 be true only if it is impossible to extended $M(s)\cup \{p\}$ to a
627 Let $\mathbf{\tilde{T}_{small}}(s):=(V_{small}\backslash
628 M_{small}(s))\backslash T_{small}(s)$, and
629 \\ $\mathbf{\tilde{T}_{large}}(s):=(V_{large}\backslash
630 M_{large}(s))\backslash T_{large}(s)$.
632 \subsubsection{Induced subgraph isomorphism}
634 $Cut_{IND}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
635 |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
636 \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap
637 \tilde{T}_{small}(s)|$ is a cutting function by $IND$.
639 \subsubsection{Graph isomorphism}
640 Note that the cutting function of induced subgraph isomorphism defined
641 above is a cutting function by $ISO$, too, however it is less
642 efficient than the following while their computational complexity is
645 $Cut_{ISO}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| \neq
646 |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
647 \tilde{T}_{large}(s)| \neq |\Gamma_{small}(u)\cap
648 \tilde{T}_{small}(s)|$ is a cutting function by $ISO$.
651 \subsubsection{Subgraph isomorphism}
653 $Cut_{SUB}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
654 |\Gamma_{small} (u)\ \cap\ T_{small}(s)|$ is a cutting function by
657 Note that there is a significant difference between induced and
658 non-induced subgraph isomorphism:
662 $Cut_{SUB}'((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <
663 |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap
664 \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap \tilde{T}_{small}(s)|$
665 is \textbf{not} a cutting function by $SUB$.
668 \section{The VF2++ Algorithm}
669 Although any total ordering relation makes the search space of VF2 a
670 tree, its choice turns out to dramatically influence the number of
671 visited states. The goal is to determine an efficient one as quickly
674 The main reason for VF2++' superiority over VF2 is twofold. Firstly,
675 taking into account the structure and the node labeling of the graph,
676 VF2++ determines a state order in which most of the unfruitful
677 branches of the search space can be pruned immediately. Secondly,
678 introducing more efficient --- nevertheless still easier to compute
679 --- cutting rules reduces the chance of going astray even further.
681 In addition to the usual subgraph isomorphism, specialized versions
682 for induced subgraph isomorphism and for graph isomorphism have been
683 designed. VF2++ has gained a runtime improvement of one order of
684 magnitude respecting induced subgraph isomorphism and a better
685 asymptotical behaviour in the case of graph isomorphism problem.
687 Note that a weaker version of the cutting rules and the more efficient
688 candidate set calculating were described in \cite{VF2Plus}, too.
690 It should be noted that all the methods described in this section are
691 extendable to handle directed graphs and edge labels as well.
693 The basic ideas and the detailed description of VF2++ are provided in
696 \subsection{Preparations}
698 \label{claim:claimCoverFromLeft}
699 The total ordering relation uniquely determines a node order, in which
700 the nodes of $V_{small}$ will be covered by VF2. From the point of
701 view of the matching procedure, this means, that always the same node
702 of $G_{small}$ will be covered on the d-th level.
706 An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
707 $V_{small}$ is \textbf{matching order}, if exists $\prec$ total
708 ordering relation, s.t. the VF2 with $\prec$ on the d-th level finds
709 pair for $u_{\sigma(d)}$ for all $d\in\{1,..,|V_{small}|\}$.
712 \begin{claim}\label{claim:MOclaim}
713 A total ordering is matching order, iff the nodes of every component
714 form an interval in the node sequence, and every node connects to a
715 previous node in its component except the first node of the
716 component. The order of the components is arbitrary. \\Formally
718 $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
719 $V_{small}$ is matching order $\Leftrightarrow$ $\forall
720 G'_{small}=(V'_{small},E'_{small})\ component\ of\ G_{small}: \forall
721 i: (\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in
722 V'_{small})\Rightarrow \exists k : k < i \wedge (\forall l: k\leq
723 l\leq i \Rightarrow u_{l}\in V'_{small}) \wedge
724 (u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in
725 \{1,..,|V_{small}|\}$\newline
728 To summing up, a total ordering always uniquely determines a matching
729 order, and every matching order can be determined by a total ordering,
730 however, more than one different total orderings may determine the
732 \subsection{Idea behind the algorithm}
733 The goal is to find a matching order in which the algorithm is able to
734 recognize inconsistency or prune the infeasible branches on the
735 highest levels and goes deep only if it is needed.
738 Let $\mathbf{Conn_{H}(u)}:=|\Gamma_{small}(u)\cap H\}|$, that is the
739 number of neighbours of u which are in H, where $u\in V_{small} $ and
740 $H\subseteq V_{small}$.
743 The principal question is the following. Suppose a state $s$ is
744 given. For which node of $T_{small}(s)$ is the hardest to find a
745 consistent pair in $G_{large}$? The more covered neighbours a node in
746 $T_{small}(s)$ has --- i.e. the largest $Conn_{M_{small}(s)}$ it has
747 ---, the more rarely satisfiable consistency constraints for its pair
750 In biology, most of the graphs are sparse, thus several nodes in
751 $T_{small}(s)$ may have the same $Conn_{M_{small}(s)}$, which makes
752 reasonable to define a secondary and a tertiary order between them.
753 The observation above proves itself to be as determining, that the
754 secondary ordering prefers nodes with the most uncovered neighbours
755 among which have the same $Conn_{M_{small}(s)}$ to increase
756 $Conn_{M_{small}(s)}$ of uncovered nodes so much, as possible. The
757 tertiary ordering prefers nodes having the rarest uncovered labels.
759 Note that the secondary ordering is the same as the ordering by $deg$,
760 which is a static data in front of the above used.
762 These rules can easily result in a matching order which contains the
763 nodes of a long path successively, whose nodes may have low $Conn$ and
764 is easily matchable into $G_{large}$. To avoid that, a BFS order is
765 used, which provides the shortest possible paths.
768 In the following, some examples on which the VF2 may be slow are
769 described, although they are easily solvable by using a proper
773 Suppose $G_{small}$ can be mapped into $G_{large}$ in many ways
774 without node labels. Let $u\in V_{small}$ and $v\in V_{large}$.
780 $lab(\tilde{u}):=red \ \forall \tilde{u}\in (V_{small}\backslash
783 $lab(\tilde{v}):=red \ \forall \tilde{v}\in (V_{large}\backslash
787 Now, any mapping by the node label $lab$ must contain $(u,v)$, since
788 $u$ is black and no node in $V_{large}$ has a black label except
789 $v$. If unfortunately $u$ were the last node which will get covered,
790 VF2 would check only in the last steps, whether $u$ can be matched to
793 However, had $u$ been the first matched node, u would have been
794 matched immediately to v, so all the mappings would have been
795 precluded in which node labels can not correspond.
799 Suppose there is no node label given, $G_{small}$ is a small graph and
800 can not be mapped into $G_{large}$ and $u\in V_{small}$.
802 Let $G'_{small}:=(V_{small}\cup
803 \{u'_{1},u'_{2},..,u'_{k}\},E_{small}\cup
804 \{(u,u'_{1}),(u'_{1},u'_{2}),..,(u'_{k-1},u'_{k})\})$, that is,
805 $G'_{small}$ is $G_{small}\cup \{ a\ k$ long path, which is disjoint
806 from $G_{small}$ and one of its starting points is connected to $u\in
809 Is there a subgraph of $G_{large}$, which is isomorph with
812 If unfortunately the nodes of the path were the first $k$ nodes in the
813 matching order, the algorithm would iterate through all the possible k
814 long paths in $G_{large}$, and it would recognize that no path can be
815 extended to $G'_{small}$.
817 However, had it started by the matching of $G_{small}$, it would not
818 have matched any nodes of the path.
821 These examples may look artificial, but the same problems also appear
822 in real-world instances, even though in a less obvious way.
824 \subsection{Total ordering}
825 Instead of the total ordering relation, the matching order will be
828 Let \textbf{F$_\mathcal{M}$(l)}$:=|\{v\in V_{large} :
829 l=lab(v)\}|-|\{u\in V_{small}\backslash \mathcal{M} : l=lab(u)\}|$ ,
830 where $l$ is a label and $\mathcal{M}\subseteq V_{small}$.
833 \begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u : u\in S \wedge f(u)=max_{v\in S}\{f(v)\}\}$ and $\mathbf{arg\ min}_{f}(S) := arg\ max_{-f}(S)$, where $S$ is a finite set and $f:S\longrightarrow \mathbb{R}$.
838 \algtext*{EndProcedure}
841 \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}
842 \begin{algorithmic}[1]
843 \Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$
844 \Comment{matching order} \While{$V_{small}\backslash \mathcal{M}
845 \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg
846 min$_{F_\mathcal{M}\circ lab}(V_{small}\backslash
847 \mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with
848 root node $r$. \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the
849 $d$-th level \State Process $V_d$ \Comment{See Algorithm
850 \ref{alg:VF2PPProcess1}} \EndFor
851 \EndWhile \EndProcedure
857 \algtext*{EndProcedure}%ne nyomtasson ..
859 \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
860 \begin{algorithmic}[1]
861 \Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}
862 \State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg
863 max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$
864 \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh
865 $F_\mathcal{M}$ \EndWhile \EndProcedure
869 Algorithm~\ref{alg:VF2PPPseu} is a high level description of the
870 matching order procedure of VF2++. It computes a BFS tree for each
871 component in ascending order of their rarest $lab$ and largest $deg$,
872 whose root vertex is the component's minimal
873 node. Algorithm~\ref{alg:VF2PPProcess1} is a method to process a level of the BFS tree, which appends the nodes of the current level in descending
874 lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately
875 to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.
877 Claim~\ref{claim:MOclaim} shows that Algorithm~\ref{alg:VF2PPPseu}
878 provides a matching order.
881 \subsection{Cutting rules}
882 \label{VF2PPCuttingRules}
883 This section presents the cutting rules of VF2++, which are improved
884 by using extra information coming from the node labels.
886 Let $\mathbf{\Gamma_{small}^{l}(u)}:=\{\tilde{u} : lab(\tilde{u})=l
887 \wedge \tilde{u}\in \Gamma_{small} (u)\}$ and
888 $\mathbf{\Gamma_{large}^{l}(v)}:=\{\tilde{v} : lab(\tilde{v})=l \wedge
889 \tilde{v}\in \Gamma_{large} (v)\}$, where $u\in V_{small}$, $v\in
890 V_{large}$ and $l$ is a label.
893 \subsubsection{Induced subgraph isomorphism}
895 \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND.
898 \subsubsection{Graph isomorphism}
900 \[LabCut_{ISO}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!\neq\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| \neq |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by ISO.
903 \subsubsection{Subgraph isomorphism}
905 \[LabCut_{SUB}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\] is a cutting function by SUB.
910 \subsection{Implementation details}
911 This section provides a detailed summary of an efficient
912 implementation of VF2++.
913 \subsubsection{Storing a mapping}
914 After fixing an arbitrary node order ($u_0, u_1, ..,
915 u_{|G_{small}|-1}$) of $G_{small}$, an array $M$ is usable to store
916 the current mapping in the following way.
920 v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INVALID &
921 if\ no\ node\ has\ been\ mapped\ to\ u_i.
924 Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
926 \subsubsection{Avoiding the recurrence}
927 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
928 as a \textit{while loop}, which has a loop counter $depth$ denoting the
929 all-time depth of the recursion. Fixing a matching order, let $M$
930 denote the array storing the all-time mapping. Based on Claim~\ref{claim:claimCoverFromLeft},
931 $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before
932 $depth$. $M[depth]$ changes
933 while the state is being processed, but the property is held before
934 both stepping back to a predecessor state and exploring a successor
937 The necessary part of the candidate set is easily maintainable or
938 computable by following
939 Section~\ref{candidateComputingVF2}. A much faster method
940 has been designed for biological- and sparse graphs, see the next
943 \subsubsection{Calculating the candidates for a node}
944 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the
945 task is not to maintain the candidate set, but to generate the
946 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$. In
947 case of any of the three problem type and a mapping $M$, if a node $v\in
948 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall
949 u'\in V_{small} : (u,u')\in
950 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in
951 E_{large}$. That is, each covered neighbour of $u$ has to be mapped to
952 a covered neighbour of $v$.
954 Having said that, an algorithm running in $\Theta(deg)$ time is
955 describable if there exists a covered node in the component containing
956 $u$, and a linear one other wise.
959 \subsubsection{Determining the node order}
960 This section describes how the node order preprocessing method of
961 VF2++ can efficiently be implemented.
963 For using lookup tables, the node labels are associated with the
964 numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It
965 enables $F_\mathcal{M}$ to be stored in an array. At first, the node order
966 $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes
967 in $V_{small}$ having label i, which is easy to compute in
968 $\Theta(|V_{small}|)$ steps.
970 Representing $\mathcal{M}\subseteq V_{small}$ as an array of
971 size $|V_{small}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.
973 \subsubsection{Cutting rules}
974 In Section~\ref{VF2PPCuttingRules}, the cutting rules were
975 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$
976 and $\tilde T_{large}$, which are dependent on the all-time mapping
977 (i.e. on the all-time state). The aim is to check the labeled cutting
978 rules of VF2++ in $\Theta(deg)$ time.
980 Firstly, suppose that these four sets are given in such a way, that
981 checking whether a node is in a certain set takes constant time,
982 e.g. they are given by their 0-1 characteristic vectors. Let $L$ be an
983 initially zero integer lookup table of size $|K|$. After incrementing
984 $L[lab(u')]$ for all $u'\in \Gamma_{small}(u) \cap T_{small}(s)$ and
985 decrementing $L[lab(v')]$ for all $v'\in\Gamma_{large} (v) \cap
986 T_{large}(s)$, the first part of the cutting rules is checkable in
987 $\Theta(deg)$ time by considering the proper signs of $L$. Setting $L$
988 to zero takes $\Theta(deg)$ time again, which makes it possible to use
989 the same table through the whole algorithm. The second part of the
990 cutting rules can be verified using the same method with $\tilde
991 T_{small}$ and $\tilde T_{large}$ instead of $T_{small}$ and
992 $T_{large}$. Thus, the overall complexity is $\Theta(deg)$.
994 An other integer lookup table storing the number of covered neighbours
995 of each node in $G_{large}$ gives all the information about the sets
996 $T_{large}$ and $\tilde T_{large}$, which is maintainable in
997 $\Theta(deg)$ time when a pair is added or substracted by incrementing
998 or decrementing the proper indices. A further improvement is that the
999 values of $L[lab(u')]$ in case of checking $u$ is dependent only on
1000 $u$, i.e. on the size of the mapping, so for each $u\in V_{small}$ an
1001 array of pairs (label, number of such labels) can be stored to skip
1002 the maintaining operations. Note that these arrays are at most of size
1003 $deg$. Skipping this trick, the number of covered neighbours has to be
1004 stored for each node of $G_{small}$ as well to get the sets
1005 $T_{small}$ and $\tilde T_{small}$.
1007 Using similar tricks, the consistency function can be evaluated in
1008 $\Theta(deg)$ steps, as well.
1010 \section{The VF2 Plus Algorithm}
1011 The VF2 Plus algorithm is a recently improved version of VF2. It was
1012 compared with the state of the art algorithms in \cite{VF2Plus} and
1013 has proven itself to be competitive with RI, the best algorithm on
1014 biological graphs. \\ A short summary of VF2 Plus follows, which uses
1015 the notation and the conventions of the original paper.
1017 \subsection{Ordering procedure}
1018 VF2 Plus uses a sorting procedure that prefers nodes in $V_{small}$
1019 with the lowest probability to find a pair in $V_{small}$ and the
1020 highest number of connections with the nodes already sorted by the
1024 $(u,v)$ is a \textbf{feasible pair}, if $lab(u)=lab(v)$ and
1025 $deg(u)\leq deg(v)$, where $u\in{V_{small}}$ and $ v\in{V_{large}}$.
1027 $P_{lab}(L):=$ a priori probability to find a node with label $L$ in
1030 $P_{deg}(d):=$ a priori probability to find a node with degree $d$ in
1033 $P(u):=P_{lab}(L)*\bigcup_{d'>d}P_{deg}(d')$\\ $M$ is the set of
1034 already sorted nodes, $T$ is the set of nodes candidate to be
1035 selected, and $degreeM$ of a node is the number of its neighbours in
1038 \algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
1039 nyomtasson .. \algtext*{EndProcedure}%ne nyomtasson ..
1041 \caption{}\label{alg:VF2PlusPseu}
1042 \begin{algorithmic}[1]
1043 \Procedure{VF2 Plus order}{} \State Select the node with the lowest
1044 $P$. \If {more nodes share the same $P$} \State select the one with
1045 maximum degree \EndIf \If {more nodes share the same $P$ and have the
1046 max degree} \State select the first \EndIf \State Put the selected
1047 node in the set $M$. \label{alg:putIn} \State Put all its unsorted
1048 neighbours in the set $T$. \If {$M\neq V_{small}$} \State From set
1049 $T$ select the node with maximum $degreeM$. \If {more nodes have
1050 maximum $degreeM$} \State Select the one with the lowest $P$ \EndIf
1051 \If {more nodes have maximum $degreeM$ and $P$} \State Select the
1052 first. \EndIf \State \textbf{goto \ref{alg:putIn}.} \EndIf
1057 Using these notations, Algorithm~\ref{alg:VF2PlusPseu}
1058 provides the description of the sorting procedure.
1060 Note that $P(u)$ is not the exact probability of finding a consistent
1061 pair for $u$ by choosing a node of $V_{large}$ randomly, since
1062 $P_{lab}$ and $P_{deg}$ are not independent, though calculating the
1063 real probability would take quadratic time, which may be reduced by
1064 using fittingly lookup tables.
1066 \section{Experimental results}
1067 This section compares the performance of VF2++ and VF2 Plus. Both
1068 algorithms have run faster with orders of magnitude than VF2, thus its
1069 inclusion was not reasonable.
1070 \subsection{Biological graphs}
1071 The tests have been executed on a recent biological dataset created
1072 for the International Contest on Pattern Search in Biological
1073 Databases\cite{Content}, which has been constructed of molecule,
1074 protein and contact map graphs extracted from the Protein Data
1075 Bank\cite{ProteinDataBank}.
1077 The molecule dataset contains small graphs with less than 100 nodes
1078 and an average degree of less than 3. The protein dataset contains
1079 graphs having 500-10 000 nodes and an average degree of 4, while the
1080 contact map dataset contains graphs with 150-800 nodes and an average
1083 In the following, the induced subgraph isomorphism and the graph
1084 isomorphism will be examined.
1086 This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For run time results, please see Figure~\ref{fig:bioIND}.
1088 In an other experiment, the nodes of each graph in the database had been
1089 shuffled, and an isomorphism between the shuffled and the original
1090 graph was searched. The solution times are shown on Figure~\ref{fig:bioISO}.
1097 \begin{subfigure}[b]{0.55\textwidth}
1099 \begin{tikzpicture}[trim axis left, trim axis right]
1100 \begin{axis}[title=Molecules ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1101 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1102 west},scaled x ticks = false,x tick label style={/pgf/number
1103 format/1000 sep = \thinspace}]
1104 %\addplot+[only marks] table {proteinsOrig.txt};
1105 \addplot table {Orig/moleculesIso.txt}; \addplot[mark=triangle*,mark
1106 size=1.8pt,color=red] table {VF2PPLabel/moleculesIso.txt};
1109 \caption{In the case of molecules, there is not such a significant
1110 difference, but VF2++ seems to be faster as the number of nodes
1111 increases.}\label{fig:ISOMolecule}
1115 \begin{subfigure}[b]{0.55\textwidth}
1117 \begin{tikzpicture}[trim axis left, trim axis right]
1118 \begin{axis}[title=Contact maps ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1119 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1120 west},scaled x ticks = false,x tick label style={/pgf/number
1121 format/1000 sep = \thinspace}]
1122 %\addplot+[only marks] table {proteinsOrig.txt};
1123 \addplot table {Orig/contactMapsIso.txt}; \addplot[mark=triangle*,mark
1124 size=1.8pt,color=red] table {VF2PPLabel/contactMapsIso.txt};
1127 \caption{The results are closer to each other on contact maps, but
1128 VF2++ still performs consistently better.}\label{fig:ISOContact}
1134 \begin{subfigure}[b]{0.55\textwidth}
1136 \begin{tikzpicture}[trim axis left, trim axis right]
1137 \begin{axis}[title=Proteins ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1138 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1139 west},scaled x ticks = false,x tick label style={/pgf/number
1140 format/1000 sep = \thinspace}]
1141 %\addplot+[only marks] table {proteinsOrig.txt};
1142 \addplot table {Orig/proteinsIso.txt}; \addplot[mark=triangle*,mark
1143 size=1.8pt,color=red] table {VF2PPLabel/proteinsIso.txt};
1146 \caption{On protein graphs, VF2 Plus has a super linear time
1147 complexity, while VF2++ runs in near constant time. The difference
1148 is about two order of magnitude on large graphs.}\label{fig:ISOProt}
1153 \caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioISO}
1160 \begin{subfigure}[b]{0.55\textwidth}
1162 \begin{tikzpicture}[trim axis left, trim axis right]
1163 \begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1164 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1165 west},scaled x ticks = false,x tick label style={/pgf/number
1166 format/1000 sep = \thinspace}]
1167 %\addplot+[only marks] table {proteinsOrig.txt};
1168 \addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
1169 size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
1172 \caption{In the case of molecules, the algorithms have
1173 similar behaviour, but VF2++ is almost two times faster even on such
1174 small graphs.} \label{fig:INDMolecule}
1178 \begin{subfigure}[b]{0.55\textwidth}
1180 \begin{tikzpicture}[trim axis left, trim axis right]
1181 \begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1182 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1183 west},scaled x ticks = false,x tick label style={/pgf/number
1184 format/1000 sep = \thinspace}]
1185 %\addplot+[only marks] table {proteinsOrig.txt};
1186 \addplot table {Orig/ContactMaps.128.txt};
1187 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1188 {VF2PPLabel/ContactMaps.128.txt};
1191 \caption{On contact maps, VF2++ runs in near constant time, while VF2
1192 Plus has a near linear behaviour.} \label{fig:INDContact}
1198 \begin{subfigure}[b]{0.55\textwidth}
1200 \begin{tikzpicture}[trim axis left, trim axis right]
1201 \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1202 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1203 west},scaled x ticks = false,x tick label style={/pgf/number
1204 format/1000 sep = \thinspace}] %\addplot+[only marks] table
1205 {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
1206 table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
1207 size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
1210 \caption{Both the algorithms have linear behaviour on protein
1211 graphs. VF2++ is more than 10 times faster than VF2
1212 Plus.} \label{fig:INDProt}
1217 \caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioIND}
1224 \subsection{Random graphs}
1225 This section compares VF2++ with VF2 Plus on random graphs of a large
1226 size. The node labels are uniformly distributed. Let $\delta$ denote
1227 the average degree. For the parameters of problems solved in the
1228 experiments, please see the top of each chart.
1229 \subsubsection{Graph isomorphism}
1230 To evaluate the efficiency of the algorithms in the case of graph
1231 isomorphism, connected graphs of less than 20 000 nodes have been
1232 considered. Generating a random graph and shuffling its nodes, an
1233 isomorphism had to be found. Figure \ref{fig:randISO} shows the runtime results
1234 on graph sets of various density.
1242 \begin{subfigure}[b]{0.55\textwidth}
1245 \begin{axis}[title={Random ISO, $\delta = 5$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1246 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1247 west},scaled x ticks = false,x tick label style={/pgf/number
1248 format/1000 sep = \space}]
1249 %\addplot+[only marks] table {proteinsOrig.txt};
1250 \addplot table {randGraph/iso/vf2pIso5_1.txt};
1251 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1252 {randGraph/iso/vf2ppIso5_1.txt};
1258 \begin{subfigure}[b]{0.55\textwidth}
1261 \begin{axis}[title={Random ISO, $\delta = 10$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1262 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1263 west},scaled x ticks = false,x tick label style={/pgf/number
1264 format/1000 sep = \space}]
1265 %\addplot+[only marks] table {proteinsOrig.txt};
1266 \addplot table {randGraph/iso/vf2pIso10_1.txt};
1267 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1268 {randGraph/iso/vf2ppIso10_1.txt};
1275 \begin{subfigure}[b]{0.55\textwidth}
1278 \begin{axis}[title={Random ISO, $\delta = 15$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1279 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1280 west},scaled x ticks = false,x tick label style={/pgf/number
1281 format/1000 sep = \space}]
1282 %\addplot+[only marks] table {proteinsOrig.txt};
1283 \addplot table {randGraph/iso/vf2pIso15_1.txt};
1284 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1285 {randGraph/iso/vf2ppIso15_1.txt};
1290 \begin{subfigure}[b]{0.55\textwidth}
1293 \begin{axis}[title={Random ISO, $\delta = 35$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1294 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1295 west},scaled x ticks = false,x tick label style={/pgf/number
1296 format/1000 sep = \space}]
1297 %\addplot+[only marks] table {proteinsOrig.txt};
1298 \addplot table {randGraph/iso/vf2pIso35_1.txt};
1299 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1300 {randGraph/iso/vf2ppIso35_1.txt};
1305 \begin{subfigure}[b]{0.55\textwidth}
1308 \begin{axis}[title={Random ISO, $\delta = 45$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1309 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1310 west},scaled x ticks = false,x tick label style={/pgf/number
1311 format/1000 sep = \space}]
1312 %\addplot+[only marks] table {proteinsOrig.txt};
1313 \addplot table {randGraph/iso/vf2pIso45_1.txt};
1314 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1315 {randGraph/iso/vf2ppIso45_1.txt};
1320 \begin{subfigure}[b]{0.55\textwidth}
1322 \begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1323 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1324 west},scaled x ticks = false,x tick label style={/pgf/number
1325 format/1000 sep = \thinspace}]
1326 %\addplot+[only marks] table {proteinsOrig.txt};
1327 \addplot table {randGraph/iso/vf2pIso100_1.txt};
1328 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1329 {randGraph/iso/vf2ppIso100_1.txt};
1334 \caption{IND on graphs having an average degree of
1335 5.}\label{fig:randISO}
1347 Considering the graph isomorphism problem, VF2++ consistently
1348 outperforms its rival especially on sparse graphs. The reason for the
1349 slightly super linear behaviour of VF2++ on denser graphs is the
1350 larger number of nodes in the BFS tree constructed in
1351 Algorithm~\ref{alg:VF2PPPseu}.
1353 \subsubsection{Induced subgraph isomorphism}
1354 This section provides a comparison of VF2++ and VF2 Plus in the case
1355 of induced subgraph isomorphism. In addition to the size of the large
1356 graph, that of the small graph dramatically influences the hardness of
1357 a given problem too, so the overall picture is provided by examining
1358 small graphs of various size.
1360 For each chart, a number $0<\rho< 1$ has been fixed and the following
1361 has been executed 150 times. Generating a large graph $G_{large}$,
1362 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,
1363 and for all the 10 subgraphs find a mapping by using both the graph
1364 matching algorithms. The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
1365 0.3, 0.6, 0.8, 0.95$ cases have been examined, see
1366 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and
1367 \ref{fig:randIND35}.
1376 \begin{subfigure}[b]{0.55\textwidth}
1379 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1380 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1381 west},scaled x ticks = false,x tick label style={/pgf/number
1382 format/1000 sep = \space}]
1383 %\addplot+[only marks] table {proteinsOrig.txt};
1384 \addplot table {randGraph/ind/vf2pInd5_0.05.txt};
1385 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1386 {randGraph/ind/vf2ppInd5_0.05.txt};
1391 \begin{subfigure}[b]{0.55\textwidth}
1394 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1395 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1396 west},scaled x ticks = false,x tick label style={/pgf/number
1397 format/1000 sep = \space}]
1398 %\addplot+[only marks] table {proteinsOrig.txt};
1399 \addplot table {randGraph/ind/vf2pInd5_0.1.txt};
1400 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1401 {randGraph/ind/vf2ppInd5_0.1.txt};
1407 \begin{subfigure}[b]{0.55\textwidth}
1410 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1411 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1412 west},scaled x ticks = false,x tick label style={/pgf/number
1413 format/1000 sep = \space}]
1414 %\addplot+[only marks] table {proteinsOrig.txt};
1415 \addplot table {randGraph/ind/vf2pInd5_0.3.txt};
1416 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1417 {randGraph/ind/vf2ppInd5_0.3.txt};
1422 \begin{subfigure}[b]{0.55\textwidth}
1425 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1426 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1427 west},scaled x ticks = false,x tick label style={/pgf/number
1428 format/1000 sep = \space}]
1429 %\addplot+[only marks] table {proteinsOrig.txt};
1430 \addplot table {randGraph/ind/vf2pInd5_0.6.txt};
1431 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1432 {randGraph/ind/vf2ppInd5_0.6.txt};
1437 \begin{subfigure}[b]{0.55\textwidth}
1440 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1441 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1442 west},scaled x ticks = false,x tick label style={/pgf/number
1443 format/1000 sep = \space}]
1444 %\addplot+[only marks] table {proteinsOrig.txt};
1445 \addplot table {randGraph/ind/vf2pInd5_0.8.txt};
1446 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1447 {randGraph/ind/vf2ppInd5_0.8.txt};
1452 \begin{subfigure}[b]{0.55\textwidth}
1454 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1455 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1456 west},scaled x ticks = false,x tick label style={/pgf/number
1457 format/1000 sep = \thinspace}]
1458 %\addplot+[only marks] table {proteinsOrig.txt};
1459 \addplot table {randGraph/ind/vf2pInd5_0.95.txt};
1460 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1461 {randGraph/ind/vf2ppInd5_0.95.txt};
1466 \caption{IND on graphs having an average degree of
1467 5.}\label{fig:randIND5}
1474 \begin{subfigure}[b]{0.55\textwidth}
1478 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1479 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1480 west},scaled x ticks = false,x tick label style={/pgf/number
1481 format/1000 sep = \space}]
1482 %\addplot+[only marks] table {proteinsOrig.txt};
1483 \addplot table {randGraph/ind/vf2pInd10_0.05.txt};
1484 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1485 {randGraph/ind/vf2ppInd10_0.05.txt};
1490 \begin{subfigure}[b]{0.55\textwidth}
1494 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1495 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1496 west},scaled x ticks = false,x tick label style={/pgf/number
1497 format/1000 sep = \space}]
1498 %\addplot+[only marks] table {proteinsOrig.txt};
1499 \addplot table {randGraph/ind/vf2pInd10_0.1.txt};
1500 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1501 {randGraph/ind/vf2ppInd10_0.1.txt};
1507 \begin{subfigure}[b]{0.55\textwidth}
1510 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1511 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1512 west},scaled x ticks = false,x tick label style={/pgf/number
1513 format/1000 sep = \space}]
1514 %\addplot+[only marks] table {proteinsOrig.txt};
1515 \addplot table {randGraph/ind/vf2pInd10_0.3.txt};
1516 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1517 {randGraph/ind/vf2ppInd10_0.3.txt};
1522 \begin{subfigure}[b]{0.55\textwidth}
1525 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1526 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1527 west},scaled x ticks = false,x tick label style={/pgf/number
1528 format/1000 sep = \space}]
1529 %\addplot+[only marks] table {proteinsOrig.txt};
1530 \addplot table {randGraph/ind/vf2pInd10_0.6.txt};
1531 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1532 {randGraph/ind/vf2ppInd10_0.6.txt};
1538 \begin{subfigure}[b]{0.55\textwidth}
1540 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1541 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1542 west},scaled x ticks = false,x tick label style={/pgf/number
1543 format/1000 sep = \space}]
1544 %\addplot+[only marks] table {proteinsOrig.txt};
1545 \addplot table {randGraph/ind/vf2pInd10_0.8.txt};
1546 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1547 {randGraph/ind/vf2ppInd10_0.8.txt};
1551 \begin{subfigure}[b]{0.55\textwidth}
1553 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1554 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1555 west},scaled x ticks = false,x tick label style={/pgf/number
1556 format/1000 sep = \thinspace}]
1557 %\addplot+[only marks] table {proteinsOrig.txt};
1558 \addplot table {randGraph/ind/vf2pInd10_0.95.txt};
1559 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1560 {randGraph/ind/vf2ppInd10_0.95.txt};
1565 \caption{IND on graphs having an average degree of
1566 10.}\label{fig:randIND10}
1574 \begin{subfigure}[b]{0.55\textwidth}
1577 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1578 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1579 west},scaled x ticks = false,x tick label style={/pgf/number
1580 format/1000 sep = \space}]
1581 %\addplot+[only marks] table {proteinsOrig.txt};
1582 \addplot table {randGraph/ind/vf2pInd35_0.05.txt};
1583 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1584 {randGraph/ind/vf2ppInd35_0.05.txt};
1589 \begin{subfigure}[b]{0.55\textwidth}
1592 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1593 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1594 west},scaled x ticks = false,x tick label style={/pgf/number
1595 format/1000 sep = \space}]
1596 %\addplot+[only marks] table {proteinsOrig.txt};
1597 \addplot table {randGraph/ind/vf2pInd35_0.1.txt};
1598 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1599 {randGraph/ind/vf2ppInd35_0.1.txt};
1605 \begin{subfigure}[b]{0.55\textwidth}
1608 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.3$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1609 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1610 west},scaled x ticks = false,x tick label style={/pgf/number
1611 format/1000 sep = \space}]
1612 %\addplot+[only marks] table {proteinsOrig.txt};
1613 \addplot table {randGraph/ind/vf2pInd35_0.3.txt};
1614 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1615 {randGraph/ind/vf2ppInd35_0.3.txt};
1620 \begin{subfigure}[b]{0.55\textwidth}
1623 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1624 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1625 west},scaled x ticks = false,x tick label style={/pgf/number
1626 format/1000 sep = \space}]
1627 %\addplot+[only marks] table {proteinsOrig.txt};
1628 \addplot table {randGraph/ind/vf2pInd35_0.6.txt};
1629 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1630 {randGraph/ind/vf2ppInd35_0.6.txt};
1636 \begin{subfigure}[b]{0.55\textwidth}
1638 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1639 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1640 west},scaled x ticks = false,x tick label style={/pgf/number
1641 format/1000 sep = \space}]
1642 %\addplot+[only marks] table {proteinsOrig.txt};
1643 \addplot table {randGraph/ind/vf2pInd35_0.8.txt};
1644 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1645 {randGraph/ind/vf2ppInd35_0.8.txt};
1649 \begin{subfigure}[b]{0.55\textwidth}
1651 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1652 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1653 west},scaled x ticks = false,x tick label style={/pgf/number
1654 format/1000 sep = \thinspace}]
1655 %\addplot+[only marks] table {proteinsOrig.txt};
1656 \addplot table {randGraph/ind/vf2pInd35_0.95.txt};
1657 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1658 {randGraph/ind/vf2ppInd35_0.95.txt};
1663 \caption{IND on graphs having an average degree of
1664 35.}\label{fig:randIND35}
1668 Based on these experiments, VF2++ is faster than VF2 Plus and able to
1669 handle really large graphs in milliseconds. Note that when $IND$ was
1670 considered and the small graphs had proportionally few nodes ($\rho =
1671 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node
1672 orders (e.g. see the $\delta=10$ case on
1673 Figure~\ref{fig:randIND10}). If these examples had been excluded, the
1674 charts would have seemed to be similar to the other ones.
1675 Unsurprisingly, as denser graphs are considered, both VF2++ and VF2
1676 Plus slow slightly down, but remain practically usable even on graphs
1677 having 10 000 nodes.
1683 \section{Conclusion}
1684 In this paper, after providing a short summary of the recent
1685 algorithms, a new graph matching algorithm based on VF2, called VF2++,
1686 has been presented and analyzed from a practical viewpoint.
1688 Recognizing the importance of the node order and determining an
1689 efficient one, VF2++ is able to match graphs of thousands of nodes in
1690 near practically linear time including preprocessing. In addition to
1691 the proper order, VF2++ uses more efficient consistency and cutting
1692 rules which are easy to compute and make the algorithm able to prune
1693 most of the unfruitful branches without going astray.
1695 In order to show the efficiency of the new method, it has been
1696 compared to VF2 Plus, which is the best concurrent algorithm based on
1699 The experiments show that VF2++ consistently outperforms VF2 Plus on
1700 biological graphs. It seems to be asymptotically faster on protein and
1701 on contact map graphs in the case of induced subgraph isomorphism,
1702 while in the case of graph isomorphism, it has definitely better
1703 asymptotic behaviour on protein graphs.
1705 Regarding random sparse graphs, not only has VF2++ proved itself to be
1706 faster than VF2 Plus, but it has a practically linear behaviour both
1707 in the case of induced subgraph- and graph isomorphism, as well.
1711 %% The Appendices part is started with the command \appendix;
1712 %% appendix sections are then done as normal sections
1718 %% If you have bibdatabase file and want bibtex to generate the
1719 %% bibitems, please use
1721 \bibliographystyle{elsarticle-num} \bibliography{bibliography}
1723 %% else use the following coding to input the bibitems directly in the
1726 %% \begin{thebibliography}{00}
1728 %% %% \bibitem{label}
1729 %% %% Text of bibliographic item
1733 %% \end{thebibliography}
1738 %% End of file `elsarticle-template-num.tex'.