0
$\begingroup$

I need an intuition how this is possible - Imagine I have a DAG(directed acyclic graph), so a graph without cycles and only directed edges;

Now for every DAG with $d$ nodes there is (at least) one topological order $\pi:1,...,d$ such that for every $j$ being an ancestor of $i$ it also holds that $j<i$, so that $j$ is before $i$ in the topological order; (follows directly from the fact that edges are directed and there are no loops)

Now I have a model defined on the graph, namely $X_1,...,X_d$ is such that:

$$X_i=\sum\limits_{j \in \text{an}(i)}c_{ji}X_j+\varepsilon_i,$$

where $\varepsilon_i$ is some positive and continous innovation, $c_{ji}>0$ and an$(i)$ are the ancestors of node $i$ - now given some data sample $X^1,...,X^n \in \mathbb R^d$ I want to estimate the topological order;

Since $ X_i/X_j \geq c_{ji}$ if $j$ is an ancestor of $i$ and $0 \leq X_i/X_j \leq 1/c_{ij}$ if $i$ is an ancestor of $j$ it might be resasonable to define a matrix $A$ with entries $a_{ji}=\bigwedge_{k=1}^nX_i/X_j$ and try to find the topological order $\pi$ such that:

$$\max_{\pi \in \Pi}\sum\limits_{\pi(j)<\pi(i)}a_{ji}$$

Also we could based on the same idea minimize the value which is NOT in our topological sort, namely:

$$\min\max_{\pi(j)>\pi(i)}a_{ji}$$

Both have the same approach but the sum should be more robust - however when I test it, the sum leads to worse results which I dont really understand;

Anyone an idea?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.