Belief Propagation Network for Hard Inductive Semi-Supervised Learning

Jaemin Yoo, Hyunsik Jeon, U Kang

Introduction

Graph-based semi-supervised learning (SSL) has traditionally focused on transductive or "soft inductive" settings. In these scenarios, test nodes are either present during training or arrive with a set of existing neighbors. However, real-world applications frequently encounter the hard inductive challenge: classifying new, isolated data points that lack any neighborhood information (e.g., a new user with no friends or a new paper with no citations). Standard Graph Neural Networks (GNNs) like GCN or GAT struggle in this setting because they are fundamentally dependent on neighborhood feature aggregation.

The Belief Propagation Network (BPN)

The Belief Propagation Network (BPN) addresses this limitation by decoupling feature-based classification from graph-based diffusion. Unlike GNNs that fuse these processes into a single architecture, BPN treats the graph as a teacher during training rather than a crutch during inference.

The BPN training and inference pipeline. The left panel shows the diffusion process, while the right panel illustrates the update mechanism using classification and induction losses.

Methodology

The BPN framework operates in two distinct stages:

  1. Prior Computation: A differentiable classifier $f$ (e.g., an MLP) processes a node's features to generate a "prior" distribution $\phi$. This represents the model's best guess based solely on local features.
  2. Diffusion Step: These priors are refined through the graph using Loopy Belief Propagation (LBP). This non-parametric step uses the graph structure to produce "beliefs" $b^*$, which are consistent with the neighborhood's labels.

Training with Induction Loss

To bridge the gap between feature-only priors and graph-aware beliefs, BPN employs a composite loss function:

  • Classification Loss ($l_c$): Standard cross-entropy ensuring final beliefs match ground-truth labels for labeled nodes.
  • Induction Loss ($l_d$): The core innovation of BPN. It minimizes the KL divergence between the feature-only priors and the graph-refined beliefs for unlabeled nodes.

By minimizing $l_d$, the classifier $f$ learns to internalize the structural information of the graph. Consequently, at test time, the graph can be discarded, and $f$ can accurately classify isolated nodes.

Experimental Evaluation

The authors evaluated BPN on citation networks (Pubmed, Cora, Citeseer) and an Amazon e-commerce dataset. To simulate the hard inductive setting, all neighborhood information was removed for test nodes.

Performance and Efficiency

BPN consistently outperformed state-of-the-art baselines, including GAT and SEANO, achieving an average accuracy improvement of 2.4 percentage points. Beyond accuracy, BPN demonstrates remarkable computational efficiency.

Average training time (seconds) across four benchmark datasets. BPN (ours) is significantly faster than traditional GNN baselines.

As shown in the figure above, BPN trains up to 150x faster than GAT. This speedup stems from the use of fixed, non-parametric diffusion (LBP), which simplifies the backpropagation process compared to GNNs that must learn complex aggregation weights.

Conclusion

BPN offers a robust solution for hard inductive SSL by using the graph as a regularizer rather than a structural dependency. This decoupling not only enables the classification of isolated nodes but also provides significant gains in training speed and model interpretability. Future work will explore extending BPN to heterogeneous and edge-attributed networks.

Summary updated

Abstract

Given graph-structured data, how can we train a robust classifier in a semi-supervised setting that performs well without neighborhood information? In this work, we propose belief propagation networks (BPN), a novel approach to train a deep neural network in a hard inductive setting, where the test data are given without neighborhood information. BPN uses a differentiable classifier to compute the prior distributions of nodes, and then diffuses the priors through the graphical structure, independently from the prior computation. This separable structure improves the generalization performance of BPN for isolated test instances, compared with previous approaches that jointly use the feature and neighborhood without distinction. As a result, BPN outperforms state-of-the-art methods in four datasets with an average margin of 2.4% points in accuracy.
BibTeX
@inproceedings{yoo2019belief,
  author = {Jaemin Yoo and Hyunsik Jeon and U Kang},
  title = {{Belief Propagation Network for Hard Inductive Semi-Supervised Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/580},
}
Figure