# Graph Neural Networks Intersect Probabilistic Graphical Models:
A Survey

Chenqing Hua  Sitao Luan  Qian Zhang  Jie Fu

###### Abstract

Graphs are a powerful data structure to represent relational data and are
widely used to describe complex real-world data structures. Probabilistic
Graphical Models (PGMs) have been well-developed in the past years to
mathematically model real-world scenarios in compact graphical representations
of distributions of variables. Graph Neural Networks (GNNs) are new inference
methods developed in recent years and are attracting growing attention due to
their effectiveness and flexibility in solving inference and learning problems
over graph-structured data. These two powerful approaches have different
advantages in capturing relations from observations and how they conduct
message passing, and they can benefit each other in various tasks. In this
survey, we broadly study the intersection of GNNs and PGMs. Specifically, we
first discuss how GNNs can benefit from learning structured representations in
PGMs, generate explainable predictions by PGMs, and how PGMs can infer object
relationships. Then we discuss how GNNs are implemented in PGMs for more
efficient inference and structure learning. In the end, we summarize the
benchmark datasets used in recent studies and discuss promising future
directions.

##  1 Introduction

Graphs are expressive to represent objects and their relations with node and
edge representations. Graph Neural Networks (GNNs) (Kipf & Welling, 2016;
Velickovic et al., 2017; Hamilton et al., 2017; Luan et al., 2020, 2021; Hua
et al., 2022; Luan et al., 2022) and Probabilistic Graphical Models (PGMs)
(Koller & Friedman, 2009) are two different powerful tools for learning graph
representations and both have been successfully developed to address practical
issues when it comes to graph-structured applications. GNNs are deep learning
architectures that are specifically designed for relational data, which are a
generalization of message-passing neural networks (Gilmer et al., 2017) for
data in non-Euclidean domain. PGMs are mathematically and statistically
interpretable models which can express the conditional dependence structure
between random variables (Qu et al., 2019, 2021). GNNs and PGMs are capable of
conducting accurate and fast inferences on graphs but the major differences
between them are how they process relational variables and how they conduct
message passing in the models, which are shown in Figure 1 and 2.

Figure 1: Visualization of relationships between probabilistic graphical
models and graph neural networks. The blue circle concludes the properties of
GNNs, the red circle shows the properties of PGMs, and the intersection area
shows the shared properties of the two powerful graph learning tools Figure 2:
Illustration of one connection between probabilistic graphical models and
graph neural networks on identifying node types, i.e., exact inference for
PGMs or node classification for GNNs. The PGM model executes the belief
propagation algorithm on passing messages between nodes and the GNN model
executes the message passing algorithm to pass node information to the
neighbors. The two powerful algorithms result in different predictions due to
their unique message-passing mechanisms.

Figure 1 summarizes the common and distinct properties of GNNs and PGMs, e.g.,
GNNs produce richer representations because they project features onto an
informative embedding space while PGMs generate more concrete representations
because they always model the relationships between input data and output
representations. Figure 2 demonstrates how GNNs and PGMs perform differently
when they conduct message passing/belief propagation on a node
classification/exact inference task. Generally speaking, the two methods have
some unique advantages, and the similarities allow the two models to be
incorporated together for more efficient and effective algorithms. We
summarize five main directions where they can benefit each other.

PGMs Benefit GNNs

The first direction of GNNs is to achieve structured representations and
predictions via Conditional Random Fields (CRF). The problem arises because
most GNNs hold a strong assumption for which the node representations and
labels are independent when node features and edges are observed (Qu et al.,
2021), while PGMs always try to model the relationships between input data and
output representations (Qu et al., 2019). It is argued that the dependence
between input data and output predictions should not be ignored in a GNN (Gao
et al., 2019; Qu et al., 2019, 2021). To achieve structured predictions, GNNs
can adopt CRFs in PGMs, which can further address the independence issue. We
will discuss CRFs enhanced GNNs that model the dependence between node input
representations and embeddings in Section 4.1.

More than achieving structured representations and predictions for GNNs
through CRFs, the second direction is that other PGM methods can be mixed with
GNNs for bette classification results in terms of the algorithm accuracy and
efficiency. We will discuss other PGM refinement methods in Section 4.2.

The second direction is the explainability of GNNs. Since complex graph
structures and node features always lead to complex composite of GNN
architectures, GNN predictions cannot be often easily explained (Ying et al.,
2019). However, we usually desire to give reasonable explanations to those
hard predictions (Ying et al., 2019; Yuan et al., 2020). And white-box PGMs
can provide an opportunity to generate reasonable graphical explanations for
those predictions. We will discuss PGMs for explainable GNNs in Section 4.3.

The third direction is graph structure learning for GNNs. The question comes
when people demand well-defined graph structures for GNNs to perform various
tasks but the structures are not well-defined. Graph structure learning is
always important when the input graph structure is noisy or sometimes missing
(Kipf et al., 2018; Zhu et al., 2021), the relations are not well-defined, the
edges do not reflect exact relationships (Wang et al., 2020). PGMs can
effectively model and infer object relationships from observed variables based
on pairwise object similarities or the potential that an edge would appear
between two objects so that they can assist GNNs to learn graph structures. We
will discuss PGMs enhanced graph structure learning in Section 4.4.

GNNs Benefit PGMs

The first direction is that GNNs can help PGMs for better inference through
more efficient message-passing algorithms. As illustrated in figure 2, both
PGMs and GNNs conduct message-passing when aggregating information in a
neighborhood. However, Loopy Belief Propagation (LBP) algorithm (Murphy et
al., 2013) is relatively slower than message passing used in GNNs and will
normally fail on real-world loopy networks (Murphy et al., 2013; Yoon et al.,
2019). Message passing algorithm used in GNNs can be adopted to improve LBP in
terms of efficiency and accuracy. We will discuss this direction in Section
5.1.

The second direction is that GNNs can benefit Directed Acyclic Graphs (DAG)
learning for PGMs. Learning a DAG from observed variables is always expensive
and is an extremely challenging NP-hard problem (Chickering, 1996).
Nevertheless, GNNs can be implemented to intermediately enhance DAG learning
due to their capability of capturing nonlinear relationships. We will discuss
GNNs enhanced DAG learning in Section 5.2.

In a nutshell, PGMs can be used to improve the prediction performance,
explainability and structure learning ability of GNNs; GNNs can be implemented
to enhance PGMs for inference and DAG learning. There is no existing
literature reviewing the intersection of GNNs and PGMs. Therefore, in this
survey, we formulate the current limitations of GNNs and PGMs that can
potentially be addressed by combining each other. This paper is organized as
follows: we introduce related background knowledge in Section 2 and 3; we
discuss applications of PGMs used in GNNs in Section 4 and discuss
applications of GNNs used in PGMs in Section 5; a comprehensive list of
benchmark datasets is summarized by category in Section 6; in Section 7, we
outline the challenges and potential research directions for future studies.

##  2 Preliminaries

#### Notations

We use bold font letters for vectors (e.g., $\mathbf{x}$), capital letters
(e.g., $\mathbf{X}$) for matrices, and regular ones for nodes and edges (e.g.,
$v,e$). Let ${G}=(V,{E})$ be an undirected, unweighted graph where
$V=\\{v_{1},...,v_{n}\\}$ is the node set and $E\in{V\times V}$ is the edge
set, $v_{i}\in V$ to denote the a node and $e_{ij}\in E$ to denote an edge
associated with nodes $v_{i},v_{j}$. The neighborhood of a node $v$ is defined
as $N(v)=\\{u\in V\ |\ e_{vu}\in E\\}$. The adjacency matrix $A$ is a $N\times
N$ matrix with $A_{ij}=1$ if $e_{ij}\in E$ and $A_{ij}=0$ otherwise.
$\mathbf{X}\in\mathbb{R}^{n\times F}$ denotes the node feature matrix, where
$\mathbf{x}_{i}\in\mathbb{R}^{F}$ corresponds to the feature of node $v_{i}$.
Each node $v_{i}$ is associated with a discrete label or a continuous value
$\mathbf{y}_{v_{i}}$.

#### Graph Neural Networks

Graph Neural Networks (GNN) can learn rich node representations on large-scale
networks and achieve state-of-the-art results in node classification and edge
prediction, so they have gradually become an important tool of conducting
network analysis and related tasks. Message-passing GNNs iteratively update
node representations in a learning task. Given the input of the first layer
$\mathbf{H}^{(0)}=\mathbf{X}$, the learned node hidden representations at each
$l$-th layer of a GNN can be denoted as
$\mathbf{H}^{(l)}=[\mathbf{h}^{(l)}_{v}]_{v\in V}$, and the node
representations $\mathbf{H}^{(L)}$ from the last GNN layer $L$ can be fed into
a classifier network for predicting classes or relevant properties. For graph
classification, an additional $\mbox{READOUT}(\cdot)$ function aggregates node
representations from the final layer to obtain a graph representation
$\mathbf{h}_{G}$ of graph $G$ as,

$\mathbf{h}_{G}=\mbox{READOUT}(\mathbf{H}^{(L)}),$

where $\mbox{READOUT}(\cdot)$ can be be a simple permutation invariant
function (e.g., sum, mean, max pooling, etc.).

#### Message Passing in Graph Neural Networks

GNNs encode node features along with local graph structures through a message-
passing mechanism, by iteratively propagating the messages from local neighbor
representations, and then combining the aggregated messages with node
themselves (Hamilton, 2020). Formally, at the $l$-th layer of a GNN, the
message-passing mechanism follows:

$\displaystyle\mathbf{m}^{(l)}_{v}$
$\displaystyle=\mbox{AGGREGATE}^{(l)}(\\{\mathbf{h}^{(l-1)}_{u},\forall u\in
N(v)\\}),$ (1) $\displaystyle\mathbf{h}_{v}^{(l)}$
$\displaystyle=\mbox{UPDATE}^{(l)}(\mathbf{h}^{(l-1)}_{v},\mathbf{m}^{(l)}_{v}),$

where $\mbox{AGGREGATE}^{(l)}(\cdot)$ and $\mbox{UPDATE}^{(l)}(\cdot)$ are
permutation invariant aggregation function (e.g., mean, sum, max pooling) and
update funtion (e.g., linear-layer combination). In words,
$\mbox{AGGREGATE}^{(l)}(\cdot)$ first aggregates information from ${N}(v)$,
then $\mbox{UPDATE}^{(l)}(\cdot)$ combines the aggregated neighborhood message
$\mathbf{m}^{(l)}_{v}$ and previous node representation to give a new
representation $\mathbf{h}^{(l)}_{v}$.

#### Bayesian Networks

Probabilistic Graphical Models (PGM) simplify a joint probability distribution
$p(\mathbf{x})$ over many variables $\mathbf{x}$ by factorizing the
distribution according to conditional independence relationships. A Bayesian
Network (BN) is a probabilistic graphical model (PGM) that measures the
conditional dependence structure of a set of random variables. A structure of
a BN takes the form of a Directed Acyclic Graph (DAG) where the loopy
structure is not allowed.

#### Markov Random Fields

Markov Random Fields (MRF) or Undirected Probabilistic Graphical Models (uPGM)
are undirected graphs $G$ equipped with a Markov property, that is, a node $v$
is independent of $u$ conditioned on $v$’s neighbors, $N(v)$, implying that
knowing the distribution on values is sufficient and the node $v$ can be
ignorant of anywhere else in the network. A Conditional Random Field (CRF) is
a MRF globally conditioned on nodes $V$ and node features $\mathbf{X}$, which
is powerful to model the pair-wise node relationships. A pair-wise CRF that
formalizes the joint label distribution follows:

$\displaystyle p(\mathbf{Y}\ |\
\mathbf{X},E)=\frac{1}{Z_{\phi}(\mathbf{X},E)}$ $\displaystyle\mbox{exp}\
\\{\sum_{v\in V}\phi_{v}(\mathbf{y}_{v},\mathbf{X},E)$ (2)
$\displaystyle+\sum_{e_{vu}\in
E}\phi_{vu}(\mathbf{y}_{v},\mathbf{y}_{u},\mathbf{X},E)\\},$

where $Z_{\phi}(\mathbf{X},E)$ is the partition function that ensures the
factorization $p(\mathbf{Y}\ |\ \mathbf{X},E)$ sum to $1$,
$\phi_{v}(\mathbf{y}_{v},\mathbf{X},E)$ and
$\phi_{vu}(\mathbf{y}_{v},\mathbf{y}_{u},\mathbf{X},E)$ are unary and pair-
wise potential functions defined on each node $v$ and each edge $e_{vu}$,
respectively. The unary function gives the prediction for each individual data
point. The pairwise energy function aims to capture the correlation between
the individual data point and its context to regularize the unary function.
CRFs are able to model the joint dependence of node labels through pair-wise
potential function $\phi_{vu}(\mathbf{y}_{v},\mathbf{y}_{u},\mathbf{X},E)$.

#### Message Passing in Markov Random Fields

(Sum-Product) Loopy Belief Propagation algorithm (LBP) (Murphy et al., 2013)
is a dynamic programming approach to pass information between nodes for
answering conditional probability queries in probabilistic graphical models.
For each edge $e_{vu}\in E$, a message
$\mathbf{m}_{{u}\rightarrow{v}}(\mathbf{y}_{v})$, representing a message of
node $u$ sending to node $v$, is to repeat the following procedure until
convergence or after sufficient iterations:

$\displaystyle\mathbf{m}_{{u}\rightarrow{v}}(\mathbf{y}_{{v}})\propto$
$\displaystyle\sum_{\mathbf{y}_{{u}}}\\{\mbox{exp}\
(\phi_{{v}}(\mathbf{y}_{{v}},E)+\phi_{{v}{u}}(\mathbf{y}_{{v}},\mathbf{y}_{{u}},E))$
(3) $\displaystyle\prod_{{v}^{\prime}\in
N({u})/{v}}\mathbf{m}_{{v^{\prime}}\rightarrow{u}}(\mathbf{y}_{{u}})\\}.$

Moreover, the (Max-Product) Loopy Belief Propagation algorithm follows:

$\displaystyle\mathbf{m}_{{u}\rightarrow{v}}(\mathbf{y}_{{v}})\propto$
$\displaystyle\underset{{\mathbf{y}_{{u}}}}{\mbox{max}}\\{\mbox{exp}\
(\phi_{{v}}(\mathbf{y}_{{v}},E)+\phi_{{v}{u}}(\mathbf{y}_{{v}},\mathbf{y}_{{u}},E))$
(4) $\displaystyle\prod_{{v}^{\prime}\in
N({u})/{v}}\mathbf{m}_{{v^{\prime}}\rightarrow{u}}(\mathbf{y}_{{u}})\\}.$

The message $\mathbf{m}_{{u}\rightarrow{v}}(\mathbf{y}_{v})$ can be derived by
simply multiplying the following items: messages of node $u$’s neighbors
(except node $v$) sending to $u$, the unitary potential of node $v$, and the
pair-wise potential of edge $e_{vu}$.

##  3 Tasks

In this section, we introduce the main learning tasks for GNNs and PGMs that
are studied in this survey. For GNN-related tasks, we have four main
categories including structured prediction for node and graph classification,
GNN explanation, graph structure learning; and for PGM-related tasks, we have
two main categories including exact inference and DAG learning. For each
category and task, we summarize the representative models in Table 1, and
introduce the relevant datasets in Table 2.

###  3.1 Graph Neural Network Tasks

We discuss how PGMs can be applied in GNNs in Section 4.

#### (Semi-supervised) Node Classification

For the node classification task of a graph, we develop effective algorithms
to determine the labelling or label distributions of nodes with associated
node features by looking at the labels of their neighbors, in which we always
model an interconnected set of nodes. Moreover we often refer node
classification as semi-supervised node classification for which only a small
proportion of nodes are provided with labels but we can still access the
features of validation and test nodes and their neighborhood structures for
training.

#### Graph Classification

For the graph classification task of a set of graphs, we seek to learn label
distributions of different graphs with associated graph features but instead
of making predictions over the individual components of a single graph. We are
particularly given a set of different graphs and our goal is to make
independent predictions specific to each graph, i.e., graph classification
follows the independent and identically distributed assumption.

#### GNN Explanation

For black-box GNNs, incorporating both graph structures and feature
information leads to complex architectures and their predictions are often
unexplainable. And the explanation task aims to generate explanations for GNN
predictions that could potentially be understood. This task usually determines
which nodes and nodes features are crucial and beneficial for message
aggregation and prediction.

#### Graph Structure Learning

Graph structure learning aims to jointly learn an optimized graph structure
and corresponding graph representations when a given graph is noisy or
incomplete, or we want to infer relations from observed data. The learned
graphs are usually less noisy and more complete than the given graphs, thus
refined optimal structures can be used to better conduct downstream tasks,
e.g., node classification, object classification.

###  3.2 Probabilistic Graphical Model Tasks

We discuss how GNNs can be applied in PGMs in Section 5.

#### Exact Inference

For exact inference in PGMs, we expect to learn probability distributions over
large numbers of random variables that interact with each other (e.g., node
label distributions over a set of observed nodes). Moreover, we do not only
expect accurate predicted probability distributions and predictions (e.g.,
node classification for which the model learns label distributions over
nodes), but also want to be able to extract meaningful relationships between
the model inputs and outputs.

#### Directed Acyclic Graph Learning

The directed acyclic graph learning task aims to learn a faithful directed
acyclic graph from observed samples of a joint distribution. Learning DAG is a
challenging combinatorial problem and the refined DAGs can be further used in
downstream tasks, e.g., inference. Structural learning of DAGs from observed
data plays a vital part in causal inference with many applications in real-
world scenarios.

Table 1: Summary of models of GNNs and PGMs in this survey.

Category | Method | Reference | Section | Sturtured Prediction for Classification | GNN Explanation | Graph Structure Learning | MRF Refinments for Classification | DAG Learning | Inference
---|---|---|---|---|---|---|---|---|---
Hidden Represnetation | Output | LBP | BN | MP | Factor
| GCN-CRF | (Gao et al., 2019) | 4.1 | $\surd$ |  |  |  |  |  |  |  [t]
| GCN-HCRF | (Liu et al., 2019) | 4.1 | $\surd$ |  |  |  |  |  |  |
| MGCN | (Tang et al., 2021) | 4.1 | $\surd$ |  |  |  |  |  |  |
| CGNF | (Ma et al., 2018) | 4.1 |  | $\surd$ |  |  |  |  |  |
| GMNN | (Qu et al., 2019) | 4.1 |  | $\surd$ |  |  |  |  |  |
Probabilistic | StructPool | (Yuan & Ji, 2020) | 4.1 |  | $\surd$ |  |  |  |  |  |
Graphical Models | SMN | (Qu et al., 2021) | 4.1 |  | $\surd$ |  |  |  |  |  |
Enhanced | PGM-Explainer | (Vu & Thai, 2020) | 4.3 |  |  | $\surd$ |  |  |  |  |
Graph Neural Networks | NRI | (Kipf et al., 2018) | 4.4 |  |  |  | $\surd$ |  |  |  |
| LGS | (Franceschi et al., 2019) | 4.4 |  |  |  | $\surd$ |  |  |  |
| BGCN | (Zhang et al., 2019b) | 4.4 |  |  |  | $\surd$ |  |  |  |
| vGCN | (Elinas et al., 2020) | 4.4 |  |  |  | $\surd$ |  |  |  |
| DenNE | (Wang et al., 2020) | 4.4 |  |  |  | $\surd$ |  |  |  |
| BPN | (Bruna & Li, 2017) | 4.2 |  |  |  |  |  | $\surd$ |  |
| LinearBP | (Gatterbauer, 2017) | 4.2 |  |  |  |  | $\surd$ |  |  |
| LCM | (Wang et al., 2021) | 4.2 |  |  |  |  | $\surd$ |  |  |
| DAGNN | (Thost & Chen, 2021) | 4.2 |  |  |  |  |  | $\surd$ |  |  [b]
|  | node-GNN&msg-GNN | (Yoon et al., 2019) | 5.1 |  |  |  |  |  |  |  | $\surd$ |  [t]
Graph Neural Networks | Factor-GNN | (Fei & Pitkow, 2021) | 5.1 |  |  |  |  |  |  |  | $\surd$ |
Enhanced | FGNN | (Zhang et al., 2020) | 5.1 |  |  |  |  |  |  |  |  | $\surd$
Probabilistic | FG-GNN | (Satorras & Welling, 2021) | 5.1 |  |  |  |  |  |  |  |  | $\surd$
Graphical Models | DAG-GNN | (Yu et al., 2019) | 5.2 |  |  |  |  |  |  | $\surd$ |
|  | DeepGMG | (Li et al., 2018) | 5.2 |  |  |  |  |  |  | $\surd$ |
|  | D-VAE | (Zhang et al., 2019a) | 5.2 |  |  |  |  |  |  | $\surd$ |  [b]

##  4 Probabilistic Graphical Models Enhanced Graph Neural Networks

Figure 3: Overview of CRF implementation for modeling joint dependence of
hidden representations and labels in GNN node classification. Top: CRF for
structured output (label) prediction. Bottom: CRF for structured hidden
representation.

In this section, we present our taxonomy of graph neural networks (GNN) with
refinements of probabilistic graphical models (PGM) and Markov random fields
(MRF). MRFs are generally implemented in GNNs for four purposes: (1) CRFs
leverage GNNs to achieve structured representations for better prediction
results; (2) PGM (other than CRF) refinements for GNN classification tasks;
(3) PGMs can reason GNNs’ predictions for achieving explainable black-box
models; and (4) PGMs can be used to infer structures from observed data for
GNNs to perform downstream tasks. GNNs with structured representations, in
detail, can be categorized into two groups, structured hidden representations
and structured outputs or structured output predictions, these two approaches
have different initiatives and motivations.

###  4.1 CRFs Enhanced GNNs for Classification

Most existing GNNs hold a strong assumption that node hidden representations
and node labels are conditionally independent on node features and edges, thus
majority of GNN architectures ignore the joint dependence of node hidden
representations and node labels, and the joint node hidden unit distribution
is factorized into the marginals as

$p(\mathbf{H}^{(l)}\ |\ \mathbf{X},E)=\prod_{v\in V}p(\mathbf{h}^{(l)}_{v}\ |\
\mathbf{X},E),$ (5)

where each marginal distribution $p(\mathbf{h}^{(l)}_{v}\ |\ \mathbf{X},E)$ is
modeled as a distribution over hidden units. The joint node label distribution
is factorized into the marginals as

$p(\mathbf{Y}\ |\ \mathbf{X},E)=\prod_{v\in V}p(\mathbf{y}_{v}\ |\
\mathbf{X},E),$ (6)

where each marginal distribution $p(\mathbf{y}_{v}\ |\ \mathbf{X},E)$ is
modeled as a categorical distribution over labels.

However, the assumption might be overstated because we also assume that, in
graphs and networks, two connected nodes tend to be similar in terms of their
representations and labels (Qu et al., 2021), so the joint dependence of node
hidden representations and node labels should not be neglected. In equation 5,
it cannot guarantee that the obtained hidden representations preserve the
similarity relationship explicitly. In equation 6, the labels of different
nodes are separately predicted according to their own marginal label
distributions, yet the joint dependence of node labels is ignored.

To overcome the problem, conditional random fields (CRF) are implemented in
GNN architectures to model the joint dependence of node hidden representations
and node labels, and therefore achieve structured representations and
predictions.

#### CRFs for Structured Hidden Representations

CRFs allow GNNs to learn from the joint dependence of node hidden
representations to preserve spatial structure information in learning so that
the hidden features can explicitly preserve similarity relationships in a
local neighborhood.

At every updating iteration, the graph model is transformed into a CRF, where
each node $v\in V$ is assigned with a unary potential $\phi_{v}(\cdot)$ and
each edge $e_{vu}\in E$ is assigned with a pair-wise potential
$\phi_{vu}(\cdot)$. The unary potential learns an individual node presentation
from its local neighborhood information, and the pair-wise potential learns an
edge representation from its connecting nodes. And further the pair-wise
potentials or edge values can be sent back to each node, e.g., LBP algorithm.

At every $l$-th updating iteration, (Gao et al., 2019) define the unary
potential $\phi_{v}(\mathbf{h}^{(l)}_{v},\hat{\mathbf{h}}_{v}^{(l)})$ to
enforce node embeddings $\mathbf{H}^{(l)}$ to be close to embeddings,
$\hat{\mathbf{H}}_{GNN}^{(l)}$, obtained from a GNN layer. And the pair-wise
potential
$\phi_{vu}(\mathbf{h}^{(l)}_{v},\mathbf{h}^{(l)}_{u},\hat{\mathbf{h}}^{(l)}_{v},\hat{\mathbf{h}}^{(l)}_{u})$
is defined to capture the similarity between two connected nodes in a way two
similar nodes tend to have similar hidden representations while two different
nodes tend to have different hidden representations.

Authors in Graph Convolution Network-Hidden Conditional Random Field (GCN-
HCRF) (Liu et al., 2019) define two unary potentials to enhance learning. The
first unary potential $\phi_{v}(\mathbf{h}_{v},\mathbf{x}_{v};\theta)$
measures the likelihood of the local feature $\mathbf{x}_{v}$ assigned to the
hidden representation $\mathbf{h}_{v}$ parameterized by $\theta$, and the
second unary potential $\psi_{v}(\mathbf{m}_{v},\mathbf{Y};\omega)$ measures
the compatibility between class labels $\mathbf{Y}$ and hidden representation
$\mathbf{m}_{v}$ parameterized by $\omega$. And the pair-wise potential
$\phi_{vu}(\mathbf{h}^{(l)}_{v},\mathbf{h}^{(l)}_{u},\mathbf{Y})$ measures the
compatibility between class labels $\mathbf{Y}$ and a pair of hidden
representations $(\mathbf{h}^{(l)}_{v},\mathbf{h}^{(l)}_{u})$.

In Mutual Conditional Random Field-Graph Neural Network (MCGN) (Tang et al.,
2021), a few-shot learning approach, the unary potential
$\phi(\mathbf{h}^{(l)}_{v},\mathbf{y}_{v})$ describes the relationship between
the hidden representation $\mathbf{h}^{(l)}_{v}$ of support samples and its
ground truth label $\mathbf{y}_{v}$, and the pair-wise potential
$\phi(\mathbf{h}^{(l)}_{v},\mathbf{h}^{(l)}_{u},\mathbf{y}_{v},\mathbf{y}_{u})$
results in high compatibility when two similar nodes take the same label or
when two dissimilar nodes take different labels.

For updating node representations or unary functions, edge values obtained by
pair-wise potentials can be propagated back to nodes that connect them until
convergence or after sufficient iterations. MRFs are efficient and effective
to produce structured hidden representations.

#### CRFs for Structured Outputs

Compared to CRFs applications in modelling structured hidden representations
for local representation dependence, CRFs can directly model the joint node
label dependencies and therefore produce structured outputs. After the GNN
training, the node representations of a graph can be transformed into a CRF,
for which the unary and pair-wise potential functions directly act on label
distributions.

Conditional Graph Neural Fields (CGNF) (Ma et al., 2018) explicitly model a
joint probability of the entire set of node labels. They define the unary
potential $\phi_{v}(\mathbf{h}_{v},\mathbf{y}_{v})$ to be the prediction loss
of a GNN which measures the compatibility between a node representation
$\mathbf{h}_{v}$ and its label $\mathbf{y}_{v}$. And the pair-wise potential
$\phi_{uv}(\mathbf{y}_{v},\mathbf{y}_{u},\hat{e}_{vu},\mathbf{u}_{vu})$ is
defined to capture label correlation of two connected nodes which is impacted
by the normalized edge weight $\hat{e}_{vu}$ and label correlation weight
$\mathbf{u}_{vu}$.

Graph Markov Neural Networks (GMNN) (Qu et al., 2019) model the joint label
distribution with a CRF, which can be effectively trained with the variational
EM algorithm parameterized by two GNNs. E-step trains a GNN to learn the
posterior distributions of node labels, and M-step applies another GNN to
learn the pair-wise potential to model the local label dependence.

In Structured Graph Pooling (StructPool) (Yuan & Ji, 2020), authors consider
the graph pooling as a node clustering problem via CRF. They define unary
potential $\phi_{v}(\mathbf{y}_{i})$ to measure energy for node $v$ to be
assigned to cluster $\mathbf{y}_{i}$, and pair-wise potential
$\phi_{vu}(\mathbf{y}_{i},\mathbf{y}_{j})$ to be a Gaussian kernel which
measures the energy for nodes $v,u$ to be assigned to clusters
$\mathbf{y}_{i},\mathbf{y}_{j}$ respectively.

Authors in Structured Markov Network (SMN) (Qu et al., 2021) implement CRFs to
achieve structured output predictions for GNN node classification. They
parameterize unary potential $\phi_{v}(\mathbf{y}_{v})$ and pair-wise
potential $\phi_{vu}(\mathbf{y}_{v},\mathbf{y}_{u})$ by two GNNs (NodeGNN and
EdgeGNN) to separately calculate label distributions over nodes and edges, and
run loopy belief propagation on variables for sufficient iterations to obtain
joint node label distribution over the node set.

Since CRFs can successfully model the relations between variables through
their pair-wise potential functions, they are a good method of leveraging GNN
architectures to calculate the joint node label distribution and further
achieve the structured prediction.

###  4.2 GNNs with PGM Refinement Methods

In the previous Section 4.1, we introduce CRFs enhanced GNNs for learning
through structured representations and predictions, more than that,
alternative PGM methods can incorporate with GNNs for better predictions.

Authors in (Bruna & Li, 2017) incorporate Graph Neural Networks with Belief
Propagation (BPN) to solve semi-supervised node classification. Their
architecture consists of a classification network and a propagation procedure.
The first step is to use an independent classifier to compute the prior label
distributions of nodes without any neighboring information which can be
directly used in classification. And the second diffusion step propagates the
priors by the LBP algorithm and computes approximate beliefs of nodes to solve
node classification.

A pair-wise Markov Random Field (pMRF) associates a discrete random variable
with each node to model its label. pMRFs define a joint probability
distribution of all random variables as the product of the node potentials and
edge potentials. The edge potential for an edge $e_{vu}$ is called coupling
matrix, whose $(i,j)$-th entry indicates the likelihood that nodes $u,v$ have
labels $\mathbf{y}_{i},\mathbf{y}_{j}$ respectively.

Authors in (Gatterbauer, 2017) propose a method that computes a closed-form
solution of loopy belief propagation of any pairwise Markov random fields
(LinearBP). They assume a heuristics-based constant coupling matrix for all
edges and present a universal implicit linear equation system to represent any
pMRFs with node potentials. The solution of LBP algorithm efficiently and
iteratively converges to an implicit definition of the final beliefs (or
marginal node label distributions). LinearBP is further applied to graph
models to efficiently solve semi-supervised node classification.

Instead of using a heuristics-based constant coupling matrix for all edge,
authors in (Wang et al., 2021) leverages LinearBP with the ability to learn
edge potentials and propose an effective method to calculate marginal node
label distributions over any pair-wise Markov Random Fields (pMRF). They
define an optimization framework to iteratively update and learn the coupling
matrix (LCM) for every edge. The final coupling matrix is applied to LinearBP
to obtain the marginal node label distributions for semi-supervised node
classification.

More than defining graph models through pair-wise Markov random fields,
authors in (Thost & Chen, 2021) incorporate GNNs with Bayesian networks and
propose a directed acyclic graph neural network (DAGNN). The messaging-passing
mechanism of DAGNN follows the flow defined by the partial order by the DAG.
In particular, they generalize a graph model into a DAG, and the DAG order
allows a GNN to sequentially update node representations based on those of all
their predecessors. The messages landed on a node are no longer limited by the
multi-hop local neighborhood, and long-range dependencies are preserved in the
message passing for better node representations.

###  4.3 Explainable GNNs

In this section, we introduce PGMs that benefit explainable GNNs. (Yuan et
al., 2020) gives a comprehensive survey for explainability in GNNs.
Incorporating both graph structures and node features always leads to complex
GNN designs and their predictions are almost impossible to be understood and
explained. People aim to generate explanations, which could potentially reason
message-passing and node representations, for GNN predictions and outputs.
Probabilistic graphical models and Markov random fields for graph learning are
always interpretable and explainable thus can be implemented to approximately
analyze and give reasons to GNN predictions.

Probabilistic Graphical Model-Explainer (PGM-Explainer) (Vu & Thai, 2020)
identifies crucial graph components for a GNN prediction and generates an
explanation in form of a Bayesian network (BN). PGM-Explainer outputs
conditional probabilities according to varied contributions of graph
components. Given an input graph $G$ and a GNN prediction to be explained,
PGM-Explainer generates a perturbed graph $G^{\prime}$ by randomly perturbing
node features of some random nodes. Then for any node in $G$, PGM-Explainer
records a random variable indicating whether its feature is perturbed in $G$
and its impact on the GNN predictions of a perturbed graph $G^{\prime}$. To
create a local dataset $D$ for sufficient random variables, the procedure is
repeated multiple times for various perturbed graphs. Then PGM-Explainer
obtains Markov-blankets111The Markov-blanket defines the boundaries of a
system for variables in a network. This means that a subset that contains all
the useful information is called a Markov-blanket, and a Markov-blanket is
sufficient to infer a random variable with a set of variables. If a Markov-
blanket is minimal, it cannot drop any variable without losing information. to
reduce the size of the local dataset $D$. Finally, an interpretable BN is
learned to fit the local dataset and explain the predictions of the original
GNN model. PGM-Explainer can be used to explain both node classification and
graph classification tasks.

###  4.4 Graph Structure Learning with PGMs

Real-world networks might partially contain noisy structures and edges, or a
graph that describes observed data is missing in some applicants. A complete
and noiseless graph needs to be learned and inferred from observed samples;
figure 4 shows the general pipeline of learning a refined graph from observed
data. PGMs are beneficial to infer and learn graph structures from observed
variables for GNNs to conduct downstream tasks (e.g., node classification,
graph classification, etc.) when the input graph is unavailable or the given
graph is noisy. The core of this task is to model the connectivity of two
observed samples. The survey (Zhu et al., 2021) concludes probabilistic
graphical modeling approaches for structure learning to benefit GNNs.

Figure 4: General illustration of Graph Structure Learning (GSL). GSL models
begin with input features and the (optional) graph structure, then the
structure modeling module iteratively updates and refines the graph structure
(by removing old edges and adding new edges). Finally, node and graph
embeddings are obtained from the new refined graph.

Kipf et al. (2018) introduce an unsupervised model, neural relational
inference (NRI), that learns to infer a graph from observed variables while
simultaneously learning the dynamics purely from the observations. NRI takes
the form of a variational auto-encoder, in which the encoder maps the observed
variables to latent representations of an underlying interaction graph
(adjacent matrix), and given the interaction graph, the decoder learns the
parameters of a dynamical GNN.

Franceschi et al. (2019) propose a bi-level programming problem which learns a
discrete and sparse dependence structure (LGS) of observed variables. LGS
learns a structure by modeling the edges between each pair of variables
sampled from a Bernoulli distribution while simultaneously training a GNN.
They develop a practical algorithm using hyper-gradient estimation to
approximately solve the bi-level problem.

Bayesian Graph Convolutional Network (BGCN) (Zhang et al., 2019b) adopt the
Bayesian approach, treating the observed graph as a sample from a parametric
family of random graphs. They target the inference of the joint posterior of
the random graph parameters and node labels. In particular, they utilize Monte
Carlo dropout to sample the GCN parameters for several times on each generated
graph.

In (Elinas et al., 2020), authors aim to carry out a joint inference over GCN
parameters and the graph structure (vGCN). They formulate a joint
probabilistic model which considers a prior over the adjacency matrix along
with a GCN-based likelihood. And they further develop a stochastic variational
inference algorithm to jointly estimate the GCN parameters and the graph
posterior. In the absence of graph information, their algorithm can
effectively solve semi-supervised node classification.

Authors in (Wang et al., 2020) propose an explicit model that learns noise-
free node representations while simultaneously eliminates noises over the
graphs (DenNE). They propose a generative model with a graph generator and a
noise generator, which incorporates different graph priors and generates graph
noise to reconstruct the original graph and noise separately. Then, the two
generators are jointly optimized via maximum likelihood estimation with real
graphs as observations.

##  5 Graph Neural Networks Enhanced Probabilistic Graphical Models

In Section 4, we discuss how PGMs can be implemented to refine GNNs for
various purposes. Conversely, GNNs can be used in PGMs for two purposes: (1)
GNNs can efficiently and effectively leverage inference in PGMs; (2) GNNs can
enhance the directed acyclic graph learning in PGMs.

###  5.1 GNN Enhanced PGMs for Exact Inference

A fundamental computation for exact inference is to compute the marginal
probabilities of task-relevant variables. The exact inference task aims to
learn the joint probability distributions over observed data through a
mathematical algorithm. More than this, we also look for a meaningful and
interpretable relationship between model inputs and outputs. Since PGMs and
GNNs both work on graph-structured data and message-passing mechanism is
essential to them, one can compose PGMs with GNNs for faster and more
effective exact inference.

Loopy belief propagation (LBP) does not guarantee convergence and can struggle
when the conditional dependence graphs contain loops, or it cannot be easily
specified for complex continuous probability distributions. Authors in (Yoon
et al., 2019) propose to use GNNs to learn the message-passing algorithm that
solves inference problems with loops. They investigate two mappings between
graphical models and GNNs. The first mapping maps a message $\mathbf{m}_{ij}$
between variables $i,j$ in the graphical model to a node $v$ in the GNN. Nodes
$v,u$ are connected in the GNN if their corresponding messages share one
variable, e.g., $\mathbf{m}_{ij}$ and $\mathbf{m}_{ik}$. The second mapping
maps variables in the probabilistic graphical model to nodes in the GNN and
does not provide any hidden states to update the factor nodes. Message-passing
algorithms conducted on both GNNs are superior to LBP in PGMs for inference.

Fei & Pitkow (2021) propose to learn an iterative message-passing algorithm
using GNNs to achieve fast approximate inference on higher-order graphical
models that involve many-variable interactions. Their message-passing
algorithm performed on GNNs overcomes the drawbacks of BP when a high-order
real-world graphical model contains numerous loops.

Moreover GNNs can be generalized into factor graphical models so that not only
pairwise dependencies are preserved in the model, but also high-order
dependencies of distant variables are kept in the model. The factor graphical
models can be trained with LBP algorithm to achieve efficient and effective
message passing among variables.

Factor Graph Neural Network (FGNN) (Zhang et al., 2020) generalize a GNN into
a factor graphical model which is effective to capture long-range dependencies
among multiple variables. In particular, a factor node $\mathbf{f}_{c}$ is
associated with a set of random variables $\mathbf{x}_{c}$ of a neighborhood
of nodes in a graph model. A factor graph model $G=(V,F,E)$ is an analogy to a
graph defined in Section 2 but with a set of factor nodes $F$, an additional
group of factor features, and extra edges between factors in $F$ and their
associated nodes in $V$. FGNN can exactly parameterize the (Max-Product) loopy
belief propagation algorithm for an effective inference.

Satorras & Welling (2021) also extend graph neural networks to factor
graphical models (FG-GNN), and further propose a hybrid approach, neural
enhanced belief propagation (NEBP). Their algotithm conjointly runs a FG-GNN
with belief propagation. As a result, FG-GNN leverages the belief propagation
with the advantages of GNNs. NEBP is an iterative updating algorithm. At every
NEBP iteration, an FG-GNN takes messages produced by BP and then runs for two
iterations and updates the BP messages. The iterative procedure is repeated
sufficient times, and the final refined beliefs are used to compute marginals
for inference.

Table 2: Summary of selected datasets for GNNs conducting the node- and graph-
level tasks.

Category | Dataset | Reference | Task | #Graphs | #Node | #Node Feature | #Edges | #Edge Feature | #Class | Metric
---|---|---|---|---|---|---|---|---|---|---
| Cora | (Sen et al., 2008) | Node | 1 | 2,708 | 1433 | 5,429 | _ | 7 | Accuracy [t]
| Citeseer | (Sen et al., 2008) | Node | 1 | 3,327 | 3703 | 4,732 | _ | 6 | Accuracy
Citation | Pubmed | (Sen et al., 2008) | Node | 1 | 19,717 | 500 | 44,338 | _ | 3 | Accuracy
| ogbn-arxiv | (Hu et al., 2020) | Node | 1 | 2,449,029 | 128 | 1,166,243 | _ | 40 | Accuracy
| ogbn-mag | (Hu et al., 2020) | Node | 1 | 1,939,743 | 128 | 21,111,007 | _ | 349 | Accuracy
| ogbn-papers100M | (Hu et al., 2020) | Node | 1 | 111,059,956 | 128 | 1,615,685,872 | _ | 172 | Accuracy [b]
Social | Reddit | (Hamilton et al., 2017) | Node | 1 | 232,965 | 602 | 11,606,919 | _ | 41 | Accuracy [t]
| REDDIT-BINARY | (Yanardag & Vishwanathan, 2015) | Graph | 2,000 | 429.61 (avg.) | _ | 497.75 (avg.) | _ | 2 | Accuracy [b]
Language | NELL | (Carlson et al., 2010) | Node | 1 | 65,755 | 61278 | 266,144 | _ | 210 | Accuracy
Mathematical | PATTERN | (Dwivedi et al., 2020) | Node | 14,000 | 117.47 (avg.) | 3 | 4749.15 (avg.) | _ | 2 | Accuracy [t]
Modeling | CLUSTER | (Dwivedi et al., 2020) | Node | 12,000 | 117.20 (avg.) | 7 | 4301.72 (avg.) | _ | 6 | Accuracy [b]
| ogbn-proteins | (Hu et al., 2020) | Node | 1 | 132,534 | _ | 39,561,252 | 8 | 112 | ROC-AUC [t]
Protein | PROTEINS | (Yanardag & Vishwanathan, 2015) | Graph | 1,113 | 39.06 (avg.) | 4 | 72.81 (avg.) | _ | 2 | Accuracy
| DD | (Yanardag & Vishwanathan, 2015) | Graph | 1,178 | 284.31 (avg.) | 82 | 715.65 (avg.) | _ | 2 | Accuracy
| ogbg-ppa | (Hu et al., 2020) | Graph | 158,100 | 243.4 (avg.) | _ | 2,266.1 (avg.) | 7 | 37 | Accuracy [b]
Commercial | ogbn-products | (Hu et al., 2020) | Node | 1 | 2,449,029 | 100 | 61,859,140 | _ | 47 | Accuracy
Chemistry | ZINC | (Dwivedi et al., 2020) | Graph | 12,000 | 23.16 (avg.) | 28 | 49.83 (avg.) | 4 | _ | MAE
| ogbg-molhiv | (Hu et al., 2020) | Graph | 41.127 | 25.5 (avg.) | 9 | 27.5 (avg.) | 3 | _ | ROC-AUC [t]
Molecule | ogbg-molpcba | (Hu et al., 2020) | Graph | 437,929 | 26.0 (avg.) | 9 | 28.1 (avg.) | 3 | _ | AP
| NCI1 | (Yanardag & Vishwanathan, 2015) | Graph | 4,110 | 29.87 (avg.) | 37 | 32.3 (avg.) | _ | 2 | Accuracy
| MUTAG | (Yanardag & Vishwanathan, 2015) | Graph | 188 | 17.93 (avg.) | 7 | 19.79 (avg.) | _ | 2 | Accuracy [b]
Computer | MNIST | (Dwivedi et al., 2020) | Graph | 70,000 | 70.57 (avg.) | 3 | 564.53 (avg.) | 1 | 10 | Accuracy [t]
Vision | CIFAR10 | (Dwivedi et al., 2020) | Graph | 60,000 | 117.63 (avg.) | 5 | 941.07 (avg.) | 1 | 10 | Accuracy [b]

###  5.2 GNN Enhanced Directed Acyclic Graph Learning

Learning directed acyclic graphs (DAG) from observed variables is an NP-hard
problem, owing mainly to the combinatorial acyclicity constraint that is
difficult to enforce efficiently (Chickering, 1996). GNNs cannot be directly
used in structure learning of probabilistic graphical models for inference,
but can intermediately enhance the structure learning due to their capability
of capturing complex nonlinear mappings.

Figure 5: Overview of DAG learning from observed variables, a DAG structure is
generally computed via a DAG autoencoder.

Li et al. (2018) propose a powerful generative model over graphs (DeepGMG),
which can capture both their structures and attributes. DeepGMG uses a
sequential process to generate one node at a time and connects each node to
the existing partial graph by creating edges one by one. They use GNNs to
express probabilistic dependencies among a graph’s nodes and edges, and can,
in principle, learn distributions over any arbitrary graph. Their method can
efficiently and effectively embed DAGs by using simultaneous message passing.

Yu et al. (2019) propose a deep graph-based generative model and apply a
variant of the structural constraint to learn a weighted adjacency matrix of a
directed acyclic graph, in which the generative model is a variational auto-
encoder parameterized by a novel graph neural network (DAG-GNN). In addition
to the rich capacity, an advantage of the proposed model is that it naturally
handles discrete variables as well as vector-valued ones.

Zhang et al. (2019a) introduce a novel DAG Variational Auto-Encoder (D-VAE) to
learn DAGs. Rather than using existing simultaneous message passing schemes in
equation 1 to encode local graph neighborhood information, they propose a
novel asynchronous message passing mechanism that allows encoding the
computations (rather than structures) on DAGs. Their model allows us to build
an injective mapping from the discrete space to a continuous latent space so
that every DAG computation has its unique embedding in the latent space.

##  6 Datasets

We categorize datasets into six diverse groups according to specific tasks:
graphs for node-level tasks, graphs for graph-level tasks, graphs for
generating explanations, graphs for structure learning, observed variables for
inference, and observed variables for directed acyclic graph learning. Dwivedi
et al. (2020) and Hu et al. (2020) contribute great datasets for GNNs to test
on the node- and graph-level tasks, provide leaderboards for fair comparisons,
and evaluate the performance of different GNNs on the node- and graph-level
tasks.

###  6.1 Node-level Task

We summarize selected node benchmark datasets in Table 2; node-level tasks
include node classification and node regression. In node-level tasks, most
methods follow full-supervised splits of train/valid/test or semi-supervised
splits on benchmark datasets including citation networks, commercial networks,
social networks, proteins graphs, mathematical modeling graphs: Cora,
Citeseer, Pubmed, NELL, PATTERN, CLUSTER, Reddit, ogbn-products, ogbn-
proteins, ogbn-arxiv, ogbn-papers100M, ogbn-mag. And it is required to report
the number of model parameters, the total training time in second or
millisecond, the number of training epochs per second or millisecond, and the
average accuracy or ROC-AUC with standard deviation on the test data over at
least five runtimes.

###  6.2 Graph-level Task

We summarize selected graph benchmark datasets in Table 2, graph-level tasks
include graph classification and graph regression. In graph-level tasks, most
methods follow full-supervised splits of train/valid/test on benchmark
datasets including computer vision graphs, chemistry graphs, molecular graphs,
protein graphs, social networks: MUTAG, DD, NCI1, PROTEINS, REDDIT-BINARY,
ZINC, MNIST, CIFAR10, ogbg-molhiv, ogbg-molpcba, ogbg-ppa. And it is required
to report the number of model parameters, the total training time in second or
millisecond, the number of training epochs per second or millisecond, the
average accuracy, AP, MAE, or ROC-AUC with standard deviation on the test data
over at least five runtimes.

###  6.3 GNN Explanation

Researchers present experiments to evaluate example-level or model-level
explanations for node classification and graph classification tasks on either
synthetic datasets or real-world datasets, e.g., benchmarking datasets listed
in Table 2 can also be used in GNN explanation task. Or more often, the trust
weighted signed networks, Bitcoin-Alpha and Bitcoin-OTC (Kumar et al., 2016),
are two datasets for evaluating GNN explanations on node-level tasks; the
computer vision graphs MNIST (Dwivedi et al., 2020), the molecular graphs
MUTAG, and the social networks Reddit-Binary (Yanardag & Vishwanathan, 2015),
are three datasets for evaluating GNN explanations on graph-level tasks. A GNN
is initially trained on these datasets to generate some representations or
label distributions, then each explainable method is compared by the
explanation accuracy.

###  6.4 Graph Structure Learning

Like the GNN explanation task, benchmarking datasets listed in Table 2 can be
used in graph structure learning for GNNs as well. Franceschi et al. (2019)
evaluate their model on incomplete Cora and Citeseer networks where they
construct graphs with missing edges by randomly sampling 25%, 50%, and 75% of
the edges. Authors of vGCN (Elinas et al., 2020) also test on incomplete Cora
and Citeseer graphs with a different setting.

Moreover, observed variables can be used to conduct graph structure learning
even if their relational graph structures are not given. Kipf et al. (2018)
experiment their method for relational inference with three simulated systems:
particles connected by springs, charged particles, and phase-coupled
oscillators (Kuramoto model). Franceschi et al. (2019) also test their model
on benchmark datasets, such as Cancer, Digits, and 20news, which are available
in scikit-learn (Pedregosa et al., 2011).

###  6.5 Exact Inference

In the exact inference, researchers often examine their algorithms on either
synthetic graphical models or real-world graphical models. The synthetic
graphical models can be Gaussian graphical models, e.g., loopy graphs and tree
graphs, or continuous non-Gaussian graphical models (Fei & Pitkow, 2021). The
real-world datasets include low-density parity check (LDPC) encoded signals
where where the decoding can be done by sum/max-product belief propagation
(Zhang et al., 2020), and the Human3.6M dataset (Ionescu et al., 2013) of the
skeleton data for human motion prediction.

###  6.6 DAG Learning

Synthetic directed acyclic graphs are often generated for DAG learning;
experiments of DAG learning only demonstrate successes on small graphical
datasets. Authors in (Yu et al., 2019) generate synthetic datasets by sampling
generalized linear models, with an emphasis on nonlinear data and vector-
valued data. In (Zhang et al., 2019a), authors evaluate their model on two DAG
optimization tasks including neural architecture search and Bayesian network
structure learning.

##  7 Future Directions

Though PGMs for GNNs and GNNs for PGMs have been developed in the past few
years, there remain several open challenges and opportunities for exploration
due to the complexity of graphs and graphical models. In this section, we
discuss future directions from three perspectives.

###  7.1 Benchmarks and Datasets

Experiments for explainability, structure learning, and exact inference
demonstrate successes on small graphs and graphical datasets. However,
existing datasets for explainable GNNs, graph structure learning, inference,
and DAG learning still remain limited in terms of their scale and
accessibility. Graph datasets (see Table 2) used in classification/regression
tasks are also often used in other tasks, however, each task should have its
specific datasets and benchmarks for evaluation and comparison. Future
experiments should consider training and testing on larger and more diverse
real-world networks, as well as on broader classes of graphical models with
more interesting sufficient statistics for nodes. Therefore we encourage
future studies to collect more data on large diverse real-world graphs for
training, and proper baselines and benchmarks for fair evaluation and
comparison.

###  7.2 Homphilic Graphs

Homophily assumption on graphs is the tendency that connected nodes are more
likely to share the same labels or similar features (Grover & Leskovec, 2016).
When the homophily assumption fails on graph-structured data, current GNNs
fail to distinguish nodes and even simple Multi-Layer Perceptrons (MLP) can
outperform GNNs by a large margin on several node classification tasks (Luan
et al., 2021). The performance of GNNs can be heavily affected by varied graph
structures at different homophily levels, and we will expect more accurate
predictions on homophilic graphs. One possible direction is to infer or to
learn homophilic graphs from observed variables. So GNNs can conduct message
passing and perform training in homophilic neighbors to achieve better
performance. Graph structure learning is a big topic in which PGMs benefit
GNNs to learn noiseless graphs for downstream tasks. Potentially, PGM
approaches could be well-adopted for generating homophilic graphs based on
feature and training label similarities.

###  7.3 Interpretability and Explainability

Interpretability and explainability are two closely-related crucial components
for GNN designs, and still open challenges in many real-world applications,
e.g., drug design, recommender system, and navigation satellite system.
Authors in (Yuan et al., 2020) clearly distinguish interpretability and
explainability in the field of GNNs. They consider a GNN to be ′interpretable′
if the model itself can provide human-level understandable interpretations of
its predictions, and the GNN should no longer follow some black-box
mechanisms. An ′explainable′ GNN implies that the model is still a black box
but the predictions could potentially be understood by post hoc explanation
techniques, such as the BN approach adopted in (Vu & Thai, 2020). How to
design interpretable GNNs and how to generate explanations for GNN predictions
are still under-explored. Since exact inference aims to precisely learn
probability distributions and extract meaningful relationships between inputs
and outputs, white-box PGMs that make interpretable and explainable message
passing and predictions on graphs should be more adopted and implemented in
designs of powerful GNNs.

## References

  * Bruna & Li (2017) Bruna, J. and Li, X.  Community detection with graph neural networks.  _stat_ , 1050:27, 2017.
  * Carlson et al. (2010) Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Hruschka, E. R., and Mitchell, T. M.  Toward an architecture for never-ending language learning.  In _Twenty-Fourth AAAI conference on artificial intelligence_ , 2010\.
  * Chickering (1996) Chickering, D. M.  Learning bayesian networks is np-complete.  In _Learning from data_ , pp. 121–130. Springer, 1996.
  * Dwivedi et al. (2020) Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X.  Benchmarking graph neural networks.  _arXiv preprint arXiv:2003.00982_ , 2020.
  * Elinas et al. (2020) Elinas, P., Bonilla, E. V., and Tiao, L.  Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.  _Advances in Neural Information Processing Systems_ , 33:18648–18660, 2020.
  * Fei & Pitkow (2021) Fei, Y. and Pitkow, X.  Generalization of graph network inferences in higher-order probabilistic graphical models.  _arXiv preprint arXiv:2107.05729_ , 2021.
  * Franceschi et al. (2019) Franceschi, L., Niepert, M., Pontil, M., and He, X.  Learning discrete structures for graph neural networks.  In _International conference on machine learning_ , pp. 1972–1982. PMLR, 2019.
  * Gao et al. (2019) Gao, H., Pei, J., and Huang, H.  Conditional random field enhanced graph convolutional neural networks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 276–284, 2019.
  * Gatterbauer (2017) Gatterbauer, W.  The linearization of belief propagation on pairwise markov random fields.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 1263–1272. JMLR. org, 2017.
  * Grover & Leskovec (2016) Grover, A. and Leskovec, J.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 855–864. ACM, 2016.
  * Hamilton (2020) Hamilton, W. L.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , 14(3):1–159, 2020.
  * Hamilton et al. (2017) Hamilton, W. L., Ying, R., and Leskovec, J.  Inductive representation learning on large graphs.  _arXiv_ , abs/1706.02216, 2017.  URL http://arxiv.org/abs/1706.02216.
  * Hu et al. (2020) Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J.  Open graph benchmark: Datasets for machine learning on graphs.  _arXiv preprint arXiv:2005.00687_ , 2020.
  * Hua et al. (2022) Hua, C., Rabusseau, G., and Tang, J.  High-order pooling for graph neural networks with tensor decomposition.  _arXiv preprint arXiv:2205.11691_ , 2022.
  * Ionescu et al. (2013) Ionescu, C., Papava, D., Olaru, V., and Sminchisescu, C.  Human3. 6m: Large scale datasets and predictive methods for 3d human sensing in natural environments.  _IEEE transactions on pattern analysis and machine intelligence_ , 36(7):1325–1339, 2013.
  * Kipf et al. (2018) Kipf, T., Fetaya, E., Wang, K.-C., Welling, M., and Zemel, R.  Neural relational inference for interacting systems.  In _International Conference on Machine Learning_ , pp. 2688–2697. PMLR, 2018.
  * Kipf & Welling (2016) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  _arXiv_ , abs/1609.02907, 2016.  URL http://arxiv.org/abs/1609.02907.
  * Koller & Friedman (2009) Koller, D. and Friedman, N.  _Probabilistic graphical models: principles and techniques_.  MIT press, 2009.
  * Kumar et al. (2016) Kumar, S., Spezzano, F., Subrahmanian, V., and Faloutsos, C.  Edge weight prediction in weighted signed networks.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pp. 221–230. IEEE, 2016.
  * Li et al. (2018) Li, Y., Vinyals, O., Dyer, C., Pascanu, R., and Battaglia, P.  Learning deep generative models of graphs.  _arXiv preprint arXiv:1803.03324_ , 2018.
  * Liu et al. (2019) Liu, K., Gao, L., Khan, N. M., Qi, L., and Guan, L.  Graph convolutional networks-hidden conditional random field model for skeleton-based action recognition.  In _2019 IEEE International Symposium on Multimedia (ISM)_ , pp. 25–256. IEEE, 2019.
  * Luan et al. (2020) Luan, S., Zhao, M., Hua, C., Chang, X.-W., and Precup, D.  Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks.  _arXiv preprint arXiv:2008.08844_ , 2020.
  * Luan et al. (2021) Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D.  Is heterophily a real nightmare for graph neural networks to do node classification?  _arXiv preprint arXiv:2109.05641_ , 2021.
  * Luan et al. (2022) Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D.  Revisiting heterophily for graph neural networks.  _arXiv preprint arXiv:2210.07606_ , 2022.
  * Ma et al. (2018) Ma, T., Xiao, C., Shang, J., and Sun, J.  Cgnf: Conditional graph neural fields.  2018\.
  * Murphy et al. (2013) Murphy, K., Weiss, Y., and Jordan, M. I.  Loopy belief propagation for approximate inference: An empirical study.  _arXiv preprint arXiv:1301.6725_ , 2013.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Qu et al. (2019) Qu, M., Bengio, Y., and Tang, J.  Gmnn: Graph markov neural networks.  In _International conference on machine learning_ , pp. 5241–5250. PMLR, 2019.
  * Qu et al. (2021) Qu, M., Cai, H., and Tang, J.  Neural structured prediction for inductive node classification.  In _International Conference on Learning Representations_ , 2021.
  * Satorras & Welling (2021) Satorras, V. G. and Welling, M.  Neural enhanced belief propagation on factor graphs.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 685–693. PMLR, 2021.
  * Sen et al. (2008) Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Tang et al. (2021) Tang, S., Chen, D., Bai, L., Liu, K., Ge, Y., and Ouyang, W.  Mutual crf-gnn for few-shot learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2329–2339, 2021.
  * Thost & Chen (2021) Thost, V. and Chen, J.  Directed acyclic graph neural networks.  _arXiv preprint arXiv:2101.07965_ , 2021.
  * Velickovic et al. (2017) Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y.  Graph attention networks.  _arXiv_ , abs/1710.10903, 2017.
  * Vu & Thai (2020) Vu, M. and Thai, M. T.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  _Advances in neural information processing systems_ , 33:12225–12235, 2020.
  * Wang et al. (2021) Wang, B., Jia, J., and Gong, N. Z.  Semi-supervised node classification on graphs: Markov random fields vs. graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 10093–10101, 2021.
  * Wang et al. (2020) Wang, J., Li, Z., Long, Q., Zhang, W., Song, G., and Shi, C.  Learning node representations from noisy graph structures.  In _2020 IEEE International Conference on Data Mining (ICDM)_ , pp. 1310–1315. IEEE, 2020.
  * Yanardag & Vishwanathan (2015) Yanardag, P. and Vishwanathan, S.  Deep graph kernels.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 1365–1374, 2015.
  * Ying et al. (2019) Ying, Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J.  Gnnexplainer: Generating explanations for graph neural networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Yoon et al. (2019) Yoon, K., Liao, R., Xiong, Y., Zhang, L., Fetaya, E., Urtasun, R., Zemel, R., and Pitkow, X.  Inference in probabilistic graphical models by graph neural networks.  In _2019 53rd Asilomar Conference on Signals, Systems, and Computers_ , pp. 868–875. IEEE, 2019.
  * Yu et al. (2019) Yu, Y., Chen, J., Gao, T., and Yu, M.  Dag-gnn: Dag structure learning with graph neural networks.  In _International Conference on Machine Learning_ , pp. 7154–7163. PMLR, 2019.
  * Yuan & Ji (2020) Yuan, H. and Ji, S.  Structpool: Structured graph pooling via conditional random fields.  In _Proceedings of the 8th International Conference on Learning Representations_ , 2020.
  * Yuan et al. (2020) Yuan, H., Yu, H., Gui, S., and Ji, S.  Explainability in graph neural networks: A taxonomic survey.  _arXiv preprint arXiv:2012.15445_ , 2020.
  * Zhang et al. (2019a) Zhang, M., Jiang, S., Cui, Z., Garnett, R., and Chen, Y.  D-vae: A variational autoencoder for directed acyclic graphs.  _Advances in Neural Information Processing Systems_ , 32, 2019a.
  * Zhang et al. (2019b) Zhang, Y., Pal, S., Coates, M., and Ustebay, D.  Bayesian graph convolutional neural networks for semi-supervised classification.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pp. 5829–5836, 2019b.
  * Zhang et al. (2020) Zhang, Z., Wu, F., and Lee, W. S.  Factor graph neural networks.  _Advances in Neural Information Processing Systems_ , 33:8577–8587, 2020.
  * Zhu et al. (2021) Zhu, Y., Xu, W., Zhang, J., Liu, Q., Wu, S., and Wang, L.  Deep graph structure learning for robust representations: A survey.  _arXiv preprint arXiv:2103.03036_ , 2021.