Inferring useful heuristics from the dynamics of iterative relational classifiers

In this paper we consider dynamical properties of simple iterative relational classifiers. We conjecture that for a class of algorithms that use label-propagation the iterative procedure can lead to non-trivial dynamics in the number of newly classified instances. The underlaying reason for this non-triviality is that in relational networks true class labels are likely to propagate faster than false ones. We suggest that this phenomenon, which we call two-tiered dynamics for binary classifiers, can be used for establishing a self-consistent classification threshold and a criterion for stopping iteration. We demonstrate this effect for two unrelated binary classification problems using a variation of a iterative relational neighbor classifier. We also study analytically the dynamical properties of the suggested classifier, and compare its results to the numerical experiments on synthetic data.