\section{Datasets Details}
{\bf ogbn-products.} As shown in Table \ref{table:ogb}, \emph{ogb-products} is an undirected and unweighted graph, representing an Amazon product co-purchasing network. The goal of this task is to predict the category of a product in a multi-class classification setup, where the 47 top-level categories are used for target labels. To match the real-world application, it conducts a splitting on the dataset based on sales ranking, where the top 10\% for training, next top 2\% for validation, and the rest for testing.


{\bf ogbn-proteins.} As shown in Table \ref{table:ogb}, \emph{ogbn-proteins} dataset is an undirected, weighted, and typed (according to species) graph. Nodes represent proteins, and edges indicate different types of biologically meaningful associations between proteins, e.g., physical interactions, co-expression or homology. The task is to predict the presence of protein functions in a multi-label binary classification setup, where there are 112 kinds of labels to predict in total. The performance is measured by the average of ROC-AUC scores across the 112 tasks. It conducts the splitting by species.

{\bf ogbn-arxiv.} As shown in Table \ref{table:ogb}, \emph{ogbn-arxiv} dataset is a directed graph, representing the citation network between all Computer Science (CS) arXiv papers indexed by MAG \citep{wang2020microsoft}. The task is to predict the 40 subject areas of arXiv CS papers, e.g., cs.AI, cs.LG, and cs.OS, which are manually determined by the paper’s authors and arXiv moderators. This dataset were splitted by time.
\label{appendix:dataset}

\section{ hyper-parameters tuned on UniMP model}
There are the hyper-parameters we tuned on our unified model for comparison with other SOTA results, where the asterisks denote the hyper-parameters we eventually selected.

\begin{table}[htbp]
\caption{The tuned hyperparamerters of our model}
\begin{tabular}{cccc}
\hline
                 & \textbf{ogbn-prdouct} & \textbf{ogbn-proteins}   & \textbf{ogbn-arxiv}                                                                          \\ \hline
sampling\_method & NeighborSampling      & Random Partition         & Full-batch                                                                                   \\ \hline
num\_layers      & {[}3*, 4{]}           & {[}3, 5, 7*, 9{]}        & {[}3*, 4{]}                                                                                  \\ \hline
hidden\_size     & {[}128*, 256{]}       & {[}32, 64*, 128{]}       & {[}128*, 256{]}                                                                              \\ \hline
num\_heads       & {[}4*,2{]}            & {[}6, 4*, 2{]}           & {[}2*, 1{]}                                                                                  \\ \hline
dropout          & {[}0.3*{]}            & {[}0, 0.1*, 0.3{]}       & {[}0.1, 0.3*{]}                                                                              \\ \hline
lr               & {[}0.01, 0.001*{]}    & {[}0.01, 0.001*{]}       & {[}0.1, 0.001*{]}                                                                            \\ \hline
weight\_decay    & -                     & -                        & {[}0, 0.0005*{]}                                                                             \\ \hline
label\_rate      & {[}0.625*{]}          & {[}0.375, 0.5*, 0.625{]} & \begin{tabular}[c]{@{}c@{}}{[}0.125, 0.25, 0.375, 0.5,\\ 0.625*, 0.75, 0.875{]}\end{tabular} \\ \hline
\end{tabular}
\end{table}
\label{appendix:hyp_sota}
\end{appendices}

\section{Experiments}

We propose a Unified Message Passing Model (UniMP) for semi-supervised node classification, which incorporates the feature and label propagation jointly by a Graph Transformer and employs a masked label prediction strategy to optimize it. We conduct the experiments on the Node Property Prediction of Open Graph Benchmark (OGBN), which includes several various challenging and large-scale datasets for semi-supervised classification, split in the procedure that closely matches the real-world application \cite{hu2020open}. To verify our models effectiveness, we compare our model with others state-of-the-art (SOTA) models in \emph{ogbn-products}, \emph{ogbn-proteins} and \emph{ogbn-arxiv} three OGBN datasets. We also provide more experiments and comprehensive ablation studies to show our motivation more intuitively, and how LPA improves our model to achieve better results.


\subsection{Datasets and Experimental Settings}



\begin{table}[htbp]
	\setlength{\abovecaptionskip}{-0cm}
	\begin{center}
		\setlength{\tabcolsep}{1.2mm}{
		\resizebox{\columnwidth}{!}{%
			\begin{tabular}{l|ccccc}
			\hline
				{\bf Name}  & {\bf Node} &  {\bf Edges}  &  {\bf Tasks}    &  {\bf Task Type} &  {\bf Metric}	\\
				\hline 
				ogbn-products  &2,449,029&61,859,140 & 1 &Multi-class class &Accuracy \\
				ogbn-proteins   &132,534&39,561,252&112  &Binary class  &ROC-AUC\\
				ogbn-arxiv     &169,343&1,166,243&1 &Multi-class class  &Accuracy \\
				\hline
		\end{tabular}}}
	\end{center}
	\caption{Dataset statistics of OGB node property prediction}
	\label{table:ogb}
	\vspace{-4mm}
\end{table}

\paragraph{Datasets.} Most of the frequently-used graph datasets are extremely small compared to graphs found in real applications. And the performance of GNNs on these datasets is often unstable due to several issues including
their small-scale nature, non-negligible duplication or leakage rates, unrealistic data splits \cite{hu2020open}. Consequently, we conduct our experiments on the recently released datasets of Open Graph Benchmark (OGB) \cite{hu2020open}, which overcome the main drawbacks of commonly used datasets and thus
are much more realistic and challenging. OGB datasets cover a variety of real-world applications and span several important domains ranging from social and information networks to biological networks, molecular graphs, and knowledge graphs. They also span a variety of prediction tasks at the level of nodes, graphs, and links/edges. As shown in table \ref{table:ogb}, in this work, we performed our experiments on the three OGBN datasets with different sizes and tasks for getting credible result, including \emph{ogbn-products} about 47 products categories classification with given 100-dimensional nodes features, \emph{ogbn-proteins} about 112 kinds of proteins function prediction with given 8-dimensional edges features and \emph{ogbn-arxiv} about 40-class topics classification with given 128 dimension nodes features. More details about these datasets are provided in appendix A in the supplementary file.


\begin{table}[htbp]
	\setlength{\abovecaptionskip}{-0cm}
	
	\begin{center}
	    \resizebox{\columnwidth}{!}{%
		\begin{tabular}{cccc}
		\hline
			& {\bf ogbn-products} &  {\bf ogbn-proteins	}  &  {\bf ogbn-arxiv} \\
			\hline
			sampling\_method &NeighborSampling & Random Partition & Full-batch \\
			num\_layers &  3 & 7 & 3\\ 
			hidden\_size & 128 & 64 & 128\\ 
			num\_heads & 4 & 4 & 2\\ 
			dropout  & 0.3 & 0.1 & 0.3\\ 
			lr & 0.001 & 0.001 & 0.001\\ 
			weight\_decay& * & * & 0.0005\\ 
			label\_rate& 0.625 & 0.5 & 0.625\\ 
			\hline
		\end{tabular}
		}
	\end{center}
	\caption{The hyper-paramerter setting of our model}
	\label{table:params}
	\vspace{-4mm}
\end{table}

\paragraph{Implementation details.}  As mentioned above, these datasets are different from each other in sizes or tasks. So we evaluate our model on them with different sampling methods following previous studies~\cite{li2020deepergcn}, getting credible comparison results. In \emph{ogbn-products} dataset, we use NeighborSampling with size =10 for each layer to sample the subgraph during training and use full-batch for inference. In \emph{ogbn-proteins} dataset, we use Random Partition to split the dense graph into subgraph to train and test our model. As for small-size \emph{ogbn-arxiv} dataset, we just apply full batch for both training and test. We set the hyper-parameter of our model for each dataset in Table \ref{table:params}, and the label\_rate means the percentage of labels we preserve during applying masked label prediction strategy. We use Adam optimizer with lr = 0.001 to train our model. Specially, we set weight decay to 0.0005 for our model in small-size \emph{ogbn-arxiv} dataset to prevent overfitting. More details about the tuned hyper-parameters are provided in appendix B in the supplementary file.
 
 
 
\subsection{Comparison with SOTA Models}
Baseline and other comparative SOTA models are provided by OGB leaderboard. And all these results are guaranteed to be reproducible with open source codes. Following the requirement of OGB, we run our experimental results for each dataset 10 times and report the mean and standard deviation. As shown in Table \ref{table:ret_products}, Table \ref{table:ret_proteins}, and Table \ref{table:ret_arxiv}, our unified model outperform all other comparative models in three OGBN datasets.
Since most of the compared models only consider optimizing their models for the features propagation, these results demonstrate that incorporating label propagation into GNN models can bring significant improvements.
Specifically, we gain 82.56\% ACC in \emph{ogbn-products}, 86.42\% ROC-AUC in \emph{ogbn-proteins}, which achieves about 0.6-1.6\%  absolute improvements compared to the newly SOTA methods like DeeperGCN \cite{li2020deepergcn}. In \emph{ogbn-arxiv}, our method gains 73.11\% ACC, achieve 0.37\% absolute improvements compared to GCNII \cite{chen2020simple}, whose parameters are four times larger than ours. 

\begin{table}[htbp]
	\setlength{\abovecaptionskip}{0.cm}
	\setlength{\belowcaptionskip}{-.2cm}
	\begin{center}
	    \resizebox{\columnwidth}{!}{%
		\begin{tabular}{l|cccc}
		    \hline
			{\bf Model}  & {\bf Test Accuracy	} &  {\bf Validation Accuracy	}  &  {\bf Params} \\
			\hline 
			GCN-Cluster \cite{chiang2019cluster} & 0.7897 $\pm$ 0.0036 & 0.9212 $\pm$ 0.0009 & 206,895 \\
			GAT-Cluster & 0.7923 $\pm$ 0.0078 & 0.8985 $\pm$ 0.0022& 1,540,848 \\ 
			GAT-NeighborSampling & 0.7945 $\pm$ 0.0059 & - & 1,751,574 \\
			GraphSAINT \cite{zeng2019graphsaint} & 0.8027 $\pm$ 0.0026 & - & 331,661 \\
			DeeperGCN  \cite{li2020deepergcn} & 0.8090 $\pm$ 0.0020 & 0.9238 $\pm$ 0.0009 & 253,743  \\
			\hline 
			{\bf UniMP} &  \bf{0.8256} $\pm$ \bf{0.0031} & \bf{ 0.9308} $\pm$ \bf{0.0017} & 1,475,605 \\
			\hline
		\end{tabular}}
	\end{center}
	\caption{Results for ogbn-products}
	\label{table:ret_products}
	\vspace{-4mm}
\end{table}

\begin{table}[htbp]
	\setlength{\abovecaptionskip}{0.cm}
	\setlength{\belowcaptionskip}{-.2cm}
	\begin{center}
     	\resizebox{\columnwidth}{!}{%
		\begin{tabular}{l|cccc}
		    \hline 
			{\bf Model}  & {\bf Test ROC-AUC} &  {\bf Validation ROC-AUC	}  &  {\bf Params} \\
			\hline 
			GaAN \cite{zhang2018gaan} & 0.7803 $\pm$ 0.0073 & - & - \\
			GeniePath-BS \cite{liu2020bandit} & 0.7825 $\pm$ 0.0035& - & 316,754 \\ 
			MWE-DGCN& 0.8436 $\pm$ 0.0065 & 0.8973$\pm$ 0.0057&538,544 \\
			DeepGCN \cite{li2019deepgcns}& 0.8496 $\pm$ 0.0028 & 0.8921 $\pm$ 0.0011 & 2,374,456 \\
			DeeperGCN \cite{li2020deepergcn}  & 0.8580 $\pm$ 0.0017 & 0.9106 $\pm$ 0.0016 & 2,374,568  \\
			\hline 
			{\bf UniMP} & \bf{0.8642} $\pm$\bf{0.0008} & \bf{0.9175} $\pm$ \bf{0.0007} &1,909,104\\
			\hline 
		\end{tabular}}
	\end{center}
	\caption{Results for ogbn-proteins}
	\label{table:ret_proteins}
	\vspace{-4mm}
\end{table}

\begin{table}[htbp]
	\setlength{\abovecaptionskip}{0.cm}
	\setlength{\belowcaptionskip}{-.2cm}
	\begin{center}
	    \resizebox{\columnwidth}{!}{%
		\begin{tabular}{l|cccc}
		    \hline 
			{\bf Model}  & {\bf Test Accuracy	} & {\bf Validation Accuracy}  & {\bf Param} \\
			\hline 
			DeeperGCN \cite{li2020deepergcn} & 0.7192 $\pm$ 0.0016 & 0.7262 $\pm$ 0.0014 &  1,471,506 \\ 
			GaAN \cite{zhang2018gaan} & 0.7197 $\pm$ 0.0024 & - &  1,471,506 \\ 
			DAGNN \cite{liu2020towards} & 0.7209 $\pm$ 0.0025 & -  & 1,751,574 \\
			JKNet \cite{xu2018representation} & 0.7219 $\pm$ 0.0021 & 0.7335 $\pm$ 0.0007 &  331,661 \\
			GCNII \cite{chen2020simple}  & 0.7274 $\pm$ 0.0016  & - & 2,148,648  \\
		
 			\hline 
			{\bf UniMP} & \bf{0.7311} $\pm$ \bf{0.0021} & \bf{0.7450} $\pm$ \bf{0.0005} &473,489 \\
			\hline 
		\end{tabular}}
	\end{center}
	\caption{Results for ogbn-arxiv}
	\label{table:ret_arxiv}
	\vspace{-4mm}
\end{table}

\begin{figure*}[htbp]
\setlength{\belowcaptionskip}{-.2cm}
	\centering
	\begin{minipage}[c]{0.03\textwidth}
	\subcaption{}
	\label{figure:fig1}
	\end{minipage}
	\begin{minipage}[c]{0.20\textwidth}
	    \includegraphics[width=\linewidth]{ogbn-arxiv-label-rate}
	\end{minipage}
    \begin{minipage}[c]{0.03\textwidth}
    \subcaption{}
	\label{figure:fig2}
	\end{minipage}
	\begin{minipage}[c]{0.20\textwidth}
		\includegraphics[width=\linewidth]{arxiv-curve-label-rate}
    \end{minipage}
    \begin{minipage}[c]{0.03\textwidth}
    \subcaption{}
	\label{figure:fig3}
	\end{minipage}
	\begin{minipage}[c]{0.20\textwidth}
		\includegraphics[width=\linewidth]{arxiv-test-label-rate}
	\end{minipage}
	\begin{minipage}[c]{0.03\textwidth}
    \subcaption{}
	\label{figure:fig4}
	\end{minipage}
	\begin{minipage}[c]{0.20\textwidth}
		\includegraphics[width=\linewidth]{ogbn-arxiv-edge-accuracy}
	\end{minipage}
	\caption{Exploration of how label coverage affects label propagation: (a) Training with different label\_rate; (b) Training with different proportion of labeled data; (c) Testing with different label\_rate; (d) Test accuracy with different neighbors. }
		\label{figure:fig_curves}
	
\end{figure*}

 
\begin{table*}[htbp]
	\centering
   
	\small
	\setlength{\tabcolsep}{5mm}{
	\begin{tabular}{c|c|c|c|c}
		\hline
		&        & \multicolumn{3}{c}{\textbf{Datasets}}                      \\ \cline{3-5} 
		\multirow{-2}{*}{\textbf{Inputs}}        & \multirow{-2}{*}{\textbf{Model}} & \multicolumn{1}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}ogbn-products   \\ Test ACC\end{tabular}}} & \multicolumn{1}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}ogbn-proteins    \\  Test ROC-AUC\end{tabular}}} & \multicolumn{1}{c}{\textbf{\begin{tabular}[c]{@{}c@{}}ogbn-arxiv \\ Test ACC\end{tabular}}} \\ \hline
		$\mathbf{X}$   & Multilayer Perceptron    &       0.6106 $\pm$ 0.0008                    &          0.7204 $\pm$ 0.0048    &               0.5765 $\pm$ 0.0012 \\ \hline
		& GCN    &    0.7851 $\pm$ 0.0011         &           0.8265 $\pm$ 0.0008            &   0.7218 $\pm$ 0.0014                  \\ 
		& GAT    &     0.8002 $\pm$ 0.0063                &    0.8376 $\pm$ 0.0007                   &     0.7246 $\pm$ 0.0013              \\ 
		\multirow{-3}{*}{$\mathbf{X,A}$}         & Graph Transformer                      &   0.8137 $\pm$ 0.0047                  &           0.8347  $\pm$  0.0014           &       0.7292 $\pm$ 0.0010             \\ \hline
		& GCN    &          0.7832 $\pm$ 0.0013           &   0.8083 $\pm$ 0.0021                   &                      0.7018  $\pm$ 0.0009        \\ 
		& GAT    &               0.7751 $\pm$ 0.0054      &  0.8247 $\pm$ 0.0033                    &       0.7055 $\pm$ 0.0012            \\
		\multirow{-3}{*}{$\mathbf{A,\hat{Y}}$}   & Graph Transformer &          0.7987 $\pm$ 0.0104           &                  0.8160 $\pm$ 0.0007    &       0.7090 $\pm$ 0.0007 \\ \hline
		& GCN    &            0.7987 $\pm$ 0.0104     &     0.8247 $\pm$ 0.0032             &   0.7264 $\pm$ 0.0003        \\
		& GAT    &      0.8193 $\pm$ 0.0017            &         0.8556  $\pm$ 0.0009              &               0.7278 $\pm$ 0.0009    \\
		& Graph Transformer  &       \bf{0.8256} $\pm$ \bf{0.0031}              &    0.8560 $\pm$ 0.0003                   &   \bf{0.7311} $\pm$ \bf{ 0.0021 }   \\
		\multirow{-4}{*}{$\mathbf{X,A,\hat{Y}}$}  & \text{\ \ \ \ \ \  \ \ \ \ }$\llcorner$ w/ Edge Feature                      & *  &    \bf{0.8642} $\pm$ \bf{0.0008}    &  * \\
		\hline
	\end{tabular}
	}

	\caption{This is the ablation studies on models with different inputs, where
$\mathbf{X}$ denotes the nodes features, $\mathbf{A}$ is the graph adjacent matrix and $\mathbf{\hat{Y}}$ is the observed labels. In \emph{ogbn-proteins}, nodes features are not provided initially. We average the edge features as their nodes features and provide the experimental result of Transformer without edge features for fair comparison in this experiment, which is slightly different from Table \ref{table:ret_proteins}.
}
 \label{table:ablation-stuidies}
 \vspace{-4mm}
\end{table*}
 
 \subsection{Ablation Studies}
 In this section, to better identify the improvements from different components of our proposed model, we conduct extensive studies with the following four aspects:
 

\begin{itemize}
 	\item Firstly, we apply the masked label prediction strategy on kinds of GNNS to show the effectiveness and robustness of incorporation LPA and GNN, shown in Table \ref{table:ablation-stuidies}.
 	\item In order to get a more practical and effective solution to apply masked label prediction strategy, we tune the label\_rate during training and inference to explore the relationship between label coverage and GNNs performance, shown in Figure \ref{figure:fig_curves}.
 	\item We also analyze how LPA affects the GNN to make it performs better, shown in Figure \ref{fig:attenion_image}.
 	\item Furthermore, in Table \ref{table:ablation in unimp_v1}, we provide more ablation studies on UniMP, compared with GAT, showing the superiority of our model. 
\end{itemize}
 
 
 \subsubsection{Graph Neural Networks with Different Inputs}
 In Table \ref{table:ablation-stuidies}, we apply masked label prediction on kinds of GNNs to improve their performance. Firstly, we re-implement classical GNN methods like GCN and GAT, following the same sampling methods and model setting shown in Table \ref{table:params}. The hidden size of GCN is head\_num*hidden\_size since it doesn't have head attention. Secondly, we change different inputs for these models to study the effectiveness of feature and label propagation, using our {\bf masked label prediction} to train the models with partial nodes label $\mathbf{\hat{Y}}$ as input.
  
 
Row 4 in Table \ref{table:ablation-stuidies} shows that only with $\mathbf{\hat{Y}}$ and  $\mathbf{A}$ as input, GNNs still work well in all three datasets, outperforming those MLP model only given $\mathbf{X}$. This implies that one's label relies heavily on its neighborhood instead of its feature. Comparing Row 3 and 5 in Table \ref{table:ablation-stuidies}, models with $\mathbf{X}$, $\mathbf{A}$ and $\mathbf{\hat{Y}}$ outperform the models with $\mathbf{X}$ and $\mathbf{A}$, which indicates that it's a waste of information for GNNs in semi-supervised classification when they making predictions without incorporating the ground truth train labels $\mathbf{\hat{Y}}$. Row 3-5 in Table \ref{table:ablation-stuidies} also show that our Graph Transformer can outperform GAT, GCN with different input settings.

\subsubsection{Relation between Label Coverage and Performance}

 Although we have verified the effectiveness of using this strategy to combine LPA and GNN, the relation between label coverage and its impact on GNNs performance remains uncertain. Therefore, shown in Figure \ref{figure:fig_curves}, we conduct more experiments in \emph{ogbn-arxiv} to investigate their relationship in the following different scenarios:
\begin{itemize}
	\item In Figure \ref{figure:fig1}, we train UniMP using $\mathbf{X, \hat{Y}, A}$ as inputs. We tune the input label\_rate which is the hyper-parameter of masked label prediction task and display the validation and test accuracy. Our model achieves better performance when label\_rate is about 0.625.
	\item Figure \ref{figure:fig2} describes the correlation between the proportion of training data and the effectiveness of label propagation. We fix the input label\_rate with 0.625. The only change is the training data proportion. It's common sense that with the increased amount of training data, the performance is gradually improving. And the model with label propagation ${\mathbf{{\hat{Y}}}}$ can gain greater benefits from increasing labeled data proportion.
	\item Our unified model always masks a part of the training input label and tries to recover them. But in the inference stage, our model utilizes all training labels for predictions, which is slightly inconsistent with the one in training. In Figure \ref{figure:fig3}, we fix our input label\_rate with 0.625 during training and perform different input label\_rate in inference. the training stage, It's found that UniMP might have worse performance (less than 0.70) than the baseline (about 0.72) when lowering the label\_rate during prediction. However, when the label\_rate climbs up, the performance can boost up to 0.73.
	
	\item In Figure \ref{figure:fig4}, we calculate the accuracy for unlabeled nodes grouped by the number of neighbors. The experimental result shows that nodes with more neighbors have higher accuracy. And the model with label propagation ${\mathbf{\hat{Y}}}$ can always have improvements even with different numbers of training neighbors.
\end{itemize}


\subsubsection{Measuring the Connection between Nodes}


In Figure \ref{fig:attenion_image}, we analyze how LPA affects GNN to make it perform better. Wang~\shortcite{wang2019unifying} has pointed out that using LPA for GCN during training can enable nodes within the same class/label to connect more strongly, increasing the accuracy (ACC) of model's prediction. Our model can be regarded as an upgraded version of them, using LPA in both training and testing time for our Graph Transformer. Therefore, we try to experimentally verify the above idea based on our model.

\begin{equation}
\resizebox{.80\linewidth}{!}{$
\begin{aligned}
MSF =\dfrac{1}{N}\sum_{i=1}^{N} \log \bigg ( 1+ \sum_{j\in \mathcal{N}(i)_{pos}} \sum_{k\in \mathcal{N}(i)_{neg}}e^{\alpha_{i,j}}-e^{\alpha_{i,k}} \bigg)\\
\end{aligned}
\label{eq:11}$}
\end{equation}

We use the Margin Similarity Function (MSF) as shown in Equation \ref{eq:11} to reflect the connection tightness between nodes within the same class (the higher scores, the stronger connection they have. We conduct the experiment on \emph{ogbn-arxiv}. And as shown in Figure \ref{fig:attenion_image}, the ACC of models' prediction is proportional to Margin Similarity. Unifying feature and label propagation can further strengthen their connection, improving their ACC. Moreover, our Graph Transformer outperforms GAT in both connection tightness and ACC with different inputs.

\begin{figure}[htpb]
\centering
	\begin{subfigure}[b]{.48\columnwidth}
		\includegraphics[width=\linewidth,trim= 0 0.2cm 0 0.2cm,clip]{attention_accuracy_arxiv}
		\label{figure:attention_accuracy}
	\end{subfigure}
	\begin{subfigure}[b]{.48\columnwidth}
		\includegraphics[width=\linewidth,trim= 0 0.2cm 0 0.2cm,clip]{attention_margin_arxiv}
		\label{figure:attention_margin}
	\end{subfigure}
	\setlength{\belowcaptionskip}{-.4cm}
	\caption{Correlation between accuracy and margin similarity between neighbors.}
	\label{fig:attenion_image}
\end{figure}


\subsubsection{More Ablation Studies on UniMP}

Finally, we provide more ablation studies on our UniMP model, compared with GAT, from the following 4 aspects: 
(1) vanilla transformer with dot-product attention or GAT with sum attention; 
(2) simple residual or gated residual;
(3) with train labels as inputs;
(4) with train and validation labels as inputs.
As shown in Table \ref{table:ablation in unimp_v1}, we can find that dot-product attention can outperform sum attention, since dot-product provides more interactions between nodes. Besides, residual and gated residual can also strengthen the GNNs with shallow layers. Moreover, our unified model can take the additional validation labels as input to further boost model's performance without more training steps. Therefore, when we apply the model to the real scene, and the labeled data are accumulated progressively, the accuracy of the unlabeled data can keep increasing without training our model from scratch, while other GNNs without explicit label modeling can't fully utilize the benefits of additional labels. 


\begin{table}[htbp]
\resizebox{\columnwidth}{!}{
\begin{tabular}{ccc}
\hline
 Model                                                                                                               & \textbf{ogbn-prdouct}                                                     & \textbf{ogbn-arxiv}                                                       \\ \hline
\begin{tabular}[l]{@{}l@{}}GAT (sum attention)\\ $\llcorner$ w/ residual \\ $\llcorner$ w/ gated residual\end{tabular}                                          & \begin{tabular}[c]{@{}c@{}} 0.8002 \\ 0.8033\\ 0.8050\end{tabular}                   & \begin{tabular}[c]{@{}c@{}} 0.7246 \\ 0.7265\\ 0.7272\end{tabular}                   \\ \hline
\begin{tabular}[l]{@{}l@{}}Transformer (dot-product)\\ $\llcorner$ w/ residual \\ $\llcorner$ w/ gated residual\\ ~~~~$\llcorner$ w/ train label (UniMP) \\  ~~~~~~~~$\llcorner$ w/ validation labels\end{tabular} & \begin{tabular}[c]{@{}c@{}} 0.8091\\ 0.8125\\ 0.8137\\ 0.8256\\ \bf{0.8312} \end{tabular} & \begin{tabular}[c]{@{}c@{}} 0.7259 \\ 0.7271 \\ 0.7292\\ 0.7311\\ \bf{0.7377}\end{tabular} \\ \hline
\end{tabular}}
\caption{Ablation studies in UniMP, compared with GAT}
	\label{table:ablation in unimp_v1}
	\vspace{-4mm}
\end{table}


\section{Introduction}
	There are various scenarios in the world, e.g., recommending related news, discovering new drugs, or predicting social relations, which can be described as graph structures. And many methods have been proposed to optimize these graph-based problems and achieved significant success in many related domains such as predicting nodes' properties ~\cite{yang2016revisiting,kipf2016semi}, relation linking ~\cite{grover2016node2vec,battaglia2018relational}, and graph classification ~\cite{duvenaud2015convolutional,niepert2016learning}.
	
	In the task of semi-supervised node classification, we are required to learn with labeled examples and then make predictions for those unlabeled ones. To better classify the nodes' labels in the graph, based on the Laplacian smoothing assumption~\cite{li2018deeper,xu2018representation}, the message passing models were proposed to aggregate the information from its connected neighbors in the graph, acquiring
	enough facts to produce a more robust prediction for unlabeled nodes. Generally, there are two main kinds of methods to implement message passing model, Graph Neural Networks (GNNs) ~\cite{kipf2016semi,hamilton2017inductive,xu2018representation,liao2019lanczosnet,xu2018powerful} and Label Propagation Algorithms (LPAs) ~\cite{zhu2003semi,zhang2007hyperparameter,wang2007label,karasuyama2013manifold,gong2016label,liu2019learning}. GNNs combine graph structures by propagating and aggregating node features through several neural layers, getting predictions from \emph{feature propagation}. While LPAs make predictions for unlabeled instances by \emph{label propagation} iteratively.


	
	Since GNN and LPA are based on the same assumption, making semi-supervised classifications by information propagation, there is an intuition that incorporating them together for boosting performance. Some superior studies have proposed their graph models based on it. For example, APPNP ~\cite{klicpera2019predict} and TPN~\cite{liu2019learning} using GNN predict soft labels and then propagate them, and GCN-LPA~\cite{wang2019unifying} uses LPA to regularize their GNN model. However, as shown in Table \ref{table:comparision}, aforementioned methods
	still can not directly incorporate GNN and LPA within a message passing model, \emph{propagating} \emph{feature} and \emph{label} in both training and inference procedure.
	\begin{table}[tbp]
		\setlength{\abovecaptionskip}{0.cm}
		\setlength{\belowcaptionskip}{-.2cm}
		\begin{center}
		
			\resizebox{0.91\columnwidth}{!}{%
				\begin{tabular}{cccccc}
					\hline
					\multicolumn{1}{c}{ }  &\multicolumn{2}{c}{ Training} &\multicolumn{2}{c}{ Inference} \\
					\multicolumn{1}{c}{\bf Model}  &\multicolumn{1}{c}{\bf Feature} &\multicolumn{1}{c}{\bf Label} &\multicolumn{1}{c}{\bf Feature} &\multicolumn{1}{c}{\bf Label}	\\
					\hline 
					LPA         & &\makecell[c]{\checkmark} & &\makecell[c]{\checkmark}   \\
					GCN             &\makecell[c]{\checkmark}  &&\makecell[c]{\checkmark}  & \\
					APPNP     &\makecell[c]{\checkmark}    &   &\makecell[c]{\checkmark}    & \\
					GCN-LPA      &\makecell[c]{\checkmark}    & \makecell[c]{\checkmark}    &\makecell[c]{\checkmark}    & \\
					\bf UniMP (Ours)     &\makecell[c]{\checkmark}    & \makecell[c]{\checkmark}    &\makecell[c]{\checkmark}    &\makecell[c]{\checkmark}  \\
					\hline
				\end{tabular}
			}
		\end{center}
		
		\caption{Comparison the input information that message passing models use in training and inference.}
		\vspace{-0.32cm}
		\label{table:comparision}
	\end{table}


	

	
	In this work, we propose a {\bf Uni}fied {\bf M}essage {\bf P}assing model (UniMP) to address the aforementioned issue with two simple but effective ideas: (a) combing node features propagation with labels and (b) masked label prediction. Previous GNN-based methods only take node features as input with the partial observed node labels for supervised training. And they discard the observed labels during inference. UniMP utilizes both node features and labels in both training and inference stages. It uses the embedding technique to transform the partial node labels from one-hot to dense vector likes node features. And a multi-layer Graph Transformer network takes them as input to perform attentive information propagation between nodes. Therefore, each node can aggregate both features and labels information from its neighbors. Since we have taken the node label as input, using it for supervised training will cause the label leakage problem. The model will overfit in the self-loop input label while performing poor in inference. To address this issue, we propose a masked label prediction strategy, which randomly masks some training instances' label and then predicts them to overcome label leakage. This simple and effective training method is drawn the lesson from masked word prediction in BERT~\cite{devlin2018bert}, and simulates the procedure of transducing labels information from labeled to unlabeled examples in the graph.
	
	We evaluate our UniMP model on three semi-supervised classification datasets in the Open Graph Benchmark (OGB), where our new methods achieve the new state-of-the-art results in all tasks, gaining 82.56\% ACC in \emph{ogbn-products}, 86.42\% ROC-AUC in \emph{ogbn-proteins} and 73.11\% ACC in \emph{ogbn-arxiv}. We also conduct ablation studies for our UniMP model, to evaluate the effectiveness of our unified method. Besides, we make the most thorough analysis of how the label propagation boosts our model's performance.
	
	\section{Preliminaries}
	In this section, we briefly review the related work and along the way, introduce our notation. We denote a graph as $G = (V,E)$, where $V$ denotes the nodes in the graph with $|V| = n$ and $E$ denotes edges. The nodes are described by the feature matrix $X \in \mathbb{R} ^{n \times m}$, which usually are dense vectors with $m$ dimension, and the target class matrix $Y \in \mathbb{R} ^{n \times c}$, with the number of classes $c$. The adjacency matrix $A = [a_{i,j}] \in \mathbb{R}^{n \times n}$ is used to describe graph $G$, and the diagonal degree matrix is denoted by $D = $ diag$(d_1,d_2,...,d_n)$ , where $d_i = \sum_{j} a_{ij}$ is the degree of node $i$. A normalized adjacency matrix is defined as $D^{-1}A$ or $D^{- \frac{1}{2}}AD^{- \frac{1}{2}}$, and we adopt the first definition in this paper.
	
	\paragraph{Graph Neural Networks.} In semi-supervised node classification, GCN \cite{kipf2016semi} is one of the most classical models based on the Laplacian smoothing assumption. GCN transforms and propagates node features $X$ across the graph by several layers, including linear layers and nonlinear activation to build the approximation
	of the mapping: $X \rightarrow Y$. The feature propagation scheme of GCN in layer $l$ is:
	\begin{equation}
	\begin{split}
	H^{(l+1)}&=\sigma(D^{-1}AH^{(l)}W^{(l)})\\
	Y&=f_{out}(H^{(L)})
	\end{split}
	\label{equ:1}
	\end{equation}
	where the $\sigma$ is an activation function, $W^{(l)}$ is the trainable weight in the $l$-th layer, and the $H^{(l)}$ is the $l$-th layer representations of nodes. $H^{(0)}$ is equal to node input features $X$. Finally, a $f_{out}$ output layer is applied on the final representation to make prediction for $Y$.
	
	\paragraph{Label propagation algorithms.} Traditional algorithms like Label Propagation Algorithm (LPA) only utilizes labels and relations between nodes to make prediction. LPA assumes the labels between connected nodes are similar and propagates the labels iteratively across the graph. Given an initial label matrix $\hat{Y}^{(0)} $, which consists of one-hot label indicator vectors $\hat{y}_i^{0}$ for the labeled nodes or zeros vectors for the unlabeled. A simple iteration equation of LPA is formulated as following:
	\begin{equation}
	\begin{split}
	\hat{Y}^{(l+1)}&=D^{-1}A\hat{Y}^{(l)}
	\end{split}
	\end{equation}
	Labels are propagated from each other nodes through a normalized adjacency matrix $D^{-1}A$. 

	
	\paragraph{Combining GNN and LPA.} Recently, there is a trend to combine GNN and LPA in semi-classification tasks in the community. APPNP~\cite{klicpera2019predict} and TPN~\cite{liu2019learning} propose to use GCN to predict soft labels and then propagate them with Personalized Pagerank. However, these works still only considered the partial node labels as the supervision training signal. GCN-LPA is most relevant to our work, as they also take the partial node labels as input. However, they combine the GNN and LPA in a more indirect way, only using the LPA in training to regularize the weight edges of their GAT model. While our UniMP directly combines GNN and LPA within a network, propagates the node features and labels 
in both training and predicting. Moreover, unlike GCN-LPA whose regularization strategy can only be used in those GNNs with trainable weight edge such as GAT~\cite{velivckovic2017graph}, GAAN~\cite{zhang2018gaan}, our training strategy can be easily extended in kinds of GNNs such as GCN and GAT to further improve their performance. We will describe our approach more specifically in the next section.
	
	\section{Unified Message Passing Model}
	\begin{figure}[tbp]
		\centering
		\includegraphics[width=\columnwidth,trim=1cm 2cm 2cm 0.2cm, clip]{unimp_architecture}
		\caption{
			The architecture of UniMP.
		}
		\vspace{-0.25cm}
		\label{figure:unimp_architecture}
	\end{figure}
	
	As shown in Figure \ref{figure:unimp_architecture}, given the node feature $X$ and partial observed labels $\hat{Y}$, we employ a Graph Transformer, jointly using label embedding to combine the aforementioned feature and label propagation together, constructing our UniMP model. Moreover, a masked label prediction strategy is introduced to train our model to prevent label leakage problem. 
	



	\subsection{Graph Transformer}
	
	Since Transformer \cite{vaswani2017attention,devlin2018bert} has been proved being powerful in NLP, we adopt its vanilla multi-head attention into graph learning with taking into account the case of edge features. Specifically, given node features $H^{(l)}=\{h^{(l)}_1,h^{(l)}_2,...,h^{(l)}_n \}$, we calculate multi-head attention for each edge from $j$ to $i$ as following:

	\begin{equation}
	\begin{split}
	q_{c,i}^{(l)} &=W_{c,q}^{(l)} h^{(l)}_{i}+b^{(l)}_{c,q} \\
	k_{c,j}^{(l)} &=W_{c,k}^{(l)} h^{(l)}_{j}+b^{(l)}_{c,k} \\
	e_{c,ij} &=W_{c,e} e_{ij}+b_{c,e} \\
	\alpha_{c,ij}^{(l)} &= \frac{ \langle q_{c,i}^{(l)} , k_{c,j}^{(l)} +e_{c, ij}  \rangle }{\sum_{u \in \mathcal{N}(i)} \langle q_{c,i}^{(l)} , k_{c,u}^{(l)} + e_{c, iu} \rangle }

	\end{split}
	\label{eq:3}
	\end{equation}

	where $\langle q,k \rangle =\exp(\frac{q^{T}k}{\sqrt{d}} )$ is exponential scale dot-product function and $d$ is the hidden size of each head.
	For the $c$-th head attention, we firstly transform the source feature $h^{(l)}_i$ and distant feature $h^{(l)}_j$ into query vector $q^{(l)}_{c,i} \in \mathbb{R}^{d}$and key vector $k^{(l)}_{c,j} \in \mathbb{R}^{d}$ respectively using different trainable parameters $W_{c,q}^{(l)} $, $W_{c,k}^{(l)} $, $b^{(l)}_{c,q}$, $b^{(l)}_{c,k}$. The provided edge features $e_{ij}$ will be encoded and added into key vector as additional information for each layer.


	
	After getting the graph multi-head attention, we make a message aggregation from the distant $j$ to the source $i$:
	\begin{equation}
	\begin{aligned}
	v_{c,j}^{(l)} &=W_{c,v}^{(l)} h^{(l)}_{j}+b^{(l)}_{c,v} \\
	\hat{h}_{i}^{(l+1)} &=  \Big\Vert_{c=1}^{C}  \big[ \sum_{j \in \mathcal{N}(i)} \alpha^{(l)}_{c,ij}(v^{(l)}_{c,j} + e_{c,ij}) \big] \\
	\end{aligned}
	\end{equation}
	where the $\parallel$ is the concatenation operation for $C$ head attention. Comparing with the Equation \ref{equ:1}, multi-head attention  matrix replaces the original normalized adjacency matrix as transition matrix for message passing. The distant feature $h_j$ is transformed to $v_{c,j} \in \mathbb{R}^{d}$ for weighted sum. 
	
	In addition, inspired by Li~\shortcite{li2019deepgcns} and Chen~\shortcite{chen2020simple}, we propose to use a gated residual connection between layers as shown in Equation \ref{eq:4} to prevent our model from over-smoothing.
	\vspace{-1mm}
	\begin{equation}
	\resizebox{.91\linewidth}{!}{$
		\begin{aligned}
		r_{i}^{(l)} &=W_{r}^{(l)} h^{(l)}_{i}+b^{(l)}_{r} \\
		\beta^{(l)}_{i} &= \text{sigmoid}(W_{g}^{(l)}[\hat{h}^{(l+1)}_{i}; r^{(l)}_i; \hat{h}^{(l+1)}_{i} -  r^{(l)}_i]) \\
		h_{i}^{(l+1)} &= \text{ReLU}(\text{LayerNorm}((1- \beta_{i}^{(l)} )\hat{h}_{i}^{(l+1)}+\beta_{i}^{(l)}  r_{i}^{(l)} )) \\
		\end{aligned}$}
	\label{eq:4}
	\end{equation}
	
	Specially, similar to GAT, if we apply the Graph Transformer on the last output layer, we will employ averaging for multi-head output and remove the non-linear transformation as following: 
	\vspace{-1mm}
	\begin{equation}
	\begin{split}
	\hat{h}_{i}^{(l+1)} &=  \frac{1}{C}\sum_{c=1}^{C}  \big[ \sum_{j \in \mathcal{N}(i)} \alpha^{(l)}_{c,ij}(v^{(l)}_{c,j} + e_{c,ij}^{(l)}) \big] \\
	h_{i}^{(l+1)} &= (1- \beta_{i}^{(l)} )\hat{h}_{i}^{(l+1)}+\beta_{i}^{(l)}  r_{i}^{(l)}\\
	\end{split}
	\end{equation}
	
	\subsection{Label Embedding and Propagation}
	We propose to embed the partially observed labels into the same space as node features: $ \hat{Y}\in\mathbb{R}^{n\times c} \rightarrow \hat{Y}_d \in \mathbb{R}^{n\times m}$, which consist of the label embedding vector for labeled nodes and zeros vectors for the unlabeled. And then, we combine the label propagation into Graph Transformer by simply adding the node features and labels vectors together as propagation information $(H^{0}=X+\hat{Y}_d) \in \mathbb{R}^{n \times m}$. We can prove that by mapping partially-labeled $\hat{Y}$ and node features $X$ into the same space and adding them up, our model is unifying both label propagation and feature propagation within a shared message passing framework. Let's take $\hat{Y}_d=\hat{Y}W_{d}$ and $A^{*}$ to be normalized adjacency matrix $D^{-1}A$ or the attention matrix from our Graph Transformer likes Equation \ref{eq:3}. Then we can find that:
	\vspace{-1mm}
	\begin{equation}
	\begin{split}
	H^{(0)} &= X + \hat{Y}W_{d} \\
	H^{(l+1)} &= \sigma(((1 - \beta) A^{*} + \beta I ) H^{(l)}W^{(l)})
	\end{split}
	\end{equation}
	where $\beta$ can be the gated function like Equation \ref{eq:4} or a pre-defined hyper-parameters like APPNP \cite{klicpera2019predict}. For simplification, we let $\sigma$ function as identity function, then we can get:
	\vspace{-1mm}
	\begin{equation}
	\resizebox{.91\linewidth}{!}{$
		\begin{aligned}
		H^{(l)} =& ((1 - \beta) A^{*} + \beta I )^{l} (X + \hat{Y}W_{d}) W^{(1)} W^{(2)}\dots W^{(l)} \\
		=& ((1 - \beta) A^{*} + \beta I )^{l}X W  + ((1 - \beta) A^{*} + \beta I )^{l}\hat{Y}W_{d} W\\
		\end{aligned}$}
	\end{equation}
	where $W=W^{(1)} W^{(2)}\dots W^{(l)}$. Then we can find that our model can be approximately decomposed into feature propagation $ ((1 - \beta) A^{*} + \beta I )^{l}X W $ and label propagation $ ((1 - \beta) A^{*} + \beta I )^{l}\hat{Y}W_{d} W$. 
	
	\subsection{Masked Label Prediction}
	
	Previous works on GNNs seldom consider using the partially observed labels $\hat{Y}$ in both training and inference stages. They only take those labels information as ground truth target to supervised train their model's parameters $\theta$ with given $X$ and $A$:
	\vspace{-1.5mm}
	\begin{equation} 
	\label{equ:ind_formulate}

	\argmax_{\theta} \quad \log p_{\theta}(\hat{Y}| X, A) = \sum_{i=1}^{\hat{V}} \log p_{\theta}(\hat{y}_i | X, A)\\

	\end{equation}
	where $\hat{V}$ represents the partial nodes with labels. However, our UniMP model propagates node features and labels to make prediction: $p(y | X, \hat{Y}, A)$. Simply using above objective for our model will make the label leakage in the training stage, causing poor performance in inference. Learning from BERT, which masks input words and makes predictions for them to pretrain their model (masked word prediction), we propose a masked label prediction strategy to train our model. During training, at each step, we corrupt the $\hat{Y}$ into $\tilde{Y}$ by randomly masking a portion of node labels to zeros and keep the others remain, which is controlled by a hyper-parameter called label\_rate. Let those masked labels be $\bar{Y}$, our objective function is to predict $\bar{Y}$ with given $X$, $\tilde{Y}$ and $A$:
	\vspace{-1.5mm}
	
	
	\begin{equation} 
	\label{equ:ind_formulate_v2}
	\argmax_{\theta} \text{\ } \log p_{\theta}(\bar{Y}| X,\tilde{Y}, A) = \sum_{i=1}^{\bar{V}} \log p_{\theta}(\bar{y}_i | X, \tilde{Y}, A)
	\end{equation}
	where $\bar{V}$ represents those nodes with masked labels. In this way, we can train our model without the leakage of self-loop labels information. And during inference, we will employ all $\hat{Y}$ as input labels to predict the remaining unlabeled nodes.





	






	\input{experiments}
	
	\section{Conclusion}
	We first propose a unified message passing model, UniMP, which jointly performs feature propagation and label propagation within a Graph Transformer to make the semi-supervised classification. Furthermore, we propose a masked label prediction method to supervised training our model, preventing it from overfitting in self-loop label information. Experimental results show that UniMP outperforms the previous state-of-the-art models on three main OGBN datasets: \emph{ogbn-products}, \emph{ogbn-proteins} and \emph{ogbn-arxiv} by a large margin, and ablation studies demonstrate the effectiveness of unifying feature propagation and label propagation.
	

	\bibliographystyle{named}
	
\section{Introduction}

The {\it IJCAI--21 Proceedings} will be printed from electronic
manuscripts submitted by the authors. These must be PDF ({\em Portable
Document Format}) files formatted for 8-1/2$''$ $\times$ 11$''$ paper.

\subsection{Length of Papers}

All paper {\em submissions} must have a maximum of six pages, plus at most one for references. The seventh page cannot contain {\bf anything} other than references.

The length rules may change for final camera-ready versions of accepted papers and will differ between tracks. Some tracks may include only references in the last page, whereas others allow for any content in all pages. Similarly, some tracks allow you to buy a few extra pages should you want to, whereas others don't.

If your paper is accepted, please carefully read the notifications you receive, and check the proceedings submission information website\footnote{\url{https://proceedings.ijcai.org/info}} to know how many pages you can finally use. That website holds the most up-to-date information regarding paper length limits at all times. Please notice that if your track allows for a special references-only page, the {\bf references-only page(s) cannot contain anything else than references} (i.e.: do not write your acknowledgments on that page or you will be charged for it).

\subsection{Word Processing Software}

As detailed below, IJCAI has prepared and made available a set of
\LaTeX{} macros and a Microsoft Word template for use in formatting
your paper. If you are using some other word processing software, please follow the format instructions given below and ensure that your final paper looks as much like this sample as possible.

\section{Style and Format}

\LaTeX{} and Word style files that implement these instructions
can be retrieved electronically. (See Appendix~\ref{stylefiles} for
instructions on how to obtain these files.)

\subsection{Layout}

Print manuscripts two columns to a page, in the manner in which these
instructions are printed. The exact dimensions for pages are:
\begin{itemize}
\item left and right margins: .75$''$
\item column width: 3.375$''$
\item gap between columns: .25$''$
\item top margin---first page: 1.375$''$
\item top margin---other pages: .75$''$
\item bottom margin: 1.25$''$
\item column height---first page: 6.625$''$
\item column height---other pages: 9$''$
\end{itemize}

All measurements assume an 8-1/2$''$ $\times$ 11$''$ page size. For
A4-size paper, use the given top and left margins, column width,
height, and gap, and modify the bottom and right margins as necessary.

\subsection{Format of Electronic Manuscript}

For the production of the electronic manuscript, you must use Adobe's
{\em Portable Document Format} (PDF). A PDF file can be generated, for
instance, on Unix systems using {\tt ps2pdf} or on Windows systems
using Adobe's Distiller. There is also a website with free software
and conversion services: \url{http://www.ps2pdf.com}. For reasons of
uniformity, use of Adobe's {\em Times Roman} font is strongly suggested.
In \LaTeX2e{} this is accomplished by writing
\begin{quote}
\mbox{\tt $\backslash$usepackage\{times\}}
\end{quote}
in the preamble.\footnote{You may want also to use the package {\tt
latexsym}, which defines all symbols known from the old \LaTeX{}
version.}

Additionally, it is of utmost importance to specify the {\bf
letter} format (corresponding to 8-1/2$''$ $\times$ 11$''$) when
formatting the paper. When working with {\tt dvips}, for instance, one
should specify {\tt -t letter}.

\subsection{Title and Author Information}

Center the title on the entire width of the page in a 14-point bold
font. The title must be capitalized using Title Case. Below it, center author name(s) in 12-point bold font. On the following line(s) place the affiliations, each affiliation on its own line using 12-point regular font. Matching between authors and affiliations can be done using numeric superindices. Optionally, a comma-separated list of email addresses follows the affiliation(s) line(s), using 12-point regular font.

\subsubsection{Blind Review}

In order to make blind reviewing possible, authors must omit their
names and affiliations when submitting the paper for review. In place
of names and affiliations, provide a list of content areas. When
referring to one's own work, use the third person rather than the
first person. For example, say, ``Previously,
Gottlob~\shortcite{gottlob:nonmon} has shown that\ldots'', rather
than, ``In our previous work~\cite{gottlob:nonmon}, we have shown
that\ldots'' Try to avoid including any information in the body of the
paper or references that would identify the authors or their
institutions. Such information can be added to the final camera-ready
version for publication.

\subsection{Abstract}

Place the abstract at the beginning of the first column 3$''$ from the
top of the page, unless that does not leave enough room for the title
and author information. Use a slightly smaller width than in the body
of the paper. Head the abstract with ``Abstract'' centered above the
body of the abstract in a 12-point bold font. The body of the abstract
should be in the same font as the body of the paper.

The abstract should be a concise, one-paragraph summary describing the
general thesis and conclusion of your paper. A reader should be able
to learn the purpose of the paper and the reason for its importance
from the abstract. The abstract should be no more than 200 words long.

\subsection{Text}

The main body of the text immediately follows the abstract. Use
10-point type in a clear, readable font with 1-point leading (10 on
11).

Indent when starting a new paragraph, except after major headings.

\subsection{Headings and Sections}

When necessary, headings should be used to separate major sections of
your paper. (These instructions use many headings to demonstrate their
appearance; your paper should have fewer headings.). All headings should be capitalized using Title Case.

\subsubsection{Section Headings}

Print section headings in 12-point bold type in the style shown in
these instructions. Leave a blank space of approximately 10 points
above and 4 points below section headings.  Number sections with
arabic numerals.

\subsubsection{Subsection Headings}

Print subsection headings in 11-point bold type. Leave a blank space
of approximately 8 points above and 3 points below subsection
headings. Number subsections with the section number and the
subsection number (in arabic numerals) separated by a
period.

\subsubsection{Subsubsection Headings}

Print subsubsection headings in 10-point bold type. Leave a blank
space of approximately 6 points above subsubsection headings. Do not
number subsubsections.

\paragraph{Titled paragraphs.} You should use titled paragraphs if and
only if the title covers exactly one paragraph. Such paragraphs should be
separated from the preceding content by at least 3pt, and no more than
6pt. The title should be in 10pt bold font and ended with a period.
After that, a 1em horizontal space should follow the title before
the paragraph's text.

In \LaTeX{} titled paragraphs should be typeset using
\begin{quote}
{\tt \textbackslash{}paragraph\{Title.\} text} .
\end{quote}

\subsubsection{Acknowledgements}

You may include an unnumbered acknowledgments section, including
acknowledgments of help from colleagues, financial support, and
permission to publish. If present, acknowledgements must be in a dedicated,
unnumbered section appearing after all regular sections but before any
appendices or references.

Use
\begin{quote}
    {\tt \textbackslash{}section*\{Acknowledgements\}})
\end{quote}
to typeset the acknowledgements section in \LaTeX{}.

\subsubsection{Appendices}

Any appendices directly follow the text and look like sections, except
that they are numbered with capital letters instead of arabic
numerals. See this document for an example.

\subsubsection{References}

The references section is headed ``References'', printed in the same
style as a section heading but without a number. A sample list of
references is given at the end of these instructions. Use a consistent
format for references. The reference list should not include publicly unavailable work.

\subsection{Citations}

Citations within the text should include the author's last name and
the year of publication, for example~\cite{gottlob:nonmon}.  Append
lowercase letters to the year in cases of ambiguity.  Treat multiple
authors as in the following examples:~\cite{abelson-et-al:scheme}
or~\cite{bgf:Lixto} (for more than two authors) and
\cite{brachman-schmolze:kl-one} (for two authors).  If the author
portion of a citation is obvious, omit it, e.g.,
Nebel~\shortcite{nebel:jair-2000}.  Collapse multiple citations as
follows:~\cite{gls:hypertrees,levesque:functional-foundations}.
\nocite{abelson-et-al:scheme}
\nocite{bgf:Lixto}
\nocite{brachman-schmolze:kl-one}
\nocite{gottlob:nonmon}
\nocite{gls:hypertrees}
\nocite{levesque:functional-foundations}
\nocite{levesque:belief}
\nocite{nebel:jair-2000}

\subsection{Footnotes}

Place footnotes at the bottom of the page in a 9-point font.  Refer to
them with superscript numbers.\footnote{This is how your footnotes
should appear.} Separate them from the text by a short
line.\footnote{Note the line separating these footnotes from the
text.} Avoid footnotes as much as possible; they interrupt the flow of
the text.

\section{Illustrations}

Place all illustrations (figures, drawings, tables, and photographs)
throughout the paper at the places where they are first discussed,
rather than at the end of the paper.

They should be floated to the top (preferred) or bottom of the page,
unless they are an integral part
of your narrative flow. When placed at the bottom or top of
a page, illustrations may run across both columns, but not when they
appear inline.

Illustrations must be rendered electronically or scanned and placed
directly in your document. They should be cropped outside latex, otherwise portions of the image could reappear during the post-processing of your paper. All illustrations should be understandable when printed in black and
white, albeit you can use colors to enhance them. Line weights should
be 1/2-point or thicker. Avoid screens and superimposing type on
patterns, as these effects may not reproduce well.

Number illustrations sequentially. Use references of the following
form: Figure 1, Table 2, etc. Place illustration numbers and captions
under illustrations. Leave a margin of 1/4-inch around the area
covered by the illustration and caption.  Use 9-point type for
captions, labels, and other text in illustrations. Captions should always appear below the illustration.

\section{Tables}

Tables are considered illustrations containing data. Therefore, they should also appear floated to the top (preferably) or bottom of the page, and with the captions below them.

\begin{table}
\centering
\begin{tabular}{lll}
\hline
Scenario  & $\delta$ & Runtime \\
\hline
Paris       & 0.1s  & 13.65ms     \\
Paris       & 0.2s  & 0.01ms      \\
New York    & 0.1s  & 92.50ms     \\
Singapore   & 0.1s  & 33.33ms     \\
Singapore   & 0.2s  & 23.01ms     \\
\hline
\end{tabular}
\caption{Latex default table}
\label{tab:plain}
\end{table}

\begin{table}
\centering
\begin{tabular}{lrr}
\toprule
Scenario  & $\delta$ (s) & Runtime (ms) \\
\midrule
Paris       & 0.1  & 13.65      \\
            & 0.2  & 0.01       \\
New York    & 0.1  & 92.50      \\
Singapore   & 0.1  & 33.33      \\
            & 0.2  & 23.01      \\
\bottomrule
\end{tabular}
\caption{Booktabs table}
\label{tab:booktabs}
\end{table}

If you are using \LaTeX, you should use the {\tt booktabs} package, because it produces better tables than the standard ones. Compare Tables \ref{tab:plain} and~\ref{tab:booktabs}. The latter is clearly more readable for three reasons:

\begin{enumerate}
    \item The styling is better thanks to using the {\tt booktabs} rulers instead of the default ones.
    \item Numeric columns are right-aligned, making it easier to compare the numbers. Make sure to also right-align the corresponding headers, and to use the same precision for all numbers.
    \item We avoid unnecessary repetition, both between lines (no need to repeat the scenario name in this case) as well as in the content (units can be shown in the column header).
\end{enumerate}

\section{Formulas}

IJCAI's two-column format makes it difficult to typeset long formulas. A usual temptation is to reduce the size of the formula by using the {\tt small} or {\tt tiny} sizes. This doesn't work correctly with the current \LaTeX{} versions, breaking the line spacing of the preceding paragraphs and title, as well as the equation number sizes. The following equation demonstrates the effects (notice that this entire paragraph looks badly formatted):
\begin{tiny}
\begin{equation}
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i
\end{equation}
\end{tiny}%

Reducing formula sizes this way is strictly forbidden. We {\bf strongly} recommend authors to split formulas in multiple lines when they don't fit in a single line. This is the easiest approach to typeset those formulas and provides the most readable output%
\begin{align}
    x =& \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \nonumber\\
    + & \prod_{i=1}^n \sum_{j=1}^n j_i
\end{align}%

If a line is just slightly longer than the column width, you may use the {\tt resizebox} environment on that equation. The result looks better and doesn't interfere with the paragraph's line spacing: %
\begin{equation}
\resizebox{.91\linewidth}{!}{$
    \displaystyle
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i
$}
\end{equation}%

This last solution may have to be adapted if you use different equation environments, but it can generally be made to work. Please notice that in any case:

\begin{itemize}
    \item Equation numbers must be in the same font and size than the main text (10pt).
    \item Your formula's main symbols should not be smaller than {\small small} text (9pt).
\end{itemize}

For instance, the formula
\begin{equation}
    \resizebox{.91\linewidth}{!}{$
    \displaystyle
    x = \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j + \prod_{i=1}^n \sum_{j=1}^n j_i + \prod_{i=1}^n \sum_{j=1}^n i_j
$}
\end{equation}
would not be acceptable because the text is too small.

\section{Examples, Definitions, Theorems and Similar}

Examples, definitions, theorems, corollaries and similar must be written in their own paragraph. The paragraph must be separated by at least 2pt and no more than 5pt from the preceding and succeeding paragraphs. They must begin with the kind of item written in 10pt bold font followed by their number (e.g.: Theorem 1), optionally followed by a title/summary between parentheses in non-bold font and ended with a period. After that the main body of the item follows, written in 10 pt italics font (see below for examples).

In \LaTeX{} We strongly recommend you to define environments for your examples, definitions, propositions, lemmas, corollaries and similar. This can be done in your \LaTeX{} preamble using \texttt{\textbackslash{newtheorem}} -- see the source of this document for examples. Numbering for these items must be global, not per-section (e.g.: Theorem 1 instead of Theorem 6.1).

\begin{example}[How to write an example]
Examples should be written using the example environment defined in this template.
\end{example}

\begin{theorem}
This is an example of an untitled theorem.
\end{theorem}

You may also include a title or description using these environments as shown in the following theorem.

\begin{theorem}[A titled theorem]
This is an example of a titled theorem.
\end{theorem}

\section{Proofs}

Proofs must be written in their own paragraph separated by at least 2pt and no more than 5pt from the preceding and succeeding paragraphs. Proof paragraphs should start with the keyword ``Proof." in 10pt italics font. After that the proof follows in regular 10pt font. At the end of the proof, an unfilled square symbol (qed) marks the end of the proof.

In \LaTeX{} proofs should be typeset using the \texttt{\textbackslash{proof}} environment.

\begin{proof}
This paragraph is an example of how a proof looks like using the \texttt{\textbackslash{proof}} environment.
\end{proof}


\section{Algorithms and Listings}

Algorithms and listings are a special kind of figures. Like all illustrations, they should appear floated to the top (preferably) or bottom of the page. However, their caption should appear in the header, left-justified and enclosed between horizontal lines, as shown in Algorithm~\ref{alg:algorithm}. The algorithm body should be terminated with another horizontal line. It is up to the authors to decide whether to show line numbers or not, how to format comments, etc.

In \LaTeX{} algorithms may be typeset using the {\tt algorithm} and {\tt algorithmic} packages, but you can also use one of the many other packages for the task.

\begin{algorithm}[tb]
\caption{Example algorithm}
\label{alg:algorithm}
\textbf{Input}: Your algorithm's input\\
\textbf{Parameter}: Optional list of parameters\\
\textbf{Output}: Your algorithm's output
\begin{algorithmic}[1]
\STATE Let $t=0$.
\WHILE{condition}
\STATE Do some action.
\IF {conditional}
\STATE Perform task A.
\ELSE
\STATE Perform task B.
\ENDIF
\ENDWHILE
\STATE \textbf{return} solution
\end{algorithmic}
\end{algorithm}

\section*{Acknowledgments}

The preparation of these instructions and the \LaTeX{} and Bib\TeX{}
files that implement them was supported by Schlumberger Palo Alto
Research, AT\&T Bell Laboratories, and Morgan Kaufmann Publishers.
Preparation of the Microsoft Word file was supported by IJCAI.  An
early version of this document was created by Shirley Jowell and Peter
F. Patel-Schneider.  It was subsequently modified by Jennifer
Ballentine and Thomas Dean, Bernhard Nebel, Daniel Pagenstecher,
Kurt Steinkraus, Toby Walsh and Carles Sierra. The current version
has been prepared by Marc Pujol-Gonzalez and Francisco Cruz-Mencia.



