

\subsection{Preliminaries}

Consider an undirected graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ composed of a node set $\mathcal{V}$ of cardinality $|\mathcal{V}|=N$, and an edge set $\mathcal{E}$ connecting nodes. 
\textit{Graph signal} refers to data/features associated with the nodes of $\mathcal{G}$, denoted by $\mathbf{X} \in \mathbb{R}^{N \times C}$ with $i$th row representing the $C$-dimensional graph signal at the $i$th node of $\mathcal{V}$.

To characterize the similarities (and thus the graph structure) among node signals, an \textit{adjacency matrix} $\mathbf{A}$ is defined on $\mathcal{G}$, which is a real-valued symmetric $N \times N$ matrix with $a_{i,j}$ as the weight assigned to the edge $(i,j)$ connecting nodes $i$ and $j$. 
Formally, the adjacency matrix is constructed from graph signals as follows,
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    \mathbf{A} = f(\mathbf{X}),
    \label{eq:A_X}
\end{equation}
where $f(\cdot)$ is a linear or non-linear function applied to each pair of nodes to get the pair-wise similarity. For example, a widely adopted function is to nonlinearly construct a $k$-nearest-neighbor ($k$NN) graph from node features \cite{wang2019dynamic,zhang2018graph}.

\begin{figure*}[t]
    \centering
    \subfigure[Original model]{
    \includegraphics[width=0.18\textwidth]{aero.pdf}
    }
    \subfigure[Global+Isotropic]{
    \includegraphics[width=0.18\textwidth]{global_same.pdf}
    }
    \subfigure[Global+Anisotropic]{
    \includegraphics[width=0.18\textwidth]{global_different.pdf}
    }
    \subfigure[Local+Isotropic]{
    \includegraphics[width=0.18\textwidth]{local_same.pdf}
    }
    \subfigure[Local+Anisotropic]{
    \includegraphics[width=0.18\textwidth]{local_different.pdf}
    }
    \caption{\textbf{Demonstration of different sampling (Global or Local) and node-wise \textit{translation} (Isotropic or Anisotropic) methods on 3D point clouds.} Red and blue points represent transformed and non-transformed points, respectively. Note that we adopt the wing as a sampled local point set for clear visualization.}
    \label{fig:sampling_transform}
    \vspace{-0.2in}
\end{figure*}

\vspace{-0.05in}
\subsection{Graph Signal Transformation}

Unlike Euclidean data like images, graph signals are irregularly sampled, whose transformations are thus nontrivial to define.
To this end, we define a graph transformation on the signals $\mathbf{X}$ as node-wise \textit{filtering} on $\mathbf{X}$. 


Formally, suppose we sample a graph transformation $\mathbf{t}$ from a transformation distribution $\mathcal{T}_g$, \textit{i.e.}, $\mathbf{t} \sim \mathcal{T}_g$. 
Applying the transformation to graph signals $\mathbf{X}$ that are sampled from data distribution $\mathcal{X}_g$, \textit{i.e.}, $\mathbf{X} \sim \mathcal{X}_g$, leads to the filtered graph signal
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    \tilde{\mathbf{X}}=\mathbf{t}(\mathbf{X}).
    \label{eq:graph_signal_t}
\end{equation}

The filter $\mathbf t$ is applied to each node individually, which can be either node-invariant or node-variant. In other words, the transformation of each node signal associated with $\mathbf t$  can be different from each other. For example, for a  translation $\mathbf t$, a distinctive translation can be applied to each node. We will call the graph transformation isotropic (anisotropic) if it is node-invariant (variant).

Consequently, the adjacency matrix of the transformed graph signal $\tilde{\mathbf{X}}$ equivaries according to \eqref{eq:A_X}:
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    \tilde{\mathbf{A}} = f(\tilde{\mathbf{X}}) = f(\mathbf{t}(\mathbf{X})),
\end{equation}
which transforms the \textit{graph structures}, as edge weights are also filtered by $\mathbf{t}(\cdot)$.

Under this definition, there exist a wide spectrum of graph signal transformations. 
Examples include affine transformations (translation, rotation and shearing) on the location of nodes (\textit{e.g.}, 3D coordinates in point clouds), and graph filters such as low-pass filtering on graph signals by the adjacency matrix \cite{sandryhaila2013discrete}.  

\vspace{-0.05in}
\subsection{Node-wise Graph Signal Transformation}

As aforementioned, in this paper, we focus on \textit{node-wise} graph signal transformation, {\it i.e.}, each node has its own transformation, either isotropically or anisotropically. 
We seek to learn graph representations through the node-wise transformations by revealing how different parts of graph structures would change globally and locally.

Specifically, here are two distinct advantages.
\begin{itemize}
    \item The node-wise transformations allow us to use node sampling to study different parts of graphs under various transformations. 
    \item By decoding the node-wise transformations, we will be able to learn the representations of individual nodes. Moreover, these node-wise representations will not only capture the local graph structures under these transformations, but also contain global information about the graph when these nodes are sampled into different groups over iterations during training.
\end{itemize}

Next, we discuss the formulation of learning graph transformation equivariant representations by decoding the node-wise transformations via a graph-convolutional encoder and decoder.




\subsection{The Formulation}

Given a pair of graph signal and adjacency matrix $(\mathbf{X}, \mathbf{A})$, and a pair of {\em transformed} graph signal and adjacency matrix $(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$ by a node-wise graph transformation $\mathbf{t}$, a function $E(\cdot)$ is \textit{transformation equivariant} if it satisfies
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    E(\tilde{\mathbf{X}}, \tilde{\mathbf{A}}) = E\left(\mathbf{t}(\mathbf{X}), f\left(\mathbf{t}(\mathbf{X})\right)\right) = \rho(\mathbf{t})\left[E(\mathbf{X}, \mathbf{A})\right],
    \label{eq:ter}
\end{equation}
where $\rho(\mathbf{t})$ is a homomorphism of transformation $\mathbf{t}$ in the representation space.

Our goal is to learn a function $E(\cdot)$, which extracts equivariant representations of graph signals $\mathbf{X}$. 
For this purpose, we employ an encoder-decoder network: we learn a graph encoder $E: (\mathbf{X},\mathbf{A}) \mapsto E(\mathbf{X},\mathbf{A})$, which encodes the feature representations of individual nodes from the graph. 
To ensure the transformation equivariance of representations, we train a decoder $D: \left(E(\mathbf{X},\mathbf{A}), E(\tilde{\mathbf{X}},\tilde{\mathbf{A}})\right) \mapsto \hat{\mathbf{t}}$ to estimate the node-wise transformation $\hat{\mathbf{t}}$ from the representations of the original and transformed graph signals. 
Hence, we cast the learning problem of transformation equivariant representations as the joint training of the representation encoder $E$ and the transformation decoder $D$. It has been proved that the learned representations in this way satisfy the generalized transformation equivariance without relying on a linear representation of graph structures \cite{qi2019avt}. 

Further, we sample a subset of nodes $\mathbf S$ following a sampling distribution $\mathcal S_g$ from the original graph signal $\mathbf X$, locally or globally in order to reveal graph structures at various scales. 
Node-wise transformations are then performed on the subset $\mathbf S$ isotropically or anisotropically, as demonstrated in Fig.~\ref{fig:sampling_transform}. 
In order to predict the node-wise transformation $\mathbf{t}$, we choose a loss function $\ell_\mathbf S(\mathbf{t}, \hat{\mathbf{t}})$ that quantifies the distance between $\mathbf{t}$ and its estimate $\hat{\mathbf{t}}$ in terms of their parameters. 
Then the entire network is trained end-to-end by minimizing the loss
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    \min_{E,D} \;
    \underset{\mathbf S \sim \mathcal S_g}{\mathbb E}~\underset{\mathbf X \sim \mathcal X_g}{\underset{\mathbf{t} \sim \mathcal{T}_g}{\mathbb E}}
     ~ \ell_\mathbf S(\mathbf{t}, \hat{\mathbf{t}}),
    \label{eq:loss}
\end{equation}
where the expectation $\mathbb{E}$ is taken over the sampled graph signals and transformations, and the loss is taken over the (locally or globally) sampled subset $\mathbf S$ of nodes in each iteration of training. 

In \eqref{eq:loss}, the node-wise transformation $\hat{\mathbf{t}}$ is estimated from the decoder
\begin{equation}
    \setlength{\abovedisplayskip}{3pt}
    \setlength{\belowdisplayskip}{3pt}
    \hat{\mathbf{t}} = D\left(E(\mathbf{X},\mathbf{A}), E(\tilde{\mathbf{X}},\tilde{\mathbf{A}})\right).
\end{equation}
Thus, we update the parameters in encoder $E$ and decoder $D$ iteratively by backward propagation of the loss.

 
\begin{figure}[t]
    \centering
    \includegraphics[width=8.3cm]{framework.pdf}
    \caption{\textbf{The architecture of the proposed GraphTER.} 
    In the unsupervised feature learning stage, the representation encoder and transformation decoder are jointly trained by minimizing (\ref{eq:loss}). In the supervised evaluation stage, the first several blocks of the encoder are fixed with frozen weights and a linear classifier is trained with labeled samples.
    }
    \label{fig:framework}
    \vspace{-0.2in}
\end{figure}

\vspace{-0.05in}
\subsection{The Algorithm}

Given graph signals $\mathbf{X}=\{\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_N\}^{\top}$ over $N$ nodes, in each iteration of training, we \textit{randomly sample} a subset of nodes $\mathbf S$ from the graph, either globally or locally. 
Global sampling refers to random sampling over the entire nodes globally, while local sampling is limited to a local set of nodes in the graph.
Node sampling not only enables us to characterize global and local graph structures at various scales, but also reduces the number of node-wise transformation parameters to estimate for computational efficiency.

Then we draw a node-wise transformation $\mathbf{t}_i$ corresponding to each sample $\mathbf{x}_i$ of nodes in $\mathbf S$, either isotropically or anisotropically. 
Accordingly, the graph $\tilde{\mathbf{A}}$ associated with the transformed graph also transforms equivariantly from the original $\mathbf{A}$ under $\mathbf t$.
Specifically, as illustrated in Fig.~\ref{fig:node_wise_transform}, we construct a $k$NN graph to make use of the connectivity between the nodes, whose matrix representation in $\mathbf{A}$ changes after applying the sampled node-wise transformations. 

To learn the applied node-wise transformations, we design a full graph-convolutional auto-encoder network as illustrated in Fig.~\ref{fig:framework}.
Among various paradigms of GCNNs, we choose EdgeConv \cite{wang2019dynamic} as a basic building block of the auto-encoder network, which efficiently learns node-wise representations by aggregating features along all the edges emanating from each connected node. Below we will explain the representation encoder and the transformation decoder in detail.

\vspace{-0.05in}
\subsubsection{Representation Encoder}

The representation encoder $E$ takes the signals of an original graph $\mathbf{X}$ and the transformed counterparts $\tilde{\mathbf{X}}$ as input, along with their corresponding graphs. 
$E$ encodes node-wise features of $\mathbf{X}$ and $\tilde{\mathbf{X}}$ through a Siamese encoder network with shared weights, where EdgeConv layers are used as basic feature extraction blocks.
As shown in Fig.~\ref{fig:node_wise_transform}, given a non-transformed central node $\mathbf{x}_i$ and its transformed neighbors $\mathbf{t}_j(\mathbf{x}_j)$, the input layer of encoded feature of $\mathbf{x}_i$ is
\begin{equation}
\setlength{\abovedisplayskip}{3pt}
\setlength{\belowdisplayskip}{3pt}
\begin{split}
    E_{\text{in}}(\tilde{\mathbf{X}}, \tilde{\mathbf{A}})_i & = \underset{j \in \mathcal{N}(i)}{\max} \; \tilde{a}_{i,j} \\
    & = \underset{j \in \mathcal{N}(i)}{\max} \; \text{ReLU}(\theta(\mathbf{t}_j(\mathbf{x}_j)-\mathbf{x}_i) + \phi \mathbf{x}_i),
\end{split}
\label{eq:encoding}
\end{equation}
where $\tilde{a}_{i,j}$ denotes the edge feature, {\it i.e.}, edge weight in $\tilde{\mathbf{A}}$. 
$\theta$ and $\phi$ are two weighting parameters,
and $j \in \mathcal{N}(i)$ denotes node $j$ is in the $k$-nearest neighborhood of node $i$. 
Then, multiple layers of regular edge convolutions \cite{wang2019dynamic} are stacked to form the final encoder.

Edge convolution in (\ref{eq:encoding}) over each node essentially aggregates features from neighboring nodes via {\it edge weights} $\tilde{a}_{i,j}$. 
Since the edge information of the underlying graph transforms with the transformations of individual nodes as demonstrated in Fig.~\ref{fig:node_wise_transform}, edge convolution is able to extract higher-level features from the original and transformed edge information.
Also, as features of each node are learned via propagation from transformed and non-transformed nodes isotropically or anisotropically by both local or global sampling, the learned representation is able to capture intrinsic graph structures at multiple scales.   

\vspace{-0.05in}
\subsubsection{Transformation Decoder}

Node-wise features of the original and transformed graphs are then concatenated at each node, which are then fed into the transformation decoder.
The decoder consists of several EdgeConv blocks to aggregate the representations of both the original and transformed graphs to predict the node-wise transformations $\mathbf{t}$. 
Based on the loss in \eqref{eq:loss}, $\mathbf{t}$ is decoded by minimizing the mean squared error (MSE) between the ground truth and estimated transformation parameters at each sampled node. Fig.~\ref{fig:framework} illustrates the architecture of learning the proposed GraphTER in such an auto-encoder structure.





















\subsection{Datasets and Experimental Setup}

\textbf{ModelNet40} \cite{wu20153d}. This dataset contains $12,311$ meshed CAD models from $40$ categories, where $9,843$ models are used for training and $2,468$ models are for testing. 
For each model, $1,024$ points are sampled from the original mesh.
We train the unsupervised auto-encoder and the classifier under the training set, and evaluate the classifier under the testing set.

\textbf{ShapeNet part} \cite{yi2016scalable}. This dataset contains $16,881$ 3D point clouds from $16$ object categories, annotated with $50$ parts. 
Each 3D point cloud contains $2,048$ points, most of which are labeled with fewer than six parts.
We employ $12,137$ models for training the auto-encoder and the classifier, and $2,874$ models for testing.

We treat points in each point cloud as nodes in a graph, and the $(x,y,z)$ coordinates of points as graph signals. 
A $k$NN graph is then constructed on the graph signals to guide graph convolution.

Next, we introduce our node-wise graph signal transformation. In experiments, we sample a portion of nodes with a sampling rate $r$ from the entire graph to perform node-wise transformations, including 
1) \textbf{Global sampling:} randomly sample $r\%$ of points from all the points in a 3D point cloud;
2) \textbf{Local sampling:} randomly choose a point and search its $k$ nearest neighbors in terms of Euclidean distance, forming a local set of $r\%$ of points.

Then, we apply three types of node-wise transformations to the coordinates of point clouds, including 
1) \textbf{Translation:} randomly translate each of three coordinates of a point by three parameters in the range $[-0.2, 0.2]$;
2) \textbf{Rotation:} randomly rotate each point with three rotation parameters all in the range $[\ang{-5},\ang{5}]$;
3) \textbf{Shearing}: randomly shear the $x$-, $y$-, $z$-coordinates of each point with the six parameters of a shearing matrix in the range $[-0.2, 0.2]$.
We consider two strategies to transform the sampled nodes: \textbf{Isotropically} or \textbf{Anisotropically}, which applies transformations with node-invariant or node-variant parameters.

\begin{table}[t]
\centering
\small
\caption{Classification accuracy (\%) on ModelNet40 dataset.}
\label{tab:classification}
\begin{tabular}{rcccc}
\hline
\multicolumn{1}{c}{\textbf{Method}} & \textbf{Year} & \textbf{Unsupervised} & \textbf{Accuracy} \\ \hline
3D ShapeNets \cite{wu20153d} & 2015 & No & 84.7 \\
VoxNet \cite{maturana2015voxnet} & 2015 & No & 85.9 \\
PointNet \cite{qi2017pointnet} & 2017 & No & 89.2 \\
PointNet++ \cite{qi2017pointnet++} & 2017 & No & 90.7 \\
KD-Net \cite{klokov2017escape} & 2017 & No & 90.6 \\
PointCNN \cite{li2018pointcnn} & 2018 & No & 92.2 \\
PCNN \cite{atzmon2018point} & 2018 & No & 92.3 \\
DGCNN \cite{wang2019dynamic} & 2019 & No & 92.9 \\
RS-CNN \cite{liu2019relation} & 2019 & No & 93.6 \\ \hline
T-L Network \cite{girdhar2016learning} & 2016 & Yes & 74.4 \\
VConv-DAE \cite{sharma2016vconv} & 2016 & Yes & 75.5 \\
3D-GAN \cite{wu2016learning} & 2016 & Yes & 83.3 \\
LGAN \cite{achlioptas2018learning} & 2018 & Yes & 85.7 \\
FoldingNet \cite{yang2018foldingnet} & 2018 & Yes & 88.4 \\
MAP-VAE \cite{han2019multi} & 2019 & Yes & 90.2 \\
L2G-AE \cite{liu2019l2g} & 2019 & Yes & 90.6 \\ \hline
GraphTER & & Yes & \textbf{92.0} \\ \hline
\end{tabular}
\vspace{-0.2in}
\end{table}

\vspace{-0.05in}
\subsection{Point Cloud Classification}

First, we evaluate the GraphTER model on the ModelNet40 \cite{wu20153d} dataset for point cloud classification.

\vspace{-0.1in}
\subsubsection{Implementation Details}

In this task, the auto-encoder network is trained via the SGD optimizer with a batch size of $32$. 
The momentum and weight decay rate are set to $0.9$ and $10^{-4}$, respectively. 
The initial learning rate is $0.1$, and then decayed using a cosine annealing schedule \cite{loshchilov2016sgdr} for $512$ training epochs. 
We adopt the cross entropy loss to train the classifier.

We deploy eight EdgeConv layers as the encoder, and the number $k$ of nearest neighbors is set to $20$ for all EdgeConv layers. 
Similar to \cite{wang2019dynamic}, we use shortcut connections for the first five layers to extract multi-scale features, where we concatenate features from these layers to acquire a $1,024$-dimensional node-wise feature vector. 
After the encoder, we employ three consecutive EdgeConv layers as the decoder -- the output feature representations of the Siamese encoder first go through a channel-wise concatenation, which are then fed into the decoder to estimate node-wise transformations.
The batch normalization layer and LeakyReLU activation function with a negative slope of $0.2$ is employed after each convolutional layer.

During the training procedure of the classifier, the first five EdgeConv layers in the encoder are used to represent input cloud data by node-wise concatenating their output features with the weights frozen. After the five EdgeConv layers, we apply three fully-connected layers node-wise to the aggregated features. Then, global max pooling and average pooling are deployed to acquire the global features, after which three fully-connected layers are used to map the global features to the classification scores. Dropout with a rate of $0.5$ is adopted in the last two fully-connected layers.

\vspace{-0.1in}
\subsubsection{Experimental Results}
Tab.~\ref{tab:classification} shows the results for 3D point cloud classification, where the proposed model applies isotropic node-wise shearing transformation with a global sampling rate of $r=25\%$.
We compare with two classes of methods: unsupervised approaches and supervised approaches. 
The GraphTER model achieves 92.0\% of classification accuracy on the ModelNet40 dataset, which outperforms the state-of-the-art unsupervised methods. 
In particular, most of the compared unsupervised models combine the ideas of both GAN and AED, and map 3D point clouds to unsupervised representations by auto-encoding data, such as FoldingNet \cite{yang2018foldingnet}, MAP-VAE \cite{han2019multi} and L2G-AE \cite{liu2019l2g}. 
Results show that the GraphTER model achieves significant improvement over these methods, showing the superiority of the proposed node-wise AET over both the GAN and AED paradigms. 

Moreover, the unsupervised GraphTER model also achieves comparable performance with the state-of-the-art fully supervised results.
This significantly closes the gap between unsupervised approaches and the fully supervised counterparts in literature. 

\vspace{-0.1in}
\subsubsection{Ablation Studies}

Further, we conduct ablation studies under various experimental settings of sampling and transformation strategies on the ModelNet40 dataset.

First, we analyze the effectiveness of different node-wise transformations under global or local sampling.
Tab.~\ref{tab:diff_transform} presents the classification accuracy with three types of node-wise transformation methods.
We see that the shearing transformation achieves the best performance,  improving by 1.05\% on average over translation, and 0.52\% over rotation.
This shows that the proposed GraphTER model is able to learn better feature representations under more complex transformations.

Moreover, we see that the proposed model achieves an accuracy of 90.70\% on average under global sampling, which outperforms local sampling by 0.46\%.
This is because global sampling better captures the global structure of graphs, which is crucial in such a graph-level task of classifying 3D point clouds.
Meanwhile, under the two sampling strategies, the classification accuracy from isotropic transformations is higher than that from the anisotropic one.
The reason lies in the intrinsic difficulty of training the transformation decoder with increased complexity of more parameters when applying anisotropic transformations. 

\begin{table}[t]
\centering
\small
\caption{Unsupervised classification accuracy (\%) on ModelNet40 dataset with different sampling and transformation strategies.}
\label{tab:diff_transform}
\begin{tabular}{c|cc|cc|c}
\hline
\multirow{2}{*}{} & \multicolumn{2}{c|}{Global Sampling} & \multicolumn{2}{c|}{Local Sampling} & \multirow{2}{*}{Mean} \\ \cline{2-5}
 & Iso. & Aniso. & Iso. & Aniso. & \\ \hline
Translation & 90.15 & 90.15 & 89.91 & 89.55 & 89.94 \\
Rotation & 91.29 & 90.24 & 90.48 & 89.87 & 90.47 \\
Shearing & \textbf{92.02} & \textbf{90.32} & \textbf{91.65} & \textbf{89.99} & \textbf{90.99} \\ \hline
\multirow{2}{*}{Mean} & \textbf{91.15} & 90.24 & \textbf{90.68} & 89.80 & \\ \cline{2-5}
 & \multicolumn{2}{c|}{\textbf{90.70}} & \multicolumn{2}{c|}{90.24} &  \\ \hline
\end{tabular}
\vspace{-0.1in}
\end{table}

Moreover, we evaluate the effectiveness of different sampling rates $r$ under the translations as reported in Tab.~\ref{tab:sample_rate}.
The classification accuracies under various sampling rates are almost the same, and the result under $r=25\%$ is comparable to that under $r=100\%$. 
This shows that the performance of the proposed model is insensitive to the variation of sampling rates, {\it i.e.}, applying node-wise transformations to a small number of nodes in the graph is sufficient to learn intrinsic graph structures.  



\begin{table}[t]
\centering
\small
\caption{Unsupervised classification accuracy (\%) on ModelNet40 dataset applying translation at different node sampling rates.}
\label{tab:sample_rate}
\begin{tabular}{c|cc|cc|c}
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Sampling\\ Rate\end{tabular}} & \multicolumn{2}{c}{Global Sampling} & \multicolumn{2}{c|}{Local Sampling} & \multirow{2}{*}{Mean} \\ \cline{2-5}
 & Iso. & Aniso. & Iso. & Aniso. & \\ \hline
25\% & 90.15 & 90.15 & 89.91 & 89.55 & 89.94 \\
50\% & 90.03 & 89.63 & 89.95 & 89.47 & 89.77 \\
75\% & 91.00 & 89.67 & 91.41 & 89.75 & 90.46 \\
100\% & 89.67 & 89.99 & 89.67 & 89.99 & 89.83 \\ \hline
\end{tabular}
\vspace{-0.1in}
\end{table}






\begin{table*}[t]
\centering
\scriptsize
\caption{Part segmentation results on ShapeNet part dataset. Metric is mIoU(\%) on points.}
\label{tab:segmentation}
\begin{tabular}{r|p{0.65cm}<{\centering}|p{0.5cm}<{\centering}|p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}p{0.4cm}<{\centering}}
\hline
 & Unsup. & Mean & Aero & Bag & Cap & Car & Chair & \begin{tabular}[c]{@{}c@{}}Ear\\ Phone\end{tabular} & Guitar & Knife & Lamp & Laptop & Motor & Mug & Pistol & Rocket & \begin{tabular}[c]{@{}c@{}}Skate\\ Board\end{tabular} & Table \\ \hline
Samples & & & 2690 & 76 & 55 & 898 & 3758 & 69 & 787 & 392 & 1547 & 451 & 202 & 184 & 283 & 66 & 152 & 5271 \\ \hline
PointNet \cite{qi2017pointnet} & No & 83.7 & 83.4 & 78.7 & 82.5 & 74.9 & 89.6 & 73.0 & 91.5 & 85.9 & 80.8 & 95.3 & 65.2 & 93.0 & 81.2 & 57.9 & 72.8 & 80.6 \\
PointNet++ \cite{qi2017pointnet++} & No & 85.1 & 82.4 & 79.0 & 87.7 & 77.3 & 90.8 & 71.8 & 91.0 & 85.9 & 83.7 & 95.3 & 71.6 & 94.1 & 81.3 & 58.7 & 76.4 & 82.6 \\
KD-Net \cite{klokov2017escape} & No & 82.3 & 80.1 & 74.6 & 74.3 & 70.3 & 88.6 & 73.5 & 90.2 & 87.2 & 81.0 & 94.9 & 57.4 & 86.7 & 78.1 & 51.8 & 69.9 & 80.3 \\
PCNN \cite{atzmon2018point} & No & 85.1 & 82.4 & 80.1 & 85.5 & 79.5 & 90.8 & 73.2 & 91.3 & 86.0 & 85.0 & 95.7 & 73.2 & 94.8 & 83.3 & 51.0 & 75.0 & 81.8 \\
PointCNN \cite{li2018pointcnn} & No & 86.1 & 84.1 & 86.5 & 86.0 & 80.8 & 90.6 & 79.7 & 92.3 & 88.4 & 85.3 & 96.1 & 77.2 & 95.3 & 84.2 & 64.2 & 80.0 & 83.0 \\
DGCNN \cite{wang2019dynamic} & No & 85.2 & 84.0 & 83.4 & 86.7 & 77.8 & 90.6 & 74.7 & 91.2 & 87.5 & 82.8 & 95.7 & 66.3 & 94.9 & 81.1 & 63.5 & 74.5 & 82.6 \\
RS-CNN \cite{liu2019relation} & No & 86.2 & 83.5 & 84.8 & 88.8 & 79.6 & 91.2 & 81.1 & 91.6 & 88.4 & 86.0 & 96.0 & 73.7 & 94.1 & 83.4 & 60.5 & 77.7 & 83.6 \\ \hline
LGAN \cite{achlioptas2018learning} & Yes & 57.0 & 54.1 & 48.7 & 62.6 & 43.2 & 68.4 & 58.3 & 74.3 & 68.4 & 53.4 & 82.6 & 18.6 & 75.1 & 54.7 & 37.2 & 46.7 & 66.4 \\
MAP-VAE \cite{han2019multi} & Yes & 68.0 & 62.7 & 67.1 & 73.0 & 58.5 & 77.1 & 67.3 & 84.8 & 77.1 & 60.9 & 90.8 & 35.8 & 87.7 & 64.2 & 45.0 & 60.4 & 74.8 \\ \hline
GraphTER & Yes & \textbf{81.9} & \textbf{81.7} & \textbf{68.1} & \textbf{83.7} & \textbf{74.6} & \textbf{88.1} & \textbf{68.9} & \textbf{90.6} & \textbf{86.6} & \textbf{80.0} & \textbf{95.6} & \textbf{56.3} & \textbf{90.0} & \textbf{80.8} & \textbf{55.2} & \textbf{70.7} & \textbf{79.1} \\ \hline
\end{tabular}
\vspace{-0.2in}
\end{table*}

\subsection{Point Cloud Segmentation}

We also apply the GraphTER model to 3D point cloud part segmentation on ShapeNet part dataset \cite{yi2016scalable}.

\vspace{-0.2in}
\subsubsection{Implementation Details}

We also use SGD optimizer to train the auto-encoding transformation network. 
The hyper-parameters are the same as in 3D point cloud classification except that we train for $256$ epochs. 
We adopt the negative log likelihood loss to train the node-wise classifier for segmenting each point in the clouds.

The auto-encoding architecture is similar to that of the classification task, where we employ five EdgeConv layers as the encoder.
However, the first two EdgeConv blocks consist of two MLP layers with the number of neurons \{64, 64\} in each layer.
We use shortcut connections to concatenate features from the first four layers to  a $512$-dimensional node-wise feature vector.

As for the node-wise classifier, we deploy the same architecture as in \cite{wang2019dynamic}. The output features from the encoder are concatenated node-wise with globally max-pooled features, followed by four fully-connected layers to classify each node. 
During the training procedure, the weights of the first four EdgeConv blocks in the encoder are kept frozen.

\vspace{-0.2in}
\subsubsection{Experimental Results}

We adopt the Intersection-over-Union (IoU) metric to evaluate the performance.
We follow the same evaluation protocol as in the PointNet \cite{qi2017pointnet}: the IoU of a shape is computed by averaging the IoUs of different parts occurring in that shape, and the IoU of a category is obtained by averaging the IoUs of all the shapes belonging to that category.
The mean IoU (mIoU) is finally calculated by averaging the IoUs of all the test shapes.

We also compare the proposed model with unsupervised approaches and supervised approaches in this task, as listed in Tab.~\ref{tab:segmentation}. 
We achieve a mIoU of $81.9\%$, which significantly outperforms the state-of-the-art unsupervised method MAP-VAE \cite{han2019multi} by $13.9\%$.

Moreover, the unsupervised GraphTER model also achieves the comparable performance to the state-of-the-art fully supervised approaches, greatly pushing closer towards the upper bound set by the fully supervised counterparts.

\vspace{-0.2in}
\subsubsection{Visualization Results}

Fig.~\ref{fig:sup_seg_results} visualizes the results of the proposed unsupervised model and two state-of-the-art fully supervised methods: DGCNN \cite{wang2019dynamic} and RS-CNN \cite{liu2019relation}.
The proposed model produces better segmentation on the ``table" model in the first row, and achieves comparable results on the other models.
Further, we qualitatively compare the proposed method with the state-of-the-art unsupervised method MAP-VAE \cite{han2019multi}, as illustrate in Fig.~\ref{fig:unsup_seg_results}. 
The proposed model leads to more accurate segmentation results than MAP-VAE, {\it e.g.}, the engines of planes and the legs of chairs.

\begin{figure}[t]
    \centering
    \subfigure[Ground-truth]{
    \includegraphics[width=0.22\columnwidth]{seg_results_gt.pdf}
    }
 	\subfigure[DGCNN]{
 	\includegraphics[width=0.22\columnwidth]{seg_results_dgcnn.pdf}
 	}
 	\subfigure[RS-CNN]{
 	\includegraphics[width=0.22\columnwidth]{seg_results_rscnn.pdf}
 	}
 	\subfigure[GraphTER]{
 	\includegraphics[width=0.22\columnwidth]{seg_results_gter.pdf}
 	}
    \caption{\textbf{Visual comparison of point cloud part segmentation with supervised methods. } 
    Our unsupervised GraphTER learning achieves comparable results with the state-of-the art fully supervised approaches.
    }
    \label{fig:sup_seg_results}
    \vspace{-0.1in}
\end{figure}

\begin{figure}[t]
    \centering
 	\subfigure[MAP-VAE]{
 	\includegraphics[width=0.95\columnwidth]{seg_results_unsup_map_vae.pdf}
 	}
 	\subfigure[GraphTER]{
 	\includegraphics[width=0.95\columnwidth]{seg_results_unsup_gter.pdf}
 	}
    \caption{\textbf{Visual comparison of point cloud part segmentation with the state-of-the-art unsupervised method MAP-VAE. } 
    We achieve more accurate segmentation even in tiny parts and transition regions.
    }
    \label{fig:unsup_seg_results}
    \vspace{-0.1in}
\end{figure}

\vspace{-0.1in}
\subsubsection{Ablation Studies}

\begin{table}[t]
\centering
\small
\caption{Unsupervised segmentation results on ShapeNet part dataset with different transformation strategies. Metric is mIoU (\%) on points.}
\label{tab:seg_ablation}
\begin{tabular}{c|cc|cc|c}
\hline
\multirow{2}{*}{} & \multicolumn{2}{c}{Global Sampling} & \multicolumn{2}{c|}{Local Sampling} & \multirow{2}{*}{Mean} \\ \cline{2-5}
 & Iso. & Aniso. & Iso. & Aniso. & \\ \hline
Translation & 79.83 & 79.88 & 80.05 & 79.85 & 79.90 \\
Rotation & 80.20 & \textbf{80.29} & 80.87 & 80.02 & 80.35 \\
Shearing & \textbf{81.88} & 80.28 & \textbf{81.89} & \textbf{80.48} & \textbf{81.13} \\ \hline
\multirow{2}{*}{Mean} & \textbf{80.64} & 80.15 & \textbf{80.94} & 80.12 & \multirow{2}{*}{\textbf{}} \\ \cline{2-5}
 & \multicolumn{2}{c|}{80.39} & \multicolumn{2}{c|}{\textbf{80.53}} & \\ \hline
\end{tabular}
\vspace{-0.2in}
\end{table}

Similar to the classification task, we analyze the effectiveness of different node-wise transformations under global or local sampling, as presented in Tab.~\ref{tab:seg_ablation}.
The proposed model achieves the best performance under the shearing transformation, improving by 1.23\% on average over translation, and 0.78\% over rotation, which demonstrates the benefits of GraphTER learning under complex transformations.

Further, the proposed model achieves a mIoU of 80.53\% on average under local sampling, which outperforms global sampling by 0.14\%.
This is because local sampling of nodes captures the local structure of graphs better, which is crucial in node-level 3D point cloud segmentation task.


\section{Introduction}
\vspace{-0.05in}
\label{sec:intro}
\input{01_introduction.tex}

\vspace{-0.1in}
\section{Related Works}
\vspace{-0.05in}
\label{sec:related_works}
\input{02_related_works.tex}

\vspace{-0.1in}
\section{Graph Transformations}
\label{sec:graphT}
\input{03_graph.tex}

\vspace{-0.1in}
\section{GraphTER: The Proposed Approach}
\label{sec:method}
\input{04_method.tex}

\vspace{-0.1in}
\section{Experiments}
\vspace{-0.05in}
\label{sec:experiments}
\input{05_experiments.tex}

\section{Conclusion}
\vspace{-0.05in}
\label{sec:conclusion}
\input{06_conclusion.tex}

\clearpage

{\small
\bibliographystyle{ieee}
