Abstract
Within-network classification involves propagating labels across a single, large graph where only a small fraction of nodes are labeled. Traditional approaches either use computationally intensive Statistical Relational Learning (SRL) or efficient Graph Transduction Algorithms (GTA) that often assume homophily. This paper introduces a novel weighting scheme that enables GTA to handle complex label correlations, including negative autocorrelation, in unweighted graphs. By grounding the weighting procedure in the Gamma test statistic, the authors demonstrate that their method significantly outperforms state-of-the-art SRL models in sparse data scenarios.
Introduction
In domains such as social networks, citation indices, and retail analytics, data is often represented as a single, massive connected graph. A common challenge is "within-network classification," where the goal is to predict labels for the majority of nodes based on a tiny subset of labeled examples.
Historically, researchers have chosen between two paradigms. Statistical Relational Learning (SRL), such as Markov Logic Networks, excels at capturing complex dependencies but suffers from high computational costs and variance when labels are sparse. Graph Transduction Algorithms (GTA), like Label Propagation, offer efficiency but typically rely on the assumption of homophily—that neighboring nodes share labels. However, many real-world networks exhibit "anti-homophily" (e.g., students linking to professors). Standard GTA methods struggle with these unweighted, negatively correlated structures.
The Weighting Framework
The authors propose a principled method to construct a weight matrix $W$ from an unweighted graph, which can then be utilized in standard graph transduction frameworks. The key is to assign weights based on the empirical distribution of labels in the known portion of the graph.
As shown in the table above, the method defines $P_{same}$ as the ratio of edges connecting nodes with the same label to the total number of labeled edges, and $P_{opp}$ for nodes with different labels. For edges involving unlabeled nodes, the framework uses an unbiased estimate based on the expected value of label correlations.
This weighting scheme is statistically grounded; the authors prove that the weight assigned to edges between unlabeled nodes is mathematically equivalent to the Gamma test statistic, a standard measure of association. To accommodate the negative weights that arise in anti-homophilous networks, the authors adapt the smoothness term in the standard Graph Laplacian regularization framework.
Experimental Evaluation
The proposed method (LGCW/HFGFW) was evaluated against synthetic and real-world benchmarks, including UW-CSE, WEBKB, and a retail dataset named BREAD.
Key Findings
- Performance in Sparse Settings: The method shines in "cold start" scenarios where only 5-10% of nodes are labeled. In these cases, it consistently outperformed complex SRL models like Relational Dependency Networks (RDNs) and Markov Logic Networks (MLNs).
- Handling Negative Correlation: In the BREAD dataset, proximity between retail stores often indicates competition rather than similarity. While standard graph techniques failed, the proposed method successfully captured this negative autocorrelation.
- Robustness: As the proportion of labeled data increases, the method remains competitive with SRL models, which typically require more data to tune their extensive parameters.
Conclusion
By bridging the gap between statistical relational modeling and efficient graph transduction, this work provides a robust framework for classification in large-scale networks. The discovery that intuitive weighting heuristics align with classical statistics like the Gamma statistic provides a theoretical foundation for the approach. Future work includes extending the framework for one-shot multi-class classification and exploring local neighborhood-based weighting to capture finer nuances in complex graph structures.
Summary updated