Exploiting Network Structure for Active Inference in Collective Classification

Active inference seeks to maximize classification perfor- mance while minimizing the amount of data that must be labeled ex ante. This task is particularly relevant in the context of relational data, where statistical dependencies among instances can be exploited to improve classification accuracy. We show that efficient methods for indexing net- work structure can be exploited to select high-value nodes for labeling. This approach substantially outperforms ran- dom selection and selection based on simple measures of local structure. We demonstrate the relative effectiveness of this selection approach through experiments with a rela- tional neighbor classifier on a variety of real and synthetic data sets, and identify the necessary characteristics of the data set that allow this approach to perform well.