What is the number of free parameters for a directed acyclic graph? I am trying to use Maximum Likelihood Estimation to learn the structure of a DAG, G.
How is the number of free parameters of G calculated to compare the complexity of different graphical models?
Is it based on one of the following, or something else?


*

*Number of edges in the graph

*Maximum number of possible edges in the graph

*Maximum number of parents (children)

 A: The answer depends on your likelihood for the data $X$
1) Joint Gaussian
You can fit the model by sequentially fitting the conditional distribution of each node $v$ given its parents $\mathrm{pa}(v)$, in this case:
$X_v | X_{\mathrm{pa}(v)} \sim N\big(\mu_v + \beta_v^\top [X_{\mathrm{pa}(v)} - \mu_{\mathrm{pa}(v)}], \sigma_v^2 \big)$
Then for each node you need 1 parameter $\mu_v$ for the mean, 1 parameter $\sigma_v^2$ for the conditional variance and a vector $\beta_v$ of length $|\mathrm{pa}(v)|$.
So the total number of parameters needed for a graph $G=(V,E)$ is $2|V| + |E|$.
2) Discrete
Suppose the variable $X_v$ for each node $v$ is discrete with $n_v$ possible outcomes. Then for each possible outcome in the parent space, you require $n_v-1$ parameters. So for each node, you will need:
$(n_v-1) \prod_{u \in \mathrm{pa}(v)} n_u$
parameters. If each node has 2 possible outcomes, you will need:
$\sum_{v} 2^{|\mathrm{pa}(v)|}$
total parameters, unless you make some simplifying assumptions, such as proportional-odds (i.e. logistic regression).
