\section{Acknowledgements}
This research was partially supported by the German Federal Ministry of Education and Research through the project DEEPLEE (01IW17001). We would also like to thank the anonymous reviewers for their feedback on the paper and Arne Binder for his feedback on the code base.

\section{Conclusions}
We presented layerwise relevance visualization in convolutional text graph classifiers. We demonstrated that our approach allows to track, visualize and inspect visible as well as hidden state dynamics. We conducted qualitative and quantitative experiments to validate the proposed method.

This is a focused contribution; further research should be conducted to test the approach in other domains and on other data sets. Future versions should also exploit LRP's ability to expose negative evidence and the method could be extended to node classifiers.
\section{Experiments}
\label{sec:experiments}
Our experiments are publicly available: \url{https://github.com/DFKI-NLP/lrv/}. We trained a GCN sentence classifier on a 20k subset of the PubMed 200k RCT dataset  \cite{dernoncourt2017pubmed}. The dataset contains scientific abstracts in which each sentence is annotated with either of the 5 labels \textit{BACKGROUND}, \textit{OBJECTIVE}, \textit{METHOD}, \textit{RESULT}, or \textit{CONCLUSION}. \citet{dernoncourt2017pubmed} describe the task as a sequential classification task since all sentences in one abstract are classified in sequence, but we treat it as a conventional sentence classification task, classifying each sentence in isolation.

In a preprocessing step, we used ScispaCy \cite{Neumann2019ScispaCyFA} for tokenization and dependency parsing to generate the input graphs for the GCN sentence classifier. For the node embeddings in the dependency graph, we utilized pre-trained fastText embeddings \cite{mikolov2018advances}. Edge type information was discarded.

Our classifier, implemented and trained using PyTorch \cite{paszke2017automatic}, consists of two stacked GCN layers (Eq.~\ref{eq:xgcnforward}), followed by a max-pooling operation and a subsequent FC layer. All layers were trained without bias and optimized with the Adam optimizer \cite{kingma2014adam}. After each optimization step we clamped the negative weights of the last FC layer to avoid negative outputs.

During training, we batched inputs, but in the post-hoc explanation phase, single graphs from the test set were forwarded through the network to implement the strategy outlined in Sec.~\ref{sec:lrv}. We first constructed the adjacency layer with $\tilde{A}$, then performed a forward pass during which we cached the inputs at each layer for LRP.

LRP started at the output neuron with the maximal activation, before the softmax normalization. For all intermediate layers we used Eq.~\ref{eq:lrp}. Since coefficients in the input word vectors are negative, we used a special propagation rule \cite{montavon2017explaining}, which we omit here, due to space contraints. We cached the intermediate contribution maps right after the max-pooling operation, after the second and after the first (input space) feature projection layers in the GCN layers.

For the qualitative analysis, we visualized the contributions of each node at each layer as well as the relevance flow over the graph's edges across layers, as outlined in Sec.~\ref{sec:lrv}. For the quantitative validation, we deleted a growing portion of the globally most relevant edges (starting with the most relevant ones) and monitored the model's classification performance. In a second experiment, we did the same starting with the least relevant edges. Here, \textit{global edge relevance} refers to the sum of an edge's relevance across all layers, $\sum_{l}e_{ij}^{(l)}$.
\section{Introduction}
A Deep Neural Network (DNN) that offers -- or from which we can retrieve -- explanations for its decisions arguably is easier to improve and debug than a black box model. Loosely following \citet{MonDSP18}, we understand an explanation as a ``collection of features (...) that have contributed for a given example to produce a decision.'' For humans to make sense of an explanation it needs to be expressed in a human-interpretable domain, which is often the input space \cite{MonDSP18}.

For instance, in the vision domain \citet{bach-plos15} propose the Layerwise Relevance Propagation (LRP) algorithm that propagates contributions from an output activation back to the first layer, the input pixel space. \citet{arras2017relevant} implement a similar strategy for NLP tasks, where contributions are propagated into the word vector space and then summed up over the word vector dimensions to create heatmaps in the plain text input space.

In the course of the backpropagation of contributions, hidden layers in the DNN are visited, but rarely inspected.\footnote{Although, \citet{arras2017relevant} propose inspecting hidden layers with LRP as a possible future direction.} A major challenge when inspecting and interpreting hidden states lies in the fact that a projection into an interpretable domain is often made difficult by the non-linearity, non-locality and dimension reduction/expansion across hidden layers.

In this work, we present an explainability method that visits and projects visible and hidden states in Graph Convolutional Networks (GCN) \cite{kipf2016semi} onto the interpretable input space. Each GCN layer fuses neighborhoods in the input graph. For this fusion to work, GCNs need to replicate the input adjacency at each layer. This allows us to project their intermediate representations back onto the graph.

Our method, layerwise relevance visualization (LRV), not only visualizes static explanations in the hidden layers, but also tracks and visualizes hidden cross-layer dynamics, as illustrated in Fig.~\ref{fig:lrv}. In a qualitative and a quantitative analysis, we experimentally demonstrate that our approach yields meaningful explanations for a GCN sentence classifier.
\section{Methods}
In this section we explain how we combine GCNs and LRP for layerwise relevance visualization. We begin with a short recap of GCNs and LRP to establish a basis for our approach and to introduce notation.
\input{sections/subsections/gcn}
\input{sections/subsections/lrp}
\input{sections/subsections/lrv}

\section{Related Work}
\citet{niepert2016learning, Wu-sgc2019} introduce graph networks that natively support feature visualization (explanations) but their models are not graph convolutional networks in the sense of \citet{kipf2016semi} that we address here.

\citet{velivckovic2017graph} propose Graph Attention Networks and also project an explanation of a hidden representation onto the input graph. They do not, however, continue across multiple layers. Furthermore, their explanation technique differs from ours. The authors use attention coefficients to scale edge thicknesses in their explanatory visualization.
In contrast, we base edge relevance on the amount of relevance an edge carried from one layer to the next, according to LRP. Our method does this in a conventional GCN, which does not apply the attention mechanism.

The body of work on the explainability of graph neural nets also includes the GNN explainer by \citet{ying2019gnn}, a model-agnostic explainability method. Since their method is model-agnostic, it can be applied to GCNs. Nevertheless, it would not reveal hidden dynamics, as our method does.

In parallel to our work, in the last couple of months, several more works on explainability in the context of graph neural nets were published. \citet{pope2019explainability}, for instance, evaluate several explainability methods on data sets from the chemistry and vision domains. The methods do not include LRP, however, and the authors do not visualize relevance layerwise. The two works that are most related to our approach were published very recently by \citet{mingming} and \citet{baldassarre2019explainability}. Both implement LRP for graph networks (inter alia).
\citet{mingming} introduce the notion of node importance visualization, which is also reflected in our explanations and \citet{baldassarre2019explainability}, similar to our approach,  suggest to trace (and visualize) explanations over feature-less edges. Both works, however, address a different task from ours: In contrast to our graph classification task, they perform node classification and identify k-hop neighbor contributions in the proximity of a central node of interest.
\section{Results}
After training, our model achieved a weighted F$_{1}$ score of 0.822 on the official (20k) test set. We then performed the post-hoc explanation with the trained model, receiving layerwise explanations as the one depicted in Fig.~\ref{fig:lrv}. More examples can be found in the appendix.

Fig.~\ref{fig:lrv} (top) shows which vectors in the final layer the GCN bases its classification decision on. The middle and bottom segments reveal how much relevant information the model fused in these vectors from neighboring nodes during the forward pass:

According to the LRV in Fig.~\ref{fig:lrv}, the model primarily bases its classification decision on the fusion of the vector representations of \texttt{total}, \texttt{patients}, and \texttt{116}. The vector representations of these nodes are accumulated in the vector of \texttt{116} in two steps.

Interestingly, the vector of \texttt{patients} contributes a larger portion after it has been fused with \texttt{total}. Furthermore, \texttt{randomized} becomes more relevant after the first GCN layer, contributing to the second most relevant n-gram \texttt{(were, randomized)}. Other n-grams, such as \texttt{(A, total)} or \texttt{(of, patients)} appear less relevant.

Note that if we had simply redistributed the contributions in the final layer, using only the adjacency matrix, without considering the activations in the forward pass as LRP does, these n-grams would have received an unsubstantiated share. Furthermore, a conventional, single explanation in the input space would have hardly revealed the hidden dynamics discussed above.

As explained in Sec.~\ref{sec:experiments}, we also conducted input perturbation experiments to validate that our method indeed identifies the graph components that are relevant to the GCN decision. Fig.~\ref{fig:pertubation} summarizes the results: The performance of our model degrades much faster when we delete edges that contributed a lot to the model's decision, according to our method. We take this as evidence that our method indeed correctly identifies the relevant components in the input graphs.
\begin{figure}[!tb]
\pgfplotstableread{top.dat}{\top}
\pgfplotstableread{bottom.dat}{\bottom}
\pgfplotsset{every axis legend/.append style={at={(0.05,0.05)}, anchor=south west}}
\begin{tikzpicture}[scale=.9, transform shape]
\begin{axis}[minor tick num=1,
xlabel=Percentage of deleted edges, ylabel=Weighted F$_1$, legend style={draw=none}]
\addplot [dashed, black,very thick] table [x={per}, y={f}] {\bottom};
\addplot [black,very thick] table [x={per}, y={f}] {\top};
\legend{least relevant, most relevant}
\end{axis}
\end{tikzpicture}
\caption{Perturbation experiment.}
\label{fig:pertubation}
\end{figure}
\subsection{Graph Convolutional Networks}

Assume a graph $G$ represented by $(\tilde{A}, H^{(0)})$ where $\tilde{A}$ is a degree-normalized adjacency matrix, which introduces self loops to the nodes in $G$, and $H^{(0)}\in {\rm I\!R}^{n \times d}$ an embedding matrix of the $n$ nodes in $G$, ordered in compliance with $\tilde{A}$. A GCN layer propagates such graph inputs according to
\begin{equation}
\label{eq:gcn}
    H^{(l+1)} = \sigma \left(\tilde{A}H^{(l)}W^{(l)}\right),
\end{equation}
which can be decomposed into a feature projection $H'^{(l)}=H^{(l)}W^{(l)}$ and an adjacency projection $\tilde{A}H'^{(l)}$, followed by a non-linearity $\sigma$.

The adjacency projection fuses each node with the features in its effective neighborhood. At each GCN layer, the effective neighborhood becomes one hop larger, starting with a one-hop neighborhood in the first layer. The last layer in a GCN classifier typically is fully connected (FC) and projects its inputs onto class probabilities.
\subsection{Layerwise Relevance Propagation}
\label{sec:lrp}
To receive explanations for the classifications of a GCN classifier, we apply LRP. LRP explains a neuron's activation by computing how much each of its input neurons contributed\footnote{We use the terms \textit{contribution} and \textit{relevance} interchangeably.} to the activation. Contributions are propagated back layerwise.

\citet{montavon2017explaining} show that the positive contribution of neuron $h^{(l)}_{i}$, as defined in \citet{bach-plos15} with the $z^{+}$-rule, is equivalent to
\begin{equation}
\label{eq:lrp}
    R_{i} = \sum_{j}\frac{h_{i}^{(l)}w_{ij}^{+}}{\sum_{k}h^{(l)}_{k}w_{kj}^{+}}R_{j},
\end{equation}
where $\sum_{k}$ sums over the neurons in layer $l$ and $\sum_{j}$ over the neurons in layer $(l+1)$. Eq.~\ref{eq:lrp} only allows positive inputs, which each layer receives if the previous layers are activated using ReLUs.\footnote{LRP is capable of tracking negative contributions, too. In this work, we focus on positive contributions.} LRP has an important property, namely the relevance conservation property: $\sum_{j} R_{j \leftarrow k} = R_{k}, R_{j} = \sum_{k} R_{j \leftarrow k}$, which not only conserves relevance from neuron to neuron but also from layer to layer  \cite{bach-plos15}.
\subsection{Layerwise Relevance Visualization}
\label{sec:lrv}
We combine graph convolutional networks and layerwise relevance propagation for layerwise relevance visualization as follows. During training, GCNs receive input graphs in the form of $(\tilde{A}, H^{(0)})$ tuples. This is efficient and allows batching but it poses a problem for LRP: If the adjacency matrix is considered part of the input, one could argue that it should receive relevance mass. This, however, would make it hard to meet the conservation property.

Instead, we treat $\tilde{A}$ as part of the model in a post-hoc explanation phase, in which we construct an FC layer with $\tilde{A}$ as its weights. The GCN layer then consists of two FC sublayers. During the forward pass, the first one performs the feature projection and the second one -- the newly constructed one -- the adjacency projection.

To make use of Eq.~\ref{eq:lrp} in the adjacency layer, we need to avoid propagating negative activations. This is why we apply the ReLU activation early, right after the feature projection, which yields the propagation rule
\begin{equation}
    \label{eq:xgcnforward}
    H^{(l+1)} = \tilde{A}\sigma(H^{(l)}W^{(l)}).
\end{equation}
When unrolled, this effectively just moves one adjacency projection from inside the first ReLU to outside the last ReLU. Alternatively, it should be possible to first perform the adjacency projection and afterwards the feature projection.

Eq.~\ref{eq:xgcnforward} allows us to directly apply  Eq.~\ref{eq:lrp} to the two projection sublayers in a GCN layer. During LRP, we cache the intermediate contribution maps $R^{(l)} \in {\rm I\!R}^{n \times f}$ that we receive right after we propagated past the feature projection sublayer and compute node $i$'s contribution in that layer as
$R(i^{(l)}) = \sum_{c}R^{(l)}_{ic}$. In addition, we also compute the edge relevance $e^{(l)}_{(i,j)}$ between nodes $i$ and $j$ as the amount of relevance that it carried from layer $l-1$ to layer $l$.

In what follows, we use $R(i^{(l)})$ and $e^{(l)}_{ij}$ to visualize hidden state dynamics (i.e. relevance flow) in the input graph. Furthermore, similar to \citet{mingming}, we make use of perturbation experiments to verify that our method indeed identifies the relevant components in the input graph.