PaperlayerView exact revision on arXiv

Source-linked AI summary

GMNN: Graph Markov Neural Networks

Meng Qu, Yoshua Bengio, Jian Tang

arXiv:1905.06214v3cs.LGcs.SIstat.ML

TL;DR

Semi-supervised object classification asks how to infer labels for unlabeled nodes in attributed relational graphs when only a few labels are known. GMNN combines a conditional random field with two graph neural networks, and experiments across object classification, link classification, and unsupervised node representation learning report state-of-the-art or very competitive results.

  • Problem

    Semi-supervised object classification predicts labels for unlabeled objects from a few labeled objects, their attributes, and graph structure.

  • Method

    GMNN uses a conditional random field for joint label distributions, with one graph neural network for approximate inference and another for local label-dependency modeling.

  • Results

    GMNN achieves state-of-the-art results on object classification and unsupervised node representation learning, with very competitive results on link classification.

  • Takeaways & Limitations

    GMNN provides a general framework that combines relational label modeling with learned object representations across three graph-learning tasks.

  • Takeaways & Limitations

    Exact inference remains intractable because of complicated relational structures between object labels.

Abstract

from arXiv · show

This paper studies semi-supervised object classification in relational data, which is a fundamental problem in relational data modeling. The problem has been extensively studied in the literature of both statistical relational learning (e.g. relational Markov networks) and graph neural networks (e.g. graph convolutional networks). Statistical relational learning methods can effectively model the dependency of object labels through conditional random fields for collective classification, whereas graph neural networks learn effective object representations for classification through end-to-end training. In this paper, we propose the Graph Markov Neural Network (GMNN) that combines the advantages of both worlds. A GMNN models the joint distribution of object labels with a conditional random field, which can be effectively trained with the variational EM algorithm. In the E-step, one graph neural network learns effective object representations for approximating the posterior distributions of object labels. In the M-step, another graph neural network is used to model the local label dependency. Experiments on object classification, link classification, and unsupervised node representation learning show that GMNN achieves state-of-the-art results.

1. Introduction

Semi-supervised object classification infers labels for interconnected objects from a few labeled examples, drawing on both statistical relational learning and graph neural networks. GMNN combines conditional-random-field label modeling with graph-neural-network representations and achieves strong results across three tasks.

  • Motivation: Semi-supervised object classification infers labels for unlabeled interconnected objects using the labels of a few objects.The objects are also associated with attributes, and the task is a central problem in relational data modeling.
  • Motivation: Statistical relational learning models dependencies among object labels, whereas graph neural networks learn object representations through end-to-end training.The two approaches emphasize complementary aspects of relational classification.
  • GMNN: GMNN combines these approaches by modeling joint label distributions with a conditional random field and learning object representations with graph neural networks.Its training alternates variational-EM inference and learning procedures, with graph neural networks supporting both stages.
  • Results: GMNN applies to object classification, link classification, and unsupervised node representation learning.The paper reports state-of-the-art results on object classification and unsupervised node representation learning, with very competitive link-classification results.

2. Related Work

Related work spans statistical relational learning, graph-based semi-supervised classification, and graph neural networks. GMNN addresses limitations of these lines by using neural networks for both label inference and dependency modeling.

  • Statistical Relational Learning: Statistical relational learning models label dependencies with probabilistic graphical models, but many methods require hand-crafted features and face difficult inference.Earlier directed models also handle only acyclic dependencies and often have limited prediction performance.
  • Graph-based Semi-supervised Classification: Label propagation methods iteratively spread labels through neighboring objects but model only linear label dependencies.GMNN instead uses a nonlinear graph neural network and also learns object representations for prediction.
  • Graph Neural Networks: Graph neural networks encode local graph structures and object attributes into useful representations through end-to-end training.This representation-learning focus differs from explicitly modeling the joint dependency of object labels.
  • GNN for PGM Inference: Compared with prior GNN-based probabilistic-graphical-model inference, GMNN uses two graph neural networks for inference and learning rather than one for inference.The prior work emphasizes standard graphical models, whereas GMNN focuses on statistical relational learning.

3. Problem Definition & Preliminary

The paper formalizes semi-supervised classification on an attributed graph and reviews conditional-random-field and graph-neural-network formulations. CRFs model label dependencies but make inference difficult, while GNNs learn object representations with factorized predictions.

  • 3.1. Problem Definition: The task is to predict labels yU for unlabeled objects U from labels yL of a few labeled objects, graph edges E, and object attributes xV.The formulation assumes a single edge type for simplicity, although edges may generally have multiple types.
  • 3.2. Statistical Relational Learning: Statistical relational learning models the conditional joint label distribution with a conditional random field whose edge potentials capture label dependencies.Potential scores are typically linear combinations of hand-crafted feature functions.
  • 3.2. Statistical Relational Learning: Exact posterior inference for unlabeled labels is usually infeasible because relational structures create complicated dependencies.Approximate methods such as loopy belief propagation are therefore used.
  • 3.3. Graph Neural Network: Graph neural networks factorize label distributions across objects and learn representations by repeatedly aggregating neighboring representations.The final representations are passed to a linear softmax classifier for label prediction.
  • 3.3. Graph Neural Network: Figure 1 depicts labeled and unlabeled objects, attributes, label distributions, and object representations within GMNN’s alternating E-step and M-step training framework.The overview uses distinct colors and shapes for these components.

4. GMNN: Graph Markov Neural Network

GMNN combines a conditional random field with two graph neural networks, using variational EM to learn representations and local label dependencies for semi-supervised classification.

  • 4.1. Pseudolikelihood Variational EM: GMNN models the joint distribution of object labels conditioned on attributes with a conditional random field optimized using pseudolikelihood variational EM.The variational E-step updates qθ, while the M-step updates pφ.
  • 4.2. Inference: Exact posterior inference is intractable because of the complicated relational structures between object labels.
  • 4.2. Inference: The inference network qθ uses a mean-field variational distribution and a graph neural network to learn object representations from attributes and local connections.All object labels are assumed independent in qθ, and a shared GNN reduces the number of inference parameters.
  • 4.3. Learning: The M-step models pφ(yn|yNB(n), xV ) with a second nonlinear GNN whose softmax classifier uses representations informed by neighboring labels.This models local label dependencies without requiring hand-crafted feature functions.
  • 4.3. Learning: Unlike label propagation, GMNN models label dependency with a learnable nonlinear GNN rather than a fixed linear propagation rule.
  • Optimization Algorithm: GMNN alternates between labeling unlabeled objects with qθ to update pφ and using pφ to update qθ until convergence.The final unlabeled-object predictions are based on qθ(yn|xV ).

5. Application

GMNN extends beyond semi-supervised object classification to unsupervised node representation learning and link classification through task-specific reformulations.

  • Unsupervised Node Representation Learning: GMNN supports unsupervised node representation learning by treating each node’s neighbors as pseudo labels when no labeled nodes are available.
  • Unsupervised Node Representation Learning: The pφ model regularizes qθ by encouraging locally smooth inferred neighbor distributions during unsupervised representation learning.
  • Link Classification: GMNN can be applied to link classification given labels for only some links, with the remaining links treated as objects to classify.
  • Link Classification: Link classification is reformulated as object classification on a line graph whose objects correspond to original-graph links.Line-graph objects are connected when their corresponding original links share a node.

6. Experiment

GMNN is evaluated on object classification, unsupervised node representation learning, and link classification against GNN, SRL, and semi-supervised baselines. It reports strong results across tasks and analyzes amortized inference, learning-network design, and convergence.

  • Evaluation setup: GMNN is evaluated on object classification, unsupervised node representation learning, and link classification using benchmark graph datasets.Object classification uses Cora, Citeseer, and Pubmed; link classification uses Bitcoin Alpha and Bitcoin OTC.
  • Compared algorithms: The comparison includes GCN, GAT, Deep Graph Infomax, probabilistic relational models, RMN, MLN, and label propagation.GAT results are unavailable for the link-classification datasets because it cannot scale to both datasets.
  • Object classification: GMNN significantly outperforms SRL, label propagation, and GCN on object classification, while remaining close to GAT.The authors attribute gains over GCN primarily to GMNN’s ability to model label dependencies; incorporating object attributes into the learning network further improves performance.
  • Unsupervised node representation learning: GMNN achieves state-of-the-art results on Cora and Pubmed for unsupervised node representation learning.Removing the pφ network causes a significant performance drop, supporting its role as a regularizer over neighbor distributions.
  • Amortized inference: Amortized inference substantially improves performance over non-amortized inference, with graph-convolutional layers adding gains by incorporating neighboring attributes.The non-amortized variant performs poorly, a one-layer neural variant improves results, and several graph-convolutional layers improve them further.
  • Convergence analysis: GMNN converges in only a few variational-EM iterations on the Cora and Citeseer object-classification analyses.The convergence analysis tracks validation accuracy for both qθ and pφ, with iteration 0 representing pre-training.

7. Conclusion

GMNN addresses semi-supervised object classification by combining a conditional random field with two graph neural networks and variational inference. Experiments across three tasks support its effectiveness, while future work targets graphs with multiple edge types.

  • GMNN models the joint distribution of object labels with a conditional random field and uses two graph neural networks to improve inference and learning.
  • Experiments on object classification, link classification, and unsupervised node representation learning support GMNN’s effectiveness.
  • Future work aims to extend GMNN to graphs with multiple edge types, such as knowledge graphs.
  • The variational objective minimizes the KL divergence between the approximate distribution qθ(yU) and the conditional distribution pφ(yU|yL).
  • The local variational optimum q∗(yn|xV) is characterized through a normalized distribution F(yn), using Markov-network conditional independence.

B.1. Results on Random Data Splits

On random data splits, GMNN is evaluated against GCN and GAT using repeated runs and consistently outperforms both baselines across all datasets.

  • GMNN is evaluated on 10 random data splits per dataset, with training, validation, and test sizes matching Yang et al. (2016).
  • For each split, GMNN, GCN, and GAT are run with 10 different seeds, and overall mean accuracy is reported in Table 7.
  • GMNN consistently outperforms GCN and GAT on all datasets in the random-split evaluation.

B.2. Results on Few-shot Learning Settings

In few-shot learning, GMNN is tested under greater label sparsity than the semi-supervised setting and significantly outperforms GCN and GAT, with a larger improvement.

  • Each dataset uses 5 labeled nodes per class for training, and each method is run with 100 different seeds.
  • GMNN significantly outperforms GCN and GAT in the few-shot learning evaluation.
  • GMNN’s improvement is larger than in the semi-supervised setting, which uses 20 labeled nodes per class.
  • The few-shot results are presented as mean accuracy in Table 8.

B.3. Comparison with Self-training Methods

GMNN is compared with self-training for semi-supervised object classification and consistently performs better. The paper attributes this to complementary information from its two networks.

  • GMNN’s pφ network annotates unlabeled objects, which are treated as additional data for updating qθ through Eq. (10).
  • The comparison with self-training for semi-supervised object classification is reported in Table 9.
  • GMNN consistently outperforms self-training because qθ and pφ capture complementary information rather than sharing one network for inference and annotation.

B.4. Comparison of Different Approximation Methods

GMNN estimates the mean-field expectation over unlabeled neighbors using several approximation strategies. Among the compared methods, annealing consistently performs best across datasets and is used throughout the paper.

  • The mean-field expectation over unlabeled neighbors factorizes into individual posterior label distributions, enabling empirical approximation methods.
  • Approximation methods: Single-sample estimation draws one label sample for each unlabeled neighbor to approximate the expectation.
  • Approximation methods: Multiple-sample estimation lowers variance but increases computational cost compared with single-sample estimation.
  • Approximation methods: Annealing introduces τ into the posterior, with τ=0.1 producing typically lower-variance samples for expectation estimation.
  • Approximation methods: Max pooling uses each neighbor's most probable label, whereas mean pooling supplies soft label vectors to a graph neural network.
  • Comparison: Annealing consistently outperforms the other approximation methods on all datasets and is therefore used in all experiments.

B.5. Best Results with Standard Deviation

GMNN's best semi-supervised object-classification accuracy is reported with standard deviations over 100 runs, and its improvement over GAT is statistically significant.

  • GMNN's best mean accuracy and standard deviation are reported over 100 runs, with improvement over GAT statistically significant.
Loading 1905.06214v3…