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:


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?


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.