Abstract
Ensemble classification methods that independently construct component models (e.g., bagging) improve accuracy over single models by reducing the error due to variance. Some work has been done to extend ensemble techniques for classification in relational domains by taking relational data characteristics or multiple link types into account during model construction. However, since these approaches follow the conventional approach to ensemble learning, they improve performance by reducing the error due to variance in learning. We note however, that variance in inference can be an additional source of error in relational methods that use collective classification, since inferred values are propagated during inference. We propose a novel ensemble mechanism for collective classification that reduces both learning and inference variance, by incorporating prediction averaging into the collective inference process itself. We show that our proposed method significantly outperforms a straightforward relational ensemble baseline on both synthetic and real-world datasets.
Introduction
In traditional machine learning, data points are typically assumed to be independent and identically distributed (i.i.d.). Relational learning, however, leverages the dependencies between entities—for instance, the tendency for individuals to share political views with their social circle. Collective Classification (CC) exploits these links to jointly infer labels across a network.
While standard ensemble methods like bagging are effective at reducing learning variance (error from training on limited data), they overlook a critical source of error in relational domains: inference variance. In CC, predictions are propagated through the network; a single noisy prediction can "infect" neighboring nodes, leading to widespread errors. This paper introduces Collective Ensemble Classification (CEC), a framework that interleaves model predictions during the collective inference process to mitigate this "ripple effect."
Methodology: Collective Ensemble Classification (CEC)
The core innovation of CEC lies in how it combines multiple models compared to a standard Relational Ensemble (RE):
- Relational Ensemble (RE): $k$ models are trained independently (e.g., on different link types). Inference is run on each model until convergence, and their final outputs are averaged.
- Collective Ensemble Classification (CEC): $k$ models are run simultaneously. During each iteration of the collective inference loop, the prediction for a node from one model is immediately averaged with the current predictions from all other models before proceeding.
By "interleaving" the averaging process inside the inference loop, CEC acts as a stabilizer, damping inference variance before it can propagate through the network.
Experimental Evaluation
The researchers evaluated CEC on three datasets: Facebook (predicting political views), IMDb (predicting blockbuster status), and synthetic graphs with varying autocorrelation and linkage density.
Performance Results
CEC consistently outperformed all baselines, including standard Relational Ensembles. As shown in the figure below, CEC maintains a significant lead in AUC across varying proportions of labeled nodes in all three test environments.
Mechanism of Improvement
The superiority of CEC is tied to its ability to reduce inference variance. In experiments varying the number of link sources and the degree of interleaving, the authors demonstrated that CEC scales better with more data sources and explicitly reduces the variance of the inference process.
Discussion and Key Insights
- Dynamic Averaging: The "Aha!" moment is that averaging at the end of inference is often too late. Stabilizing the process during inference prevents error propagation.
- Robustness to Sparsity: CEC is particularly effective when labels are sparse (e.g., 10% labeled). By pooling information early, it identifies reliable paths to correct labels that single models might miss.
- Complexity vs. Stability: Simply combining all link types into one large model often underperformed due to increased model complexity. The ensemble approach provided greater stability.
Conclusion and Future Work
CEC provides a robust framework for relational classification by addressing both learning and inference variance. While this work focused on multi-source ensembles, future research could extend CEC to single-source scenarios using relational resampling. Additionally, combining CEC with stacking techniques could further enhance performance by reducing model bias.
Summary updated