Abstract
This paper introduces Two-Stage-MR-BPR, a novel matrix factorization framework designed for multi-label classification in sparse networks. By leveraging transitive node similarity to estimate relationship weights and employing a sequential two-stage training protocol, the model addresses the critical challenges of network sparsity and uniform edge weighting. Experimental evaluations across social, biological, and citation networks demonstrate that Two-Stage-MR-BPR significantly outperforms state-of-the-art methods, including DeepWalk and Node2Vec, particularly in data-constrained scenarios.
Introduction
Network classification is a fundamental task involving the prediction of node labels, such as user interests in social media or protein functions in biological systems. Most real-world networks rely on implicit feedback, where only the existence of a connection is observed without information regarding its strength or semantic significance.
Current state-of-the-art methods face two primary hurdles:
- Sparsity: Networks are often extremely sparse, hindering the learning of robust latent representations.
- Uniform Weighting: Existing models typically treat all observed edges as equally important, failing to distinguish between "strong" and "weak" ties.
While some models attempt to learn weights through external metadata like timestamps, such data is often unavailable. This research proposes approximating these weights using only the intrinsic network structure.
Methodology
The proposed Two-Stage-MR-BPR model introduces two primary innovations to improve latent representation learning in sparse graphs.
Transitive Node Similarity (FriendTNS)
To address the uniform weighting problem, the authors utilize a similarity function based on node degrees. Connections between nodes with relatively low degrees are weighted more heavily than those involving high-degree "hubs." This serves as a structural proxy for relationship strength without requiring external metadata.
Two-Stage Training Protocol
Standard Bayesian Personalized Ranking (BPR) models distinguish between observed and unobserved edges. However, alternating between ranking weighted edges and distinguishing observed from unobserved edges can lead to "information overwrite." The Two-Stage-MR-BPR model employs a sequential approach within every epoch:
- Stage 1: The model is trained to rank observed edges based on their calculated structural weights.
- Stage 2: The model is trained to distinguish observed edges from unobserved ones.
This sequential optimization shifts the scores of observed edges away from unobserved ones while preserving the internal ranking of weighted edges, leading to a more stable optimization path.
Experimental Results
The model was evaluated on four diverse datasets: BlogCatalog (social), PPI (biological), Wiki (informational), and Cora (citation).
Performance Highlights
Two-Stage-MR-BPR consistently outperformed baselines across all datasets and training splits. Notably:
- Efficiency: On the BlogCatalog dataset, the model achieved higher Micro-F1 scores using 50% of the training data than competing models like DeepWalk achieved with 90%.
- Robustness: In the PPI network, the model maintained superior performance even when only 10% of labeled nodes were available for training.
- Statistical Significance: Improvements over Node2Vec and DeepWalk were found to be statistically significant ($p < 0.01$).
Conclusion
Two-Stage-MR-BPR demonstrates that network structure alone can provide a powerful signal for differentiating relationship strengths in sparse graphs. The sequential two-stage training protocol effectively prevents the information loss common in alternating learning schemes. Future work may explore incorporating non-linear latent representations via deep learning and investigating non-uniform sampling strategies to further refine edge ranking.
Summary updated