Transductive label spreading on a hypergraph
Source:R/hypergraph_laplacian.R
hypergraph_transduction.Rdhypergraph_transduction() classifies the unlabelled nodes of a
hypergraph from a few labelled ones, by the label-spreading framework of
Zhou et al. (2006). The labels spread over the hypergraph as the scores
$$F = (1 - \xi) (I - \xi S)^{-1} Y,$$
where \(S = I - L\) is the similarity operator of the chosen Laplacian
(see hypergraph_laplacian()) and \(Y\) marks each labelled node's
class, and each node is assigned the class with the highest score. This
is the non-neural ancestor of hypergraph-attention text classifiers: with
documents as hyperedges over words (or the reverse), it classifies
unlabelled nodes from a handful of labelled ones.
The margin of a node, its winning minus its runner-up score, says how
clearly it was assigned; assignments with a small margin are the ones to
distrust. The given labels are not held fixed, so a labelled node can be
predicted into another class, and a class's scores grow with its number
of labelled nodes. As xi approaches 1, every node's scores become
proportional to the same vector, so in the limit every node is assigned
the same class. The default 0.99 is the value of Zhou et al. (2006) and
suits large hypergraphs; on a small one it over-smooths. In the example
below it assigns five of the six nodes to one class, where xi = 0.9
splits them three and three, so on a small hypergraph pass a smaller
xi and compare.
Usage
hypergraph_transduction(
hg,
labels,
xi = 0.99,
type = c("zhou", "random_walk"),
edge_weights = NULL
)
# S3 method for class 'net_hypergraph_transduction'
print(x, ...)
# S3 method for class 'net_hypergraph_transduction'
summary(object, ...)
label_predictions(x)
label_scores(x)
# S3 method for class 'net_hypergraph_transduction'
plot(x, ...)Arguments
- hg
The hypergraph: a connected
net_hypergraph, as forhypergraph_laplacian().- labels
The known class labels, in one of two forms: a vector named by node, covering some of the nodes, or an unnamed vector with one entry per node, in the hypergraph's node order, and
NAfor the unlabelled ones. Required. It must hold at least two distinct classes; a name that is not a node, or an unnamed vector of the wrong length, raises an error.- xi
The spreading coefficient, a number strictly between 0 and 1. Larger values give the hypergraph structure more weight relative to the given labels. Default
0.99.- type, edge_weights
The Laplacian and its hyperedge weights, passed to
hypergraph_laplacian(). Defaults"zhou"andNULL.- x
For the
print()andplot()methods and forlabel_predictions()andlabel_scores(): anet_hypergraph_transductionobject.- ...
For the methods: ignored.
- object
For the
summary()method: anet_hypergraph_transductionobject.
Value
A net_hypergraph_transduction object. print() reports the
Laplacian, xi, the classes and how many nodes each was predicted
for; summary() returns one row per class; plot() draws the
node-by-class score heatmap. The object's fields:
- predictions
A data frame with one row per node:
node,label(the given label,NAfor an unlabelled node),predicted,score(the winning class's score) andmargin(the winning minus the runner-up score).- classes
The classes, sorted.
- scores
The node-by-class score matrix.
- xi, type
The spreading coefficient and the Laplacian type.
- n_labeled, n_nodes
The numbers of labelled and of all nodes.
- params
The
edge_weightsused.
The print() method returns its input invisibly. The summary()
method returns a data frame with one row per class: class,
n_labeled, n_predicted and mean_margin (the mean margin of the
nodes predicted into the class, NA when there are none).
label_predictions() returns a data frame with one row per node:
node, label (NA for an unlabelled node), predicted, score and
margin. label_scores() returns a data frame with one row per node
and class: node, class and score. The plot() method
returns the score heatmap as a ggplot, visibly, so plot(x) draws
it: one row per node, grouped by
predicted class and ordered by margin within it, one column per class,
the tiles shaded and labelled by score. Labelled nodes have a black
border on their given class, and a dot marks each node's winning class,
so seeds, scores and assignments can be compared in one panel.
References
Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with hypergraphs: Clustering, classification, and embedding. NeurIPS 19.
Examples
events <- data.frame(
person = c("a", "b", "c", "a", "b", "c", "d", "e", "f",
"d", "e", "f", "c", "d"),
meeting = c("m1", "m1", "m1", "m2", "m2", "m2", "m3", "m3", "m3",
"m4", "m4", "m4", "m5", "m5")
)
hg <- bipartite_groups(events, player = "person", group = "meeting")
tr <- hypergraph_transduction(hg, labels = c(a = "x", d = "y"), xi = 0.9)
tr
#> Hypergraph transductive label spreading (zhou Laplacian, xi = 0.9)
#> Nodes: 6 (2 labeled) | Classes: x, y
#> Predicted: x = 3, y = 3
label_predictions(tr)
#> node label predicted score margin
#> 1 a x x 0.3062500 0.21439413
#> 2 b <NA> x 0.2062500 0.11439413
#> 3 c <NA> x 0.2143304 0.06433035
#> 4 d y y 0.3500000 0.25814413
#> 5 e <NA> y 0.2143304 0.15808035
#> 6 f <NA> y 0.2143304 0.15808035
label_scores(tr)
#> node class score
#> 1 a x 0.30625000
#> 2 b x 0.20625000
#> 3 c x 0.21433035
#> 4 d x 0.09185587
#> 5 e x 0.05625000
#> 6 f x 0.05625000
#> 7 a y 0.09185587
#> 8 b y 0.09185587
#> 9 c y 0.15000000
#> 10 d y 0.35000000
#> 11 e y 0.21433035
#> 12 f y 0.21433035