
\section{Alternative Methods of Calculating Statistical Significance}

One might ask why we care about statistical significance (reflected in the p-value calculation in the previous section). Studies have shown that in many biological networks, small sub-networks of real networks that are much more frequent than random networks of the same size \cite{alon2007network,milo2002network} often act as functionally important modules.
For example, in \cite{alon2007network,milo2002network} the authors identified motifs representing positive and negative autoregulation (subnetworks of one node and one edge), coherent and incoherent feed forward loops (subnetworks of 3 nodes and 3 edges),  single-input modules (one node connected to few or many other nodes) and dense overlapping regulons (many nodes connected to few or many other nodes). One function of a coherent feed forward loop formed by a target $Z$ and two transcription factors $X$ and $Y$ is the logic operation AND of a circuit: $Z$ is activated by both $X$ and $Y$, however $Y$ is also regulated by $X$. Motif functionality has also been investigated with respect to evolution \cite{kashtan2005spontaneous,sole2002model} showing that motifs with the same topologies can have important functionality in different conditions. 

That explains our interest in finding statistically over-represented substructures. This section discusses approaches to establishing statistical significance.

Formally, given a graph $ G = (V, E) $ (directed or undirected) with $ n $ vertices  whose ids are uniquely  labeled with integers from 1  to $n$. A connected subgraph induced by a set of vertices of cardinality $k$ (a {\em topology} for short) is called a motif when it occurs statistically significantly more often than the same subgraph in randomized networks derived from the original network \cite{milo2004uniform}.


The random generation  method to find motifs given a real network consists of following steps:
(i) generate a large set of random networks that share the characteristics of the real network; (ii) find candidate topologies, consisting of subgraphs  in the real network; (iii) count the occurrences of these topologies (iv) assess the significance of each topology by computing its number of occurrences in each of the random networks. 

The first step creates networks that have the same number of nodes and edges of the real network. Moreover, each node in the generated network maintains its original number of edges leaving and entering the node \cite{newman2001random}.  
Next, by proceeding in an exhaustive manner, an algorithm can define all possible topologies of subgraphs with $n$ nodes and count all the occurrences of such subgraphs in the real and in the random networks \cite{milo2004uniform}. 

The random generation method consists of two expensive steps: the generation of a large number of networks and the application of subgraph isomorphism algorithms to compute the number of occurrences.
Over the last decades, researchers have worked to reduce the expense of both steps. We list the main results in the following sections. For the sake of brevity, we point to the main alternative approaches, but give few details. 

\subsection{Quasi-analytical methods to assess the statistical significance of a topology }

The random generation method described above evaluates the significance of
the topology through the computation of a z-score using
a Gaussian assumption or a p-value using a resampling approach \cite{milo2002network,milo2004uniform,prill2005dynamic,shenorr2002network}.
The Gaussian assumption may not apply to a particular application, but
a reliable p-value requires a large number of random graphs 
whose analysis turns out to be computational expensive (by far
more expensive than analyzing the target network alone).
Recently, researchers have investigated the possibility of analyzing the distribution of the topologies, both non-induced and induced, from an analytical point of view that would avoid the need for random generation.

Approximation methods, based on the Erdos-Renyi model, have studied the asymptotic normality of the distribution of the count of the topologies \cite{wernicke2006efficient}.  
Unfortunately, the Erdos-Renyi random model is a poor approximation to some networks of interest, such as biological networks \cite{barabasi1999emergence}.
Alternative reference models include the fixed degree Distribution (FDD) \cite{newman2001random} that models the random generation method of swapping random edges. The swapping approach guarantees that a given node has the same valence in the random graphs as in the original one.  There is also a variant of the FDD called Expected Degree Distribution (EDD) \cite{picard2008assessing} and the Erdos-Renyi Mixture for Graphs ERMG \cite{picard2008assessing}.

The EDD model generates random graphs whose degrees follow the distribution of the original graph, but particular nodes may obtain different valences. Conditional to the distribution of node degrees, the probability of edges is modeled as independent and exists with a probability proportional to the product of the degree distributions of the
involved nodes. 
In the ERMG model, the nodes are spread among $Q$ hidden classes with respective proportions \\ $\alpha_1,\cdots, \alpha_Q$. 
The edges are  independent conditional on the class of the nodes. The connection probability depends on the classes of both nodes.

It has been also shown that the use of the Compound-Poisson distribution \cite{adelson1966compound} in the Erdos-Renyi random model allows the accurate approximation of the number of over-represented topologies  \cite{picard2008assessing}.
In \cite{picard2008assessing}  the authors propose a model for the exact calculation of the mean and variance under any model of exchangeable random graphs (exchangeability means that the probability of occurrence of a topology does not dependent on its position in the graph, i.e., on the topological structure of the neighborhood of the topology). 
Furthermore, the authors have shown that the Polya-Aeppli distribution (also known as the Poisson Geometric distribution which is a special case of the Poisson-Compound distribution) is a good model for the distribution of the count of the topologies (both induced and non-induced) and leads to a more accurate p-value than a Gaussian model for the graphs of many applications.
The reason is that the Geometric-Poisson distribution is particularly suitable for describing the number of events that occur in clusters, where a Poisson distribution describes the number of clusters and the counts of events within a cluster follows a geometric distribution. Here, this fits the case when distinct topologies can share nodes and edges (i.e. clumps) \cite{picard2008assessing}.
In fact, the authors show that when the number of clumps has a Poisson distribution with mean $\lambda$ and the sizes of the clumps are independent of each other and have a Geometric distribution $G(1-a)$, the number of observed events $X$ (topologies) has a distribution $ P(\lambda, a) $ and leads to an estimate of the number of occurrences of a given topology. 

So far, our discussion has concerned label-free (also known as color-free)
networks.
Schbath et al. \cite{schbath2009assessing} propose an analytical model for the computation of p-values for colored patterns. 
A colored pattern is a topology having a given multiset of colors (vertex labels). For example, a star of size 5 having 4 Bs and 1 C.
An occurrence of the pattern is defined as a connected subgraph whose labels have a match with the multiset. Schbath et al would make no distinction between a star having the C in the center or one having the C on the outside. That subtle difference makes our job more difficult, but the starting point for our current research is their excellent work.i

Schabat et al. define analytical formulas for the mean and variance
of the number of colored topologies by using the  Erdos-Renyi model.
Thanks to this, they were able to derive a reliable z-score for each topology.
The authors then model the distribution of the count of coloured topologies under the Erdos-Renyi model. 
%Also in this case the authors conclude that the Polya-Aeppli distribution has a very good approximation of the count and it fits better than the Gaussian distribution.


\subsection{Random Generation Methods}

Whereas the previous subsection discussed analytical method, no published 
analytical
method can discover p-values under our model of query (though, as mentioned, 
we ourselves are making progress towards that goal).
So we turn to random generation methods.
Improving random generation methods entails intelligent searching through graphs to enumerate topologies. The basic idea is to start from single nodes and expand them with their neighbourhoods in a tree like fashion, checking at each step that each subgraph in the tree appears only once and that it does not violate the color constraints of the query. This procedure can be further improved by sampling the network \cite{alon2007network} or the neighbourhoods in the expanding phases \cite{wernicke2006efficient}. Alternatively, Grochow and Kellis \cite{grochow2007network} used subgraph enumeration and symmetry breaking to avoid the search for automorphisms of the subgraphs occurrences. 
We now give some examples of the state-of-the-art algorithms upon which
we build our structure.

The ESU algorithm \cite{wernicke2006efficient} enumerates all subgraphs of size $k$ 
by starting from a root vertex $v$ of the graph and computing the occurrences of the topology by extending it node by node. 
The algorithm uses the concept of exclusive neighborhood which is defined as follows. For a subset $ V ^ {'} \subseteq V $, its open neighborhood $ N (V ^ {'}) $ is the set of vertices in $ V \setminus V ^ {'} $ which are adjacent to at least one vertex in $ V ^ {'} $. For each node $ v \in V \setminus V ^ {'} $, the exclusive neighborhood with respect to  $ V ^ {'} $ and denoted by $ N_ {excl} (v, V ^ {'}) $, consists of all vertices that neighbours of  $ v $ but are not in $ V \cup N (V ^ {'}) $.

The key idea of the algorithm is to add into the extension set  of $v$, called $ V_ {Extension} $, only those vertexes  satisfying the two following properties:
(i) their vertex ids must be greater than $v$; (ii) must be neighbors only to the newly  added $w $ and not already in $ V_ {subgraph} $ (i.e. they must be in $N(w, V_ {subgraph}) $).


Its randomized variant, Rand-ESU, introduces an option that performs a uniform sampling in the graph, thus avoiding the need to explore it all. The algorithm is essentially the same as the original one with the exception that the recursion is carried out with a certain probability that decreases with the depth of the enumeration. In practice, the probability is high in the first steps of the recursion and then decreases
as the size of the subgraphs to be explored increases.

The sampling in RAND-ESU is unbiased and is quite
simple to implement. On the other hand, RAND-ESU gives only
an estimate of the number of occurrences.

%Segue figura esempio 
\begin{center}
\begin{figure}[h!]
\includegraphics[scale=0.4]{esu}
\caption{The ESU tree for generating all subgraphs of $k$=3 nodes}\label{esu}
\end{figure}
\end{center}

%Descrizione di Gtrie + 
Graph mining algorithms \cite{yan2002gspan} find frequent subgraphs in a database of graphs or in a single large graph.
A subgraph is frequent if its support (occurrence frequency) in a given  dataset (or in a graph) is no less than a {\em minimum support} threshold.
Computing the statistical significance of such topologies is done by simulation,
as described above.

In this chapter, we consider the problem of searching for topologies of labelled graphs. However, there are several possible definitions of labeled topology.

In \cite{schbath2009assessing}, the authors define a potential $k$-colored motif to be any connected subgraph of $k$ nodes containing a specified multiset of colors (defined on the nodes). The motif is "potential" because its statistical significance may not meet a threshold. In this case, different topologies with the same labels define the same motif. Adami et al \cite{adami2011information} consider the definition of colored motif as above, and use a measure based on entropy to determine the significance. In \cite{wernicke2006efficient} and \cite{ribeiro2014discovering}, the authors use the definition of motifs colored on both nodes and edges having a specific topology. \cite{wernicke2006efficient} is based on the ESU algorithm, whereas Ribeiro et al \cite{ribeiro2014discovering} introduce a version of GTrie capable to find colored motifs. 


%For this last definition of colored motifs no analytical way exists to compute the
%p-value therefore the only feasible way is based on simulations.
 

%In \cite {}  introduce a version of GTrie capable  to find  colored motifs on both nodes and edges having a specific topology.

%{\em Alfredo/Rosalba: Ok, but now we have to say how we define signficance under our three definitions of significance and how we calculate it

%Two more kind of colored motifs can be defined. The first one takes into account the topology of nodes and the connections among the multiset of colors do not matter.

%The last type has constraints on both  topology and the connections among colors.~\cite{ribeiroColored}.  For both of this two last definitions no analytical way exists to compute the
%p-value therefore the only feasible way is based on simulations.

%}
%Dennis
In this chapter, we adopt the motif definition introduced in \cite{ribeiro2014discovering}. 
\begin{definition}
Let $G$ be a labeled graph. Let $m(V_m, E_m, LV_m, LE_m)$ be a subgraph of $G$ with $V_m$ nodes and $E_m$ edges, where $LV_m$ and $LE_m$ are two sets of colors representing the labels of nodes and edges respectively. Let $c$ be the number of isomorphic occurrences of $m$ in $G$, and let $\alpha$ be a critical value.
Let $G_R$ be a random variant of $G$ obtained by applying the edge shuffling method based on the Fixed Degree Distribution, and let $c_R$ be the number of occurrences of $m$ in the random variant $G_R$.
We say that $m$ is a motif of $G$ if, by applying a permutation test using $k$ random variant of $G$, $G_{R,i}$ (k = 500 usually),  $\frac{\#(c_{R,i} > c)}{k} < \alpha$, where $\#(c_{R,i} > c)$ is the number of times the number of occurrences of $m$ in $G_{R,i}$ is greater than in $G$.
\end{definition}


Because there is no analytical way to compute the significance of such a network motif yet,
we will use the simulation on the random generated networks to establish the significance of colored network topologies.
Algorithm ~\ref{alg:ptest} shows the implementation of a permutation test.


\begin{algorithm}
\caption{Randomized Generation Test to Discover p-values}\label{alg:ptest}
\begin{algorithmic}
	\REQUIRE network $G$, candidate topologies $m_1,m_2,\cdots, m_l$,
	 $c_i$ number of occurrences  of \\ $m_i$ in $G$, number of iterations $k$, critical value $\alpha$
	\COMMENT {returns the p-value of topology $m_j$}
	\STATE $s_j := 0$
	 \FOR{$j = 1,\ldots l$}
\FOR{$i=0\ldots k$} 
	\STATE $G_{R,i} = randomize(G)$
	\STATE $c_{R,j} :=$ number of occurrences of $m_j$ in $G_{R,i}$;
	\FOR{$j=0\ldots l$}
		\IF {$c_{R,j}\geq c_j$} 
		\STATE $s_j++$
		\ENDIF
	\ENDFOR
\ENDFOR
\ENDFOR
\FOR{$j=0\ldots l$}
	\STATE {output p-value of topology $m_j$ is $s_{j}/k$}
\ENDFOR

\end{algorithmic}
\end{algorithm}

In our current efforts, we extend the analytical approach of \cite{schbath2009assessing,picard2008assessing} to compute the significance of topologies given a multiset of colors.

