Abstract
This paper investigates methods for improving classification accuracy in networked data by integrating noisy external classifier information with graph-based relational structures. Traditional semi-supervised learning often relies on a small set of perfectly labeled nodes. In contrast, this work explores scenarios where every node has an initial, potentially inaccurate label distribution. We propose a Least Squares Regularization (LSR) method that is computationally efficient and robust. Experimental results across various benchmarks and real-world datasets demonstrate that utilizing "soft" information from all nodes significantly outperforms selecting a high-confidence subset, with LSR providing a 6–10x speedup over existing information regularization techniques.
Introduction
Classifying large-scale networked data, such as web pages or research citations, often faces the challenge of expensive manual labeling. While "gold standard" labels are scarce, two resources are frequently available: the relational structure of the data (the graph) and noisy initial predictions from an external classifier (e.g., a simple keyword search or a basic logistic regression model).
The core research question addressed is how to effectively leverage the graph structure to "clean up" these noisy external labels. Unlike traditional relational learning that assumes a binary state of labeled vs. unlabeled nodes, this study treats every node as having a noisy prior, seeking a global labeling that balances local external evidence with graph-wide smoothness.
Methodology
The authors evaluate two primary strategies for integrating external classifier distributions:
- Hard Selection (Setting 1): The external classifier identifies a subset of nodes where it has the highest confidence. These are treated as fixed labels, and the problem is reduced to standard semi-supervised learning.
- Soft Fitting (Setting 2): The external classifier’s full distribution for every node is used as a "fitting" term in a global objective function. This approach aims to find a labeling that is smooth across connected nodes while remaining close to the initial noisy guesses.
Algorithmic Contributions
A key contribution is the Least Squares Regularization (LSR) method. While Information Regularization (IR) methods typically use KL-divergence—requiring expensive non-linear optimization—LSR utilizes squared error as a divergence measure. This allows for efficient, closed-form updates. Additionally, the authors extend the Weighted Vote Relational Neighbor (WvRN) algorithm using "dongle nodes" to incorporate external distributions as fixed reference points for every node in the graph.
Experimental Setup
The proposed methods were evaluated on several benchmark datasets and real-world shopping data. The benchmarks include WebKB, USPS, and two versions of the CORA citation dataset.
For datasets with "perfect" ground truth labels, the authors simulated inaccurate external classifiers by injecting controlled levels of noise. Real-world tests were conducted on shopping datasets from CompUSA, UncommonGoods, and Walmart, focusing on binary classification tasks like identifying product detail pages.
Results and Discussion
The experimental results yield several key insights:
- Comprehensive Data Utilization: "Soft Fitting" (Setting 2) consistently outperformed "Hard Selection" (Setting 1). Retaining the noisy information from all nodes provides a superior prior for graph regularization compared to discarding data.
- Efficiency of LSR: LSR achieved accuracy comparable to Information Regularization methods while being 6–10 times faster than Dual IR (DIR). This scalability makes it highly suitable for large-scale web applications.
- Robustness: Sorting nodes by Entropy for validation or labeling was more effective than using maximum probability. Furthermore, LSR and the extended WvRN-V2 showed greater stability across varying regularization constants ($C$) compared to traditional methods like LGC.
- Real-World Impact: On shopping datasets, leveraging link structure improved external classifier accuracy by up to 10%.
Conclusion
This work demonstrates that inaccurate external information, when properly regularized via a graph structure, is a powerful asset for classification. The proposed LSR method offers a compelling balance of speed and accuracy. Future research may explore automated weighting schemes to identify which external labels are most likely to be erroneous based on graph topology, further enhancing the robustness of these relational learning techniques.
Summary updated