Language-Constraint Reachability Learning in Probabilistic Graphs

Claudio Taranto, Nicola Di Mauro, Floriana EspositoarXiv 2012 · arXiv

Introduction

Traditional graph analysis typically treats edges as binary entities. However, real-world networks—ranging from social interactions to sensor data—often involve uncertainty, where edges represent probabilities of existence or strengths of association. While link prediction (determining if an edge exists) is well-studied, link classification (determining the type or label of an edge) in probabilistic environments remains a significant challenge. This paper introduces Eagle, a framework that bridges formal language theory and probabilistic inference to address this problem.

The Eagle Framework

The Eagle system treats the probability of specific path types as high-quality features for a classifier. The methodology consists of five core stages:

  1. Probabilistic Graph Modeling: Graphs are defined with labeled edges and associated existence probabilities.
  2. Language-Constraint Reachability: Complex relationship patterns are formalized using Context-Free Languages (CFLs). For instance, a path might represent a sequence like "User A follows User B, who purchased Item X."
  3. Monte Carlo Inference: Calculating exact path probabilities across all "possible worlds" is computationally intractable. Eagle employs Monte Carlo sampling, generating $n$ discrete graph snapshots to estimate the overall reachability probability.
  4. Feature Engineering: These estimated probabilities serve as input features for the learning model.
  5. Classification: An L2-regularized logistic regression model (via LIBLINEAR) is trained on these features to predict unobserved link labels, such as movie ratings.

Experimental Evaluation

The researchers validated Eagle using the MovieLens 100K dataset, which contains 100,000 ratings (1 to 5) from 943 users on 1,682 movies. The task was framed as a 5-class classification problem to predict the specific rating a user would assign to a movie.

Table 1: Frequency distribution of ratings r1 through r5 in the MovieLens 100K dataset, illustrating the inherent class imbalance.

As shown in the distribution above, the dataset exhibits a clear imbalance, with higher ratings (4 and 5) being significantly more frequent than lower ones. This distribution provides the ground truth for the classification task.

Results and Discussion

Eagle was compared against Singular Value Decomposition (SVD), a standard baseline in recommendation systems. The results indicated that Eagle achieved a lower Macroaveraging Mean Absolute Error ($MAE^M$) of approximately 0.835, compared to SVD's 0.908. This improvement was statistically significant ($p < 10^{-6}$).

Key insights from the study include:

  • Structural Topology: Path probabilities capture the network's structural topology more effectively than local neighborhood metrics.
  • Hybrid Features: Combining user-based path features with item-based features yields superior accuracy compared to using either alone.
  • Robustness to Imbalance: Eagle proved more resilient to the skewed rating distribution shown in the experimental data compared to baseline methods that assumed uniform distributions.

Conclusion and Future Work

While Eagle demonstrates the power of language-constrained features, it faces scalability challenges due to the computational cost of Monte Carlo sampling on large-scale graphs. Future research directions include "grammar induction" to automatically learn predictive path types and exploring deeper graph traversals beyond the current focus on short paths (length 2-4).

Summary updated

Abstract

The probabilistic graphs framework models the uncertainty inherent in real-world domains by means of probabilistic edges whose value quantifies the likelihood of the edge existence or the strength of the link it represents. The goal of this paper is to provide a learning method to compute the most likely relationship between two nodes in a framework based on probabilistic graphs. In particular, given a probabilistic graph we adopted the language-constraint reachability method to compute the probability of possible interconnections that may exists between two nodes. Each of these connections may be viewed as feature, or a factor, between the two nodes and the corresponding probability as its weight. Each observed link is considered as a positive instance for its corresponding link label. Given the training set of observed links a L2-regularized Logistic Regression has been adopted to learn a model able to predict unobserved link labels. The experiments on a real world collaborative filtering problem proved that the proposed approach achieves better results than that obtained adopting classical methods.
BibTeX
@misc{taranto2012language,
  author = {Claudio Taranto and Nicola Di Mauro and Floriana Esposito},
  title = {{Language-Constraint Reachability Learning in Probabilistic Graphs}},
  year = {2012},
  eprint = {1205.5367},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1205.5367},
}
Figure