
\subsection{Graph neural networks}
Graph neural networks (GNNs) attempt to learn embeddings (i.e, vector representations) of nodes and/or graphs, 
utilizing the mechanisms of neural networks adapted to the topology of graphs. 
The core idea of GNNs is to allow messages to pass between neighbors so that 
the 
representation of each node can incorporate the information 
from its neighborhood and thus to enable the GNNs to indirectly learn the graph 
structures. Numerous novel architectures for GNNs have been proposed and 
tested, 
which differ by the information-passing mechanisms. Among the most recent 
architectures are graph convolutions~\cite{kipf2016semi},  attention 
mechanisms~\cite{velickovic2018graph}, and those inspired by convolutional 
neural networks~\cite{gao2019graph,niepert2016learning,defferrard2016convolutional}. The final 
embeddings obtained from GNNs can be utilized 
for various graph mining tasks, such as node 
classification~\cite{kipf2016semi}, link 
prediction~\cite{schlichtkrull2018modeling}, and graph 
classification~\cite{zhang2018end,dai2016discriminative}.

\subsection{Graph classification by GNN}
In graph classification, GNNs are tasked with predicting the label of an unseen 
graph. While node embeddings can be updated within a graph, the elusive step 
here is how to combine them into a vector representation of the entire graph 
that can distinguish among different labels. Two of the most common approaches 
are global pooling~\cite{duvenaud2015convolutional} and hierarchical 
pooling~\cite{zhitao2018hierarchical,yao2019graph,lee2019self}. The simplest 
ways for 
global pooling are global mean and global max of the final node embeddings. In 
contrast, hierarchical pooling iteratively reduces the number of nodes either by merging 
similar nodes into supernodes~\cite{zhitao2018hierarchical,yao2019graph} or 
selecting most significant nodes~\cite{lee2019self} until reaching a final 
supernode whose embedding is used to represent the whole 
graph. 

\subsection{Transfer learning for graphs}
While most existing methods attempt to train GNNs as an end-to-end 
classification system, some studies considered transfer learning in which the GNN 
is trained on a large dataset before being applied to the task of interest, often in 
a much smaller dataset. \cite{hlugzlplstrategies} succeeded in 
improving 3 (out of 4 attempted) existing GNNs by transfer learning from other 
tasks. Rather than training a GNN to classify a dataset right away, the authors 
pre-trained that GNN on another massive dataset (up to 456K 
graphs);
then they added a classifier and trained the whole architecture on the graph 
classification task. However, transfer learning for graph remains a major 
challenge, as \cite{ching2018opportunities,wang2019data} pointed out that 
considerable domain knowledge is required to design the appropriate 
pre-training procedure.


\subsection{Metric learning}
Metric learning aims to approximate a real-valued distance between two objects, and the most common objectives are contrastive loss and triplet loss. 
Some work has focused on metric learning on 
graphs~\cite{ktena2018metric,liu2019community,ling2020hierarchical}. Some of 
them~\cite{ktena2018metric,liu2019community}
employ a Siamese network structure, in which a twin network sharing the same 
weights is applied on a pair of graphs, and the two output vectors acting as 
representation of the two graphs are passed through a distance measure.

In computer vision,~\cite{schroff2015facenet} learns metric on triplet 
of images, where two (anchor and positive) share the same label and  
one (negative) has a different label. The model aims to
minimize the distance between the anchor and the positive, while 
maximizing the distance between the anchor and the negative. This inspired our 
interest in learning graph metrics with a triplet loss. 

 

\subsubsection{Problem definition}
We tackle the task of graph classification. Given 
$\mathcal{D}=\{(G_1,y_1),(G_2,y_2),...\}$ where $y_i \in \mathcal{Y}$ is the 
class label of the graph $G_i \in \mathcal{G}$, the goal of graph 
classification is to learn a mapping $f : \mathcal{G} \to \mathcal{Y}$ that 
maps graphs to the set of class labels and predicts the class labels of unknown 
graphs. 

\subsubsection{Outline of our method}
Our method combines the advantages of both GNN and metric learning.
Specifically, to facilitate a better accuracy of the classifier, our method 
first maps input graphs into vectors in the 
Euclidean space such that their corresponding vectors are well-separated 
based on classes. Below, we first briefly introduce GNNs and a learning 
scheme on triplet loss. 
We then describe the two stages of our method: pre-training a GNN and 
training a classifier.  


\subsection{Graph neural networks}
Various GNNs have been proposed and proven effective in 
approximating such a function $f$. Starting from a graph $G=(V,E)$ with node 
features $X_G = \{x_v | v \in V \}$, GNNs obtain final embeddings 
of nodes $Z_G = \{z_v | v \in V \}$ and a final embedding $h_G$ of the 
graph after $K$ layers of aggregation. Specifically, at each $(k+1)$-th layer, 
the embedding $h_v^{(k+1)}$ of each node $v$ incorporates the embeddings of itself and its neighboring nodes $N(v)$ at the $k$-th layer as follows:
\begin{equation*}
	h_v^{(k+1)} = MERGE\Big(h_v^{(k)}, AGGR\Big(\{h_u^{(k)} | u \in 
	N(v)\}\Big) \Big)
\end{equation*}
The embedding $h_G$ of the graph $G$ is then obtained by pooling all node 
embeddings into a single vector as follows:
\begin{equation*}
	h_G = POOL\Big( \{h_v^{(i)} | v \in V; i=1,..,K\}\Big)
\end{equation*}
GNNs differ by how the incorporating function $MERGE$, the 
aggregating function $AGGR$, and the final pooling function $POOL$ are 
implemented.

\begin{figure}[t]
	\centering
	\vspace{-2.5mm}
	\includegraphics[width=0.96\linewidth]{FIG/stage1.pdf} \\
	\vspace{-1.5mm}
	\caption{\label{fig:stage1}
		First training stage for a GNN. $\hat{f}(.)$ is trained to differentiate graphs of different classes via the triplet loss.
	}
\end{figure}

\begin{figure}[t]
	\centering
	\vspace{-4mm}
	\includegraphics[width=0.85\linewidth]{FIG/stage2.pdf} \\
	\vspace{-2mm}
	\caption{\label{fig:stage2}
		Second training stage for a classifier. After $\hat{f}(.)$ maps $g_i$ 
		to $\hat{f}(g_i)$, a classifier is added to map $\hat{f}(g_i)$ to the 
		class probability prediction. At this step, either the classifier is 
		trained independently (\textsc{2STG}\xspace) or the whole architecture is 
		trained together (\textsc{2STG+}\xspace).
	}
\end{figure}

\subsection{Metric learning based on triplet loss}
Triplet loss was first introduced in ~\cite{schroff2015facenet}. The core idea 
is to enforce a 
margin between classes of samples. This results in embeddings of the same 
class mapped to a cluster distant apart from that of other classes. 
Specifically, given a mapping $\bar{f}$, we wish for a graph $g_a$ (anchor) 
to be closer to another graph 
$g_p$ (positive) of the same class than to a graph $g_n$ (negative) of another 
class by at least a margin $\alpha$, which is a hyperparameter, i.e.,
$$\|\bar{f}(g_a)-\bar{f}(g_p)\|_2^2 + 
\alpha < 
\|\bar{f}(g_a)-\bar{f}(g_n)\|_2^2.$$

The triplet loss for the whole dataset becomes:
\begin{equation*}
\sum_{(a,p,n)}\max\left(\|\bar{f}(g_a)-\bar{f}(g_p)\|_2^2 - 
\|\bar{f}(g_a)-\bar{f}(g_n)\|_2^2 + 
\alpha, 0\right)
\end{equation*}
with the summation over all considered triplets.

Our two-stage method combines the power of both GNNs and the metric 
learning method, as described below.
\subsection{First training stage (pre-training a GNN)}
\label{subsec:firststage}
In the first training stage (depicted in Fig.~\ref{fig:stage1}), given a GNN architecture 
$\hat{f}(.)$, its weights are shared 
among a triplet network $T$, which consists of three identical GNN architectures having the same weights as $\hat{f}(.)$. The parameters of $T$ are trained on each triplet 
of graphs $(g_a,g_p,g_n)$ (anchor, positive, negative), in which the anchor and 
the positive graphs are of the same class while the negative graph is of 
another class. $T$ maps a triplet of graphs to a triplet of real-valued vectors in the Euclidean space: $T(g_a, g_p, g_n) = 
(\hat{f}(g_a), \hat{f}(g_p), \hat{f}(g_n))$. Ideally, $\hat{f}(g_a)$ and 
$\hat{f}(g_p)$ should be close while $\hat{f}(g_n)$ is far from them 
both. The triplet loss for $(g_a,g_p,g_n)$ is defined as: 
\begin{equation*}
	\max\left(\|\hat{f}(g_a)-\hat{f}(g_p)\|_2^2 - 
	\|\hat{f}(g_a)-\hat{f}(g_n)\|_2^2 + 
	\alpha,0\right)
\end{equation*}


\subsection{Second training stage (training a classifier)}
\label{subsec:secondstage}
In the second stage, a classifier is either trained 
independently, or added on top of the trained GNN and trained together on the 
graph classification task (see Fig.~\ref{fig:stage2}).

In summary, we propose two training methods for GNNs: \textsc{2STG}\xspace and 
\textsc{2STG+}\xspace, both consist of two stages.
\begin{itemize}
	\item \textbf{\textsc{2STG}\xspace} (Pre-training Setting): In the first stage, the 
	GNN maps each triplet of graphs to a triplet of 
	Euclidean-space vectors, and the GNN is trained on triplet loss. In the 
	second stage, a classifier is trained independently to classify the graph 
	embeddings.
	\item \textbf{\textsc{2STG+}\xspace} (Fine-tuning setting): It has the same structure as \textsc{2STG}\xspace 
	except that in the second stage, the classifier is plugged on top of 
	the trained GNN, and then the whole architecture is trained together in an end-to-end 
	manner.
\end{itemize}

Note that our methods are compatible to any GNN model that maps each 
graph to a representation vector. As shown in the next section, when applied to 
this method, each GNN model outperformed itself in the original setting.


\subsection{GNN architectures}

In order to demonstrate that our two-stage method helps realize better 
accuracy of GNNs, for each of the following GNN model, we compare the accuracy obtained in 
the original setting versus that from our method:
\begin{itemize}
	\item \textsc{GraphSage}~\cite{hamiltoninductive}: Global 
	pooling is used to pool node embeddings into one graph embedding.
	\item \textsc{GAT}~\cite{velickovic2018graph}: Global pooling is also applied on the node embeddings.
	\item \textsc{DiffPool}~\cite{zhitao2018hierarchical}: A 
	hierarchical approach for pooling the node embeddings. 
	\item \textsc{EigenGCN}~\cite{yao2019graph}: A different design for hierarchical 
	pooling.
	\item \textsc{SAGPool}~\cite{lee2019self}: A hierarchical graph pooling with 
	self-attention mechanisms.
\end{itemize} 
In previous studies, these models were trained end-to-end, mapping each graph 
to a prediction of class probabilities.
To further illustrate the competency of our method, we also compare it with a 
transfer-learning method \cite{hlugzlplstrategies}. 

\input{tab_graph_statistics}
\subsection{Datasets}

To validate the claims, we apply our methods on 12 
datasets. Some statistics of the datasets are summarized in 
Table.~\ref{tab:graph_stats}.
\subsubsection{Benchmark datasets}
They include some commonly tested binary-class datasets 
~\cite{morris2020tudataset} for graph classification: \textsc{DD}, \textsc{MUTAG}, 
\textsc{MUTAGENICITY}, \textsc{PTC-FM}, \textsc{PROTEINS}, and \textsc{IMDB-B}.
\subsubsection{New York Taxi datasets}
In addition, we also test our 
method on NYC Taxi 
datasets.\footnote{https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page}. We extracted the taxi ridership data in 2019 from New York City (NYC) Taxi 
Commission. The areas in New York are represented as 
nodes, and each taxi trip is an edge connecting the source and destination 
nodes. All taxi trips in an 1-hour interval form a graph, and each dataset 
spans 
a month of taxi operations. We augmented the binary label for each graph 
as taxi trips in weekdays (Mon-Thu) vs. weekend (Fri-Sun). We considered two 
taxi 
operators (Yellow and Green) and processed data in January, February and March 
of 2019, making 6 datasets in total: \textsc{Jan. G.}, \textsc{Feb. G.}, \textsc{Mar. G.}, \textsc{Jan. Y.}, \textsc{Feb. Y.}, and \textsc{Mar. Y.}.
 
\subsection{Experimental procedure}
We test the ability of each GNN architecture to classify graphs in the 
following three
settings:
\begin{itemize}
	\item Original setting: The GNN with a final classifier outputs the 
	estimated class 
	probabilities, and the weights are updated by the cross-entropy loss 
	with respect to the ground truth. We use the implementation 
	provided by the authors. To enhance the capacity of the final classifier, 
	we tune it by using up to three fully-connected layers and 
	select the model based on validation sets.
	\item \textsc{2STG}\xspace and \textsc{2STG+}\xspace: See Section~\ref{sec:method}.











\end{itemize}

We also compare our two-stage method with the transfer-learning 
method in~\cite{hlugzlplstrategies}, which also claims the effectiveness of a 
pre-training strategy. Out of the 5 GNN models investigated in our work, 
\textsc{GraphSage} and \textsc{GAT} are provided with trained weights by 
\cite{hlugzlplstrategies}, and they are compared with \textsc{GraphSage}/\textsc{GAT} trained in 
\textsc{2STG+}\xspace.

Each dataset is randomly split into three sets: train (80\%), validation 
(10\%) and test (10\%).
Details about hyperparameter search are in Appendix~\ref{appendix:hyperparameter}.
The reported results are mean and standard deviation 
of test accuracy of five splits.

We initialize node features as learnable features that are 
optimized with GNN parameters during training. 
While input features are provided in some datasets, we empirically find that using learnable features often leads to better accuracy.

In \textsc{2STG}\xspace and \textsc{2STG+}\xspace, each graph can be anchor once, while the positive and negative graphs are chosen 
randomly. The classifier is a multi-layer perceptron (MLP).


\subsection{Results and discussion}
 
\subsubsection{Improvement by our methods}
We draw some observations from the results of comparing \textsc{2STG}\xspace and \textsc{2STG+}\xspace with the original 
setting (Tables~\ref{tab:triplet_ppi} 
and~\ref{tab:triplet_taxi}):
\begin{itemize}
	\item Pre-training using triplet loss (i.e., the first stage of \textsc{2STG}\xspace and \textsc{2STG+}\xspace)
	consistently enhances the graph classification accuracy
	of each GNN model by $0.9-5.4\%$ 
	points, compared to its original setting.
	\item Fine-tuning the weights of GNNs (i.e, the second stage of \textsc{2STG+}\xspace) further improves the 
	accuracy from \textsc{2STG}\xspace in some cases by up to 1.3\% points.
\end{itemize}

\input{tab_triplet_ppi}
\input{tab_triplet_taxi}
\input{tab_triplet_pretrain}
\input{tab_triplet_pretrain2}

The improvement in accuracy by \textsc{2STG}\xspace and \textsc{2STG+}\xspace suggests two 
possible explanations:
\begin{itemize}
	\item The end-to-end training methods fail to realize the full potential 
	of the GNN models. Even if the final classifier of is 
	upgraded from a fully-connected layer to an MLP, the accuracy is not as high 
	as in \textsc{2STG}\xspace and \textsc{2STG+}\xspace.
	\item Learning meaningful embeddings in between that are fairly separated 
	based on classes (see Figure~\ref{fig:dd}), for example through metric 
	learning as in our methods,  	
	 facilitates a better accuracy of the final classifier.
\end{itemize}

\begin{figure}[t]
	\addtolength{\tabcolsep}{-3pt}
	\begin{center}
		\vspace{-2mm}



				\includegraphics[width=1.04in]{FIG/dd_original.pdf} 
				\includegraphics[width=1.08in]{FIG/dd_triplet.pdf}
				\includegraphics[width=1.08in]{FIG/dd_finetune.pdf}



		\caption{\label{fig:dd}
			Visualization of the final embeddings in Original (left), 
			\textsc{2STG}\xspace (middle) and \textsc{2STG+}\xspace (right) settings (\textsc{DD} 
			dataset). 
			Instances of the two classes are separated better in \textsc{2STG}\xspace 
			and \textsc{2STG+}\xspace
			than in the 
			original setting.
		}	
	\end{center}
\end{figure}

\subsubsection{Comparison with a transfer learning method}
We compare the pre-trained models of \textsc{GraphSage}/\textsc{GAT}
in~\cite{hlugzlplstrategies} with \textsc{GraphSage}/\textsc{GAT} of the same architecture (5 
layers, 300 dimensional hidden units and global mean pooling) trained in 
\textsc{2STG+}\xspace.
The pre-trained models are fine-tuned on the datasets.
The mean and standard deviation of test accuracy of 5 splits are reported in Tables~\ref{tab:triplet_pretrain} and~\ref{tab:triplet_pretrain2}.
Despite being pre-trained on a much smaller dataset, \textsc{2STG+}\xspace achieves better accuracy in $83\%$ of the considered cases: up to $2\%$ 
points in  the benchmark 
datasets and up to $3\%$ points in the NYC Taxi 
datasets. This validates our claims in Table~\ref{tab:compare}.


\subsubsection{Running time}
For each hyperparameter setting in a dataset, the original setting takes up to 
half an hour to train a model.  Due to having two stages, \textsc{2STG}\xspace and 
\textsc{2STG+}\xspace take up to an hour for both stages. 
In~\cite{hlugzlplstrategies}, the transfer-learning method was reported to 
take up to one day to pre-train on a rich dataset.


\subsection{Further analysis}
We study the final embeddings, generated by three training methods: original, \textsc{2STG}\xspace, \textsc{2STG+}\xspace. In Fig.~\ref{fig:dd}, despite having 2 dimensions, the embeddings of the original setting can be reduced to 1 dimension. We suspect that given the potential capacity, specifically the dimension of the final embeddings, \textsc{2STG}\xspace and \textsc{2STG+}\xspace utilize such expressive power better than the original setting by resulting in higher intrinsic dimension, weaker correlation between dimensions, and larger distance between embeddings~\cite{chen2020measuring}. While measuring the distance did not provide clear evidence, the results of the other two measurements validate our hypothesis. 

\subsubsection{Intrinsic dimension}
We measure the \textit{intrinsic dimension}, which we define as the dimension needed to retain 99$\%$ of the variance in the final embeddings. In the final embeddings of dimension $d$ of the validation set, we apply Principal Component Analysis (PCA) and measure the cumulative explained variance $V(i)$ achieved by setting the final dimension as $i$ for $i=1,2,..,d$. Assume that $V(j) \leq 0.99 \leq V(j+1)$, we linearly interpolate between $j$ and $(j+1)$ to obtain the dimension with $99\%$ explained variance. Such dimensions are reported in Table.~\ref{tab:eff_dim}. Given $64$ dimensions as the capacity, \textsc{2STG}\xspace and \textsc{2STG+}\xspace retain a higher intrinsic dimension, implying that they utilize this capacity better than the original setting.
\input{tab_eff_dim}
\input{tab_pair_corr}




\begin{figure*}[htbp!]
	\vspace{-3mm}
	\begin{subfigure}[b]{0.196\textwidth}
		\includegraphics[width=1.35in]{FIG/Features/Pairwise/green1_sage_5_std.pdf}
		\caption{\textsc{GraphSage}}
	\end{subfigure}
	\begin{subfigure}[b]{0.196\textwidth}
		\includegraphics[width=1.35in]{FIG/Features/Pairwise/green1_gat_5_std.pdf}
		\caption{\textsc{GAT}}
	\end{subfigure}
	\begin{subfigure}[b]{0.196\textwidth}
	\includegraphics[width=1.35in]{FIG/Features/Pairwise/green1_diffpool_5_std.pdf}
	\caption{\textsc{DiffPool}}
	\end{subfigure}
	\begin{subfigure}[b]{0.196\textwidth}
	\includegraphics[width=1.35in]{FIG/Features/Pairwise/green1_eigen_5_std.pdf}
	\caption{\textsc{EigenGCN}}
	\end{subfigure}
	\begin{subfigure}[b]{0.196\textwidth}
	\includegraphics[width=1.35in]{FIG/Features/Pairwise/green1_sag_5_std.pdf}
	\caption{\textsc{SAGPool}}
	\end{subfigure}
	\caption{\label{fig:green1}
		Average absolute correlation coefficients over epochs on the Jan. G. dataset. Means and standard deviations of 15 runs are plotted. Embedding dimensions quickly become strongly correlated in the orginal setting. Such correlation is much weaker in \textsc{2STG}\xspace and \textsc{2STG+}\xspace.
	}
\end{figure*}

\subsubsection{Correlation between final embedding dimensions}
We measure the average absolute correlation coefficients between final embedding dimensions. Specifically, given final embeddings of dimension five, the 
average of absolute values of ${5 \choose 2}$ pairwise correlation coefficients is 
calculated. As seeen in Table.~\ref{tab:pair_corr}, in most of the cases, the original setting leads to stronger 
correlation than \textsc{2STG}\xspace and \textsc{2STG+}\xspace, and several obtained dimensions
are too strongly correlated, making them redundant. This implies that 
\textsc{2STG}\xspace and \textsc{2STG+}\xspace utilize the provided capacity (i.e., dimension of final embeddings) better than the original setting by giving fewer redundant dimensions.
As seen in Fig.~\ref{fig:green1}, the average absolute correlation coefficients in the original setting quickly become close to 1. In \textsc{2STG}\xspace and \textsc{2STG+}\xspace, such correlation is much weaker.






\subsubsection*{Source code}
All source code used in the paper can be found at: \href{https://github.com/manhtuando97/two-stage-gnn}{https://github.com/manhtuando97/two-stage-gnn.}
\section{ Supplementary information}




\section{Datasets}
\label{appendix:datasets}


We tested our training method using 12 datasets.
Some statistics of the datasets are summarized in 
Table.~\ref{tab:graph_stats}

\subsection{Benchmark datasets}
These are the commonly tested binary-class datasets 
~\cite{morris2020tudataset} for the 
graph classification task: \textsc{DD}, \textsc{MUTAG}, 
\textsc{MUTAGENICITY}, \textsc{PTC-FM}, \textsc{PROTEINS}, and \textsc{IMDB-B}.



\subsection{New York City Taxi datasets}
We extracted the taxi ridership data in 2019 from New York City (NYC) Taxi 
Commission. The areas in New York are represented as 
nodes, and each taxi trip is an edge connecting the source and destination 
nodes. All taxi trips in an 1-hour interval form a graph, and each dataset 
spans 
a month of taxi operations. We augmented the binary label for each graph 
as taxi trips in weekdays (Mon-Thu) vs. weekend (Fri-Sun). We considered two 
taxi 
operators (Yellow and Green) and processed data in January, February and March 
of 2019, making 6 datasets in total: \textsc{Jan. G.}, \textsc{Feb. G.}, \textsc{Mar. G.}, \textsc{Jan. Y.}, \textsc{Feb. Y.}, and \textsc{Mar. Y.}.

\section{GNN architectures}
\label{appendix:gnn}

In order to demonstrate that our two-stage training method helps realize a 
better 
performance of GNNs, for each GNN architecture, we compared the accuracy 
obtained in 
the original setting versus that from our method. The GNN 
architectures we considered in this work are:
\begin{itemize}
	\item \textsc{GraphSage}~\cite{hamiltoninductive}: This is often used as a 
	strong baseline in 
	graph classification. After obtaining node embeddings, global mean/max 
	pooling is applied to combine all node embeddings into one graph embedding.
	\item \textsc{GAT}~\cite{velickovic2018graph}: Instead of uniformly passing 
	neighbor information into 
	a node embedding, \cite{velickovic2018graph} employs an attention 
	mechanism for the 
	importance of each neighboring node.
	\item \textsc{DiffPool}~\cite{zhitao2018hierarchical}: While using the same 
	aggregation mechanism as \cite{hamiltoninductive}, 
	\cite{zhitao2018hierarchical} proposes a 
	hierarchical approach to pool the node embeddings. 
	Rather than a ``flat-pooling" step at the end, diff-pool repeatedly merges 
	nodes into ``supernodes" until there is only one supernode whose embedding is 
	treated as the graph embedding.
	\item \textsc{EigenGCN}~\cite{yao2019graph}: Attempting to implement hierarchical 
	pooling like \cite{zhitao2018hierarchical}, \cite{yao2019graph} 
	formulates a different way to combine nodes and their respective embeddings 
	making use of the eigenvectors of the Laplacian matrix.
	\item \textsc{SAGPool}~\cite{lee2019self}: Hierarchical graph pooling employing 
	self-attention mechanisms.
\end{itemize} 


\section{Hyperparameter search}
\label{appendix:hyperparameter}
For each GNN, the hyperparameters regarding the network 
architecture were tuned in the 
same search space for the three settings: original, \textsc{2STG}\xspace, 
\textsc{2STG+}\xspace. The search space for the dimensions of the input vector, hidden 
vector and output vector for all GNNs was $\{16, 32, 64, 96, 128\}$. For 
\textsc{DiffPool}, we used three 
layers of graph convolution and one \textsc{DiffPool} layer as described in the original 
paper. For \textsc{EigenGCN}, we used three pooling operators as it was shown to 
achieve 
the best performance in the original paper. For \textsc{SAGPool}, we used  three 
pooling 
layers as explained in the original paper. Other hyperparameters that are 
exclusive to each GNN architecture were set to the
default values provided in each paper's original code of each architecture's 
authors. 


In all three settings, the architecture of the final classifier was also tuned. 
The number of fully-connected layers was up to 3 while the search space for 
the hidden dimension was $\{2^h | 1 \leq h \leq \log_2(d)\}$, where $d$ is the dimension of the output vector.

The two settings \textsc{2STG}\xspace and \textsc{2STG+}\xspace require an additional 
hyperparameter $\alpha$ as the margin in the triplet loss. 
While~\cite{schroff2015facenet} found $\alpha=0.2$ to 
be effective, we empirically found that this value was too small to separate 
instances of different classes. Instead, the search space for $\alpha$ we used 
was $\{0.5, 1.0, 1.5, 2.0, 2.5\}$.

\section{Computing specifications \& dependencies}
All experiments were performed on Ubuntu 18.04 LTS running on a machine with four RTX2080Ti GPUs, each of which has $11$GB memory.

The following libraries were used to run the code:
\begin{itemize}
	\item torch 1.7.0,
	\item networkx 2.5,
	\item sklearn 0.23.2,
	\item numpy 1.16.4,
	\item torch-geometric 1.6.3.
\end{itemize}

\section{Introduction}
\label{sec:intro}
\input{010introduction}

\section{Related Works}
\label{sec:background}
\input{020background}

\section{Proposed Method}
\label{sec:method}
\input{030method}

\section{Experiments}
\label{sec:experiments}
\input{040experiments}

\section{Conclusion}
\label{sec:conclusion}
\input{050conclusion}


\bibliographystyle{named}











