Single Network Relational Transductive Learning

Amit Dhurandhar, Jun Wang

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.

Definitions of symbols used in the weighting scheme.

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.

Illustration of the transformation from an unweighted graph $T$ to a weighted graph $T_w$ using the proposed scheme.

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

Abstract

Relational classification on a single connected network has been of particular interest in the machine learning and data mining communities in the last decade or so. This is mainly due to the explosion in popularity of social networking sites such as Facebook, LinkedIn and Google+ amongst others. In statistical relational learning, many techniques have been developed to address this problem, where we have a connected unweighted homogeneous/heterogeneous graph that is partially labeled and the goal is to propagate the labels to the unlabeled nodes. In this paper, we provide a different perspective by enabling the effective use of graph transduction techniques for this problem. We thus exploit the strengths of this class of methods for relational learning problems. We accomplish this by providing a simple procedure for constructing a weight matrix that serves as input to a rich class of graph transduction techniques. Our procedure has multiple desirable properties. For example, the weights it assigns to edges between unlabeled nodes naturally relate to a measure of association commonly used in statistics, namely the Gamma test statistic. We further portray the efficacy of our approach on synthetic as well as real data, by comparing it with state-of-the-art relational learning algorithms, and graph transduction techniques with an adjacency matrix or a real valued weight matrix computed using available attributes as input. In these experiments we see that our approach consistently outperforms other approaches when the graph is sparsely labeled, and remains competitive with the best when the proportion of known labels increases.
BibTeX
@article{dhurandhar2013single,
  author = {Amit Dhurandhar and Jun Wang},
  title = {{Single Network Relational Transductive Learning}},
  journal = {J. Artif. Intell. Res.},
  year = {2013},
  doi = {10.1613/jair.4068},
}
Figure