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. 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 are used for sequential inference (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 et al. (2018) ). Also, a large bulk of works are developed in reinforcement learning for sequential inference of the environment with partial observation, non-future aware states, and world dynamics. Graph-structured models are another class of models that heavily rely on local observations and sequential inference. It contains nodes and message functions with partial information, the final output of model relies on a sequence of communication operations which transforms the nodes information dynamically over iterations. A general formulation of learning graph-structured models is maximizing the likelihood: The objective describes the process where it takes in the information x over a graph, starts from initial states s 0 and maps to the target output y. This process involves two key components, message functions F and inference process P . Message function 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 et al. (2012) ). Kernelized potential functions (Lafferty et al. (2004) ), gaussian energy functions (Krähenbühl & Koltun (2011) ), or semantic-driven potential functions (Lan et al. (2011) ) are developed in varied cases to adapt to specific tasks. Deep graph neural networks generalizes the message functions to neural networks. There are a variety of function types developed such as graph convolution operations (Kipf & Welling (2016) ), attention-based functions (Veličković et al. (2017) ), gated functions (Li et al. (2015) ; Deng et 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. (2001) ), and tree-reweighted message passing ( Wainwright et al. (2003) ). However, there has not been many research in developing powerful inference process in 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, we take a different tack and instead propose to represent the inference process modeled by a neural network P φ : The neural network P φ 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 or 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 a 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 a variational inference based framework for learning the inference models. Thirdly, We empirically demonstrate that having a powerful inference machine can enhance the prediction in graph-structured models, especially on difficult reasoning tasks, or graphs with noisy edges. Reasoning over graphs can be formulated as a learnable process in a Bayesian framework. We described a reasoning process that takes as input a graph and generates a distribution over messages that could be passed to 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.
An probabilistic inference algorithm driven by neural network for graph-structured models This paper introduces policy message passing, a graph neural network with an inference mechanism that assigns messages to edges in a recurrent fashion, indicating competitive performance on visual reasoning tasks.