# HG changeset patch
# User Madarasi Peter
# Date 1480283876 -3600
# Node ID 909bcb203f25dc5100d9a6aec913d56a160db246
# Parent  8349e9e65e1891701c758908afa365b5fed6f681
Fine tune. To be reviewed: abstract, intro, conclusion.

diff -r 8349e9e65e18 -r 909bcb203f25 damecco.tex
--- a/damecco.tex	Sat Nov 26 00:15:22 2016 +0100
+++ b/damecco.tex	Sun Nov 27 22:57:56 2016 +0100
@@ -329,10 +329,10 @@
 $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)$.
+  \textbf{equivalent} if $lab(u)=lab(v)$.
 \end{definition}
 
-When node labels are also given, the matched nodes must have the same
+When node labels are 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
@@ -345,16 +345,7 @@
 \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.
+Note that he other two definitions can be extended in the same way.
 
 \subsection{Common problems}\label{sec:CommProb}
 
@@ -395,19 +386,19 @@
 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
+\textbf{mapping} if no node of $V_{small}\cup 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
+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
+A mapping $M$ is $\mathbf{whole\ mapping}$ if $M$ covers all the
 nodes in $V_{small}$.
 \end{definition}
 
@@ -418,9 +409,8 @@
 \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}$.
+Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$ if such a node
+exist, otherwise $\mathbf{Pair(M,v)}$ is undefined, where $M$ is a mapping and $v\in V_{small}\cup V_{large}$.
 \end{notation}
 
 Note that if $\mathbf{Pair(M,v)}$ exists, then it is unique
@@ -441,26 +431,26 @@
 
 \begin{definition}
 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a
-\textbf{consistency function by } $\mathbf{PT}$, if the following
+\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
+\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
+$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
+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}
@@ -508,7 +498,7 @@
 $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
+$\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
@@ -518,13 +508,8 @@
 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.
+Note that a state may be reached in exponentially many different ways, since the
+order of insertions into $M$ does not influence the nascent mapping.
 
 However, one may observe
 
@@ -533,9 +518,9 @@
 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$,
+$\exists (\tilde{u},\tilde{v})\in P(s): \tilde{u} \prec u$,
 \end{center}
-then no state can be reached more than ones and each state associated
+then no state can be reached more than once, and each state associated
 with a whole mapping remains reachable.
 \end{claim}
 
@@ -557,7 +542,7 @@
 \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
+nodes, and if there is not such a node pair, all the pairs containing
 two uncovered nodes are added. Formally, let
 \[
  P(s)\!=\!
@@ -578,8 +563,8 @@
 For example, the consistency function of induced subgraph isomorphism is as follows.
 \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}\}$
+(u,\tilde{u})\in E_{small}\}$, and $\mathbf{\Gamma_{large}
+  (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$, where $u\in V_{small}$ and $v\in V_{large}$.
 \end{notation}
 
 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow
@@ -656,25 +641,15 @@
 
 \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
+$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
+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
+previous node in its component except the first node of each component.
 \end{claim}
 
 To summing up, a total ordering always uniquely determines a matching
@@ -782,7 +757,7 @@
 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}$.
+\begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u\in S : 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}
@@ -810,7 +785,7 @@
 \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$}
+\Procedure{VF2++ProcessLevel}{$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
@@ -858,10 +833,10 @@
  M[i] =
   \begin{cases} 
    v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INVALID &
-   if\ no\ node\ has\ been\ mapped\ to\ u_i.
+   if\ no\ node\ has\ been\ mapped\ to\ u_i,
   \end{cases}
 \]
-Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
+where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
 means "no node".
 \subsubsection{Avoiding the recurrence}
 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
@@ -884,7 +859,7 @@
 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the
 task is not to maintain the candidate set, but to generate the
 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$.  In
-case of any of the three problem type and a mapping $M$, if a node $v\in
+case of any of the three problem types and a mapping $M$ if a node $v\in
 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall
 u'\in V_{small} : (u,u')\in
 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in
@@ -893,7 +868,7 @@
 
 Having said that, an algorithm running in $\Theta(deg)$ time is
 describable if there exists a covered node in the component containing
-$u$, and a linear one other wise.
+$u$, and a linear one otherwise.
 
 
 \subsubsection{Determining the node order}
@@ -950,7 +925,7 @@
 \section{The VF2 Plus Algorithm}
 The VF2 Plus algorithm is a recently improved version of VF2. It was
 compared with the state of the art algorithms in \cite{VF2Plus} and
-has proven itself to be competitive with RI, the best algorithm on
+has proved itself to be competitive with RI, the best algorithm on
 biological graphs.  \\ A short summary of VF2 Plus follows, which uses
 the notation and the conventions of the original paper.
 
@@ -961,7 +936,7 @@
 algorithm.
 
 \begin{definition}
-$(u,v)$ is a \textbf{feasible pair}, if $lab(u)=lab(v)$ and
+$(u,v)$ is a \textbf{feasible pair} if $lab(u)=lab(v)$ and
   $deg(u)\leq deg(v)$, where $u\in{V_{small}}$ and $ v\in{V_{large}}$.
 \end{definition}
 $P_{lab}(L):=$ a priori probability to find a node with label $L$ in
@@ -975,8 +950,9 @@
 selected, and $degreeM$ of a node is the number of its neighbours in
 $M$.
 \begin{algorithm}
-\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
-nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
+\algtext*{EndIf}%ne nyomtasson end if-et
+\algtext*{EndFor}%nenyomtasson ..  
+\algtext*{EndProcedure}%ne nyomtasson ..
 \algtext*{EndWhile}
 \caption{}\label{alg:VF2PlusPseu}
 \begin{algorithmic}[1]
@@ -1023,13 +999,76 @@
 In the following, the induced subgraph isomorphism and the graph
 isomorphism will be examined.
 
-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}.
+This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For runtime results, please see Figure~\ref{fig:bioIND}.
 
 In an other experiment, the nodes of each graph in the database had been
 shuffled, and an isomorphism between the shuffled and the original
 graph was searched. The solution times are shown on Figure~\ref{fig:bioISO}.
 
 
+\begin{figure}[H]
+\vspace*{-2cm}
+\hspace*{-1.5cm}
+\begin{subfigure}[b]{0.55\textwidth}
+\begin{figure}[H]
+\begin{tikzpicture}[trim axis left, trim axis right]
+\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
+=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
+  west},scaled x ticks = false,x tick label style={/pgf/number
+  format/1000 sep = \thinspace}]
+%\addplot+[only marks] table {proteinsOrig.txt};
+\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
+  size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
+\end{axis}
+\end{tikzpicture}
+\caption{In the case of molecules, the algorithms have
+  similar behaviour, but VF2++ is almost two times faster even on such
+  small graphs.} \label{fig:INDMolecule}
+\end{figure}
+\end{subfigure}
+\hspace*{1.5cm}
+\begin{subfigure}[b]{0.55\textwidth}
+\begin{figure}[H]
+\begin{tikzpicture}[trim axis left, trim axis right]
+\begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
+=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
+  west},scaled x ticks = false,x tick label style={/pgf/number
+  format/1000 sep = \thinspace}]
+%\addplot+[only marks] table {proteinsOrig.txt};
+\addplot table {Orig/ContactMaps.128.txt};
+\addplot[mark=triangle*,mark size=1.8pt,color=red] table
+        {VF2PPLabel/ContactMaps.128.txt};
+\end{axis}
+\end{tikzpicture}
+\caption{On contact maps, VF2++ runs almost in constant time, while VF2
+  Plus has a near linear behaviour.} \label{fig:INDContact}
+\end{figure}
+\end{subfigure}
+
+\begin{center}
+\vspace*{-0.5cm}
+\begin{subfigure}[b]{0.55\textwidth}
+\begin{figure}[H]
+\begin{tikzpicture}[trim axis left, trim axis right]
+  \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
+  =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
+    west},scaled x ticks = false,x tick label style={/pgf/number
+    format/1000 sep = \thinspace}] %\addplot+[only marks] table
+    {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
+    table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
+      size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
+  \end{axis}
+  \end{tikzpicture}
+\caption{Both the algorithms have linear behaviour on protein
+  graphs. VF2++ is more than 10 times faster than VF2
+  Plus.} \label{fig:INDProt}
+\end{figure}
+\end{subfigure}
+\end{center}
+\vspace*{-0.5cm}
+\caption{\normalsize{Induced subgraph isomorphism on biological graphs}}\label{fig:bioIND}
+\end{figure}
+
 
 \begin{figure}[H]
 \vspace*{-2cm}
@@ -1090,75 +1129,10 @@
 \end{subfigure}
 \end{center}
 \vspace*{-0.6cm}
-\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioISO}
+\caption{\normalsize{Graph isomorphism on biological graphs}}\label{fig:bioISO}
 \end{figure}
 
 
-\begin{figure}[H]
-\vspace*{-2cm}
-\hspace*{-1.5cm}
-\begin{subfigure}[b]{0.55\textwidth}
-\begin{figure}[H]
-\begin{tikzpicture}[trim axis left, trim axis right]
-\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
-=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
-  west},scaled x ticks = false,x tick label style={/pgf/number
-  format/1000 sep = \thinspace}]
-%\addplot+[only marks] table {proteinsOrig.txt};
-\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
-  size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
-\end{axis}
-\end{tikzpicture}
-\caption{In the case of molecules, the algorithms have
-  similar behaviour, but VF2++ is almost two times faster even on such
-  small graphs.} \label{fig:INDMolecule}
-\end{figure}
-\end{subfigure}
-\hspace*{1.5cm}
-\begin{subfigure}[b]{0.55\textwidth}
-\begin{figure}[H]
-\begin{tikzpicture}[trim axis left, trim axis right]
-\begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
-=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
-  west},scaled x ticks = false,x tick label style={/pgf/number
-  format/1000 sep = \thinspace}]
-%\addplot+[only marks] table {proteinsOrig.txt};
-\addplot table {Orig/ContactMaps.128.txt};
-\addplot[mark=triangle*,mark size=1.8pt,color=red] table
-        {VF2PPLabel/ContactMaps.128.txt};
-\end{axis}
-\end{tikzpicture}
-\caption{On contact maps, VF2++ runs in near constant time, while VF2
-  Plus has a near linear behaviour.} \label{fig:INDContact}
-\end{figure}
-\end{subfigure}
-
-\begin{center}
-\vspace*{-0.5cm}
-\begin{subfigure}[b]{0.55\textwidth}
-\begin{figure}[H]
-\begin{tikzpicture}[trim axis left, trim axis right]
-  \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
-  =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
-    west},scaled x ticks = false,x tick label style={/pgf/number
-    format/1000 sep = \thinspace}] %\addplot+[only marks] table
-    {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
-    table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
-      size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
-  \end{axis}
-  \end{tikzpicture}
-\caption{Both the algorithms have linear behaviour on protein
-  graphs. VF2++ is more than 10 times faster than VF2
-  Plus.} \label{fig:INDProt}
-\end{figure}
-\end{subfigure}
-\end{center}
-\vspace*{-0.5cm}
-\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioIND}
-\end{figure}
-
-
-
 
 
 \subsection{Random graphs}
@@ -1168,7 +1142,7 @@
 experiments, please see the top of each chart.
 \subsubsection{Graph isomorphism}
 To evaluate the efficiency of the algorithms in the case of graph
-isomorphism, connected graphs of less than 20 000 nodes have been
+isomorphism, random connected graphs of less than 20 000 nodes have been
 considered. Generating a random graph and shuffling its nodes, an
 isomorphism had to be found. Figure \ref{fig:randISO} shows the runtime results
 on graph sets of various density.
@@ -1276,29 +1250,15 @@
 \end{figure}
 
 
-
-
-
-
-
-
-
-
-Considering the graph isomorphism problem, VF2++ consistently
-outperforms its rival especially on sparse graphs. The reason for the
-slightly super linear behaviour of VF2++ on denser graphs is the
-larger number of nodes in the BFS tree constructed in
-Algorithm~\ref{alg:VF2PPPseu}.
-
 \subsubsection{Induced subgraph isomorphism}
-This section provides a comparison of VF2++ and VF2 Plus in the case
+This section presents a comparison of VF2++ and VF2 Plus in the case
 of induced subgraph isomorphism. In addition to the size of the large
 graph, that of the small graph dramatically influences the hardness of
 a given problem too, so the overall picture is provided by examining
 small graphs of various size.
 
-For each chart, a number $0<\rho< 1$ has been fixed and the following
-has been executed 150 times. Generating a large graph $G_{large}$,
+For each chart, a number $0<\rho< 1$ has been fixed, and the following
+has been executed 150 times. Generating a large graph $G_{large}$ of an average degree of $\delta$,
 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,
 and for all the 10 subgraphs find a mapping by using both the graph
 matching algorithms.  The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
@@ -1610,7 +1570,7 @@
 considered and the small graphs had proportionally few nodes ($\rho =
 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node
 orders (e.g. see the $\delta=10$ case on
-Figure~\ref{fig:randIND10}). If these examples had been excluded, the
+Figure~\ref{fig:randIND10}). If these instances had been excluded, the
 charts would have seemed to be similar to the other ones.
 Unsurprisingly, as denser graphs are considered, both VF2++ and VF2
 Plus slow slightly down, but remain practically usable even on graphs