Policy Message Passing: A New Algorithm for Probabilistic Graph Inference
Authors: Zhiwei Deng
Greg Mori
Venue:  (2020)
Keywords: graph inference algorithm
graph reasoning
variational inference

Abstract: A general graph-structured neural network architecture operates on graphs through two core components: (1) complex enough message functions; (2) a fixed information aggregation process. In this paper, we present the Policy Message Passing algorithm, which takes a probabilistic perspective and reformulates the whole information aggregation as stochastic sequential processes. The algorithm works on a much larger search space, utilizes reasoning history to perform inference, and is robust to noisy edges. We apply our algorithm to multiple complex graph reasoning and prediction tasks and show that our algorithm consistently outperforms state-of-the-art graph-structured models by a significant margin.

Under review as a conference paper at ICLR 2020
POLICY MESSAGE PASSING: A NEW ALGORITHM FOR PROBABILISTIC GRAPH INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
A general graph-structured neural network architecture operates on graphs through two core components: (1) complex enough message functions; (2) a fixed infor- mation aggregation process. In this paper, we present the Policy Message Passing algorithm, which takes probabilistic perspective and reformulates the whole information aggregation as stochastic sequential processes. The algorithm works much larger search space, utilizes reasoning history perform inference, and is robust to noisy edges. We apply our algorithm to multiple complex graph rea- soning and prediction tasks and show that our algorithm consistently outperforms state-of-the graph-structured models by a significant margin.
INTRODUCTION
Not every path is created equal. Powerful sequential inference algorithms have been a core research topic across many tasks that involve partial information, large search spaces, or dynamics over time. An early algorithm example is dynamic programming which memorizes the local information and uses a fixed inference trace to acquire a global optimum. In the modern deep learning era, sequential memory architectures such as recurrent neural networks (e.g. language generation (Sutskever et al. (2014))) to narrow down the search space. Neural- based iterative correction is developed in amortized inference for posterior approximation (Marino al. (2018). Also, a large bulk of works are developed reinforcement learning for sequential inference of the environment with partial observation, non-future aware states, and world dynamics.
used for sequential inference
Graph-structured models are another class of models that heavily rely on local observations and sequential inference. contains nodes and message functions with partial information, the final output of model relies on sequence of communication operations which transforms the nodes information dynamically over iterations. A general formulation of learning graph-structured models is maximizing the likelihood:
max maxppyysoo.o Fo, P)
The objective describes the process where it takes in the information æ over a graph, starts from initial states so and maps the target output y. This process involves key components, message functions F and inference process P.
Message functionn designs focus on the choices of functions defined over the interaction between nodes or variables. Simple log- linear potential functions are commonly used in traditional probabilistic graphical models (Sutton al. (2012)). Kernelized potential functions (Lafferty al.) (2004)). gaussian energy functions (Krähenbühl & Koltun (201T)), or semantic-driven potential functions (Lan jet al. ()0TT) are developed varied cases to adapt to specific tasks. Deep graph neural networks generalizes the message functions to neural networks. There are variety of function types developed such as graph convolution operations (Kipf & Welling (2016)), attention- functions (Veličković et al. (2017)) gated functions (Li et al. (2015): Deng al. (2016)).
Inference procedures over graphs are mainly developed under the context of probabilistic graphical models, with the classic inference techniques such as belief propagation (Pearl (1988)), generalized belief propagation (Yedidia et al. (200T)), )) and tree-reweighted message passing (Wainwright et al. (2003)). However, there has not been many research in developing powerful inference process in

---

Under review as a conference paper at ICLR 2020
modern deep graph-structured models (Graph Neural Networks). Most graph-structured models still follow a fixed hand-crafted rule for performing inference over nodes.
In this paper, take different tack and instead propose represent the inference process modeled by a neural network Pa:
max P [p(y] x, T; Fo)] $9.0
(2)
The neural network Pa represents the distribution over all possible inference trajectories in the graph model. By taking the distribution perspective of message passing, the whole inference is reformulated as stochastic sequential processes in the deep graph-structured models. This formulation introduces several properties: Distribution nature - the possible inference trajectories in graph, besides synchronous asynchronous, are in a vast space with varied possibilities, leading to different results; Consistent inference maintaining a powerful neural network memorizing over time could lead to more effective and consistent inference over time; Uncertainty inference itself will affect prediction, with distribution, such uncertainty over the reasoning between nodes can be maintained.
The primary contributions of this paper are three folds. Firstly, we introduce a new perspective on message passing that generalizes the whole process to stochastic inference. Secondly, we propose variational inference based framework for learning the inference models. Thirdly, We empirically demonstrate that having powerful inference machine can enhance the prediction in graph-structured models, especially on difficult reasoning tasks, or graphs with noisy edges.
2 BACKGROUND: GRAPH NEURAL NETWORKS
large volume of Graph Neural Network (GNN) models have been developed recently (Defferrard et al. (2016); Li et al. (215)): : Kipf & Welling (2016; Henaff al. (2015); Duvenaud et al. (2015)) for varied applications and tasks. This line of methods typically share some common structures such propagation networks and output functions. In paper, without loss of generality, we follow
a unified view of graph neural network proposed in a recent survey (Battaglia et al. (2018) and introduce the graph neural network architecture here.
In this formulation, there are two key components: propagation networks and output networks. In the propagation networks, the fundamental unit is "graph-to-graph" module. This module takes graph with states 8, as input and performs information propagation (message passing) operations to modify the values to $141. The graph states at each step consists of sets of variables representing the attributes of nodes V; = {u), and edges & {eh. along with global properties u. The graph-to- trap-tt-graphh module updates the attributes of these nodes, edges, and global properties via a set of message passing, implemented as neural networks.
e, fe (fv) &,, E): = fo (fe)e. Vr, E): u- fu (1o)),, feh.. E
(3)
The message passing in the standard graph neural networks is fixed aggregation process defined by the graph structure E. The outpul network is general part of model that maps the information in the graph states to the target output y: p(y]ST). ). In general, there is no restriction on the form of target y or the output mapping function, like the target can be set of labels for nodes, edges, the whole graph or even sentences.
3 GRAPH MODELS WITH POLICY MESSAGE PASSING
In this section we describe our stochastic graph inference algorithm under the formulation of graph neural networks. As the inference process under the algorithms is more of reasoning procedure, we refer to it as reasoning in the later content. Our approach takes the initial state Su of graph representing observations and latent variables in domain, uses a set of parameterized reasoning agents to pass messages over this graph, and infers the output prediction y. Our model contains three main parts:
1. Graph 8t, representing states of observed and latent variables.
2

---

Under review as a conference paper at ICLR 2020
Sharot
Sarrel
Agest
Aguus
Reuzzing
Aport
Agent
Agent
Groph states
Generate oction distribution
Action sampling/ Function selection
Time stop: 1-1
Time stop:
Time step: 1
(a) Single timestep action proposal.
(b) Dynamic graph reasoning over multiple steps.
Figure We design agents that learn reason over graphs by sequentially performing actions for inference. (a) We learn function set. Each function is possible message along edge. At each time step of inference, our reasoning agent examines the current graph states and produces distribution over the function set sample from. (b) A set of these agents, each one considering its own edge, run to produce the full set of messages for a graph. Each agent maintains its own state and can communicate with the other agents via shared memory.
2. A set of message functions {ʃa(s : Ox)}. parameterized by 0z. that determine the possible manner which messages can be passed over edges the graph.
3. An automatic reasoning agent A-: Φ), parameterized by ø, that determines which message function would be appropriate to along edge in the graph.
For every timestep during reasoning, our model takes the current graph state 8, and the previous reasoning history. then generates distribution over actions for choosing which messages to pass (or pass no information). The new graph state $t+1 is obtained through performing message passing actions sampled from the distribution. The final prediction is thus inferred sequentially through the operation of the reasoning agents over the graph. Fig. [ iillusraats the algorithm.
3.1 MODEL DEFINITION
Our inference procedure operates graphs. We start with an initial graph state so (vo, Co un), where Un. én, and ug contain information about individual nodes, edges, and global information about the graph respectively. Nodes in this graph can represent observations or latent variables from our domain; we assume the set of nodes is known and fixed. Edges in this graph represent possible relationships between nodes, over which we will potentially pass messages during inference. The edges are assumed known and fixed, though our method will permit flexibility via its inference.
Given graph state s, we can output y using network (s f,). Note that general this formulation could have variety of possible output functions, corresponding to different tasks. In the current instantiation we focus on a single such output function that used for a single task. Given the initial graph state 8p. perform set of reasoning steps that pass messages over this graph to obtain refined graph representation. The goal of this message passing is to successively refine the graph state such that the graph state can be accurately decoded to match the correct output for the given input graph. The update functions we define will modify the node attributes v. though the formulation could be generalized to edge and global attributes well.
Message Formulation: The message passing is decomposed into operations on edges in the graph. For the tt node in the graph, update its state by passing messages from all nodes in its neighbour set N (i)...
v'
Σ fa JEN()
(4)
The form of message to pass is a crucial component of our method. We select the function fae (-..) use in this message passing for each edge.
3

---

Under review as a conference paper at ICLR 2020
We define common set of functions {ff( ) Joskss & that can be used across any edge in the graph. To allow for no information to be passed along an edge, we define the function fo(..-) = O. Each of the other functions fx( -) is non-linear function (e.g. MLP) with its own learnable parameters 0/.-
Reasoning Agents: Alongside these functions, we define a reasoning agent that determines which function use particular edge in the graph at the current time step of inference. We one copy of this reasoning agent for each edge of the graph. The reasoning agent takes as input the current graph state and for its edge (i,j) outputs distribution over the message pass on that edge (computed by network A). The reasoning agent maintains state lig (propagated via a network B) over iterations of inference so that it can potentially remember which types of message passing actions were taken at different time steps L. We also include global state hy Eig h which can be used to share information across the agents operating on different edges.
The networks are updated and distributions computed using the following equations:
h h ((s,, L. h (B)
(5)
7 (=f41188) x A(se, i, h, h 0A) +1
(6)
where (<24/155)) is distribution over 1. the message function use for edge (i.j) step t + 1 given the current graph state. Note that a uniform prior is added to message distribution for regularization, though in general other priors could be used for this purpose. The parameters é = 1 0B) for the reasoning agent are shared; however, each edge maintains its own copy of these agents, via different states h.P
Action sampling: Given these distributions म, we can now use them perform inference by sampling actions from these distributions. In our implementation, the Gumbel softmax trick is used for differentiable sampling.
By executing a set of actions {z,} sampled from each of these distributions our model takes selected nodes and corresponding message functions to pass, and the graph state is updated to 8 after one reasoning/passing step. Over a sequence of time steps, this process corresponds to reasoning trajectory 7 = (21, ,,,...; Er) that produces a sequence of graph states (8y, 81,.... $T). At test time, evaluate learned model by sampling multiple such reasoning trajectory sequences and aggregating the results.
3.2 LEARNING OBJECTIVE
We assume that are provided with training data that specify an input graph structure along with its corresponding value to be inferred. For case of exposition, we derive our learning objective for single training data pair of graph with target value y. For the learning objective. we adopt probabilistic view on reasoning. As per the previous section, we can infer these values by running a particular reasoning process. However, rather than fixing reasoning process, we could instead imagine inferring values y by marginalizing over all possible reasoning sequences
p(y]s) Σ Ep(y,TI8 = - (ss(
The "prior" (8) could be either learnable prior or a hand-designed prior. Belief propagation or other neural message passing frameworks define delta function where the prior deterministic and fixed. Here we instead adopt learnable prior for P(T(s), where the reasoming process depends on the graph states. represents the latent reasoning sequence. Given a graph initial state and ground truth label y, we are interested in the posterior distribution over trajectories that describes an efficient and effective reasoning process. We adopt standard variational inference to approximate the posterior distribution and try to find such action spaces.
As per the previous section, we have a method for computing y given a reasoning sequence т. However, in variational inference applications, evaluation of the summation in Eq. 7 challenging. Standard sampling approaches, i.e. choosing an inference procedure from an arbitrary proposal distribution, would be likely to lead to inference procedures ineffective for the given graph/inference task. Instead, we utilize our reasoning agent as a proposal distribution to propose inference procedures. If the proposal distribution is close the posterior distribution over reasoning actions, then we can
4

---

Under review as a conference paper at ICLR 2020
conduct both effective and efficient inference obtain the final desired output. Hence, we hope to minimize the following KL divergence:
( 8))
(8)
where & is the proposal distribution over reasoning actions. x² the true posterior distribution over reasoning sequences given the target inference values and graph state 8, which is unknown, We adopt the standard variational inference method to derive the following equations:
log puy s) (TT(((Tl,ss)(/== (Tly.s) = By-q
s)] - ()) (9)
We can optimize the right hand side, which is also known as the evidence lowerbound (ELBO). The log likelihood and KL divergence in Eq. [ are then implicitly optimized. We can also decide define the learning objective as a product of probabilities over the T time steps in the reasoning process. In this case, the objective would be:
T
Rac=a [logplylzz 8 1D] [L(((T) ()l
(10)
To summarize, we learn the parameters of the networks fo and {fx} which specify p s): and A and B which specify [T s). This is accomplished by maximizing the ELBO in Eq. over all graph-target value pairs in the training data.
The learning objective consists in two terms. Likelihood term: This term provides main objective for the agent and model to maximize. The policy should be learned to perform accurate reasoning to fit the data and maximize the likelihood of the ground truth values for y. KL ferm: The policy we learn in proposal distribution can be used to guide the learnable prior agent toward good inference procedures. The KL divergence term the objective function can be used to achieve this.
Interpretation Learning Objective:
3.3 MIXED SAMPLING FROM SEQUENTIAL DISTRIBUTIONS
As the whole inference over graphs is a sequential procedure, there is common issue that will appear the above formulation: the drifting problem when facing unfamiliar graph states in some inference step The proposal distribution in the variational inference formulation has access to ground truth data, which will lead to "good" graph states in most cases, while the prior agent will probably face some graph states that will lead to failure predictions and have been found in sequential data generation (Lamb et al. (2016)) or imitation learning (Ross et al.) (201I). In our model, we adopt easy fix by mix the sampling from both prior and proposal in the trajectory level, to have graph neural networks visit different states, and by firstly rollout using prior agent, then use the proposal agent complete the trajectory. The objective re-weighted using importance sampling weights when mixing the trajectories.
drift away further. Similar issues
4 EXPERIMENTS
We test proposed model two types of modalities of data: complex visual reasoning tasks and social network classification. Visual data has more information and more complex possible interactions variations between nodes in the graph, while social network has larger scale of graphs.
4.1 VISUAL REASONING
We introduce two visual reasoning tasks: (1) visual cue-based position reasoning and (2) large-scale image puzzle solving. To solve these visual based reasoning tasks, we require model to have strong ability in handling imperfect observations, performing inference, handling noisy edges, and flexibly making modifications to graph nodes.
Baseline methods: We compare our proposed model with several popular graph neural network based variants. These models all more or less have the ability to learn and control the information flow, and have been demonstrated to have strong performance many tasks applications.
5

---

Under review as a conference paper at ICLR 2020
number of objects
25
36
random
4
2.78
GNN
32.92
16.21
GNN-atiention
40.26
21.58
RRN
35.10
19.62
NRI
38.74
18.84
PMP (ours)
81.26
46.8
(a) Illustration of the "Where am I" dataset and tasks. Each object is extracted from the original image along with its context. Be- tween some patches there will be similar pat- terns appear.
(b) Performance results "Where am r" dataset, measured by per-node position clas- sification accuracy.
Figure 2: Our "Where am I" dataset(left) and results compared with baseline methods measured by per object accuracy(rightt.
Graph Neural Network (Battagli et al. (2018) We follow the graph neural network model
described in the survey Battaglia et al. (2018). The graph neural network contains three update functions: node, edge, global states. The aggregation process we used is mean pooling of messages.
Attention-base baased Graph Neural Network (Veličković et al. (2017): Wang et al. (2018);
Vaswani al. (2017)) An attention mechanism used for modulating the information flow from different messages and can be viewed as a non-probabilistic single-step version of our model. We implement the attention by using sigmoid gates over different message functions.
Recurrent Relational Network (Battaglia et al. (2018), ). We follow the open source code and implement the recurrent relational network (RRN) model. The RRN model updates the node states through Gated Recurrent Unit and adds dense supervision across all timesteps.
Neural Relational Inference model (Kipf et al. (2018). The Neural Relational Inference model is the first proposed probabilistic model that captures the distribution over graph structures. We follow the same implementation and use four function types on each edge with entropy as an extra penalty in the objective function.
4.1.1 "Where am I": VISUAL POSITION REASONING
Task design: We firstly design synthetic dataset named "Where am I", The dataset based on the Shapes Andreas al. (216)) dataset, initially proposed in the Visual Question Answering (VQA) context. The dataset contains 30K images with shape objects randomly dropped on x k grids. We assume that each shape object has 3 3 context field of view and ensure that all those shape objects are connected within the visible context. The dataset is set up to have two grid settings, x 9 and 12 12, which contain 25 objects and 36 objects respectively. For each image, the position for one object is known and the model needs to perform inference over objects by comparing the context to infer the correct position of other objects.
Model setup and problem difficulties: We build a graph to solve this problem. Each node in the graph represents one object, one of them contains a known position tuple (x. y), and the positions for the rest obejcts are unknown. The graph is assumed to be fully connected. We use graph networks with 50 hidden dimension on both node and edge. ELU as activation functions. Each model takes and 8 steps of inference for 25 object and 36 object cases respectively. The difficulty of this problem that for each object, there are 16 ways/configurations to overlap with another object. Each position configuration can contain N candidates. If N is larger than 1, there will be confusion, and models need to solve other objects first to provide more context information. The task in general needs model to perform iterative modification of nodes content and avoid false messages.
Experiment results: Table 2b shows the performance of each model measured by the classification accuracy for each object. Our proposed Policy Message Passing (PMP) model and its variants achieve a large performance boost over the baselines, demonstrating that there exists a strong need for this kind of dynamical reasoning in complex tasks. The models with fixed structure and rigid aggregation

---

Under review as a conference paper at ICLR 2020
Models
Acc(%)
Kendall-tau
2x2
3x3
4x4
5x5
2x2
3x3
4x4
5x5
Mena et (2018)
1.0
.9
.79
1.0
.96
.88
.78
PMP
1.0
1.0
.99
.99
1.0
1.0
.99
.99
(a) Illustration of the image puzzle solving task. The example image is from visual genome.
(b) We compare model's performance with state-of-the-art deep learning based puzzle solving model on Celcha dataset.
Figure 3: Image puzzle solving problem(left) and results compared with state-of-the-an method on Celeba dataset(right).
processes tend to not learn or generalize well. Attention based models slightly alleviate that problem, but are not able to perform consistent and strategic reasoning over objects.
4.1.2 IMAGE PUZZLE SOLVING ON BENCHMARKS
Task design and datasets: Next we move on to large-scale benchmark datasets with real images containing complex visual information. We test model the Jigsaw Puzzle solving task for real images. Given an image with size H x W, we divide the image into x d non-overlapping patches. The d2 patches are un-ordered and need be reassembled into the original image. We use two datasets to mainly test our model: (1) Visual Genome The Visual Genome dataset contains 64346 images for training and 43903 images for testing. is often used in image based scene graph generation tasks, indicating that there exists very rich interactions and relationships between visual elements the image. We test the models on three different puzzle sizes: 3 x 3, 4, and 6 (2) COCO dataset We use the COCO dataset (2014 version) that contains 82783 images for training and 40504 images for testing. We set up three tasks, 3 x 3,
and 6 x for evaluation.
Evaluation metric and model implementation: To evaluate the models' performance, we use per- patch classification score over the d² classes and measure the Kendall-tau correlation score between predicted patch order and the ground-truth order. For all graph models, we use 50 hidden dimensions on both nodes and edges. Models will perform d + steps inference. For all baseline methods, we use 200 dimensions for nodes and messages, while still remain 50 dimensions for main model.
Models
Accuracy($))
Kendall-tau
3x3
4x4
6x6
3x3
4x4
6x6
random
11.11
6.25
2.78
GNN
93.86
77.37
50.81
94.54
82.54
74.55
GNN-attention
91.29
81.36
68.39
92.70
86.56
79.11
RRN
89.91
78.14
62.52
85.33
84.46
76.63
NRI
87.63
81,93
69.01
89.12
86.67
79.78
PMP
98.31
97.96
90.53
99.27
98.67
96.01
Table 1: Performance results on COCO dataset, measured by per-patch classification accuracy and correlation score Kendall-tau. We use Kendall-tau 100 here for better comparison. Results are shown across different puzzle sizes.
Experiment results: Tables [ and 4a summarize the results of all models across varied task settings. Our proposed models consistently outperform baseline models by a 10% 20% margin, even when baseline models have much larger capacity on the graphs. This is further indication that having powerful inference process is crucial to deep graph-structured models.
Analysis on number of inference steps and size of function set: inference steps and number of functions in function set on our models, shown in 4b We found that empirically a function set of size is enough for message diversity. For inference step analysis, we test our PMP model on 6 x puzzles and found with 6 steps the model can already achieve good performance. Similar behaviours are found for bascline models too. We only plot our main model in the figure.
We further examine the impact of
7

---

Under review as a conference paper at ICLR 2020
Models
Accuracy(%)
Kendall-tau
3x3
4x4
6x6
3x3
4x4
6x6
random
11.11
6.25
2.78
GNN
82.83
72.46
61.22
85,47
79.94
79.58
GNN-attention
86.87
77.35
71.27
88.75
85.51
83.35
RRN
85.60
77.27
69.23
88.07
83.31
78.50
NRI 87.63
73.51
70.62
89.37
80.06
79.91
PMP
97.92
96.74
94.61
98.58
98.07
97.05
(a) Performance results on Visual Genome dataset, measured by per-patch classification accuracy and correlation score Kendall-tau. Results are shown across different puzzle sizes.
(b) Analysis our model on num- ber of inference steps and number of functions.
Figure 4: Performance on Visual Genome(left) and model analysis plots(right).
Comparison with state-of-the-art puzzle solving method: We compared our method with state- of-the-art deep learning based image puzzle solving on the CelebA dataset. The results are shown in Table 3b) Our model shows near perfect puzzle solving results on 2 x 2, 3 x 3,4 x 4 and 5 x 5 settings.
4.2 SOCIAL NETWORK CLASSIFICATION WITH NOISY EDGES
We further inspect models' ability on handling noisy edges on large scale graphs. Current graph neural network benchmark datasets on social networks, such as Cora (Sen et al. (2008)), heavily rely well caliberated edge matrix aggregation process are less, compare to more general cases where adjacency matrix information are often noisy or missing. In this experiment, we compare our model's performance with two state-of- the-art graph-structured models: (1) Graph Convolutional Networks (GCN) and (2) Graph Attention Networks (GAT) standard benchmark Cora. Instead of using only the well designed adjacency matrix information, we also generate perturbation to the matrix by adding { (%50, %100, %200) Bb] more noisy edges, [E] is the number of edges in the original graph. For implementation, we use the official release of the codes on two baseline models and default settings. In our proposed model, we follow the same hyper-parameters graph networks and uses recurrent network agent with 32 hidden dimensions. Results summarized in table 2 show that our model is more robust noisy edges in performing inference over large scale graphs.
strong prior information for inference. The burden
Models
Noisy edges 100%
50%
200%
GCN
26.55 + 1.3
23.53 + 1.44
22.62 + 1.84
GAT
58.83 + 1.35
45.82
+ 2.55
34.53 + 0.45
PMP
65.37 + 1.36
61.42 + 1.31
50.3 = 1.13
Table 2: The performance of node classification for Cora dataset under varied noisy edge settings. The experiment follows the standard transductive setup in Yang et al. (2016).
5 CONCLUSION
Reasoning over graphs can be formulated as a learnable process in Bayesian framework. We described a reasoning process that takes as input a graph and generates a distribution over messages that could be passed propagate data over the graph. Both the functional form of the messages and the parameters that control the distribution over these messages are learned. Learning these parameters can be achieved via a variational approximation to the marginal distribution over provided graph label. Future possibilities include adapting our model to use a more general set of functions where some of them is not differentiable.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 39-48, 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: Akl::0800.11211 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016.
pp.
Zhiwei Deng, Arash Vahdat, Hexiang Hu, and Greg Mori. Structure inference machines: Recurrent neural networks for analyzing relations in group activity recognition. In Computer Vision and Puttern Recognition (CVPR), 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances neural information processing systems, pp. 2224-2232, 2015.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data.
arXiv preprint arXiv: arXiv:1506.00 50600563, 2015.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. arXiv preprint arXiv:1802.04668) 2018.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks.
arXiv preprint arXiv: wee:::699000000 2016.
Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected crfs with gaussian edge potentials. In Advances in neural information processing systems, pp. 109-117, 2011.
John Lafferty, Xiaojin Zhu, and Yan Liu. Kernel conditional random fields: representation and clique selection. In Proceedings of the twenty-first international conference on Machine learning, pp. 64.
ACM, 2004.
Alex M Lamb, Anirudh Goyal Alias Parth Goyal, Ying Zhang, Saizheng Zhang, Aaron C Courville, and Yoshua Bengio. Professor forcing: A new algorithm for training recurrent networks. In Advances In Neural Information Processing Systems, pp. 4601-4609, 2016.
Tian Lan, Yang Wang, Weilong Yang, Stephen Robinovitch, and Greg Mori. Discriminative latent models for recognizing contextual group activities. IEEE Transactions Pattern Analysis and Machine Intelligence, 34(8):1549-1555 1562,, 2011.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural 2015.
networks. arXiv preprint
Joseph Marino, Yisong Yue, and Stephan Mandt. Iterative amortized inference. arXiv preprint arXiv: /807.09300 2018.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snock. Learning latent permutations with gumbel-sinkhom networks. arXiv preprint arXiv:1802.08660 2018.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, 2011.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ran Collective classification in network data. Al magazine, 29(3):93-93, 2008

---

Under review as a conference paper at ICLR 2020
Iya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. In Advances neural information processing systems, pp. -112,, 2014.
Charles Sutton, Andrew McCallum, et al. An introduction to conditional random fields. Foundations and Trends() in Machine Learning, 4(4):267-373, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 5998-60000 Curran Associates, Inc., 2017. URL URLhttp: you- sreed.pp..
//papers wwpps.rs.iip..ommmm..m..mm wttpapppcccppprre//eeeeeep 7181 attention-is
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky. Tree-based reparameterization frame- work for analysis of sum-product and related algorithms. IEEE Transactions on information theory, 1925):1120-1 1246 2003.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 7794-7803, 2018.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv preprint arXiv: 1603, (166600886,,, 2016.
Jonathan S Yedidia, William T Freeman, and Yair Weiss. Generalized belief propagation, In Advances in neural information processing systems, pp. 689-695, 2001.
10


Reviews:
[{"review_id": "rygh-IRtdH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces policy message passing: a graph neural network with multiple message types and an inference mechanism that assigns messages of a particular type to edges in a recurrent fashion. Experiments on visual reasoning tasks and on a noisy citation network classification task indicate competitive performance.\n\nThere are many interesting ideas in this paper and I believe that the overall approach/idea has merit and is interesting for the community. In its current state, however, the paper has issues in terms of clarity of writing, technical and notational mistakes, unclear experimental settings and unclear implementation of baseline models, and needs a major revision, hence I recommend reject. This feedback is mostly meant as an encouragement to “polish” the ideas outlined in the paper and their presentation, as I believe that these can be quite impactful, if presented well and once all technical issues have been addressed.\n\nDiscussion of the main idea outlined in this paper: \n———————————————————————\nThe proposed dynamic message passing procedure (termed “reasoning agents” in the paper) can be understood as an extension of Neural Relational Inference (NRI; Kipf et al., ICML 2018), where a Gumbel softmax-based attention mechanism in parallel softly assigns a particular message function per edge in the graph. The main difference to NRI is that this is done sequentially over multiple message passing steps in the graph, whereas NRI (in the training phase) only performs one single such step (for all edges in the graph). \n\nGetting this to work well in practice is a challenging problem, as sequential sampling steps can accumulate biases in the approximate inference scheme. The authors propose to address this issue in a number of ways: the attention mechanism per edge is coupled over time steps via a local hidden state and coupled to all other edges via a global hidden state (this is novel), a vector of ones is added to the action probabilities and subsequently re-normalized to act as a regularizer (this appears to be a hack), they use a learned prior distribution instead of a fixed prior as in NRI, and lastly, the authors introduce a mixed sampling strategy which mixes samples from the (learned) prior distribution for edge types and the proposal distribution while re-weighing the objective with importance sampling weights — for this last contribution (mixing + reweighing) the description in the paper misses some details (how precisely is the mixing done over the course of training?).\n\nClarity, technical correctness, experimental evaluation\n———————————————————————————\n* The paper contains a lot of spelling mistakes and grammatical errors, making it difficult to read.\n* Notational issues: Eq 3 is unclear (no node/edge indices provided, function arguments unspecific — all three functions have the same arguments); Eq. 8/9 switches between posteriors p, true posteriors \\pi^* (what’s the difference from p?) and priors \\pi without explanation— a derivation would be helpful. Eq. 10 only places a prior on the first time step — where does this come from? A derivation would be helpful.\n* “Belief propagation or other neural message passing frameworks define a delta function where the prior is deterministic and fixed” -> this is not the case for NRI\n* What temperature is used for the Gumbel softmax distribution? Does the forward pass use “hard” (straight-through trick) or soft activations?\n* Eq. 5: Why condition B on the indices i and j? This will likely not generalize to new edges\n* Eq. 6: What is the motivation for adding a vector of ones? Wouldn't it be possible to achieve the desired regularization effect by increasing the softmax temperature?\n* How are the edge and global hidden states initialized?\n* The explanation for the mixed sampling procedure is unclear, please elaborate (potentially use an appendix)\n* What are the train/val/test splits, how are hyper parameters optimized in all experiments?\n* Why implement attention-based GNN baselines with sigmoid gates even though you cite Transformers and Graph Attention Networks (GAT) in this paragraph? I suspect that multi-head dot product attention (default for Transformers/GAT) instead of sigmoid gating would perform much better.\n* Please explain the architecture / experimental setting used in the GNN and RRN baselines in an appendix. Please also clarify how you use NRI (recurrent version, Markovian version etc.)\n* “Where am I” task: the model setup paragraph is unclear\n* Figure 3a: the example provided is not d x d (but 3x4 in terms of # puzzle pieces)\n* Ablation studies: please consider including experiments that analyze how the proposed model performs without global state, without the added prior (vector of ones), without the mixed sampling procedure, without recurrence and with different numbers of functions per edge.\n\n\nOther comments:\n* Please consider familiarizing yourself with the \\citep command in LaTeX for parenthetical citations to avoid sequences of closing parentheses. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "rJe6pYX-cS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a policy message passing algorithm for graph neural network where both node & edge energy functions and the message passing procedure are treated in a unified manner as outputs of neural nets. In particular, the message passing procedures for individual edges are individualized (i.e. not homogeneous) while a common memory pool is also shared among these procedures. It also aims at doing message passing in the distribution level instead of singling out a particular message passing rule. The idea is new (to my understanding) and interesting. Empirical results demonstrate the usefulness of the proposed methods. On the other hand, the main concerns are:\n*Only a rough idea is introduced and discussed, then followed by some nice practical results. In the middle, there is lacking of concrete execution of the proposed idea. The devil could lie in the details. \n*many details are missing. Throughout the paper, it is not clear at all how the message functions and the inference procedure functions (or called reasoning agents) are realized in practice. Also I do not see the practical implementation would be made publicly accessible. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkeMtm2WcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Policy Message Passing, a Bayesian GNN which models edge message passing as a mixture distribution with corresponding coefficient generated by a learnable prior defined on graph state. I think the motivation is reasonable and the experiment on Jigsaw Puzzle is impressive. But the writing and other experiments can be further improved, as detailed below.\n\nSec 3.1: What does ```````+1 mean in Eq. (6)?\n\nSec 3.2: The choice for the variational distribution q is not mentioned. Is q a parametric model (e.g., NN) or non-parametric? It is hard to connect prior, posterior and variational posterior in Sec 3.2 to the reasoning agent/message formulation in Sec 3.1. I suggest reformulating Sec 3.1 & 3.2 to give a thorough presentation of the training objective, model structure and optimization details of PMP.\n\nModeling graph using graph neural network with Bayesian framework has been investigated in several papers, e.g., [1-2]. They also take a probabilistic perspective. I think this paper should discuss the connections to previous Bayesian GNNs and compare their performance with PMP at least in Sec 4.2. Besides, GNN with edge information (e.g., [3]) has also been investigated in several papers. According to my understanding, PMP can also be regarded as a GNN with latent edge information (modeled with a learnable prior and inferred with a variational posterior). So I think adding discussion/experiment to them can better support your claim.\n\nAs for the experiment part, my major concern is whether the comparison with other models (e.g., GCN and GAT) is fair. It seems that the number of parameters of PMP is much larger than GCN and GAT. Could you provide details for the model size and the training/inference time cost?\n\nSec 4.2. What's the performance of PMP when no noisy edges is added? \n\n[1] Bayesian graph convolutional neural networks for semi-supervised classification, AAAI 2019\n[2] Bayesian Semi-supervised Learning with Graph Gaussian Processes, NIPS 2018\n[3] Exploiting Edge Features for Graph Neural Networks, CVPR 2019\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was reviewed by 3 experts, who recommend Weak Reject, Weak Reject, and Reject. The reviewers were overall supportive of the work presented in the paper and felt it would have merit for eventual publication. However, the reviewers identified a number of serious concerns about writing quality, missing technical details, experiments, and missing connections to related work. In light of these reviews, and the fact that the authors have not submitted a response to reviews, we are not able to accept the paper. However given the supportive nature of the reviews, we hope the authors will work to polish the paper and submit to another venue.
Decision: Reject