Abstract
Within-network classification aims to predict labels for unknown nodes using graph structure and limited labeled data. Traditional methods often struggle with class overlap and sparse labels, as they typically assume data points are independent and identically distributed (IID). This paper introduces ReSLMin (Regularized Structural Loss Minimization), a framework that replaces standard local loss functions with a "structural loss" accounting for neighborhood consistency and a "homophily regularizer" to smooth decision boundaries. Experimental results on real-world datasets demonstrate that ReSLMin achieves state-of-the-art performance and exhibits significant robustness to high class overlap compared to existing methods.
Introduction: The Challenge of Class Overlap
In within-network classification, we predict labels of unknown nodes based on a few labeled examples and the link structure of the graph. Unlike traditional machine learning, nodes in a network are inherently dependent—friends share interests, and papers cite similar research.
A major flaw in current approaches is class overlap. In many networks, a node might sit on the boundary of two communities. Standard loss functions, such as Hinge Loss, penalize a node only if its predicted label doesn't match its ground truth. This "all-or-nothing" approach fails to capture the "soft membership" of boundary nodes. Furthermore, when labels are sparse, traditional methods struggle to find a robust decision boundary because they do not look far enough into a node's neighborhood.
Methodology: ReSLMin
The authors propose a two-pronged solution called ReSLMin:
- Structural Loss Function: Instead of a node's loss being purely local, ReSLMin employs a "reverse cascading" loss. If a node is misclassified, it induces a loss not just on itself, but also on its neighbors (and their neighbors, recursively). This ensures the learned model favors labels consistent with the majority of the neighborhood. Mathematically, this is expressed as a weighted sum of expected losses across $k$-level neighborhoods.
- Homophily Regularizer: To prevent overfitting, the authors combine standard $\ell_2$ (ridge) regularization with a graph-Laplacian-based "homophily regularizer." This forces the "discriminatory power" (the weights $w$) to transition smoothly between connected nodes, reinforcing the idea that connected entities should exhibit similar behavior.
The resulting objective function is convex, allowing for efficient solution via Stochastic Gradient Descent (SGD).
Datasets and Evaluation
The authors evaluated ReSLMin on four diverse real-world datasets:
- Co-citation Graphs (PubMed & CoRA): Academic papers where edges represent citations.
- Product Graph (Amazon): Books where edges represent "similar products." This dataset is particularly challenging due to high class overlap (books often belong to multiple genres).
- Web Graph (Wikipedia): Articles from computer science categories where edges are hyperlinks.
Key Insights
- Neighborhood as Evidence: The structural loss treats the neighborhood as a collective voting block, providing evidence for unlabeled nodes.
- Handling the "Boundary" Problem: By normalizing neighbor influence, the model avoids bias toward high-degree "hub" nodes, finding more accurate boundaries in dense, overlapping areas.
- Smoothing Discriminatory Power: The homophily regularizer smooths the parameters of the classifier across the graph topology, making the model robust to noisy links.
- Scalability: ReSLMin’s SGD-based approach scales linearly with the number of edges and nodes.
Key Results and Robustness
ReSLMin consistently outperformed heavy hitters like DeepWalk, SocioDim (SDEC), and Social Context Relational Neighbor (SCRN) across Hamming score, Micro-$F_1$, and Macro-$F_1$ metrics.
A critical finding is ReSLMin's robustness to overlap. In synthetic tests using the LFR benchmark, ReSLMin maintained high accuracy even as the "mixing coefficient" (a measure of class overlap) increased. In contrast, competing methods like SNBC saw sharp performance drops as the network became more "messy." This effectiveness was further confirmed on the Amazon dataset, where ReSLMin showed the most significant gains.
Limitations and Future Work
While ReSLMin demonstrates strong results, future work could address hyperparameter sensitivity ($\alpha, \lambda, \mu$) and the computational trade-offs of very deep neighborhood cascades. Additionally, extending the framework to natively handle edge directionality in directed graphs could capture more nuance in web or citation data.
Summary updated