9.1. Approach
123
5. Allocate each unlabelled node to a class based on the sign of the corresponding
entry in the principal eigenvector of the eigendecomposition corresponding to
the signed graph Laplacian. It would be plausible to use a subset of k of the
eigenvectors, and cluster in k-dimensional space, using any standard clustering
algorithm, but this turns out not to be stable.
When there are more than two classes, a one-versus-the-rest strategy is used, in the
style of support vector machines. The effect of this strategy is shown in Figure 9.1(a).
(a) Adding edges between station nodes
(b) Adding edges between all labelled nodes
Figure 9.1: Two possible ways to add negative edges. The solid edges are positive
and the dashed edges are negative.
It would also be possible to add positive nodes between labelled nodes with
the same label, and negative edges between nodes with different labels. The result
is shown in Figure 9.1(b). With this strategy, the number of added edges increases
quadratically in the number of labelled nodes, while our strategy requires extra edges
only linear in the number of labelled nodes. As the figures show, even for this small
graph the difference is non-trivial.
A technical problem remains which requires an extension to the previous signed
spectral embedding technique. Node degree matters and the labelled nodes have all
had their degree increased by one by the addition of a new edge to the class representative node. The total degree of the graph has also increased. To avoid the distortions
that this might create, we modify the total degree term in L sns so that the total degree of original nodes are computed based on the original graph edges, and the total
degree of stations are computed based on the total degree in the new graph.
Let A be the original n × n graph adjacency matrix, and apw and anw be the
added positive and negative edge weights. Assume we have two classes with a n × 2
label indication matrix F, where F i = [1, 0] (the ith row vector of F) if node x i is
123
5. Allocate each unlabelled node to a class based on the sign of the corresponding
entry in the principal eigenvector of the eigendecomposition corresponding to
the signed graph Laplacian. It would be plausible to use a subset of k of the
eigenvectors, and cluster in k-dimensional space, using any standard clustering
algorithm, but this turns out not to be stable.
When there are more than two classes, a one-versus-the-rest strategy is used, in the
style of support vector machines. The effect of this strategy is shown in Figure 9.1(a).
(a) Adding edges between station nodes
(b) Adding edges between all labelled nodes
Figure 9.1: Two possible ways to add negative edges. The solid edges are positive
and the dashed edges are negative.
It would also be possible to add positive nodes between labelled nodes with
the same label, and negative edges between nodes with different labels. The result
is shown in Figure 9.1(b). With this strategy, the number of added edges increases
quadratically in the number of labelled nodes, while our strategy requires extra edges
only linear in the number of labelled nodes. As the figures show, even for this small
graph the difference is non-trivial.
A technical problem remains which requires an extension to the previous signed
spectral embedding technique. Node degree matters and the labelled nodes have all
had their degree increased by one by the addition of a new edge to the class representative node. The total degree of the graph has also increased. To avoid the distortions
that this might create, we modify the total degree term in L sns so that the total degree of original nodes are computed based on the original graph edges, and the total
degree of stations are computed based on the total degree in the new graph.
Let A be the original n × n graph adjacency matrix, and apw and anw be the
added positive and negative edge weights. Assume we have two classes with a n × 2
label indication matrix F, where F i = [1, 0] (the ith row vector of F) if node x i is