6.2. Layered approach and compositions
71
In the second part, each of the nodes of this 2n × 2n graph is replicated into
an in version and an out version, using the construction in Section 4.4. The newly
added blue edges, since they are directed, are also included in this next step. The new
configuration of node versions and added edges that result is shown in Figure 6.1(a).
We call this the nexus of versions of each original node.
The weights of the added edges are:
• weight(blue edge from green to red) = weight(green out)
• weight(blue edge from red to green) = weight(red out)
• weight(green dashed edge) = weight(total in) + weight(total out) = weight(green
in) + 2 × weight(green out) + weight(red out)
• weight(red dashed edge) = weight(total in) + weight(total out) = weight(red
in) + 2 × weight(red out) + weight(green out)
More formally, let A 1 , ..., A c be the c n × n adjacency matrices of each of the
typed subgraphs, and D 1 , ..., D c be the diagonal matrices of the outgoing degrees of
each. The embedding happens in three steps:
1. Bind together the versions of each node in the different colored layers to build
a cn × cn adjacency matrix as:
W =
A 1
· · ·
1
c−1 D 1 · · ·
1
c−1 D 1
. . .
. . .
. . .
. . .
. . .
1
c−1 D i · · ·
A i
· · ·
1
c−1 D i
. . .
. . .
. . .
. . .
. . .
1
c−1 D c · · ·
1
c−1 D c · · ·
A c
,
2. Split each node in every version into in and out copies as:
M =
0
W + D W
in + D W
out
W + D W
in + D W
out
0
,
where D W
in and D W
out are the diagonal in and out degree matrices of adjacency
matrix W .
3. Convert M to a Laplacian matrix and use an eigendecomposition to embed it.
As before, all of the work involves connecting node versions by the appropriate edges, and defining weights for the new edges that were not present in the
original graph. Once this is done, the resulting matrix is apparently larger, but does
not contain more than a linear number of extra non-zero entries. The (sparse) eigendecomposition required to do the actual embedding is straightforward.
71
In the second part, each of the nodes of this 2n × 2n graph is replicated into
an in version and an out version, using the construction in Section 4.4. The newly
added blue edges, since they are directed, are also included in this next step. The new
configuration of node versions and added edges that result is shown in Figure 6.1(a).
We call this the nexus of versions of each original node.
The weights of the added edges are:
• weight(blue edge from green to red) = weight(green out)
• weight(blue edge from red to green) = weight(red out)
• weight(green dashed edge) = weight(total in) + weight(total out) = weight(green
in) + 2 × weight(green out) + weight(red out)
• weight(red dashed edge) = weight(total in) + weight(total out) = weight(red
in) + 2 × weight(red out) + weight(green out)
More formally, let A 1 , ..., A c be the c n × n adjacency matrices of each of the
typed subgraphs, and D 1 , ..., D c be the diagonal matrices of the outgoing degrees of
each. The embedding happens in three steps:
1. Bind together the versions of each node in the different colored layers to build
a cn × cn adjacency matrix as:
W =
A 1
· · ·
1
c−1 D 1 · · ·
1
c−1 D 1
. . .
. . .
. . .
. . .
. . .
1
c−1 D i · · ·
A i
· · ·
1
c−1 D i
. . .
. . .
. . .
. . .
. . .
1
c−1 D c · · ·
1
c−1 D c · · ·
A c
,
2. Split each node in every version into in and out copies as:
M =
0
W + D W
in + D W
out
W + D W
in + D W
out
0
,
where D W
in and D W
out are the diagonal in and out degree matrices of adjacency
matrix W .
3. Convert M to a Laplacian matrix and use an eigendecomposition to embed it.
As before, all of the work involves connecting node versions by the appropriate edges, and defining weights for the new edges that were not present in the
original graph. Once this is done, the resulting matrix is apparently larger, but does
not contain more than a linear number of extra non-zero entries. The (sparse) eigendecomposition required to do the actual embedding is straightforward.