Inferring useful heuristics from the dynamics of iterative relational classifiers

Aram Galstyan, Paul R. Cohen

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)708-713
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2005
Externally publishedYes
Event19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom
Duration: Jul 30 2005Aug 5 2005

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Inferring useful heuristics from the dynamics of iterative relational classifiers'. Together they form a unique fingerprint.

Cite this