Leveraging Relational Autocorrelation with Latent Group Models

Jennifer Neville, David D. Jensen

TL;DR

This paper introduces Latent Group Models (LGMs) to better leverage autocorrelation in relational data by explicitly modeling hidden group structures that influence observed attributes and relationships. LGMs outperform existing methods, especially when initial information for inference is scarce, by providing a more principled way to model complex dependencies.

What Problem Does This Paper Address?

Relational data often exhibits autocorrelation, meaning related entities tend to have similar attributes or labels. While collective inference methods exploit this by reasoning over relationships, they often fail to capture a common underlying cause: the presence of latent groups or communities that influence these attributes. For instance, movies from the same studio are more likely to share similar success, not just because they are linked, but because the studio's unobserved properties (like marketing budget) influence them. Existing methods struggle to model these hidden structures, limiting their ability to fully exploit autocorrelation and understand the data.

Methods

The core contribution is the Latent Group Model (LGM), a generative probabilistic model that jointly models attributes, link structure, and latent group membership. LGMs assume that objects belong to groups, and these group memberships, along with group types, influence both the objects' attributes and the likelihood of links between them.

Key aspects of the LGM approach:

  • Generative Process: The model defines how data is generated, starting with group types, then assigning objects to groups, and finally generating attributes and links based on these group assignments.
  • Joint Modeling: Unlike methods that model attributes and links separately, LGMs integrate them, allowing for richer inference.
  • Approximate Learning: Due to the complexity of exact inference, an approximate learning algorithm is proposed. It first uses a spectral decomposition method to "hard cluster" objects into groups based on link structure alone. Then, an Expectation-Maximization (EM) algorithm is used to infer group types and estimate model parameters.
  • Inference: LGMs can be used for two main tasks: clustering objects into groups based on observed data, or inferring group memberships and unobserved attributes/links in new datasets with partial information.

Datasets

The paper evaluates LGMs on three real-world relational datasets:

  • Internet Movie Database (IMDb): A dataset of 1,382 movies (1996-2001) with links indicating common studios. The task was to predict movie opening weekend returns.
  • Cora: A dataset of 4,330 computer science research papers with links representing co-citation. The task was to predict paper topic (seven topics, including Neural Networks and Reinforcement Learning).
  • WebKB Project: A dataset of 3,877 web pages from four computer science departments, with links representing co-citation. The task was to predict page category (e.g., course, faculty, staff).

Key Insights and Ideas

  • Hidden groups are crucial: The paper strongly argues that explicitly modeling latent groups is essential for effectively leveraging relational autocorrelation, especially when initial information is limited.
  • Joint modeling unlocks power: By jointly modeling attributes and links, LGMs can capture more complex dependencies than methods that treat them separately.
  • Decoupling for tractability: The proposed approximate learning strategy, which separates group discovery from parameter estimation, makes learning feasible for complex relational data.
  • Group structure aids inference: LGMs can propagate information more effectively than methods relying solely on direct links, especially in sparse graphs, by leveraging group membership.

Key Results

  • Improved Accuracy: LGMs consistently outperform baseline models (Relational Probability Tree - RPT, Relational Bayesian Classifier - RBC, Relational Dependency Network - RDN) on the three classification tasks, particularly when the proportion of labeled instances used for inference is low.
  • Near Ceiling Performance: On IMDb and WebKB, LGMs quickly reach performance levels comparable to RDN-ceil (a theoretical upper bound using true labels), indicating their ability to effectively exploit group structure.
  • RBC Limitations: The RBC model, which uses cluster IDs as features, performs well when test instances link to training instances but drops to random performance when training and test sets are disjoint, highlighting the importance of generalization.
  • Subjective Evaluation (IMDb): Table 1 shows that LGMs can infer meaningful group types (e.g., high vs. low probability of high returns) and associate them with specific studios, demonstrating interpretability.

Limitations and Future Work

  • Clustering Quality: The paper notes that LGM performance in Cora was suboptimal, potentially due to the quality of clusters recovered from highly variable group sizes. Future work could involve iterating clustering and model estimation or using soft clustering.
  • Computational Complexity: While LGMs offer improvements, exact inference in complex graphical models remains challenging. The paper acknowledges the need for approximate inference techniques and suggests that future work could explore more efficient methods.
  • Active Inference: The authors suggest active inference as a promising direction, where the model intelligently chooses which instances to label to maximize the improvement in collective predictions.
  • Generalization: Further research is needed to explore the full applicability and power of LGMs, particularly in extending their capabilities beyond the current assumptions (e.g., unipartite graphs, binary links).

Summary updated

BibTeX
@inproceedings{neville2005leveraging,
  author = {Jennifer Neville and David D. Jensen},
  title = {{Leveraging Relational Autocorrelation with Latent Group Models}},
  booktitle = {ICDM},
  year = {2005},
  doi = {10.1109/icdm.2005.89},
}

Loading related content...

Figure