%% 

%% Copyright 2007, 2008, 2009 Elsevier Ltd

%% 

%% This file is part of the 'Elsarticle Bundle'.

%% ---------------------------------------------

%% 

%% It may be distributed under the conditions of the LaTeX Project Public

%% License, either version 1.2 of this license or (at your option) any

%% later version.  The latest version of this license is in

%%    http://www.latex-project.org/lppl.txt

%% and version 1.2 or later is part of all distributions of LaTeX

%% version 1999/12/01 or later.

%% 

%% The list of all files belonging to the 'Elsarticle Bundle' is

%% given in the file `manifest.txt'.

%% 

%% Template article for Elsevier's document class `elsarticle'

%% with numbered style bibliographic references

%% SP 2008/03/01

\documentclass[preprint,12pt]{elsarticle}

%% Use the option review to obtain double line spacing

%% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn

%% for a journal layout:

%% \documentclass[final,1p,times]{elsarticle}

%% \documentclass[final,1p,times,twocolumn]{elsarticle}

%% \documentclass[final,3p,times]{elsarticle}

%% \documentclass[final,3p,times,twocolumn]{elsarticle}

%% \documentclass[final,5p,times]{elsarticle}

%% \documentclass[final,5p,times,twocolumn]{elsarticle}

%% For including figures, graphicx.sty has been loaded in

%% elsarticle.cls. If you prefer to use the old commands

%% please give \usepackage{epsfig}

%% The amssymb package provides various useful mathematical symbols

\usepackage{amssymb}

%% The amsthm package provides extended theorem environments

%% \usepackage{amsthm}

%% The lineno packages adds line numbers. Start line numbering with

%% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on

%% for the whole article with \linenumbers.

%% \usepackage{lineno}

\usepackage{amsmath}

%% \usepackage[pdftex]{graphicx}

\usepackage{pgfplots}

\pgfplotsset{width=9cm}

\pgfplotsset{compat=1.8}

\usepackage{caption}

\usepackage{subcaption} 

\usepackage{algorithm}

\usepackage{algpseudocode}

\usepackage{tikz}

\usepackage{amsthm,amssymb}

\renewcommand{\qedsymbol}{\rule{0.7em}{0.7em}}

\newtheorem{theorem}{Theorem}[subsection]

\newtheorem{corollary}{Corollary}[theorem]

\newtheorem{claim}[theorem]{Claim}

\newtheorem{definition}{Definition}[subsection]

\newtheorem{notation}{Notation}[subsection]

\newtheorem{example}{Example}[subsection]

\usetikzlibrary{decorations.markings}

\let\oldproofname=\proofname

%% \renewcommand{\proofname}{\rm\bf{Proof:}}

\captionsetup{font=normalsize}

\journal{Discrete Applied Mathematics}

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;

%% use the tnotetext command for theassociated footnote;

%% use the fnref command within \author or \address for footnotes;

%% use the fntext command for theassociated footnote;

%% use the corref command within \author for corresponding author footnotes;

%% use the cortext command for theassociated footnote;

%% use the ead command for the email address,

%% and the form \ead[url] for the home page:

%% \title{Title\tnoteref{label1}}

%% \tnotetext[label1]{}

%% \author{Name\corref{cor1}\fnref{label2}}

%% \ead{email address}

%% \ead[url]{home page}

%% \fntext[label2]{}

%% \cortext[cor1]{}

%% \address{Address\fnref{label3}}

%% \fntext[label3]{}

\title{Improved Algorithms for Matching Biological Graphs}

%% use optional labels to link authors explicitly to addresses:

%% \author[label1,label2]{}

%% \address[label1]{}

%% \address[label2]{}

\author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}

\address{Dept of Operations Research, ELTE}

\begin{abstract}

Subgraph isomorphism is a well-known NP-Complete problem, while its

special case, the graph isomorphism problem is one of the few problems

in NP neither known to be in P nor NP-Complete. Their appearance in

many fields of application such as pattern analysis, computer vision

questions and the analysis of chemical and biological systems has

fostered the design of various algorithms for handling special graph

structures.

The idea of using state space representation and checking some

conditions in each state to prune the search tree has made the VF2

algorithm one of the state of the art graph matching algorithms for

more than a decade. Recently, biological questions of ever increasing

importance have required more efficient, specialized algorithms.

This paper presents VF2++, a new algorithm based on the original VF2,

which runs significantly faster on most test cases and performs

especially well on special graph classes stemming from biological

questions. VF2++ handles graphs of thousands of nodes in practically

near linear time including preprocessing. Not only is it an improved

version of VF2, but in fact, it is by far the fastest existing

algorithm regarding biological graphs.

The reason for VF2++' superiority over VF2 is twofold. Firstly, taking

into account the structure and the node labeling of the graph, VF2++

determines a state order in which most of the unfruitful branches of

the search space can be pruned immediately. Secondly, introducing more

efficient - nevertheless still easier to compute - cutting rules

reduces the chance of going astray even further.

In addition to the usual subgraph isomorphism, specialized versions

for induced subgraph isomorphism and for graph isomorphism are

presented. VF2++ has gained a runtime improvement of one order of

magnitude respecting induced subgraph isomorphism and a better

asymptotical behaviour in the case of graph isomorphism problem.

After having provided the description of VF2++, in order to evaluate

its effectiveness, an extensive comparison to the contemporary other

algorithms is shown, using a wide range of inputs, including both real

life biological and chemical datasets and standard randomly generated

graph series.

The work was motivated and sponsored by QuantumBio Inc., and all the

developed algorithms are available as the part of the open source

LEMON graph and network optimization library

(http://lemon.cs.elte.hu).

\end{abstract}

\begin{keyword}

%% keywords here, in the form: keyword \sep keyword

%% PACS codes here, in the form: \PACS code \sep code

%% MSC codes here, in the form: \MSC code \sep code

%% or \MSC[2008] code \sep code (2000 is the default)

\end{keyword}

\end{frontmatter}

%% \linenumbers

%% main text

\section{Introduction}

\label{sec:intro}

In the last decades, combinatorial structures, and especially graphs

have been considered with ever increasing interest, and applied to the

solution of several new and revised questions.  The expressiveness,

the simplicity and the studiedness of graphs make them practical for

modelling and appear constantly in several seemingly independent

fields.  Bioinformatics and chemistry are amongst the most relevant

and most important fields.

Complex biological systems arise from the interaction and cooperation

of plenty of molecular components. Getting acquainted with such

systems at the molecular level has primary importance, since

protein-protein interaction, DNA-protein interaction, metabolic

interaction, transcription factor binding, neuronal networks, and

hormone signaling networks can be understood only this way.

For instance, a molecular structure can be considered as a graph,

whose nodes correspond to atoms and whose edges to chemical bonds. The

secondary structure of a protein can also be represented as a graph,

where nodes are associated with aminoacids and the edges with hydrogen

bonds. The nodes are often whole molecular components and the edges

represent some relationships among them.  The similarity and

dissimilarity of objects corresponding to nodes are incorporated to

the model by \emph{node labels}.  Many other chemical and biological

structures can easily be modeled in a similar way. Understanding such

networks basically requires finding specific subgraphs, which can not

avoid the application of graph matching algorithms.

Finally, let some of the other real-world fields related to some

variants of graph matching be briefly mentioned: pattern recognition

and machine vision \cite{HorstBunkeApplications}, symbol recognition

\cite{CordellaVentoSymbolRecognition}, face identification

\cite{JianzhuangYongFaceIdentification}.  \\

Subgraph and induced subgraph matching problems are known to be

NP-Complete\cite{SubgraphNPC}, while the graph isomorphism problem is

one of the few problems in NP neither known to be in P nor

NP-Complete. Although polynomial time isomorphism algorithms are known

for various graph classes, like trees and planar

graphs\cite{PlanarGraphIso}, bounded valence

graphs\cite{BondedDegGraphIso}, interval graphs\cite{IntervalGraphIso}

or permutation graphs\cite{PermGraphIso}.

In the following, some algorithms based on other approaches are

summarized, which do not need any restrictions on the graphs. However,

an overall polynomial behaviour is not expectable from such an

alternative, it may often have good performance, even on a graph class

for which polynomial algorithm is known. Note that this summary

containing only exact matching algorithms is far not complete, neither

does it cover all the recent algorithms.

The first practically usable approach was due to

Ullmann\cite{Ullmann} which is a commonly used depth-first

search based algorithm with a complex heuristic for reducing the

number of visited states. A major problem is its $\Theta(n^3)$ space

complexity, which makes it impractical in the case of big sparse

graphs.

In a recent paper, Ullmann\cite{UllmannBit} presents an

improved version of this algorithm based on a bit-vector solution for

the binary Constraint Satisfaction Problem.

The Nauty algorithm\cite{Nauty} transforms the two graphs to

a canonical form before starting to check for the isomorphism. It has

been considered as one of the fastest graph isomorphism algorithms,

although graph categories were shown in which it takes exponentially

many steps. This algorithm handles only the graph isomorphism problem.

The \emph{LAD} algorithm\cite{Lad} uses a depth-first search

strategy and formulates the matching as a Constraint Satisfaction

Problem to prune the search tree. The constraints are that the mapping

has to be injective and edge-preserving, hence it is possible to

handle new matching types as well.

The \textbf{RI} algorithm\cite{RI} and its variations are based on a

state space representation. After reordering the nodes of the graphs,

it uses some fast executable heuristic checks without using any

complex pruning rules. It seems to run really efficiently on graphs

coming from biology, and won the International Contest on Pattern

Search in Biological Databases\cite{Content}.

The currently most commonly used algorithm is the

\textbf{VF2}\cite{VF2}, the improved version of VF\cite{VF}, which was

designed for solving pattern matching and computer vision problems,

and has been one of the best overall algorithms for more than a

decade. Although, it can't be up to new specialized algorithms, it is

still widely used due to its simplicity and space efficiency. VF2 uses

a state space representation and checks some conditions in each state

to prune the search tree.

Our first graph matching algorithm was the first version of VF2 which

recognizes the significance of the node ordering, more opportunities

to increase the cutting efficiency and reduce its computational

complexity. This project was initiated and sponsored by QuantumBio

Inc.\cite{QUANTUMBIO} and the implementation --- along with a source

code --- has been published as a part of LEMON\cite{LEMON} open source

graph library.

This paper introduces \textbf{VF2++}, a new further improved algorithm

for the graph and (induced)subgraph isomorphism problem, which uses

efficient cutting rules and determines a node order in which VF2 runs

significantly faster on practical inputs.

Meanwhile, another variant called \textbf{VF2 Plus}\cite{VF2Plus} has

been published. It is considered to be as efficient as the RI

algorithm and has a strictly better behavior on large graphs.  The

main idea of VF2 Plus is to precompute a heuristic node order of the

small graph, in which the VF2 works more efficiently.

\section{Problem Statement}

This section provides a detailed description of the problems to be

solved.

\subsection{Definitions}

Throughout the paper $G_{small}=(V_{small}, E_{small})$ and

$G_{large}=(V_{large}, E_{large})$ denote two undirected graphs.

\begin{definition}\label{sec:ismorphic}

$G_{small}$ and $G_{large}$ are \textbf{isomorphic} if $\exists M:

  V_{small} \longrightarrow V_{large}$ bijection, for which the

  following is true:

\begin{center}

$\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

  (M(u),M(v))\in{E_{large}}$

\end{center}

\end{definition}

For the sake of simplicity in this paper subgraphs and induced

subgraphs are defined in a more general way than usual:

\begin{definition}

$G_{small}$ is a \textbf{subgraph} of $G_{large}$ if $\exists I:

  V_{small}\longrightarrow V_{large}$ injection, for which the

  following is true:

\begin{center}

$\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Rightarrow (I(u),I(v))\in E_{large}$

\end{center}

\end{definition}

\begin{definition} 

$G_{small}$ is an \textbf{induced subgraph} of $G_{large}$ if $\exists

  I: V_{small}\longrightarrow V_{large}$ injection, for which the

  following is true:

\begin{center}

$\forall u,v \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

  (I(u),I(v))\in E_{large}$

\end{center}

\end{definition}

\begin{definition}

$lab: (V_{small}\cup V_{large}) \longrightarrow K$ is a \textbf{node

    label function}, where K is an arbitrary set. The elements in K

  are the \textbf{node labels}. Two nodes, u and v are said to be

  \textbf{equivalent}, if $lab(u)=lab(v)$.

\end{definition}

When node labels are also given, the matched nodes must have the same

labels.  For example, the node labeled isomorphism is phrased by

\begin{definition}

$G_{small}$ and $G_{large}$ are \textbf{isomorphic by the node label

    function lab} if $\exists M: V_{small} \longrightarrow V_{large}$

  bijection, for which the following is true:

\begin{center}

$(\forall u,v\in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

  (M(u),M(v))\in{E_{large}})$ and $(\forall u\in{V_{small}} :

  lab(u)=lab(M(u)))$

\end{center}

\end{definition}

The other two definitions can be extended in the same way.

Note that edge label function can be defined similarly to node label

function, and all the definitions can be extended with additional

conditions, but it is out of the scope of this work.

The equivalence of two nodes is usually defined by another relation,

$\\R\subseteq (V_{small}\cup V_{large})^2$. This overlaps with the

definition given above if R is an equivalence relation, which does not

mean restriction in biological and chemical applications.

\subsection{Common problems}\label{sec:CommProb}

The focus of this paper is on two extensively studied topics, the

subgraph isomorphism and its variations. However, the following

problems also appear in many applications.

The \textbf{subgraph matching problem} is the following: is

$G_{small}$ isomorphic to any subgraph of $G_{large}$ by a given node

label?

The \textbf{induced subgraph matching problem} asks the same about the

existence of an induced subgraph.

The \textbf{graph isomorphism problem} can be defined as induced

subgraph matching problem where the sizes of the two graphs are equal.

In addition to existence, it may be needed to show such a subgraph, or

it may be necessary to list all of them.

It should be noted that some authors misleadingly refer to the term

\emph{subgraph isomorphism problem} as an \emph{induced subgraph

  isomorphism problem}.

The following sections give the descriptions of VF2, VF2++, VF2 Plus

and a particular comparison.

\section{The VF2 Algorithm}

This algorithm is the basis of both the VF2++ and the VF2 Plus.  VF2

is able to handle all the variations mentioned in Section

  \ref{sec:CommProb}.  Although it can also handle directed graphs,

for the sake of simplicity, only the undirected case will be

discussed.

\subsection{Common notations}

\indent Assume $G_{small}$ is searched in $G_{large}$.  The following

definitions and notations will be used throughout the whole paper.

\begin{definition}

A set $M\subseteq V_{small}\times V_{large}$ is called

\textbf{mapping}, if no node of $V_{small}$ or of $V_{large}$ appears

in more than one pair in M.  That is, M uniquely associates some of

the nodes in $V_{small}$ with some nodes of $V_{large}$ and vice

versa.

\end{definition}

\begin{definition}

Mapping M \textbf{covers} a node v, if there exists a pair in M, which

contains v.

\end{definition}

\begin{definition}

A mapping $M$ is $\mathbf{whole\ mapping}$, if $M$ covers all the

nodes in $V_{small}$.

\end{definition}

\begin{notation}

Let $\mathbf{M_{small}(s)} := \{u\in V_{small} : \exists v\in

V_{large}: (u,v)\in M(s)\}$ and $\mathbf{M_{large}(s)} := \{v\in

V_{large} : \exists u\in V_{small}: (u,v)\in M(s)\}$.

\end{notation}

\begin{notation}

Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$, if such a node

exist, otherwise $\mathbf{Pair(M,v)}$ is undefined. For a mapping $M$

and $v\in V_{small}\cup V_{large}$.

\end{notation}

Note that if $\mathbf{Pair(M,v)}$ exists, then it is unique

The definitions of the isomorphism types can be rephrased on the

existence of a special whole mapping $M$, since it represents a

bijection. For example

\begin{center}

$M\subseteq V_{small}\times V_{large}$ represents an induced subgraph

  isomorphism $\Leftrightarrow$ $M$ is whole mapping and $\forall u,v

  \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow

  (Pair(M,u),Pair(M,v))\in E_{large}$.

\end{center}

\begin{definition}

A set of whole mappings is called \textbf{problem type}.

\end{definition}

Throughout the paper, $\mathbf{PT}$ denotes a generic problem type

which can be substituted by any problem type.

A whole mapping $W\mathbf{\ is\ of\ type\ PT}$, if $W\in PT$. Using

this notations, VF2 searches a whole mapping $W$ of type $PT$.

For example the problem type of graph isomorphism problem is the

following.  A whole mapping $W$ is in $\mathbf{ISO}$, iff the

bijection represented by $W$ satisfies Definition~\ref{sec:ismorphic}.

The subgraph- and induced subgraph matching problems can be formalized

in a similar way. Let their problem types be denoted as $\mathbf{SUB}$

and $\mathbf{IND}$.

\begin{definition}

\label{expPT}

$PT$ is an \textbf{expanding problem type} if $\ \forall\ W\in

PT:\ \forall u_1,u_2\in V_{small}:\ (u_1,u_2)\in E_{small}\Rightarrow

(Pair(W,u_1),Pair(W,u_2))\in E_{large}$, that is each edge of

$G_{small}$ has to be mapped to an edge of $G_{large}$ for each

mapping in $PT$.

\end{definition}

Note that $ISO$, $SUB$ and $IND$ are expanding problem types.

This paper deals with the three problem types mentioned above only,

but the following generic definitions make it possible to handle other

types as well.  Although it may be challenging to find a proper

consistency function and an efficient cutting function.

\begin{definition}

Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a

\textbf{consistency function by } $\mathbf{PT}$, if the following

holds. If there exists whole mapping $W$ of type PT for which

$M\subseteq W$, then $Cons_{PT}(M)$ is true.

\end{definition}

\begin{definition} 

Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a

\textbf{cutting function by } $\mathbf{PT}$, if the following

holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a

whole mapping W of type PT.

\end{definition}

\begin{definition}

$M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if

  $Cons_{PT}(M)$ is true.

\end{definition}

$Cons_{PT}$ and $Cut_{PT}$ will often be used in the following form.

\begin{notation}

Let $\mathbf{Cons_{PT}(p, M)}:=Cons_{PT}(M\cup\{p\})$ and

$\mathbf{Cut_{PT}(p, M)}:=Cut_{PT}(M\cup\{p\})$, where

$p\in{V_{small}\!\times\!V_{large}}$ and $M\cup\{p\}$ is mapping.

\end{notation}

$Cons_{PT}$ will be used to check the consistency of the already

covered nodes, while $Cut_{PT}$ is for looking ahead to recognize if

no whole consistent mapping can contain the current mapping.

\subsection{Overview of the algorithm}

VF2 uses a state space representation of mappings, $Cons_{PT}$ for

excluding inconsistency with the problem type and $Cut_{PT}$ for

pruning the search tree.  Each state $s$ of the matching process can

be associated with a mapping $M(s)$.

Algorithm~\ref{alg:VF2Pseu} is a high level description of

the VF2 matching algorithm.

\begin{algorithm}

\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne

nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..

\caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu}

\begin{algorithmic}[1]

\Procedure{VF2}{State $s$, ProblemType $PT$} \If{$M(s$) covers

  $V_{small}$} \State Output($M(s)$) \Else

  \State Compute the set $P(s)$ of the pairs candidate for inclusion

  in $M(s)$ \ForAll{$p\in{P(s)}$} \If{Cons$_{PT}$($p, M(s)$) $\wedge$

    $\neg$Cut$_{PT}$($p, M(s)$)} \State Compute the nascent state

  $\tilde{s}$ by adding $p$ to $M(s)$ \State \textbf{call}

  VF2($\tilde{s}$, $PT$) \EndIf \EndFor \EndIf \EndProcedure

\end{algorithmic}

\end{algorithm}

The initial state $s_0$ is associated with $M(s_0)=\emptyset$, i.e. it

starts with an empty mapping.

For each state $s$, the algorithm computes $P(s)$, the set of

candidate node pairs for adding to the current state $s$.

For each pair $p$ in $P(s)$, $Cons_{PT}(p,M(s))$ and

$Cut_{PT}(p,M(s))$ are evaluated. If $Cons_{PT}(p,M(s))$ is true and

$Cut_{PT}(p,M(s))$ is false, the successor state $\tilde{s}=s\cup

\{p\}$ is computed, and the whole process is recursively applied to

$\tilde{s}$. Otherwise, $\tilde{s}$ is not consistent by $PT$ or it

can be proved that $s$ can not be extended to a whole mapping.

In order to make sure of the correctness see

\begin{claim}

Through consistent mappings, only consistent whole mappings can be

reached, and all of the whole mappings are reachable through

consistent mappings.

\end{claim}

Note that a state may be reached in many different ways, since the

order of insertions into M does not influence the nascent mapping. In

fact, the number of different ways which lead to the same state can be

exponentially large. If $G_{small}$ and $G_{large}$ are circles with n

nodes and n different node labels, there exists exactly one graph

isomorphism between them, but it will be reached in $n!$ different

ways.

However, one may observe

\begin{claim}

\label{claim:claimTotOrd}

Let $\prec$ an arbitrary total ordering relation on $V_{small}$.  If

the algorithm ignores each $p=(u,v) \in P(s)$, for which

\begin{center}

$\exists (\hat{u},\hat{v})\in P(s): \hat{u} \prec u$,

\end{center}

then no state can be reached more than ones and each state associated

with a whole mapping remains reachable.

\end{claim}

Note that the cornerstone of the improvements to VF2 is a proper

choice of a total ordering.

\subsection{The candidate set P(s)}

\label{candidateComputingVF2}

$P(s)$ is the set of the candidate pairs for inclusion in $M(s)$.

Suppose that $PT$ is an expanding problem type, see

Definition~\ref{expPT}.

\begin{notation}

Let $\mathbf{T_{small}(s)}:=\{u \in V_{small} : u$ is not covered by

$M(s)\wedge\exists \tilde{u}\in{V_{small}: (u,\tilde{u})\in E_{small}}

\wedge \tilde{u}$ is covered by $M(s)\}$, and

\\ $\mathbf{T_{large}(s)}\!:=\!\{v \in\!V_{large}\!:\!v$ is not

covered by

$M(s)\wedge\!\exists\tilde{v}\!\in\!{V_{large}\!:\!(v,\tilde{v})\in\!E_{large}}

\wedge \tilde{v}$ is covered by $M(s)\}$

\end{notation}

The set $P(s)$ includes the pairs of uncovered neighbours of covered

nodes and if there is not such a node pair, all the pairs containing

two uncovered nodes are added. Formally, let

\[

 P(s)\!=\!

  \begin{cases} 

   T_{small}(s)\times T_{large}(s)&\hspace{-0.15cm}\text{if }

   T_{small}(s)\!\neq\!\emptyset\!\wedge\!T_{large}(s)\!\neq

   \emptyset,\\ (V_{small}\!\setminus\!M_{small}(s))\!\times\!(V_{large}\!\setminus\!M_{large}(s))

   &\hspace{-0.15cm}otherwise.

  \end{cases}

\]

\subsection{Consistency}

This section defines the consistency functions for the different

problem types mentioned in Section~\ref{sec:CommProb}.

\begin{notation}

Let $\mathbf{\Gamma_{small} (u)}:=\{\tilde{u}\in V_{small} :

(u,\tilde{u})\in E_{small}\}$\\ Let $\mathbf{\Gamma_{large}

  (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$

\end{notation}

Suppose $p=(u,v)$, where $u\in V_{small}$ and $v\in V_{large}$, $s$ is

a state of the matching procedure, $M(s)$ is consistent mapping by

$PT$ and $lab(u)=lab(v)$.  $Cons_{PT}(p,M(s))$ checks whether

including pair $p$ into $M(s)$ leads to a consistent mapping by $PT$.

\subsubsection{Induced subgraph isomorphism}

$M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow

(\forall \tilde{u}\in M_{small}: (u,\tilde{u})\in E_{small}

\Leftrightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.\newline The

following formulation gives an efficient way of calculating

$Cons_{IND}$.

\begin{claim}

$Cons_{IND}((u,v),M(s)):=(\forall \tilde{v}\in \Gamma_{large}(v)

  \ \cap\ M_{large}(s):\\(Pair(M(s),\tilde{v}),u)\in E_{small})\wedge

  (\forall \tilde{u}\in \Gamma_{small}(u)

  \ \cap\ M_{small}(s):(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a

  consistency function in the case of $IND$.

\end{claim}

\subsubsection{Graph isomorphism}

$M(s)\cup \{(u,v)\}$ is a consistent mapping by $ISO$

$\Leftrightarrow$ $M(s)\cup \{(u,v)\}$ is a consistent mapping by

$IND$.

\begin{claim}

$Cons_{ISO}((u,v),M(s))$ is a consistency function by $ISO$ if and

  only if it is a consistency function by $IND$.

\end{claim}

\subsubsection{Subgraph isomorphism}

$M(s)\cup \{(u,v)\}$ is a consistent mapping by $SUB$ $\Leftrightarrow

(\forall \tilde{u}\in M_{small}:\\(u,\tilde{u})\in E_{small}

\Rightarrow (v,Pair(M(s),\tilde{u}))\in E_{large})$.

\newline

The following formulation gives an efficient way of calculating

$Cons_{SUB}$.

\begin{claim}

$Cons_{SUB}((u,v),M(s)):= (\forall \tilde{u}\in \Gamma_{small}(u)

  \ \cap\ M_{small}(s):\\(v,Pair(M(s),\tilde{u}))\in E_{large})$ is a

  consistency function by $SUB$.

\end{claim}

\subsection{Cutting rules}

$Cut_{PT}(p,M(s))$ is defined by a collection of efficiently

verifiable conditions. The requirement is that $Cut_{PT}(p,M(s))$ can

be true only if it is impossible to extended $M(s)\cup \{p\}$ to a

whole mapping.

\begin{notation}

Let $\mathbf{\tilde{T}_{small}}(s):=(V_{small}\backslash

M_{small}(s))\backslash T_{small}(s)$, and

\\ $\mathbf{\tilde{T}_{large}}(s):=(V_{large}\backslash

M_{large}(s))\backslash T_{large}(s)$.

\end{notation}

\subsubsection{Induced subgraph isomorphism}

\begin{claim}

$Cut_{IND}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

  |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

  \tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap

  \tilde{T}_{small}(s)|$ is a cutting function by $IND$.

\end{claim}

\subsubsection{Graph isomorphism}

Note that the cutting function of induced subgraph isomorphism defined

above is a cutting function by $ISO$, too, however it is less

efficient than the following while their computational complexity is

the same.

\begin{claim}

$Cut_{ISO}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| \neq

  |\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

  \tilde{T}_{large}(s)| \neq |\Gamma_{small}(u)\cap

  \tilde{T}_{small}(s)|$ is a cutting function by $ISO$.

\end{claim}

\subsubsection{Subgraph isomorphism}

\begin{claim}

$Cut_{SUB}((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

  |\Gamma_{small} (u)\ \cap\ T_{small}(s)|$ is a cutting function by

  $SUB$.

\end{claim}

Note that there is a significant difference between induced and

non-induced subgraph isomorphism:

\begin{claim}

\label{claimSUB}

$Cut_{SUB}'((u,v),M(s)):= |\Gamma_{large} (v)\ \cap\ T_{large}(s)| <

|\Gamma_{small} (u)\ \cap\ T_{small}(s)| \vee |\Gamma_{large}(v)\cap

\tilde{T}_{large}(s)| < |\Gamma_{small}(u)\cap \tilde{T}_{small}(s)|$

is \textbf{not} a cutting function by $SUB$.

\end{claim}

\begin{proof}$ $\\

\vspace*{-0.5cm}

\begin{figure}

\begin{center}

\begin{tikzpicture}

  [scale=.8,auto=left,every node/.style={circle,fill=black!15}]

  \node[rectangle,fill=black!15] at (4,6) {$G_{small}$}; \node (u4) at

  (2.5,10) {$u_4$}; \node (u3) at (5.5,10) {$u_3$}; \node (u1) at

  (2.5,7) {$u_1$}; \node (u2) at (5.5,7) {$u_2$};

  \node[rectangle,fill=black!30] at (13.5,6) {$G_{large}$};

  \node[fill=black!30] (v4) at (12,10) {$v_4$}; \node[fill=black!30]

  (v3) at (15,10) {$v_3$}; \node[fill=black!30] (v1) at (12,7)

       {$v_1$}; \node[fill=black!30] (v2) at (15,7) {$v_2$};

  \foreach \from/\to in {u1/u2,u2/u3,u3/u4,u4/u1} \draw (\from) --

  (\to); \foreach \from/\to in {v1/v2,v2/v3,v3/v4,v4/v1,v1/v3} \draw

  (\from) -- (\to);

%    \draw[dashed] (\from) -- (\to);

\end{tikzpicture}

\caption{Graphs for the proof of Claim~\ref{claimSUB}}

\label{fig:proofSUB}

\end{center}

\end{figure}

Let the two graphs of Figure~\ref{fig:proofSUB} be the input

graphs.  Suppose the total ordering relation is $u_1 \prec u_2 \prec

u_3 \prec u_4$,$M(s)\!=\{(u_1,v_1)\}$, and VF2 tries to add

$(u_2,v_2)\in P(s)$.\newline $Cons_{SUB}((u_2,v_2),M(s))=true$, so

$M\cup \{(u_2,v_2)\}$ is consistent by $SUB$. The cutting function

$Cut_{SUB}((u_2,v_2),M(s))$ is false, so it does not let cut the

tree.\newline On the other hand $Cut_{SUB}'((u_2,v_2),M(s))$ is true,

since\\$0=|\Gamma_{large}(v_2)\cap

\tilde{T}_{large}(s)|<|\Gamma_{small}(u_2)\cap

\tilde{T}_{small}(s)|=1$ is true, but still the tree can not be

pruned, because otherwise the

$\{(u_1,v_1)(u_2,v_2)(u_3,v_3)(u_4,v_4)\}$ mapping can not be found.

\end{proof}

\section{The VF2++ Algorithm}

Although any total ordering relation makes the search space of VF2 a

tree, its choice turns out to dramatically influence the number of

visited states. The goal is to determine an efficient one as quickly

as possible.

The main reason for VF2++' superiority over VF2 is twofold. Firstly,

taking into account the structure and the node labeling of the graph,

VF2++ determines a state order in which most of the unfruitful

branches of the search space can be pruned immediately. Secondly,

introducing more efficient --- nevertheless still easier to compute

--- cutting rules reduces the chance of going astray even further.

In addition to the usual subgraph isomorphism, specialized versions

for induced subgraph isomorphism and for graph isomorphism have been

designed. VF2++ has gained a runtime improvement of one order of

magnitude respecting induced subgraph isomorphism and a better

asymptotical behaviour in the case of graph isomorphism problem.

Note that a weaker version of the cutting rules and the more efficient

candidate set calculating were described in \cite{VF2Plus}, too.

It should be noted that all the methods described in this section are

extendable to handle directed graphs and edge labels as well.

The basic ideas and the detailed description of VF2++ are provided in

the following.

\subsection{Preparations}

\begin{claim}

\label{claim:claimCoverFromLeft}

The total ordering relation uniquely determines a node order, in which

the nodes of $V_{small}$ will be covered by VF2. From the point of

view of the matching procedure, this means, that always the same node

of $G_{small}$ will be covered on the d-th level.

\end{claim}

\begin{proof}

In order to make the search space a tree, the pairs in $\{(u,v)\in

P(s) : \exists \hat{u} : \hat{u}\prec u\}$ are excluded from $P(s)$.

\newline

Let $\tilde{P}(s):=P(s)\backslash \{(u,v)\in P(s) : \exists \hat{u} :

\hat{u}\prec u\}$

\newline

The relation $\prec$ is a total ordering, so $\exists!\ \tilde{u} :

\forall\ (u,v)\in \tilde{P}(s): u=\tilde u$. Since a pair form

$\tilde{P}(s)$ is chosen for including into $M(s)$, it is obvious,

that only $\tilde{u}$ can be covered in $V_{small}$. Actually,

$\tilde{u}$ is the smallest element in $T_{small}(s)$ (or in

$V_{small}\backslash M_{small}(s)$, if $T_{small}(s)$ were empty), and

$T_{small}(s)$ depends only on the covered nodes of $G_{small}$.

\newline

Simple induction on $d$ shows that the set of covered nodes of

$G_{small}$ is unique, if $d$ is given, so $\tilde{u}$ is unique if

$d$ is given.

\end{proof}

\begin{definition}

An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of

$V_{small}$ is \textbf{matching order}, if exists $\prec$ total

ordering relation, s.t. the VF2 with $\prec$ on the d-th level finds

pair for $u_{\sigma(d)}$ for all $d\in\{1,..,|V_{small}|\}$.

\end{definition}

\begin{claim}\label{claim:MOclaim}

A total ordering is matching order, iff the nodes of every component

form an interval in the node sequence, and every node connects to a

previous node in its component except the first node of the

component. The order of the components is arbitrary.  \\Formally

spoken, an order

$(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of

$V_{small}$ is matching order $\Leftrightarrow$ $\forall

G'_{small}=(V'_{small},E'_{small})\ component\ of\ G_{small}: \forall

i: (\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in

V'_{small})\Rightarrow \exists k : k < i \wedge (\forall l: k\leq

l\leq i \Rightarrow u_{l}\in V'_{small}) \wedge

(u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in

\{1,..,|V_{small}|\}$\newline

\end{claim}

\begin{proof}

Suppose a matching order is given. It has to be shown that the node

sequence has a structure described above.\\ Let

$G'_{small}=(V'_{small},E'_{small})$ be an arbitrary component and $i$

an arbitrary index.

\newline

$(\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in

V'_{small})\Rightarrow u_{\sigma(i)}$ is not the first covered node in

$G_{small}\ \Rightarrow u_{\sigma(i)}$ is connected to a covered node

$u_{\sigma(k)}$ where $k<i$, since $u_{\sigma(i)}\in T_{small}(s)$ for

some $s$ and $T_{small}(s)\subseteq{V'_{small}}$ contains only nodes

connected to at least one covered node. It's easy to see, that

$\forall l: k\leq l\leq i \Rightarrow u_{l}\in V'_{small}$, since

$T_{small}(s)$ contains only nodes connected to some covered ones,

while it is not empty, but if it were empty, then $u_{\sigma(k)}$ and

$u_{\sigma(i)}$ were not in the same component.

Now, let us show that if a node sequence has the special structure

described above, it has to be matching

order.\\ $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ is

a total ordering, which determines the matching order

$(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$.

\end{proof}

To summing up, a total ordering always uniquely determines a matching

order, and every matching order can be determined by a total ordering,

however, more than one different total orderings may determine the

same matching order.

\subsection{Idea behind the algorithm}

The goal is to find a matching order in which the algorithm is able to

recognize inconsistency or prune the infeasible branches on the

highest levels and goes deep only if it is needed.

\begin{notation}

Let $\mathbf{Conn_{H}(u)}:=|\Gamma_{small}(u)\cap H\}|$, that is the

number of neighbours of u which are in H, where $u\in V_{small} $ and

$H\subseteq V_{small}$.

\end{notation}

The principal question is the following. Suppose a state $s$ is

given. For which node of $T_{small}(s)$ is the hardest to find a

consistent pair in $G_{large}$? The more covered neighbours a node in

$T_{small}(s)$ has --- i.e. the largest $Conn_{M_{small}(s)}$ it has

---, the more rarely satisfiable consistency constraints for its pair

are given.

In biology, most of the graphs are sparse, thus several nodes in

$T_{small}(s)$ may have the same $Conn_{M_{small}(s)}$, which makes

reasonable to define a secondary and a tertiary order between them.

The observation above proves itself to be as determining, that the

secondary ordering prefers nodes with the most uncovered neighbours

among which have the same $Conn_{M_{small}(s)}$ to increase

$Conn_{M_{small}(s)}$ of uncovered nodes so much, as possible.  The

tertiary ordering prefers nodes having the rarest uncovered labels.

Note that the secondary ordering is the same as the ordering by $deg$,

which is a static data in front of the above used.

These rules can easily result in a matching order which contains the

nodes of a long path successively, whose nodes may have low $Conn$ and

is easily matchable into $G_{large}$. To avoid that, a BFS order is

used, which provides the shortest possible paths.

\newline

In the following, some examples on which the VF2 may be slow are

described, although they are easily solvable by using a proper

matching order.

\begin{example}

Suppose $G_{small}$ can be mapped into $G_{large}$ in many ways

without node labels. Let $u\in V_{small}$ and $v\in V_{large}$.

\newline

$lab(u):=black$

\newline

$lab(v):=black$

\newline

$lab(\tilde{u}):=red \ \forall \tilde{u}\in (V_{small}\backslash

\{u\})$

\newline

$lab(\tilde{v}):=red \ \forall \tilde{v}\in (V_{large}\backslash

\{v\})$

\newline

Now, any mapping by the node label $lab$ must contain $(u,v)$, since

$u$ is black and no node in $V_{large}$ has a black label except

$v$. If unfortunately $u$ were the last node which will get covered,

VF2 would check only in the last steps, whether $u$ can be matched to

$v$.

\newline

However, had $u$ been the first matched node, u would have been

matched immediately to v, so all the mappings would have been

precluded in which node labels can not correspond.

\end{example}

\begin{example}

Suppose there is no node label given, $G_{small}$ is a small graph and

can not be mapped into $G_{large}$ and $u\in V_{small}$.

\newline

Let $G'_{small}:=(V_{small}\cup

\{u'_{1},u'_{2},..,u'_{k}\},E_{small}\cup

\{(u,u'_{1}),(u'_{1},u'_{2}),..,(u'_{k-1},u'_{k})\})$, that is,

$G'_{small}$ is $G_{small}\cup \{ a\ k$ long path, which is disjoint

from $G_{small}$ and one of its starting points is connected to $u\in

V_{small}\}$.

\newline

Is there a subgraph of $G_{large}$, which is isomorph with

$G'_{small}$?

\newline

If unfortunately the nodes of the path were the first $k$ nodes in the

matching order, the algorithm would iterate through all the possible k

long paths in $G_{large}$, and it would recognize that no path can be

extended to $G'_{small}$.

\newline

However, had it started by the matching of $G_{small}$, it would not

have matched any nodes of the path.

\end{example}

These examples may look artificial, but the same problems also appear

in real-world instances, even though in a less obvious way.

\subsection{Total ordering}

Instead of the total ordering relation, the matching order will be

searched directly.

\begin{notation}

Let \textbf{F$_\mathcal{M}$(l)}$:=|\{v\in V_{large} :

l=lab(v)\}|-|\{u\in V_{small}\backslash \mathcal{M} : l=lab(u)\}|$ ,

where $l$ is a label and $\mathcal{M}\subseteq V_{small}$.

\end{notation}

\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}$.

\end{definition}

\begin{algorithm}

\algtext*{EndIf}

\algtext*{EndProcedure}

\algtext*{EndWhile}

\caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}

\begin{algorithmic}[1]

\Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$

\Comment{matching order} \While{$V_{small}\backslash \mathcal{M}

  \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg

min$_{F_\mathcal{M}\circ lab}(V_{small}\backslash

\mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with

root node $r$.  \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the

$d$-th level \State Process $V_d$ \Comment{See Algorithm

  \ref{alg:VF2PPProcess1}} \EndFor

\EndWhile \EndProcedure

\end{algorithmic}

\end{algorithm}

\begin{algorithm}

\algtext*{EndIf}

\algtext*{EndProcedure}%ne nyomtasson ..

\algtext*{EndWhile}

\caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}

\begin{algorithmic}[1]

\Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}

\State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg

max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$

\State Append node $m$ to the end of $\mathcal{M}$ \State Refresh

$F_\mathcal{M}$ \EndWhile \EndProcedure

\end{algorithmic}

\end{algorithm}

Algorithm~\ref{alg:VF2PPPseu} is a high level description of the

matching order procedure of VF2++. It computes a BFS tree for each

component in ascending order of their rarest $lab$ and largest $deg$,

whose root vertex is the component's minimal

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

lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately

to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.

Claim~\ref{claim:MOclaim} shows that Algorithm~\ref{alg:VF2PPPseu}

provides a matching order.

\subsection{Cutting rules}

\label{VF2PPCuttingRules}

This section presents the cutting rules of VF2++, which are improved

by using extra information coming from the node labels.