\subsubsection*{\bibname}}


\usepackage[english]{babel}
\addto{\captionsenglish}{%
  \renewcommand{\bibname}{References}
}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[noend]{algpseudocode}
\usepackage{fancyhdr,amssymb}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{array}
\usepackage{stmaryrd}
\usepackage{amsfonts}


\usepackage{amsfonts,amsmath,amssymb,amsthm,epsfig,psfrag}
\usepackage[T1]{fontenc}
\usepackage{babel}

\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{dsfont}
\usepackage{systeme}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage{blindtext}
\usepackage{enumitem}
\usepackage{xcolor}

\newcommand{\cmmnt}[1]{}

\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
\newcolumntype{N}{@{}m{0pt}@{}}

\setlist[description]{leftmargin=\parindent,labelindent=\parindent}

\begin{document}

\maketitle

\begin{abstract}
    We address the problem of graph classification based only on structural information. Inspired by natural language processing techniques (NLP), our model sequentially embeds information to estimate class membership probabilities. Besides, we experiment with NLP-like variational regularization techniques, making the model predict the next node in the sequence as it reads it. We experimentally show that our model achieves state-of-the-art classification results on several standard molecular datasets. Finally, we perform a qualitative analysis and give some insights on whether the node prediction helps the model better classify graphs.
    
\end{abstract}

\section{Introduction}

Many natural or synthetic systems have a natural graph representation where entities are described through their mutual connections: chemical compounds, social or biological networks, for example. Therefore, automatic mining of such structures is useful in a variety of applications.

Graph classification raises several difficulties to leverage standard machine learning algorithms. Indeed, most of these algorithms take vectors of fixed size as inputs. In the case of graphs, usual representations such as edge list or adjacency matrix do not match this constraint. The size of the representations is graph dependent (number of edges in the first case, number of nodes squared in the second) and these representations are index dependent: up to indexing of its nodes, a same graph admits several equivalent representations. In a classification task, the label of a graph is independent from the indices of its nodes, so the model used for prediction should be invariant to node ordering as well. Handling discrete inputs with variable size and ordering is a well known problem in natural language processing (NLP). This is why we adapt NLP techniques to tackle graph classification.

In this paper, we propose a method to sequentially embed graph information in order to perform classification. By construction, this recurrent graph classifier overcomes the common difficulties listed above. Besides, we propose to use an additional node prediction block to help the model to capture the intrinsic structure of the graphs. The complete model is denoted \textit{variational recurrent graph classifier} (VRGC). Experiments show that this leads to better classification results for larger datasets. For clarity of the contribution of our work, we use neither node attributes nor edge attributes.

Related works use either graph kernels \citep{nikolentzos2017kernel, nikolentzos2017matching, nikolentzos2018degeneracy, neumann2016propagation, shervashidze2011weisfeiler, yanardag2015deep}, sequential methods \citep{callut2008classification, xu2012protein, jin2018learning, you2018graphrnn} or graph features \citep{barnett2016feature, DBLP:journals/corr/NarayananCVCLJ17, gomez2017dynamics, dutta2017high}.


\section{Model}
\label{sec:model}

We propose to use a sequential approach to embed graphs with a variable number of nodes and edges into a vector space of a chosen dimension. This latent representation is then used for classification. Node index invariance is approximated through specific pre-processing and aggregation.

Let $G=(V, E)$ be an undirected and unweighted graph with $V$ a set of nodes and $E$ a set of edges. The graph $G$ can be represented, modulo any permutation $\pi$ over its nodes $\{n_i\}_{i=1}^{|V|}$, by its boolean adjacency matrix $A^{\pi}$ such that $A^{\pi}_{ij} = 1$ if nodes indexed by $i$ and $j$ are connected in the graph and $A^{\pi}_{ij} = 0$ otherwise. We use this adjacency matrix as a raw representation of the graph. 

Our VRGC is composed of three main parts: node ordering and embedding, classification and regularization with variational auto-regression (VAR). See Figure \ref{fig:macro} for an illustration.


\begin{figure*}
    \centering
    \includegraphics[width=1\textwidth]{archi_macro.png}
    \caption{Macroscopic representation of VRGC.}
    \label{fig:macro}
\end{figure*}



\paragraph{Node ordering and embedding}
\label{subsec:node ordering}

Before being processed by the neural network, the adjacency matrix of a graph is transformed on-the-fly \citep{you2018graphrnn}. First, a node is selected at random and used as root for a breadth first search (BFS) over the graph. The rows and columns of the adjacency matrix are then reordered according to the sequence of nodes returned by the BFS. Next, each row $i$ (corresponding to the $i^{th}$ node in the BFS ordering) is truncated to keep only the connections of node $n_{i}$ with the $\min(i, d)$ nodes that preceded in the BFS. This way, each node is $d$-dimensional, and each truncated matrix is zero-padded in order to have dimensions $(|V|_{max}, d_n)$. Throughout the rest of the paper, we use the notation $n_G$ for $|V|_{max}$. 

After node ordering and pre-embedding, each graph is processed as a sequence of $d$-dimensional nodes by a gated recurrent unit (GRU) neural network \citep{cho2014learning}. The GRU is a special RNN able to learn long term dependencies by solving vanishing gradient effect\footnote{The choice of GRU over Long Short Term Memory networks is arbitrary as they have equivalent long-term modeling power \citep{chung2014empirical}.}. In order to help the recurrent network training, we propose to add a simple fully connected network between pre-embedding and recurrent embedding. Therefore, the node will be presented to the GRU in the shape of continuous vectors instead of binary adjacency vectors. 

Finally the GRU sequentially embeds each node $n_i$ by using $n_{i-1}$ and information contained in a memory cell $h_{i-1}$ that theoretically embeds all previously seen information. The embedded node sequence $\{h_i\}_{i=1}^{n_G}$ then feeds both the VAR and the classifier as discussed in subsequent sections. See top line of Figure \ref{fig:archi}.

\paragraph{Classification}
\label{subsec:classification}

After the embedding step, we use an additional GRU dedicated to classification that takes $\{h_i\}_{i=1}^{n_G}$ as input.
Its last memory cell, denoted $\tilde{h}_{n_G}$, feeds a softmax multilayer perceptron (MLP) which performs class prediction.
Formally, let $c$ be the class index, the classifier is trained by minimizing the cross-entropy loss between ground-truth and $\hat{p}(G, r)$ the softmax class membership probability vector for a given graph $G$ that has been sorted by a BFS rooted with node $r$. We call this objective term $\mathcal{L}_{classif}$.
As discriminating patterns might be spread across the whole graph, the network is required to model long-term dependencies. By construction, GRUs have such ability. See middle line of Figure \ref{fig:archi}.

\paragraph{Regularization with variational auto-regression}
\label{subsec:vap}

As the structure of a graph is the concatenation of the interactions between all nodes and their respective neighbors, learning a good representation without using node attributes requires for the model to capture the structure of the graph while classifying. Accordingly, we add an auto-regression block to our model: at each node, the network makes a prediction for the next node adjacency. Multi-task learning is a powerful leverage to learn rich representation \citep{sanh2018hierarchical} in NLP. In particular, such representation for sequence classification has already been used for sentiment analysis \citep{latif2017variational, xu2017variational}.

We use a variational auto-encoder (VAE) \citep{kingma2013auto} to learn a representation of each node $n_i$ given $h_{i-1}$. The first layers of the encoder are shared with the classifier and corresponds to the graphs preprocessing (blue part in Figures \ref{fig:macro} and \ref{fig:archi}). The subsequent encoder layers, the latent sampling and the decoder constitute the VAR. For each graph $G$ with embedded nodes $\{ n_{i} \}_{i \in \llbracket 1, n_G \rrbracket}$, the fully connected variational auto-encoder takes $h\coloneqq\{ h_{i} \}_{i \in \llbracket 1, n_G-1 \rrbracket }$ as input. Let $\{ z_{i} \}_{i \in \llbracket 1, n_G \rrbracket}$ be the latent random variables for the following model 

\begin{align*}
    p(G,z|h) = p(n_1, z_1)\prod_{i=2}^{n_G}{p_\theta(n_i|z_{i})q_\phi(z_{i}|h_{i-1})}.
\end{align*} 

In practice, $p_\theta$ and $q_\phi$ are modelled by neural networks parametrized by $\theta$ and $\phi$, which require differentiable functions for training. However, $p_\theta(n_i|z_i)$ models a binary adjacency vector representing the connections between node $n_i$ and previously visited nodes $n_{j<i}$. Therefore, we use sigmoid continuous relaxation to train our model, and hard binary sampling at test time. We use a Gaussian variational posterior distribution. Training is done by maximizing the variational lower bound of the log-likelihood of the observation as in Kingma's VAE. The exact loss is displayed in Appendix \ref{app:elbo} and denoted $\mathcal{L}_{pred}$. 

The regularization part is illustrated in the bottom line of Figure \ref{fig:archi}. In the end, the model is trained by minimizing the total loss $\mathcal{L} = \mathcal{L}_{classif} + \alpha \mathcal{L}_{pred}$, where $\alpha$ is a hyper-parameter.


\begin{figure*}
    \centering
    \includegraphics[width=1\textwidth]{VRGC.png}
    \caption{Architecture for VRGC. Top: node ordering and embedding. Middle: classification. Bottom: regularization with VAR plus final aggregation. FC stands for fully-connected.}
    \label{fig:archi}
\end{figure*}

\paragraph{Aggregation of the results at test time}
\label{sub:aggreg}

The node ordering step introduces randomness to our model. On the one hand, it helps learn more general graph representations during the training phase, but on the other hand, it might produce different outputs for the same graph during the testing phase, depending on the root of the BFS. In order to counter this side effect, we add the following aggregation step for the testing phase\cmmnt{ combining a soft and a hard vote}. Each graph is processed $N$ times by the model with $N$ different roots for BFS ordering. The $N$ class membership probability vectors are extracted and averaged. The average score vector is noted $\bar{p}$ and computed as follows with an element-wise sum: 

$$
    \bar{p}(G) = \frac{1}{N} \sum_{\substack{i=1 \\ r \sim \mathcal{U}(\llbracket 1, n_G \rrbracket)}}^N {\hat{p}(G, r)}.
$$

This soft vote is repeated $K$ times resulting in $K$ probability vectors $\left\{\bar{p}_{.,k}(G)\right\}_{k=1}^K$ for each graph $G$. The final class attributed to a graph corresponds to the highest probability among the $K$ vectors.  
This second hard vote enables to choose the batch of votes for which the model is the most confident.
\begin{align*}
    \hat{c}(G) & = \arg \max_{c\in \llbracket 1,C \rrbracket} \left\{ || \bar{p}_{c, .}(G) ||_\infty \right\}
\end{align*}

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

\paragraph{Datasets and results}

We evaluated our model against four standard datasets from biology: Mutag (MT), Enzymes (EZ), Proteins Full (PF) and National Cancer Institute (NCI1) \citep{KKMMN2016}. A detailed description of each dataset in provided in Appendix \ref{app:datasets}.

We compare our results to those obtained by Earth Mover's Distance \citep{nikolentzos2017matching} (EMD), Pyramid Match \citep{nikolentzos2017matching} (PM), Feature-Based \citep{barnett2016feature} (FB), Dynamic-Based Features \citep{gomez2017dynamics} (DyF), Stochastic Graphlet Embedding \citep{dutta2017high} (SGE), Truncated Laplacian Spectrum \citep{de2018simple} (TLS) and Family of Graph Spectral Distances \citep{verma2017hunt} (FGSD). All values are directly taken from the aforementioned papers as they use a setup similar to ours. For algorithms presenting results with and without node features, we reported the results without node features. For those presenting results with several sets of hyper-parameters, we reported the results for the parameters that performed best on the largest number of datasets. Results are reported in Table \ref{tab:results}. We obtain state-of-the-art results on three out of the four datasets used for this paper and the second best result on the fourth one. 

\begin{table}
    \centering
    \renewcommand{\arraystretch}{1.2}
    \begin{tabular}{l|M{1.5cm} M{1.5cm} M{1.5cm} M{1.5cm} M{1.5cm} M{1.5cm}}
           & MT            &      EZ       & PF            & NCI1 \\
      \hline
      EMD  & 86.1          &     36.8      & -             & 72.7 \\
      PM   & 85.6          &     28.2      & -             & 69.7 \\
      FB   & 84.7          &     29.0      & 70.0          & 62.9 \\
      DyF  & 86.3          &     26.6      & 73.1          & 66.6 \\
      SGE  & 87.3          &     40.7      & 71.9          & - \\
      TLS  & 88.4          &     43.7      & 73.6          & 75.2 \\
      FGSD & \textbf{92.1} &     -         & 73.4          & 79.8 \\
      \hline
      RGC  & 89.5          & \textbf{48.7} & 72.5          & 78.1 \\
      VRGC & 86.3          & 48.4          & \textbf{74.8} & \textbf{80.7} \\
      \end{tabular}
  \caption{Experimental results of different models plus our own on four standard molecular datasets. RGC stands for recurrent graph classifier, VRGC for variational RGC. All other acronyms are defined in section \ref{sec:experiments}.}
  \label{tab:results}
\end{table}



\paragraph{Node indexing invariance}
Our model is designed to be independent from node ordering of the graph with respect to different BFS roots. Inputs representing the same graph (up to node ordering) should be close from one another in the latent embedding space. As the preprocessing is performed on each graph at each epoch, a same graph is processed many times by the model during training with different embeddings. This creates a natural regularization for the network. Indeed, as illustrated in Figure \ref{fig:projection}, the projections corresponding to the same graphs form a heap in the low dimensional representation of the latent space.


\paragraph{Contribution of the VAR to classification}
The variational regularization term seems to help the model finding a more meaningful latent representation for classification while graph dataset becomes larger. Note that the extra cost of training the VAR is marginal with respect to the training of the RNNs. We provide an illustration of the output of VAR block in Figure \ref{fig:reconstructions}.

\paragraph{Conclusion and room for improvement}
This paper proposed a recurrent graph classifier with variational regularization. The invariance to node indexing is greedy learned from numerous iterations on randomly rooted BFS-ordered graph. For future work, we should investigate the impact VAR capacity (number and size of hidden layers) on classification accuracy or generalization.


\paragraph{Acknowledgments} We would like to thank Thomas Bonald and Sebastien Razakarivony for their comments and help. We also would like to thank NVIDIA and its GPU Grant Program for providing the hardware we used in our experiments. This work is supported by the company Safran through the CIFRE convention 2017/1317. 



\bibliographystyle{abbrvnat}

