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.
Methodology
The BPN framework operates in two distinct stages:
- 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.
- 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.
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