38
Chapter 4. Modelling relationships of different types
Figure 4.4: Embedding of Florentine families with typed but undirected edges; there
are now two versions of each node. Financial layer: solid lines; personal layer:
dashed lines; vertical edges: dotted lines. Little can be seen of the central structure
in this view, but zoomed-in versions are shown in subsequent figures.
type graph has its own underlying structure, but is influenced by others.
Most attempts to represent graphs with different edge types are based on the
first assumption, and two common strategies can be applied. One strategy is to combine all the subgraphs of each edge type into a consistent whole, and then do further
analysis based on the new graph. Directly adding all subgraphs together is the easiest
way. However, when the density of each edge type is quite different, the final embedding of the whole graph tends to be based mostly on the structure of the edge type
with the greatest density. Thus, some kind of normalization is usually the first step.
For example, Zhou and Burges [119] combined random walk normalized Laplacian
matrices of different views with user-determined weights for the views. Xia et al.
[107] used iterative techniques to optimize the weights of different views, and then
combined symmetric normalized Laplacian matrices into a whole. Cheng and Zhao
[16] combined the distances in each separate Laplacian embedding to create a completely new similarity matrix and then repeated the spectral clustering of this matrix
to produce the final embedding. Muthukrishnan et al. [66] fused all subgraphs together using a regularization framework over edges in multiple graphs, and then
applied the Laplacian approach. Dong et al. [28] and Tao et al. [97] used a similar
way to merge the Laplacian matrices of each subgraph into a general Laplacian matrix for embedding. The problem with this strategy is deciding how the individual
representations should be combined, and there is usually not enough information to
Chapter 4. Modelling relationships of different types
Figure 4.4: Embedding of Florentine families with typed but undirected edges; there
are now two versions of each node. Financial layer: solid lines; personal layer:
dashed lines; vertical edges: dotted lines. Little can be seen of the central structure
in this view, but zoomed-in versions are shown in subsequent figures.
type graph has its own underlying structure, but is influenced by others.
Most attempts to represent graphs with different edge types are based on the
first assumption, and two common strategies can be applied. One strategy is to combine all the subgraphs of each edge type into a consistent whole, and then do further
analysis based on the new graph. Directly adding all subgraphs together is the easiest
way. However, when the density of each edge type is quite different, the final embedding of the whole graph tends to be based mostly on the structure of the edge type
with the greatest density. Thus, some kind of normalization is usually the first step.
For example, Zhou and Burges [119] combined random walk normalized Laplacian
matrices of different views with user-determined weights for the views. Xia et al.
[107] used iterative techniques to optimize the weights of different views, and then
combined symmetric normalized Laplacian matrices into a whole. Cheng and Zhao
[16] combined the distances in each separate Laplacian embedding to create a completely new similarity matrix and then repeated the spectral clustering of this matrix
to produce the final embedding. Muthukrishnan et al. [66] fused all subgraphs together using a regularization framework over edges in multiple graphs, and then
applied the Laplacian approach. Dong et al. [28] and Tao et al. [97] used a similar
way to merge the Laplacian matrices of each subgraph into a general Laplacian matrix for embedding. The problem with this strategy is deciding how the individual
representations should be combined, and there is usually not enough information to