# HG changeset patch # User Madarasi Peter # Date 1480521156 -3600 # Node ID 1a4874982d84e34c18bc8377125b92bdf4c79852 # Parent 54e95bfead8c580f84ec9e865e5a35496945e7c9 outline, fine tune diff -r 54e95bfead8c -r 1a4874982d84 damecco.tex --- a/damecco.tex Wed Nov 30 16:13:29 2016 +0100 +++ b/damecco.tex Wed Nov 30 16:52:36 2016 +0100 @@ -274,7 +274,9 @@ code --- has been published as a part of LEMON\cite{LEMON} open source graph library. -\section{Problem Statement} +Outline: Section~\ref{sec:ProbStat} defines the problems to be solved, Section~\ref{sec:VF2Alg} provides a description of VF2, Section~\ref{sec:VF2ppAlg} introduces VF2++, a new graph matching algorithm, Section~\ref{sec:VF2ppImpl} presents the details of an efficient implementation of VF2++, and Section~\ref{sec:ExpRes} compares VF2++ to a state of the art algorithm. + +\section{Problem Statement}\label{sec:ProbStat} This section provides a formal description of the problems to be solved. \subsection{Definitions} @@ -340,17 +342,13 @@ 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. +In addition, one may want to find a \textbf{single} mapping or \textbf{enumerate} all of them. -It should be noted that some authors misleadingly refer to the term +Note that some authors 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} +\section{The VF2 Algorithm}\label{sec:VF2Alg} 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, @@ -549,7 +547,7 @@ \tilde{T}_{1}(\mathfrak{m})|$ is a cutting function by $IND$. \end{claim} -\section{The VF2++ Algorithm} +\section{The VF2++ Algorithm}\label{sec:VF2ppAlg} 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 @@ -564,18 +562,15 @@ 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. +designed. -Note that a weaker version of the cutting rules and the more efficient -candidate set calculating were described in \cite{VF2Plus}, too. +Note that a weaker version of the cutting rules and an efficient +candidate set calculating were described in \cite{VF2Plus}. It should be noted that all the methods described in this section are -extendable to handle directed graphs and edge labels as well.\newline - +extendable to handle directed graphs and edge labels as well. The basic ideas and the detailed description of VF2++ are provided in -the following. +the following.\newline The goal is to find a matching order in which the algorithm is able to recognize inconsistency or prune the infeasible branches on the @@ -624,11 +619,11 @@ \newline $\mathcal{L}(v):=black$ \newline -$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in (V_{1}\backslash -\{u\})$ +$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash +\{u\}$ \newline -$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in (V_{2}\backslash -\{v\})$ +$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash +\{v\}$ \newline Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since @@ -732,7 +727,7 @@ \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1} \begin{algorithmic}[1] \Procedure{VF2++ProcessLevel}{$V_{d}$} \While{$V_d\neq\emptyset$} -\State $m\in$ arg min$_{F_\mathcal{M}\circ\ \mathcal{L}}($ arg max$_{deg}($arg +\State $m\in$ arg min$_{F_{\mathcal{M}\circ\ \mathcal{L}}}($ 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 @@ -778,10 +773,10 @@ -\section{Implementation details} +\section{Implementation details}\label{sec:VF2ppImpl} This section provides a detailed summary of an efficient implementation of VF2++. -\subsubsection{Storing a mapping} +\subsection{Storing a mapping} After fixing an arbitrary node order ($u_0, u_1, .., u_{|G_{1}|-1}$) of $G_{1}$, an array $M$ is usable to store the current mapping in the following way. @@ -794,7 +789,7 @@ \] where $i\in\{0,1, ..,|G_{1}|-1\}$, $v\in V_{2}$ and $INV\!ALI\!D$ means "no node". -\subsubsection{Avoiding the recurrence} +\subsection{Avoiding the recurrence} The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized as a \textit{while loop}, which has a loop counter $depth$ denoting the all-time depth of the recursion. Fixing a matching order, let $M$ @@ -811,7 +806,7 @@ has been designed for biological- and sparse graphs, see the next section for details. -\subsubsection{Calculating the candidates for a node} +\subsection{Calculating the candidates for a node} Being aware of Claim~\ref{claim:claimCoverFromLeft}, the task is not to maintain the candidate set, but to generate the candidate nodes in $G_{2}$ for a given node $u\in V_{1}$. In @@ -827,7 +822,7 @@ $u$, and a linear one otherwise. -\subsubsection{Determining the node order} +\subsection{Determining the node order} This section describes how the node order preprocessing method of VF2++ can efficiently be implemented. @@ -841,7 +836,7 @@ Representing $\mathcal{M}\subseteq V_{1}$ as an array of size $|V_{1}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes. -\subsubsection{Cutting rules} +\subsection{Cutting rules} In Section~\ref{VF2PPCuttingRules}, the cutting rules were described using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$ and $\tilde T_{2}$, which are dependent on the all-time mapping @@ -876,7 +871,7 @@ Using similar techniques, the consistency function can be evaluated in $\Theta(deg)$ steps, as well. -\section{Experimental results} +\section{Experimental results}\label{sec:ExpRes} This section compares the performance of VF2++ and VF2 Plus. According to our experience, both algorithms run faster than VF2 with orders of magnitude, thus its inclusion was not reasonable.