  Online structure learning approaches, such as those stemming from Statistical
Relational Learning, enable the discovery of complex relations in noisy data
streams. However, these methods assume the existence of fully-labelled training
data, which is unrealistic for most real-world applications. We present a novel
approach for completing the supervision of a semi-supervised structure learning
task. We incorporate graph-cut minimisation, a technique that derives labels
for unlabelled data, based on their distance to their labelled counterparts. In
order to adapt graph-cut minimisation to first order logic, we employ a
suitable structural distance for measuring the distance between sets of logical
atoms. The labelling process is achieved online (single-pass) by means of a
caching mechanism and the Hoeffding bound, a statistical tool to approximate
globally-optimal decisions from locally-optimal ones. We evaluate our approach
on the task of composite event recognition by using a benchmark dataset for
human activity recognition, as well as a real dataset for maritime monitoring.
The evaluation suggests that our approach can effectively complete the missing
labels and eventually, improve the accuracy of the underlying structure
learning system.
