Chapter 9
Signed graph-based
semi-supervised learning
We now turn to using the signed graph embedding construction of the last chapter as
a new way to frame and solve the problems of semi-supervised prediction, especially
for classes of different sizes.
Consider a social network where only a few nodes have been labelled with
the value of a particular property. The task is to label all of the other nodes in the
way that best respects the known labels and the connection structure of the social
network. Of course, this will only work well if the property of interest is associated
with homophily — similar nodes from the social-network perspective are likely to
be similar with respect to the property. Examples include political affiliation (friends
tend to have similar political views), age (friends tend to be in a similar age cohort),
and length of arrest record (criminals tend to have criminal friends).
The intuition for graph-based semi-supervised prediction is that an unlabelled
record should be assigned the label of its “closest” labelled neighbor — but “closest”
is a subtle relationship because it may depend not only on the shortest path from the
unlabelled node to the labelled node, but also on the number of such paths. In other
words, an unlabelled node connected to a class A node by a single short path, but to
a class B node by several slightly longer paths, may still be reasonably classified as
class B. Graph-based semi-supervised prediction is appropriate when the properties
of a node are best understood within some larger context — for example, the decision
to buy a product may depend not only on an individual’s preferences, but also on
those of their neighbors in the social network, either because of social pressure, or
because they get trusted recommendations from their neighbors. Graph-based SemiSupervised Learning (SSL) algorithms tend to have a better performance than nongraph-based SSL approaches [92] and have been successfully used in many areas
[93].
The labels of the labelled subset of the nodes could be thought of as a kind of
influence that flows along the edges of a graph, flowing most easily along edges with
heavy weights and gradually diminishing in intensity, but also flowing in parallel
121
Signed graph-based
semi-supervised learning
We now turn to using the signed graph embedding construction of the last chapter as
a new way to frame and solve the problems of semi-supervised prediction, especially
for classes of different sizes.
Consider a social network where only a few nodes have been labelled with
the value of a particular property. The task is to label all of the other nodes in the
way that best respects the known labels and the connection structure of the social
network. Of course, this will only work well if the property of interest is associated
with homophily — similar nodes from the social-network perspective are likely to
be similar with respect to the property. Examples include political affiliation (friends
tend to have similar political views), age (friends tend to be in a similar age cohort),
and length of arrest record (criminals tend to have criminal friends).
The intuition for graph-based semi-supervised prediction is that an unlabelled
record should be assigned the label of its “closest” labelled neighbor — but “closest”
is a subtle relationship because it may depend not only on the shortest path from the
unlabelled node to the labelled node, but also on the number of such paths. In other
words, an unlabelled node connected to a class A node by a single short path, but to
a class B node by several slightly longer paths, may still be reasonably classified as
class B. Graph-based semi-supervised prediction is appropriate when the properties
of a node are best understood within some larger context — for example, the decision
to buy a product may depend not only on an individual’s preferences, but also on
those of their neighbors in the social network, either because of social pressure, or
because they get trusted recommendations from their neighbors. Graph-based SemiSupervised Learning (SSL) algorithms tend to have a better performance than nongraph-based SSL approaches [92] and have been successfully used in many areas
[93].
The labels of the labelled subset of the nodes could be thought of as a kind of
influence that flows along the edges of a graph, flowing most easily along edges with
heavy weights and gradually diminishing in intensity, but also flowing in parallel
121