
%==========================================================================
\section{Pseudocode of Backpropagation of ISGMR and TRWP}

Due to the limited space of the main paper, we provide
the pseudocode of backpropagation of ISGMR and TRWP in this appendix, in
Algorithms~\ref{alg:isgmr-back}-\ref{alg:trwp-back} respectively.

\setlength{\textfloatsep}{0.5ex}
\begin{algorithm}
\KwIn{Partial energy parameters $\{\theta_{i,j}\}$, gradients of final costs
$\mathbf{\nabla c} = \{\nabla c_{i}{(\lambda)}\}$, set of nodes $\mathcal{V}$,
edges $\mathcal{E}$, directions $\mathcal{R}$, indices $\{p^r_{k,i}{(\lambda)}\}$,
$\{q^r_{k,i}\}$, iteration number $K$.
We replace $\nabla m^{r,k+1}$ by $\nabla \hat{m}^r$ and
$\nabla m^{r,k}$ by $\nabla m^r$ for simplicity.}
\KwOut{Gradients $\{\nabla \theta_{i}, \nabla \theta_{i,j}(\cdot, \cdot)\}$.}
\caption{Backpropagation of ISGMR} \label{alg:isgmr-back}
$\nabla \mathbf{m}^{\mathbf{r}} \gets \nabla \mathbf{\Theta_i} \gets \nabla
\mathbf{c}$, $\nabla \mathbf{\Theta_{i,j}} \gets 0$
% \tcp*[f]{back \eqref{eq:isgmr-aggregation}}
\tcp*[f]{back Eq. (7)}
\\
$\nabla \hat{\mathbf{m}}^{\mathbf{r}} \gets \nabla \mathbf{m}^{\mathbf{r}}$
\tcp*[f]{back message updates} \\
\For{\textup{iteration $k \in \{K, ..., 1\}$}}{
  $\nabla \mathbf{m}^{\mathbf{r}} \gets 0$ \tcp*[f]{zero-out} \\
    \ForAll(\tcp*[f]{\textbf{parallel}}){\textup{directions $r \in
\mathcal{R}$}}{
      \ForAll(\tcp*[f]{\textbf{parallel}}){\textup{scanlines $t$ in direction
$r$}}{
        \For(\tcp*[f]{\textbf{sequential}}){\textup{node $i$ in scanline $t$}}{
          $\lambda^* \gets q^r_{k,i} \in \mathcal{L}$ \tcp*[f]{extract index}
\\
          $\nabla \hmesnew{r}{i}{\lambda^*} \mathrel{-}= \sum_{\lambda \in
\mathcal{L}}{\nabla \hmesnew{r}{i}{\lambda}}$
% \tcp*[f]{back \eqref{eq:isgmr-norm}}
\tcp*[f]{back Eq. (5)}
\\
          \For{\textup{label $\lambda \in \mathcal{L}$}}{
            $\mu^* \gets p^r_{k,i}{(\lambda)} \in \mathcal{L}$ \tcp*[f]{extract
index} \\
            $\nabla \theta_{i-r}{(\mu^*)} \mathrel{+}= \nabla
\hmesnew{r}{i}{\lambda}$
% \tcp*[f]{back \eqref{eq:isgmr}}
\tcp*[f]{back Eq. (9)}
\\
            $\nabla \hmesnew{r}{i-r}{\mu^*} \mathrel{+}= \nabla
\hmesnew{r}{i}{\lambda}$ \\
            $\nabla \mesnew{d}{i-r}{\mu^*} \mathrel{+}= \nabla
\hmesnew{r}{i}{\lambda}, \forall d \in \mathcal{R} \setminus \{r,r^-\}$ \\
            $\nabla \theta_{i-r,i}(\mu^*, \lambda) \mathrel{+}= \nabla
\hmesnew{r}{i}{\lambda}$ \\
          }
        }
      }
    $\nabla \hat{\mathbf{m}}^r \gets 0$ \tcp*[f]{zero-out} \\
  }
  $\nabla \mathbf{m^r} \mathrel{+}= \nabla \hat{\mathbf{m}}^\mathbf{r}$
\tcp*[f]{gather history gradients} \\
  $\nabla \hat{\mathbf{m}}^\mathbf{r} \gets \nabla \mathbf{m^r}$ \tcp*[f]{back
message updates after iteration} \\
}
\end{algorithm}

\setlength{\textfloatsep}{0.5ex}
\begin{algorithm}
\KwIn{Partial energy parameters $\{\theta_{i,j}\}$, gradients of final costs
$\mathbf{\nabla c} = \{\nabla c_{i}{(\lambda)}\}$,  tree decomposition coefficients
$\{\rho_{i,j}\}$, set of nodes $\mathcal{V}$, edges $\mathcal{E}$, directions
$\mathcal{R}$, indices $\{p^r_{k,i}{(\lambda)}\}$, $\{q^r_{k,i}\}$, iteration number $K$.}
\KwOut{Gradients $\{\nabla \theta_{i}, \nabla \theta_{i,j}(\cdot, \cdot)\}$.}
\caption{Backpropagation of TRWP} \label{alg:trwp-back}
$\nabla \mathbf{m}^{\mathbf{r}} \gets \nabla \mathbf{\Theta_i} \gets
d\mathbf{c}$, $d\mathbf{\Theta_{i,j}} \gets 0$
% \tcp*[f]{back \eqref{eq:isgmr-aggregation}}
\tcp*[f]{back Eq. (7)}
\\
\For{\textup{iteration $k \in \{K, ..., 1\}$}}{
  \For(\tcp*[f]{\textbf{sequential}}){\textup{direction $r \in \mathcal{R}$}}{
    \ForAll(\tcp*[f]{\textbf{parallel}}){\textup{scanlines $t$ in direction
$r$}}{
      \For(\tcp*[f]{\textbf{sequential}}){\textup{node $i$ in scanline $t$}}{
        $\lambda^* \gets q^{r}_{k,i} \in \mathcal{L}$ \tcp*[f]{extract index}
\\
        $\nabla \mesnew{r}{i}{\lambda^*} \mathrel{-}= \sum_{\lambda \in
\mathcal{L}}{\nabla \mesnew{r}{i}{\lambda}}$
% \tcp*[f]{back \eqref{eq:isgmr-norm}}
\tcp*[f]{back Eq. (5)}
\\
        \For{\textup{label $\lambda \in \mathcal{L}$}}{
          $\mu^* \gets p^{r}_{k,i}{(\lambda)} \in \mathcal{L}$ \tcp*[f]{extract
index} \\
          $\nabla \theta_{i-r}{(\mu^*)} \mathrel{+}= \rho_{i-r,i} \nabla
\mesnew{r}{i}{\lambda}$
% \tcp*[f]{back \eqref{eq:trwp}}
\tcp*[f]{back Eq. (11)}
\\
          $\nabla \mesnew{d}{i-r}{\mu^*} \mathrel{+}= \rho_{i-r,i} \nabla
\mesnew{r}{i}{\lambda}, \forall d \in \mathcal{R}$ \\
          $\nabla \mesnew{r^-}{i-r}{\mu^*} \mathrel{-}= \nabla \mesnew{r}{i}{\lambda}$
\\
          $\nabla \theta_{i-r,i}(\mu^*, \lambda) \mathrel{+}= \nabla
\mesnew{r}{i}{\lambda}$ \\
        }
      }
    }
    $\nabla \mathbf{m}^{r} \gets 0$ \tcp*[f]{zero-out} \\
  }
}
\end{algorithm}

%==========================================================================
\section{Maintaining Energy Function in Iterations}
With the same notations in Eq.\myblue{(1)} and Eq.\myblue{(9)} in the
main paper, let a general energy function in a MRF defined as

\begin{equation}
\label{eq:supp-energy-function}
\begin{aligned}
  E(\mathbf{x} | \mathbf{\Theta}) = \sum_{i \in \mathcal{V}} \theta_{i}(x_i)
  + \sum_{(i, j) \in \mathcal{E}} \theta_{i,j}(x_i, x_j)\ .
\end{aligned}
\end{equation}
In the standard SGM and ISGMR, given a node $i$ and an edge from nodes $j$
to $i$, the message will be updated at $k$th iteration as follows,

\begin{equation}
\centering
\label{eq:supp-isgmr}
\begin{aligned}
\mesnew{r,k+1}{i}{\lambda} = \min_{\mu \in \mathcal{L}}
\big(\theta_{i-r}{(\mu)}
+ \theta_{i-r,i}(\mu,\lambda)
+ \mesnew{r,k+1}{i-r}{\mu} &+ \sum_{d \in \mathcal{R} \setminus \{r,r^-\}}
\mesnew{d,k}{i-r}{\mu}\big) \ .
\end{aligned}
\end{equation}
In \myfig{fig:supp-passing}, however, if we add a term $m_{i}{(\lambda)}$
to node $i$ at label $\lambda$ via $m_{ji}{(\lambda)}$
from node $j$ to node $i$ at label $\lambda$, the same value should
be subtracted along all edges connecting this node $i$, that is $\forall (i,j)
\in \mathcal{E}$, in order to maintain the
same \eqref{eq:supp-energy-function} in optimization.
This supports the exclusion of $r^-$ from $\mathcal{R}$ in \eqref{eq:supp-isgmr}.
This is important for multiple iterations because the non-zero messages after
the 1st iteration, as additional terms, will change the energy function via
\eqref{eq:supp-isgmr}.
Hence, a simple combination of many standard SGMs will change the energy
function due to the lack of the subtraction above.

\begin{figure}[t]
\centering
\includegraphics[width=0.25\linewidth]{passing.eps}
\caption{Energy function maintained in iterative message passing.
When adding a term $m_{ji}{(\lambda)}$ to node $i$ at label $\lambda$,
the same value should be subtracted on all edges connecting node $i$ at
label $\lambda$.}
\label{fig:supp-passing}
\end{figure}

%==========================================================================
\section{Indexing First Nodes by Interpolation}
Tree graphs contain horizontal, vertical, and diagonal (including symmetric,
asymmetric wide, and asymmetric narrow) trees, shown in
\myfig{fig:supp-paths}.
Generally, the horizontal and vertical trees are for 4-connected graphs,
symmetric trees are for 8-connected graphs, and asymmetric
trees are for more
than 8-connected graphs, resulting in different ways of indexing the
first nodes
for parallelization. In the following, we denote an image size with height
$H$ and
width $W$, coordinates of the first node in vertical and horizontal
directions
as $p_h$ and $p_w$ respectively, and scanning steps in vertical and
horizontal
directions as $S_h$ and $S_w$ respectively.

\begin{figure}
\centering
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{horizontal.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{vertical.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{lr.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{rl.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{lr_2.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{lr_3.eps}
\caption{}
\end{subfigure}
\caption{Multi-direction message passing(forward passing
in 6 directions).
(a) horizontal trees. (b) vertical trees. (c) symmetric trees
from up-left to down-right.
(d) symmetric trees from up-right to down-left. (e) asymmetric
narrow trees with height
and width steps $S=(S_h, S_w)=(2, 1)$. (f) asymmetric wide trees
with $S=(1, 2)$.}
\label{fig:supp-paths}
\end{figure}

\noindent \textbf{Horizontal and vertical graph trees.} Coordinate
of the first node
of a horizontal and vertical tree, $p=(p_h, p_w)$, can be presented
by ($p_h,0$) and
($0,p_w$) respectively in the forward pass, and ($p_h, W-1$) and
($H-1, p_w$) respectively
in the backward pass.

\noindent \textbf{Symmetric and asymmetric wide graph trees.}
Coordinate of the first
node $p=(p_h, p_w)$ is calculated by
%
\begin{equation}
\label{eq:supp-wide}
\begin{aligned}
  N &= W + (H-1)*\text{abs}(S_w)\ , \\
  p_w &= \left[0:N-1\right] - (H-1) * \max{(S_w, 0)}\ , \\
  p_h &= \begin{cases} 0 & \text{ if } S_h > 0\ ,\\
           H - 1 & \text{otherwise}\ ,
         \end{cases}
\end{aligned}
\end{equation}
where $N$ is tree number, $\text{abs}(*)$ is absolution, and $T_s$
is shifted indices of trees.

\textbf{Asymmetric narrow graph trees.} Coordinate of the first node $p$ by
interpolation is calculated by

\begin{equation}
\label{eq:supp-narrow}
\begin{aligned}
  c_1 &= \text{mod}(T_s, \text{abs}(S_h))\ , \\
  c_2 &= \frac{\text{float}(T_s)}{\text{float}(\text{abs}(S_h))}\ , \\
  p_h &= \begin{cases}
           \text{mod}(\text{abs}(S_h) - c_1, \text{abs}(S_h)) & \text{ if } S_w > 0\ ,\\
           c_1 & \text{otherwise}\ ,
         \end{cases} \\
  p_h &= H - 1 - p_h \text{ if } S_h < 0\ , \\
  p_w &= \begin{cases}
           \text{ceil}(c_2) & \text{ if } S_w > 0\ ,\\
           \text{floor}(c_2) & \text{otherwise}\ ,
         \end{cases}
\end{aligned}
\end{equation}
where $\text{mod}(*)$ is modulo, $\text{floor}(*)$ and $\text{ceil}(*)$ are two
integer approximations, $\text{float}(*)$ is data conversion for single-precision
floating-point values, and the rest share the same notations in \eqref{eq:supp-wide}.

Although ISGMR and TRWP are parallelized over individual trees, message updates
on a tree are sequential. The interpolation for asymmetric diagonals avoids as many
redundant scanning as possible, shown in \myfig{fig:supp-head}. This is more practical
for realistic stereo image pairs that the width is much larger than the height.

\begin{figure}
\begin{subfigure}[b]{0.4\textwidth}
\centering
\includegraphics[width=0.8\textwidth]{head_a.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.25\textwidth}
\centering
\includegraphics[width=0.75\textwidth]{head_b.eps}
\caption{}
\end{subfigure}
~
\begin{subfigure}[b]{0.25\textwidth}
\centering
\includegraphics[width=0.75\textwidth]{head_c.eps}
\caption{}
\end{subfigure}
\caption{Interpolation in asymmetric graph trees in forward passing. (a)
asymmetric wide trees with steps $S=(1, 2)$. (b) asymmetric narrow trees with $S=(2, 1)$.
(c) asymmetric narrow trees with $S=(3, 1)$. Red circles are first nodes of trees;
large circles are within image size; small circles are interpolated; $o$ is axes center.
Coordinates of interpolations in (a) are integral; in (b)-(c) round to the nearest
integers by \eqref{eq:supp-narrow}.}
\label{fig:supp-head}
\end{figure}

%==========================================================================
\section{Differentiability of ISGMR}
Below, we replace $m^{r,k}$ by $m^r$ and $m^{r,k+1}$ by $\hat{m}^r$
for simplicity. This is because from the practical implementation, messages
in direction $r$ should be updated instead of allocating new
memories in each iteration to avoid GPU memory increase. Thus, we only use
two variables $m^r$ and $\hat{m}^r$ for messages before and after an iteration.

%--------------------------------------------------------------------------
\subsection{Explicit Representation of Forward Propagation}
Since message update in ISGMR relies on recursively updated messages $\hat{\mathbf{m}}^r$
in each scanning direction $r$ and messages $\mathbf{m}^r$ from all the other directions
updated in the previous iteration, an explicit ISGMR message update is

\begin{equation}
\label{eq:supp-isgmr-explicit}
\begin{aligned}
\hmesnew{r}{i}{\lambda} &= \min_{\mu \in \mathcal{L}}\, \big(\theta_{i-r}{(\mu)}
+ \theta_{i-r, i}(\mu, \lambda)
+ \hmesnew{r}{i-r}{\mu} 
+ \sum_{d \in \mathcal{R} \setminus \{r, r^-\}} \mesnew{d}{i-r}{\mu} \big), \\
&\quad \quad \forall i \in \mathcal{V}, \forall \lambda \in \mathcal{L},
\forall r \in \mathcal{R}\ .
\end{aligned}
\end{equation}
Applying message reparametrization by

\begin{equation}
\label{eq:supp-isgmr-norm}
\begin{aligned}
\hmesnew{r}{i}{\lambda} = \hmesnew{r}{i}{\lambda} - \min_{k \in \mathcal{L}}
\hmesnew{r}{i}{k}, \quad \forall i \in \mathcal{V}, \forall \lambda \in \mathcal{L},
\forall r \in \mathcal{R}\ .
\end{aligned}
\end{equation}
After updating messages in \textbf{all directions within an iteration},
we assign the updated message $\hat{\mathbf{m}}$ to $\mathbf{m}$ by

\begin{equation}
\label{eq:supp-isgmr-renew}
\begin{aligned}
m_{i}{(\lambda)} = \hat{m}_{i}{(\lambda)}, \quad \forall i \in \mathcal{V},
\forall \lambda \in \mathcal{L}\ .
\end{aligned}
\end{equation}
Eventually, \textbf{after all iterations}, unary potentials and updated messages
from all directions will be aggregated by

\begin{equation}
\label{eq:supp-isgmr-aggregate}
\begin{aligned}
c_{i}{(\lambda)} = \theta_{i}{(\lambda)} + \sum_{d \in \mathcal{R}}
\mesnew{d}{i}{\lambda}, \quad \forall i \in \mathcal{V}, \forall \lambda \in \mathcal{L}\ .
\end{aligned}
\end{equation}

Different from optimization with winner-takes-all for labelling in learning by
$\mathbf{x}_{i} = \text{argmin}_{\lambda \in \mathcal{L}}c_{i}{(\lambda)},
\forall i \in \mathcal{V}$, a regression with disparity confidences calculated
by the final costs is used to fit with the real-valued ground truth
disparities $\mathbf{g}=\{g_i\}, \forall i \in \mathcal{V}$. Generally, the
disparity confidence $f_{i}{(\lambda)}$ with a normalization such as SoftMin() is represented by

\begin{equation}
\label{eq:supp-isgmr-confidence}
\begin{aligned}
f_{i}{(\lambda)} = \text{SoftMin}(c_{i}{(\lambda)}), \quad \forall i \in
\mathcal{V}, \forall \lambda \in \mathcal{L}\ ,
\end{aligned}
\end{equation}
and the regression for real-valued disparity $\mathbf{d}=\{d_i\},
\forall i \in \mathcal{V}$ is

\begin{equation}
\label{eq:supp-isgmr-regression}
\begin{aligned}
d_{i} = \sum_{\lambda \in \mathcal{L}} \lambda f_{i}{(\lambda)},
\forall i \in \mathcal{V}\ .
\end{aligned}
\end{equation}

The loss function $L(\mathbf{d}, \mathbf{g})$ in learning can be standard L1 or smooth L1
loss function.

%--------------------------------------------------------------------------
\subsection{Derivations of Differentiability}

Now we do backpropagation at $k$th iteration for learnable parameters $\{ \theta_i$, $\theta_{i,j} \}$.
With the same notations in Section~\myblue{4} in the main paper, $\{ p^{r}_{k,i}{(\lambda)} \}$
and $\{ q^r_{k,i} \}$ are indices stored in the forward propagation from message minimization and
reparameterization respectively, and $\nabla * = dL / d*$.

\subsubsection{Gradients of unary potentials} \

\noindent \textbf{Proposition:} Gradients of unary potentials $\{\theta_{i}{(\lambda)}\}$ are represented by

\begin{equation}
\label{eq:supp-gradient-unary}
\begin{aligned}
\nabla \theta_{i}{(\lambda)}
&= \nabla c_{i}{(\lambda)} + \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}} \left. \nabla
\hmesnew{r}{i+r}{v} \right \vert_{\lambda = p^r_{k,i+r}{(v)}} \\
&= \nabla c_{i}{(\lambda)} + \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}} \sum_{\mu \in \mathcal{L}}
\Big( \left. \nabla \hmesnew{r}{i+2r}{\mu} \right \vert_{v = p^r_{k,i+2r}{(\mu)}} \\
&\quad \quad + \sum_{d \in \mathcal{R} \setminus \{r, r^{-}\}} \left.
\nabla \mesnew{d}{i+r+d}{\mu} \right \vert_{v = p^d_{k,i+r+d}{(\mu)}} \left. \Big ) \right \vert_{\lambda = p^r_{k,i+r}{(v)}}\ .
\end{aligned}
\end{equation}

\noindent \textit{Derivation:}

The backpropagation from \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-explicit} is

\begin{equation}
\label{eq:supp-isgmr-back-unary}
\begin{aligned}
\nabla \theta_{i}{(\lambda)}
&=\frac{dL}{d\theta_{i}{(\lambda)}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \frac{\partial L}{\partial d_{j}{(v)}}
\frac{\partial d_{j}{(v)}}{\partial f_{j}{(v)}} \frac{\partial f_{j}{(v)}}{\partial c_{j}{(v)}}
\frac{\partial c_{j}{(v)}}{\partial \theta_{i}{(\lambda)}}
& \tcp*[f]{back \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-confidence}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\Big ( \frac{\partial c_{j}{(v)}}{\partial \theta_{j}{(v)}}
\frac{\partial \theta_{j}{(v)}}{\partial \theta_{i}{(\lambda)}} + \sum_{r \in \mathcal{R}}
\frac{\partial c_{j}{(v)}}{\partial m^r_{j}{(v)}} \frac{\partial m^r_{j}{(v)}}{\partial \theta_{i}{(\lambda)}} \Big )
& \tcp*[f]{back \eqref{eq:supp-isgmr-aggregate}} \\
&= \nabla c_{i}{(\lambda)} + \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}}
\sum_{r \in \mathcal{R}} \nabla \mesnew{r}{j}{v} \frac{\partial \mesnew{r}{j}{v}}{\partial \theta_{i}{(\lambda)}}  \\
&= \nabla c_{i}{(\lambda)} + \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}}
\sum_{r \in \mathcal{R}} \nabla \mesnew{r}{j}{v} \frac{\partial \mesnew{r}{j}{v}}{\partial \hmesnew{r}{j}{v}}
\frac{\partial \hmesnew{r}{j}{v}}{\partial \theta_{i}{(\lambda)}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-renew}} \\
&= \nabla c_{i}{(\lambda)} + \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}}
\sum_{r \in \mathcal{R}} \nabla \hmesnew{r}{j}{v} \frac{\partial \hmesnew{r}{j}{v}}{\partial \theta_{i}{(\lambda)}}\ .
\end{aligned}
\end{equation}

With backpropagation of \eqref{eq:supp-isgmr-norm} using an implicit message reparametrization
with index $v^* = q^{r}_{k,j}$ at $k$th iteration, $\nabla \hmesnew{r}{j}{v}$ in the second term above is updated by

\begin{equation}
\label{eq:supp-isgmr-back-norm}
\begin{aligned}
\nabla \hmesnew{r}{j}{v}
& \gets
  \begin{cases}
    \nabla \hmesnew{r}{j}{v} & \text{ if } v \neq v^*\ , \\
     - \sum_{v^{'}\in \mathcal{L} \setminus v^*} \nabla \hmesnew{r}{j}{v^{'}} & \text{otherwise}\ .
  \end{cases}
\end{aligned}
\end{equation}

\noindent \textit{Derivation of \eqref{eq:supp-isgmr-back-norm}:}

Explicit representation of \eqref{eq:supp-isgmr-norm} is $\tilde{m}^{r}_{i}{(\lambda)} =
\hmesnew{r}{i}{\lambda} - \hmesnew{r}{i}{\lambda^{*}}$, where $\lambda^{*} = q^r_{k,i}$, then we have

\begin{equation}
\label{eq:supp-isgmr-back-norm-explicit}
\centering
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
&= \frac{\partial L}{\partial \hmesnew{r}{i}{\lambda}} \\
&= \sum_{i^{'} \in \mathcal{V}} \sum_{\lambda^{'} \in \mathcal{L}}
\frac{\partial L}{\partial \tilde{m}^r_{i^{'}}{(\lambda^{'})}}
\frac{\partial \tilde{m}^r_{i^{'}}{(\lambda^{'})}}{\partial \hmesnew{r}{i}{\lambda}}  \\
&= \sum_{i^{'} \in \mathcal{V}} \sum_{\lambda^{'} \in \mathcal{L}}
\frac{\partial L}{\partial \tilde{m}^r_{i^{'}}{(\lambda^{'})}}
\Big( \frac{\partial \tilde{m}^r_{i^{'}}{(\lambda^{'})}}{\partial \hmesnew{r}{i^{'}}{\lambda^{'}}}
\frac{\partial \hmesnew{r}{i^{'}}{\lambda^{'}}}{\partial \hmesnew{r}{i}{\lambda}}
+ \frac{\partial \tilde{m}^r_{i^{'}}{(\lambda^{'})}}{\partial \hmesnew{r}{i^{'}}{\lambda^{*}}}
\frac{\partial \hmesnew{r}{i^{'}}{\lambda^{*}}}{\partial \hmesnew{r}{i}{\lambda}} \Big) \\
&= \frac{\partial L}{\partial \tilde{m}^r_{i}{(\lambda)}} - \sum_{\lambda^{'} \in \mathcal{L}} \left.
\frac{\partial L}{\partial \tilde{m}_{i}{(\lambda^{'})}} \right \vert _{\lambda=\lambda^{*}} \\
&= \begin{cases}
     \nabla \tilde{m}^r_{i}{(\lambda)} & \text{ if } \lambda \neq \lambda^* \ ,\\
      - \sum_{\lambda^{'}\in \mathcal{L} \setminus \lambda^*} \nabla \tilde{m}^r_{i}{(\lambda^{'})} & \text{otherwise}\ .
   \end{cases}
\end{aligned}
\end{equation}
Back to the implicit message reparametrization with $\nabla \tilde{m}^r$ replaced
by $\nabla \hat{m}^r$, we have

\begin{equation}
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
&= \begin{cases}
     \nabla \hmesnew{r}{i}{\lambda} & \text{ if } \lambda \neq \lambda^* \ , \\
      - \sum_{\lambda^{'}\in \mathcal{L} \setminus \lambda^*} \nabla \hmesnew{r}{i}{\lambda^{'}} & \text{otherwise}\ .
   \end{cases}
\end{aligned}
\end{equation}

\noindent \textit{End of the derivation of \eqref{eq:supp-isgmr-back-norm}}. 

Next, we continue the backpropagation through \eqref{eq:supp-isgmr-explicit} for unary potentials as

\begin{equation}
\label{eq:supp-isgmr-back-message-unary}
\begin{aligned}
\nabla \theta_{i}{(\lambda)}
&= \nabla c_{i}{(\lambda)} + \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}}
\sum_{r \in \mathcal{R}} \nabla \hmesnew{r}{j}{v} \frac{\partial \hmesnew{r}{j}{v}}{\partial \theta_{i}{(\lambda)}} 
& \tcp*[f]{from \eqref{eq:supp-isgmr-back-unary}} \\
&= \nabla c_{i}{(\lambda)} + \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}}
\nabla \hmesnew{r}{i+r}{v} \frac{\partial \hmesnew{r}{i+r}{v}}{\partial \theta_{i}{(\lambda)}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-explicit} without recursion} \\
&= \nabla c_{i}{(\lambda)} + \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}} \left.
\nabla \hmesnew{r}{i+r}{v} \right \vert_{\lambda = p^r_{k,i+r}{(v)}}. \ & \tcp*[f]{satisfy argmin()
rule in \eqref{eq:supp-isgmr-explicit}}
\end{aligned}
\end{equation}

Derivation of $\nabla c_{i}{(\lambda)}$ by backpropagation from the loss function,
disparity regression, and SoftMin(), can be obtained by PyTorch autograd directly.
For the readability of derivations by avoiding using
$\{m^r_{i+r}(m^{r}_i(\theta_{i-r}{(\lambda)})), m^r_{i+2r}(m^r_{i+r}(m^{r}_i(\theta_{i-r}{(\lambda)}))), ...\}$, 
we do not write the recursion of gradients in the derivations. Below, we derive
$\nabla \hmesnew{r}{i+r}{v}$ in the backpropagation.

\subsubsection{Gradients of Messages} \

For notation readability, we first derive message gradient $\nabla \hmesnew{r}{i}{\lambda}$
instead of $\nabla \hmesnew{r}{i+r}{v}$.

\noindent \textbf{Proposition:} Gradients of messages $\{ \hmesnew{r}{i}{\lambda} \}$ are
represented by

\begin{equation}
\label{eq:supp-gradient-message}
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
= \sum_{v \in \mathcal{L}} \Big( \left. \nabla \hmesnew{r}{i+r}{v} \right \vert_{\lambda
= p^r_{k,i+r}{(v)}} + \sum_{d \in \mathcal{R} \setminus \{r, r^{-}\}} \left. \nabla m^d_{i+d}{(v)} \right \vert_{\lambda = p^d_{k,i+d}{(v)}} \Big )\ .
\end{aligned}
\end{equation}

\noindent \textit{Derivation:}

\begin{equation}
\label{eq:supp-isgmr-back-message}
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
&= \frac{dL}{d\hmesnew{r}{i}{\lambda}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\frac{\partial c_{j}{(v)}}{\partial \hmesnew{r}{i}{\lambda}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-confidence}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}}  \nabla c_{j}{(v)}
\sum_{d \in \mathcal{R}} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}}
\frac{\partial m^d_{j}{(v)}}{\partial \hmesnew{r}{i}{\lambda}}
& \tcp*[f]{back \eqref{eq:supp-isgmr-aggregate}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\sum_{d \in \mathcal{R}} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}}
\frac{\partial m^d_{j}{(v)}}{\partial \hmesnew{d}{j}{v}} \frac{\partial \hmesnew{d}{j}{v}}{\partial \hmesnew{r}{i}{\lambda}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-renew}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \hmesnew{r}{i}{\lambda}}\ ,
\end{aligned}
\end{equation}
then we update $\nabla \hmesnew{d}{j}{v}$ by \eqref{eq:supp-isgmr-back-norm} and continue as follows,

\begin{equation}
\label{eq:supp-isgmr-back-message-2}
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \hmesnew{r}{i}{\lambda}} 
& \tcp*[f]{from \eqref{eq:supp-isgmr-back-message}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \Big ( \sum_{\lambda^{'} \in \mathcal{L}}
\frac{\partial \hmesnew{d}{j}{v}}{\partial \hmesnew{d}{j-d}{\lambda^{'}}}
\frac{\partial \hmesnew{d}{j-d}{\lambda^{'}}}{\partial \hmesnew{r}{i}{\lambda}} \\
& \quad + \sum_{d^{'} \in \mathcal{R} \setminus \{d, d^{-}\}}
\sum_{\lambda^{'} \in \mathcal{L}} \frac{\partial \hmesnew{d}{j}{v}}{
\partial m^{d^{'}}_{j-d}{(\lambda^{'})}} \frac{\partial m^{d^{'}}_{j-d}{(\lambda^{'})}}{\partial \hmesnew{r}{i}{\lambda}} \Big )
& \tcp*[f]{back \eqref{eq:supp-isgmr-explicit}} \\
&= \sum_{v \in \mathcal{L}} \Big( \left. \nabla \hmesnew{r}{i+r}{v}
\right \vert_{\lambda = p^{r}_{k,i+r}{(v)}} \\
&\quad + \sum_{d \in \mathcal{R}} \sum_{d^{'} \in \mathcal{R} \setminus \{d, d^{-}\}}
\sum_{\lambda^{'} \in \mathcal{L}} \nabla \hmesnew{d}{j}{v}
\frac{\partial \hmesnew{d}{j}{v}}{\partial m^{d^{'}}_{j-d}{(\lambda^{'})}}
\frac{\partial m^{d^{'}}_{j-d}{(\lambda^{'})}}{\partial \hmesnew{r}{i}{\lambda}} \Big ) \ .
\end{aligned}
\end{equation}
Since $m^{d^{'}}_{j-d}{(\lambda^{'})}$ is differentiable by $\hmesnew{r}{i}{\lambda}$
due to \eqref{eq:supp-isgmr-renew} and, for ISGMR, message gradients in directions
except the current direction $r$ come from the next iteration (since in the forward
propagation these messages come from the previous iteration), we have

\begin{equation}
\label{eq:supp-isgmr-back-message-3}
\begin{aligned}
\nabla \hmesnew{r}{i}{\lambda}
&= \sum_{v \in \mathcal{L}} \Big( \left. \nabla \hmesnew{r}{i+r}{v}
\right \vert_{\lambda = p^{r}_{k,i+r}{(v)}} \\
&\quad + \sum_{d \in \mathcal{R}} \sum_{d^{'} \in \mathcal{R} \setminus \{d, d^{-}\}}
\sum_{\lambda^{'} \in \mathcal{L}} \nabla \hmesnew{d}{j}{v}
\frac{\partial \hmesnew{d}{j}{v}}{\partial m^{d^{'}}_{j-d}{(\lambda^{'})}}
\frac{\partial m^{d^{'}}_{j-d}{(\lambda^{'})}}{\partial \hat{m}^r_{i}{(\lambda)}} \Big ) 
&\tcp*[f]{from \eqref{eq:supp-isgmr-back-message-2}} \\
&= \sum_{v \in \mathcal{L}} \Big( \left. \nabla \hmesnew{r}{i+r}{v}
\right \vert_{\lambda = p^{r}_{k,i+r}{(v)}} \\
&\quad + \sum_{d \in \mathcal{R}} \left. \nabla \hmesnew{d}{i+d}{v}
\frac{\partial \hmesnew{d}{i+d}{v}}{\partial m^{r}_{i}{(\lambda)}}
\frac{\partial m^{r}_{i}{(\lambda)}}{\partial \hmesnew{r}{i}{\lambda}}
\right \vert_{r \not \in \{d, d^{-}\}} \Big ) 
& \tcp*[f]{due to \eqref{eq:supp-isgmr-renew}} \\
&= \sum_{v \in \mathcal{L}} \Big( \left. \nabla \hmesnew{r}{i+r}{v}
\right \vert_{\lambda = p^r_{k,i+r}{(v)}} \\
&\quad + \sum_{d \in \mathcal{R} \setminus \{r, r^{-}\}} \left.
\nabla m^d_{i+d}{(v)} \right \vert_{\lambda = p^d_{k,i+d}{(v)}} \Big )\ .
\end{aligned}
\end{equation}
Here, updating the message gradient at node $i$ depends on its next node
$i + r$ along the scanning direction $r$; this scanning direction is opposite
to the forward scanning direction, and thus, it depends on node $i + r$ instead
of $i - r$. Gradient of message $m^r_{i}{(\lambda)}$ can be derived in the same way.

Now one can derive $\nabla \hmesnew{r}{i+r}{v}$ in the same manner of
$\nabla \hmesnew{r}{i}{\lambda}$ and apply it to \eqref{eq:supp-isgmr-back-message-unary}
to obtain \eqref{eq:supp-gradient-unary}.

\subsubsection{Gradient of Pairwise Potentials} \

\noindent \textbf{Proposition:} Gradients of pairwise potentials
$\{ \theta_{i-r,i}(\mu,\lambda) \}$ are represented by

\begin{equation}
\label{eq:supp-gradient-pairwise}
\begin{aligned}
\nabla \theta_{i-r,i}(\mu,\lambda) = \left. \nabla \hmesnew{r}{i}{\lambda}
\right \vert_{\mu=p^{r}_{k,i}{(\lambda)}}, \quad \forall i \in \mathcal{V},
\forall r \in \mathcal{R}, \forall \lambda,\mu \in \mathcal{L}\ .
\end{aligned}
\end{equation}

\noindent \textit{Derivation:}

\begin{equation}
\label{eq:supp-isgmr-back-pairwise}
\begin{aligned}
\nabla \theta_{i-r,i}(\mu,\lambda)
&= \frac{dL}{d\theta_{i-r, i}(\mu,\lambda)} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\frac{\partial c_{j}{(v)}}{\partial \theta_{i-r, i}(\mu,\lambda)} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-confidence}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\sum_{d \in \mathcal{R}} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}} 
\frac{\partial m^d_{j}{(v)}}{\partial \theta_{i-r, i}(\mu,\lambda)} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-aggregate}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla c_{j}{(v)} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}}
\frac{\partial m^d_{j}{(v)}}{\partial \hmesnew{d}{j}{v}} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}(\mu,\lambda)} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-renew}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}(\mu,\lambda)}\ .
\end{aligned}
\end{equation}

Now we update $\nabla \hmesnew{d}{j}{v}$ by \eqref{eq:supp-isgmr-back-norm}. Then

\begin{equation}
\label{eq:supp-isgmr-back-pairwise-2}
\begin{aligned}
\nabla \theta_{i-r,i}(\mu,\lambda)
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}(\mu,\lambda)} 
& \tcp*[f]{from \eqref{eq:supp-isgmr-back-pairwise}} \\
&= \left. \nabla \hmesnew{r}{i}{\lambda} \right \vert_{\mu=p^{r}_{k,i}{(\lambda)}} \ .
& \tcp*[f]{back \eqref{eq:supp-isgmr-explicit} without recursion}
\end{aligned}
\end{equation}

One can note that the memory requirement of $\{\theta_{i-r,i}(\mu, \lambda)\}$ is
$4 \sum_{r\in\mathcal{R}} |\mathcal{E}^r| |\mathcal{L}| |\mathcal{L}|$ bytes
using single-precision floating-point values. This will be high when the number
of disparities $|\mathcal{L}|$ is large. In practical, since the pairwise potentials
can be decomposed by $\theta_{i,j}(\lambda, \mu) = \theta_{i,j} V(\lambda, \mu),
\forall (i,j) \in \mathcal{E}, \forall \lambda, \mu \in \mathcal{L}$ with edge weights
$\theta_{i,j}$ and a pairwise function $V(\cdot, \cdot)$, it takes up
$4 ( \sum_{r\in\mathcal{R}} |\mathcal{E}^r| + |\mathcal{L}| |\mathcal{L}|)$ bytes
in total, which is much less than $4 \sum_{r\in\mathcal{R}} |\mathcal{E}^r| |\mathcal{L}| |\mathcal{L}|$ above.
Therefore, we additionally provide the gradient derivations of these two terms,
edge weights and pairwise functions, for practical implementations of the backpropagation.

\subsubsection{Gradient of Edge Weights} \

\noindent \textbf{Proposition:} Gradients of edge weights $\{ \theta_{i-r,i} \}$ are represented by

\begin{equation}
\label{eq:supp-gradient-edge}
\begin{aligned}
\nabla \theta_{i-r,i} = \sum_{v \in \mathcal{L}} \nabla \hmesnew{r}{i}{v}
V(p^r_{k,i}{(v)},v), \quad \forall i \in \mathcal{V}, \forall r \in \mathcal{R}\ .
\end{aligned}
\end{equation}

\noindent \textit{Derivation:}

\begin{equation}
\label{eq:supp-isgmr-back-edge}
\begin{aligned}
\nabla \theta_{i-r,i}
&= \frac{dL}{d\theta_{i-r, i}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\frac{\partial c_{j}{(v)}}{\partial \theta_{i-r, i}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-confidence}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\sum_{d \in \mathcal{R}} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}}
\frac{\partial m^d_{j}{(v)}}{\partial \theta_{i-r, i}} 
& \tcp*[f]{back \eqref{eq:supp-isgmr-aggregate}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla c_{j}{(v)} \frac{\partial c_{j}{(v)}}{\partial m^d_{j}{(v)}}
\frac{\partial m^d_{j}{(v)}}{\partial \hmesnew{d}{j}{v}} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}}
& \tcp*[f]{back \eqref{eq:supp-isgmr-renew}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}}\ .
\end{aligned}
\end{equation}
Again, before updating gradients of edge weights by \eqref{eq:supp-isgmr-explicit},
$\nabla \hmesnew{d}{j}{v}$ is updated by \eqref{eq:supp-isgmr-back-norm}. Then

\begin{equation}
\label{eq:supp-isgmr-back-edge-2}
\begin{aligned}
\nabla \theta_{i-r,i}
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{i-r, i}}
& \tcp*[f]{from \eqref{eq:supp-isgmr-back-edge}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{d \in \mathcal{R}}
\nabla \hmesnew{d}{j}{v} \frac{\partial \hmesnew{d}{j}{v}}{\partial \theta_{j-d, j}} V(p^d_{k,j}{(v)},v)
\frac{\partial \theta_{j-d, j}}{\partial \theta_{i-r, i}}
& \tcp*[f]{back \eqref{eq:supp-isgmr-explicit}, no recursion} \\
&= \sum_{v \in \mathcal{L}} \nabla \hmesnew{r}{i}{v} V(p^r_{k,i}{(v)},v)\ .
\end{aligned}
\end{equation}

In the case that when edge weights are undirected, \ie, $\theta_{i,j} = \theta_{j,i}$,
the derivations above still hold, and if $\theta_{i,j} = \theta_{j,i}$ are stored in
the same tensor, $\nabla \theta_{i,j}$ will be accumulated by adding $\nabla \theta_{j,i}$
for storing the gradient of this edge weight. This is also applied to the gradient of
pairwise potentials in \eqref{eq:supp-gradient-pairwise} above.

\subsubsection{Gradients of Pairwise Functions} \

\noindent \textbf{Proposition:} Gradients of a pairwise function $V(\cdot, \cdot)$ are

\begin{equation}
\label{eq:supp-gradient-smoothness}
\begin{aligned}
\nabla V(\lambda, \mu) = \sum_{j \in \mathcal{V}} \sum_{r \in \mathcal{R}} \left.
\theta_{j-r, j} \nabla \hmesnew{r}{j}{\mu} \right \vert_{\lambda = p^r_{k,j}{(\mu)}}, \quad \forall \lambda, \mu \in \mathcal{L}\ .
\end{aligned}
\end{equation}

\noindent \textit{Derivation:}

\begin{equation}
\label{eq:supp-isgmr-back-smoothness}
\begin{aligned}
\nabla V(\lambda, \mu)
&= \frac{dL}{dV(\lambda, \mu)} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\frac{\partial c_{j}{(v)}}{\partial V(\lambda, \mu)}
& \tcp*[f]{back \eqref{eq:supp-isgmr-regression}-\eqref{eq:supp-isgmr-confidence}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \nabla c_{j}{(v)}
\sum_{r \in \mathcal{R}} \frac{\partial c_{j}{(v)}}{\partial m^r_{j}{(v)}}
\frac{\partial m^r_{j}{(v)}}{\partial V(\lambda, \mu)}
& \tcp*[f]{back \eqref{eq:supp-isgmr-aggregate}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}}
\nabla c_{j}{(v)} \frac{\partial c_{j}{(v)}}{\partial m^r_{j}{(v)}}
\frac{\partial m^r_{j}{(v)}}{\partial \hmesnew{r}{j}{v}} \frac{\partial \hmesnew{r}{j}{v}}{\partial V(\lambda, \mu)}
& \tcp*[f]{back \eqref{eq:supp-isgmr-renew}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}}
\nabla \hmesnew{r}{j}{v} \frac{\partial \hmesnew{r}{j}{v}}{\partial V(\lambda, \mu)}\ .
\end{aligned}
\end{equation}

$\nabla \hmesnew{r}{j}{v}$ is updated by \eqref{eq:supp-isgmr-back-norm}. Then

\begin{equation}
\label{eq:supp-isgmr-back-smoothness-2}
\begin{aligned}
\nabla V(\lambda, \mu)
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}}
\nabla \hmesnew{r}{j}{v} \frac{\partial \hmesnew{r}{j}{v}}{\partial V(\lambda, \mu)}
& \tcp*[f]{from \eqref{eq:supp-isgmr-back-smoothness}} \\
&= \sum_{j \in \mathcal{V}} \sum_{v \in \mathcal{L}} \sum_{r \in \mathcal{R}}
\nabla \hmesnew{r}{j}{v} \sum_{\lambda^{'} \in \mathcal{L}}
\frac{\partial \hmesnew{r}{j}{v}}{\partial V(\lambda^{'}, v)} \frac{\partial V(\lambda^{'}, v)}{\partial V(\lambda, \mu)}
& \tcp*[f]{from \eqref{eq:supp-isgmr-explicit}} \\
&= \sum_{j \in \mathcal{V}} \sum_{r \in \mathcal{R}} \left. \theta_{j-r, j}
\nabla \hmesnew{r}{j}{\mu} \right \vert_{\lambda = p^r_{k,j}{(\mu)}}\ .
\end{aligned}
\end{equation}

%--------------------------------------------------------------------------
\subsection{Characteristics of Backpropagation}
\textbf{1. Accumulation.}
Since a message update usually has several components, its gradient is therefore
accumulated when backpropagating through every component.
For instance, in \eqref{eq:supp-isgmr-back-message-unary}, the gradient of unary
potential $\nabla \theta_{i}{(\lambda)}$ has $\nabla c_{i}{(\lambda)}$ and $\nabla \hmesnew{r}{i+r}{v}, \forall r \in \mathcal{R}$
and $\forall v$ satisfying $\lambda = p^r_{k, i+r}{(v)}$ at $k$th iteration.
It is calculated recursively but not at once due to multiple nodes on a tree,
multiple directions, and multiple iterations. In \eqref{eq:supp-isgmr-back-message-3},
the message gradient of a node relies on the gradient of all nodes after it in the
forward propagation since this message will be used to all the message updates after this node.

\noindent \textbf{2. Zero Out Gradients.}
Message gradients are not accumulated throughout the backpropagation but should be
zeroed out in some cases. In more details, in the forward propagation, the repeated
usage of $\mathbf{m}^\mathbf{r}$ and $\hat{\mathbf{m}}^\mathbf{r}$ is for all iterations
but the messages are, in fact, new variables whenever they are updated. Since the
gradient of a new message must be initialized to 0, zeroing out the gradients of
the new messages is important. Specifically, in ISGMR that within an iteration
$\mathbf{m^r} \gets \hat{\mathbf{m}}^{\mathbf{r}}$ is executed only when message
updates in all directions are done. Thus, $\nabla \mathbf{m^r}$ must be zeroed
out after $\nabla \hat{\mathbf{m}}^\mathbf{r} \gets \nabla \mathbf{m^r}$. Similarly,
after using $\nabla \hat{\mathbf{m}}^\mathbf{r}$ to update the gradients of learnable
parameters and messages, $\nabla \hat{\mathbf{m}}^\mathbf{r} \gets 0, \forall r \in \mathcal{R}$.

%--------------------------------------------------------------------------
\subsection{PyTorch GPU version \textit{vs.} our CUDA version}
For the compared PyTorch GPU version, we highly paralleled individual trees
in each direction while sequential message updates in each tree (equally
scanline) are iterative.
As Pytorch auto-grad is not customized for our min-sum message passing
algorithms, these iterative message updates require to allocate new GPU
memory for each updated message, which makes it very inefficient and
memory-consuming.
Its backpropagation is slower since extra memory is needed to unroll the
forward message passing to compute gradients of messages and all
intermediate variables that require gradients.

In contrast, our implementation is specific to the min-sum message passing.
This min-sum form greatly accelerates our backpropagation by updating
gradients only related to the indices which are stored in pre-allocated
GPU memory during forward pass (line 10 in Alg. 1).
For example, from node $i$ to $i + r$ in Fig. 2(a), forward pass needs messages
over 9 edges (grey lines); but only one (1 of 3 blue lines) from $i + r$ to
$i$ requires gradient updates in the backpropagation.
This makes our CUDA implementation much faster than the PyTorch GPU
version, especially the backpropagation with at least $700\times$ speed-up.

%==========================================================================
\section{Computational Complexity of Min-Sum \& Sum-Product TRW}
Given a graph with parameters $\{\theta_{i}, \theta_{i,j}\}$, maximum iteration $K$,
set of edges $\{\mathcal{E}^r\}$, disparities $\mathcal{L}$, directions $\mathcal{R}$,
computational complexities of min-sum and sum-product TRW are shown below.
For the efficient implementation, let $\theta_{i,j}(\lambda, \mu) = \theta_{i,j} V(\lambda, \mu)$.

%--------------------------------------------------------------------------
\subsection{Computational Complexity of Min-Sum TRW}
Representation of a message update in min-sum TRW is

\begin{equation}
\label{eq:supp-cc-min-sum}
m^r_{i}{(\lambda)} = \min_{\mu \in \mathcal{L}} \Big( \rho_{i-r, i}
\big(\theta_{i-r}{(\mu)} + \sum_{d \in \mathcal{R}} m^d_{i-r}{(\mu)} \big) - m^{r^-}_{i-r}{(\mu)}
+ \theta_{i-r,i} V(\mu, \lambda) \Big) \ .
\end{equation}

In our case where the maximum disparity is less than 256, memory for the backpropagatio
of the min-sum TRW above is only for indices $\mu^* = p^r_{k,i}{(\lambda)} \in \mathcal{L}$
from message minimization with $K\sum_{r\in\mathcal{R}}|\mathcal{E}^r| |\mathcal{L}|$
bytes 8-bit unsigned integer values, as well as for indices from message reparametrization
with $K\sum_{r\in\mathcal{R}}|\mathcal{E}^r|$ bytes. In total, the min-sum TRW
needs $K\sum_{r\in\mathcal{R}}|\mathcal{E}^r| \left( |\mathcal{L}| + 1 \right)$ bytes for the backpropagation.

%--------------------------------------------------------------------------
\subsection{Computational Complexity of Sum-Product TRW}
Representation of a message update in sum-product TRW is
%
\begin{equation}
\label{eq:supp-cc-sum-product}
\begin{aligned}
\exp(-m^r_{i}{(\lambda)})
&= \sum_{\mu \in \mathcal{L}} \exp \Big( -\rho_{i-r, i} \big( \theta_{i-r}{(\mu)}
+ \sum_{d \in \mathcal{R}} m^d_{i-r}{(\mu)} \big) + m^{r^-}_{i-r}{(\mu)} \\
&\quad - \theta_{i-r, i} V(\mu, \lambda) \Big) \\
&= \sum_{\mu \in \mathcal{L}} \Big( \exp \big(-\rho_{i-r, i} \theta_{i-r}{(\mu)} \big)
\prod_{d \in \mathcal{R}} \exp \big(- \rho_{i-r, i} m^d_{i-r}{(\mu)} \big) \\
&\quad \exp( m^{r^-}_{i-r}{(\mu)}) \exp \big(- \theta_{i-r, i} V(\mu, \lambda) \big) \Big)\ .
\end{aligned}
\end{equation}
%
Usually, it can be represented as
%
\begin{equation}
\label{eq:supp-cc-sum-product-2}
\begin{aligned}
\tilde{m}^r_{i}{(\lambda)}
&= \sum_{\mu \in \mathcal{L}} \Big( \exp^{-\rho_{i-r, i} \underline{\theta_{i-r}{(\mu)}}_{1}}
\prod_{d \in \mathcal{R}} \big( \underline{\tilde{m}^d_{i-r}{(\mu)}}_{2} \big)^{\rho_{i-r,i}}
\frac{1}{ \underline{\tilde{m}^{r^-}_{i-r}{(\mu)}}}_{3} \exp^{- \underline{\theta_{i-r,i}}_{4}
\underline{V(\mu, \lambda)}_{5}} \Big) \ .
\end{aligned}
\end{equation}

\noindent \textbf{Problem 1: Numerical Overflow:}
For single-precision floating-point data, a valid numerical range of $x$ in $\exp(x)$ is
less than around 88.7229; otherwise, it will be infinite.
Therefore, for the exponential index in \eqref{eq:supp-cc-sum-product}, a numerical overflow
will happen quite easily. One solution is to reparametrize these messages to a small range,
such as $[0, 1]$, in the same manner as SoftMax(), which requires logarithm to find the
maximum index, followed by exponential operations.

\noindent \textbf{Problem 2: Low efficiency OR high memory requirement in backpropagation:}
In the backpropagation, due to the factorization in \eqref{eq:supp-cc-sum-product-2}, it
needs to rerun the forward propagation to calculate intermediate values OR store all these
values in the forward propagation. However, the former makes the backpropagation at least
as slow as the forward propagation while the later requires a large memory, \\
$K\sum_{r\in\mathcal{R}}|\mathcal{E}^r| |\mathcal{L}| \left( 8|\mathcal{L}|
+ 4 |\mathcal{R}| |\mathcal{L}| + 4 \right)$ bytes single-precision floating-point values.

\noindent \textit{Derivation:}

For one message update in \eqref{eq:supp-cc-sum-product-2}, the gradient calculation
of terms 1,2-3,4,5 (underlined) requires $4 \times \{|\mathcal{L}|,
|\mathcal{R}| |\mathcal{L}|, 1, |\mathcal{L}|\}$ bytes respectively.
For $K$ iterations, set of directions $\mathcal{R}$, edges $\{\mathcal{E}^r\}$,
$\forall r \in \mathcal{R}$, it requires $K\sum_{r\in\mathcal{R}}|\mathcal{E}^r|
|\mathcal{L}| \left( 8|\mathcal{L}| + 4 |\mathcal{R}| |\mathcal{L}| + 4 \right)$ bytes in total.
This is in $\mathcal{O} (|\mathcal{R}| |\mathcal{L}|)$ order higher than the memory
requirement in the min-sum TRW memory requirement, $K\sum_{r\in\mathcal{R}}|\mathcal{E}^r| \left( |\mathcal{L}| + 1 \right)$ bytes.

%==========================================================================
\section{Additional Evaluations}

%--------------------------------------------------------------------------
\subsection{More Evaluations with Constant Edge Weights}
More results from the main experiments are given in Tables~\myblue{\ref{tb:supp-middlebury}}-\myblue{\ref{tb:supp-kitti}}.

\begin{table*}
\centering
\caption{Energy minimization on Middlebury with constant edge weights. For Map,
ISGMR-4 has the lowest energy among ISGMR-related methods; for others, ISGMR-8 and TRWP-4
have the lowest energies in ISGMR-related and TRWP-related methods respectively. ISGMR is
more effective than SGM in optimization, and TRWP-4 outperforms MF and SGM.}
\resizebox{\textwidth}{!}{\begin{tabular}{l||r|r|r|r|r|r|r|r|r|r}
  \hline
  \multicolumn{1}{c||}{\multirow{2}{*}{\textbf{Method}}} & \multicolumn{2}{c|}{\textbf{Tsukuba}} &
  \multicolumn{2}{c|}{\textbf{Teddy}} & \multicolumn{2}{c|}{\textbf{Venus}} &
  \multicolumn{2}{c|}{\textbf{Cones}} & \multicolumn{2}{c}{\textbf{Map}} \\
  \cline{2-11}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c}{\textbf{50 iter}} \\
  \hline \hline
  MF-4 & 3121704 & 1620524 & 3206347 & 2583784 & 108494928 & 14618819 & 9686122 &
  6379392 & 1116641 & 363221 \\
  SGM-4 & 873777 & 644840 & 2825535 & 2559016 & 5119933 & 2637164 & 3697880 &
  3170715 & 255054 & 216713 \\
  TRWS-4 & 352178 & \underline{314393} & 1855625 & \underline{1807423} & 1325651
  & \lgray 1219774 & 2415087 & \lgray 2329324 & 150853 & \lgray 143197 \\
  ISGMR-4 (ours) & 824694 & 637996 & 2626648 & 1898641 & 4595032 & 1964032 & 3296594
  & 2473646 & 215875 & 148049 \\
  TRWP-4 (ours) & 869363 & \lgray 314037 & 2234163 & \lgray 1806990 & 32896024 &
  \underline{1292619} & 3284868 & \underline{2329343} & 192200 & \underline{143364} \\
  \hline \hline
  MF-8 & 2322139 & 504815 & 3244710 & 2545226 & 68718520 & 2920117 & 7762269 &
  3553975 & 840615 & 213827 \\
  SGM-8 & 776706 & 574758 & 2868131 & 2728682 & 4651016 & 2559933 & 3631020 &
  3309643 & 243058 & 222678 \\
  ISGMR-8 (ours) & 684185 & \lgray 340347 & 2532071 & \lgray 1847833 & 4062167 &
  \lgray 1285330 & 3039638 & \lgray 2398060 & 195718 & \lgray 149857 \\
  TRWP-8 (ours) & 496727 & \underline{348447} & 1981582 & \underline{1849287} &
  8736569 & \underline{1347060} & 2654033 & \underline{2396257} & 162432 & \underline{151970} \\
  \hline
  MF-16 & 1979155 & 404404 & 3315900 & 2622047 & 43077872 & 1981096 & 6741127 & 3062965 & 638753 & 204737 \\
  SGM-16 & 710727 & 587376 & 2907051 & 2846133 & 4081905 & 2720669 & 3564423 & 3413752 & 242932 & 232875 \\
  ISGMR-16 (ours) & 591554 & \lgray 377427 & 2453592 & \lgray 1956343 & 3222851 &
  \lgray 1396914 & 2866149 & \lgray 2595487 & 190847 & \lgray 165249 \\
  TRWP-16 (ours) & 402033 & \underline{396036} & 1935791 & \underline{1976839} &
  2636413 & \underline{1486880} & 2524566 & \underline{2660964} & 162655 & \underline{164704} \\
  \hline
\end{tabular}}
\label{tb:supp-middlebury}
\end{table*}

\begin{table*}
\centering
\caption{Energy minimization on 3 image pairs of KITTI2015 and 2 of ETH-3D with
constant edge weights. ISGMR is more effective than SGM in optimization in both single
and multiple iterations, and TRWP-4 outperforms MF and SGM.}
\label{tb:supp-kitti}
\resizebox{\textwidth}{!}{\begin{tabular}{l||r|r|r|r|r|r|r|r|r|r}
  \hline
  \multicolumn{1}{c||}{\multirow{2}{*}{\textbf{Method}}}
  & \multicolumn{2}{c|}{\textbf{000002\_11}}
  & \multicolumn{2}{c|}{\textbf{000041\_10}}
  & \multicolumn{2}{c|}{\textbf{000119\_10}}
  & \multicolumn{2}{c|}{\textbf{delivery\_area\_1l}}
  & \multicolumn{2}{c}{\textbf{facade\_1s}} \\
  \cline{2-11}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c|}{\textbf{50 iter}}
  & \multicolumn{1}{c|}{\textbf{1 iter}}
  & \multicolumn{1}{c}{\textbf{50 iter}} \\
  \hline \hline
  MF-4 & 82523536 & 44410056 & 69894016 & 36163508 & 72659040 & 42392548 & 19945352 &
  9013862 & 13299859 & 6681882 \\
  SGM-4 & 24343250 & 18060026 & 15926416 & 12141643 & 24999424 & 18595020 & 5851489 &
  4267990 & 1797314 & 1429254 \\
  TRWS-4 & 9109976 & \lgray 8322635 & 6876291 & \lgray 6491169 & 10811576 &
  \lgray 9669367 & 1628879 & \lgray 1534961 & 891282 & \lgray 851273 \\
  ISGMR-4 (ours) & 22259606 & 12659612 & 14434318 & 9984545 & 23180608 & 18541970
  & 5282024 & 2212106 & 1572377 & 980151 \\
  TRWP-4 (ours) & 40473776 & \underline{8385450} & 30399548 & \underline{6528642}
  & 36873904 & \underline{9765540} & 9899787 & \underline{1546795} & 2851700 & \underline{854552} \\
  \hline
  MF-8 & 61157072 & 18416536 & 53302252 & 16473121 & 57201868 & 21320892 & 16581587
  & 4510834 & 10978978 & 3422296 \\
  SGM-8 & 20324684 & 16406781 & 13740635 & 11671740 & 20771096 & 16652122 & 5396353
  & 4428411 & 1717285 & 1464208 \\
  ISGMR-8 (ours) & 17489158 & \lgray 8753990 & 11802603 & \lgray 6639570 & 18411930
  & \lgray 10173513 & 4474404 & \lgray 1571528 & 1438210 & \lgray 884241 \\
  TRWP-8 (ours) & 18424062 & \underline{8860552} & 13319964 & \underline{6678844}
  & 20581640 & \underline{10445172} & 4443931 & \underline{1587917} & 1358270 & \underline{889907} \\
  \hline
  MF-16 & 46614232 & 14192750 & 40838292 & 12974839 & 44706364 & 16708809 & 13223338
  & 3229021 & 9189592 & 2631006 \\
  SGM-16 & 18893122 & 16791762 & 13252150 & 12162330 & 19284684 & 16936852 & 5092094
  & 4611821 & 1670997 & 1535778 \\
  ISGMR-16 (ours) & 15455787 & \lgray 9556611 & 10731068 & \lgray 6806150 & 16608803
  & \lgray 11037483 & 3689863 & \lgray 1594877 & 1324235 & \lgray 937102 \\
  TRWP-16 (ours) & 11239113 & \underline{9736704} & 8187380 & \underline{6895937}
  & 13602307 & \underline{11309673} & 2261402 & \underline{1630973} & 1000985 & \underline{950607} \\
  \hline
\end{tabular}}
\end{table*}

%--------------------------------------------------------------------------
\subsection{More Visualizations for Image Denoising}
We provide more visualizations of image denoising on ``Penguin" and ``House" in
Figures~\myblue{\ref{fig:denoise_penguin}}-\myblue{\ref{fig:denoise_house}}
corresponding to Table~\myblue{2} in the main paper.

\begin{figure}[]
\centering
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_input.png}
\caption{noisy}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_gt.png}
\caption{GT}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_MeanField_iter_50_TQ_trunc_200_dir_4_rho_1.png}
\caption{MF-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_MeanField_iter_50_TQ_trunc_200_dir_8_rho_1.png}
\caption{MF-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_MeanField_iter_50_TQ_trunc_200_dir_16_rho_1.png}
\caption{MF-16}
\end{subfigure}
\\
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_SGM_iter_50_TQ_trunc_200_dir_4_rho_1.png}
\caption{SGM-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_SGM_iter_50_TQ_trunc_200_dir_8_rho_1.png}
\caption{SGM-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_SGM_iter_50_TQ_trunc_200_dir_16_rho_1.png}
\caption{SGM-16}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_TRWS.png}
\caption{TRWS-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_ISGMR_iter_50_TQ_trunc_200_dir_4_rho_1.png}
\caption{ISGMR-4}
\end{subfigure}
\\%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_ISGMR_iter_50_TQ_trunc_200_dir_8_rho_1.png}
\caption{ISGMR-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_ISGMR_iter_50_TQ_trunc_200_dir_16_rho_1.png}
\caption{\scriptsize ISGMR-16}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_TRWP_iter_50_TQ_trunc_200_dir_4_rho_0.5.png}
\caption{TRWP-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_TRWP_iter_50_TQ_trunc_200_dir_8_rho_0.5.png}
\caption{TRWP-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/penguin/penguin_TRWP_iter_50_TQ_trunc_200_dir_16_rho_0.5.png}
\caption{TRWP-16}
\end{subfigure}
\caption{Visualization of MRF inferences for image denoising on ``Penguin".}
\label{fig:denoise_penguin}
\end{figure}

\begin{figure}[]
\centering
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_input.png}
\caption{noisy}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_gt.png}
\caption{GT}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_MeanField_iter_50_TQ_trunc_-1_dir_4_rho_1.png}
\caption{MF-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_MeanField_iter_50_TQ_trunc_-1_dir_8_rho_1.png}
\caption{MF-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_MeanField_iter_50_TQ_trunc_-1_dir_16_rho_1.png}
\caption{MF-16}
\end{subfigure}
\\
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_SGM_iter_50_TQ_trunc_-1_dir_4_rho_1.png}
\caption{SGM-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_SGM_iter_50_TQ_trunc_-1_dir_8_rho_1.png}
\caption{SGM-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_SGM_iter_50_TQ_trunc_-1_dir_16_rho_1.png}
\caption{SGM-16}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_TRWS.png}
\caption{TRWS-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_ISGMR_iter_50_TQ_trunc_-1_dir_4_rho_1.png}
\caption{ISGMR-4}
\end{subfigure}
\\%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_ISGMR_iter_50_TQ_trunc_-1_dir_8_rho_1.png}
\caption{ISGMR-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_ISGMR_iter_50_TQ_trunc_-1_dir_16_rho_1.png}
\caption{\scriptsize ISGMR-16}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_TRWP_iter_50_TQ_trunc_-1_dir_4_rho_0.5.png}
\caption{TRWP-4}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_TRWP_iter_50_TQ_trunc_-1_dir_8_rho_0.5.png}
\caption{TRWP-8}
\end{subfigure}
%
\begin{subfigure}[b]{0.15\textwidth}
\includegraphics[width=\textwidth]{denoise/house/house_TRWP_iter_50_TQ_trunc_-1_dir_16_rho_0.5.png}
\caption{TRWP-16}
\end{subfigure}
\caption{Visualization of MRF inferences for image denoising on ``House".}
\label{fig:denoise_house}
\end{figure}