\subsection{Preliminaries}

We define the terms: \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}). 

For simplicity, our discussion will center on undirected graphs, although our method works with directed graphs as well. Given a graph $G$, we denote by $V_G$ its set of vertices, by $E_G$ its set of edges, by $L_G$ its alphabet of labels and by $l_G$ a function that assigns 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$).

A \emph{labeled topology} is an undirected (node-) labeled connected graph $G$. An \emph{unlabeled topology} is a labeled topology stripped 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$. So, a given motif may have zero, one, or more occurrences in a graph.

Checking whether two (labeled or unlabeled) topologies are isomorphic is and expensive task that requires finding an isomorphism between the topologies or proving that no isomorphism exists. In motif discovery this operation has to be performed frequently to map network subgraphs to the correct topology. To simplify this operation, we can map a graph to a \emph{canonical form}, i.e. a string that uniquely identify a topology and is invariant with respect to isomorphism. In other words two isomorphic graphs have the same canonical form, while two graphs that are not isomorphic have different canonical forms. Computing the canonical form of a graph may be expensive, but once it is computed the isomorphism check becomes trivial (equivalence between strings).   

An easy way to perform a canonical form for unlabeled topologies is to consider all possible adjacency matrices of a graph (by reordering nodes in all possible ways), linearize them into strings (by putting all rows of an adjacency matrix contiguously in a unique line) and considering the smallest string (with respect to a lexicographic order). This simple approach guarantees invariance with respect to isomorphism since two isomorphic graphs have the same adjacency matrix except for their rows/columns order. The approach can be generalized to labeled topologies by including the sequence of labels in the string. Since enumerating all possible node orders is impractical, more efficient methods have been defined. A widely used method is nauty~\cite{mckay1981practical}.

@book{mckay1981practical,
  title={Practical graph isomorphism},
  author={McKay, Brendan D and others},
  year={1981},
  publisher={Department of Computer Science, Vanderbilt University}
}

The canonical form of a graph is associated to a \emph{canonical order} of nodes, i.e. the order of nodes that produces it. Note that a canonical form may be associated with more than one canonical order since a graph may have several automorphisms.

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


\subsection{Problem definition}

We aim to support \emph{motif-based queries} in which the user specifies a set of constraints and the system returns all motifs that satisfy the constraints. In our framework, a user specifies a frequency threshold, a p-value threshold and a bag (multiset) of labels that the motifs must contain. An example 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 when a user is not satisfied with the answer, he or she can change the constraints and quickly get a new answer. We accept a slow (but still reasonable) off-line \emph{preprocessing} step in exchange for fast \emph{query processing}. 

Formally, 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. 

\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 number of nodes (size) $k$, whose number of occurrences in $\mathbb{G}$ is at least $f$ and whose p-value is no more than $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{gLabTrie}). Later, during the online \emph{query processing} phase, we probe the gLabTrie 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. Since our approach has been implemented on top of G-Trie we first give an overview of G-Trie and our subsequent description will refer to it. However, how approach is general in that it can be applied on other network centric algorithms for motif discovery.

\subsection{G-Trie method for unlabeled motif discovery}

The main data structure of a network-centric method for motif discovery is a key-value map (hash table or search tree) that associates each unlabeled topology (up to a certain size) to a counter. Unlabeled topologies may be represented by their canonical form, so that equivalence check is efficient. G-Trie~\cite{ribeiro2014g} uses a more efficient data structure (that we call the \emph{gTrie}) that generalizes tries to graphs. A gTrie organizes a set of unlabeled topologies in a multiway tree in such a way that subgraphs correspond to ancestors. An example of gTrie that stores all unlabeled topologies of size up to four nodes is given in Fig.~\ref{fig:gtrie}.

@article{ribeiro2014g,
  title={G-Tries: a data structure for storing and finding subgraphs},
  author={Ribeiro, Pedro and Silva, Fernando},
  journal={Data Mining and Knowledge Discovery},
  volume={28},
  number={2},
  pages={337--377},
  year={2014},
  publisher={Springer}
}


\begin{figure}[ht]
    \centering
    \includegraphics[width=.30\textwidth]{FIG/gtrie.png}
   \caption{Example of a gTrie with $K=4$. The data structure stores all unlabeled topologies with up to 4 nodes.}\label{fig:gtrie}
\end{figure}

Each node of the gTrie stores information associated to the corresponding topology, typically a counter (not shown in the figure). A gTrie can be seen as a map that associates topologies to counters (similar in principle to a hash table or a binary tree). However gTrie is specifically designed for motif discovery and hence it is much more efficient for this task.

Similarly to previous methods, GTrie counts the number of occurrences of all unlabeled topologies in the input network and compares them with the corresponding number of occurrences in random networks with similar properties. 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, size $K$, 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 $gTrie$
	\STATE call $census(network,gTrie)$
	\STATE initialize $map\_count$
\FOR{$i=0\ldots r$} 
	\STATE $rand\_net = randomize(network)$
	\STATE initialize $gTrie\_rand$
	\STATE call $census(rand\_net, gTrie\_rand)$
	\FOR{all $t \in topologies(gTrie\_rand)$}
		\IF {$gTrie\_rand[t]\geq gTrie[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 {$gTrie[t] \geq f$ and $pval\leq p$} 
	\STATE output $t$, $gTrie[t]$, $pval$
	\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

First a gTrie with all unlabeled topologies up to size $K$ is built. Then the core procedure, $census()$, which takes as input a network and fills the gTrie\footnote{In general the overall algorithm can work with any data structure that associates keys to values (e.g. hash tables) in place of gTrie. Keys are canonical forms of topologies, while values are counters.} with the correct counting, is called. This procedure enumerates all subgraphs of the network one by one and increases the counter of the corresponding topology. Then, a map of counters ($map\_count$) is initialized. This map is a hash table that associates topologies (more precisely canonical forms of topologies) to counters and is used to store the number of random networks in which a given topology occurs more than in the input network. Next, a number of randomizations of the input network are computed and $census()$ is executed on each of them. For every topology found, if its number of occurrence is greater than the one in the input network, its counter is increased. Function $topologies(gTrie)$ returns all topologies stored in $gTrie$ while $gTrie[t]$ refers to the counter associated with topology $t$ in $gTrie$. At the end, frequencies and p-values are computed and all topologies that satisfy the input constraints are returned. In the next paragraphs we give more details on the core procedure, $census()$. Further details on the other parts can be found in~\cite{ribeiro2014g}.  

The algorithm for graph census (procedure $census()$) is detailed in Alg.~\ref{alg:census}.

\begin{algorithm}
\caption{Census algorithm for unlabeled motif discovery}\label{alg:census}
\begin{algorithmic}
	\REQUIRE network, gTrie
	\COMMENT {returns the gTrie filled with the number of occurrences of each topology.}
	\STATE $Match(gTrie.root, \emptyset)$ 
	\RETURN $gTrie$
	\STATE
	\STATE \textbf{Procedure} $Match(node,V_{used})$
	\IF {$V_{used} = \emptyset$} 
		\STATE $V_{cand} \leftarrow V(network)$
	\ELSE
		\STATE $V_{cand} \leftarrow \{ v \in N( V_{used} ) : v \mbox{ satisfy symmetry breaking conditions}\}$
	\ENDIF
	\STATE $V \leftarrow \emptyset$
	\FOR {all $v \in V_{cand}$}
		\IF {$v$ is connected with $V_{used}$ as defined in $node$} 
			\STATE $V \leftarrow V \cup \{v\}$
		\ENDIF
	\ENDFOR
	\FOR {all $v \in V$}
		\IF {$isLeaf(node)$ }
			\STATE $node.counter += 1$
		\ENDIF
		\FOR {all children $c$ of $node$}
			\STATE $Match(c, V_{used} \cup \{ v \})$
		\ENDFOR
	\ENDFOR
	%\ENDPROCEDURE
	\STATE \textbf{End Procedure}
\end{algorithmic}
\end{algorithm}

The algorithm is based on the recursive procedure $Match$ that matches paths of the gTrie with all possible subgraph of the input network. At the beginning, the procedure $Match$ is called on the root of the gTrie and with an empty subgraph ($V_{used}=\emptyset$). The procedure picks a vertex at a time and starts to grow a subgraph from that vertex. Every time a new children of a gTrie node is explored, all vertices associable with that node are considered and possibly added to the current subgraph ($V_{used}$). When a leaf node is considered, the node counter is increased. This means that a new subgraph isomorphic to the topology associated to that node was found.

%calls 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. Without symmetry breaking conditions, the $Match$ procedure would find the same subgraph multiple times (there are many ways of producing the same subgraph). To avoid this, the census algorithm considers a carefully designed set of symmetry breaking conditions that guarantee that a subgraph is enumerated exactly once. Details on how symmetry breaking conditions are computed are given in~\cite{ribeiro2014g}. 

\subsection{gLabTrie data structure for labeled motif discovery}

A natural extension for handling labeled networks would consist in considering labels in the gTrie nodes. A node would represent a labeled topology as opposed to unlabeled topologies. However, this approach would cause an explosion of the number of gTrie nodes as the number of labels grows. Each node has to maintain both connectivity and label information and hence the same connectivity information would be stored multiple times.

To optimize memory, 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 choosing, among all possible canonical orders of unlabeled topologies, the one that corresponds to the lexicographically minimum sequence of labels. We refer to a canonical order that satisfy this condition as a \emph{lexically ordered canonical 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 that nodes with smaller labels are assigned with smaller node ids (i.e. $v \leq u$ if $l_\mathbb{G}(v) \leq l_\mathbb{G}(u)$). We call a graph that satisfies this condition a \emph{lexically numbered graph}.

The procedure described above solves the problem in Fig.~\ref{fig:example}. 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 always gives 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 labeled canonical forms (topology + label sequence) coincide;
	\item given two labeled topologies, if their corresponding labeled 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. In fact, the labeled canonical form is computed by combining the unlabeled canonical form with the sequence of labels. 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 labeled topologies and $S_1$, $S_2$ be the sequence of labels given by their lexically ordered canonical order. If $G_1$ and $G_2$ are isomorphic then $S_1=S_2$. 
\end{lemma}

Proof: by contradiction. Suppose $S_1 \neq S_2$. Without lost of generality 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 is 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 labels smaller than $S_2$. This contradicts the hypothesis that $G_2$ is a lexically ordered canonical order. QED

We modify the G-Trie algorithm to support labels. The main change concerns the information associated with gTrie nodes. Specifically, we substitute the counters of gTrie nodes with hash tables 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 hash table. 

In summary, we apply the following changes:

\begin{enumerate}
	\item we introduce a first step that reassigns ids to nodes of the input network so that nodes with smaller labels are assigned with smaller node ids;
	\item we substitute the counters of gTrie nodes with hash tables that associate label sequences to counters; 
	\item we change the census procedure to increase the counters of labeled topology as opposed as unlabeled ones. 
\end{enumerate}

Since the major changes are in the census algorithm we only report the census procedure for labeled motif discovery (the overall algorithm is quite similar with the addition of the initial node ids assignment step). The census algorithm is shown in Alg.~\ref{alg:census_labeled}.

\begin{algorithm}
\caption{Census algorithm for unlabeled motif discovery}\label{alg:census_labeled}
\begin{algorithmic}
	\REQUIRE labeled network, gTrie
	\COMMENT {returns the gTrie filled with hash tables with the number of occurrences of each labeled topology.}
	\STATE $Match(gTrie.root, \emptyset)$ 
	\RETURN $gTrie$
	\STATE
	\STATE \textbf{Procedure} $Match(node,V_{used})$
	\IF {$V_{used} = \emptyset$} 
		\STATE $V_{cand} \leftarrow V(network)$
	\ELSE
		\STATE $V_{cand} \leftarrow \{ v \in N( V_{used} ) : v \mbox{ satisfy symmetry breaking conditions}\}$
	\ENDIF
	\STATE $V \leftarrow \emptyset$
	\FOR {all $v \in V_{cand}$}
		\IF {$v$ is connected with $V_{used}$ as defined in $node$} 
			\STATE $V \leftarrow V \cup \{v\}$
		\ENDIF
	\ENDFOR
	\FOR {all $v \in V$}
		\IF {$isLeaf(node)$ }
		  \STATE $label_seq \leftarrow $ labels of $V_{used}$ in lexically ordered canonical order
			\STATE $node.hash_table[label_seq] += 1$ \COMMENT{now we have a hash table as opposed as a counter}
		\ENDIF
		\FOR {all children $c$ of $node$}
			\STATE $Match(c, V_{used} \cup \{ v \})$
		\ENDFOR
	\ENDFOR
	%\ENDPROCEDURE
	\STATE \textbf{End Procedure}
\end{algorithmic}
\end{algorithm}


\subsection{An index for querying motifs}

During the preprocessing phase we find all motifs up to size $K$ (a pre-defined parameter)in the input network as described previously. We not set neither a frequency threshold nor a p-value threshold, so all labeled topologies occurring in the input network are considered. We limit the search to motifs having size $K$ or less. For 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{gLabtrie}\emph{-- Dennis, the index data structure is different from the gLabTrie. We should find another name or just call it The Index, as I did}, that facilitates later retrieval. An example of a gLabTrie 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 gLabTrie. Our data structure for processing motif-based queries}\label{fig:index}
\end{figure}

The gLabTrie consists of a DAG, which embodies the superset relation between sets, and a collection of lists of topologies contained in the 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 the label constraints associated with the leaf, with the topologies' frequencies and p-values. 

The described gLabTrie enables fast lookup 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, i.e. it contains all possible nodes up to depth 3, 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 gLabTrie}

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 gLabTrie}\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 gLabTrie 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 gLabTrie}\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 gLabTrie described above, and a query $Q=(C,k,f,p)$ with $k=K$, query processing is quite straightforward. To perform a query $Q=(C,k,f,p)$ with $k=K$, first look up the node $n$ of the DAG associated with the set of labels in $C$, then explore all nodes of the DAG reachable from $n$. Finally, retrieve all topologies associated with reachable leaves and return the ones whose frequencies are greater than or equal to $f$ and whose p-values are less than or equal to $p$.

Note that with small changes the gLabTrie can support queries of size $k\leq K$. Indeed internal nodes at depth $k$ can be associated to labeled topologies of size $k$ (for all $k=1\ldots K-1$). Answering queries with $k\geq K$ is not trivial and is the subject of our current work.