% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.4 for LaTeX2e as of 16. April 2010
%
\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%

\usepackage{times}
\usepackage{amsmath}
\usepackage{balance}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{color}
\usepackage{algorithmic}
\usepackage{url}
\usepackage[boxed,noend]{algorithm2e}
\usepackage{mdwlist}
%\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{epstopdf}


\begin{document}
%
% \frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
\vspace{1cm}
\tableofcontents
%
\mainmatter              % start of the contributions
%
\title{gLabTrie: a data structure for motif discovery with constraints}
%
\titlerunning{gLabTrie}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Giovanni/Misael et al\inst{1} \and SnoopDog\inst{2}}
%
%
%
\institute{Catania,\\
\email{I.Ekeland@princeton.edu},\\ WWW home page:
\texttt{http://users/\homedir iekeland/web/welcome.html}
\and
SnoopDog academy
France}

\maketitle              % typeset the title of the contribution

\begin{abstract}
Motif finding in a graph G is the problem of 
discovering a subgraph S in G that appears surprisingly often.  
Such a subgraph may have practical significance 
(e.g. it might indicate an evolutionarily conserved interaction 
pattern in biology). 
We look at the problem of constrained search for motifs based on labels. 
For example, we might be concerned with genomic interaction patterns 
involving metabolic genes or social interaction patterns 
involving rock musicians. 
This chapter reviews the state of the art in 
motif finding 
and then extends the gTrie data structure from 
Ribeiro's thesis to support labels. 
Experiments validate the usefulness of our structure.
\keywords{graphs, motif finding, constraints}
\end{abstract}
%
\section{The Problem and its Motivation}

A motif in a graph is a subgraph that appears 
statistically significantly often. 
Frequently occurring motifs may have practical significance. 
One familiar example is the ubiquity of feedback 
networks underlying homeostasis in 
biological, natural, and even economic systems. 
As an engineering example, X et al [ref to synthetic biology paper] 
use the frequent motifs found in biological networks as a 
library for synthetic biology. 
In fact X et al pointed out that there are often motifs that behave 
as a single node in a larger network motif. 
So, there may be motifs at different levels of abstraction. 
For the purposes of our chapter, we will take 
the usefulness of motifs for granted and talk 
about how to discover such motifs efficiently.

Further, we will be particularly concerned with graphs 
whose vertices have labels. 
We will use the notation G = (V, E, L, Lab) 
where V is the set of vertices, 
E is a set of directed or undirected edges on V and L 
is a function from V to a set of labels Lab.  
A constrained motif query is to find a statistically 
significant motif satisfying some constraint on the labels. 
Our notion of constraint is simply a count of labels from the set Lab. 

In the sequel we will define our notion of statistical significance, 
but informally, this will entail a simulation of the following process: 
1. find many random variations of the input graph G where 
each random variation preserves the degree counts of each node 
in G and preserves the number of edges linking nodes
having each pair of labels. 
2. See how often a motif of interest is found in those random graphs. 
If infrequently, then the motif is significant in G.

The computational challenge in motif finding is that the number 
of possible subgraphs could, depending on the graph, 
grow exponentially with the size of the subgraph. 
For a completely connected graph 
G = (V, E, L, Lab), there are $|E|$ subgraphs of size 2 (having
two nodes),
$|E| times |E|$ subgraphs of size 3, and in general $|E| sup {k}$ 
of size k.
For sparser graphs, the growth may be less dramatic, but still exponential.

For that reason, we require data structures to make this fast.
Our work builds directly on the beautiful gTrie data structure
developed by Ribeiro [ref] which is why we call our structure
gLabTrie.

\section{Related Work}

{\em Misael writes this: review definitions.
Start with Uri Alon work and then
discuss briefly the other works, but focus on ESU and on gTrie.
Show pictures of the latter two structures and explain them in detail.
Note that gTrie is better for small graphs but Ribeiro suspects
that ESU might be better otherwise.}

review definitions.
Start with Uri Alon work and then
discuss briefly the other works, but focus on ESU and on gTrie.
Show pictures of the latter two structures and explain them in detail.
Note that gTrie is better for small graphs but Ribeiro suspects
that ESU might be better otherwise.

Also, here are some other references that constitute the other works:



2002 Milo et al networks from diverse fields
contain patterns that are unlikely to occur by chance.

Statistically overrepresented sub-structures.

Feedforward loop:

X ---> Z, Y --> Z, X --> Y.

All interactions are positive happens a lot.
X induces Z, X positive towards Y, but Y represses Z
happens a lot.
In Ecoli and yeast.

Other ones like:
autoregulation, single input module, dense overlapping regulons and feedback loops, etc



====
Synthetic bio ref
http://kurata21.bio.kyutech.ac.jp/cadlive/References/Brief%20Bioinform-2013-Kurata.pdf

BioFNet: biological functional network
database for analysis and synthesis of
biological systems
Hiroyuki Kurata, Kazuhiro Maeda, Toshikazu Onaka and Takenori Takata
Briefings in Bioinformatics Advance Access published July 27, 2013
BRIEFINGS IN BIOINFORMATICS. page 1 of 11 doi:10.1093/bib/bbt048

This paper discusses motifs in both synthetic and natural networks.
Smaller motifs can be part of larger motifs, e.g. feed forward
networks can be part of first-in first-out networks.
(Figures 1 and 2) based on different kinetic coefficients.

Also" "Addition of a functional network to an existing
network can enhance the function of the existing
one. Addition of a positive feedback loop to a negative
feedback loop network enhances the oscillatory
behavior generated by the negative feedback"

Can get robustness:
"In this context, biological
design is characterized by the fact that cells must
coexist with such parameter uncertainty and noise.
In fact, some biochemical systems use noise to enhance
oscillation and bistability or to generate heterogeneity
of gene expression. Noise-generated
heterogeneity can increase the chances for some
parts of the cell population to adapt to fluctuating
environments. They may be advantageous for survival
in consistently fluctuating environments."

So conclusion is that we want to detect all motifs.
There may be overlap..

BioFNet
$http://kurata22.bio.kyutech.ac.jp/db/pub/pub_main.php?Ver=3.7$

Could look just for those motifs.

Also would want to query on edges as well.

=====

$survey_freq_subgraph.pdf$
The Knowledge Engineering Review, Vol. 00:0, 1–31.
c 2004, Cambridge University Press
DOI: 10.1017/S000000000000000 Printed in the United Kingdom
A Survey of Frequent Subgraph Mining Algorithms
Chuntao Jiang, Frans Coenen and Michele Zito

        Chuntao Jiang, Frans Coenen, Michele Zito: A survey of frequent subgraph mining algorithms. Knowledge Eng. Review 28(1): 75-105 (2013)


p. 8:
"A canonical labelling strategy defines a unique code for a given graph"

We want this to detect identical graphs (not isomorphic ones,
as the paper says, but identical ones).
One approach is simply to use the node ids but in the case
of loops this leads to ambiguity.
Another approach is to name the edges by their vertex ids
and then sort them by their vertex ids in lexicographic order.
I think this should work as long as every edge has the same label.

DISCUSS: why aren't we talking about frequent subgraph mining algorithms.

DISCUSS: "For discussion purposes, the FGM algorithms examined in this section are categorized into
“general purpose” and “pattern dependent” FGM. The distinction is that in the latter case
the nature of the patterns to be discovered is in some way specialized or limited because of
the nature of the application domain (e.g. we are only interested in subgraphs satisfying some
specific constraints). Consequently, knowledge of the nature of these special patterns allows for
a reduction of the search space."

DISCUSS: p. 22:
"Relational graphs are suitable for modelling large scale networks such as biological or social
networks. Yan et al. (2005a) indicated that relational pattern mining has three features which
serve to differentiate it from general purpose frequent subgraph mining: (i) the data has distinct
vertex labels, (ii) the data comprises very large graphs, and (iii) a focus on frequent patterns with
certain connectivity constraints (e.g. the minimum degree19 of a pattern). Thus relational graph
mining aims to identify all frequent patterns displaying a specified connectivity constraint."

Should read section 5.2 of this paper.

DISCUSS:
5.2.4 Constrained pattern mining
The main idea of user constraint based frequent pattern mining is to integrate constraints into
the mining process in order to prune the search space. Zhu et al. (2007) presented a framework,
called gPrune, to incorporate various constraints into the frequent subgraph mining process. In
gPrune, the search spaces of both data and patterns were examined and a new concept, patterninseparable-
data-anti-monotonicity (D-anti-monotonicity), introduced to support effective pruning
of the search space. However, an empirical study showed that the benefit of such D-antimonotonicity
pruning was coupled tightly with the speed of the corresponding constraint measure
function. Furthermore, experiments indicated that the effectiveness of integrating constraints
into the FSM process is influenced by many aspects, including the properties of the data and
the pruning cost. Constraint based mining algorithms therefore need to take into account the
trade-off between the pruning cost and any potential benefit.


=====

Ribeiro thesis:

p. 32:
Analytical methods to estimate the significance of motifs are
now appearing [MSB+06, PDK+08]. These methods would be able to escape the need
for the ensemble of random networks and their respective census, but there is still a
long path to be accomplished in order for them to be general and practical enough

pp. 40ff: lots of nice pictures.

p. 43: The original paper from Milo et al. [MSOI+02] uses {0.01, 4, 0.1, 1000} as the set of
respective parameters {P, U,D,N}. This is the same as saying that they used 1000
similar random networks and considered a subgraph to be a motif if: the probability
that it appears more often in a random network than in the original network is less
than 1%; it appeared at least 4 times; the difference between its frequency in the
original network and the average frequency in random networks is at least 10% of that
average frequency.

p. 49: We should also note that Birmel´e presented an alternative motif definition, in which
significance is evaluated through local over-representation, instead of global overrepresentation,
and introduced a statistical method for computing this measure without
the generation of random networks [Bir11].

p. 50 to distinguish with frequent subgraph mining:
is substantially different because its goal
is to find the most frequent subgraphs that appear in a set of graphs, while in the
network motifs we try to find the frequency of all subgraphs on a single graph.

p. 51: Figures of motifs.

p. 58: basic algorithm.

Algorithm 3.1 Typical program flow of motif discovery.
Require: Graph G and integers k and R
Ensure: Motifs of size k in graph G
1: subgraphCensus(k, G)
2: for i := 1 to R do
3: Ri := generateSimilarRandomNetwork(G)
4: subgraphCensus(k, Ri)
5: calculateSignificanceMotifs()

pp. 60 ff: description of the algorithms.

Symmetry Breaking indicates if the method only finds once each occurrence of the
motif. Since a subgraph can have several automorphisms, a careless approach could
end up finding the same subgraph following a different search path. It is therefore
desirable to find each instance only once, avoiding redundant calculations due to
symmetry.

pp. 64ff: starts with netfinder.

p. 66
ESU: the way you read it is that on the left of the comma,
you have the nodes in the growing subgraph and to the right
you have candidate neighbors (whose numbers must
be greater than the "spawning" node which seems to be
the last node added).


1 -- 3 -- 2 ==> seems like we never get all three nodes.

\input{related_and_pval_revised}

\section{gLabTrie structure}

\subsection{Preliminaries}

We define formally the \emph{input network} (denoted by $\mathbb{G}$), \emph{topologies} (denoted by $G$), i.e. unlabeled graphs that represent motif structures and \emph{topology instances} (denoted by $g$), i.e. subgraphs of $\mathbb{G}$ that accommodate certain topologies. We also introduce the notation that we use in the rest of the paper (\emph{isomorphism}, \emph{orbit} and \emph{canonical label}). 

We consider directed and undirected graphs. For simplicity, in our discussion we refer to undirected graphs, although our method works with directed graphs as well. Given a graph $G$, we denote with $V_G$ its set of vertices, with $E_G$ its set of edges, with $L_G$ its alphabet of labels and with $l_G$ a function that assign a label to each vertex. We also write $G=(V_G,E_G,L_G,l_G)$. A subgraph $G'$ of a graph $G$ (denoted by $G'\subseteq G$) is a graph that contain a subset of vertices and a subset of edges of $G$ (i.e. $V_{G'}\subseteq V_{G}$ and $E_{G'}\subseteq E_{G}$).

An \emph{isomorphism} between two graphs $G_1$ and $G_2$ is a one-to-one mapping $\varphi : V_{G_1} \rightarrow V_{G_2}$ between vertices, which preserves the structure, i.e. $(u,v)\in G_1 \Leftrightarrow (\varphi(u),\varphi(v)) \in G_2$, and the labels, i.e. $l_G(u)=l_G(\varphi(u))$. If there is at least an isomorphism between $G_1$ and $G_2$ we say that they are \emph{isomorphic} and write $G_1 \sim G_2$. An automorphism in $G$ is an isomorphism between $G$ and itself. Every graph admits at least one automorphism (where each node corresponds to itself). Typically, a graph can have many automorphisms. We abuse the notation and write $\varphi(G)$, with $G \subseteq G_1$ to denote the subgraph of $G_2$ that corresponds to $G$ according to $\varphi$ (i.e. the subgraph composed by nodes $\varphi(v)$ with $v\in G$ and edges $(\varphi(v_1),\varphi(v_2))$ with $(v_1,v_2)\in G$).

We call \emph{labeled topology} an undirected labeled connected graph $G$. An \emph{unlabeled topology} is a labeled topology stripped off of its labels. A labeled topology that occurs frequently in $G$ is also called \emph{motif}. An \emph{occurrence} $g$ of a topology $G$ is a connected subgraph of $\mathbb{G}$ that is isomorphic to $G$. 

%\reminder{Say that we call $u$ both the node and its id}

%\reminder{Describe canonical form and canonical order}

%\reminder{define orbits}

\subsection{Problem definition}

We aim at processing \emph{motif-based queries}, i.e. the user specifies a set of constraints and the system returns all motifs that satisfy the constraints. Typically a user specifies a frequency threshold, a p-value threshold and a bag (multiset) of labels that the motifs must contain. An example of query would be: ``Give me all labeled topologies that have at least two labels A and one label B, occur at least $f$ times and have a p-value smaller than $p$''. We also want the query processing to be really fast, so as a user that is not satisfied with the answer can change the constraints and quickly get the new answer. We accept a slow off-line \emph{preprocessing} step in change to fast \emph{query processing}. 

More precisely, we define a \emph{motif-based query} (more simply a query) as a quadruple $Q=(C,k,f,p)$, where $C$ is a bag of labels (a bag, also called multiset, is similar to a set, but an element may occur more than once), $k$ is the requested size of motifs, $f$ is a frequency threshold and $p$ is a p-value threshold. Now we are ready to define our problem.

\begin{definition}
\textbf{Motif-based query processing}. Given a network $\mathbb{G}$ and a query $Q=(C,k,f,p)$, find all labeled topologies $T$ with size $k$, whose number of occurrences in $\mathbb{G}$ is above or attained to $f$ and whose p-value is below or attained to $p$.
\end{definition}

We solve the defined problem in two steps. During an offline \emph{preprocessing} phase we census the input network to find all labeled motifs up to a certain size $K$, and organize them in a suitable data structure (that we call the \emph{index}). Later, during the online \emph{query processing} phase, we probe the index to efficiently retrieve motifs that satisfy the query constraints.

In the remaining part of this section we describe how we extend existing approaches to support labeled motifs and the data structure used for quickly processing queries.

\subsection{Labeled motifs}

We propose a method for enhancing existing network-centric methods for motif discovery to support labeled motifs. The main data structure of a network-centric method is a key-value map (hash table or binary tree) that associates each unlabeled topology (up to a certain size) to a counter. Unlabeled topologies can be represented by their canonical form, so that equivalence check is efficient. The overall algorithm is shown in Alg.~\ref{alg:overall}.

\begin{algorithm}
\caption{Overall network-centric algorithm for unlabeled motif discovery}\label{alg:overall}
\begin{algorithmic}
	\REQUIRE network, frequency threshold $f$, p-value threshold $p$, number of randomizations $r$
	\COMMENT {returns the set of motifs with frequency $\geq f$ and p-value $\leq p$}
	\STATE initialize $map$
	\STATE call $census(network,map)$
	\STATE initialize $map\_count$
\FOR{$i=0\ldots r$} 
	\STATE $rand\_net = randomize(network)$
	\STATE initialize $map\_rand$
	\STATE call $census(rand\_net, map\_rand)$
	\FOR{all $t \in keys(map\_rand)$}
		\IF {$map\_rand[t]\geq map[t]$} 
		\STATE $map\_count[t] = map\_count[t] + 1$
		\ENDIF
	\ENDFOR
\ENDFOR
\FOR{all $t \in keys(map\_count)$}
	\STATE $pval = map\_count[t]/r$
	\IF {$map[t] \geq f$ and $pval\leq p$} 
	\STATE output $t$, $map[t]$, $pval$
	\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

The core procedure is $census()$, which takes as input a network and fills a map. This procedure enumerates all subgraphs of the network one by one and call a method $notify\_subgraph(map,topology)$ (not shown) for every subgraph of the input network. To perform a correct counting, every subgraph has to be processed exactly once. Graph census algorithms use a subgraph expanding procedure that takes one node at a time and expands it in all possible ways. Since this procedure is prone to find the same subgraph multiple times (there are many ways of producing the same subgraph), the census algorithms consider a carefully designed set of breaking conditions that guarantee that a subgraph is enumerated exactly once. The nodes of each topology must be given in a canonical order in order to quickly compute the canonical form.  

A straightforward way to handle labeled topologies consists in considering as keys for the map topology/counter the canonical form of labeled topologies as opposed as unlabeled topologies. This would require computing a canonical form for every subgraph of the network and would frustrate the effort of avoiding this expensive step, made by recent methods (such as gTrie). 

To avoid computing the canonical form for each subgraph, we resort to a different approach that consists in combining the canonical form of the unlabeled topology with the sequence of labels. This approach introduces the problem of determining the order of labels. Indeed, the canonical order of unlabeled topologies is not sufficient. To clarify this point let us consider the two subgraphs in Fig.~\ref{fig:example}. Numbers represent the canonical order of nodes, while letters represent labels. Note that the order between 2 and 3 is ambiguous (1-3-2 would be a valid order as well) since by exchanging them we obtain the same unlabeled canonical form. The two labeled topologies are clearly isomorphic. However the label sequences in the canonical orders are different (ABC vs. ACB). 

\begin{figure}[ht]
    \centering
    \includegraphics[width=.30\textwidth]{FIG/example.png}
   \caption{Example of two unlabeled canonical orders that produce different sequence of labels on isomorphic graphs. The order is given by numbers. The two corresponding sequences of labels are ABC and ACB.}\label{fig:example}
\end{figure}

To guarantee that isomorphic labeled topologies have the same label sequence, we solve the ambiguity in the canonical ordering by ordering labels (e.g. in alphabetic order) and using this order to break the ties. This is equivalent to choose, among all possible canonical orders, the one that corresponds to the smallest sequence of labels (in lexical order). Note that network-centric tools (e.g. gTrie) solve the ambiguity by considering the order of node ids to break the ties. Therefore we just need to ensure that the order of node ids is consistent with the order of labels. This can be done by reassigning node ids of the input network so as that nodes with smaller labels are assigned with smaller label ids (i.e. $v \leq u$ if $l_\mathbb{G}(v) \leq l_\mathbb{G}(u)$).

The procedure described above solve the problem in Fig.~\ref{fig:example}. Indeed the order of the second topology is forced to be as in Fig.~\ref{fig:example}
and hence both label sequences would be ABC. Now we prove that this procedure gives always the correct result. Specifically, we prove that:

\begin{figure}[ht]
    \centering
    \includegraphics[width=.30\textwidth]{FIG/example2.png}
   \caption{By considering unambiguous canonical orders we can guarantee that isomorphic graphs are associated with the same sequence of labels. In this example both sequences of labels are ABC.}\label{fig:example}
\end{figure}

\begin{itemize}
	\item if two labeled topologies are isomorphic then their associated canonical forms coincide;
	\item given two labeled topologies, if their corresponding canonical forms coincide, then they are isomorphic.
\end{itemize}

The second condition is trivial. Indeed the canonical order of two topologies defines an association between nodes that preserves both the structure and the label sequence.

In order to prove the first condition, we need to prove that if two labeled topologies are isomorphic then their corresponding sequence of labels coincide. Indeed the labeled canonical form is computed by combining the unlabeled canonical form with the sequence of label. Since by stripping off the labels two isomorphic topologies remain isomorphic, the two unlabeled canonical forms coincide. Therefore we need to be concerned only about the label sequences. 

\begin{lemma}
Let $G_1$, $G_2$ be two isomorphic labeled topologies and $S_1$, $S_2$ be the sequence of labels given by their corresponding unambiguous canonical order (i.e. there is no other canonical order that produces a sequence of label smaller than $S_1$, nor other canonical order that produces a sequence of label smaller than $S_1$, as assured by the previously described ordering of node ids). Then $S_1=S_2$. 
\end{lemma}

Proof: by contradiction suppose $S_1 \neq S_2$. Without lost in generality let's consider $S_1 \leq S_2$. Since $G_1$ and $G_2$ are isomorphic, there is at least an isomorphism between $G_1$ and $G_2$ (that is a one-to-one association between nodes of $G_1$ and nodes of $G_2$). We can use this node correspondence to construct an order of nodes for $G_2$ that equivalent to the canonical order of $G_1$. This is a valid canonical order for $G_2$ since it produces the same unlabeled canonical form. Moreover this order corresponds to the same sequence of labels as $S_1$. We found a valid canonical order for $G_2$ that produces a sequence of label smaller than $S_2$. This contradicts the hypothesis that there is no canonical order that produces a sequence of label smaller than $S_2$.


We change the overall algorithm (Alg.~\ref{alg:overall}) so as to support labels. The main change concerns the data structure that maintains the topology counters. Specifically, we substitute the maps topology/counter ($map$, $map\_rand$, $map\_count$) with key-value maps where keys are unlabeled topologies and values are themselves maps (as opposed to counters) that associate label sequences to counters. To retrieve the counter of a labeled topology we first look up the entry corresponding to its unlabeled topology, then we look up the counter associated with the label sequence in the corresponding map. 

Ultimately, we apply the following changes:

\begin{enumerate}
	\item we introduce a first step which reassigns ids to nodes of the input network so that nodes with smaller labels are assigned with smaller node ids;
	\item we change the maps topology/counter into maps topology/label map, where label map is a key-value map that associates label sequences to counters; 
	\item we change the method $notify\_subgraph(map,topology)$ into $notify\_subgraph(map,topology,label\_seq)$ and change the method $census()$ accordingly.
\end{enumerate}

The final overall algorithm for labeled motif discovery is shown in Alg.~\ref{alg:overall_labeled}.

\begin{algorithm}
\caption{Overall network-centric algorithm for labeled motif discovery}\label{alg:overall_labeled}
\begin{algorithmic}
	\REQUIRE network, frequency threshold $f$, p-value threshold $p$, number of randomizations $r$
	\COMMENT {returns the set of motifs with frequency $\geq f$ and p-value $\leq p$}
	\STATE initialize $map$
	\STATE call $census(network,map)$
	\STATE initialize $map\_count$
\FOR{$i=0\ldots r$} 
	\STATE $rand\_net = randomize(network)$
	\STATE initialize $map\_rand$
	\STATE call $census(rand\_net, map\_rand)$
	\FOR{all $t \in keys(map\_rand)$}
	\FOR{all $ls \in keys(map\_rand[t])$}
		\IF {$map\_rand[t][ls]\geq map[t][ls]$} 
		\STATE $map\_count[t][ls] = map\_count[t][ls] + 1$
		\ENDIF
	\ENDFOR
	\ENDFOR
\ENDFOR
\FOR{all $t \in keys(map\_count)$}
	\FOR{all $ls \in keys(map\_rand[t])$}
	\STATE $pval = map\_count[t][ls]/r$
	\IF {$map[t][ls] \geq f$ and $pval\leq p$} 
	\STATE output $t$, $map[t][ls]$, $pval$
	\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{An index for querying motifs}

During the preprocessing phase we find all motifs in the input network as described previously. We do not set a frequency threshold nor a p-value threshold so that all labeled topologies occurring in the input network are considered. We only limit the search to motifs with size not above $K$, where $K$ is a predefined parameter. To simplicity of exposition in the following we consider only motifs of size exactly $K$, although our method can encompass also motifs with size smaller than $K$. We put all extracted labeled topologies in a data structure, which we call the \emph{index}, that facilitates later retrieval. An example of index for $K=3$ and two labels (A and B) is depicted in Fig.~\ref{fig:index}. 

\begin{figure}[ht]
    \centering
    \includegraphics[width=.50\textwidth]{FIG/index.png}
   \caption{The index. Our data structure for processing motif-based queries}\label{fig:index}
\end{figure}

The index is composed by a DAG, which embodies the superset relation between sets, and a collection of lists of topologies contained in leaves of the DAG. Specifically, nodes of the DAG represent bags of labels (label constraints) and an edge is drawn between two nodes $u$ and $v$ if $v$ is superset of $u$ (i.e. it contains all labels in $u$ with multiplicity below or attained to the one in $v$), and $v$ has exactly one label more than $u$. The edge is associated with the label that is different between $u$ and $v$. Each leaf (node that does not have any outgoing edges) contains a list of all labeled topologies that satisfy label constraints associated with the leaf, with their frequencies and p-values. 

The described index enables fast look up of a bag of labels and then fast retrieval of associated topologies (by exploring the part of the DAG reachable from the corresponding node). The DAG shown in the example in Fig.~\ref{fig:index} is complete, but in general it may be incomplete. For instance, if there are no topologies with labels ABB and BBB, the nodes ABB, BBB and BB are not included in the DAG, thus making its exploration more efficient. 

\subsubsection{Building the index}

The building procedure is given in Alg.~\ref{alg:building}. First we group the topologies by their label bags. Then, for each label bag we create a leaf and store it in a hash table that associates label bags with the corresponding nodes. We create the other nodes of the DAG by calling $create\_dag()$ (Alg.~\ref{alg:create_dag}), which recursively removes one label a time from nodes and creates nodes up to the root. 

\begin{algorithm}
\caption{Building the index}\label{alg:building}
\begin{algorithmic}
	\REQUIRE set $T$ of labeled topologies of size $K$ with associated frequency and p-value
	\COMMENT {returns the root of the index data structure}
	\STATE group $T$ by label bags 
	\FOR {each label bags $lb$ and its corresponding set of topologies $T_{lb}$}
		\STATE initialize $node$ \COMMENT {create a leaf node}
		\STATE $node.label\_bag = lb$
		\STATE $node.topologies = T_{lb}$
		\STATE $hash\_table[lb] = node$ 
		\STATE call $create\_dag(node, hash\_table)$
	\ENDFOR
	\STATE return $hash\_table[\{\emptyset\}]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Recursive procedure $create\_dag$ for building the index}\label{alg:create_dag}
\begin{algorithmic}
	\REQUIRE a node $node$ and the hash table of nodes $hash\_table$
	\IF {$node.label\_bag == \emptyset$}
		\STATE return
	\ENDIF
	\FOR {all label $l$ in $node.label\_bag$}
		\STATE $lb\_parent = node.label\_bag - \{l\}$
		\IF {$lb\_parent \in keys(hash\_table)$}
			\STATE $parent = hash\_table[lb\_parent]$
		\ELSE
			\STATE initialize $parent$ \COMMENT {create a new node}
			\STATE $parent.label\_bag = lb\_parent$
			\STATE $hash\_table[lb\_parent] = parent$
			\STATE call $create\_dag(parent, hash\_table)$
		\ENDIF
		\STATE $parent.children[l] = node$
	\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsubsection{Query processing}

Given the index described above, and a query $Q=(C,k,f,p)$ with $k=K$, the query processing is quite straightforward. Note that with small changes the index can support queries of size $k\leq K$, while answering queries with $k\geq K$ is not trivial and will be subject of further investigation. 

To perform a query $Q=(C,k,f,p)$ with $k=K$, we first look up the node $n$ of the DAG associated with the set of labels in $C$, then we explore all nodes of the DAG reachable from $n$. We retrieve all topologies associated with reachable leaves and return the ones whose frequencies are above or attained to $f$ and whose p-values are below or attained to $p$.

\subsection{Experiments}

\input{experiments}

\section{Conclusion}


%
% ---- Bibliography ----
%
\begin{thebibliography}{5}
%
\bibitem {clar:eke}
Clarke, F., Ekeland, I.:
Nonlinear oscillations and
boundary-value problems for Hamiltonian systems.
Arch. Rat. Mech. Anal. 78, 315--333 (1982)


\end{thebibliography}
\clearpage
\addtocmark[2]{Author Index} % additional numbered TOC entry
\renewcommand{\indexname}{Author Index}
\printindex
\clearpage
\addtocmark[2]{Subject Index} % additional numbered TOC entry
\markboth{Subject Index}{Subject Index}
\renewcommand{\indexname}{Subject Index}
\input{subjidx.ind}
\end{document}
