<p>If you create an adjacency matrix $A$ between $O$ and $T$ where:</p>

<ul>
<li>the rows correspond to objects in $O$</li>
<li>the column correspond to objects in $T$</li>
<li>the entry $A_{i,j} = 1$ if there is a link between $i \in O$ and $j \in T$, or $A_{i,j} = 0$ otherwise.</li>
</ul>

<p>Then, finding the <strong>least number of</strong> intermediate 'hidden' nodes correspond to computing <a href="http://en.wikipedia.org/wiki/Nonnegative_rank_(linear_algebra)" rel="nofollow">Nonnegative rank factorization</a> of the matrix $A$.</p>

<p>Suppose $A=BC$ is the nonnegative rank factorization of $A$, then create as many hidden nodes as the column size of matrix $B$ (or equally, the row size of matrix $C$). Let's call this hidden nodes set $H$. Then, the matrix $B$ gives the adjacency matrix from set $O$ to $H$ and the matrix $C$ gives the adjacency matrix from set $H$ to $T$.</p>

CC BY-SA 3.0
2014-09-17T12:55:59.430Z
2014-09-17T13:01:23.843Z
2014-09-17T13:01:23.843Z
Apiwat Chantawibul
<p>I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements of set of $T$ to elements of set $O$. For example all the links are of the form</p>

<p>$(a,b)$ where $a$ belongs to $T$ and $b$ belongs to $O$. The set $O$ can be huge compared to $T$ and consequently the graph can be huge. But let me give you an example</p>

<p>Suppose $O=\{o_1,o_2,o_3\}$ and $T=\{t_1,t_2,t_3\}$</p>

<p>and I have the full set of allowed links</p>

<p>If I insert in the graph a hidden node $h$ then I can create a graph with links
$(o_1,h), (o_2,h), (o_3,h)$ and $(h,t_1),(h,t_2),(h,t_3)$</p>

<p>Then the tagging is preserved if we define that :</p>

<p>"object $o$ has tag $t$ if there is a path from $o$ to $t$".</p>

<p>The definition as you see is invariant with the hidden node.</p>

<p>Moreover while previously I had 9 links, now I have 6 while the number of nodes is increased by 1.</p>

<p>For a fully linked case with $N$ objects and $M$ tags the gain becomes</p>

<p>$(NM)/(N+M)$ which as $N$ increases the gain tends to $M$.</p>

<p>Do you know for such research? What category of problems this belongs? I am also very interested in the online case.</p>

<p>Thank you in advance.</p>

<graph-theory><ds.data-structures>
tagging and graph “compression”
Vasileios Anagnostopoulos
# tagging and graph “compression”

(Asked by: username_0 on 2014-09-17)

I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements of set of $T$ to elements of set $O$. For example all the links are of the form

$(a,b)$ where $a$ belongs to $T$ and $b$ belongs to $O$. The set $O$ can be huge compared to $T$ and consequently the graph can be huge. But let me give you an example

Suppose $O=\{o\_1,o\_2,o\_3\}$ and $T=\{t\_1,t\_2,t\_3\}$

and I have the full set of allowed links

If I insert in the graph a hidden node $h$ then I can create a graph with links
$(o\_1,h), (o\_2,h), (o\_3,h)$ and $(h,t\_1),(h,t\_2),(h,t\_3)$

Then the tagging is preserved if we define that :

"object $o$ has tag $t$ if there is a path from $o$ to $t$".

The definition as you see is invariant with the hidden node.

Moreover while previously I had 9 links, now I have 6 while the number of nodes is increased by 1.

For a fully linked case with $N$ objects and $M$ tags the gain becomes

$(NM)/(N+M)$ which as $N$ increases the gain tends to $M$.

Do you know for such research? What category of problems this belongs? I am also very interested in the online case.

Thank you in advance.

**Tags:** graph-theory, ds.data-structures


---

## 1 answers

### Answer by username_1 on 2014-09-17. Score: 2 | Accepted answer

If you create an adjacency matrix $A$ between $O$ and $T$ where:

* the rows correspond to objects in $O$
* the column correspond to objects in $T$
* the entry $A\_{i,j} = 1$ if there is a link between $i \in O$ and $j \in T$, or $A\_{i,j} = 0$ otherwise.

Then, finding the **least number of** intermediate 'hidden' nodes correspond to computing [Nonnegative rank factorization](http://en.wikipedia.org/wiki/Nonnegative_rank_(linear_algebra)) of the matrix $A$.

Suppose $A=BC$ is the nonnegative rank factorization of $A$, then create as many hidden nodes as the column size of matrix $B$ (or equally, the row size of matrix $C$). Let's call this hidden nodes set $H$. Then, the matrix $B$ gives the adjacency matrix from set $O$ to $H$ and the matrix $C$ gives the adjacency matrix from set $H$ to $T$.


---

