\section{Additional FUN Experiments} \label{additional_fun_experiments}
\subsection{Input Compression} \label{input compression section}
\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c c c}
    \toprule
    \# Input Channels & Y/Cb/Cr & Top-1 Acc. & \# Parameters (M) \\
    \midrule
    $192$ &
    \multicolumn{1}{c}{$64/64/64$} &
    \multicolumn{1}{c}{$77.01$} &
    \multicolumn{1}{c}{$4.23$}  \\
    $88$ &
    \multicolumn{1}{c}{$64/12/12$} &
    \multicolumn{1}{c}{$76.02$} &
    \multicolumn{1}{c}{$3.99$} \\
    $88$ &
    \multicolumn{1}{c}{$44/22/22$} &
    \multicolumn{1}{c}{$74.15$} &
    \multicolumn{1}{c}{$3.99$} \\
    $64$ &
    \multicolumn{1}{c}{$44/10/10$} &
    \multicolumn{1}{c}{$73.95$} &
    \multicolumn{1}{c}{$3.96$}   \\
    $48$ &
    \multicolumn{1}{c}{$32/8/8$} &
    \multicolumn{1}{c}{$69.45$} &
    \multicolumn{1}{c}{$3.93$}   \\
    $24$ &
    \multicolumn{1}{c}{$14/5/5$} &
    \multicolumn{1}{c}{$51.85$} &
    \multicolumn{1}{c}{$3.91$} \\
    \bottomrule
    \end{tabular}
    }
    \caption{Effects of dropping channels on accuracy and model size for EFNet-B0}
\label{tb:performace_vs_num_channels}
\end{table}

\begin{figure}
    \includegraphics[scale=0.4]{figures/fig_input_compression.png}
    \caption{Imagenet Acc vs input compression ratio}
    \label{imagenet_acc_vs_input_compression}
\end{figure}

In this experiment, we take a trained eFUN show the effects of discarding input channels on the model accuracy and size. To do so, during inference we zero out selected Y, Cb, and Cr channels.
We show that one can significantly reduce the number of frequency channels used to represent the input by keeping only the lowest frequency channels in each of Y, Cb, and Cr.

Our results, presented in Table~\ref{tb:performace_vs_num_channels}, show that when using our FUN framework, one can significantly reduce the size of the input, while maintaining a relatively high accuracy. For example, dropping $54\%$ of the input channels (from $192$ to $88$) results in a $1\%$ drop in accuracy while dropping $75\%$ of the input channels results in a $7.5\%$ drop in accuracy. These results offer a desirable property: as no additional training is performed here, our framework inherently supports different possible operating points with regard to the input compression ratio.

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c}
    \toprule
    Model & Imagenet Top-1 Acc.& \# Parameters(M)\\
    \midrule
    eFUN &
    \multicolumn{1}{c}{77} &
    \multicolumn{1}{c}{4.2} \\
    DCT-Encoder &
    \multicolumn{1}{c}{72.8} &
    \multicolumn{1}{c}{4.3} \\
    Learned-DCT &
    \multicolumn{1}{c}{77.2} &
    \multicolumn{1}{c}{4.3} \\
    \bottomrule
    \end{tabular}
    }
    \caption{comparison of jpeg dct vs learnable transforms}
\label{tb:res_learnable_dct}
\end{table}

\begin{figure*}
\setlength{\tabcolsep}{1pt}
\centering
    \begin{tabular}{c c c}
        \includegraphics[width=0.3\textwidth]{figures/fig_learnable_dct_finetune.png}&
        \includegraphics[width=0.3\textwidth]{figures/fig_learnable_dct_full_train.png}&
        \includegraphics[width=0.3\textwidth]{figures/fig_dct.png}
    \end{tabular}
    \caption{dct filters. Left to right: learned encoder, learned full train, static JPEG \yac{This names are not clear, but I assume we'll fix that later.}}
    \label{fig:dct_filers}
\end{figure*}

\subsection{A Learnable DCT Transformation}
In this experiment, we study whether the input DCT can be replaced with a learnable convolutional layer. In particular, the new convolutional layer receives as input a YCbCr image obtained from its RGB representation. It then transforms each $8\times8\times1$ input block into $1\times1\times64$ outputs. The final DCT output, of size $28\times28\times192$, is then fed into the original network, as before.

We propose two methods of learning this transformation:
\begin{enumerate}
    \item Adding a DCT-like convolutional layer before the eFUN architecture and training the entire network end-to-end, denoted Learnable-DCT
    \item Adding a DCT-like convolutional layer before an already trained eFUN model and training only the added convolutional layer, denoted DCT-Encoder.
\end{enumerate}
Intuitively, the second approach implements an "encoder-decoder" architecture, where the decoder is a fixed eFUN network and the encoder is trained to produce inputs similar to those expected by the decoder.

The results achieved by each of the methods are presented in Table~\ref{tb:res_learnable_dct}. We can see that using the learned convolutional filters provides the best accuracy, while being a slightly larger model compared to the standard eFUN model.
Freezing the entire network with the exception of the input convolutional layer results poor accuracy. However, by allowing the entire network to learn, the Learnable-DCT method achieves accuracy slightly higher than that of our eFUN model.

The filters learned by each of the three methods are presented in Figrue~\ref{fig:dct_filers}. We can see that some of the filters learned by our new layers seem similar to those of the standard DCT - they include vertical and horizontal lines in some frequency. However, most filters still look rather different than those of the DCT, showing the usefulness of using the static DCT filters, which allow us a level of understanding and a built-in meaningful ordering of the filters, which does not exist for the learned filters. \yac{I am not sure what is supposed to be better, but seems like the right-most is the nicest. Need to see how we can formulat that to make it standout?} \kgc{I tried explaining a bit more}

Our results show that using a DCT-like learned convolutional layer for RGB inputs can provide results similar to those of eFUN models in terms of model size, latency, and top-1 accuracy. However, using a learned transformation makes it difficult to analyze the importance of each input channel and does not provide inherent support for dynamic input compression presented in Section~\ref{input compression section}.
\section{Conclusions} \label{Conclusions}
In this paper we have presented the FUN family. These architectures were designed, using modern building blocks, to utilize DCT inputs instead of the standard RGB ones. We show that using this representation one can create architectures that are much more efficient, in terms of size and latency, while still maintaining the accuracy of RGB-based models. The effectiveness of this representation is then shown using an extensive set of experiments. We hope that, apart from its direct impact, FUN would inspire more research into the effectiveness of the frequency-domain for training neural networks.

\section{Discussion} \label{Discussion}
1. Frequency domain is good for smaller models

2. Wider inputs allow shallower networks which speed up inference

3. FLOPs isn't a good measure for GPU latency

4. Frequency domain is a built-in way of prioritizing input information, unlike just resizing the RGB input image

5. With some prior knowledge on the data (e.g. - natural images usually don't feature high frequencies) efficiency can be leveraged further

6. Room for more research - NAS, architectures for less channels, optimizing for CPU, other transforms
\section{Experiments} \label{Experiments}
In this section an evaluation of the FUN models introduced in Section \ref{FUN framework} is performed.
We start by evaluating our ResFUN architecture in comparison to the standard ResNet architectures.
We then conduct an extensive evaluation of our eFUN family of models, and compare them to a wide variety of efficiency-oriented RGB-based models.
We continue by investigating the transfer-learning capabilities of our models compared to those of RGB-based models.
Finally, we perform an ablation study to explore different possible architectural choices.

\begin{table*}
  \vskip 0.1in
    \centering
    \begin{tabular}{l c c c c}
    \toprule
    Model & Top-1 Acc. & \# Parameters (M) & Images / sec. & \#FLOPs (M)\\
    \midrule
    \bf eFUN-S+ &
    \multicolumn{1}{c}{$73.3\%$} &
    \multicolumn{1}{c}{$2.5$} &
    \multicolumn{1}{c}{$145$} &
    \multicolumn{1}{c}{$520$} \\
    RegNetX-400MF \cite{radosavovic2020designing} &
    \multicolumn{1}{c}{$72.4\%$} &
    \multicolumn{1}{c}{$5.2$} &
    \multicolumn{1}{c}{$70$} &
    \multicolumn{1}{c}{$400$} \\
    MobileNet-V2 1.0 \cite{sandler2018mobilenetv2} &
    \multicolumn{1}{c}{$73\%$} &
    \multicolumn{1}{c}{$3.5$} &
    \multicolumn{1}{c}{$148$} &
    \multicolumn{1}{c}{$300$} \\
    MobileNet-V3-Large 0.75 \cite{howard2019searching} &
    \multicolumn{1}{c}{$73.4\%$} &
    \multicolumn{1}{c}{$4$} &
    \multicolumn{1}{c}{$95$} &
    \multicolumn{1}{c}{$150$} \\
    \hline
    \bf eFUN-S &
    \multicolumn{1}{c}{$75.6\%$} &
    \multicolumn{1}{c}{$3.4$} &
    \multicolumn{1}{c}{$132$} &
    \multicolumn{1}{c}{$600$}\\
    FBNet-C\cite{wu2019fbnet}&
    \multicolumn{1}{c}{$75.1\%$} &
    \multicolumn{1}{c}{$5.6$} &
    \multicolumn{1}{c}{$122$} &
    \multicolumn{1}{c}{$375$} \\
    SEMNASNet 1.0 \cite{tan2019mnasnet} &
    \multicolumn{1}{c}{$75.4\%$} &
    \multicolumn{1}{c}{$3.9$} &
    \multicolumn{1}{c}{$122$} &
    \multicolumn{1}{c}{$300$} \\
    MobileNet-V3-Large 1.0 \cite{howard2019searching} &
    \multicolumn{1}{c}{$75.8\%$} &
    \multicolumn{1}{c}{$5.5$} &
    \multicolumn{1}{c}{$94$} &
    \multicolumn{1}{c}{$220$} \\
    RegNetY-800MF \cite{radosavovic2020designing}&
    \multicolumn{1}{c}{$76.3\%$} &
    \multicolumn{1}{c}{$6.3$} &
    \multicolumn{1}{c}{$77$} &
    \multicolumn{1}{c}{$800$} \\
    \hline
    \bf eFUN &
    \multicolumn{1}{c}{$77\%$} &
    \multicolumn{1}{c}{$4.2$} &
    \multicolumn{1}{c}{$124$} &
    \multicolumn{1}{c}{$850$} \\
    EfficientNet-B0 \cite{tan2019efficientnet}&
    \multicolumn{1}{c}{$77.4\%$} &
    \multicolumn{1}{c}{$5.3$} &
    \multicolumn{1}{c}{$77$} &
    \multicolumn{1}{c}{$400$} \\
    \hline
    \bf eFUN-L &
    \multicolumn{1}{c}{$78.8\%$} &
    \multicolumn{1}{c}{$6.2$} &
    \multicolumn{1}{c}{$101$}  &
    \multicolumn{1}{c}{$1,600$} \\
    EfficientNet-B1 \cite{tan2019efficientnet} &
    \multicolumn{1}{c}{$79.3\%$} &
    \multicolumn{1}{c}{$7.8$} &
    \multicolumn{1}{c}{$56$} &
    \multicolumn{1}{c}{$700$} \\
    \bottomrule
    \end{tabular}
    \caption{eFUN performance on ImageNet. CNNs with similar top-1 accuracy are grouped together for clear comparison.}
    \label{tab:imagenet_results}
\end{table*}

\subsection{ImageNet Results on ResFUN}
We first show results obtained on the ImageNet classification task using our constructed ResFUN architecture compared to standard ResNet architectures operating on inputs represented in RGB.
Results are summarized in Table~\ref{tab:resnet_results}. While the RGB-based ResNets offer different trade-offs between accuracy and model size by changing the depth of the model, our frequency-based ResFUN offers appealing advantages. Compared to the smallest ResNet model, ResNet-18, ResFUN is both shallower and uses less filters in each block while achieving a higher top-1 accuracy by approximately $3\%$ and being smaller in size. Although the larger ResNet-34 architecture out-performs our model with respect to top-1 accuracy, the ResFUN architecture provides an attractive alternative being $\times2$ smaller than the standard ResNet-34 architecture. These comparisons show that the ResFUN architecture manages to be smaller than the ResNet18 while being almost as accurate as the ResNet34, making ResFUN significantly more efficient than the ResNet architectures.

\subsection{ImageNet Results on eFUN}~\label{imagenet results section}
The results of our eFUN models are presented in Table~\ref{tab:imagenet_results} and show that the eFUN model is $20\%$ smaller and $65\%$ faster than the highly-efficient, state-of-the-art EfficientNet-B0 model, while being very close in terms of accuracy ($77.4\%$ for EfficientNet-B0 compared to $77\%$ eFUN).
Building on the eFUN model, we use EfficientNet's compound scaling method, allowing us to scale up and scale down the eFUN architecture to provide flexibility with respect to the desired computational budget. In particular, the smallest architecture generated by compound scaling of the eFUN model is the eFUN-S+ architecture, which is $30\%$ smaller and $0.3\%$ more accurate than the comparable MobileNet-V2-100 model. Although both models obtain similar inference latency (Figure~\ref{imagenet_acc_vs_latency}), MobileNet-V2 was specifically designed and optimized for inference latency, while eFUN-S+ is inherently fast due to the advantages offered by FUN, while also being smaller and more accurate than the former.

\begin{figure}
    \includegraphics[scale=0.4]{figures/fig_latency.png}
    \caption{ImageNet Accuracy vs. Latency.}
    \label{imagenet_acc_vs_latency}
\end{figure}

Table~\ref{tab:imagenet_results} shows that while  eFUN models are typically faster than similar RGB-based models at inference time, their FLOP count is significantly higher. FLOPs are usually used as a proxy to estimate the run time of models on different CPUs without measuring on a specific setup. Our results show that FLOPs are not a good indicator for inference latency when measured on GPUs, due to their highly paralleled nature. Since eFUN models are generally significantly shallower ($10-13$ layers) than EfficientNet models ($18$ layers for EfficientNet-B0), their execution on GPUs, proportional to the depth of the network, is faster.

\begin{table}
  \vskip 0.1in
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{l c c c c}
    \toprule
    Dataset & Train size & Test Size & \# Classes \\
    \midrule
    CIFAR-100 \cite{krizhevsky2009learning} &
    \multicolumn{1}{c}{50,000} &
    \multicolumn{1}{c}{10,000} &
    \multicolumn{1}{c}{100} \\
    Stanford Cars \cite{krause2013collecting} &
    \multicolumn{1}{c}{8,144} &
    \multicolumn{1}{c}{8,041} &
    \multicolumn{1}{c}{196} \\
    FGVC Aircraft \cite{maji2013fine} &
    \multicolumn{1}{c}{6,667} &
    \multicolumn{1}{c}{3,333} &
    \multicolumn{1}{c}{100} \\
    \bottomrule
    \end{tabular}
    }
    \caption{Transfer Learning Datasets.}
    \label{tab:transfer_learning_datasets}
\end{table}

\begin{figure*}
\setlength{\tabcolsep}{1pt}
\centering
    \begin{tabular}{c c c}
        \includegraphics[width=0.33\textwidth]{figures/fig_cifar100.png}&
        \includegraphics[width=0.33\textwidth]{figures/fig_fgvc_aircraft.png}&
        \includegraphics[width=0.33\textwidth]{figures/fig_stanford_cars.png}
    \end{tabular}
    \caption{Transfer learning results, from left to right: CIFAR100~\cite{krizhevsky2009learning}, FGVC aircraft~\cite{maji2013fine}, Stanford Cars~\cite{krause2013collecting}.}
    \label{fig:transfer_learning}
\end{figure*}

\subsection{Transfer Learning Results for FUN Architectures}
To show that FUN generalizes for different tasks, we present an evaluation of our models on three commonly used transfer learning datasets, which are presented in Table \ref{tab:transfer_learning_datasets}.
For these experiments, the same settings defined in Section~\ref{subsec:imp} are applied, where each model is first pretrained on ImageNet and then fine-tuned on its task.

Figure \ref{fig:transfer_learning} illustrates the trade-off between model accuracy, model size and inference latency for three transfer learning datasets. For each model, we report results for top-1 accuracy, inference speed (in images per second), and model size (in number of parameters). One can see that eFUN models significantly outperform the competing models in terms of model size and inference latency, while providing comparable accuracy.
Specifically, when considering the popular CIFAR-100 dataset~\cite{krizhevsky2009learning}, the eFUN model outperforms the EfficientNet-B0 model by $0.9\%$ accuracy, while still being $20\% $smaller and $65\%$ faster. Our eFUN-S+ model is lower in accuracy compared to EfficientNet-B0 model ($82.5\%$ for EfficientNet-B0 compared to $81.1\%$ for eFUN-S+), but is $53\%$ smaller and $91\%$ faster.

\subsection{Architecture Ablation Study}

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c c c}
    \toprule
    Stage &
    Operator &
    Resolution &
    \# Channels  &
    \# Layers\\
    $i$ &
    $\mathcal{\hat{F}}_i$ &
    $\mathcal{\hat{H}}_i\times\mathcal{\hat{W}}_i$ &
    $\mathcal{\hat{C}}_i$ &
    $\mathcal{\hat{L}}_i$ \\
    \midrule
    $1$ &
    \multicolumn{1}{c}{MBConv1, k3x3} &
    \multicolumn{1}{c}{$28\times28$} &
    \multicolumn{1}{c}{16} &
    \multicolumn{1}{c}{1}  \\
    $2$ &
    \multicolumn{1}{c}{MBConv6, k3x3} &
    \multicolumn{1}{c}{$28\times28$} &
    \multicolumn{1}{c}{24} &
    \multicolumn{1}{c}{2}  \\
    $3$ &
    \multicolumn{1}{c}{MBConv6, k5x5} &
    \multicolumn{1}{c}{$28\times28$} &
    \multicolumn{1}{c}{40} &
    \multicolumn{1}{c}{2}  \\
    $4$ &
    \multicolumn{1}{c}{MBConv6, k3x3} &
    \multicolumn{1}{c}{$28\times28$} &
    \multicolumn{1}{c}{80} &
    \multicolumn{1}{c}{3}  \\
    $5$ &
    \multicolumn{1}{c}{MBConv6, k5x5} &
    \multicolumn{1}{c}{$14\times14$} &
    \multicolumn{1}{c}{112} &
    \multicolumn{1}{c}{3}  \\
    $6$ &
    \multicolumn{1}{c}{MBConv6, k5x5} &
    \multicolumn{1}{c}{$14\times14$} &
    \multicolumn{1}{c}{192} &
    \multicolumn{1}{c}{4}  \\
    $7$ &
    \multicolumn{1}{c}{MBConv6, k3x3} &
    \multicolumn{1}{c}{$7\times7$} &
    \multicolumn{1}{c}{320} &
    \multicolumn{1}{c}{1}  \\
    $8$ &
    \multicolumn{1}{c}{Conv1x1 \& Pooling \& FC} &
    \multicolumn{1}{c}{$7\times7$} &
    \multicolumn{1}{c}{1280} &
    \multicolumn{1}{c}{1} \\
    \bottomrule
    \end{tabular}
    }
\caption{The eFUN-variant-A architecture. Each row describes a stage, $i$, with $\hat L_i$ layers, input resolution $\langle \hat H_i, \hat W_i \rangle$ and output channels $\hat C_i$.}
\label{tb:ablation_effnet_b0}
\end{table}

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c c c}
    \toprule
    Stage &
    Operator &
    Resolution &
    \# Channels  &
    \# Layers\\
    $i$ &
    $\mathcal{\hat{F}}_i$ &
    $\mathcal{\hat{H}}_i\times\mathcal{\hat{W}}_i$ &
    $\mathcal{\hat{C}}_i$ &
    $\mathcal{\hat{L}}_i$ \\
    \midrule
    $1$ &
    \multicolumn{1}{c}{MBConv6, k3x3} &
    \multicolumn{1}{c}{$28\times28$} &
    \multicolumn{1}{c}{80} &
    \multicolumn{1}{c}{3}  \\
    $2$ &
    \multicolumn{1}{c}{MBConv6, k5x5} &
    \multicolumn{1}{c}{$14\times14$} &
    \multicolumn{1}{c}{112} &
    \multicolumn{1}{c}{3}  \\
    $3$ &
    \multicolumn{1}{c}{MBConv6, k5x5} &
    \multicolumn{1}{c}{$14\times14$} &
    \multicolumn{1}{c}{192} &
    \multicolumn{1}{c}{4} \\
    $4$ &
    \multicolumn{1}{c}{MBConv6, k3x3} &
    \multicolumn{1}{c}{$7\times7$} &
    \multicolumn{1}{c}{320} &
    \multicolumn{1}{c}{1} \\
    $5$ &
    \multicolumn{1}{c}{Conv1x1 \& Pooling \& FC} &
    \multicolumn{1}{c}{$7\times7$} &
    \multicolumn{1}{c}{1280} &
    \multicolumn{1}{c}{1} \\
    \bottomrule
    \end{tabular}
    }
\caption{The eFUN-variant-B architecture. Each row describes a stage, $i$, with $\hat L_i$ layers, input resolution $\langle \hat H_i, \hat W_i \rangle$ and output channels $\hat C_i$.}
\label{tb:ablation_bottleneck}
\end{table}

In this section we conduct an ablation study with various alternative architectures to those presented above in order to validate our architecture design.
The first architecture considered is the standard EfficientNet-B0 architecture presented in \cite{tan2019efficientnet}, with a few key changes. First, the first convolution layer is removed and the number of strides is reduced accordingly, in order to keep the spatial dimension of the output layer the same as the original architecture. The modified architecture is presented in Table~\ref{tb:ablation_effnet_b0} and is denoted eFUN-variant-A.
The second architecture was designed by following the modifications made to the ResNet-50 model in order to create the ResFUN architecture. In this architecture, the DCT inputs are fed directly to the stage in the original EfficientNet architecture which is designed to have inputs with the same spatial size as eFUN's DCT inputs ($28\times28$). The rest of the network is the same as the final stages of the standard EfficientNet-B0 architecture. The modified architecture is denoted eFUN-variant-B and presented in Table~\ref{tb:ablation_bottleneck}.

Our results, presented in Table~\ref{tb:ablation}, show that the original eFUN model outperforms both variants. We conclude that the balance between the width and resolution of the network is crucial and that a naive change to the architecture does not yield the same results. In particular, we find that EfficientNet-B0 is not suitable for DCT inputs due to the large difference in input resolution required. Thus, intelligent modifications are needed to design a smaller architecture able to exploit the strengths of the DCT representation.

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c}
    \toprule
    Architecture & Top-1 Acc. & \# Parameters (M) \\
    \midrule
    eFUN &
    \multicolumn{1}{c}{77} &
    \multicolumn{1}{c}{4.2} \\
    eFUN-variant-A &
    \multicolumn{1}{c}{75} &
    \multicolumn{1}{c}{5.3} \\
    eFUN-variant-B &
    \multicolumn{1}{c}{74.9} &
    \multicolumn{1}{c}{5.6} \\
    \bottomrule
    \end{tabular}
    }
    \caption{Architecture ablation study, presented on the ImageNet dataset.}
\label{tb:ablation}
\end{table}

\subsection{Input Compression} \label{input compression section}

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{c c c c c}
    \toprule
    \# Input Channels & Y/Cb/Cr & Top-1 Acc. & \# Parameters (M) \\
    \midrule
    $192$ &
    \multicolumn{1}{c}{$64/64/64$} &
    \multicolumn{1}{c}{$77.01$} &
    \multicolumn{1}{c}{$4.23$}  \\
    $88$ &
    \multicolumn{1}{c}{$64/12/12$} &
    \multicolumn{1}{c}{$76.02$} &
    \multicolumn{1}{c}{$3.99$} \\
    $64$ &
    \multicolumn{1}{c}{$44/10/10$} &
    \multicolumn{1}{c}{$73.95$} &
    \multicolumn{1}{c}{$3.96$}   \\
    $48$ &
    \multicolumn{1}{c}{$32/8/8$} &
    \multicolumn{1}{c}{$69.45$} &
    \multicolumn{1}{c}{$3.93$}   \\
    $24$ &
    \multicolumn{1}{c}{$14/5/5$} &
    \multicolumn{1}{c}{$51.85$} &
    \multicolumn{1}{c}{$3.91$} \\
    \bottomrule
    \end{tabular}
    }
    \caption{The effects of dropping input channels on eFUN performance.}
\label{tb:performace_vs_num_channels}
\end{table}

In this experiment, we take a trained eFUN show the effects of discarding input channels on the model accuracy and size. To do so, during inference selected Y, Cb, and Cr channels are zeroed-out.
We show that one can significantly reduce the number of frequency channels used to represent the input by keeping only the lowest frequency channels in each of Y, Cb, and Cr.

Our results, presented in Table~\ref{tb:performace_vs_num_channels}, show that when using FUN, it is possible to significantly reduce the size of the input, while maintaining a relatively high accuracy. For example, dropping $54\%$ of the input channels (from $192$ to $88$) results in a $1\%$ drop in accuracy while dropping $75\%$ of the input channels results in a $7.5\%$ drop in accuracy. These results offer a desirable property: as no additional training is performed here, FUN models inherently support different possible operating points with regard to the input compression ratio. Figure~\ref{imagenet_acc_vs_input_compression} shows the effect of compression on the Top-1 accuracy for both our DCT eFUN model and an RGB EfficientNet-B0, where simple down-sampling is used to simulate compression for RGB-based models.

\begin{figure}
    \includegraphics[scale=0.4]{figures/fig_input_compression.png}
    \caption{ImageNet accuracy vs. input compression ratio.}
    \label{imagenet_acc_vs_input_compression}
\end{figure}

\begin{figure*}
\setlength{\tabcolsep}{1pt}
\centering
    \begin{tabular}{c c c}
        \includegraphics[width=0.3\textwidth]{figures/encoder_learned_filters.pdf}&
        \includegraphics[width=0.3\textwidth]{figures/fig_learnable_dct_full_train.png}&
        \includegraphics[width=0.3\textwidth]{figures/fig_dct.png}
    \end{tabular}
    \caption{Dct filters. From left to right: $\mbox{LeFUN}$, $\mbox{LeFUN}_{\mbox{e2e}}$, standard DCT.}
    \label{fig:dct_filers}
\end{figure*}

\subsection{A Learnable DCT Transformation}
The core advantage of FUN comes from the usage of the DCT representation, which is static and not learned.
In this experiment, we study whether the input DCT can be replaced with a learnable convolutional layer. In particular, the new convolutional layer receives as input a YCbCr image obtained from its RGB representation. It then transforms each $8\times8\times1$ input block into $1\times1\times64$ outputs. The final DCT output, of size $28\times28\times192$, is then fed into the original network, as before.

We propose two methods of learning this transformation:
\begin{enumerate}
    \item Adding a DCT-like convolutional layer before an already trained eFUN model and training only the added convolutional layer, this Learnable-eFUN variant is denoted LeFUN.
    \item Adding a DCT-like convolutional layer before the eFUN architecture and training the entire network end-to-end, denoted $\mbox{LeFUN}_{\mbox{e2e}}$.
\end{enumerate}
Intuitively, the second approach implements an "encoder-decoder" architecture, where the decoder is a fixed eFUN network and the encoder is trained to produce inputs similar to those expected by the decoder.

The results achieved by each of the methods are presented in Table~\ref{tb:res_learnable_dct}. The results show that $\mbox{LeFUN}_{\mbox{e2e}}$ provides the best accuracy, while resulting in a slightly larger model compared to the standard eFUN model, and $\mbox{LeFUN}$ provides the worst accuracy by a large margin.
The filters learned by each of the three methods are presented in Figure~\ref{fig:dct_filers}.
One can see that some of the filters learned by our new layers seem similar to those of the standard DCT, as they include vertical and horizontal lines in some frequency.
However, most filters still look rather different than those of the DCT, showing the usefulness of using the static DCT filters, which allows an higher level of understanding and has meaningful ordering of the filters.

Our results show that using a DCT-like learned convolutional layer for RGB inputs can provide results similar to those of eFUN models in terms of model size, latency, and top-1 accuracy. However, using a learned transformation makes it difficult to analyze the importance of each input channel and does not provide inherent support for dynamic input compression presented in Section~\ref{input compression section}.

\begin{table}
    \setlength{\tabcolsep}{2.2pt}
    \centering
    \resizebox{1.0\columnwidth}{!}{
    \begin{tabular}{l c c}
    \toprule
    Model & Top-1 Acc.& \# Parameters (M)\\
    \midrule
    eFUN &
    \multicolumn{1}{c}{77} &
    \multicolumn{1}{c}{4.2} \\
    LeFUN  &
    \multicolumn{1}{c}{72.8} &
    \multicolumn{1}{c}{4.3} \\
    $\mbox{LeFUN}_{\mbox{e2e}}$ &
    \multicolumn{1}{c}{77.2} &
    \multicolumn{1}{c}{4.3} \\
    \bottomrule
    \end{tabular}
    }
    \caption{Comparison of fixed and learnable transforms.}
\label{tb:res_learnable_dct}
\end{table}

\section{Frequency-Domain Utilization Networks}~\label{FUN framework}
In this section we introduce a set of novel architectures operating on inputs in the frequency domain. We first describe the preprocessing required for the DCT inputs, followed by the network design process for the different architectures.

\begin{figure}[b]
    \resizebox{1.0\columnwidth}{!}{\includegraphics[scale=0.5]{figures/dct_preprocess.pdf}}
    \caption{RGB to DCT preprocessing for FUN}
    \label{fig:fun_preprocess}
    \vspace{-2mm}
\end{figure}

\begin{figure*}
    \centering
    \begin{subfigure}{\textwidth}
        \centering
        \includegraphics[width=0.75\textwidth]{figures/resfun_arch.pdf}
        \caption{}
        ~\label{fig:resfun_arch}
    \end{subfigure}\\
    \begin{subfigure}{\textwidth}
        \centering
        \includegraphics[width=0.75\textwidth]{figures/efun_arch.pdf}
        \caption{}
        ~\label{fig:efun_arch}
    \end{subfigure}
    \newline
    \caption{FUN architectures, (\subref{fig:resfun_arch}) presents ResFUN, (\subref{fig:efun_arch}) presents eFUN.}
    \label{archs}
    \vspace{-2mm}
\end{figure*}

\subsection{The DCT Preprocessing Pipeline}~\label{preprocessing}
Our preprocessing stage is described in Figure \ref{fig:fun_preprocess}. Similar to \cite{gueguen2018faster}, the RGB-represented input image is first converted to its corresponding YCbCr representation, representing the luminance (Y) and chroma (Cb, Cr) of the image. The two chroma channels are then down-sampled by a factor of $2$, as is done in the JPEG codec. Each of the three channels is then split into $8\times8$ blocks and passed through the DCT converting each to its frequency-domain representation. Next, the two chroma channels are up-sampled to have the same spatial size as the luminance channel. Finally, the three channels are stacked over the frequency domain.

\subsection{The ResFUN Architecture}
First, as an illustrative example, we present the ResFUN architecture described in Figure \ref{fig:resfun_arch}. Similar to the standard ResNet architecture \cite{he2016deep}, ResFUN is constructed using Residual Blocks. In the case of ResFUN, however, the input layer must be changed to accommodate the DCT-represented inputs. In a similar fashion to \cite{gueguen2018faster}, we remove the first convolutional layer and first Residual Block of the ResNet, corresponding to the initial $\times8$ down-sampling of the original RGB input image, to fit the $28\times28$ spatial size of the DCT-based inputs.

Additionally, to further reduce the number of parameters in our model, we decrease the number of filters in each of the ResNet stages --- from $512$, $1024$, $2048$ in ResNet-50 to $512$, $768$, $1024$ in our ResFUN architecture, respectively. Doing so reduces the model size by a factor of $2.5$, from $25.5$M parameters in ResNet-50, to $10.4$M in our ResFUN model. This additional reduction in model size is possible since our DCT inputs are already a processed, more compact representation than the RGB inputs, for which the standard ResNets are designed.

\subsection{The eFUN Architecture}
Having successfully converted the ResNet architecture to operate on DCT-represented inputs, we then turn to more efficiency-oriented architectures. Specifically, we focus on the class of architectures utilizing the Inverted Residual Block (MBConv)~\cite{sandler2018mobilenetv2,howard2019searching, tan2019mnasnet, tan2019efficientnet, radosavovic2020designing}. A notable example of such architectures is the EfficientNet~\cite{tan2019efficientnet} family of architectures, which additionally introduces the compound model scaling technique. There, one can generate scaled-up versions of a baseline model by intelligently balancing the width, depth, and input resolution to maximize performance for a given computational budget.
Following these recent architectural advancements, we present a family of FUN models, efficientFUN (eFUN). Our baseline eFUN model, illustrated in Figure~\ref{fig:efun_arch} is inspired by EfficientNet-B0, but with several key differences.

\paragraph{Shallower Architecture} As EfficientNet-B0 receives RGB inputs of size $224\times224\times3$, their input is only down-sampled to a spatial dimension of $28\times28$ after the first six layers. Conversely, our eFUN models are given DCT inputs already with a spatial resolution of $28\times28$.
The smaller input resolution enables us to create a shallower network, leading to lower inference latency compared to the larger EfficientNet counterpart.

\paragraph{Wider Bottleneck} In EfficientNet-B0, the stages with equivalent input resolutions to the DCT domain are $5$ and $6$. To compensate for the loss of representation strength from stages $1$ through $4$, we widen stages $5$ and $6$ of EfficientNet-B0 channels from $80$ and $112$, to $128$ and $160$ respectively.

\paragraph{Scaled-Down Models} Given the base model constructed above, the compound scaling method is leveraged to generate additional architectures. In contrast to ~\cite{tan2019efficientnet} however, we scale \textit{down} our eFUN model and generate the smaller eFUN-S+ and eFUN-S models in addition to scaling up to obtain the larger eFUN-L model.

\subsection{The Benefits of FUN}

The shallower design of the eFUN and ResFUN architectures is a direct consequence of working in the frequency domain. Specifically in the case of DCT, this results in a wider but shallower network. In the following sections we show that this design change in the eFUN architecture is superior to the original design in both accuracy and model size. Our results are in agreement with  \cite{zagoruyko2016wide} where it was shown that the wider but shallower deep residual networks outperformed previous deeper but thinner versions of the same networks.

Additionally, due to the parallel compute paradigm in modern GPUs, a known rule of thumb is that, all else being equal, shallow and wide beats deep and narrow in terms of inference latency. For our eFUN network, this can lead to between $30\%$ and $80\%$ inference time improvements compared to baseline RGB architectures.

Finally, FUNs allow for dynamic reduction of the input size. Unlike the RGB or YCbCr representations, where all 3 input channels have similar importance, in DCT coefficients the lower frequencies tend to have a larger visual importance. This insight is leveraged to show how the eFUN architectures can work well even when significantly reducing the number of input channels of a trained model, with no additional training or modifications needed.

\subsection{Implementation Details}\label{subsec:imp}
All of our FUN models take as input 224x224 RGB images, which first pass through the preprocessing presented in Section~\ref{preprocessing}. We use the computed DCT of each input image, with the same configuration as the standard JPEG DCT, and use JPEG image quality set to 100, meaning the DCT coefficients are not further compressed. The DCT coefficients obtained from the JPEG pipeline are in the shape of 28x28x64 for the Y channel, and 14x14x64 for each of the Cb and Cr channels. The chroma channels are then up-sampled and all three channels are stacked over the frequency dimension, resulting in a final input of size 28x28x192.

The eFUN models are trained on ImageNet using a similar settings to that of~\cite{tan2019efficientnet}:
The RMSProp optimizer is used with decay of 0.9 and momentum of 0.9; weight decay of 1e-5; and a learning rate scheduler with an initial learning rate of 0.048 with a decay of 0.97 every 2.4 epochs.
We also use stochastic depth with a drop probability of 0.2 for eFUN-S+, eFUN-S and eFUN, and 0.3 drop probability for eFUN-L. The models are trained for 450 epochs using 4 NVIDIA V100 GPUs and a batch size of 512 and inference latency of all models is measured using a single NVIDIA V100 GPU with a batch size of 1. All latency measurements are computed as if the images were already loaded in the relevant representation (RGB/DCT), thus the timing improvement possible due to reduced JPEG decompression time for DCT representation is not taken into account.
The results for RGB-based models are reported using the same implementation \footnote{\url{https://github.com/rwightman/pytorch-image-models}} where EfficientNet-B0 and EfficientNet-B1 are trained using the same settings as the eFUN models.
Additionally, Our ResFUN model is trained using the SGD optimizer with a learning rate of 0.1 for 90 epochs, 0.01 for 20 epochs, and 0.001 for 20 epochs.

\begin{table}
  \vskip 0.1in
    \centering
    \begin{tabular}{l c c c}
    \toprule
    Model & Top-1 Acc. & \# Parameters (M) & Images / sec.\\
    \midrule
    \bf ResFUN &
    \multicolumn{1}{c}{$72.8\%$} &
    \multicolumn{1}{c}{$10.4$} &
    \multicolumn{1}{c}{$167$} \\
    ResNet18 &
    \multicolumn{1}{c}{$69.8\%$} &
    \multicolumn{1}{c}{$11.7$} &
    \multicolumn{1}{c}{$330$} \\
    ResNet34 &
    \multicolumn{1}{c}{$73.3\%$} &
    \multicolumn{1}{c}{$21.8$} &
    \multicolumn{1}{c}{$180$} \\
    \bottomrule
    \end{tabular}
    \caption{ResFUN performance compared to ResNets with different depths}
    \label{tab:resnet_results}
\end{table}

\section{Introduction}
\blfootnote{Code available at\ \ \url{https://github.com/kfir99/FUN}}
The introduction of well-designed convolutional neural networks (CNNs) has revolutionized the computer vision field~\cite{krizhevsky2012imagenet, alom2018history,conneau2016very, szegedy2015going, he2016deep}. While early efforts in the design of such networks focused mostly on maximizing accuracy, recent works \cite{tan2019efficientnet,howard2017mobilenets,radosavovic2020designing,wu2019fbnet,tan2019mnasnet} have shown the importance of architectures that are not only accurate, but also efficient. More specifically, these works focus on lowering the number of floating point operations (FLOPs), inference latency and the number of model parameters while maximizing model accuracy.

\begin{figure}
    \includegraphics[scale=0.4]{figures/fig_model_size.png}
    \caption{ImageNet Accuracy vs Model Size}
    \label{imagenet_acc_vs_size}
\end{figure}

An increasingly popular avenue for research on CNNs efficiency
is to leverage frequency domain representations of images, most commonly achieved using the Discrete Cosine Transform (DCT). Being part of the JPEG codec, the DCT is both widely used and convenient to work with. As a result, previous works used the DCT coefficients as inputs to CNNs, achieving faster inference ~\cite{gueguen2018faster, Ehrlich_2019_ICCV} and more control ~\cite{xu2020learning} over the input size.
\\
We build upon these works by introducing a family of novel Frequency-domain Utilization Networks (FUN). As the name suggests, FUN networks utilize the advantages inherent in the frequency domain representations. We present a family of architectures that allow for trade-offs between model accuracy, model size, and inference latency, while also allowing for different levels of input compression.\\

Motivated by the results presented in \cite{gueguen2018faster}, we explore similar design principles in the widely used ResNet architectures. The resulting frequency domain architecture, named ResFUN, is superior in terms of efficiency and model size to both the original ResNet and the modified DCT based architecture in \cite{gueguen2018faster}. Next, we apply these design principles to more efficiency oriented class of architectures ~\cite{sandler2018mobilenetv2,tan2019efficientnet} whose main building block is the Inverted Residual Block (MBConv). The resulting DCT-based architecture, named eFUN, is significantly faster and lighter than the equivalent RGB-based architectures, while achieving comparable, and at times, even better accuracy. We further extend our FUN family by using the compound scaling method~\cite{tan2019efficientnet}, generating models with a range of sizes, speeds, and accuracy, providing different degrees of freedom when selecting a model for different computational budgets. Figure~\ref{imagenet_acc_vs_size} summarizes our performance on the ImageNet classification task, showing that eFUN outperforms other competing models.\\

Extensive evaluations are performed to measure the effectiveness and benefits of our eFUN family of models compared to highly-optimized RGB-based networks. For example, on the ImageNet classification task, our base model, eFUN, is $20\%$ smaller and $65\%$ faster than EfficientNet-B0, while dropping only a small percentage of accuracy. Notably our results show that due to the inherent properties of the DCT representation, one can remove more than half of the input channels of a model trained on ImageNet with a drop of less than $1\%$ in top-1 accuracy with no additional training.

Our main contributions are:
\begin{itemize}
    \item A novel, DCT-based, CNN architecture achieving state-of-the-art results on ImageNet classification.
    \item A family of frequency-based models constructed using the compound scaling method introduced in~\cite{tan2019efficientnet}.
\end{itemize}

\section{Related Work} \label{Related Work}

\paragraph{Efficient CNNs}
In recent years, CNNs have significantly improved, becoming increasingly more accurate over time. However, this accuracy has come at a cost in the form of slower, larger architectures~\cite{touvron2020fixing, xie2020self, huang2019gpipe}.
As these CNNs have gotten bigger, we have begun reaching hardware capacity limitations. For example, GPIPE \cite{huang2019gpipe} with over $560$M parameters requires a dedicated infrastructure for training. Therefore, recent works \cite{tan2019mnasnet, howard2017mobilenets, sandler2018mobilenetv2, tan2019efficientnet, zhang2017shufflenet, i2016squeezenet} have focused on designing more efficient architectures without compensating for accuracy.
While many works have done so using more standard techniques such as pruning \cite{frankle2018lottery} and quantization \cite{wu2016quantized}, it has become common to design highly-optimized architectures obtained using a Neural Architecture Search (NAS) aimed at optimizing the FLOP count as a proxy for inference latency that is agnostic of the underlying hardware.
Contrary to these works, we approach the efficiency problem by changing the representation of the data, from RGB to DCT coefficients, and design efficient architectures operating on the DCT inputs.

\paragraph{Frequency Domain Based Networks}
The utilization of the frequency domain for CNNs has been studied in the past for various reasons.
\cite{gueguen2018faster} have shown that feeding DCT inputs to ResNet-based CNNs can lead to a significant speedup in inference latency while maintaining accuracy close to that of RGB-based models. The speedup provided by their architectures is due to the shallower network and the lower spatial size of the DCT inputs.
We extend this work, utilizing more modern architectural building blocks and achieving better efficiency in terms of inference latency, model size, and input size.
\cite{xu2020learning} trade-off the spatial size of the input with the number of DCT coefficients used to represent each block in the DCT. They suggest using DCT inputs with larger spatial dimensions ($448\times448$ compared to $224\times224$ for RGB), while keeping only a certain number of DCT coefficients from each block. We show that our FUN models can work well even when drastically reducing the number of DCT channels used for each block, without any need to change the spatial size of the input, thus enabling the use of highly compressed inputs.
Finally, \cite{ulicny2020harmonic} propose using a new block, the Harmonic block, in RGB-based architectures, which relies on the DCT filters.


\section{IMPLEMENTATION DETAILS}
\label{appendix:impl}

\subsection{Hyperparameters}
In Table~\ref{tbl:synth-cfg} we show the hyperparameters used for the experiments on the procedurally generated data sets. The only differences in the experiments for the city road networks are the number of training steps which was set to 40000 and the hidden layer width of the neural network (see next subsection). We elaborate on hyperparameters, the usage of which may not be immediately clear:

\paragraph{Node History}
It is common in deep reinforcement learning to replace the input observation $\mathbf{x}_t$ with a stack of the last $k$ observations $[\mathbf{x}_{t-k+1}, \mathbf{x}_{t-k+2}, \ldots, \mathbf{x}_t]$, particularly when the observations are images. This gives the agent a sense of the environment dynamics. We found that using a stack of the last 2 feature vectors for each node also improves performance in graph exploration, as it gives a sense of direction.

\paragraph{Feature Range}
As a preprocessing step, shifting input features to the $[-0.5, 0.5]$ range speeds up learning.

\paragraph{Target Normalization}
As a postprocessing step, target normalization also aids the learning process. We scaled targets $\mathbf{y}$ by the standard deviation of measurements collected during random exploration, as described by \cite{dosovitskiy2016learning}.

\paragraph{Evaluation Episodes}
For evaluation, we sampled 50 graphs from the test set and fixed one source node per graph. If the test set contained less than 50 graphs, we sampled 50 source nodes uniformly from all test graphs.

\paragraph{$\varepsilon$-greedy Policy}
As described in our training algorithm, we used an $\varepsilon$-greedy policy to collect experiences, namely a random frontier node was selected to be visited with probability $\varepsilon$ and a node was selected by the network's policy with probability 1 - $\varepsilon$. We linearly interpolated $\varepsilon$ from 1 to 0.15 over the course of training. During testing, the greedy policy ($\varepsilon=0$) was used.

\begin{table}[h!]
	\caption{Hyperparameters used in experiments on procedurally generated graphs.}
	\vspace{-.1in}
	\begin{center}
		\input{tables/cfg_synth.tex}
	\end{center}
	\label{tbl:synth-cfg}

\end{table}

\subsection{Network Architecture}
The architecture of our network, used for the procedurally generated graphs, is shown in Table~\ref{tbl:net-synth-cfg}. The same architecture was used for the city road networks except that all layers - apart for input and output - are wider by a factor of two. The input dimension for the graph neural network (GNN) was 3 for NOGE and 4 for NOGE-NN. In all networks we use the ReLU nonlinearity after all layers except for the output layer of the row-wise feed-forward (rFF) network.

\subsection{Replay Buffer for Graphs}
To use the replay buffer for training, we need to be able to sample graph observations $G_t$ from any time step in an episode. To do that, for each episode we store the discovered graph $G_T=(V_T, E_T)$ at the end of the episode and two arrays: an array of node counts and an array of edge counts, indicating the size of the graph at each time step. To be able to reconstruct the frontier at an arbitrary time step $t$, we need to store two integers per node $v$: the time of discovery $t_{dis}(v)$ and the time of visit $t_{dis}(v)$. Then the frontier $F_t$ at any time step $t$ is:
\begin{equation}
	F_t = \{v \in V_t : t \geq  t_{dis}(v) \land t < t_{vis}(v) \}
\end{equation}

\begin{table}[h!]
	\caption{The network architecture.}
	\vspace{-.1in}
	\begin{center}
		\begin{tabular}{lcc}
			\toprule
			module & input dimension & output dimension \\
			\midrule
			GNN    &			   3 or 4 & 32 \\
				   &			  32 & 64 \\
			\midrule
			MLP	   &			   1 & 64 \\
				   &			  64 & 64 \\
			\midrule
			rFF    &			 256 & 128 \\
				   &			 128 & 8 \\
			\bottomrule
		\end{tabular}
	\end{center}
	\label{tbl:net-synth-cfg}
\end{table}

\section{COMPARISON TO DQN}
\label{appendix:dqn}

\begin{figure*}
	\vspace{.1in}
	\begin{center}
		\includegraphics[width=\linewidth, height=0.4\textheight]{figures/curves_synth_dqn}
		\caption{Exploration rate over gradient steps for the six procedurally generated data sets.}
		\label{fig:curves-synth-dqn}
	\end{center}

\end{figure*}

We originally tried using standard RL algorithms but found them to be unstable compared to DFP. In Figure~\ref{fig:curves-synth-dqn}, we additionally show the test exploration rate of a DQN \citep{mnih2015human} during training on the procedurally generated data sets. The curves show mean and standard deviation over 5 random seeds. Except for the original path length reward function (PL), described in the paper, we also tried using the exploration rate difference between two time steps (ER). In both cases the DQN had access to the NN feature. We can see that in 3 out of 6 data sets, the DQN struggles and degrades to solutions much worse than those found by NOGE.

\subsubsection*{\bibname}}

\usepackage{hyperref}
\usepackage{booktabs}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{wrapfig}

\include{defs}

\begin{document}

\twocolumn[

\aistatstitle{Neural Online Graph Exploration}

\aistatsauthor{ Ioannis Chiotellis \And Daniel Cremers}

\aistatsaddress{ Technical University of Munich \And  Technical University of Munich }
\vspace{-.76cm}
\aistatsaddress{ john.chiotellis@tum.de \And cremers@tum.de}
]

\begin{abstract}
Can we \emph{learn} how to explore unknown spaces efficiently? To answer this question, we study the problem of Online Graph Exploration, the online version of the Traveling Salesperson Problem. We reformulate graph exploration as a reinforcement learning problem and apply Direct Future Prediction~\citep{dosovitskiy2016learning} to solve it. As the graph is discovered online, the corresponding Markov Decision Process entails a dynamic state space, namely the observable graph and a dynamic action space, namely the nodes forming the graph's frontier. To the best of our knowledge, this is the first attempt to solve online graph exploration in a data-driven way. We conduct experiments on six data sets of procedurally generated graphs and three real city road networks. We demonstrate that our agent can learn strategies superior to many well known graph traversal algorithms, confirming that exploration can be learned.
\end{abstract}

\section{INTRODUCTION}

In online graph exploration, an agent is immersed in a completely unknown environment. Located at a node of an unknown graph, they can only see the node's immediate neighbors. The agent moves and discovers the graph as they go. Whenever they visit a new node, all incident edges are revealed, along with their weights and their end nodes. To visit a new node, the agent has to traverse a path of known edges in the discovered graph. For each of these edges, the agent pays their weight as a cost. The goal of the agent is to visit all nodes in the graph, while paying the minimum cost.

By removing any particular geometric constraints, a large number of problems can be reduced to online graph exploration, as it basically is \textit{search} with partial information in a discrete space.
We revisit online graph exploration for undirected unweighted connected graphs. This task can be directly associated with many major problems in robotics such as planning, navigation, tracking and mapping \citep{yamauchi1997frontier}. All these subfields have been thoroughly investigated and a large number of algorithms have been devised, both classical and recently also learning-based. While path planning and navigation algorithms consider the question \textit{``How can I get from A to B the fastest?''}, exploration algorithms consider a more abstract question: \textit{``Where should I go beginning from A in order to discover the world the fastest?''}. In other words, while path planning studies \textit{how} to reach a given destination, exploration is concerned with \textit{which} destination should be reached next, a problem more akin to dynamic planning. We argue that exploration is a fundamental sequential decision making problem and it is therefore worth investigating if algorithms can \textit{learn} which destinations are worth reaching and when.

The best known exploration strategy remains a simple greedy method - the nearest neighbor algorithm (NN). However, as NN selects the nearest (in terms of shortest path distance) unexplored node, its decisions are optimal only when considering a horizon of a single decision step. Therefore, a reasonable question is whether there are algorithms that can consider a longer horizon and thus minimize the \textit{cumulative} path length, which is the true objective of exploration.

We present a learning algorithm that does exactly this. Our contributions can be summarized as follows:
\begin{itemize}
	\item reformulate online graph exploration as a reinforcement learning problem,

	\item propose a neural network that can handle the associated dynamic state and action space,

	\item show experimentally that the proposed approach solves graph exploration as fast or faster than many classical graph exploration algorithms.
\end{itemize}

\section{RELATED WORK}

The problem of graph exploration has been studied by the graph theory community for decades. A large number of works has been conducted, studying the problem for specific classes of graphs \citep{miyazaki2009online, higashikawa2014online}, with multiple collaborative agents \citep{dereniowski2013fast} or for variations of the problem with  additional information \citep{dobrev2012online} or energy constraints \citep{duncan2006optimal, das2015collaborative}. Successful exploration algorithms are often sophisticated variations of depth first search (DFS), where the algorithm has to decide when to diverge from DFS \citep{kalyanasundaram1994constructing, megow2012online}. A similar problem has been studied by \cite{deng1999exploring} for unweighted \textit{directed} graphs, where the agent has to traverse all edges instead of visiting all nodes. In this setting, the offline equivalent problem is known as the Chinese Postman Problem (CPP) \citep{guan1962graphic} which is solvable in polynomial time. In contrast, the offline equivalent of Online Graph Exploration is the Traveling Salesperson Problem, an NP-hard problem.

Besides the large volume of research, for general graphs, the best known exploration algorithm remains a simple greedy method - the nearest neighbor algorithm (NN). The trajectories followed by NN are provably at most $O(\log n)$\footnote{where $n$ is the number of nodes} longer than the optimal ones \citep{rosenkrantz1977analysis}.

\begin{figure}[h]
	\vspace{.3in}
	\includegraphics[width=\linewidth]{figures/teaser_graph}
	\vspace{-.1in}
	\caption{A graph exploration agent (\textbf{red}) keeps track of the nodes already visited (\textbf{blue}) and the \textit{frontier} nodes that could be visited next (\textbf{green}). The frontier nodes form the boundary between known and unknown (\textbf{white}) space. The goal is to discover and visit all nodes as fast as possible.}
	\label{fig:teaser}
\end{figure}

However, to the best of our knowledge, it has not been attempted to solve graph exploration in a data-driven way. In this work, we investigate whether, given a training set of graphs, a learning algorithm is able to find good exploration strategies that are competitive or even superior to traditional methods. Recently, there has been growing interest in applying learning to combinatorial optimization problems. In the work of \cite{vinyals2015pointer}, three problems were studied and solved by learning to ``point'' to elements of a set with a neural network. Among these problems was the Traveling Salesperson Problem, which can be thought of as the offline equivalent to graph exploration. \cite{vinyals2015pointer} proposed a recurrent neural network (RNN) architecture, called Pointer Network, based on the attention mechanism introduced by \cite{bahdanau2015neural}.
However, using an RNN might introduce a bias due to the ordering of the elements in the input sequence. To alleviate this bias, several works have studied neural architectures that can preserve the permutation-invariance property of sets \citep{edwards2016towards,zaheer2017deep, lee2018set}. Moreover, in recent years, Graph Neural Networks (GNNs) \citep{battaglia2018relational} have emerged. These neural networks consider not just sets of nodes but also their pairwise connections or relationships as inputs and can learn how to solve problems such as node classification \citep{kipf2016semi} and link prediction \citep{zhang2018link}. Further, methods such as DeepWalk \citep{perozzi2014deepwalk} and node2vec \citep{grover2016node2vec} have been used to learn node embeddings in an unsupervised way, borrowing ideas from natural language processing \citep{mikolov2013distributed}. These methods make an implicit assumption that nodes that co-appear in a random walk on the graph are more similar than nodes that don't.
Nevertheless, it remains a challenge to learn node embeddings for dynamic graphs that are changing while an algorithm makes decisions about the graph's structure.

Close to our work is the work of \cite{dai2019learning} which studies exploration on environments with graph-structured state-spaces, such as software testing. In contrast to \citep{dai2019learning}, we study the original problem as defined by the graph theory community which prohibits the revisiting of past nodes. This allows us to study the problem in isolation, without the interference of other tasks such as visual feature learning and the perceptual aliasing problem.

\section{FORMULATION}
\label{sec:formulation}

\begin{figure*}[t!]

	\begin{center}
		\includegraphics[width=\textwidth]{figures/pomdp_memory2}
		\caption{The task of a graph exploring agent is to select the frontier node $v_{t+1} \in F_t$ to visit next. Once the node is visited, the environment reveals a new set of nodes $\Delta V_{t+1}$ and edges $\Delta E_{t+1}$, expanding the agent's knowledge to the graph $G_{t+1} = (V_{t+1}, E_{t+1})$. The distance traveled by the agent from $v_{t}$ to $v_{t+1}$ is paid as a negative reward $r_{t+1}$. The agent acts upon an integrated observation $\mathbf{x}_{t+1}$ retrieved from its memory. The subset of nodes that have been discovered but are not yet visited are labeled as the frontier $F_{t+1}$.}
		\label{fig:mdp_reduced}
	\end{center}
	\vskip -0.2in
\end{figure*}

\subsection{Graph Exploration Overview}
\label{sec:oge-as-rl}
An agent explores a connected unweighted graph $G=(V, E)$. At time step $t=0$, they start at an arbitrary node $v_0 \in V$ and they can only observe an initial \textit{map} $G_0 = (V_0, E_0)$ comprised of the neighbors and incident edges of $v_0$. We assume the agent has a memory where it can store and integrate observations. Therefore, at any time step $t$, the agent observes a subgraph $G_t = (V_t, E_t)$ with a subset of visited nodes $C_t$ and a subset of frontier nodes $F_t$ that are to be explored.
Being at node $v_t \in C_t$, the agent has to choose a node $v_{t+1} \in F_t$ to visit next. Once a decision is made, the agent follows a path from $v_t$ to $v_{t+1}$ of length $l_{t+1} = d_{G_t}(v_t, v_{t+1})$. Note that this is a shortest path in $G_t$ but not necessarily in $G$\footnote{In the rest of the paper, we omit $G_t$ and use the shorter notation $d(v_t, v_{t+1})$ wherever possible.}. The new node $v_{t+1}$ gets removed from the frontier and becomes part of the set of visited nodes: $C_{t+1} \leftarrow C_t \cup \{v_{t+1}\}$. Finally, the agent observes the neighbors $N(v_{t+1})$ of $v_{t+1}$ and the frontier gets expanded by the subset of neighbors that have not been observed in the past:
\begin{equation}
F_{t+1} \leftarrow F_t \cup N(v_{t+1}) \setminus C_{t+1}.
\end{equation}

The goal is to visit the nodes in such an \textit{order} that the total path length is minimized. Notice that we use a different timescale than commonly used \textit{e.g. } in navigation problems. In a single time step, the exploration agent can traverse a path of arbitrary length in the known graph $G_t$.
The differences between exploration algorithms lie in the way they choose the node $v \in F_t$ to visit next. For instance, DFS considers the order of entry in the frontier and chooses the most recently entered node. The nearest neighbor algorithm (NN) chooses the node closest to the current node $v_t \in C_t$:
\begin{equation}
v_{t+1}^{NN} = \argmin_{v \in F_t} d(v_t, v)
\end{equation}

However, since the NN selection rule is greedy, it might be suboptimal. Namely, an algorithm $A$ could exist that takes into account the \textit{expected} future path lengths and could therefore make better decisions:
\begin{equation}
v_{t+1}^A = \argmin_{v \in F_t} \mathbb{E}[d(v_t, v) + \sum_{i=t+1}^{\infty} d(v_i, v_{i+1})].
\end{equation}

This formulation is reminiscent of reinforcement learning (RL). In RL an agent in a state $s_t$ and following a policy $\pi$, chooses action $a_t = \pi(s_t)$ and receives an immediate reward $r_{t+1}$. The true objective of the agent is to maximize the cumulative reward:
\begin{equation}
\label{eq:fixed_action_space}
a_t = \argmax_{a \in \mathcal{A}} \mathbb{E}[r_{t+1} + \sum_{i=t+1}^{\infty} \gamma^{i-t} r_{i+1} | \pi, a],
\end{equation}

where $\gamma \in [0, 1]$ is a discount factor that weighs distant future rewards less than imminent rewards. The expectation of cumulative rewards is also known as the action value $Q^\pi(s_t, a_t)$. Notice that the NN algorithm can be exactly recovered for $\gamma = 0$.

\subsection{Markov Decision Process}
\label{sec:mdp}
RL problems are formally described as Markov Decision Processes (MDPs). An MDP is defined as a 5-tuple $(\mathcal{S}, \mathcal{A}, p, r, \gamma)$, namely a state space $\mathcal{S}$, an action space $\mathcal{A}$, a state transition probability function $p: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \mapsto [0, 1]$, a reward function $r: \mathcal{S} \times \mathcal{A}\mapsto \mathbb{R}$ and a discount factor $\gamma  \in [0, 1]$. A partially observable Markov decision process (POMDP) is a generalization of a MDP, where the agent cannot directly observe the state $s_t \in \mathcal{S}$ but has partial information through observations $o_t \in \mathcal{O}$. An agent with a memory component can integrate partial observations to cumulative observations $\mathbf{x}_t \in \mathcal{X}$. Notice that the observation space $\mathcal{X}$ is a subset of the state space $\mathcal{S}$. Thus, we refer to the setting of Online Graph Exploration as a memory-augmented POMDP. In Figure~\ref{fig:mdp_reduced}, we illustrate this setting. In the following, we describe the components of this MDP.

\paragraph{State Space}
Let $\mathcal{G}$ be the set of all conceivable graphs, and let $\mathcal{P}_G$ denote the set of all conceivable visit orderings $P_G$ for a graph $G\in\mathcal{G}$.  Then the state space $\mathcal{S}$ is defined as the set of all pairs $(G, P_G)$ of graphs $G\in\mathcal{G}$ and associated visit orderings $P_G\in\mathcal{P}_G$:

\paragraph{Observation Space}
At each time step, the environment reveals the neighborhood of the visited node. Therefore, the observation space is exactly the subset of graphs that are star graphs.

\paragraph{Action Space}
It is common in RL problems with discrete action spaces, for the agent to have access to a fixed set of actions $\mathcal{A}$ as in Eq.~\eqref{eq:fixed_action_space}. Instead, in graph exploration, a new unique action set $\mathcal{A}_t$ is induced from the state at each time step. This action set corresponds to the nodes that have been observed but not visited yet, namely the nodes in the frontier:
\begin{equation}
\mathcal{A}_t = F_t.
\end{equation}
The general action space can be described by the power set of all nodes: $\mathcal{A} = 2^\mathcal{V}$.
Note that the frontier can be derived from the known graph $G_t=(V_t, E_t)$
and the path $P_t$ as $F_t = V_t \setminus C_t$, where $C_t$ denotes the \textit{set} of visited nodes found in the sequence $P_t$.

\paragraph{Reward Function}
As defined in section \ref{sec:oge-as-rl}, the rewards correspond to negative geodesic distances. Therefore, assuming unweighted graphs, all rewards are strictly negative:
\begin{equation}
r(s_t, a_t) = -d(v_t, v_{t+1}) < 0.
\end{equation}

\paragraph{State Transition Function}
Let $v_{t+1}$ be the node to visit next. Then, if $s_t = (G, P_t)$ is the state described by the graph $G$ and the path $P_t$, the new state is described by the same graph $G$ and the extended path $P_{t+1} \leftarrow P_{t} \; || \; v_{t+1}$\footnote{By $||$ we denote concatenation of a sequence with a new element.}.

\paragraph{Memory Update}
Upon observing $\Delta V_{t+1} = N(v_{t+1})$, namely the neighbors of $v_{t+1}$, and $\Delta E_{t+1} = E(v_{t+1})$, the edges from $v_{t+1}$ to $N(v_{t+1})$, the agent's memory is updated as:
\begin{align}
V_{t+1} &\leftarrow V_t \cup \Delta V_{t+1} \\
E_{t+1} &\leftarrow E_t \cup \Delta E_{t+1} \\
P_{t+1} &\leftarrow P_{t} \; || \; v_{t+1} \\
C_{t+1} &\leftarrow C_t \cup \{v_{t+1}\}\\
F_{t+1} &\leftarrow F_t \cup \Delta V_{t+1} \setminus C_{t+1}.
\end{align}

\section{METHODOLOGY}
\label{sec:methodology}
\subsection{Predicting the Future Path Lengths}
Our premise is that a learning agent can perform better than traditional exploration algorithms, as long as they can predict the future distances to be traveled. Inspired by the framework introduced by \cite{dosovitskiy2016learning}, we use Direct Future Prediction (DFP) to learn a predictor of future path lengths. Confirming the authors' observations, we found that reducing policy learning to a supervised regression problem makes training faster and more stable. In particular, at time $t$, we aim to predict the vector
\begin{equation}
\mathbf{y}_t = (\mathbf{m}_{t+\tau_1} - \mathbf{m}_t, \mathbf{m}_{t+\tau_2} - \mathbf{m}_t, \dots, \mathbf{m}_{t+\tau_M} -\mathbf{m}_t),
\end{equation}

where $\mathbf{m}_t$ is a low-dimensional measurement vector augmenting the agent's high-dimensional observation $\mathbf{x}_t$, and $\{\tau_j\}_{j=1}^M$ are temporal offsets. Following \cite{dosovitskiy2016learning}, we choose exponential offsets $\tau_j = 2^{j-1}$. We could directly use a scalar measurement $L_t = \sum_{i=0}^{t} l_i$, namely the cumulative path length up to time $t$. However, there are several disadvantages with this choice. For unweighted graphs, we know that any \textit{one-step} path length $l_t$ lies in the range $[1, N_{max}-1]$, where $N_{max}$ is the maximum number of nodes we are considering. Thus, directly predicting path lengths would limit our ability to generalize to graphs larger than our training graphs.
Second, the distribution of path lengths naturally grows over time together with the observable graph's diameter. To avoid these problems, instead of minimizing path lengths, we maximize the agent's exploration rate $u_t = \frac{|C_t|}{L_t} = \frac{t}{L_t}$ which always lies in the $[0, 1]$ interval and thus the entries of $\mathbf{y}$ always lie in $[-1, 1]$. At test time, we choose the node to visit next by simply taking the $\argmax$:
\begin{equation}
v_{t+1} = \argmax_{v \in F_t} \mathbf{g}^\top \mathbf{f}_{\theta} (\mathbf{x}_t, \mathbf{m}_t, v),
\end{equation}

where $\mathbf{f}_{\theta}$ is our parameterized predictor network, $\mathbf{x}_t=(V_t, E_t, X_t)$ is the observable graph with node features $X_t$ and $\mathbf{g}$ is a goal vector expressing how much we care about different future horizons.
Another advantage of using DFP instead of RL is that, given information about the remaining time available, we can directly incorporate it in the goal vector, both at training and at test time without the need of retraining the network. In contrast to \cite{dosovitskiy2016learning}, we don't use $\mathbf{g}$ as an input to the network~\footnote{We found that adding a goal module does not improve and some times even hurts performance.}, but only as a weighting of the predictions to obtain a policy.

\begin{figure*}[t!]

	\begin{center}
		\includegraphics[width=\linewidth, height=.33\textheight]{figures/network_noge_dfp}
		\caption{The proposed neural network architecture for online graph exploration.}
		\label{fig:dots_net}
	\end{center}
	\vskip -0.2in
\end{figure*}

\subsection{Network Architecture}
\label{sec:implementation}

In Figure~\ref{fig:dots_net} we show our network architecture. We first obtain node embeddings $Z_F$, $Z_C$ and $z_{v_t}$ by passing the observable graph $\mathbf{x}_t=(V_t, E_t, X_t)$ through a graph neural network (GNN). The embeddings correspond to the node subsets $F_t$, $C_t$ and the current node $v_t$. We use a standard graph convolutional network (GCN) \citep{kipf2016semi}, but any graph neural network that produces node embeddings can be used. We then aggregate the node embeddings $Z_C$ of the visited set to obtain a subgraph embedding $\bar{z}_{C}$. Even though more sophisticated pooling methods (\textit{e.g. } attention~\citep{velivckovic2017graph}) may be used, we use simple mean pooling.

We pass $\mathbf{m}_t$ through a multi-layer Perceptron (MLP) to obtain a measurement embedding $z_m$. The vectors $\bar{z}_C$, $z_{v_t}$ and $z_m$ are concatenated to form a \emph{context} vector $z_{ctx}$. Each frontier node embedding $z_F(v) \in Z_F$ is concatenated with $z_{ctx}$, resulting in a set of state-action encodings $\phi(\mathbf{x}_t, \mathbf{m}_t, v)$, one for each node $v \in F_t$. Finally we pass these encodings through a row-wise feed-forward network (another MLP) to obtain a prediction vector $\mathbf{f}(\mathbf{x}_t, \mathbf{m}_t, v)$ for each node $v \in F_t$. The state-action value $Q(\mathbf{x}_t, \mathbf{m}_t, v, \mathbf{g})$ of each node in the frontier can be obtained by multiplying the associated prediction vector $\mathbf{f}(\mathbf{x}_t, \mathbf{m}_t, v)$ with the goal vector $\mathbf{g}$.

\subsection{Input Features}
\label{sec:input-features}

Solving online graph exploration as a learning problem depends critically on what the learning algorithm ``sees'' as input. The state $s_t$ consists of the known graph $G_t$ and the path $P_t$. Therefore, we have to decide on the nodes and perhaps also edge input features of the graph $G_t$. Second, we have to consider a representation of the path $P_t$.

We used categorical node features indicating if a node belongs to the visited set $C_t$, the frontier set $F_t$ or if it is the current node $v_t$:
\begin{equation}
x(v_i) = [\mathbf{1}(v_i \in C_t), \mathbf{1}(v_i \in F_t), \mathbf{1}(v_i = v_t)].
\end{equation}

Note that a categorical node feature space can incorporate many classical graph traversal algorithms (\textit{e.g. } BFS, DFS and NN) as special cases by simply adding a binary channel that indicates the node that would be selected by the respective algorithm. Furthermore, this representation allows the learning algorithm to potentially learn a \textit{hyper-policy} \citep{precup1998theoretical} by combining greedy algorithms in novel ways.

In preliminary experiments, we investigated ways to utilize the order of visit of the nodes, $P_t$, by using positional encodings \citep{vaswani2017attention} as continuous node features. We found that these features degraded the agent's performance both when used on their own and when combined with the categorical features.

\subsection{Training}
In Algorithm~\ref{alg:noge-training} we describe our training procedure. In each episode, we randomly sample a graph from the training set and then randomly set one of its nodes as source. This virtually increases the training set size from the number of training graphs $|\mathcal{G}_{train}|$ to the total number of nodes in all training graphs $\sum_{G \in \mathcal{G}_{train}} |V_G|$, where by $V_G$ we denote the vertices of graph $G$.

\begin{algorithm}[t!]
	\caption{Training \text{\Method}}
	\label{alg:noge-training}
	\begin{algorithmic}[1]
		\STATE {\bfseries Input:} network $\mathbf{f}_{\theta}$, training set of graphs $\mathcal{G}_{train}$, time limit $T_{max}$, goal vector $\mathbf{g}$, minibatch size B.
		\STATE {\bfseries Output:} trained network $\mathbf{f}_{\theta}$.
		\STATE Initialize $\theta$ randomly.
		\STATE Initialize an experience replay buffer $\mathcal{R}$.
		\WHILE{\emph{training}}
		\STATE Sample a graph $G=(V, E) \sim \mathcal{G}_{train}$.
		\STATE Sample a source node $v_0 \sim V$.
		\STATE Explore $G$
		using $\mathbf{f}_{\theta}$,  $\mathbf{g}$ and $\epsilon$-greedy policy for up to $T_{max}$ episode steps.  \\
		\STATE Store $G_T$ and the followed path $P_T$ in $\mathcal{R}$.
		\STATE Sample a minibatch $\{G_t^{(i)}, P_t^{(i)}\}_{i=1}^B$ from $\mathcal{R}$.
		\STATE Reconstruct tuples $\{\mathbf{x}_t^{(i)}, \mathbf{m}_t^{(i)}, v_{t+1}^{(i)}, \mathbf{y}_t^{(i)}\}_{i=1}^B$.
		\STATE Train $\mathbf{f}_{\theta}$ with the minibatch, using Adam \citep{kingma2014adam} to minimize the mean squared error:\\
		$L(\theta) = \frac{1}{B} \sum_{i=1}^{B} || \mathbf{y}_t^{(i)} - \mathbf{f}_{\theta}(\mathbf{x}_t^{(i)}, \mathbf{m}_t^{(i)}, v_{t+1}^{(i)})||^2$.
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}

\section{EXPERIMENTS}
\label{sec:results}

The complete set of hyperparameters used is reported in Appendix~\ref{appendix:impl} and our full source code is available at \url{https://github.com/johny-c/noge}.

\subsection{Evaluation Protocol}
We evaluate our algorithm - \text{\Method} (Neural Online Graph Exploration) on data sets of generated and real networks. In addition to the basic version of our algorithm, we  evaluate NOGE with an extra node feature, indicating the nearest neighbor, as described in section~\ref{sec:input-features}. We call this variant NOGE-NN. We use three well known graph exploration algorithms as baselines: Breadth First Search (BFS), Depth First Search (DFS) and Nearest Neighbor (NN). We note that these heuristics do not need any training. For completeness, we also report a random exploration baseline (RANDOM). We compare the algorithms in terms of the \textit{exploration rate} $u_T$, namely the number of visited nodes over the total path length at the end of episodes:

\begin{equation}
u_T = \frac{|C_T|}{|P_T|} = \frac{T}{\sum_{i=0}^{T} l_i}.
\end{equation}

For the test sets we fix a set of source nodes per graph, to compare all methods given the exact same initial conditions. The metrics reported are computed on the test sets after either all nodes have been explored or when a fixed number of $T_{max}=500$ exploration steps has been reached. For all experiments we report mean and standard deviation over 5 random seeds.

\subsection{Procedurally Generated Graphs}
\label{experiment:synth}

We first examine six classes of procedurally generated graphs (Figure~\ref{fig:data_synth}). We used the \textit{networkx} library (\url{https://github.com/networkx/networkx}) to generate a diverse (in terms of size and connectivity) set of graphs for each class. In Table~\ref{tbl:data-synth-stats} we report basic statistics describing the size and connectivity of the graphs. We split each data set in a training (80\%) and test set (20\%) of graphs. For some of these data sets, an optimal strategy is known. For instance, DFS explores trees optimally by traversing each edge two times - once to explore and once to backtrack. Thus its exploration rate is approximately $0.5$. It is worthwhile examining if \text{\Method} can find this optimal strategy.

In Figure~\ref{fig:curves-synth} we show the test performance of NOGE over 25600 training steps.  In Table~\ref{tbl:synth-final-results} we report the final performance of the algorithms compared to the baselines. NOGE is able to outperform other methods on grids and the caveman data set and find the optimal strategy on trees. Somewhat surprisingly the NN feature seems to only help on the maze and tree data sets. Note that in ladder and tree, DFS's line is hidden as its performance matches that of NN.

\begin{table}[h!]
	\caption{Basic statistics of the procedurally generated data sets (tr: training set, te: test set).}
			\vspace{-.1in}
	\begin{center}
		\input{tables/synth_data_stats.tex}
	\end{center}
	\label{tbl:data-synth-stats}
\end{table}

\begin{table}[b!]
	\caption{Basic statistics of the city road network data sets (tr: training set, te: test set).}
	\vspace{-.1in}
	\begin{center}
		\input{tables/real_data_stats.tex}
	\end{center}
	\label{tbl:data-real-stats}
\end{table}

\begin{table*}[t!]
	\caption{Final exploration rate: Mean and standard deviation on the generated data sets.}
	\vspace{-.15in}
	\begin{center}
		\small
		\input{tables/synth_results.tex}
	\end{center}
	\label{tbl:synth-final-results}
\end{table*}

\begin{figure*}[h!]
	\vspace{.1in}
	\begin{center}
		\includegraphics[width=\linewidth, height=0.4\textheight]{figures/curves_synth}
			\caption{Exploration rate over gradient steps for the six procedurally generated data sets.}
			\label{fig:curves-synth}
	\end{center}
\end{figure*}

\subsection{City Road Networks}
\label{experiment:real}
\vspace{-.15cm}
To examine its capabilities, we also evaluate \text{\Method},  on three real road networks. We use openly available drivable road networks from OpenStreetMap \citep{haklay2008openstreetmap}. We explore three cities with diverse networks: Munich (MUC), Oxford (OXF) and San Francisco (SFO), shown in Figure \ref{fig:data-real}.

In Table~\ref{tbl:data-real-stats}, we show basic statistics for these data sets. We constructed a training set and test set for each city by cutting each graph in two components and removing any edges connecting them. The cut was defined by the diagonal of each city's 2D bounding box. The larger component (approx. 60\% of the nodes) was used for training and the smaller one for testing.

In Figure~\ref{fig:curves-real} we show the test performance of NOGE over 40000 training steps and in Table~\ref{tbl:real-final-results} we report the final performance. Nearest Neighbor performs clearly better in San Francisco and Munich. NOGE-NN is able to match and surpass DFS, as the second best method. In Oxford, NOGE-NN is within a standard deviation from the best performance by NN. In these graphs the NN feature clearly improves performance.

\begin{table*}[t!]
	\caption{Final exploration rate: Mean and standard deviation on the city road networks data sets.}
		\vspace{-.1in}
	\begin{center}
		\small
		\input{tables/real_results.tex}
	\end{center}
	\label{tbl:real-final-results}
\end{table*}

\begin{figure*}[h!]
	\begin{center}
		\includegraphics[width=\linewidth, height=0.25\textheight]{figures/curves_real}
			\caption{Exploration rate over gradient steps for the city road networks data sets.}

		\label{fig:curves-real}
	\end{center}
	\vspace{-.1in}

\end{figure*}

\begin{figure*}[h!]
		\vskip -0.1in
	\begin{center}
		\includegraphics[height=0.31\textheight]{figures/datasets_synthetic}
		\caption{Samples from the procedurally generated data sets used in the experiments of Section~\ref{experiment:synth}.}
		\label{fig:data_synth}
	\end{center}
	\vskip -0.2in
\end{figure*}

\begin{figure*}[h!]

	\begin{subfigure}{0.32\linewidth}
		\includegraphics[height=.16\textheight]{figures/Munich500}
		\caption{Munich}
		\label{fig:muc}
	\end{subfigure}
	\begin{subfigure}{0.32\linewidth}
		\includegraphics[height=.16\textheight]{figures/Oxford500}
		\caption{Oxford}
		\label{fig:oxf}
	\end{subfigure}
	\begin{subfigure}{0.32\linewidth}
		\includegraphics[height=.16\textheight]{figures/SanFrancisco500}
		\caption{San Francisco}
		\label{fig:sfo}
	\end{subfigure}

	\caption{The road city networks used for the experiments in Section~\ref{experiment:real}.}
	\label{fig:data-real}
\end{figure*}

\section{CONCLUSION}
\label{sec:conclusion}

In this work, we presented \text{\Method}, a learning-based algorithm for exploring graphs online. First, we formulated an appropriate memory-augmented Markov Decision Process. Second, we proposed a neural architecture that can handle the growing graph as input and the dynamic frontier as output. Third, we devised a node feature space that can represent greedy methods as \emph{options}~\citep{precup1998theoretical}. Finally, we showed experimentally that \text{\Method} is competitive to well known classical graph exploration algorithms in terms of the exploration rate of unseen graphs.

\nocite{mnih2015human}
\newpage
\bibliographystyle{apalike}