Statistical Relational Learning for Document Mining

Alexandrin Popescul, Lyle H. Ungar, Steve Lawrence, David M. Pennock

TL;DR

This paper introduces Structural Logistic Regression (SLR), a novel method for mining complex relational databases by integrating feature generation and statistical model selection. SLR significantly improves document classification accuracy by automatically discovering and utilizing rich, multi-relation features, outperforming traditional "flat" feature approaches.

What Problem Does This Paper Address?

Many real-world data mining tasks involve data stored in relational databases, which have complex interconnections rather than a simple, single-table structure. Traditional data mining algorithms often struggle with this complexity, assuming data is in a flat table format. This forces a manual and often incomplete process of feature engineering, where domain experts must manually craft features that capture relationships between different tables. This is a major bottleneck, as it's difficult to anticipate all potentially useful relational features, and the process is time-consuming and prone to missing crucial insights. The paper aims to bridge this gap by developing a method that can automatically learn from relational data, integrating the discovery of relevant features with the statistical modeling process.

Methods

The core of the paper is the Structural Logistic Regression (SLR) method. SLR combines two key components:

  • Relational Feature Generation: This process is framed as a search problem within the space of relational database queries. The authors adapt techniques from Inductive Logic Programming (ILP), specifically using a top-down search over "refinement graphs." Unlike traditional ILP which focuses on logic descriptions, SLR treats database queries as generators of data tables. These tables are then processed using aggregate operators (like size, average, min, max) to produce scalar, real-valued features. This allows for richer features than simple boolean indicators. The search is guided by the statistical model itself.
  • Statistical Model Selection: SLR uses logistic regression as its underlying statistical model. The model selection process is integrated directly into the feature generation search. Information criteria like AIC (Akaike Information Criterion) and BIC (Bayesian Information Criterion) are used to dynamically decide which generated features to include in the model. This integrated approach allows the model to make feature selection decisions in a step-wise manner, balancing model complexity with predictive power. The process involves a two-phase model selection: an inclusive pre-selection phase using AIC, followed by a more rigorous final selection using BIC.

Datasets

The primary dataset used for evaluation is CiteSeer. CiteSeer is an online digital library of computer science papers that contains rich relational data, including:

  • Citation information (links between documents)
  • Text of titles, abstracts, and full documents
  • Author names and affiliations
  • Conference and journal names

The authors represent this data in a relational format and use it to train and test their model for the task of classifying scientific papers into conference/journal categories. They define specific binary classification tasks by selecting pairs of conferences or journals and their immediate citation graph neighborhoods.

Key Insights and Ideas

  • Integrated Feature Generation and Model Selection: The most significant insight is the tight coupling of feature generation and model selection. Instead of a two-step process (generate features, then build a model), SLR dynamically drives feature generation based on the statistical model's criteria. This allows the model to "ask" for the most informative features.
  • Richer Features from Relational Data: By using aggregate operators on database queries, SLR can generate complex, real-valued features that capture nuanced relationships across multiple tables (e.g., the average count of a specific word in cited documents). This goes far beyond simple boolean features derived from single tables.
  • "Upgrades" vs. "Propositionalization": The paper positions SLR within the ILP "upgrades" paradigm, contrasting it with "propositionalization." Upgrades integrate learning and relational structure search, while propositionalization decouples them, often leading to difficulty in selecting useful features a priori.
  • Statistical Modeling for Noisy, Sparse Data: The authors highlight that relational data (like the Web or scientific publications) is often noisy and sparse. Statistical approaches like logistic regression are better suited to handle this uncertainty than deterministic methods.

Key Results

  • Improved Classification Accuracy: SLR consistently outperformed models using only "flat" features across all tested tasks. The average improvement was 3.3 percentage points, which was statistically significant at the 99% confidence level.
  • Specific Task Performance: For example, in the WWW-SIGMOD task, SLR achieved 79.3% test accuracy compared to 77.5% for flat features. In the AI-ML task, SLR achieved 82.2% versus 76.7% for flat features. (Refer to Table 2 for detailed results).
  • Feature Utility: Relational features based on word counts in cited documents and publication venues were commonly selected. Features involving specific cited documents or direct authorship were less frequent, suggesting their utility might be higher in domains with less textual information or in multilingual settings.

Limitations and Future Work

  • Search Space Size: The authors acknowledge that the search space for relational features can grow very rapidly, especially with more complex queries (e.g., involving quadratic numbers of features like co-authorship). They currently avoid these subspaces and suggest that intelligent search heuristics and sampling will be crucial for scaling to truly large problems.
  • Feature Subspace Exploration: While they use a breadth-first search, they note that more intelligent search strategies and heuristics are needed for larger domains.
  • Extending Relations: Future work includes exploring the use of clustering to generate new relations and features, which can help model sparse data and improve scalability.
  • Other Regression Models: The approach is easily extendable to other regression models beyond logistic regression.
  • Database Meta-Information: Leveraging database meta-information is suggested as a way to improve scaling.

Summary updated

Abstract

A major obstacle to fully integrated deployment of many data mining algorithms is the assumption that data sits in a single table, even though most real-world databases have complex relational structures. We propose an integrated approach to statistical modelling from relational databases. We structure the search space based on "refinement graphs", which are widely used in inductive logic programming for learning logic descriptions. The use of statistics allows us to extend the search space to include richer set of features, including many which are not Boolean. Search and model selection are integrated into a single process, allowing information criteria native to the statistical model, for example logistic regression, to make feature selection decisions in a step-wise manner. We present experimental results for the task of predicting where scientific papers will be published based on relational data taken from CiteSeer. Our approach results in classification accuracies superior to those achieved when using classical "flat" features. The resulting classifier can be used to recommend where to publish articles.
BibTeX
@inproceedings{popescul2003statistical,
  author = {Alexandrin Popescul and Lyle H. Ungar and Steve Lawrence and David M. Pennock},
  title = {{Statistical Relational Learning for Document Mining}},
  booktitle = {ICDM},
  year = {2003},
  doi = {10.1109/icdm.2003.1250930},
}

Loading related content...

Figure