\section{Introduction}
Inferring highly deformable 3D human pose and shape from in-the-wild monocular images has been a longstanding goal in the vision community~\cite{hogg1983model}. This is considered as a key step for a wide range of downstream applications such as robot interaction, rehabilitation guidance, animation industry, etc. Being one of the important subtasks, human pose estimation has gained considerable performance improvements in recent years~\cite{sun2018integral,martinez2017simple,rogez2017lcr}, but in a fully-supervised setting. Such approaches heavily rely on large-scale 2D or 3D pose annotations. Following this, the parametric models of human body, such as SCAPE~\cite{anguelov2005scape}, SMPL~\cite{loper2015smpl}, SMPL(-X)~\cite{pavlakos2019expressive,romero2017embodied} lead the way for a full 3D pose and shape estimation. Additionally, to suppress the inherent 2D-to-3D ambiguity, researchers have also utilized auxiliary cues of supervision such as temporal consistency~\cite{arnab2019exploiting,sun2019human}, multi-view image pairs~\cite{rhodin2016general,joo2018total,huang2017towards}, or even alternate sensor data from Kinect~\cite{weiss2011home} or IMUs~\cite{von2017sparse}. However, estimating 3D human pose and shape from a single RGB image without relying on any direct supervision remains a very challenging problem.

Early approaches~\cite{bogo2016keep,Guan2009estimating,LassnerClosing} adopt iterative optimization techniques to fit a parametric human model (\emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot SMPL) to a given image observation. These works attempt to iteratively estimate the body pose and shape that best describe the available 2D observation, which is most often the 2D landmark annotations. Though these works usually get good body fits, such approaches are slow and heavily rely on the 2D landmark annotations~\cite{andriluka20142d,johnson2010clustered,kundu2018ispa} or predictions of an off-the-shelf, fully-supervised Image-to-2D pose networks. However, the recent advances in deep learning has shifted the interest towards data-driven regression based methods~\cite{kanazawa2018end,tung2017self}, where a deep network directly regresses parameters of the human model for a given input image~\cite{omran2018neural,pavlakos2018learning,zanfir2018deep} in a single-shot computation. This is a promising direction as the network can utilize the full image information instead of just the sparse landmarks to estimate human body shape and pose. In the absence of datasets having images with 3D pose and shape ground-truth (GT), several recent works leverage a variety of available paired 2D annotations~\cite{texturepose,tan2018indirect} such as 2D landmarks or silhouettes~\cite{pavlakos2018learning}; alongside the unpaired 3D pose samples to instill the 3D pose priors~\cite{kanazawa2018end} (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot to assure recovery of valid 3D poses). The strong reliance on paired 2D keypoint ground-truth limits the generalization of such approaches when applied to images from an unseen wild environment. Given the transient nature of human fashion, the visual appearance of human attire keeps evolving. This demands such approaches to periodically update their 2D pose dataset in order to retain their functionality.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.99\textwidth]{figures/final_eccv_fig_3_compressed.pdf}
    \caption{\small Our framework disentangles the co-salient FG human from input image pairs. The resulting colored mesh prediction opens up its usage for a variety of tasks.
    }
    \label{fig_concept}
\end{figure*}

In this work, the overarching objective is to move away from any kind of paired pose-related supervision for superior generalizability. Our aim is to explore a form of self-supervised objective which can learn both pose and shape from monocular images without accessing any paired GT annotations. We draw motivation from works~\cite{mathieu2016disentangling,rifai2012disentangling,ma2018disentangled,kundu2020self} that aim to disentangle the fundamental factors of variations from a given image. For human-centric images~\cite{kundu2020kinematic}, these factors could be; a) pose, b) foreground (FG) appearance, and c) background (BG) appearance. Here, we leverage the full advantage of incorporating a parametric human model in our framework. Note that, this parametric model not only encapsulates the pose but also segregates the FG region from the BG, which is enabled by projecting the 3D mesh onto the image plane. Thus, the problem boils down to a faithful registration of the 3D mesh onto the image plane or in other words disentanglement of FG from BG. To achieve this disentanglement, we rely on {image pairs} depicting consistent FG appearance but varied 3D poses. Such image pairs can be obtained from videos depicting actions of a single person, which are abundantly available on the internet.
Our idea stems from the concept of co-saliency detection~\cite{zhang2016co,hsu2018unsupervised} where the objective is to segment out the common, salient FG from a set of two or more images.
Surprisingly, this idea works the best for image pairs sampled from wild videos as compared to videos captured in a constrained in-studio setup (static homogeneous background). This is because in wild scenarios, the commonness of FG is distinctly
salient in relatively diverse BGs as a result of substantial camera movements (see Fig.~\ref{fig_concept}{\color{red}B}). Thus, in contrast to prior self-supervised approaches that either rely on videos with static BG~\cite{rhodin2018unsupervised} or operate under the assumption of BG commonness between temporally close frames~\cite{jakab2018unsupervised}; our approach is more favorable to learn from wild videos hence better generalizable.

\begin{wraptable}[9]{r}{7.5cm}
\caption
Characteristic
comparison against prior-arts.
}
\centering
\label{tab_char}
\setlength{\tabcolsep}{0.4pt}
\resizebox{1.0\linewidth}{!}{

    \begin{tabular}{l|c|c|c}
    \hlin
    \makecell{Model-based\\ methods} & \makecell{2D keypoint\\ supervision} & \makecell{Temporal\\supervision} & \makecell{Colored mesh \\prediction} \\
    \hline\hline
    \cite{kanazawa2018end,kolotouros2019learning,kolotouros2019nal,pavlakos2018learning,omran2018neural} & Yes & No & No \\
    \cite{sun2019human,arnab2019exploiting,kanazawa2019learning} & Yes & Yes & No \\ \hline
    Ours(self-sup.) & \textbf{No} & \textbf{No} & \textbf{Yes} \\
    \hline
\end{tabular}
}
\end{wraptable}

In the proposed framework, we first employ a CNN regressor to obtain the parameters (both pose and shape) of the SMPL model for a given input image. The human mesh model uses these parameters to output the mesh vertex locations. In contrast to the general trend~\cite{alp2018densepose,kanazawa2018learning}, we propose a novel way of inferring mesh texture where the network’s burden to regress vertex color or any sort of appearance representation (such as UV map) is entirely taken away. This is realized via a differentiable \textit{Color-recovery} module which aims to assign color to the mesh vertices via spatial registration of the mesh over the image plane while effectively accounting for the challenges of mesh-vertex visibility like self and inter-part occlusions. To obtain a {fully-colored mesh}, we use a predefined, 4-way symmetry grouping knowledge (front-back and left-right) to propagate the color from camera visible vertices to the non-visible ones in a fully differentiable fashion.

For a given image pair, we pass them through two parallel pathways of our colored mesh prediction framework (see Fig.~\ref{fig_concept}{\color{red}A}). The commonness of FG appearance allows us to impose an appearance consistency loss between the predicted mesh representations. In the absence of any paired supervision, this appearance consistency not only helps us to segregate the common FG human from their respective wild BGs but also discovers the required pose deformation in a fully self-supervised manner. {The proposed reflectional symmetry module brings in a substantial advantage in our self-supervised framework by allowing us to impose appearance consistency even between body parts which are ``\textit{commonly invisible}" in both the images}. Recognizing the unreliability of consistent raw color intensities which can easily be violated as result of illumination changes, we propose a \textit{part-prototype} consistency objective. This aims to match a higher level appearance representation beyond the raw color intensities which is enabled by operating the \textit{Color-recovery} module on convolutional feature maps instead of the raw image. Additionally, to regularize the self-supervised framework, we also impose a shape consistency loss alongside the imposition of 3D pose prior learned from a set of unpaired MoCap samples. Note that at test time, we perform single image inference to estimate 3D human pose and shape.

In summary, we make the following main contributions:
\begin{itemize}
    \item We propose a self-supervised learning technique to perform simultaneous pose and shape estimation which uses image pairs sampled from in-the-wild videos in the absence of any paired supervision.
    \item The proposed \textit{Color-recovery} module
    completely eliminates the network’s burden to regress any appearance-related representation via efficient realization of color-picking and reflectional symmetry. This best suits our self-supervised framework
    which relies on FG appearance consistency.
    \item We demonstrate generalizability of our framework to operate on \textit{unseen} wild datasets.
    We achieve \textit{state-of-the-art} results against the prior model-based pose estimation approaches when tested at comparable supervision levels.

\end{itemize}

\section{Related Work}
\textbf{Vertex-color reconstruction.} In literature, we find different ways to infer textured 3D mesh from a monocular RGB image.
Certain approaches~\cite{l2019differ,song2017semantic} train a deep network to directly regress 3D features (RGB colors) for individual vertices. In the second kind, a fully convolutional deep network is trained to map the location of each pixel to the corresponding continuous UV-map coordinate parameterization~\cite{alp2018densepose}.
In the third kind, the deep model is trained to directly regress the UV-image~\cite{kanazawa2018learning}. Note that, the spatial structure of the UV image is much different from that of the input image which prevents employing a fully-convolutional network for the same. Recently proposed, Soft-Rasterizer~\cite{liu2019soft} uses a color-selection and color-sampling network whose outputs are processed to obtain the final vertex colors. All the above approaches adopt a learnable way to obtain the mesh color (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot obtained as neural output). In such cases, the deep network requires substantial training iterations to instill the knowledge of pre-defined UV mapping conventions. We believe this is an additional burden for the network specifically in absence of any auxiliary paired supervisions.

\textbf{Model-based human mesh estimation.}
Recently, parametric human models~\cite{anguelov2005scape,loper2015smpl} have been used as the output target for the simultaneous pose and shape estimation task. Such a well-defined mesh model with ordered vertices provides a direct mapping to the corresponding 3D pose and part segments. Both optimization~\cite{bogo2016keep,LassnerClosing,zanfir2018monocular} and regression~\cite{kanazawa2018end,omran2018neural,pavlakos2018learning,zanfir2018deep} based approaches estimate the body pose and shape that best describes the available 2D observations such as 2D keypoints~\cite{kanazawa2018end}, silhouettes~\cite{pavlakos2018learning}, body/part segmentation~\cite{omran2018neural} etc. Due to the lack of datasets having wild images with 3D pose and shape GT, most of the above approaches fully rely on the availability of 2D keypoint annotations~\cite{andriluka20142d,lin2014microsoft} followed by different variants of a 2D reprojection loss~\cite{tan2018indirect,tung2017self} (see Table~\ref{tab_char}).

\textbf{Use of auxiliary supervision.}
In the absence of any shape supervision, certain prior works also leverage full mesh supervision available from synthetically rendered human images~\cite{varol2017learning} or images with fairly successful body fits~\cite{LassnerClosing}.
Furthermore, multi-view image pairs have also been used for 3D pose~\cite{rhodin2018unsupervised} and shape estimation~\cite{hofmann2009multi,liang2019shape} via enforcing consistency of canonical 3D pose across multiple views.
Liang~\emph{et al}\onedot~\cite{liang2019shape} use a multi-stage regressor for multi-view images to further reduce the projection ambiguity in order to obtain a better performance for 3D human body under clothing. To inculcate strong 3D pose prior, Zhou~\emph{et al}\onedot~\cite{zhou2017towards} makes use of left-right symmetric bone-length constraint for the skeleton based 3D pose estimation task. Further, to assure recovery of valid 3D poses for the model-based pose estimation task, Kanazawa~\emph{et al}\onedot~\cite{kanazawa2018end} enforce learning based human pose and shape prior via adversarial networks using unpaired sample of plausible 3D pose and shape. With the advent of differentiable renderers~\cite{henderson19ijcv,kato2018renderer} certain methods supervise 3D shape and pose estimation through a textured mesh prediction network to encourage matching of the rendered texture image with the image FG~\cite{kanazawa2018learning}, alongside the 2D keypoint supervision~\cite{texturepose}.

\section{Approach}
We aim to discover the 3D human pose and shape from unlabeled image pairs of consistent FG appearance. During training, we assume access to a
parametric human mesh model to aid our self-supervised paradigm.
The mesh model provides a low dimensional parametric representation of variations in human shape and pose deformations. However, by design, this model is unaware of the plausibility restrictions of human pose and shape. Thus, it is prone to implausible poses and self-penetrations specifically in the absence of paired 3D supervision~\cite{kanazawa2018end}. Therefore, to constrain the pose predictions, we assume access to a pool of human 3D pose samples to learn a 3D pose prior.

Fig.~\ref{fig_approach} shows an overview
of our training approach.
For a given image pair, two parallel pathways of shared CNN regressors predict the human shape and pose parameters alongside the required camera settings to segregate the co-salient FG human. Moreover, to realize a colored mesh representation, we develop a differentiable \textit{Color-recovery} module which infers mesh vertex colors directly from the given image without employing any explicit appearance extraction network.

\subsection{Representation and notations}\label{sec_1}
\noindent \textbf{Human mesh model.} We employ the widely used SMPL body model~\cite{loper2015smpl} which parameterizes a triangulated human mesh of $K=6890$ vertices. This model factorizes the mesh deformations into shape $\beta\in\mathbb{R}^{10}$ and pose $\theta\in\mathbb{R}^{3J}$ with $J=23$ skeleton joints~\cite{kanazawa2018end}.
We use the first 10 PCA coefficients of the shape space as a compact shape representation inline with~\cite{kanazawa2018end}. And, the pose is parameterized as parent-relative rotations in the axis-angle representation. This differentiable SMPL function outputs mesh vertex locations in a canonical 3D space which is represented as $V\in\mathbb{R}^{K\times 3}=\mathcal{M}(\theta, \beta)$. Here, the corresponding 3D pose (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot 3D location of $J$ joints) is obtained using a pre-trained linear regressor, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $Y\in\mathbb{R}^{J\times 3}=W_pV$ parameterized by $W_p\in\mathbb{R}^{J\times K}$.
RGB color corresponding to the mesh vertices, $V$
is denoted as $C\in \mathbb{R}^{3\times K}=\textit{CRM}(V, I)$, where \textit{CRM} is the \textit{Color-recovery} module. For each vertex id $k$, $C^{(k)}$ stores the corresponding RGB color intensities. As shown in Fig.~\ref{fig_approach}, we use subscripts $a$ and $b$ to associate
the terms with the respective input images, $I_a$ and $I_b$.

\textbf{Camera model.} We define a weak perspective camera model using a global orientation $R\in\mathbb{R}^{3\times 3}$ in axis-angle representation (3 angle parameters), a translation $t\in\mathbb{R}^{2}$ and a scale $s\in\mathbb{R}$. Given these parameters, the 2D camera space coordinates of the 3D mesh vertices with vertex index $k$ is obtained as $v^{(k)}=\pi(V^{(k)}) = s\Pi(RV^{(k)})+t$; $v^{(k)}\in\mathcal{U}$,
where $\Pi$ denotes orthographic projection and $\mathcal{U}\subset \mathbb{R}^2$ denotes the space of image coordinates. Similarly, the camera projected 2D joint locations (2D pose) is expressed as $y\in\mathbb{R}^{J\times 2}=\pi(Y)$.

\subsection{Mesh estimation architecture}\label{sec_2}
For a given monocular image, $I$ as input, we first employ a CNN regressor to predict the SMPL parameters (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\theta$ and $\beta$) alongside the camera parameters, $(R, s, t)$. This is followed by the \textit{Color-recovery} module. The prime functionality of this module is to assign color to the 3D mesh vertices, $C^{(k)}$; $k=1,2,...K$ based on the corresponding image space coordinates obtained via camera projection. However, a reliable color assignment requires us to segregate the vertices based on the following two important criteria.

a) \textbf{Non-camera-facing vertices}: First, the camera-facing vertices are
separated from the non-camera-facing ones using the mesh vertex normals. Here, the vertex normal is computed as the normalized average of the surface normals of the faces connected to a given vertex. We first transform these normals from the default canonical system to the camera coordinate system. Following this, Z-component of the \textit{camera-space-normals}, $N^{(k)}\in\mathbb{R}$ are used to segregate the non-camera-facing vertices via a \textit{sigmoid} operation, as shown in Fig.~\ref{fig_approach}.

b) \textbf{Camera-facing, self-occluded vertices}: Note that, $N^{(k)}$ can not be used to select all the
camera-visible vertices in presence of inter-part occlusions (see Fig.~\ref{fig_approach}). As, in such scenario, there exist mesh vertices which face the camera but are obscured by other camera-facing vertices which are closer to the camera in 3D. This calls for modeling the relative depth of mesh-vertices as the second criteria to reliably select the vertices which are closer to the camera among all the camera-facing vertices projected to a certain spatial region. To realize this, we utilize \textit{camera-space-depths},
$Z^{(k)}\in\mathbb{R}$ which stores the Z-component (or depth) of the vertex location in the camera transformed space.

\subsubsection{Color-recovery module.}
In absence of any appearance related features, we plan to realize a spatial depth map using a fast differentiable renderer~\cite{henderson19ijcv} where the camera-space-depth of the mesh vertices, $Z$ is treated as the color intensities for the rendering pipeline. The resultant depth-map is represented as $I^z(u)$, where $u$ spans the space of spatial indices. The
general idea is to use this depth-map as a {margin}.
More concretely, for effective color assignment, one must select the spatially modulated mesh vertices which have the least absolute depth difference with respect to the above defined depth margin.
To realize this, we compute a depth difference $D^{(k)}$ as $ \vert I^z(v^{(k)}) - Z^{(k)} \vert$, where $I^z(v^{(k)})$ is computed by performing bilinear sampling on $I^z(u)$. In accordance with the above discussion, we formulate a
\textit{visibility-aware-weighing} which takes into account both the above mentioned criteria required for an effective mesh vertex selection.

$$
W^{(k)} \in [0,1] = \exp (-\alpha  D^{(k)} )~ \sigma (\gamma N^{(k)}) \text{, where } D^{(k)}= \vert I^z(v^{(k)}) - Z^{(k)} \vert
$$
Here, $\exp (-\alpha D^{(k)})$ performs a soft selection by assigning a higher weight value (close to 1) for mesh vertices, $k$ whose \textit{camera-space-depth} $Z^{(k)}$ is in agreement with $I^z(v^{(k)})$ and vice-versa. In the second term, $\sigma$ denotes a sigmoid function with a higher steepness $\gamma$ to reject the non-camera-facing mesh vertices by attributing a low (close to 0) weighing value.
Refer Fig.~\ref{fig_approach} for visual illustration.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/final_eccv_fig_approach.pdf
    \caption{The proposed self-supervised
    framework makes use of a differentiable \textit{Color-recovery} module to recover the fully colored mesh vertices. \textit{Yellow-circle}: camera-facing vertices does not account for inter-part occlusion. \textit{Green-circle}: $W_a$ accounts for the inter-part occlusion. \textit{Blue-circle}: Fully colored mesh vertices via reflectional symmetry.

    }
    \label{fig_approach}
\end{figure*}

\noindent
\textbf{Intermediate vertex color assignment.}
The above defined \textit{visibility-aware-weighing} is employed to realize a primary vertex color assignment. We denote $\tilde{C}\in\mathbb{R}^{3\times K}$ as the intermediate vertex color, where $\tilde{C}^{(k)}$ stores the corresponding RGB color intensities acquired from the given input image $I$. Thus, the primary vertex colors are obtained as, $\tilde{C}^{(k)} = I(v^{(k)}) ~ (2W^{(k)}-1)$, where $I(v^{(k)})$ stores the RGB color intensities at the spatial coordinates $v^{(k)}$ realized via performing bilinear sampling on the input RGB image $I$. The scaled weighing function $(2W^{(k)}-1)$ assigns negative weight to the vertices having low visibility. This assigns a negative color intensity for the corresponding vertices thereby allowing a distinction between the \textit{less-bright} (near-black)
colors versus \textit{unassigned} vertices.

\subsubsection{Vertex color assignment via reflectional symmetry.}
Here, the prime objective is to propagate the reliable color intensities from the assigned vertices to the unreliable/unassigned ones. The idea is to use reflectional symmetry as a prior knowledge by accessing a predefined set of reflectional groups. For each group-id $g=1,2,...G$, a set of 4 vertices are identified according to left-right and front-back symmetry which would have the same color property (except the vertices belonging to the head where only left-right symmetry is used). This symmetry knowledge is stored as a multi-hot encoding denoted as $S^{(g)}\in \{0,1\}^K$ which constitutes of four ones indicating vertex members in the symmetry group $g$. All the symmetry groups are combined in a symmetry-encoding matrix represented as $S\in \{0,1\}^{G\times K}$. This multi-hot symmetry group representation helps us to perform a fully-differentiable vertex color assignment for all the vertices including the occluded and non-camera facing ones.

To realize the final vertex colors $C$, we first estimate a group-color for each group $g$ which is denoted by $\mathcal{C}^{(g)}\in\mathbb{R}^{3} = (S^{(g)} \circ \operatorname{ReLU}(\tilde{C})) / (S^{(g)}\circ \operatorname{ReLU}(2W-1))$. Here, $\circ$ denotes dot product between the $K$-dimensional vectors. The group color can be interpreted as a combination of the intermediate vertex colors weighted by their visibility weighing $W$. This effectively handles the cases when only one or more of the vertices in a group are initially colored (visible). That is,
when visibility is active only for a single vertex among the four vertices in a symmetry set; and when visibility is active for all the 4 vertices in a symmetry set; and also the intermediate cases. Finally, the group color is directly propagated to all the mesh vertices using the following matrix multiplication operation, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $C=S^T * \mathcal{C}$, where $\mathcal{C}\in\mathbb{R}^{G\times 3} = [\mathcal{C}^{(1)}, \mathcal{C}^{(2)},...\mathcal{C}^{(G)}]$ (see Suppl for more details).

\subsection{Self-supervised learning objectives}\label{sec_3}
For a given image pair, denoted as $I_a$ and $I_b$ (depicting the same person in diverse pose and BGs), we forward them through two parallel pathways of our colored mesh estimation architecture (see Fig.~\ref{fig_approach}). The commonness of FG appearance allows us to impose an appearance consistency loss between the predicted fully colored mesh representations.

\textbf{a) Color consistency.} First, we impose the following consistency loss,
$$
\boldsymbol{\mathcal{L}_{\textit{CC}}} = \mathcal{L}_{{C}} + \lambda \mathcal{L}_{\tilde{C}} \text{ , where } \mathcal{L}_C=\Vert C_a - C_b \Vert \text{ and } \mathcal{L}_{\tilde{C}}=\Vert W_a\odot W_b\odot (\tilde{C}_a-\tilde{C}_b) \Vert
$$

Here, $\odot$ denotes element-wise multiplication. Note that, $\mathcal{L}_{\tilde{C}}$ enforces a vertex-color consistency on the co-visible mesh vertices (computed as $(W_a\odot W_b)$), \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot the vertices which are visible in both the mesh representations obtained from the image pair, $(I_a, I_b)$.
However, $\mathcal{L}_{C}$ enforces full vertex color consistency. Here, $\mathcal{L}_{\textit{CC}}$ combines both of the losses thereby providing a higher weightage to the co-visible vertex colors as compared to the approximate full color representation, considering the
approximate nature of the symmetry assumption.

\textbf{b) Part-prototype consistency.} The proposed \textit{Color-recovery} module can also be applied on the convolutional feature maps. For a given vertex $k$ and a convolutional feature map $H\in\mathbb{R}^{\tilde{w}\times \tilde{h}\times \tilde{d}}$, we sample $\mathcal{H}^{(k)}\in\mathbb{R}^{\tilde{d}} = H(v^{(k)})$. Note that, we  define a fixed
vertex to part-segmentation mapping represented as $Q^{(l)}$, which stores a set of vertex indices for each part $l=1,2,...L$. Now, one can use the vertex visibility weighing $W^{(k)}$ to obtain a prototype appearance feature for each body-part $l$, which is computed as;
$\mathcal{F}^{(l)} = (\Sigma_{k\in Q^{(l)}} W^{(k)}\mathcal{H}^{(k)}) /( \Sigma_{k\in Q^{(l)}} W^{(k)})$
Following this, we enforce a prototype consistency loss between the image pairs as $\boldsymbol{\mathcal{L}_P} = \Sigma_l \Vert \mathcal{F}_a^{(l)} - \mathcal{F}_b^{(l)} \Vert/ L$. Note that, the prototype feature computation is inherently aware of the inter-part occlusions as a result of incorporating the visibility weighing $W^{(k)}$. As compared to enforcing vertex-color consistency, $\mathcal{L}_{\textit{CC}}$ (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot the raw color intensities), the part-prototype consistency aims to match a higher-level semantic abstraction (\emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot checkered regular patterns
versus just plain {individual colors}) of the part appearances extracted from the image pairs. This also helps us to overcome the unreliability of raw vertex colors which could arise due to illumination differences.
Motivated by the perceptual loss idea~\cite{johnson2016perceptual}, we obtain $H_a$ and $H_b$
as the \textit{Conv2-1} features corresponding to $I_a$ and $I_b$ from an ImageNet trained (frozen) VGG-16 network~\cite{simonyan2014very}.

\textbf{c) Shape-consistency.} We also enforce a shape consistency loss between the shape parameters obtained from the image pair, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\boldsymbol{\mathcal{L}_\beta} = \vert \beta_a - \beta_b \vert$. Almost all the prior
works~\cite{kanazawa2018end,pavlakos2018learning,texturepose} utilize an \textit{unpaired} human shape dataset to enforce plausibility of the shape predictions via adversarial prior. However, in the proposed self-supervised framework we do not access any human shape dataset. To regularize the shape parameters during the initial training iterations we enforce a loss on shape predictions with respect to a fixed mean shape as a regularization. However, after gaining a decent mesh estimation performance we gradually reduce weightage of this loss by allowing shape variations beyond the mean shape driven by the proposed appearance and shape consistency objectives.

\textbf{d) Enforcing validity of pose predictions.}
Additionally, to assure validity of the predicted pose parameters we train an adversarial auto-encoder~\cite{makhzani2015adversarial} to realize a continuous human pose manifold~\cite{kundu2019bihmp,kundu2019unsupervised} mapped from a latent pose representation, $\phi\in [-1,1]^{32}$. This is trained using an unpaired 3D human pose dataset. The frozen pose decoder obtained from this generative framework is directly employed as a module, with instilled human 3D pose prior. More concretely, a \textit{tanh} non-linearity on the pose-prediction head of the CNN regressor (inline with the latent pose $\phi$) followed by the frozen pose decoder prevents implausible pose predictions during our self-supervised training. In contrast to enforcing an adversarial pose prior objective~\cite{kanazawa2018end,texturepose}, the proposed setup greatly simplifies our training procedure (devoid of discriminator training).

In absence of paired supervision, parameters of the shared CNN regressor is trained by directly enforcing the above consistency losses, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\mathcal{L}_{\textit{CC}}$, $\mathcal{L}_P$, and $\mathcal{L}_\beta$.

\section{Experiments
We perform thorough experimental analysis to demonstrate the generalizability of our framework across several datasets on a variety of tasks.

\textbf{Implementation details.} We use Resnet-50~\cite{he2016identity} initialized from ImageNet as the base CNN network. The average pooled last layer features are forwarded through a series of fully-connected layers to regress the pose (latent pose encoding $\phi$), shape and camera parameters. Note that, the series of differentiable operations post the CNN regressor do not include any trainable parameters even to estimate the vertex colors. During training, we optimize individual loss terms at alternate training iteration using Adam optimizer~\cite{kingma2014adam}.
We enforce prediction of the mean shape for initial 100k training iterations. We also impose a silhouette loss on the predicted human mesh with respect to a pseudo silhouette ground-truth obtained either by using an unsupervised saliency detection method~\cite{zhu2014saliency} or by using a background estimate as favourable for static camera scenarios~\cite{rhodin2018unsupervised}.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.92\textwidth]{figures/eccv_fig_6_qualitative_results_raka_cr_compressed.pdf
    \caption{Qualitative results. In each panel, 1st column depicts the input image, 2nd column depicts our colored mesh prediction, and 3rd column shows the model-based part segments. Our model fails (in magenta) in presence of complex inter-part occlusions.
    }
    \label{fig_view_syn}
\end{figure*}

\textbf{Datasets.}
We sample image pairs with diverse BG (pairs with large \textit{L2} distance) from the following standard datasets, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot Human3.6M~\cite{ionescu2013human3}, MPII~\cite{andriluka20142d}, MPI-INF-3DHP~\cite{mehta2017monocular} and an in-house collection of wild YouTube videos. In contrast to the in-studio datasets with hardly any camera movement implying static BG~\cite{ionescu2013human3}, the videos collected from YouTube have diverse camera movements (\emph{e.g}\onedot} \def\Eg{\emph{E.g}\onedot Parkour and Free-running videos). We prune the raw video samples using a
person-detector~\cite{ren2015faster} to obtain reliable human-centric crops as required for the mesh estimation pipeline (see Suppl). The unpaired 3D pose dataset required to train the 3D pose prior is {obtained from} CMU-MoCap (also used in MoSh~\cite{loper2014mosh}).

\textbf{a) Human3.6M}
This is a widely used dataset consisting of paired image with 3D pose annotations of actors imitating various day-to-day tasks in a controlled in-studio environment. Adhering to well established standards~\cite{kanazawa2018end} we consider subjects S1, S6, S7, S8 for training, S5 for validation and S9, S11 for evaluation, in both Protocol-1 \cite{rhodin2018unsupervised,rhodin2018learning} and Protocol-2 \cite{kanazawa2018end}.

\textbf{b) LSP}
A standard 2D pose dataset consisting of wild athletic actions. We access the LSP test-set with silhouette and part segment annotations as given by Lassner~\emph{et al}\onedot~\cite{LassnerClosing}.
In absence of any standard shape evaluation dataset, segmentation results are considered as a proxy for the shape fitting performance~\cite{kanazawa2018end,kolotouros2019nal}.

\textbf{c) 3DPW}
We also evaluate on the 3D Poses in the Wild dataset~\cite{von2018recovering}. We do not train on 3DPW and use it only to evaluate our cross-dataset generalizability~\cite{kundu2020unsupervised}. We compute the mean per joint position error (MPJPE)~\cite{ionescu2013human3}, both before and after rigid alignment. Rigid alignment is done via Procrustes Analysis~\cite{gower1975generalized}. MPJPE computed post Procrustes alignment is denoted by PA-MPJPE.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.99\textwidth]{figures/eccv_fig_6_qualitative_results_rakb_cr_compressed.pdf
    \caption{\textbf{A.} Qualitative results on single image colored human mesh recovery. The model fails in presence of complex inter-limb occlusions (in magenta box). \textbf{B.} Qualitative analysis demonstrating importance of incorporating $\mathcal{L}_P$ to extract relevant part-semantics.

    }
    \label{fig_box}
\end{figure*}

\subsection{Ablative study}
To analyze effectiveness of individual self-supervised consistency objectives, we perform ablations by removing certain losses as shown in Table~\ref{tab_ablation}. First, we train \textit{Baseline-1} by enforcing $\mathcal{L}_C$ and $\mathcal{L}_\beta$. Following this, in \textit{Baseline-2} we enforce $\mathcal{L}_{\textit{CC}}$ by incorporating $\mathcal{L}_{\tilde{C}}$ which further penalizes color inconsistency between the vertices which are commonly visible in both the mesh representations. This results in marginal improvement of performance.
Moving forward, we recognize a clear limitation in our assumption of FG color consistency (raw RGB intensities) which can easily be violated by illumination differences. Further, the assumption of left-right and front-back symmetry in apparel color can also be violated specifically for {asymmetric upper body apparel}. As a solution, the proposed part-prototype consistency objective, $\mathcal{L}_P$ tries to match a higher level appearance representation beyond just raw color intensities (see Fig.~\ref{fig_box}{\color{red}B}), thus resulting in a significant performance gain (\textit{Ours(unsup)} in Table~\ref{tab_ablation}). Note that, $\mathcal{L}_P$ is possible as a consequence of the proposed differentiable \textit{Color-recovery} module.

\begin{figure*}[t]
\CenterFloatBoxes
\begin{floatrow}

\capbtabbox{%
\setlength{\tabcolsep}{1.8pt}
\resizebox{0.99\linewidth}{!}{
    \caption{Ablative study (on Human3.6M) to analyze importance of self-supervised objectives (first 3 rows), and results at varied degree of paired supervision (last 3 rows). P1 and P2 denote MPJPE and PA-MPJPE in Protocol-1 and Protocol-2 respectively.

    }
    \label{tab_ablation}
    \begin{tabular}{l|ccc}

    \toprule
    Methods & P1($\downarrow$) && P2($\downarrow$) \\
    \midrule\midrule

    \textit{Baseline-1}; ($\mathcal{L}_C+\mathcal{L}_\beta$) & 127.1 && 101.2 \\
    \textit{Baseline-2}; ($\mathcal{L}_{\textit{CC}}+\mathcal{L}_\beta$) & 119.6 && 97.4 \\
    \textit{Ours(unsup.)}; ($\mathcal{L}_{\textit{CC}}$+$\mathcal{L}_\beta$+$\mathcal{L}_p$) & \textbf{110.8} && \textbf{90.5} \\
    \midrule
    \textit{Ours(multi-view-sup)} & 102.1 && 74.1 \\
    \textit{Ours(weakly-sup)} & 86.4 && 58.2 \\
    \textit{Ours(semi-sup)} & \textbf{73.8} && \textbf{48.1} \\

    \bottomrule
\end{tabular}}}

\capbtabbox{%
\setlength{\tabcolsep}{1.1pt}
\resizebox{0.99\linewidth}{!}{
    \caption{Evaluation on wild 3DPW dataset in a \textit{fully-unseen} setting. Note that, in contrast to Temporal-HMR \cite{kanazawa2019learning} we do not use any temporal supervision.
    Methods in first 5 rows use equivalent 2D and 3D pose supervision, thus directly comparable.

    }
    \label{tab_3dpw}
    \begin{tabular}{l|ccc}
    \toprul
    Methods & MPJPE($\downarrow$) && PA-MPJPE($\downarrow$) \\
    \midrule\midrule

    Martinez~\emph{et al}\onedot~\cite{martinez2017simple} & - && 157.0 \\
    SMPLify~\cite{bogo2016keep} & 199.2 && 106.1 \\
    TP-Net~\cite{Dabral_2018_ECCV} & 163.7 && 92.3 \\
    Temporal-HMR~\cite{kanazawa2019learning} & 127.1 && 80.1 \\
    \textit{Ours(semi-sup)} & \textbf{125.8} && \textbf{78.2} \\
    \midrule
    \textit{Ours(weakly-sup)} & 153.4 && 89.8 \\
    \textit{Ours(unsup)} & 187.1 && 102.7 \\
    \bottomrule
\end{tabular}}}
{%
}
\end{floatrow}
\end{figure*}

Further, maintaining a fair comparison ground against the prior weakly supervised approaches, we train 3 variants of the proposed framework by utilizing increasing level of paired supervisions alongside our self-supervised objectives.

\noindent
a) \textbf{\textit{Ours(multi-view-sup)}} Under multi-view supervision, we impose additional consistency loss on the canonically aligned (view-invariant) 3D mesh vertices (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\Vert V_a - V_b\Vert$) and the 3D pose (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\Vert Y_a-Y_b \Vert$) for the time synchronized multi-view pairs, $(I_a, I_b)$. Inline with Rhodin~\emph{et al}\onedot~\cite{rhodin2018unsupervised}, we also use full 3D pose supervision only for S1 while evaluating on the standard Human3.6M dataset. We outperform Rhodin~\emph{et al}\onedot~\cite{rhodin2018unsupervised} by a significant margin as reported in the
Table~\ref{tab_h36m}. This is beyond the usual trend of weaker performance in non-parametric approaches against the model-based parametric ones. Thus, we attribute this performance gain to the proposed appearance consensus driven self-supervised objectives.

\noindent
b) \textbf{\textit{Ours(weakly-sup)}} In this setting, we access image datasets with paired 2D landmark annotations, inline with the supervision setting of prior model-based approaches~\cite{kanazawa2018end}. Alongside the proposed self-supervised objectives, we impose a direct 2D landmark supervision loss (\emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot $\Vert y-y_\textit{gt}\Vert$) with respect to the corresponding ground-truths but only on samples from specific datasets, such as LSP, LSP-extended~\cite{johnsonclustered} and MPII~\cite{andriluka20142d}. Certain prior arts, such as HMR~\cite{kanazawa2018end}, use even more images with paired 2D landmark annotations from COCO~\cite{lin2014microsoft}.

\noindent
c) \textbf{\textit{Ours(semi-sup)}} In this variant, we access paired 3D pose supervision on the widely used in-studio Human3.6M~\cite{ionescu2013human3} dataset alongside the 2D landmark supervision as used in \textit{Ours(weakly-sup)}. Note that, a better performance on Human3.6M (with limited BG and FG diversity as a result of the in-studio data collection setup) does not translate to the same on wild images as a result of the significant domain gap. As we impose the above supervisions alongside the proposed self-supervised objective on unlabeled wild images, such a training is expected to deliver improved performance by successfully overcoming the domain-shift issue. We evaluate this on the wild 3DPW dataset.

\subsection{Comparison with the state-of-the-art}
\textbf{Evaluation on Human3.6M.}
Table~\ref{tab_h36m} shows a comparison of different variants of the proposed framework against the prior-arts which are grouped based on the respective supervision levels. We clearly outperform in all the three groups \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot while accessing comparable a) 3D pose supervision, b) 2D landmark supervision, and c) multi-view supervision. Except Rhodin~\emph{et al}\onedot~\cite{rhodin2018unsupervised} all the prior works mentioned in Table~\ref{tab_h36m} use parametric human model for the human mesh estimation task. Note the significant performance gain specifically in absence of any 3D pose supervision, \emph{i.e}\onedot} \def\Ie{\emph{I.e}\onedot for \textit{Ours(weakly-sup)} and \textit{Ours(multi-view-sup)} against the relevant counterparts as reported in the last 4 rows.

\noindent
\textbf{Evaluation on 3DPW.}
Table~\ref{tab_3dpw} reports a comparison of different variants of the proposed framework against the prior-arts which use comparable pose supervision as used in \textit{Ours(semi-sup)} (except certain methods, such as HMR~\cite{kanazawa2018end} which use even more supervision on 3D pose from the MPI-INF-3DHP~\cite{mehta2017monocular} dataset). It is worth noting that none of our model variants is trained on the samples from 3DPW dataset (not even in self-supervised paradigm). A better performance in such \textit{unseen} setting highlights our superior cross-dataset generalizability.

\begin{figure*}[t]
\CenterFloatBoxes
\begin{floatrow}
\capbtabbox{%
\setlength{\tabcolsep}{3.7pt}
\resizebox{0.99\linewidth}{!}{
    \caption{Evaluation on Human3.6M (Protocol-2). Methods in first 9 rows use equivalent 2D and 3D pose supervision hence are directly comparable. Same analogy applies for the rows 10-11 and 12-13.
    }
    \label{tab_h36m}
    \begin{tabular}{ll|c}
    \toprul
    No. & Methods & PA-MPJPE($\downarrow$) \\
    \midrule\midrule
    1. & Lassner \emph{et al}\onedot~\cite{LassnerClosing} & 93.9 \\
    2. & Pavlakos~\emph{et al}\onedot~\cite{pavlakos2018learning} & 75.9 \\
    3. & Omran~\emph{et al}\onedot~\cite{omran2018neural} & 59.9 \\
    4. & HMR~\cite{kanazawa2018end} & 56.8 \\
    5. & Temporal HMR~\cite{kanazawa2019learning} & 56.9 \\
    6. & Arnab~\emph{et al}\onedot~\cite{arnab2019exploiting} & 54.3 \\
    7. & Kolotouros~\emph{et al}\onedot~\cite{kolotouros2019nal} & 50.1 \\
    8. & TexturePose~\cite{texturepose} & 49.7 \\
    9. & \textit{Ours(semi-sup)} & \textbf{48.1} \\ \midrule

    10. & HMR unpaired~\cite{kanazawa2018end} & 66.5 \\
    11. & \textit{Ours(weakly-sup)} & \textbf{58.2} \\ \midrule

    12. & Rhodin~\emph{et al}\onedot~\cite{rhodin2018unsupervised} & 98.2 \\
    13. & \textit{Ours(multi-view-sup)} & \textbf{74.1} \\
    \bottomrule
\end{tabular}}}

\capbtabbox{%
\setlength{\tabcolsep}{1.1pt}
\resizebox{0.999\linewidth}{!}{
  \caption{Evaluation of FG-BG and 6-part segmentation on LSP test set. It reports accuracy (Acc.) and F1 score values of ours against the prior-arts.
  \textbf{First group}: Iterative, \textit{optimization-based} approaches.
  \textbf{Last 3 groups}: \textit{Regression-based} methods grouped based on comparable supervision levels.

    }
  \label{tab_part_seg}

    \begin{tabular}{l|cc|cc}
        \toprule
        \multirow{2}{*}{Methods} & \multicolumn{2}{c|}{\textbf{FG-BG Seg.}} &
 		\multicolumn{2}{c}{\textbf{Part Seg.}} \\
 		\cline{2-5}
 		& Acc.($\uparrow$) & F1($\uparrow$) & Acc.($\uparrow$) & F1($\uparrow$) \\ \midrule\midrule
 		SMPLify \textit{oracle}~\cite{bogo2016keep} &  92.17 & 0.88 & 88.82 & 0.67 \\
 		SMPLify~\cite{bogo2016keep} &  91.89 & 0.88 & 87.71 & 0.64 \\
 		SMPLify on~\cite{pavlakos2018learning} &  92.17 & 0.88 & 88.24 & 0.64 \\
 		Bodynet~\cite{varol2018bodynet} &  92.75 & 0.84 & - & - \\
 		\midrule
        HMR~\cite{kanazawa2018end} & 91.67 & 0.87 & 87.12 & 0.60 \\
        Kolotouros~\emph{et al}\onedot~\cite{kolotouros2019nal} & 91.46 & 0.87 & 88.69 & 0.66 \\
        TexturePose~\cite{texturepose} & 91.82 & 0.87 & 89.00 & 0.67 \\
        \textit{Ours(semi-sup)} & \textbf{91.84} & 0.87 & \textbf{89.08} & 0.67 \\
        \midrule
        HMR unpaired~\cite{kanazawa2018end} & 91.30 & 0.86 & 87.00 & 0.59 \\
       \textit{ Ours(weakly-sup)} & \textbf{91.70} & \textbf{0.87} & \textbf{87.12} & \textbf{0.60} \\
        \midrule
        \textit{Ours(unsup)} & 91.46 & 0.86 & 87.26 & 0.64 \\
        \bottomrule
    \end{tabular}
    \label{tab:ablation}}}
{%
}
\end{floatrow}
\end{figure*}

\noindent
\textbf{Evaluation of part-segmentation.}
We also evaluate our performance on FG-BG segmentation and body part-segmentation tasks which are considered as a proxy to quantify the shape fitting performance. In presence of 2D landmark annotation, iterative model fitting approaches have a clear advantage over the single-shot regressor based approaches as shown in Table~\ref{tab_part_seg}. At comparable supervision, \textit{Ours(semi-sup)} not only outperforms the relevant regression based prior arts but also performs competitive to the iterative model fitting based approaches with a significant advantage on inference time (1 min vs ~0.04 sec).
Note that, \textit{Ours(unsup)} performs competitive to the prior supervised regression-based approache
, thus establishing the importance of FG appearance consistency for accurate shape recovery.

\subsection{Qualitative results}
The proposed mesh recovery model not only infers pose and shape but also outputs a colored mesh representation as a result of the proposed \textit{reflectional-symmetry} procedure. To evaluate effectiveness of the recovered part appearance we perform 2 different tasks a) part-conditioned appearance transfer,
and b) full-body appearance transfer as shown in Fig.~\ref{fig_part_syn}. On the top, we show the target images whose pose and shape (network predicted) is combined with part appearances recovered from the source image (only for the highlighted parts) shown on left, to realize a novel synthesized image. Note that, in case of \textit{part-conditioned} appearance transfer, appearance of the non-highlighted parts are taken from the target image shown on the top. For instance, in the first row, the synthesized image depicts upper-body apparel of the person in the source image combined with the lower-body apparel from the target (and in the target image pose). Qualitative results of \textit{Ours(semi-sup)} model on other primary tasks are shown in Fig.~\ref{fig_view_syn} and Fig.~\ref{fig_box} with highlighted failure scenarios (see Suppl).

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.94\textwidth]{figures/eccv_fig_4_part_transfer_rak_cr_compressed.pdf
    \caption{Qualitative results on \textbf{A.} {Part-conditioned},

    and \textbf{B.} {Full-body} appearance transfer. This is enabled as a result of our ability to infer the colored mesh representation.

    }
    \label{fig_part_syn}
\end{figure*}

\section{Conclusion}
We introduce a self-supervised framework for model-based human pose and shape recovery.
The proposed appearance consistency not only helps us to segregate the common FG human from their respective wild BGs but also discovers the required pose deformation in a fully self-supervised manner.
However, extending such a framework for human centric images with occlusion by external objects or truncated human visibility, remains to be explored in future.

\noindent
\textbf{Acknowledgements.} We thank Qualcomm Innovation Fellowship India 2020.

\clearpage

\includepdf[pages=1-1]{2788-supp_compressed.pdf}
\includepdf[pages=2-2]{2788-supp_compressed.pdf}
\includepdf[pages=3-3]{2788-supp_compressed.pdf}
\includepdf[pages=4-4]{2788-supp_compressed.pdf}
\includepdf[pages=5-5]{2788-supp_compressed.pdf}
\includepdf[pages=6-6]{2788-supp_compressed.pdf}
\includepdf[pages=7-7]{2788-supp_compressed.pdf}

\bibliographystyle{splncs04}


\section{Introduction}
\label{sec:intro}
Deep learning techniques such as convolutional neural networks (CNNs) have had a major impact on fields like computer vision and other Euclidean data domains (in which data have a uniform, grid-like structure), yet in many important applications data are indexed by irregular and non-Euclidean structures, which require graphs or manifolds to explicitly model. Such applications include social networks, sensor feeds, web traffic, supply chains, and biological systems. An illustration of these contrasting data structures is shown in Fig.~\ref{fig:data_structures}.
\begin{figure}[htbp]
    \centering
	\includegraphics[height=6cm]{media/fig1.png}
	\caption{Problems in Euclidean data domains, like images and time series (left), have seen great advances through deep learning. Non-Euclidean data domains (right) require new deep learning techniques to achieve similar advances.}
	\label{fig:data_structures}
\end{figure}

Conventional deep learning approaches are often limited when the data index lacks Euclidean structure to exploit. A CNN that takes advantage of the indexing graph structure significantly outperforms CNNs that do not meaningfully incorporate that structure but are otherwise the same. The extension of deep learning to non-Euclidean data is an area of research now called \textit{geometric deep learning} \cite{bronstein_geometric_2017}. Our paper concentrates on 1)~how graph signal processing~(GSP) can be used to adapt the CNN architecture to take advantage of the graph structure, and 2)~how to design the resulting graph CNN architecture based on the graph structure.

Graph signal processing (GSP), the generalization of traditional digital signal processing to graphs \cite{DSP, ShumanNFOV, ortega_graph_2017}, can be used to extend CNNs to graph data. We concentrate on CNNs in this paper in part because of their particular effectiveness among deep learning models---notably because of the shift invariance of convolutional filters---and in part because the convolutional kernel is straightforward to define in GSP.

Graph structure, defined by its adjacency matrix, may differ from problem domain to problem domain to a far greater extent then, e.g., image structure in different computer vision problems. We consider the effect of graph structure with respect to 1)~\textit{node classification}, a semisupervised learning task in which unlabeled nodes of a graph are classified based on labeled nodes in the same graph, and 2)~\textit{graph classification}, a supervised learning task in which previously unseen graphs are classified based on a collection of labeled graphs. Analysis of the underlying graph structure can help in understanding how certain graphs may be easier to infer over, or are more suitable to different learning architectures.

\textbf{Remark:} The scope of this paper is on graph CNNs and two related applications: node and graph classification. There are many other geometric deep learning architectures not treated herein, such as graph autoencoders, recurrent graph neural networks, and spatial-temporal graph neural networks (e.g., \cite{li2019forecaster}). Please see \cite{review1, review2} for comprehensive surveys of graph neural networks. Also, there are important geometric deep learning problems beyond node classification and graph classification, including representation learning, link prediction, anomaly detection, graph generation, community detection, graph embedding, and combinatorial optimization (which require more complex architectures than graph CNNs). We consider only a small subset of application areas, mostly in chemistry and social networks. Some others include natural language processing (text generation, machine translation), computer vision (image classification, object detection), logistics, neuroscience, and other areas of science (see \cite{review1,review2}).

\textbf{Summary}: Below, we give a cursory introduction to CNNs and GSP in Section~\ref{sec:CNN} and Section~\ref{sec:GSP}, respectively. Section~\ref{sec:GCNN} addresses how GSP can be used with CNNs, leading to \textit{graph} CNNs, by discussing each of the core components of a graph CNN architecture. In Section~\ref{sec:Use}, we explore design considerations for graph CNNs; how the topology of the data graph defined by the graph adjacency matrix affects the performance of these models for node and graph classification. We then evaluate the results in Section~\ref{sec:res} and conclude with a discussion of open problems in Section~\ref{sec:Conc}.

\section{A Brief Overview of CNNs}
\label{sec:CNN}

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.8\linewidth]{media/fig2.png}
    \caption[CNN Architecture and kernel]{Basic CNN architecture and kernel. A typical CNN consists of several component types (e.g., several convolutional + nonlinear activation layers, interleaved with pooling layers, followed by fully connected layers before prediction). The convolutional kernel sums the point-wise multiplications of a subset of the signal\footnotemark ~$\mathbf{X}$ with a learned filter $\mathbf{H}$. This operation is repeated as the filter ``slides'' across the input. (Note that what is termed convolution by the deep learning community is actually cross-correlation.)}
    \label{fig:cnn}
\end{figure}

CNNs, like that shown in Fig.~\ref{fig:cnn}, have proven effective in domains like computer vision because the convolutional kernel has several powerful properties: 1) it has a fixed number of parameters, allowing for a small memory footprint and computational cost; 2) it operates locally, meaning higher-level, global features can be composed of lower-level, local features; and 3) it is shift invariant. In constructing a graph CNN, such properties should ideally translate. The basic operation of a CNN convolutional kernel is shown in detail in Fig.~\ref{fig:cnn}, where a $3 \times 3$ filter or kernel (red window) slides over the input ($\mathbf{X}$) to generate the output.

The CNN architecture has been successfully applied to many classification tasks like image classification and speech recognition. The model shown in Fig.~\ref{fig:cnn} transforms an input through a sequence of hidden layers. Each early-stage hidden layer consists of 1) a set of learned filters like convolution, followed by 2) a nonlinear activation function, and 3) pooling. A filter outputs a feature map that serves as the input to the subsequent layer, which also includes several parallel channels (3 shown in Fig.~\ref{fig:cnn}). Later hidden layers are typically fully connected and, finally, a prediction is made at the output layer, using a loss function like cross-entropy loss.  Numerous variants and improvements have been detailed across the literature. A more complete treatment of CNNs can be found in \cite{LeCun2015}.

\footnotetext{For CNNs, we denote the signal as $\mathbf{X}$ because the input is typically an image and therefore a matrix.}

\section{Elements of Graph Signal Processing}
\label{sec:GSP}
 Graph signal processing (GSP) extends traditional signal processing operations such as shifting, Fourier transforms, convolution, and sampling to graphs \cite{DSP, ShumanNFOV, ortega_graph_2017}. GSP provides an intuitive, theoretically rigorous framework to evaluate signals on graphs and can be used to extend CNNs to graphs. In this section, we give a brief primer on GSP theory, which is related to the graph CNN architecture and analysis in the subsequent sections. More thorough introductions to GSP can be found in \cite{DSP, ShumanNFOV, ortega_graph_2017}.

\subsection{The Shift Operator}
\label{sec:shift}

GSP has been developed to process, from first principles, graph-structured data \cite{DSP, ShumanNFOV, ortega_graph_2017}. GSP can be thought of as a generalization of classical signal processing: whereas the structure indexing classical signals is implicit, the structure of non-Euclidean data must be explicitly represented, which GSP does with the pairwise relationships of graphs. Because GSP is a generalization of classical signal processing \cite{DSP, ShumanNFOV, ortega_graph_2017}, GSP reduces to DSP in the special case of a uniform graph (e.g., the pixels of an image \cite{puschel2008} or indices of a time series).

GSP can perhaps best be understood by beginning with a generalization of the shift operation from DSP. A finite-support (or periodic) discrete-time signal $x[n]$ with period $N$ can be represented by a vector $x=[x_0, x_1, \dots, x_{N-2}, x_{N-1}]^T$. In this representation, to filter $x[n]$ by some finite impulse response (FIR) filter $g$, we represent $g$ as a matrix $\mathbf{G}$ and simply perform a matrix multiplication $x' = \mathbf{G}x$.

The shift operator plays a crucial role in DSP; any linear, shift-invariant filter, \textbf{G}, can be expressed as a polynomial of the circular shift. For the time model and DSP, we can write the circular shift as
\begin{equation}
\label{eq:A}
    \mathbf{A} =
\begin{bmatrix}
	0  & 0 & 0 & \hdots & 0 & 1 \\
	1  & 0 & 0 &  \hdots & 0 & 0 \\
	0  & 1 & 0 &  \hdots & 0 & 0 \\
	\vdots  & \vdots & \ddots & \ddots & \vdots  & \vdots\\
	0  & 0 & 0 &  \hdots & 1 & 0 \\
	\end{bmatrix}.
\end{equation}
Given this choice for the shift operator~$\mathbf{A}$, the shift operation\footnote{Shifting the signal $x[n]$ to the right to produce $x[n-1]$.} in DSP on $x$ is written as $\mathbf{A}x$, i.e.,
\begin{equation}
\label{eq:ring_shift}
    [x_{N-1}, x_0, \dots, x_{N-3}, x_{N-2}]^T =
    \mathbf{A}[x_0, x_1, \dots, x_{N-2}, x_{N-1}]^T.
\end{equation}
We can interpret this DSP operation as a graph operation by recasting $\mathbf{A}$ as an adjacency matrix—a matrix representation of a graph. More precisely, $\mathbf{A}$ corresponds to the adjacency matrix of a directed ring graph $\mathcal{G}=(\mathcal{V,E})$, where $\mathcal{V}$ is a set of $N$ vertices and $\mathcal{E}$ the set of directed edges connecting each vertex to its next neighbor (with the final vertex connecting back to the first). The $N$ elements of the signal or data $x$ are indexed by the $N$ vertices of $\mathcal{V}$, and each element $(\mathbf{A})_{ij}$ is the weight $w_{ij}$ of the edge connecting vertex $i$ to $j$.

This dual role played by the matrix $\mathbf{A}$ is the key to constructing a linear, shift invariant GSP \cite{DSP}. Instead of using only the DSP ring graph, with adjacency matrix given by \eqref{eq:A}, we generalize this to an arbitrary graph in GSP.

We note here that graph shift operators other than $\mathbf{A}$ have been proposed, such as the graph Laplacian $\mathbf{L}=\mathbf{D}-\mathbf{A}$, where $\mathbf{D}$ is the degree matrix of $\mathcal{G}$, defined as the diagonal matrix $(\mathbf{D})_{ii}=\sum_j (\mathbf{A})_{ij}$. Graph Laplacians apply only to undirected graphs, since they are symmetric and positive semidefinite, and have been widely studied within the field of spectral graph theory \cite{ortega_graph_2017}.

\subsection{Graph Convolution}
\label{sec:graphconv}
Under appropriate conditions\footnote{The characteristic and minimal polynomials are the same. To simplify the discussion in the paper, we assume the sufficient condition that the eigenvalues of $\mathbf{A}$ are distinct.}, graph convolution is defined by the matrix vector multiplication
\begin{equation}
\label{eq:gconv}
    \mathbf{G}x = \text{g}(\textbf{A})x =  \sum_{k=0}^K \alpha_k \mathbf{A}^k x, \; K<N
\end{equation}
where $x$ is the graph data or graph signal, $\text{g}(\textbf{A})$ is the polynomial filter of degree $K$, and $\alpha_k$ the $k$-th filter coefficient. In practice, $\mathbf{A}$ is often normalized in some manner to ensure numerical stability. For example, dividing $\textbf{A}$ by $|\lambda_{\text{max}}|$ where $\lambda_{\text{max}}$ is the eigenvalue of $\textbf{A}$ with greatest magnitude, or, with an undirected graph, using $\mathbf{\bar{A}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$ in place of $\mathbf{A}$, where $\mathbf{D}$ is the degree matrix of $\mathbf{A}$. These guarantee that the (non-maximal) eigenvalues of the adjacency matrix are inside the unit circle, thereby making $\mathbf{G}$ computationally stable.

If we reorder the nodes of $\textbf{A}$, then we get an adjacency matrix $\textbf{A}_{\textrm{new}} = \textbf{PAP}^T$, where $\textbf{P}$ is a permutation matrix. This also reorders the graph signal $x$ to become $x_{\textrm{new}}=\textbf{P}x$. Using \eqref{eq:gconv}, graph convolution with permuted graph signal and adjacency matrix becomes
\begin{equation}
    \label{eq:convperm}
    \mathbf{G}_{\textrm{new}}x_{\textrm{new}} = \text{g}(\mathbf{A}_{\textrm{new}})x_{\textrm{new}} =
    \sum_{k=0}^K \alpha_k \mathbf{A}_{\textrm{new}}^k \textbf{P}x =
    \sum_{k=0}^K \alpha_k \textbf{P}\mathbf{A}^k\textbf{P}^T \textbf{P}x =
    \textbf{P} \sum_{k=0}^K \alpha_k \textbf{A}^k x = \textbf{P}\left(\textbf{G}x\right).
\end{equation}
Thus, if we reorder the nodes and convolve, we obtain the original result reordered in the same manner. This is a desirable property for learning architectures because reordering the nodes in $\mathbf{A}$ should not adversely affect the inference result.

\subsection{Frequency Representation}

GSP unifies the vertex and spectral domains of a graph, much as classical signal processing connects the time and frequency domains of a time-series.

In DSP, the discrete Fourier transform (DFT)\footnote{$\text{DFT} = \frac{1}{\sqrt{N}} \left[e^{-\frac{2\pi jkl}{N}}\right]_{k,l = 0,1,\hdots,N-1}$, $j = \sqrt{-1}$. The DFT is unitary; i.e, $\text{DFT}^H = \text{DFT}^{-1}$.} follows from the eigendecomposition of the ring graph adjacency matrix  $\mathbf{A}$ given in \eqref{eq:A},
\begin{equation}
\label{eq:A_eigen}
    \mathbf{A} = \text{DFT}^H\mathbf{\Lambda}\ \text{DFT}.
\end{equation}
Similarly, in GSP, the graph Fourier transform (GFT) is defined by the eigendecomposition of an arbitrary adjacency matrix
\begin{equation}
\label{eq:A_eigengsp}
    \mathbf{A} = \text{GFT}^{-1}\mathbf{\Lambda} \ \text{GFT}.
\end{equation}
The inverse graph Fourier transform $\text{GFT}^{-1}$ is formed with the eigenvectors of $\textbf{A}$. $\text{GFT} = \text{DFT}$ for a directed ring graph where $\textbf{A}$ is in \eqref{eq:A}. The graph spectral representation of the graph signal $x$ is given by $\widehat{x} = \text{GFT}x$.

\section{Graph CNN Architecture}
\label{sec:GCNN}
Like a conventional CNN architecture, a graph CNN architecture also has convolutional, pooling, and fully connected layers (shown in Fig.~\ref{fig:gcnn}). Convolutional and pooling layers can be formulated anew to incorporate graph structure using GSP theory. We describe these layers in this section and explore design considerations in Section~\ref{sec:Use}.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.8\linewidth]{media/fig3.jpg}
    \caption{Graph CNN architecture and kernel, extending CNN elements to graph-structured data. An example graph convolutional filter of degree $1$ is shown. The filter, centered on the blue vertex, aggregates neighborhood information (shown in red) by multiplying the graph signal with a polynomial of shifts to produce an output (shown in green). The filter is applied on each node in the graph.}
    \label{fig:gcnn}
\end{figure}

\subsection{Graph Convolutional Layer}

\label{sec:graphCNN}

Broadly speaking, two approaches to graph CNNs have been pursued, the spectral and the vertex domain approaches. Graph convolution was first generalized from CNNs to graph-structured data in the spectral domain using the graph Laplacian. The spectral approach takes the graph signal $x$, multiplies by GFT to get $\widehat{x}$, and then multiplies by $\text{GFT}^{-1}$ to return to the vertex domain \cite{bronstein_geometric_2017, bruna_spectral_2013}. To avoid the expensive eigendecomposition of \textbf{A} to find the GFT matrix, \cite{defferrard_convolutional_2016} used Chebyshev polynomials to approximate the GFT.

The vertex approach defines convolution in the vertex domain, as given by \eqref{eq:gconv}. These approaches are typified graph convolutional networks (GCNs) \cite{kipf17} and topology-adaptive graph convolutional networks (TAGCNs) \cite{du2017}, which we consider below. Other implementations, like GraphSAGE \cite{hamilton2017} and graph attention network (GATs) \cite{Velickovic2018}, are deep learning approaches defined in the vertex domain, but their kernels do not meet the definition of convolution in GSP.

Consider a graph $\mathcal{G}=(\mathcal{V,E})$, where $\mathcal{V}$ is a set of $N$ vertices defined by graph signal\footnote{For ease of notation, we use $x$ here to refer to the graph signal. If each node has more than one channel ($C>1$), then $x$ can be a matrix.} $x^{(0)} \in \mathbb{R}^{N \times C}$($C$ is the number of signal dimensions, or channels) and $\mathcal{E}$ is defined by its adjacency matrix $\mathbf{A} \in \mathbb{R}^{N \times N}$. The GCN \cite{kipf17} convolutional layer in general form is
\begin{equation}
\label{eq:gcn}
    x^{(\ell+1)}=
    \sigma \left(
    \tilde{\mathbf{A}}
    x^{(\ell)} \mathbf{W}^{(\ell)} \right),
\end{equation}
where $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_N$, $\mathbf{W}^{(\ell)} \in \mathbb{R}^{C \times F}$ is the trainable weight matrix, $\sigma$ is the nonlinear activation function, and $F$ is the number of output features. The layer number is $\ell$, with $\ell=0$ for the input layer. Adding the identity matrix to $\mathbf{A}$ and then normalizing helps address numerical instabilities and vanishing gradients.

The TAGCN implementation of graph convolution \cite{du2017} treats in addition to $\mathbf{W}^{(\ell)}$ the polynomial filter coefficients as learnable weights and their degrees as hyperparameters. We can write the general form of the TAGCN graph convolutional layer as
\begin{equation}
\label{eq:tagcn}
     x^{(\ell+1)} = \sigma \left( x^{(\ell)}\mathbf{W}_0^{(\ell)} + \textbf{A} x^{(\ell)} \mathbf{W}_1^{(\ell)}+ \hdots + \textbf{A}^K x^{(\ell)} \mathbf{W}_K^{(\ell)}
     \right) = \sigma \left(\sum_{k=0}^K \textbf{A}^k x^{(\ell)} \mathbf{W}_k^{(\ell)} \right),
\end{equation}

where $K$ is the degree of the graph polynomial filter.
A visual representation of the TAGCN convolutional layer is shown in Fig.~\ref{fig:gcnn}. A degree 1 graph filter (bottom) uses information from first-order neighbors to compute its output. The polynomial coefficients are learned, similar to the filter coefficients of a CNN. Like a CNN, the filter ``slides'' across the graph from vertex to vertex, and the output is fed to a nonlinear activation function. As mentioned in Section~\ref{sec:graphconv}, we can use normalized versions of $\tilde{\textbf{A}}$ and $\textbf{A}$ in \eqref{eq:gcn}, \eqref{eq:tagcn}.

The graph convolutional layer in GCN \cite{kipf17} and TAGCN \cite{du2017} can be stated in terms of the vertex domain covolution in \eqref{eq:gconv}. Each graph convolutional layer can be interpreted in GSP as: $x' = \sigma\left(\text{g}(\textbf{A}) x\right)$
where $x$ and $x'$ are the input and output of the layer, $\text{g}(\textbf{A})$ a polynomial of degree $K$ and $\sigma$ the nonlinear activation.
By~\eqref{eq:A_eigengsp}, the convolutional layer (ignoring nonlinear activation) can be interpreted in the spectral domain as $\text{g}(\mathbf{\Lambda})\widehat{x}$ with
\begin{equation}
    \label{eqn:Achain}
    \text{g}(\mathbf{A})x = \text{GFT}^{-1}\text{g}(\mathbf{\Lambda})\text{GFT}x =
    \text{GFT}^{-1}\text{g}(\mathbf{\Lambda})\widehat{x} \xrightarrow{\text{GFT}}\text{g}(\mathbf{\Lambda})\widehat{x}.
\end{equation}

\subsection{Graph Pooling Layer}
\label{subsec:graphpoolinglayer-1}
Pooling in some form is usually desirable in graph classification models for two reasons: dimensionality reduction and hierarchical learning. Graph pooling algorithms generally reduce the number of nodes and hence the number of learned parameters of the model. Some pooling algorithms also enforce hierarchical representation of the data, so the graph CNN can learn large-scale and global patterns in the data.

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\linewidth]{media/fig4.png}
    \caption{Graph pooling and graph aggregation. Graph pooling (left) accepts a graph signal and produces a new, representative graph signal indexed by a smaller graph support. Global aggregation (right) can accept graphs of potentially varying sizes and produce fixed-length, representative vectors.}
    \label{fig:pool_aggregation}
\end{figure}
More formally, using the notation in Section~\ref{sec:graphCNN}, graph pooling yields signal $x' \in \mathbb R^{N' \times C}$ and adjacency matrix $\mathbf{A}' \in \mathbb R^{N' \times N'}$, with $N' \leq N$ (shown in Fig.~\ref{fig:pool_aggregation}). Pooling can be understood as a nonlinear downsampling operation. In deep learning, unlike as normally treated in DSP, recoverability is not a key concern for downsampling, and unlike graph convolution, which has a GSP definition, graph pooling has not been rigorously defined. In CNNs, max pooling is usually used, whereas in graph CNNs, there is no consensus how best to pool nodes in a graph. Recent methods of graph pooling include Sort Pooling (SortPool) \cite{zhang2018}, Differentiable Pooling (DiffPool) \cite{ying2018}, Top-k Pool \cite{gao2019}, and Self-Attention Graph Pooling (SagPool) \cite{SagPool2019}. See Fig.~\ref{fig:graph_pooling_methods} for an overview. In Section~\ref{sec:graphsample}, we discuss pooling's connection to sampling in GSP as an open problem.

\begin{figure}[hbtp]
    \centering
    \includegraphics[width=0.8\linewidth]{media/fig5.png}
    \caption{High-level illustrations of recently proposed graph pooling methods. DiffPool \cite{ying2018} uses a graph CNN model to obtain an assignment matrix for clustering the nodes. SagPool \cite{SagPool2019} uses a graph CNN layer to calculate self-attention as mask for pooling the nodes. In SortPool \cite{zhang2018}, graph CNN layers are followed by a ranking of the nodes to select the top nodes. Top-k Pool \cite{gao2019} uses a projection vector to select the the top nodes, which form a new graph.}
    \label{fig:graph_pooling_methods}
\end{figure}

\subsection{Graph Aggregation Layer}
\label{subsec:graphaggregationlayer}
In conventional CNNs, inputs are generally of the same size and have a fixed ordering. However, in graph classification problems, one often needs to consider graphs of various sizes, and with data defined on each graph in an arbitrary node-permuted order (e.g., molecular networks). The resulting vectors that would serve as input to a fully connected layer vary in both size and labeling order, making direct comparison difficult.

The graph aggregation layer, sometimes called the final pooling layer, solves this problem by collapsing the nodes into a fixed number of features, regardless of input size, for comparison (see Fig.~\ref{fig:pool_aggregation}). This is often done using a mean or sum operation over all nodes in a graph. However, several other statistics and approaches can be used. One such heuristic is the family of graph spectral distances, $\textrm{F}_{\textrm{GSD}}$ \cite{verma2017}, which uses the adjacency matrix to capture global information about the graph structure by taking harmonic distances for all nodes. Other approaches include using graph capsules (e.g., GCAPs-CNN \cite{verma2018} and CapsGNN \cite{xinyi2019})

\section{Design Considerations and Applications}
\label{sec:Use}
In this section, we address how the structure of the graph $\mathcal{G}$ defined by its adjacency matrix $\mathbf{A}$ affects the design of graph CNNs for two application areas: node and graph classification. The key difference between graph CNNs and traditional CNNs is how the kernel operations in each layer are implemented. Conventional deep learning algorithms can still be applied (e.g., backpropagation, dropout, and gradient-based optimization). We consider the design of three components of graph CNN architecture: graph convolutional layer, graph pooling layer, and graph aggregation layer.

\subsection{Node Classification}
\label{sec:node_classification}
 %
In node classification, we infer the classes of unlabeled nodes in a graph using the graph's labeled nodes. Common node classification benchmarks are the citation networks, three of which \cite{node_dataset} are visualized in Fig.~\ref{fig:viz}: CORA-ML, CiteSeer and PubMed. On these graphs, each node represents a scientific publication, with bag-of-words feature vectors. An undirected edge is formed between two nodes if one cites the other. Node labels represent different publication categories. In CORA-ML, for example, the labels represent seven subfields of machine learning (e.g., computational biology and natural language processing).

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\linewidth]{media/fig6.png}
    \caption{Visualization \cite{GEPHI} of citation network datasets. Class labels are color-coded.}
    \label{fig:viz}
\end{figure}

\textbf{The effect of representing graph structures:} We first confirm that accounting for the graph structure defined by the adjacency matrix in the neural network significantly improves performance. In Fig.~\ref{fig:graphEffect}, we consider the performance of GCN on the CORA-ML dataset (its graph structure is visualized in Fig.~\ref{fig:viz}). The green trend shows GCN performance when trained with the graph structure of CORA-ML, which significantly outperforms the same model when the graph structure is ignored (i.e., trained with the identity matrix) or randomly generated (i.e., trained with a random Erd\H{o}s-Ren\`yi graph).

\begin{figure}[htbp]
    \centering
    \includegraphics[height=5cm]{media/fig7.png}
    \caption{Comparison of graph CNN test accuracy on the CORA-ML citation network dataset with three types of graph structures: 1)~the dataset's citation network graph, CORA-ML, 2)~the identity matrix, and 3)~an Erd\H{o}s-R\`enyi graph.}
    \label{fig:graphEffect}
\end{figure}

\textbf{Measuring graph structure effectiveness:} For a node classification task, it is natural to ask how useful the graph structure is. To measure this, we consider the graph structure, the number of classes, the label rate, and the content of the graph signal. To this end, we define a graph structure as \textit{effective} if a graph CNN model trained with the adjacency matrix  $\mathbf{A}$ has higher test accuracy than a graph CNN model trained with the identity matrix (which is effectively a neural network that does not incorporate the graph structure). To measure the effectiveness of graph structure a priori, we introduce a metric called edge entropy. Edge entropy measures the quality of the label information encoded in the graph based on the graph's conditional class distribution. A low edge entropy implies a more certain class distribution, and therefore a more useful graph structure for classification. Fig.~\ref{fig:viz} shows that CORA-ML has relatively low edge entropy, because nodes of the same class tend to cluster together. In such a case, the graph structure is helpful because the edges encode predictive label information. For example, if we know a node $u$ is a math paper, and node $v$ is a neighbor of node $u$, then it is likely that node $v$ is also a math paper.

Formally, given a graph $\mathcal{G}$ with~$M$ node classes, we define the $n$-th-order edge entropy of any class $i$ as a function $H_n: \{1, \hdots, M\} \to [0,1]$ such that
\begin{equation}\label{edgeEntropy}
	H_{n}(i) := -\sum_{j \in \{1, \hdots, M\}} p_{ij}(n)\log_{M}(p_{ij}),
\end{equation}
where the $n$-th order interclass connectivity probability $p_{ij}$ is defined as
\begin{equation}\label{connProb}
p_{ij}(n) := \frac{|\{\text{length } n \text{ walk } w: \text{start}(w) \in \mathcal{V}_{i} \land \text{end}(w) \in \mathcal{V}_{j} \}|}{|\{\text{length } n \text{ walk } w: \text{start}(w) \in \mathcal{V}_{i}\}|},
\end{equation}
where $\mathcal{V}_{i}$ is the set of nodes that belong to the $i$-th class, $|\cdot|$ is the cardinality of the set, and $p_{ij}$ is the conditional class distribution of nodes that are a walk of length $n$ away from a node of class $i$ (i.e., $p_{ij}$ is the probability that a node~$v$ belongs to class~$j$ given that there exists a walk of length~$n$ between~$v$ and a node of class~$j$). More comprehensive results and analysis of edge entropy, including other parameters, are to be published elsewhere.

\textbf{How to choose the graph CNN architecture:} Here, we consider the number of convolutional layers. A graph CNN architecture for node classification tasks has graph convolutional layers, but no pooling or aggregation layers (as each node need to be classified). We consider the two graph convolution variants, GCN \cite{kipf17} and TAGCN \cite{du2017}, defined formally in \eqref{eq:gcn} and \eqref{eq:tagcn}. Choosing the polynomial order of each graph convolutional layer is a design consideration for TAGCN, but not GCN. This is because a GCN convolutional layer has a fixed polynomial degree of 1 ($\mathbf{A} + \mathbf{I}$), whereas a TAGCN layer can have degree $K$. Choosing the number of graph convolutional layers is a design consideration for both variants. The objective of such considerations is to sufficiently capture the structure and complexity of the data without oversmoothing: where too much distinguishing information at each node is lost to repeated graph convolutions. Theoretically, if we choose the number of layers such that the overall order $K$ is the graph diameter (longest shortest path length) in the given graph structure, then the model can learn to combine the information of any two nodes. In practice, a small number of layers (e.g., 2) will perform better unless oversmoothing is addressed in some way \cite{oversmooth}. For citation networks, our results show that 2 layers generally give the best performance (see Section~\ref{subsec:graph_convolution_results}, Fig.~\ref{fig:node_classification_results}).

\subsection{Graph Classification}
\label{sec:graph_classification}

In graph classification, we infer the classes of unlabeled graphs, given a set of labeled graphs (with graph structures, graph signals, and class labels given a strict subset of graphs). This is analogous to the image classification task seen in computer vision. For example, in MUTAG \cite{graphstat}, molecules are graphs defined according to the chemical bonds between atoms and the task is to predict whether a molecule is mutagenic or not.

\textbf{How to choose the graph CNN architecture:} Here, we consider the graph convolutional layer, graph pooling layer, and aggregation layer. In graph classification, large-scale or global structure may be important. For example, predictive structural relationships may exist between large subgraph structures that are not visible between individual nodes or small neighborhoods. It is helpful to consider the sparsity or connectedness of the graphs in question using network parameters like average degree and graph diameter. These parameters can inform graph CNN architecture design.

We consider the two graph convolution variants: GCN \cite{kipf17} and TAGCN \cite{du2017}. As shown in \eqref{eq:gcn} and \eqref{eq:tagcn}, GCN considers the immediate neighbors of each node in each layer (one hop away), and  TAGCN, with a polynomial filter of degree $K$, considers nodes that are~$K$ hops away in each layer. In GCN convolution, after $\ell$ layers, each node has only received information from nodes~$\ell$ hops away. With polynomial filters of degree~$K$ in TAGCN, the output at the $i$-th node of the $\ell$-th layer depends on the input values of nodes up to $K\ell$ hops away. TAGCN presents an interesting tradeoff between number of layers and degree of the polynomial filters used by the model. For denser graphs, it is possible to cover the entire graph using just a few graph convolutional layers (so that each node has information from most if not all of the other nodes). In general, we find that if the average degree is high and the diameter is small, the nodes are more connected and, therefore, fewer convolutional layers are needed.

Beyond the convolutional layer, there are design choices for pooling and aggregation layers. If we add pooling layers and cluster the nodes before the aggregation layer, as in DiffPool \cite{ying2018} and Top-k Pool \cite{gao2019}, we can capture hierarchical structure (see Section~\ref{subsec:graphpoolinglayer-1}). Some other approaches include embedding graphs as a feature (e.g., family of graph spectral distances (F$_{\text{GSD}}$) \cite{verma2017}), and using multiple statistics or attention-based capsules to capture more global information (see Section~\ref{subsec:graphaggregationlayer}). Results are shown in Section~\ref{sec:res} Fig.~\ref{fig:pooling_results} and Fig.~\ref{fig:aggregation_results}.

\section{Results}
\label{sec:res}

\subsection{Graph Convolution}
\label{subsec:graph_convolution_results}

We compare GCNs \cite{kipf17} and TAGCNs \cite{du2017} for node and graph classification on popular benchmark datasets in Fig.~\ref{fig:node_classification_results} and Fig.~\ref{fig:pooling_results} (``No pool''), respectively. See \cite{node_dataset,graphstat} for descriptions of datasets. For TAGCN, we consider graph polynomial filters up to degree 3. We perform all experiments using the PyTorch Geometric Library \cite{fey2019}.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.4\textwidth]{media/fig8.png}
    \caption{Comparison of graph CNN variants for node classification on benchmark datasets (see \cite{node_dataset} for dataset descriptions and \cite{kipf17} for experimental setup). The horizontal black line represents the mean accuracy and the vertical line represents the standard deviation.}

    \label{fig:node_classification_results}

\end{figure}

In general, TAGCN performs better than GCN for both node and graph classification in terms of mean classification accuracy. However, the TAGCN filtering operation has more complexity, overfitting more easily and may lead to higher variance. For node classification on citation networks, GCN and TAGCN empirically perform poorly with more than 2 layers, as they tend to oversmooth. For graph classification, GCN and TAGCN require more layers to achieve high performance on sparser graphs, as measured by average degree or graph diameter. For a more in-depth discussion, see \cite{du2017}.

\subsection{Graph Pooling}
\label{subsec:graph_pool_results}
We compare different pooling algorithms for graph classification used with graph CNNs on popular benchmark datasets (see \cite{graphstat} for descriptions of datasets) in Fig.~\ref{fig:pooling_results} \footnote{We include GraphSAGE in some of our analysis as it is used in some of the original papers.}. In general, pooling helps if the graphs are sparse (MUTAG, PROTEINS, IMDB-B, and REDDIT-B). We conjecture that DiffPool generally performs better on the benchmark datasets because it learns a new graph structure and signal (instead of selecting from existing nodes and edges). SagPool and SortPool perform better for MUTAG and PROTEINS, but they are similar or worse for IMDB-B and REDDIT-B. TAGCN tends to perform better than the other architectures.  For a more in-depth discussion, see \cite{cheung2019}.

\setlength{\belowcaptionskip}{0pt}
\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{media/fig9.png}
     \caption{Comparison of pooling methods for graph classification on benchmark datasets (see \cite{graphstat} for dataset descriptions). The horizontal black line represents the mean accuracy and the vertical line represents the standard deviation.}
      \label{fig:pooling_results}

\end{figure}
\setlength{\belowcaptionskip}{-10pt}
\subsection{Graph Aggregation}

We compare different graph aggregation methods for graph classification used with graph CNNs on popular benchmark datasets (see \cite{graphstat} for descriptions of datasets) in Fig.~\ref{fig:aggregation_results} \footnotemark \footnotetext{The results for $\textrm{F}_{\textrm{GSD}}$, GCAPS-CNN and CapsGNN are taken from \cite{verma2017}, \cite{verma2018}, and \cite{xinyi2019}, respectively, and blank if no results are provided for given datasets.}. In general, for graph CNNs, there is no single best aggregation method across the considered datasets. However, certain aggregation methods may be complementary (e.g., combining mean and variance leads to an increase in accuracy), but some combinations lead to overfitting (e.g., combining mean and max actually reduces the test accuracy for the IMDB-B dataset). Capsule-based techniques improve the performance for some datasets (e.g.  GCAPS-CNN and CapsGNN improve performance for the MUTAG and PROTEINS datasets). Some datasets are classified well using just the graph structure but not the graph signal (e.g., MUTAG, PROTEINS, IMDB-B show good accuracy with $\textrm{F}_{\textrm{GSD}}$, which does not consider graph signals).

\begin{figure}
     \centering
    \includegraphics[width=\linewidth]{media/fig10.png}
        \caption{Comparison of aggregation methods for graph classification on benchmark datasets (see \cite{graphstat} for dataset descriptions). The horizontal black line represents the mean accuracy and the vertical red line represents the standard deviation.}
        \label{fig:aggregation_results}
\end{figure}

\section{Conclusion}
\label{sec:Conc}
Inference tasks on graph-structured data demand learning architectures that can adequately model non-Euclidean structure, and GSP---e.g., with graph filters of different degrees---provides a principled methodology for the design and analysis of those architectures. As the field continues to develop, new connections will emerge and the formalism of GSP should continue to play a significant role in deep learning on graphs.

The identity matrix case shown in Fig.~\ref{fig:graphEffect} is analogous to ignoring the graph structure and applying a multilayer perceptron (MLP) to the problem. When comparing deep learning architectures, it is typical to compare them in terms of their representational power, but this is insufficient for understanding potential performance. CNNs, for example, are not as general as MLPs, but in practice are far more effective in domains where shift invariance is important. Shift invariance is invaluable for vision-based pattern recognition, but, like Tolstoy's unhappy families\footnote{``Happy families are all alike; every unhappy family is unhappy in its own way,'' from \textit{Anna Karenina} (1877) by Leo Tolstoy.}, no graph problems are alike: there is no guarantee that the properties that make a particular deep learning architecture effective on one class of graph-structured problems apply to another. The data and structure of the problem domain are as important as the learning architecture itself, and this importance only grows in the irregular world of geometric deep learning.

We identify some open research questions on the application of GSP to  deep learning:
\begin{itemize}
    \item \textbf{Different kernels for graph convolution:} GCN and TAGCN define the convolutional layer in terms of the adjacency matrix. \textit{Can we use other kernels?} One candidate is spectral domain convolution, introduced in \cite{shisample}, a polynomial of the spectral domain shift $\textbf{M} = \textrm{GFT} \Lambda^* \textrm{GFT}^{-1}$ where $\Lambda^*$ is the complex conjugate of the matrix of eigenvalues in \eqref{eq:A_eigengsp}.

    \item \textbf{When graph CNNs fail:}
 Popular graph CNNs can incorrectly produce the same output for non-isomorphic graphs \cite{XuHLJ19}. GCN and TAGCN work well in practice, but fail on certain edge cases. \textit{What approaches can we take to prevent graph CNN failure in these cases? How can we increase the expressive power of graph CNNs?}

    \item \textbf{Interpretability of graph pooling methods:} \label{sec:graphsample}
    Reference \cite{shisample} presents sampling methods in both the vertex domain and the spectral domain. \textit{How can we relate aforementioned pooling algorithms (e.g., DiffPool, SagPool) to GSP sampling theory? How can we use GSP sampling theory to develop novel pooling methods?}

    \item \textbf{Other Problems:} GSP can also be used to tackle other research directions for graph CNNs, including model depth, oversmoothing \cite{oversmooth}, scalability, heterogenity, dynamicity, and interpretability (see \cite{review1, review2} for more details).
\end{itemize}
{
\pagebreak

\paragraph{Authors:}  \mbox{} \\
\textbf{Mark Cheung} (\href{mailto:markcheu@andrew.cmu.edu}{markcheu@andrew.cmu.edu}) received his B.S. degrees in Electrical Engineering and Computer Engineering in 2014 from University of Virginia. He is currently a Ph.D. candidate in the Electrical and Computer Engineering Department at Carnegie Mellon University. His research interests include geometric deep learning and neuroscience.

\noindent \textbf{John Shi} (\href{mailto:jshi3@andrew.cmu.edu}{jshi3@andrew.cmu.edu}) received his B.S. degrees in Computer Engineering and Applied Mathematics in 2017 from the University of Maryland, College Park. He is currently a Ph.D. candidate in the Electrical and Computer Engineering Department at Carnegie Mellon University. His research interests include graph signal processing theory and applications.

\noindent \textbf{Oren Wright} (\href{mailto:owright@sei.cmu.edu}{owright@sei.cmu.edu}) received his B.S. degree in 2010 and his M.S. degree in 2011 in Electrical and Computer Engineering from Carnegie Mellon University. In 2016, he joined the Carnegie Mellon University Software Engineering Institute, where he has since led research in machine learning and its application to critical defense problems.

\noindent \textbf{Lavender Yao Jiang} (\href{mailto:lavenderjiang@cmu.edu}{lavenderjiang@cmu.edu}) is an undergraduate student in the Electrical and Computer Engineering Department and the Mathematical Sciences Department at Carnegie Mellon University. Her research interests include evaluating the quality of graphs and biomedical applications of graph signal processing.

\noindent \textbf{Xujin Liu} (\href{mailto:xujinl@andrew.cmu.edu}{xujinl@andrew.cmu.edu}) is an undergraduate student in the Electrical and Computer Engineering Department at Carnegie Mellon University. His research interests include graph theory, graph neural networks, and their application to biomedical fields.

\noindent \textbf{Jos\'e M.F. Moura} (\href{mailto:moura@andrew.cmu.edu}{moura@andrew.cmu.edu}) is the Philip L. and Marsha Dowd University Professor at Carnegie Mellon University. The technology of two of his patents (co-inventor Alek Kavcic) are in over four billion disk drives in 60\% of all computers sold worldwide in the last 15 years. He is Fellow of IEEE, AAAS, and U.S. National Academy of Inventors, corresponding member of Portugal Academy of Sciences, and member of U.S. National Academy of Engineers. He holds a Doctor Honoris Causa from University of Strathclyde, UK, and received the Grand Cross of the Order of Prince Henry from the President of the Republic of Portugal. He was 2019 IEEE President and CEO. }

\pagebreak
\singlespacing
\bibliographystyle{IEEEtran}