1.1 --- a/damecco.tex Wed Nov 30 22:45:35 2016 +0100
1.2 +++ b/damecco.tex Wed Nov 30 23:03:41 2016 +0100
1.3 @@ -103,46 +103,60 @@
1.4 %% \address{Address\fnref{label3}}
1.5 %% \fntext[label3]{}
1.6
1.7 -\title{VF2++ --- An Improved Subgraph Isomorphism Algorithm}
1.8 +\title{Improved Algorithms for Matching Biological Graphs}
1.9
1.10 %% use optional labels to link authors explicitly to addresses:
1.11 %% \author[label1,label2]{}
1.12 %% \address[label1]{}
1.13 %% \address[label2]{}
1.14
1.15 -\author[egres,elte]{Alp{\'a}r J{\"u}ttner}
1.16 -\ead{alpar@cs.elte.hu}
1.17 -\author[elte]{P{\'e}ter Madarasi}
1.18 -\ead{madarasip@caesar.elte.hu}
1.19 -\address[egres]{MTA-ELTE Egerv{\'a}ry Research Group, Budapest, Hungary.}
1.20 -\address[elte]{Department of Operations Research, E{\"o}tv{\"o}s Lor{\'a}nd University, Budapest, Hungary.}
1.21 +\author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}
1.22 +
1.23 +\address{Dept of Operations Research, ELTE}
1.24
1.25 \begin{abstract}
1.26 +Subgraph isomorphism is a well-known NP-Complete problem, while its
1.27 +special case, the graph isomorphism problem is one of the few problems
1.28 +in NP neither known to be in P nor NP-Complete. Their appearance in
1.29 +many fields of application such as pattern analysis, computer vision
1.30 +questions and the analysis of chemical and biological systems has
1.31 +fostered the design of various algorithms for handling special graph
1.32 +structures.
1.33
1.34 - This paper presents a largely improved version of the VF2 algorithm
1.35 - for the \emph{Subgraph Isomorphism Problem}. The improvements are
1.36 - twofold. Firstly, it is based on a new approach for determining the
1.37 - matching order of the nodes, and secondly, more efficient -
1.38 - nevertheless easier to compute - cutting rules significantly
1.39 - reducing the search space are applied.
1.40 +This paper presents VF2++, a new algorithm based on the original VF2,
1.41 +which runs significantly faster on most test cases and performs
1.42 +especially well on special graph classes stemming from biological
1.43 +questions. VF2++ handles graphs of thousands of nodes in practically
1.44 +near linear time including preprocessing. Not only is it an improved
1.45 +version of VF2, but in fact, it is by far the fastest existing
1.46 +algorithm especially on biological graphs.
1.47
1.48 - In addition to the usual subgraph isomorphism, the paper also
1.49 - presents specialized versions for the \emph{Induced Subgraph
1.50 - Isomorphism} and for the \emph{Graph Isomorphism Problems}.
1.51 +The reason for VF2++' superiority over VF2 is twofold. Firstly, taking
1.52 +into account the structure and the node labeling of the graph, VF2++
1.53 +determines a state order in which most of the unfruitful branches of
1.54 +the search space can be pruned immediately. Secondly, introducing more
1.55 +efficient - nevertheless still easier to compute - cutting rules
1.56 +reduces the chance of going astray even further.
1.57
1.58 - Finally, an extensive experimental evaluation is provided using a
1.59 - wide range of inputs, including both real life biological and
1.60 - chemical datasets and standard randomly generated graph series. The
1.61 - results show major and consistent running time improvements over the
1.62 - other known methods.
1.63 -
1.64 - The C++ implementations of the algorithms are available open source as
1.65 - the part of the LEMON graph and network optimization library.
1.66 -
1.67 +In addition to the usual subgraph isomorphism, specialized versions
1.68 +for induced subgraph isomorphism and for graph isomorphism are
1.69 +presented. VF2++ has gained a runtime improvement of one order of
1.70 +magnitude respecting induced subgraph isomorphism and a better
1.71 +asymptotical behaviour in the case of graph isomorphism problem.
1.72 +
1.73 +After having provided the description of VF2++, in order to evaluate
1.74 +its effectiveness, an extensive comparison to the contemporary other
1.75 +algorithms is shown, using a wide range of inputs, including both real
1.76 +life biological and chemical datasets and standard randomly generated
1.77 +graph series.
1.78 +
1.79 +The work was motivated and sponsored by QuantumBio Inc., and all the
1.80 +developed algorithms are available as the part of the open source
1.81 +LEMON graph and network optimization library
1.82 +(http://lemon.cs.elte.hu).
1.83 \end{abstract}
1.84
1.85 \begin{keyword}
1.86 - Computational Biology, Subgraph Isomorphism Problem
1.87 %% keywords here, in the form: keyword \sep keyword
1.88
1.89 %% PACS codes here, in the form: \PACS code \sep code
1.90 @@ -180,7 +194,7 @@
1.91 edges to chemical bonds. The similarity and dissimilarity of
1.92 objects corresponding to nodes are incorporated to the model
1.93 by \emph{node labels}. Understanding such networks basically
1.94 -requires finding specific subgraphs, thus calls for efficient
1.95 +requires finding specific subgraphs, thus it calls for efficient
1.96 graph matching algorithms.
1.97
1.98 Other real-world fields related to some
1.99 @@ -255,12 +269,13 @@
1.100 efficient cutting rules and determines a node order in which VF2 runs
1.101 significantly faster on practical inputs.
1.102
1.103 +graph and network optimization library
1.104 +
1.105 This project was initiated and sponsored by QuantumBio
1.106 -Inc.\cite{QUANTUMBIO} and the implementation --- along with a source
1.107 -code --- has been published as a part of LEMON\cite{LEMON} open source
1.108 -graph library.
1.109 +Inc.\cite{QUANTUMBIO} and the implementation is available open source as the
1.110 +part of the LEMON\cite{LEMON} graph and network optimization library.
1.111
1.112 -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.
1.113 +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 the state of the art algorithm.
1.114
1.115 \section{Problem Statement}\label{sec:ProbStat}
1.116 This section provides a formal description of the problems to be