122
Chapter 9. Signed graph-based semi-supervised learning
along multiple edges. The label given to an unlabelled node becomes either that of
the leading edge of the flow from one of the labelled nodes, or the greatest intensity
of flow that reached it from any labelled node. Most existing algorithms use some
variant of this “spreading activation” intuition.
When the sizes of the classes are different, or the number of labelled nodes
is not proportional to the size of the class that they represent, the performance of
these algorithms degrades. It is easy to see why. The flow from the labelled nodes
of a small class can quickly reach all of the nodes of the cluster of unlabelled nodes
that belong to that class, and then begins to infiltrate the nodes of other clusters,
even though these other clusters are only weakly connected to it. If there are few
labelled nodes for one of the classes, then the flow from them does not necessarily
reach all of the nodes in the appropriate cluster before the flow from nodes with other
labels reaches them. These performance degradations can be demonstrated in both
synthetic and real-world datasets.
Embedding the social network in a geometric space simplifies the spreading
process because it becomes a wavefront moving directly in that space. Or, to put
it another way, the label of an unlabelled node can be determined by computing
the distance between it and the labelled nodes in the geometry. Using the signed
network embedding technique introduced in the previous chapter enables a semisupervised prediction algorithm that performs at about the same level as other graphbased SSL approaches when the classes, or the labelled class representatives, are
balanced. However, when either, or both, are not balanced this approach performs
substantially better. Since there is no reason to suppose that real-world datasets will
necessarily be doubly balanced, as these other algorithms require, our approach is
more general.
We compare our SSL method with existing spectral kernel SSL methods: LGC
[118], LapSVMp [59] and TACO [73] by applying them to several synthetic and
two real-world datasets: the USPS handwritten digits and ISOLET Spoken Letter
datasets.
9.1 Approach
We avoid the problems associated with spreading activation strategies and leverage
the ability to embed signed graphs. Consider first the two-class case. The high-level
algorithm uses these steps:
1. Add two new nodes (“stations”) that act as class representatives;
2. Connect the labelled nodes of each class to their class representative by positively weighted edges;
3. Force the class representatives apart by adding a negative edge between them
(which tends to pull the labelled nodes of each class further from one another
which, in turn, tends to pull the unlabelled nodes of each class further apart);
4. Embed the graph in a Euclidean space using the spectral signed network embedding algorithm;
Chapter 9. Signed graph-based semi-supervised learning
along multiple edges. The label given to an unlabelled node becomes either that of
the leading edge of the flow from one of the labelled nodes, or the greatest intensity
of flow that reached it from any labelled node. Most existing algorithms use some
variant of this “spreading activation” intuition.
When the sizes of the classes are different, or the number of labelled nodes
is not proportional to the size of the class that they represent, the performance of
these algorithms degrades. It is easy to see why. The flow from the labelled nodes
of a small class can quickly reach all of the nodes of the cluster of unlabelled nodes
that belong to that class, and then begins to infiltrate the nodes of other clusters,
even though these other clusters are only weakly connected to it. If there are few
labelled nodes for one of the classes, then the flow from them does not necessarily
reach all of the nodes in the appropriate cluster before the flow from nodes with other
labels reaches them. These performance degradations can be demonstrated in both
synthetic and real-world datasets.
Embedding the social network in a geometric space simplifies the spreading
process because it becomes a wavefront moving directly in that space. Or, to put
it another way, the label of an unlabelled node can be determined by computing
the distance between it and the labelled nodes in the geometry. Using the signed
network embedding technique introduced in the previous chapter enables a semisupervised prediction algorithm that performs at about the same level as other graphbased SSL approaches when the classes, or the labelled class representatives, are
balanced. However, when either, or both, are not balanced this approach performs
substantially better. Since there is no reason to suppose that real-world datasets will
necessarily be doubly balanced, as these other algorithms require, our approach is
more general.
We compare our SSL method with existing spectral kernel SSL methods: LGC
[118], LapSVMp [59] and TACO [73] by applying them to several synthetic and
two real-world datasets: the USPS handwritten digits and ISOLET Spoken Letter
datasets.
9.1 Approach
We avoid the problems associated with spreading activation strategies and leverage
the ability to embed signed graphs. Consider first the two-class case. The high-level
algorithm uses these steps:
1. Add two new nodes (“stations”) that act as class representatives;
2. Connect the labelled nodes of each class to their class representative by positively weighted edges;
3. Force the class representatives apart by adding a negative edge between them
(which tends to pull the labelled nodes of each class further from one another
which, in turn, tends to pull the unlabelled nodes of each class further apart);
4. Embed the graph in a Euclidean space using the spectral signed network embedding algorithm;