Markov Process-Based Graph Convolutional Networks for Entity Classification in Knowledge Graphs

Johannes Mäkelburg, Yiwen Peng, Mehwish Alam, Tobias Weller, Maribel AcostaarXiv 2024 · arXiv

TL;DR

This paper introduces MPERL, a novel Graph Convolutional Network (GCN) framework that dynamically adjusts its computational budget—a concept known as "pondering"—based on the complexity of the entity being classified in a Knowledge Graph. By embedding GCNs within a Markov process and utilizing evidential learning instead of standard softmax, MPERL improves classification accuracy while avoiding overconfident predictions.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful tools for organizing structured data, but they are notoriously incomplete. A major challenge is entity classification: determining the class or type affiliation of an entity (e.g., predicting that a specific node represents a "Company" or an "Artist").

While Graph Convolutional Networks (GCNs) are highly effective at this task, standard architectures suffer from a fundamental limitation: their computational cost scales with the size of the input data, not the complexity of the problem. A simple entity with clear-cut relationships requires the same number of layers and steps as an ambiguous entity buried in a noisy neighborhood. Furthermore, standard GCNs rely on the softmax function, which often yields overconfident, misleading probability distributions when faced with uncertainty.

Methods

The authors propose MPERL (Markov Process and Evidential with Regularization Loss), an end-to-end architecture that tackles these issues through two main innovations:

  1. Markov Process-Based Pondering: MPERL embeds a relational GCN (R-GCN) within a Markov process consisting of two states: continue and halt. At each step, the model decides whether to perform another computational step or stop. The halting probability is modeled using a generalized geometric distribution. This allows the network to dynamically choose the optimal number of "pondering" steps for each entity.
  2. Evidential Learning with Dirichlet Priors: Instead of using a standard softmax layer for final classification, MPERL aggregates the hidden features across all Markov steps and uses them to parameterize a Dirichlet distribution. This approach treats predictions as a distribution over probability distributions, allowing the model to explicitly capture both aleatoric (data) and epistemic (knowledge) uncertainty.

The overall architecture is optimized using a dual-component loss function: an evidential loss ($L_{Ev}$) to fit predictions to ground truth, and a regularization loss ($L_{Reg}$) to penalize excessive computational steps.

Overview of the MPERL architecture showing the integration of GCNs, the Markov process, and the Dirichlet distribution.

Datasets

The model was evaluated across two distinct settings:

  • Small Datasets (Single-label classification): AIFB, MUTAG, BGS, and AM. In these benchmarks, each entity belongs to exactly one class.
  • Large Datasets (Multi-label classification): FB15kET and YAGO43kET. These represent real-world, large-scale KGs where entities can belong to multiple classes simultaneously.

Key Insights and Ideas

  • Synergy of Pondering and Feature Aggregation: Unlike previous pondering models that only use the final step's output, MPERL takes a weighted average of hidden features across all steps. This reduces sensitivity to "noisy" graph neighbors because well-fitting intermediate representations are preserved.
  • Faster Convergence: Reusing the hidden features ($h_{n-1}$) from the previous Markov step as an input to the next step acts as a strong inductive bias, leading to faster training convergence over epochs.
  • Softmax Alternatives Matter: Moving away from standard point-estimators (like softmax) to conjugate priors (like Dirichlet distributions) allows the model to better handle out-of-distribution data and irregular graph structures without making overconfident errors.

Key Results

MPERL was compared against standard GNN baselines (R-GCN, CompGCN) and embedding-based methods (RDF2Vec, ConnectE, ASSET).

  • Small Datasets: MPERL consistently outperformed all baselines. For instance, on the AIFB dataset, it achieved an accuracy of 97.22% and an F1-Macro score of 96.13%, significantly beating vanilla R-GCN (92.22% accuracy).
  • Large Datasets: On FB15kET, MPERL achieved competitive results, notably outperforming all baselines on the Hit@1 metric (58.18%), proving its high accuracy for top-1 missing type predictions.
  • The Hyperparameter Effect: The authors found that setting the geometric distribution prior ($\lambda_p$) to 0.2 (equivalent to an expected 5 Markov steps) provides the best trade-off between classification accuracy and computational efficiency.

Limitations and Future Work

While MPERL excels on smaller and moderately sized graphs, it faces scalability challenges on massive, highly dense graphs. On the YAGO43kET dataset, which features high-degree "hub" entities and over 45,000 classes, MPERL's performance degraded. Due to GPU memory constraints, the authors had to restrict the maximum Markov steps to 2 and implement neighborhood sampling, which likely discarded important structural context.

Future Directions: * Developing an automated approach to dynamically select the optimal $\lambda_p$ hyperparameter. * Replacing the Dirichlet distribution with a Beta distribution to better scale and handle multi-label classification settings. * Introducing a gated unit to automatically learn the optimal weights when combining hidden representations from sequential Markov steps.

Summary updated

Abstract

Despite the vast amount of information encoded in Knowledge Graphs (KGs), information about the class affiliation of entities remains often incomplete. Graph Convolutional Networks (GCNs) have been shown to be effective predictors of complete information about the class affiliation of entities in KGs. However, these models do not learn the class affiliation of entities in KGs incorporating the complexity of the task, which negatively affects the models prediction capabilities. To address this problem, we introduce a Markov process-based architecture into well-known GCN architectures. This end-to-end network learns the prediction of class affiliation of entities in KGs within a Markov process. The number of computational steps is learned during training using a geometric distribution. At the same time, the loss function combines insights from the field of evidential learning. The experiments show a performance improvement over existing models in several studied architectures and datasets. Based on the chosen hyperparameters for the geometric distribution, the expected number of computation steps can be adjusted to improve efficiency and accuracy during training.
BibTeX
@misc{makelburg2024markov,
  author = {Johannes Mäkelburg and Yiwen Peng and Mehwish Alam and Tobias Weller and Maribel Acosta},
  title = {{Markov Process-Based Graph Convolutional Networks for Entity Classification in Knowledge Graphs}},
  year = {2024},
  eprint = {2412.17438},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.17438},
}
Figure