Title: DYNAMIC GRAPH MESSAGE PASSING NETWORKS

Abstract: Modelling long-range dependencies is critical for scene understanding tasks in computer vision. Although CNNs have excelled in many vision tasks, they are still limited in capturing long-range structured relationships as they typically consist of layers of local kernels. A fully-connected graph is beneficial for such modelling, however, its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity compared to related works modelling a fully-connected graph. This is achieved by adaptively sampling nodes in the graph, conditioned on the input, for message passing. Based on the sampled nodes, we dynamically predict node-dependent filter weights and the affinity matrix for propagating information between them. Using this model, we show significant improvements with respect to strong, state-of-theart baselines on three different tasks and backbone architectures. Our approach also outperforms fully-connected graphs while using substantially fewer floating-point operations.

1. INTRODUCTION:

Capturing long-range dependencies is crucial for complex scene understanding tasks such as semantic segmentation, instance segmentation and object detection. Although convolutional neural networks (CNNs) have excelled in a wide range of scene understanding tasks (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016) , they are still limited by their ability to capture these long-range interactions. To improve the capability of CNNs in this aspect, a recent popular model Non-local networks (Wang et al., 2018) proposes a generalisation of the attention model of (Vaswani et al., 2017) and achieves significant advance in several computer vision tasks.

Non-local networks essentially model pairwise structured relationships among all feature elements in a feature map to produce the attention weights which are used for feature aggregation. Considering each feature element as a node in a graph, Non-local networks effectively model a fully-connected feature graph and thus have a quadratic inference complexity with respect to the number of the feature elements. This is infeasible for dense prediction tasks on high-resolution imagery, as commonly encountered in semantic segmentation (Cordts et al., 2016) . Moreover, in dense prediction tasks, capturing relations between all pairs of pixels is usually unnecessary due to the redundant information contained within the image (Fig. 1 ). Simply subsampling the feature map to reduce the memory requirements is also suboptimal, as such naïve subsampling would result in smaller objects in the image not being represented adequately.

To tackle the complexity issue of the fully connected models, graph convolution networks (GCNs) (Kipf & Welling, 2017; Gilmer et al., 2017) , which propagate information along graphstructured input data, can alleviate the computational issues of non-local networks to a certain extent. However, this stands only if local neighbourhoods are considered for each node. Employing such local-connected graphs means that the long-range contextual information needed for complex vision tasks such as segmentation and detection (Rabinovich et al., 2007; Oliva & Torralba, 2007) will only be partially captured. Along this direction, GraphSAGE (Hamilton et al., 2017) introduces an efficient graph learning model based on a graph sampling method. However, the sampling considers a spatial uniform sampling strategy and is not dependant on the feature nodes. Thus the modelling capacity is also restricted as it basically assumes a static input graph where the neighbours for each node are fixed and the filter weights are shared among all nodes. "boathouse", one needs to consider the "boat" and the "water" next to it. Fully-connected message passing models (a) are able to obtain this information, but are prohibitively expensive. Furthermore, they capture a lot of redundant information (i.e."trees" and "sky"). Locally-connected models (b) are more efficient, but miss out on important context. Our proposed approach (c), dynamically samples a small subset of relevant feature nodes based on a learned dynamic sampling scheme, i.e. the learned position-specific random walk (indicated by the white dashed arrow lines), and also dynamically predicts filter weights and affinities (indicated by unique edge and square colors.), which are both conditioned on the sampled feature nodes. We demonstrate the proposed model on the tasks of semantic segmentation, object detection and instance segmentation on the challenging Cityscapes (Cordts et al., 2016) and COCO (Lin et al., 2014) datasets. We achieve clearly better performance than the fully-connected Non-local model, while using substantially fewer floating point operations (FLOPs). Significantly, one variant of our model with dynamic filters and affinities (i.e. the second dynamic property) achieves similar performance to Non-local while only using 9.4% of its FLOPs and 25.3% of its parameters. Furthermore, "plugging" our module into existing networks, we show considerable improvements with respect to strong, state-of-the-art baselines on three different tasks and backbone architectures.

2. RELATED WORK:

An early technique for modelling context for computer vision tasks involved conditional random fields. In particular, the DenseCRF model (Krhenbhl & Koltun, 2011) was popular as it modelled interactions between all pairs of pixels in an image. Although such models have been integrated into neural networks (Chen et al., 2015; Zheng et al., 2015; Arnab et al., 2016; Xu et al., 2017) , they are limited by the fact that the pairwise potentials are based on simple handcrafted features, and mostly model on the discrete label space, thus not directly applicable in the feature learning task in which the feature variables are typically considered continuous. Coupled with the fact that CRFs are computationally expensive, CRFs are no longer used for most computer vision tasks.

A complementary technique for increasing the receptive field of CNNs was to use dilated convolutions (Chen et al., 2015; Yu & Koltun, 2016; Chen et al., 2017) . Other modifications to the convolution operation include deformable convolution (Dai et al., 2017; Zhu et al., 2019) , which learns the offset with respect to a predefined grid. While the deformable strategy could learn the random walks of the feature nodes, it only considers very local field, and the filters are shared across all convolutional positions. In contrast, our dynamic sampling aims to sample over the whole feature graph to obtain a large receptive field, and also the predicted affinities and the weights for message passing are position specific and conditioned on the dynamically sampled nodes. Our model is thus able to better capture position-based semantic context to enable more effective message passing among feature nodes.

The idea of graph node sampling has previously been explored in GraphSAGE (Hamilton et al., 2017) . GraphSAGE simply uniformly samples nodes. In contrast, our sampling strategy is learned based on the node features. Specifically, we first sample the nodes uniformly in the spatial dimension, and then dynamically predict walks of each node conditioned on the node features. Therefore the sampling in our model is input-dependant and clearly different from GraphSAGE. Furthermore, GraphSAGE does not consider our second important property, i.e. the dynamic prediction of the affinities and the message passing kernels, and it does not explore the challenging detection and segmentation tasks.

We also note that Jia et al. (2016) developed an idea of "dynamic convolution", that is predicting a dynamic convolutional filter for each feature position. More recently, Wu et al. (2019) further reduced the complexity of this operation in the context of natural laguage processing with lightweight group convolutions. Unlike (Jia et al., 2016; Wu et al., 2019) , we present a graph-based formulation, and jointly learn dynamic weights and dynamic affinities, which are conditioned on an adaptively sampled neighbourhood for each feature node in the graph using the proposed dynamic sampling strategy for effective message passing.

3. DYNAMIC GRAPH MESSAGE PASSING NETWORKS:



3.1. PROBLEM DEFINITION AND NOTATION:

Given an input feature map interpreted as a set of feature vectors, i.e. F = {f i } N i=1 with f i ∈ R 1×C , where N is the number of pixels and C is the feature dimension respectively, our goal is to learn a set of refined latent feature vectors H = {h i } N i=1 by utilising hidden structured information among the feature vectors at different pixel locations. H has the same dimension as the observation F. To learn such structured representations, we convert the feature map into a graph domain by constructing a feature graph G = {V, E, A} with V as its nodes, E as its edges and A as its adjacency matrix. Specifically, the nodes of the graph are represented by the latent feature vectors, i.e. V = {h i } N i=1 , and A ∈ R N ×N is a binary or learnable matrix with self-loops describing the connections between nodes. In this work, we propose a novel dynamic graph message passing network Gilmer et al. (2017) for deep representation learning, which refines each graph feature node by passing messages on the graph G. Different from existing message passing neural networks considering a fully-or locally-connected static graph (Wang et al., 2018; Gilmer et al., 2017) , we propose a dynamic graph network model with two dynamic properties, i.e. dynamic sampling of graph nodes to approximate the full graph distribution, and dynamic prediction of node-conditioned filter weights and affinities, in order to achieve more efficient and effective message passing.

3.2. GRAPH MESSAGE PASSING NEURAL NETWORKS FOR DEEP REPRESENTATION LEARNING:

Message passing neural networks (MPNNs) (Gilmer et al., 2017) present a generalised form of graph neural networks such as graph convolution networks (Kipf & Welling, 2017), gated graph sequential networks (Li et al., 2015) and graph attention networks (Veličković et al., 2018) . In order to model structured graph data, in which latent variables are represented as nodes on an undirected or directed graph, feed-forward inference is performed through a message passing phase followed by a readout phase upon the graph nodes. The message passing phase usually takes T iteration steps to update feature nodes, while the readout phase is for the final prediction e.g. graph classification with updated nodes. In this work, we focus on the message passing phase for learning efficient and effective feature refinement, since well-represented features are critical in all downstream tasks. The message passing phase consists of two steps, i.e. a message calculation step M t and a message updating step U t . Given a latent feature node h (t) i at an iteration t, for computational efficiency, we consider a locally connected node field with v i ⊂ V and v i ∈ R (K×C) , where K N is the number of sampled nodes in v i . Thus we can define the message calculation step for node i operated locally as

m (t+1) i = M t A i,j , {h (t) 1 , • • • , h (t) K }, w j = j∈N (i) A i,j h (t) j w j , with A i,j = A[i, j], (1)

where A i,j describes the connection relationship i.e. the affinity between latent nodes h (t) i and h

(t) j , N (i) denotes a self-included neighborhood of the node h (t)

i which can be derived from v i and w j ∈ R C×C is a transformation matrix for message calculation on the hidden node h message updating function U t is applied to update the node h (t) i with a linear combination of the calculated message and the observation feature f i at the node position i as:

EQUATION

where α m i of a learnable parameter for scaling the message, and the operation σ(•) is a non-linearity function e.g. ReLU. By iteratively performing message passing on each node with T steps, we obtain a refined feature map H (T ) as output.

3.3. FROM A FULLY-CONNECTED GRAPH TO A DYNAMIC SAMPLED GRAPH:

A fully-connected graph typically contains many connections and parameters, which thus naturally brings redundancy in the connections, and also makes the network optimisation more difficult especially when dealing with limited training data. Therefore, as in Eq. 1, a local node connection field is considered in the graph message passing network, in order to substantially reduce the computational overhead of large fully-connected graphs. However, in various computer vision tasks, such as detection and segmentation, learning deep representations capturing both local and global receptive fields is important for the model performance (Rabinovich et al., 2007; Oliva & Torralba, 2007) . To maintain a large receptive field while utilising much fewer parameters than the fullyconnected setting, we further explore dynamic sampling strategies in our proposed graph message passing network. We develop a uniform sampling scheme, which we extend to a predicted random walk sampling scheme which aims to reduce the redundancy found in a fully-connected graph. This sampling is performed in a dynamic fashion, meaning that for a given node h i , we aim to sample an optimal subset of v i from V to update h i via message passing as shown in Fig. 2 .

Multiple uniform sampling for dynamic receptive fields. Uniform sampling is a commonly used strategy for graph node sampling (Leskovec & Faloutsos, 2006) based on Monte-Carlo estimation. To approximate the distribution of V, we consider a set of S uniform sampling rates ϕ with ϕ = {ρ q } S q=1 , where ρ q is a sampling rate. Let us assume that the latent feature nodes are located in a P -dimensional space R P . For instance, P = 2 for images considering the xand y-dimensions of the image plane. For each latent node h i , a total of K neighbouring nodes are sampled from R P . The receptive field of v i is thus determined by ρ q and K. Note that the sampling rate ρ q corresponds to the "dilation rate" often used in convolution (Yu & Koltun, 2016) and is thus able to capture a large receptive field whilst maintaining a small number of connected nodes. Thus we can achieve much lower computational overhead compared with fully-connected message passing in which typically all N nodes are used when one of the nodes is updated. Each node receives S complementary messages from distinct receptive fields for updating as where β q is a weighting parameter for the message from the q-th sampling rate. A q denotes a formed adjacent matrix under a sampling rate ρ q , with A q i,j , w q j and N q (i) defined analogously. The uniform sampling scheme acts as a linear sampler based on spatial distribution while not considering the original feature distribution of the hidden nodes, i.e. sampling independently of the node features. Eq. 2 can still be used to update the nodes.

EQUATION

Learning position-specific random walks for node-dependant adaptive sampling. To take into account the feature data distribution when sampling nodes, we further present a random walk strategy upon the uniform sampling. Walks around the uniformly sampled nodes could sample the graph in a non-linear and adaptive manner, and we believe that it could facilitate learning better approximation of the original feature distribution. The "random" here refers to the fact that the walks are predicted in a data-driven fashion from stochastic gradient descent. Given a set of uniformly sampled nodes v q i ∈ R K×C under a sampling rate ρ q , the random walk of each node is further estimated based on the feature data of the sampled node set. Given the P -dimensional space where the nodes distribute (P = 2 for images), let us denote d q j ∈ R P ×1 as predicted walks from a uniformly sampled node h j with j ∈ N q (i). The node walk prediction can then be performed using a matrix transformation as

EQUATION

where W q i,j ∈ R P ×(K×C) and b q i,j ∈ R P ×1 are the matrix transformation parameters, which are learned separately for each node v q i . With the predicted walks, we can obtain a new set of adaptively sampled nodes v q i , and generate the corresponding adjacent matrix A q , which can be used to calculate the messages as

EQUATION

where the function (•) is a bilinear sampler (Jaderberg et al., 2015) which samples a new feature node h

(t) j around h (t)

j given the predicted walk d q j and the whole set of graph vertexes V.

3.4. JOINT LEARNING OF NODE-CONDITIONED DYNAMIC FILTERS AND AFFINITIES:

In the message calculation formulated in Eq. 5, the set of weights {w q j } K j=1 of the filter is shared for each adaptively sampled node field v q i . However, since each v q i essentially defines a node-specific local feature context, it is more meaningful to use a node-conditioned filter to learn the message for each hidden node h (t) i . In additional to the filters for the message calculation in Eq. 5, the affinity A i,j of any pair of nodes h (t) i and h (t) j could be also be predicted and should also be conditioned on the node field v q i , since the affinity reweights the message passing only in v q i . As shown in Fig. 3 , we thus use matrix transformations to simultaneously estimate the dynamic filter and affinity which are both conditioned on v q i , {w q j , A A q i,j = softmax c (A

EQUATION

EQUATION

)

where the function softmax c (•) denotes a softmax operation along the channel axis, which is used to perform a normalisation on the estimated affinity G×C+1) are matrix transformation parameters. To reduce the number of the filter parameters, we consider the group transformation (Chollet, 2017) with a set of G groups split from the total C feature channels, and G C, i.e. each group of C/G feature channels shares the same set of filter parameters. For the dynamic weights, we relax them in the prediction without using non-linearity after the matrix transformation. The predicted dynamic filter weights and the affinities are used in Eq. 5 for dynamic message calculation.

EQUATION

3.5. MODULAR INSTANTIATION:

Figures 2 and 3 shows how our proposed dynamic graph message passing network (DGMN) can be implemented in neural networks. The proposed module accepts a single feature map F as input, which can be derived from any CNN layer. H (0) denotes an initial state of the latent feature map, H, and is initialised with F. H and F have the same dimension, i.e. F, H ∈ R H×W ×C , where H, W and C are the height, width and the number of feature channels of the feature map respectively. We first define a set of S uniform sampling rates (we show two uniform sampling rates in Fig. 2 for clarity). The uniform and the random walk sampler sample the nodes from the full graph and return the node indices for subsequent dynamic message calculation (DMC) in Fig. 3 . The matrix transformation W q i,j to estimate the node random walk in Eq. 4 is implemented by a 3×3 convolution layer. Note that other sampling strategies could also be flexibly employed in our framework. The sampled feature nodes are processed along two data paths: one for predicting the node-dependant dynamic affinities A q ∈ R H×W ×K and another path for dynamic filters w q ∈ R H×W ×K×G where K (e.g. , 3 × 3) is the kernel size for the receiving node. The matrix transformation W k,A i,j used to jointly predict the dynamic filters and affinities in Eq 6 is implemented by a 3 × 3 convolution layer. Message M q ∈ R H×W ×C corresponding to the q-th sampling rate is then scaled to perform a linear combination with the observation feature map F, to produce a refined feature map H (1) as output. To balance performance and efficiency, as in existing graph-based feature learning models (Wang et al., 2018; Chen et al., 2019; Lin et al., 2015) , we also perform T = 1 iteration of message updating.

4. EXPERIMENTS:



4.1. EXPERIMENTAL SETUP:

Tasks and Datasets. We evaluate our proposed model on two challenging public benchmarks, i.e. Cityscapes (Cordts et al., 2016) for semantic segmentation, and COCO (Lin et al., 2014) for object detection and instance segmentation. Both datasets have hidden test sets which are evaluated on a public evaluation server. We follow the standard protocol and evaluation metrics used by these public benchmarks. More details can be found in Appendix A.2.

Baseline models. For semantic segmentation on Cityscapes, our baseline architecture is Dilated-FCN (Yu & Koltun, 2016) with a ResNet-101 backbone pretrained on ImageNet. A 3 × 3 convolution layer, together with batch normalisation and ReLU is used after the backbone to produce a dimensionreduced feature map of 512 channels which is then fed into the proposed DGMN module as input. For the task of object detection and instance segmentation on COCO, our baseline is Mask-RCNN (He et al., 2017; Massa & Girshick, 2018) with FPN and ResNet/ResNeXt (He et al., 2016; Xie et al., 2017) as a backbone architecture. We insert one or multiple random initialised DGMN modules into the backbone for deploying our approach for the feature learning. Across all tasks and datasets, we consider Non-local networks (Wang et al., 2018) as an additional baseline. We use single scale and single model testing for all the evaluation experiments on COCO without using other complementary performance boosting tricks.

To have a direct comparison with the Deformable Convolution method (Dai et al., 2017; Zhu et al., 2019) , we consider two baselines: (i) deformable message passing, which is a variant of our model using the deformable convolution for message calculation without using the proposed dynamic sampling and dynamic weights/affinities strategies, and (ii) the original deformable method which replaces the convolutional operations as in (Dai et al., 2017) .

To demonstrate the effectiveness of the proposed different components of our model, we conduct ablation studies of: (i) DGMN w/ DA, which adds the dynamic affinity (DA) strategy on the DGMN base model; (ii) DGMN w/ DA+DW, adding the proposed dynamic weights (DW) prediction upon DGMN w/ DA; (iii) DGMN w/ DA+DW+DS, which is our full model with the dynamic sampling (DS) scheme added upon DGMN w/ DA+DW. Note that DGMN Base was described in Sec. 3.2, DS in Sec. 3.3, and DA and DW in 3.4. Implementation details. When predicting dynamic filter weights, we used the grouping parameter G = 4. For our experiments on Cityscapes, the sample rates are set to ϕ = {1, 6, 12, 24, 36}. For experiments on COCO, we use smaller sampling rates of ϕ = {1, 4, 8, 12}. The effect of this hyperparameter is studied in Appendix A.3, whislt additional implementation and training details are described in Appendix A.2.

4.2. MODEL ANALYSIS:

Effectiveness of the dynamic sampling strategy. Table 1a shows quantitative results of semantic segmentation on the Cityscapes validation set. DGMN w/ DA+DW+DS clearly outperforms DGMN w/ DA+DW on the challenging segmentation task, meaning that the feature-conditioned adaptive sampling based on learned random walks is more effective compared with spatial uniform sampling strategy when selecting nodes. More importantly, all variants of our module for both semantic segmentation and object detection that use dynamic sampling (Table 1a and Table 2 ) achieve higher performance than a fully-connected model (i.e. Non-local Wang et al. (2018) ) with substantially fewer FLOPs. This emphasises the performance benefits of our dynamic graph sampling model.

Effectiveness of joint learning the dynamic filters and affinities. As shown in Table 1a , DGMN w/ DA is 1.5 points better than Dilated FCN baseline with only a slight increase in FLOPs and parameters, showing the benefit of using predicted dynamic affinities for reweighting the messages in message passing. By further employing the estimated dynamic filter weights for message calculation, the performance increases substantially from a mIoU of 76.5% to 79.1%, which is almost the same as the 79.2% of the Non-local model (Wang et al., 2018) . Furthermore, our approach only uses 9.4% of the FLOPs and 25.3% of the parameters compared to Non-local. These results clearly demonstrate our motivation of joint learning the dynamic filters and dynamic affinities from sampled graph nodes.

mIoU (%):

Params FLOPs Dilated FCN (Yu & Koltun, 2016) 75.0 --+ Deformable (Zhu et al., 2019) 78.2 +1.31M +12.34G + ASPP (Chen et al., 2017) 78.9 +4.42M +38.45G + Non-local (Wang et al., 2018) 79 Comparison with other baselines. We clearly outperform the ASPP module of Deeplab v3 (Chen et al., 2017) which also considers increasing the receptive field via using various dilation rates. Notably, we beat the direct competitor Non-local (Wang et al., 2018) which models a fully-connected graph whilst using only 39% of the FLOPs of Non-local. This suggests that a fully-connected graph models redundant information, and further confirms the performance and efficiency of our model.

For fair comparison with Non-local (Wang et al., 2018) as well as other alternatives on COCO, we insert one random initialised DGMN module right before the last residual block of res4 (Table 2 ).

GCNet and CCNet both aim to reduce the complexity of the fully connected graph model Non-local. Our proposed DGMN model substantially improves upon these strong baselines and alternatives. Figure 6 further shows the validation curves of our method and different baselines in terms of the metric AP. Our method is consistently better than the Non-local and Mask R-CNN baseline throughout the training procedure.

Effectiveness of multiple DGMN modules. We further show the effectiveness of our approach for representation learning by inserting multiple of our DGMN modules into the ResNet-50 backbone. Specifically, we add our full DGMN module after all 3 × 3 conv layers in res5 which we denote as "C5". The second part of Table 2 shows that our model significantly improves upon the Mask R-CNN baseline with the improvements of 2.4 points for the AP box on object detection, and 1.6 points for the AP mask on instance segmentation. We insert the GCNet module (Cao et al., 2019) in the same places for comparison, and our model achieves clearly better performance. A straightforward comparsion to the deformable method of Zhu et al. (2019) is the deformable message passing baseline in which we disable the proposed dyanamic sampling and the dynamic weights and affinities learning strategies.

In Table 2 , our model significantly improves the deformable message passing method, which is a direct evidence of the effectiveness of joint modeling the dynamic sampling and dynamic filters and affinities for more effective feature learning. Furthermore, we consider the original Deformable Conv method (Zhu et al., 2019) in C5, which is complementary to our model since it is plugged before 3 × 3 layers to replace the convolution operations. Our approach also achieves better performance compared with it. 

4.3. COMPARISON TO STATE-OF-THE-ART:

Performance on Cityscapes test set. Table 1b compares our approach with state-of-the-art methods on Cityscapes. Note that all methods are trained using only the fine annotations and evaluated on the public evaluation server as test-set annotations are withheld from the public. As shown in the table, DGMN (ours) achieves an mIoU of 81.8%, surpassing all previous works. Among competing methods, GloRe (Chen et al., 2019) , Non-local (Wang et al., 2018) , CCNet (Huang et al., 2019) and DANet (Fu et al., 2019) are the most related to us as they all based on graph neural network modules. Note that we followed common practice and employed several complementary strategies used in semantic segmentation to boost performance, including Online Hard Example Mining (OHEM) (Fu et al., 2019) , Multi-Grid (Chen et al., 2017) and Multi-Scale (MS) ensembling (Zhao et al., 2017) .

The contribution of each strategy on the final performance is reported in the Appendix A.3.

Performance on COCO 2017 test set. Table 3 presents our results on the COCO test-dev set, where we compare to various existing strong backbones. By inserting DGMN into all layers of C4 and C5, we substantially improve the performance of Mask R-CNN, observing a gain of of 3.0 and 2.2 points on the AP box and the AP mask of object detection and instance segmentation respectively. We observe similar improvements when using the ResNet-101 or ResNeXt-101 backbones as well, showing that our proposed DGMN module generalises to multiple backbone architectures. Furthermore, we compare ours with previous state-of-the-arts shown in Appendix A.4.

5. CONCLUSION:

We proposed Dynamic Graph Message Passing Networks, a novel graph neural network module that dynamically determines the graph structure for each input. It learns dynamic sampling of a small set of relevant neighbours for each node, and also predicts the weights and affinities dependant on the feature nodes to propagate information through this sampled neighbourhood. This formulation significantly reduces the computational cost of static, fully-connected graphs such as Non-local networks (Wang et al., 2018) which contain many redundancies. This is exhibited by the fact that we are able to clearly improve upon the accuracy of Non-local, and several state-of-art baselines, on three complex computer vision problems. C5 of ResNet-101, DGMN (C5) outperforms the Mask R-CNN baseline with 1.6 points on the metric AP box and 1.2 points on the metric AP mask . On ResNeXt-101, DGMN (C5) also improves by 1.5 and 0.9 points on the AP box and the AP mask , respectively. 

:



Figures and Tables:

(a) Fully-connected message passing (b) Locally-connected message passing (c) Dynamic graph message passing

Figure 1: Contextual information is crucial for complex scene understanding tasks. To recognise the

Figure 2: Overview of our proposed dynamic graph message passing network (DGMN). The neighbourhood used to update the feature representation of each node (we show a single node with a red square) is predicted dynamically conditioned on each input. This is done by first uniformly sampling (denoted by "US") a set of S neighbourhoods around each node. Each neighbourhood contains K (e.g. 3 × 3) sampled nodes. Here, the blue nodes were sampled with a low sampling rate, and the green ones with a high sampling rate. Walks are predicted (conditioned on the input) from these uniformly sampled nodes, denoted by the s symbol representing the random walk sampling operation described in Sec. 3.3. DMC1, • • • , DMCS and β1, • • • , βS denotes S dynamic message calculation operations and S message scaling parameters, respectively. The DMC module is detailed in Figure 3. The symbol ⊕ indicates an element-wise addition operation.

Figure 3: Schematic illustration of the proposed dynamic message passing calculation (DMC) module. Thesmall red square indicates the receiving node whose message is calculated from its neighbourhood, i.e. the sampled K (e.g. 3×3) features nodes. The module accepts a feature map as input and produces its corresponding message map. The symbol * denotes group convolution operation using the dynamically predicted and position specific group kernels and affinities.

Figure 4: Visualisation of the nodes sampled via learning the random walks with our network. The red point indicates a receiving node i. Different color families (i.e. yellow and blue) indicate the learned position specific weights and affinities of the sampled nodes. Different colors in the same family show the sampled nodes with different sampling rates for the same receiving node.

Figure 5: Qualitative examples of the semantic segmentation on Cityscapes (the first row), and object detection and instance segmentation on COCO (the second row).

Figure 8: Qualitative examples of the object detection task on the COCO validation dataset. The first and third rows are the results from the Mask R-CNN baseline(Massa & Girshick, 2018;He et al., 2017). The second and fourth row are the detection results from our DGMN approach.

Results comparison for the semantic segmentation task on Cityscapes. In the ablation study, all the methods are evaluated in single-scale mIoU and with a ResNet-101 backbone. For the state-of-art comparison, all the methods are trained on the fine-annotation training and validation sets.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Backbone</td><td>mIoU (%)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>PSPNet (Zhao et al., 2017)</td><td>R101</td><td>78.4</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>PSANet (Zhao et al., 2018)</td><td>R101</td><td>80.1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>DenseASPP (Yang et al., 2018)</td><td>D161</td><td>80.6</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>.2</td><td>+2.88M</td><td>+73.33G</td><td>GloRe (Chen et al., 2019)</td><td>R101</td><td>80.9</td></tr><tr><td colspan="4">+ DGMN w/ DA</td><td/><td/><td/><td/><td colspan="2">76.5</td><td>+0.57M</td><td>+5.32G</td><td>Non-local (Wang et al., 2018)</td><td>R101</td><td>81.2</td></tr><tr><td colspan="5">+ DGMN w/ DA+DW</td><td/><td/><td/><td colspan="2">79.1</td><td>+0.73M</td><td>+6.88G</td><td>CCNet (Huang et al., 2019)</td><td>R101</td><td>81.4</td></tr><tr><td colspan="6">+ DGMN w/ DA+DW+DS</td><td/><td/><td colspan="2">80.4</td><td>+3.02M</td><td>+28.45G</td><td>DANet (Fu et al., 2019)</td><td>R101</td><td>81.5</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>DGMN (Ours)</td><td>R101</td><td>81.8</td></tr><tr><td/><td/><td/><td colspan="8">(a) Ablation study on the validation set.</td><td>(b) State-of-the-art comparison on the test set.</td></tr><tr><td/><td>0.45</td><td/><td/><td/><td/><td/><td/><td/><td/><td>AP b AP b 50 AP b 75 AP m AP m 50 AP m 75</td></tr><tr><td/><td>0.4</td><td/><td/><td/><td/><td/><td/><td/><td/><td>Mask R-CNN baseline</td><td>37.8</td><td>59.1</td><td>41.4</td><td>34.4</td><td>55.8</td><td>36.6</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>+ Non-local (Wang et al., 2018)</td><td>38.5</td><td>60.0</td><td>41.8</td><td>34.9</td><td>56.5</td><td>37.3</td></tr><tr><td/><td>0.35</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>+ GCNet (Cao et al., 2019)</td><td>38.1</td><td>60.0</td><td>41.2</td><td>34.9</td><td>56.5</td><td>37.2</td></tr><tr><td>AP</td><td>0.25 0.3</td><td/><td/><td/><td/><td/><td/><td/><td/><td>+ CCNet (Huang et al., 2019) + Deformable Message Passing</td><td>39.3 38.7</td><td>-60.4</td><td>-42.4</td><td>36.1 35.0</td><td>-56.9</td><td>-37.4</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">DGMN (box)</td><td/><td>+ DGMN</td><td>39.5</td><td>61.0</td><td>43.3</td><td>35.7</td><td>58.0</td><td>37.9</td></tr><tr><td/><td>0.2</td><td/><td/><td/><td/><td/><td colspan="2">DGMN (mask) Non-local (box)</td><td/><td>+ GCNet (C5) (Cao et al., 2019)</td><td>38.7</td><td>61.1</td><td>41.7</td><td>35.2</td><td>57.4</td><td>37.4</td></tr><tr><td/><td>0.15</td><td/><td/><td/><td/><td/><td colspan="3">Non-local (mask) Mask R-CNN (box)</td><td>+ Deformable (C5) (Zhu et al., 2019) 39.9</td><td>-</td><td>-</td><td>34.9</td><td>-</td><td>-</td></tr><tr><td/><td>0.1</td><td/><td/><td/><td/><td/><td colspan="3">Mask R-CNN (mask)</td><td>+ DGMN (C5)</td><td>40.2</td><td>62.0</td><td>43.4</td><td>36.0</td><td>58.3</td><td>38.2</td></tr><tr><td/><td>0</td><td>10</td><td>20</td><td>30</td><td>40</td><td>50</td><td>60</td><td>70</td><td>80</td><td>90</td></tr><tr><td/><td/><td/><td/><td colspan="3">Epochs (K)</td><td/><td/><td/></tr><tr><td colspan="11">Figure 6: Validation curves of AP box</td></tr><tr><td colspan="11">and AP mask on COCO for Mask-RCNN</td></tr><tr><td colspan="11">baseline, Non-local and the proposed</td></tr><tr><td colspan="11">DGMN. The number of training epochs</td></tr><tr><td colspan="2">is 90K.</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Quantitative results of different models on the COCO 2017 validation set for object detection (AP b ) and instance segmentation (AP m ). C5 denotes inserting DGMN after all 3 × 3 convolutional layers in res5. All methods are based on the Mask R-CNN with ResNet-50 as backbone.

Table content: <table/>

Quantitative results via plugging our DGMN module on different backbones on the COCO 2017 test-dev set for object detection (AP box ) and instance segmentation (AP mask ).

Table content: <table><tr><td/><td>Backbone</td><td>AP box</td><td>AP box 50</td><td>AP box 75</td><td colspan="2">AP mask AP mask 50</td><td>AP mask 75</td></tr><tr><td>Mask R-CNN baseline</td><td/><td>38.0</td><td>59.7</td><td>41.5</td><td>34.6</td><td>56.5</td><td>36.6</td></tr><tr><td>+ DGMN (C5)</td><td>ResNet 50</td><td>40.2</td><td>62.5</td><td>43.9</td><td>36.2</td><td>59.1</td><td>38.4</td></tr><tr><td>+ DGMN (C4, C5)</td><td/><td>41.0</td><td>63.2</td><td>44.9</td><td>36.8</td><td>59.8</td><td>39.1</td></tr><tr><td>Mask R-CNN baseline</td><td>ResNet 101</td><td>40.2</td><td>61.9</td><td>44.0</td><td>36.2</td><td>58.6</td><td>38.4</td></tr><tr><td>+ DGMN (C5)</td><td/><td>41.9</td><td>64.1</td><td>45.9</td><td>37.6</td><td>60.9</td><td>40.0</td></tr><tr><td>Mask R-CNN baseline</td><td>ResNeXt 101</td><td>42.6</td><td>64.9</td><td>46.6</td><td>38.3</td><td>61.6</td><td>40.8</td></tr><tr><td>+ DGMN (C5)</td><td/><td>44.3</td><td>66.8</td><td>48.4</td><td>39.5</td><td>63.3</td><td>42.1</td></tr></table>

Quantitative results via applying the proposed DGMN module into different strong backbone networks for object detection and instance segmentation on COCO 2017 validation set.

Table content: <table><tr><td>Model</td><td>Backbone</td><td colspan="2">AP box AP box 50</td><td>AP box 75</td><td colspan="2">AP mask AP mask 50</td><td colspan="2">AP mask 75</td></tr><tr><td>Mask R-CNN baseline + DGMN (C5)</td><td>ResNet-101</td><td>40.1 41.7</td><td>61.7 63.8</td><td>44.0 45.7</td><td>36.2 37.4</td><td>58.1 60.4</td><td colspan="2">38.3 39.8</td></tr><tr><td colspan="2">Mask R-CNN baseline ResNeXt-101 + DGMN (C5)</td><td>42.2 43.7</td><td>63.9 65.9</td><td>46.1 47.8</td><td>37.8 38.7</td><td>60.5 62.1</td><td colspan="2">40.2 41.3</td></tr><tr><td colspan="3">A.4 STATE-OF-ART COMPARISON ON COCO</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>Backbone</td><td colspan="3">AP box AP box 50 AP box 75</td><td colspan="2">AP mask AP mask 50</td><td>AP mask 75</td></tr></table>

Peer review (iclr2020):
This work explores methods that capture long-range dependencies for computer vision tasks. It uses a graph-based formulation to view the problem, and proposes to perform input-dependent sampling and learn input-dependent weights and affinities for message passing. Pros: 1. The proposed method is clearly introduced 2. The differences between the proposed method and related work are clearly explained and demonstrated through ablation study. 3. The visualization in Figure 4 backups the authors* claims. Cons: 1. It is not clear why the graph-based formulation is better, making it hard to compare the proposed method with (Jia et al., 2016; Wu et al., 2019). More details should be provided. 2. The results of Non-local (Wang et al., 2018) in Table 2 is not consistent with the original paper. 3. In all experiments, is the training setting the same for all the models involved?