\begin{abstract}
Motif discovery is the problem of finding subgraphs of a network that appear surprisingly often.  
Each such subgraph may indicate a small scale interaction feature in 
applications ranging from
a genomic interaction network, a  
significant relationship
involving rock musicians, or any other application that can be
represented as a network.
We look at the problem of constrained search for motifs based on labels
(e.g. gene ontology, musician type to continue our example from above).
This chapter presents a brief review of the state of the art in 
motif finding 
and then extends the gTrie data structure from 
Ribeiro et al \cite{ribeiro2014gtrie} to support labels. 
Experiments validate the usefulness of our structure for small subgraphs,
showing that we recoup the cost of the index after only a handful
of queries.
\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. 
Motifs can also be useful in engineering disciplines
such as synthetic biology.
Kurata et al \cite{kurata2014biofnet} 
use the frequent motifs found in biological networks as a 
library for synthetic biology. 
In fact Kurata et al pointed out that there are often motifs that behave 
as a single node in a larger network motif, just as an AND gate
in an electronic circuit built out of transistors and resistors
acts as a single node in a logic diagram.
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. 
A constrained labeled motif query is to find a statistically 
significant motif satisfying some constraint on the labels. 

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 labeled topological
structure  of interest is found in those random graphs. 
If infrequently, then the labeled topological
structure is significant in G and constitutes a motif.

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. 
%AR: the counting are ambiguous, it better to remove it. 
%For a completely connected graph 
%$G=(V_G,E_G,L_G,l_G)$ (with $V_G$ vertices, $E_G$ edges, $L_G$ alphabet of labels and $l_G$ labels assignment), there are $|E_G|$ subgraphs of size 2 (havingtwo nodes), $|E_G| \times |E_G|$ subgraphs of size 3, and in general $|E_G|^k$  of size k.
For sparser graphs, the growth may be less dramatic, but still rapid.

For that reason, we use data structures to make this fast.
Our work builds directly on the gTrie data structure
developed by Ribeiro \cite{ribeiro2012querying} which is why we call our structure
gLabTrie.

This chapter begins with a discussion of the data structure 
and algorithm  we will use.
We then follow with  a discussion of how to find rare structures.
Finally, we give an experimental evaluation of our structure
and algorithms.

