Source-linked AI summary
Bayesian graph convolutional neural networks for semi-supervised classification
Yingxue Zhang, Soumyasundar Pal, Mark Coates, Deniz Üstebay
TL;DR
GCNNs generally treat observed graph topology as ground truth, limiting their ability to represent uncertainty when graphs are noisy or miss relationships. The paper introduces Bayesian GCNNs that jointly infer random-graph parameters and labels, using an assortative mixed-membership block model, and reports better performance with few labels. Its scope is preliminary, covering one graph model and one graph-learning problem.
Problem
Existing GCNNs have limited ability to incorporate uncertainty in graph structure because they process observed topology as ground truth.
Method
The Bayesian GCNN framework models the observed graph through a parametric random graph family and performs approximate joint inference using an assortative mixed-membership stochastic block model.
Results
Bayesian GCNN improves classification particularly with very few labels and reduces prediction-accuracy losses under random node attacks compared with GCNN.
Takeaways & Limitations
The formulation can learn more from less data, represent uncertainty better, and improve robustness and resilience to graph noise or adversarial attacks.
Takeaways & Limitations
The investigation is preliminary and focuses on one graph model and one graph learning problem.
Abstract
from arXiv · showhide
Recently, techniques for applying convolutional neural networks to graph-structured data have emerged. Graph convolutional neural networks (GCNNs) have been used to address node and graph classification and matrix completion. Although the performance has been impressive, the current implementations have limited capability to incorporate uncertainty in the graph structure. Almost all GCNNs process a graph as though it is a ground-truth depiction of the relationship between nodes, but often the graphs employed in applications are themselves derived from noisy data or modelling assumptions. Spurious edges may be included; other edges may be missing between nodes that have very strong relationships. In this paper we adopt a Bayesian approach, viewing the observed graph as a realization from a parametric family of random graphs. We then target inference of the joint posterior of the random graph parameters and the node (or graph) labels. We present the Bayesian GCNN framework and develop an iterative learning procedure for the case of assortative mixed-membership stochastic block models. We present the results of experiments that demonstrate that the Bayesian formulation can provide better performance when there are very few labels available during the training process.
1 Introduction
The paper introduces Bayesian GCNNs to handle uncertainty in graph structure rather than treating observed topology as ground truth. It develops the framework for semi-supervised node classification using an assortative mixed-membership block model.
- Current GCNNs have limited ability to handle graph-structure uncertainty because they treat topology as ground-truth information.
- The Bayesian framework models the observed graph as a realization from a parametric random graph family and uses adjacency, features, and labels for joint inference.
- The formulation can learn more from less data, better represent uncertainty, and improve robustness, although it is computationally more demanding.
- The concrete framework targets semi-supervised node classification with an assortative mixed-membership stochastic block model.
2 Related work
Graph learning developed from recursive graph neural networks to convolutional architectures with spectral, spatial, attention, and architectural enhancements. The paper’s methodological novelty is treating the observed graph as data within a Bayesian inference framework.
- Early graph neural networks recursively process and propagate information across graphs, but training can converge slowly as graph size increases.
- GCNNs introduced spectral and spatial filtering strategies for learning from graph-structured data.
- Attention mechanisms, gates, edge conditioning, and skip connections have been explored to improve graph neural-network performance.
- Other approaches consider ensembles of graphs, multiple adjacency matrices, or dual graphs for graph learning.
- Unlike prior approaches, this paper adopts a Bayesian framework and treats the observed graph as additional data during inference.
3 Background
GCNNs propagate node features through graph-derived mixing operations and train weights against observed labels. The paper identifies a limitation of fixed topology and motivates Bayesian treatment of graph and neural-network uncertainty.
- The node-classification task uses graph structure, node features, and labels for a subset of nodes to infer labels across the graph.
- Standard GCNN layers mix transformed node features using a matrix derived from the observed graph.
- Weights, hidden features, activation functions, and final predictions are learned through neural-network training against observed labels.
- Existing GCNNs treat noisy graph topology as ground truth; attention can downweight existing edges but cannot create missing edges.
- Bayesian neural networks model weights as random variables, making predictions random and requiring approximate inference because posterior integration is generally intractable.
4 Methodology
The Bayesian GCNN jointly models graph uncertainty and neural-network predictions by inferring random-graph parameters and labels, then approximating predictions through sampled graphs and weights. The method uses an assortative mixed-membership stochastic block model with iterative, stochastic inference to make computation more tractable.
- Bayesian GCNN framework: The framework treats the observed graph as a realization from a parametric random-graph family and targets joint posterior inference over graph parameters, GCNN weights, and labels.Label posteriors are obtained by marginalizing over graph parameters and weights.
- Bayesian GCNN framework: Predictions are approximated by sampling graph parameters or using MAP estimates, generating graphs, sampling GCNN weights with Monte Carlo dropout, and averaging GCNN outputs.The implemented approximation samples graphs from p(G|π̂, β̂) and weights from the Bayesian GCNN over each sampled graph.
- Assortative MMSBM: The adopted assortative MMSBM represents each node with community-membership probabilities and assigns higher within-community link probabilities through community strengths βk.Nodes may belong to multiple communities, while cross-community links use a usually small probability δ.
- Assortative MMSBM: The joint posterior combines priors over β and π with the observed-graph likelihood, using Beta and Dirichlet priors for community strengths and memberships.The posterior is optimized under constraints on the membership and community-strength parameters.
- Stochastic inference: Full-batch posterior updates cost O(N 2K) per iteration, so the method exactly processes observed edges while subsampling 1 percent of non-edges and n nodes for φ updates.The resulting φ updates require O(n2K) operations instead of O(N 2K) for a full-batch update.
- Stochastic inference: Because random initialization often performs poorly in the high-dimensional MMSBM posterior, a GCNN softmax output initializes π and the block structure initializes β.The resulting initialization is incorporated into Algorithm 1 before alternating MMSBM inference and Bayesian-GCNN sampling.
5 Experimental Results
Experiments evaluate Bayesian GCNN against established graph neural network methods under limited-label classification and random graph perturbations. The Bayesian model improves accuracy and reduces variance on Cora and Citeseer in random splits, while its benefits depend on graph structure and are stronger under attack.
- Datasets and setup: Experiments use Cora, CiteSeer, and Pubmed citation datasets, where nodes are documents with bag-of-words features and topic labels.Edges represent citations, with direction ignored to form undirected graphs.
- Datasets and setup: The study compares Bayesian GCNN with ChebyNet, GCNN, and GAT using 20, 10, or 5 labels per class.Results are evaluated over fixed and randomly generated train-test splits.
- Semi-supervised node classification: Random splits improve classification accuracy for Bayesian GCNN on Cora and Citeseer, with larger gains when only 10 or 5 labels per class are available.Bayesian GCNN also produces lower variance in most tested scenarios.
- Semi-supervised node classification: Bayesian GCNN performs best on Pubmed with 5 labels per class but is outperformed at 10 and 20 labels because assortative MMSBM poorly matches Pubmed’s graph structure.Pubmed has lower intra-community density and a heavy-tailed degree distribution.
- Classification under node attacks: Random poisoning attacks remove and add neighbors around selected nodes, replacing half of Δ = d_v0 + 2 perturbations with cross-community edges.Each target receives five perturbed graphs, and attacks are evaluated on 40 correctly classified test nodes selected by classification margin.
- Classification under node attacks: Attacks reduce accuracy by 30% on Cora and 44.5% on Citeseer for GCNN, compared with 17% and 20.5% for Bayesian GCNN.On Citeseer, Bayesian GCNN’s classifier margin decreases 34% but remains positive on average, while GCNN’s margin is almost eliminated.
6 Conclusions and Future Work
The paper presents Bayesian graph convolutional neural networks for uncertain graph information and finds benefits for semi-supervised node classification, especially with few labels and under random edge attacks. This remains a preliminary investigation limited to one graph model and one graph-learning problem.
- 6 Conclusions and Future Work: Bayesian GCNNs incorporate uncertain graph information through a parametric random graph model.The framework combines stochastic optimization for random-graph parameters with approximate variational inference through Monte Carlo dropout.
- 6 Conclusions and Future Work: The methodology improved upon state-of-the-art techniques for semi-supervised node classification, particularly when training labels were scarce.
- 6 Conclusions and Future Work: Bayesian GCNNs appeared considerably more resilient than standard GCNNs under attacks that randomly changed a subset of node edges.
- 6 Conclusions and Future Work: The study focuses on one graph model and one graph-learning problem, with future work extending the approach to other models and tasks.