summaries: This paper proposes a decomposition-based explanations method for graph neural networks.  In detail, the authors design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes, so as to achieve the faithful explanation for GNN predictions. They demonstrate the effectiveness of the proposed method on synthetic and real-world datasets.

summaries: The paper aims at tackling the black-box nature problem of GNN by introducing a new type of explainable GNN framework called DEGREE (Decomposition based Explanation for GRaph nEural nEtworks). There are mainly two innovations. The first one lies in its ability to track contribution of components in the input graph. The second one is the algorithm for subgraph-level explanation via agglomeration. The model achieves a good compromise between performance and time efficiency.

summaries: This paper proposes a decomposition-based explanation method for graph neural networks. The motivation of this paper is that existing works based on approximation and perturbation suffer from drawbacks. To address the issue of existing works, the authors directly decompose the influence of node groups in the forward pass. The decomposition rules are designed for GCN and GAT. Further, to efficiently select subgraph groups from all possible combinations, the authors propose a greedy approach to search for maximally influential node sets. Experiments on synthetic and real-world datasets verify the improvements over existing works.

summaries: The paper provides DEGREE, which decomposes the feedforward propagation mechanism of a GNN to understand it. They give realistic decomposition techniques for those typically used layers in GNNs after presenting the key guidelines for developing decomposition-based explanations. They also devise an approach for providing subgraph-level explanation via agglomeration, which makes effective use of graph topology. DEGREE surpasses baselines in terms of fidelity and can capture important structures in graph data, according to experimental results.

abstractText: Graph Neural Networks (GNNs) are gaining extensive attention for their application in graph data. However, the black-box nature of GNNs prevents users from understanding and trusting the models, thus hampering their applicability. Whereas explaining GNNs remains a challenge, most existing methods fall into approximation based and perturbation based approaches with suffer from faithfulness problems and unnatural artifacts respectively. To tackle these problems, we propose DEGREE (Decomposition based Explanation for GRaph nEural nEtworks) to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. Based on this, we further design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods. The efficiency of our algorithm can be further improved by utilizing GNN characteristics. Finally, we conduct quantitative and qualitative experiments on synthetic and real-world datasets to demonstrate the effectiveness of DEGREE on node classification and graph classification tasks.

authors:
Federico Baldassarre
Hossein Azizpour

title: Explainability techniques for graph convolutional networks, 2019

authors:
Albert-László Barabási
Réka Albert

title: Emergence of scaling in random

venue: networks. science,

authors:
Lei Cai
Shuiwang Ji

title: A multi-scale approach for graph link prediction

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Sergio Casas
Cole Gulino
Renjie Liao
Raquel Urtasun

title: Spatially-aware graph neural networks for relational behavior forecasting from sensor data

authors:
Chun-Hao Chang
Elliot Creager
Anna Goldenberg
David Duvenaud

title: Explaining image classifiers by counterfactual generation

venue: arXiv preprint arXiv:1807.08024,

authors:
Asim Kumar Debnath
Rosa L Lopez de Compadre
Gargi Debnath
Alan J Shusterman
Corwin Hansch

title: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity

venue: Journal of medicinal chemistry,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: Bert: Pre-training of deep bidirectional transformers for language understanding, 2019

authors:
Mengnan Du
Ninghao Liu
Xia Hu

title: Techniques for interpretable machine learning

venue: Communications of the ACM,

authors:
Wenqi Fan
Yao Ma
Qing Li
Yuan He
Eric Zhao
Jiliang Tang
Dawei Yin

title: Graph neural networks for social recommendation

venue: In The World Wide Web Conference,

authors:
Mikael Henaff
Joan Bruna
Yann LeCun

title: Deep convolutional networks on graph-structured data

venue: arXiv preprint arXiv:1506.05163,

authors:
Qiang Huang
Makoto Yamada
Yuan Tian
Dinesh Singh
Dawei Yin
Yi Chang

title: Graphlime: Local interpretable model explanations for graph neural networks

venue: arXiv preprint arXiv:2001.06216,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax, 2017

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

authors:
Jian Liang
Bing Bai
Yuren Cao
Kun Bai
Fei Wang

title: Adversarial infidelity learning for model interpretation

venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Cheng-Hao Liu
Maksym Korablyov
Stanisław Jastrzebski
Paweł Włodarczyk-Pruszyński
Yoshua Bengio
Marwin HS Segler

title: Retrognn: Approximating retrosynthesis by graph neural networks for de novo drug design

authors:
Meng Liu
Youzhi Luo
Limei Wang
Yaochen Xie
Hao Yuan
Shurui Gui
Haiyang Yu
Zhao Xu
Jingtun Zhang
Yi Liu
Keqiang Yan
Haoran Liu
Cong Fu
Bora Oztekin
Xuan Zhang
Shuiwang Ji

title: DIG: A turnkey library for diving into graph deep learning research

venue: arXiv preprint arXiv:2103.12608,

authors:
Ninghao Liu
Qiaoyu Tan
Yuening Li
Hongxia Yang
Jingren Zhou
Xia Hu

title: Is a single vector enough? exploring node polysemy for network embedding

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Ana Lucic
Maartje ter Hoeve
Gabriele Tolomei
Maarten de Rijke
Fabrizio Silvestri

title: Cfgnnexplainer: Counterfactual explanations for graph neural networks, 2021

authors:
Scott Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions, 2017

authors:
Dongsheng Luo
Wei Cheng
Dongkuan Xu
Wenchao Yu
Bo Zong
Haifeng Chen
Xiang Zhang

title: Parameterized explainer for graph neural network

venue: arXiv preprint arXiv:2011.04573,

authors:
W James Murdoch
Arthur Szlam

title: Automatic rule extraction from long short term memory networks

venue: arXiv preprint arXiv:1702.02540,

authors:
W James Murdoch
Peter J Liu
Bin Yu

title: Beyond word importance: Contextual decomposition to extract interactions from lstms

venue: arXiv preprint arXiv:1801.05453,

authors:
Phillip E Pope
Soheil Kolouri
Mohammad Rostami
Charles E Martin
Heiko Hoffmann

title: Explainability methods for graph convolutional neural networks

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

title: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

venue: Nature Machine Intelligence,

authors:
Thomas Schnake
Oliver Eberle
Jonas Lederer
Shinichi Nakajima
Kristof T. Schütt
Klaus-Robert Müller
Grégoire Montavon

title: Higher-order explanations of graph neural networks via relevant walks, 2020

authors:
Robert Schwarzenberg
Marc Hübner
David Harbecke
Christoph Alt
Leonhard Hennig

title: Layerwise relevance visualization in convolutional text graph classifiers, 2019

authors:
Avanti Shrikumar
Peyton Greenside
Anshul Kundaje

title: Learning important features through propagating activation differences

venue: In International Conference on Machine Learning,

authors:
Karen Simonyan
Andrea Vedaldi
Andrew Zisserman

title: Deep inside convolutional networks: Visualising image classification models and saliency maps

venue: arXiv preprint arXiv:1312.6034,

authors:
Chandan Singh
W James Murdoch
Bin Yu

title: Hierarchical interpretations for neural network predictions

venue: arXiv preprint arXiv:1806.05337,

authors:
Mukund Sundararajan
Ankur Taly
Qiqi Yan

title: Axiomatic attribution for deep networks

authors:
Minh N Vu
My T Thai

title: Pgm-explainer: Probabilistic graphical model explanations for graph neural networks

venue: arXiv preprint arXiv:2010.05788,

authors:
Xiang Wang
Yingxin Wu
An Zhang
Xiangnan He
Tat seng Chua

title: Causal screening to interpret graph neural networks, 2021

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

venue: arXiv preprint arXiv:1810.00826,

authors:
Rex Ying
Dylan Bourgeois
Jiaxuan You
Marinka Zitnik
Jure Leskovec

title: Gnnexplainer: Generating explanations for graph neural networks

venue: Advances in neural information processing systems,

authors:
Hao Yuan
Jiliang Tang
Xia Hu
Shuiwang Ji

title: Xgnn: Towards model-level explanations of graph neural networks

authors:
Hao Yuan
Haiyang Yu
Jie Wang
Kang Li
Shuiwang Ji

title: On explainability of graph neural networks via subgraph explorations

venue: arXiv preprint arXiv:2102.05152,

authors:
Muhan Zhang
Yixin Chen

title: Link prediction based on graph neural networks

venue: arXiv preprint arXiv:1802.09691,

authors:
Muhan Zhang
Zhicheng Cui
Marion Neumann
Yixin Chen

title: An end-to-end deep learning architecture for graph classification

authors:
Jie Zhou
Ganqu Cui
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Lifeng Wang
Changcheng Li
Maosong Sun

title: Graph neural networks: A review of methods and applications

venue: arXiv preprint arXiv:1812.08434,

venue: We employ the ACC Liang et al

heading: 1 INTRODUCTION

text:
Graph Neural Networks (GNNs) play an important role in modeling data with complex relational information (Zhou et al., 2018), which is crucial in applications such as social networking (Fan et al., 2019), advertising recommendation (Liu et al., 2019), drug generation (Liu et al., 2020), and agent interaction (Casas et al., 2019). However, GNN suffers from its black-box nature and lacks a faithful explanation of its predictions.
Recently, several approaches have been proposed to explain GNNs. Some of them leverage gradient or surrogate models to approximate the local model around the target instance (Huang et al., 2020; Baldassarre & Azizpour, 2019; Pope et al., 2019). Some other methods borrow the idea from perturbation based explanation (Ying et al., 2019; Luo et al., 2020; Lucic et al., 2021), under the assumption that removing the vital information from input would significantly reduce output confidence. However, approximation based methods do not guarantee the fidelity of the explanation obtained, as Rudin (2019) states that a surrogate that mimics the original model possibly employs distinct features. On the other hand, perturbation based approaches may trigger adversarial nature of the depth model. Chang et al. (2018) reported this phenomenon where masking some parts of the input image introduces unnatural artifacts. Additionally, additive feature attribution methods (Vu & Thai, 2020; Lundberg & Lee, 2017) such as gradient based methods and GNNExplainer only provide a single heatmap or subgraph as explanation. The nodes in graph are usually semantically individual and we need a fine-grained explanation to the relationships between them. For example, in organic chemistry, the same functional group combined with different structures can exhibit very different properties.
To solve the above problems, we propose DEGREE (Decomposition based Explanation for GRaph nEural nEtworks) , which measures the contribution of components in the input graph to the GNN prediction. Specifically, we first summarize the intuition behind the Context Decomposition (CD) algorithm (Murdoch et al., 2018) and propose that the information flow in GNN’s message propagation mechanism is decomposable. Then we design the decomposition schemes for the most commonly used layers and operations in GNNs, so as to isolate the information flow from distinct
node groups. Furthermore, we explore the subgraph-level explanation via an aggregation algorithm that utilizes DEGREE and the structural information of the input graph to construct a series of subgraph sets as the explanation. DEGREE guarantees explanation fidelity by directly analyzing GNN feed-forward propagation, instead of relying on input perturbation or the use of alternative models. DEGREE is non-additive and can therefore uncover non-linear relationships between nodes. We quantitatively and qualitatively evaluate the DEGREE on both synthetic and real-world datasets to validate the effectiveness of our method. The contributions of this work are summarized as follows:
• We propose a new explanation method (DEGREE) for GNNs, from the perspective of decomposition. By elucidating the feed-forward propagation mechanism within GNN, DEGREE allows capturing the contribution of individual components of the input graph to the final prediction. • We propose an aggregation algorithm that provides a series of subgraphs as explanation in order to mine the complex interactions between graph components. We combine the property of the message propagation mechanism to further reduce the computation. • We evaluate DEGREE on both synthetic and real-world datasets. The quantitative experiments show that our method could provide faithful explanations. The qualitative experiments indicate that our method may capture the interaction between graph components.

heading: 2 RELATED WORK

text:
Despite the great success in various applications, the black-box nature of deep models has long been criticized. Explainable Artificial Intelligence (XAI) tries to bridge the gap by understanding the internal mechanism of deep models (Du et al., 2019). Meanwhile, the need to tackle non-Euclidean data, such as geometric information, social networks, has given rise to the development of GNNs. Similar to the tasks on image or text data, GNNs focus on node classification (Henaff et al., 2015), graph classification (Xu et al., 2018; Zhang et al., 2018), and link prediction (Zhang & Chen, 2018; Cai & Ji, 2020). Message passing mechanism allows the information to flow from one node to another along edges, and empowers GNNs with convolutional capabilities for graph data.
While the explainability in image and text domains is widely studied (Shrikumar et al., 2017; Sundararajan et al., 2017; Simonyan et al., 2013), the explainability of GNN is on the rise. First, some recent work adapts the interpretation methods used for traditional CNNs to GNNs (Baldassarre & Azizpour, 2019; Pope et al., 2019). They employ gradient values to investigate the contribution of node features to the final prediction. However, these methods ignore the topological information, which is a crucial property of graph data. Second, some methods trace the model prediction back to the input space in a backpropagation manner layer by layer (Schwarzenberg et al., 2019; Schnake et al., 2020). Third, some methods define a perturbation-based interpretation whereby they perturb node, edge, or node features and identify the components that affect the prediction most. Specifically, GNNExplainer and PGExplainer (Ying et al., 2019) maximize the mutual information between perturbed input and original input graph to identify the important features. Causal Screening (Wang et al., 2021) searches for the important subgraph by monitoring the mutual information from a cause-effect standpoint. CF-GNNExplainer (Lucic et al., 2021) proposes to generate counterfactual explanations by finding the minimal number of edges to be removed such that the prediction changes. In addition, XGNN (Yuan et al., 2020) builds a model-level explanation for GNNs by generating a prototype graph that can maximize the prediction. Moreover, due to the discrete and topological nature of graph data, XGNN defines graph generation as a reinforcement learning task instead of gradient ascent optimization.
Many previous explanation methods for GNNs suffer from adversarial triggering issues, faithfulness issues and additive assumptions. To this end, we propose a decomposition based explanation for GNNs (DEGREE) to remedy these problems. DEGREE enables to track the contribution of the components from the input graph to the final prediction by decomposing a trained GNN. Thus, DEGREE guarantees the integrity of the input and eliminates the adversarial triggering issue of the perturbation-based approach. Since no surrogate models are used, DEGREE guarantees its faithfulness. Meanwhile, by integrating the decomposition to the normal layer, DEGREE does not have any additional training process.

heading: 3 DEGREE: DECOMPOSITION BASED EXPLANATION FOR GNNS

text: In this section, we introduce the details of the proposed explanation method. First, we introduce the notations and problem definition. Then, we discuss the general idea of decomposition based explanation. Finally, we develop concrete decomposition schemes for different GNNs layers

heading: 3.1 PROBLEM DEFINITION

text: We first introduce the notations used in this work. Given a graph G = (V, E), where V is the set of nodes and E is the set of edges between nodes. The adjacency matrix of G is denoted as A ∈ RN×N , where N = |V| is the number of nodes, so V = {v1, v2, ..., vN}. The nodes are associated with features, and the feature matrix is denoted as X ∈ RN×F , where F is the feature dimension. In this work, we focus on explaining GNN-based classification models. Let f denote the target GNN model. f computes the likelihood of a node or graph belonging to the target class, where f : G 7→ R|V| or f : G 7→ R, for node or graph classification respectively. The goal of explanation is to find the most important subgraph in G given f(G), which requires measuring the contribution of all possible subgraphs and find the ones with high contribution scores. However, there are two challenges to be addressed. (1) Given any subgraph of interest, how to estimate its contribution without breaking up the input graph? (2) The number of all subgraphs in G is usually very large, so how to choose candidate subgraphs for improving explanation efficiency? We tackle the first challenge in the following part of Sec 3 and solve the second one in Sec 4.

heading: 3.2 DECOMPOSITION BASED EXPLANATION

text:
In general, a prediction model f contains multiple layers Lt, t ∈ {1, . . . , T}: f(X) = LT ◦ LT−1 ◦ · · · ◦ L2 ◦ L1(X). (1)
Let X[t] denotes the input of Lt, so X[t + 1] = Lt(X[t]) and X[1] = X. The symbol ◦ denotes function composition. Here X[t] ∈ RN×Ft is the embedding matrix at t-th layer, where Ft is the latent dimension. The embedding vector of the i-th node at t-th layer is denoted as Xi[t].
The core idea of decomposition based explanation is that, given a target node group (or subgraph) of interest, we estimate its contribution score to model prediction merely through feed-forward propagation. We call the information propagated from the target group as target portion, and the rest of information is called background portion. In the following, we use γ and β to denote target portion and background portion, respectively. Let m ∈ RN and mn ∈ {0, 1}, where mn = 1 means vn belongs to the target group and otherwise mn = 0. Then, the decomposition is initialized from the layer of node features, where the target portion and background portion of the input feature matrix
are: Xγ = diag(m)X and Xβ = (I−diag(m))X, respectively. In a neural network, different parts of input are entangled in the feedforward process into latent representations, which poses challenges for explanation. Suppose the target and background portion in X[t] are known from prior layer, we could explain the model if we can still distinguish the information flows of the two portions inside Lt. That is, at layer Lt, suppose its input can be decomposed as X[t] = Xγ [t]+Xβ [t], the following relations need to hold for explanation:
LDt (X γ [t],Xβ [t]) = Γ(Xγ [t],Xβ [t])︸ ︷︷ ︸ Xγ [t+1] , B(Xγ [t],Xβ [t])︸ ︷︷ ︸ Xβ [t+1]  (2) Lt(X[t]) = X[t+ 1] = X γ [t+ 1] + Xβ [t+ 1], (3)
where LDt (·, ·) denotes the decomposed version of layer Lt. Γ(·, ·) and B(·, ·) corresponds to the contribution of the target and the background portion to layer Lt. Xγ [t+ 1] and Xβ [t+ 1] denotes the target and background portion of X[t + 1] as the input to the next layer. The decomposition above goes from the input, through all intermediate layers, to the final prediction. If a target node group or subgraph is important, then it should contributes to most of the prediction, meaning that Γ(Xγ [T ],Xβ [T ]) ≈ f(X).

heading: 3.3 INTUITIONS BEHIND DECOMPOSITION BASED EXPLANATION FOR GNN

text:
The intuition behind decomposition based explanation are summarized as two rules: (1) the target and background portion at a higher layer mainly comes from the target and background portion at the lower layer respectively; (2) ideally there should be little interaction between the target portion and the background portion. It is worth noting that the partition is not dimension-wise, meaning that each latent dimension may contain information from both target and background portions.
Figure 1 briefly illustrates the working principle of GNNs: the model computes neural message for each node pair and aggregates message for them from their neighbors. One more rule should be introduced to govern the decomposition of GNNs: the target and background portion of a node feature aggregates from the target and background portion of its neighbours, respectively. This can be easily illustrated by a decomposition of the concise aggregation mechanism of GNN:
X[t+ 1] = AX[t] = A ( Xγ [t] + Xβ [t] ) = AXγ [t]︸ ︷︷ ︸
Xγ [t+1] +AXβ [t]︸ ︷︷ ︸ Xβ [t+1] , (4)
where the intuition is that information aggregation is distributive in nature. To develop an effective explanation, several challenges should be tackled. First, how to design the decomposition scheme for different types of layers? Second, how to find a good target group given all possible combinations?

heading: 3.4 DECOMPOSING GNN LAYERS

text: In this work, we consider the decomposition scheme for two commonly used GNN architectures: GCN (Kipf & Welling, 2016) and GAT (Veličković et al., 2017).

heading: 3.4.1 DECOMPOSING GCNS

text:
The GCN architecture consists of graph convolution layers, fully connected layers, and ReLU.
Graph Convolution Layer: The graph convolution operation pass messages between nodes:
X[t+ 1] = D̃− 1 2 ÃD̃− 1 2X[t]W + b, (5)
where W and b denote the trainable weights and bias. Here b is optional. Ã = A + I denotes the adjacency matrix with self loop. The matrix D̃i,i = ∑ j Ãi,j is the diagonal degree matrix of Ã. The corresponding decomposition can be designed as follows:
γ[t] = D̃− 1 2 ÃD̃− 1 2Xγ [t]W , β[t] = D̃− 1 2 ÃD̃− 1 2Xβ [t]W, (6) Xγ [t+ 1] = γ[t] + b · ∣∣γ[t]∣∣∣∣γ[t]∣∣+∣∣β[t]∣∣ , Xβ [t+ 1] = β[t] + b · ∣∣β[t]∣∣∣∣γ[t]∣∣+∣∣β[t]∣∣ , (7) where Xγ [t] and Xβ [t] is the target and background portion of X[t], respectively. The derivation of γ[t] and β[t] is intuitive since graph convolution is a linear operation. Motivated by (Singh et al., 2018), we let γ[t] and β[t] to compete for their share of b, as shown in Eq 7.
∣∣γ[t]∣∣ ∈ RFt+1 measures the dimension-wise magnitude of Xγ [t] after the linear mapping (
∣∣β[t]∣∣ is defined similarly). Fully Connected Layer: A fully connected layer prevalent in the model is shown below:
X[t+ 1] = X[t]Θ + b, (8)
where Θ and b denote trainable weights and bias. Structure-wise, it is very similar to the GCN. The decomposition can be designed as:
Xγ [t+1] = Xγ [t]Θ+b· ∣∣Xγ [t]Θ∣∣∣∣Xγ [t]Θ∣∣+∣∣Xβ [t]Θ∣∣ ,Xβ [t+1] = Xβ [t]Θ+b· ∣∣Xβ [t]Θ∣∣∣∣Xγ [t]Θ∣∣+∣∣Xβ [t]Θ∣∣ . (9) ReLU Activation: For the activation operator ReLU, we use the telescoping sum decomposition from Murdoch & Szlam (2017). We update the target term first and then update the background term by subtracting this from total activation:
Xγ [t+ 1] = ReLU ( Xγ [t] ) , Xβ [t+ 1] = ReLU ( Xγ [t] + Xβ [t] ) − ReLU ( Xγ [t] ) . (10)
Maxpooling: We track the node indices selected by pooling in both target and background portion.

heading: 3.4.2 DECOMPOSING GATS

text:
The graph attention layer in GAT is similar to Eq. 5, but uses the attention coefficients αi,j to aggregate the information (an alternative way to understand Eq. 5 is that αi,j = (D̃− 1 2 ÃD̃− 1 2 )i,j):
αi,j =
exp ( LeakyReLU ([ Xi[t]W‖Xj [t]W ] a ))
∑ k∈Ni∪{i} exp ( LeakyReLU ([ Xi[t]W‖Xk[t]W ] a )) , (11)
where ‖ represents the concatenation operation. W and a are parameters. Xi[t] denotes the embedding of node i at layer Lt. Ni denotes the neighbors of node i. Therefore, a graph attention layer can be seen as consisting of four smaller layers: linear mapping, concatenation, LeakyReLU activation, and softmax operation. Decomposing a linear mapping is as trivial as decomposing an FC layer. To decompose the concatenation operator:
Xi[t]‖Xj [t] = Xγi [t]‖X γ j [t] + X β i [t]‖X β j [t]. (12)
For LeakyReLU, the idea of decomposition is the same as ReLU. For softmax operation, we split the coefficients proportionally to the exponential value of the target and the background term of input:
Xγ [t+ 1] = softmax ( X[t] ) ·
exp (∣∣Xγ [t]∣∣)
exp (∣∣Xγ [t]∣∣)+ exp(∣∣Xβ [t]∣∣) ,
Xβ [t+ 1] = softmax ( X[t] ) ·
exp (∣∣Xβ [t]∣∣)
exp (∣∣Xβ [t]∣∣)+ exp(∣∣Xγ [t]∣∣) .
(13)
Here we employ the similar motivation that used to split bias term in Eq. 7, and let ∣∣Xγ [t]∣∣ and∣∣Xβ [t]∣∣ to compete for the original value.

heading: 4 SUBGRAPH-LEVEL EXPLANATION VIA AGGLOMERATION

text: Through decomposition, we could compute the contribution score of any given node groups. However, this is not enough for explaining GNNs. Our goal of explanation is to find the most important subgraph structure, but it is usually impossible to exhaustively compute and compare the scores of all possible subgraphs. In this section, we design an agglomeration algorithm to tackle the challenge.

heading: 4.1 CONTEXTUAL CONTRIBUTION SCORE

text:
We first introduce a new scoring function to be used in our algorithm. Different from the absolute contribution scores provided by decomposition, in many scenarios, we are more interested in the relative contribution of the target compared to its contexts. Let Vγ ⊂ V be the target node group, and fD(·) be the contribution score calculated from decomposition. The relative contribution of Vγ averaged over different contexts is calculated as:
φ(Vγ) , EC∼RW(NL(Vγ)) [ fD(Vγ ∪ C)− fD(C) ] , (14)
where C is the context around Vγ , and NL (Vγ) contains the neighboring nodes of Vγ within Lhops. Here we use a random walk process RW () to sample C within the neighborhood around Vγ . The reason for sampling within the neighborhood is based on the information aggregation, where a node collects the information from its neighbors within certain hops constrained by the GNN depth.

heading: 4.2 SUBGRAPHS CONSTRUCTION VIA AGGLOMERATION

text:
Our agglomeration algorithm initializes from individual nodes and terminates when the whole graph structure is included. Specifically, the interpretation process constructs a series of intermediate subgraph sets E = {S1, ...,SI}, where Si = {B1, ...,BMi} contains Mi subgraphs. At each step, the algorithm searches for the candidate node or node group v that most significantly affects the contribution of subgraph Bm,m ∈ {1, ...,Mi} according to the ranking score r(v):
s(v) , φ ( {v} ∪ Bm ) − φ (Bm) , r(v) , ∣∣∣s(v)− Ev′ [s(v′)]∣∣∣ , s.t. v, v′ ∈ N (Bm), (15) whereN (Bm) is the set of neighbor nodes or node groups to Bm. Here s(v) measures the influence of v to Bm, while r(v) further revises the value by considering the relative influence of v compared to other candidates v′. At the beginning of our algorithm, Bm = ∅. A node v is selected if r(v) ≥ q ·maxv′ r(v′), and we set q = 0.6 in experiments. The selected nodes are merged into subgraphs to form Si+1. Small subgraphs will be merged into larger ones, so we have Mi ≤ Mj , i ≥ j. The algorithm executes the above steps repeatedly and terminates until all nodes are included (i.e., Mi = 1), or a certain pre-defined step budget is used up. Further details of the algorithm can be found in Section B of the Appendix.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL DATASETS

text: Following the setting in previous work (Ying et al., 2019), we adopt both synthetic datasets and real-world datasets. The statistic of all datasets are given in Sec A in the Appendix.

heading: 5.1.1 SYNTHETIC DATASETS

text:
• BA-Shapes. BA-Shapes is a unitary graph based on a 300-node Barabási-Albert (BA) graph (Barabási & Albert, 1999). 80 five-node motifs are randomly attached to the base graph. The motif is a ”house” structured network in which the points are divided into top-nodes, middlenodes, or bottom-nodes. 10% of random edges are attached to perturb the graph. • BA-Community. BA-Community dataset is constructed by combining two BA-Shapes graphs. To distinguish the nodes, the distribution of features of nodes in different communities differs. There are eight node classes based on the structural roles and community membership.
• Tree-Cycles. The Tree-Cycles dataset germinates from an eight-level balanced binary tree base graph. The motif is a six-node cycle. 80 motifs are randomly added to the nodes of the base graph. The nodes are classified into two classes, i.e., base-nodes and motif-nodes. • Tree-Grids. It is constructed in the same way as the Tree-Cycles dataset. The Tree-Grid dataset has the same base graph while replacing the cycle motif with a 3-by-3 grid motif.

heading: 5.1.2 REAL-WORLD DATASETS

text: • MUTAG. It is a dataset with 4,337 molecule graphs. Every graph is labeled according to their mutagenic effect on the bacterium. As discussed in (Debnath et al., 1991), the molecule with chemical group NH2 or NO2 and carbon rings are known to be mutagenic. Since non-mutagenic molecules have no explicit motifs, only mutagenic ones are presented during the analysis. • Graph-SST2. It is a dataset of 70,042 sentiment graphs, which are converted through Biaffine parser (Liu et al., 2021). Every graph is labeled according to its sentiment, either positive or negative. The nodes denote words, and edges denote their relationships. The node features are initialized as the pre-trained BERT word embeddings (Devlin et al., 2019).

heading: 5.2 EXPERIMENTAL SETUP

heading: 5.2.1 EVALUATION METRICS

text: The interpretation problem is formalized as a binary classification problem distinguishing between important and unimportant structures (nodes or edges, depending on the nature of ground truth). A good explanation should assign high scores to the important structures and low scores to unimportant ones. We consider the nodes within the motif to be important for the synthetic dataset and the rest to be unimportant. In the MUTAG dataset, the ”N-H” and ”N-O” edges are important, and the rest are unimportant. We conduct quantitative experiments on the synthetic datasets and the MUTAG dataset, and qualitative experiments on the MUTAG dataset and the Graph-SST2 dataset. We adopt the Area Under Curve (AUC) to evaluate the performance quantitatively.

heading: 5.2.2 BASELINES METHODS AND IMPLEMENTATION DETAILS

text:
Baselines Methods. We compare with four baselines methods: GRAD (Ying et al., 2019), GAT (Veličković et al., 2017), GNNExplainer (Ying et al., 2019) and PGExplainer (Luo et al., 2020). (1) GRAD computes the gradients of GNN output with respect to the adjacency matrix or node features. (2) GAT averages the attention coefficients across all graph attention layers as edge importance. (3) GNNExplainer optimizes a soft mask of edges or node features by maximizing the mutual information. (4) PGExplainer learns an MLP (Multi-layer Perceptron) model to generate the mask using the reparameterization trick (Jang et al., 2017).
Construction of Target Models. We use all synthetic datasets together with the MUTAG dataset for quantitative evaluation experiments. We train a GCN and GAT model as the model to be explained for all datasets following the setup of previous work. Meanwhile, we construct DEGREE(GCN) and DEGREE(GAT) as the decomposed version for our method. We set the number of GNN layers to 3 for all datasets, except for the Tree-Grid dataset where it is 4. Since the 3-hop neighbors of some target nodes has only in-motif nodes (no negative samples). For the qualitative evaluation experiment, we use the MUTAG dataset and Graph-SST2 dataset. For all the model training, we use Adam optimizer. All the datasets are divided into train/validation/test sets.
Explainer Setting. For all baseline methods, we keep the default hyper-parameters. For baselines (e.g., PGExplainer) who need training additional modules, we also split the data. We also split data for baselines requiring additional training (e.g. PGExplainer). We use all nodes in the motif for evaluation. For explainers that only provide node explanation, we average the score of its vertexes as edge explanation. The details of explainer settings can be found in Sec A in Appendix.

heading: 5.3 QUANTITATIVE EVALUATION

text:
In this section, we introduce experimental results on both synthetic datasets and the MUTAG dataset. For node classification, the computation graph only contains nodes within l-hop from the target node, where l is the number of model layer. The reason is that the nodes outside the computation
graph will not influence the final prediction. Table 1 shows the explanation AUC and time efficiency (the training time is shown outside the parentheses for PGExplainer). We have the following key findings. First, DEGREE achieves SOTA performances in most scenarios, showing its advantages in faithfulness over baseline methods. Second, the performance of DEGREE on GCN and GAT models can achieve similar high performance. This observation demonstrates the adaptability of our approach. Third, the improvement of AUC on BA-Community (˜9%) and MUTAG (˜5%) is more noticeable, where the two datasets distinguish themselves from others is that their features are not constants. It thus shows that our explanation method could well handle node features as they propagate through the graph structure. In terms of efficiency, DEGREE is implemented by decomposing the built-in forward propagation function, so there is no training process. The time cost is highly correlated to the complexity of the target model and the input size. We report further quantitative experiments in Appendix C.

heading: 5.4 QUALITATIVE EVALUATION

text:
In this section, we use Graph-SST2 and MUTAG datasets to visualize the explanation and demonstrate the effectiveness of our subgraph agglomeration algorithm in Sec 4.
In the first example, we show three visualizations from the MUTAG dataset in Figure 2. The first row represents a correctly predicted instance. Our model successfully identifies the ”NO2” motif as a moderately positive symbol for mutagenicity. The ”H” or the carbon ring is considered a negative sign for mutagenicity. Once the ”NO2” and the ring join, they become a strong positive symbol for mutagenicity. This phenomenon is consistent with the knowledge that the carbon rings and ”NO2” groups tend to be mutagenic (Debnath et al., 1991). We check instances with wrong predictions and show two representative examples. From the second row in Fig. 2, the GCN model precisely finds out the ”NH2” motif with the ring motif as a strong mutagenic symbol. But another wandering part without connection shows a strong non-mutagenic effect, ultimately leading to an incorrect prediction. The second row shows another typical failure pattern. The model catches the ”NH2” and part of the carbon ring as a mutagenic symbol, but the ”CH3” on the bottom right shows a strong non-mutagenic effect. The model erroneously learns a negative interaction between them.
In the second example, we show two visualizations for the Graph-SST2 dataset in Figure 3. The sentence in the first row is labeled negative, yet its prediction is wrong. Our algorithm can explain the decision that the GNN model regards first half of the sentence (”Maybe it’s asking too much”) as negative, the second half (”going to inspire me”, ”want a little more than this”) as positive. But the model can not tell the subjunctive tone behind the word ”if”, and consequently yields a positive but incorrect prediction. The sentence in the second row is negative, and the prediction is correct. Our algorithm precisely identifies the positive part (”Though Ford and Neeson capably hold our interest”) and the negative part (”but its just not a thrilling movie”). Moreover, it reveals that the GCN model can correctly learn the transition relationship between these two components.
We observe that our method can detect non-linear interactions between subgraphs throughout the agglomeration process from above examples. It can help to diagnose the incorrect predictions and enhance the credibility of the model. More visualizations and efficiency study are in Appendix D.

heading: 6 CONCLUSIONS

text: In this work, we present DEGREE which explains a GNN by decomposing its feedforward propagation process. After summarizing the fundamental rules for designing decomposition based explanation, we propose concrete decomposition schemes for those commonly used layers in GNNs. We also design an algorithm to provide subgraph-level explanation via agglomeration, which efficiently employs the topological information in graphs. Experimental results show that DEGREE outperforms baselines in terms of faithfulness and can capture meaningful structures in graph data.

heading: A DATASETS AND EXPERIMENTAL SETTING

text:
In this section, we introduce the detail of the datasets as wall as the experimental setting. The code can be found at https://anonymous.4open.science/r/DEGREE-3128.
Model setup: We adopt GCN model and GAT model architecture for corresponding experiments. We use GCN(#in channel,#out channel, activation) to denote a GCN layer, and similar notation for GAT layer and fully connected layer.
The structure of GCN model for node classification task is following: GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − FC(20, 20, ReLU)− FC(20,#label, Softmax). For graph classification task, we adopt a Max-pooling layer before the FC layers: GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − Maxpooling − FC(20, 20, ReLU)− FC(20,#label, Softmax). For GAT model architecture, we replace all GCN layers with GAT layer and keep the remaining setting unchanged. For experiments on Tree-Grid dataset, we adopt 4-layer GCN/GAT model by adding one more GCN/GAT layer with same setting before FC layers.
Dataset statistic: The statistics of synthetic datasets and real-world datasets are reported in Table 2.
Experimental setting: For all datasets, we use a train/validation/test split of 80%/10%/10%. For all synthetic datasets, the GCN model is trained for 1,000 epochs and the GAT model is trained for 200 epochs. For MUTAG dataset, the GCN and GAT model is trained 30 epochs. For Graph-SST2 dataset, the GCN model is trained 10 epochs. We use Adam optimizer and set the learning rate to 0.005, the other parameters remain at their default values. We also report the accuracy metric reached on each dataset in Table 3.
Hardware setting: We introduce the hardware that we use for the experiments.
CPU: AMD EPYC 7282 16-Core Processor.
GPU: GeForce RTX 3090 NVIDIA-SMI: 460.32.03 Driver Version: 460.32.03 CUDA Version: 11.2.

heading: B ALGORITHM

text:
We conclude the computation steps of subgraph-level explanation (Sec 4) in Algorithm 1, 2 and 3.
Algorithm 1: The algorithm of subgraph agglomeration Data: Graph G = (V, E), Label y, Target model f , Hyperparameter q. Result: Explanation tree T . Score Metric Function: φ from Algorithm 3. Initialization: score queue ScoresQ← ∅, explanation tree T ← ∅. for v ∈ V do
ScoresQ.add ( {v}, priority = φ(f, y, {v}) ) end while ScoresQ is not empty do
Select Base Subgraph Set B = ScoresQ.top(q) T.add(B) ScoresQ← ∅ for Bm ∈ B do
Candidate Subgroup Set C = Get Candidate(G, Bm) with Algorithm 2 for c ∈ C do
ScoresQ.add(c, priority = φ(f, y, c)− φ(f, y,Bm)) end
end ScoresQ = |ScoresQ− E(ScoresQ)|
end return T
Algorithm 2: The algorithm of candidate node set selection Data: Graph G = (V, E),Subgraph Bm. Result: Candidate Subgraph Set C. C ← ∅ Neighbour nodes N ← {n̄|e =< n, n̄ >, e ∈ E , n ∈ Bm, n̄ ∈ V \ Bm} for v ∈ N do C.add(Bm ∪ {v}) end return C
Algorithm 3: The algorithm of score computation φ Data: Graph G = (V, E), model f , NodeSet N Result: score φ(f, y,N ) Sample a context set S by Random Walk within the L-hop neighbor region of N . Return: φ(fD, y,N ) = 1|S| ∑ s∈S(f(N ∪ s)− f(s))

heading: C EFFICIENCY STUDY

text:
DEGREE is achieved by decomposing the feedforward process of the target model. Thus the efficiency is highly dependent on the model structure. We report the statistic of time consuming on each dataset for GCN and GAT model in Table 4.
We quantified the relationship between the size of the calculation graph and the time taken. The result is reported in Figure 4

heading: D QUALITATIVE EXPERIMENTS EXAMPLES

text:
In this section, we report more qualitative evaluation results on the Graph-SST2 and the MUTAG datasets. The results are reported in Figure 5 and 6.We also investigate the time efficiency of our agglomeration algorithm in terms of the relationship between q, the node number and the time spent.
We also investigate the time efficiency of our agglomeration algorithm in terms of the relationship between q, the node number and the time spent.

heading: E ADDITIONAL EXPERIMENTS FOR REBUTTAL

text:
E.1 QUANTITATIVE EVALUATION
In this section, we perform additional experiments comparing DEGREE with GNN-LRP Schnake et al. (2020) and SubgraphX Yuan et al. (2021). We use the MUTAG dataset and the Graph-SST2 dataset, as presented in Sec 5.1. The target model is the same as that introduced in Sec 5.2.2. Note that we modify our method to search only for nodes that boost the score of the class of interest. We employ the ACC Liang et al. (2020) as an evaluation metric. The ACC reflects the consistency of predictions based on the whole graph and between interpreted subgraphs. Thus, ACC does not require ground truth label. We further define the sparsity as the ratio of the size of the explanation subgraph to the original graph. At the same sparsity, the higher the ACC, the better the interpretation. Figure 8 shows the ACC of DEGREE, GNN-LRP and SubgraphX under various sparsity. We can find that DEGREE has competitive performance compared to GNN-LRP and SubgraphX. Besides, DEGREE has better time efficiency.
E.2 QUALITATIVE COMPARISON
In this section we make a qualitative comparison between DEGREE and SubgraphX. We randomly select a number of similar molecules and visualize the explanations generated by DEGREE and SubgraphX. We report them in the Figure 9. We can find that none of the subgraphs generated by SubgraphX include the ’N-H’ or ’N-O’. They only select the carbon ring as the important part. In contrast, DEGREE can precisely indicate that the mutagenicity is caused by the ’N-H’ or ’N-O’.
E.3 FORWARD-LOOKING EXPERIMENT
In this section, we present a simple prospective experiment from the early stages of this work. The dataset was generated by modifying the MUTAG dataset by selecting half of the graphs in the dataset and picking a node at random in each graph, giving it a special feature value of 1 while giving the other nodes a background white noise feature. Our task is to predict whether a graph contains special nodes or not. We train a 3-layer GCN which achieves 100% accuracy. We then use DEGREE to calculate the contribution score for each node. DEGREE is able to locate special nodes with 100% accuracy. Figure 10 shows the visualisation.

title: DEGREE: DECOMPOSITION BASED EXPLANATION


summaries: This paper proposes DiffStride as a drop-in replacement to standard downsampling layers. It extends previous work Spectral Poolnig and learns the size of the cropping box in the frequency domain by backpropagation. Experiments are conducted on audio and image classification, and the results show that the model can learn non-integer stride and adapt different initial stride well.

summaries: In this work the authors introduce a differentiable stride formulation, which allows for learning the stride value. To this end, they propose learning the size of a cropping mask in the Fourier domain, which allows for learning how to perform resize in a differentiable way. Authors present experiments on several datasets on different domains (image, audio), including large scale datasets.

summaries: In this paper, the authors propose DiffStride, a technique for learning the stride of downsampling operations in neural networks by gradient descent. Specifically, similarily to SpectralPool, the feature map is transformed to the frequency domain by a Discrete Fourier Transform, where it is then cropped according to learnable parameters. The authors envision a simple soft-relaxation of the cropping in order to allow the gradient to flow towards cropping parameters. Performances against both standard and random stride policies are reported on a number of datasets, both for audio and image recognition. Moreover, the authors introduce a regularization objective that penalizes the use of small strides, in the interest of encouraging downsampling for improving computational and memory cost.

summaries: This paper proposes an approach to learning optimal striding parameters in convolutional networks. The proposed approach, DiffStride, is a downsampling layer that builds on spectral pooling to allow for integer output dimensions, but arbitrary strides by cropping in the Fourier domain. Unlike spectral pooling, DiffStride relaxes the parameters of the cropping mask to be differentiable, and using the stop-gradient operator in the cropping. Results show that the proposed approach can work well as a drop-in replacement for normally fixed pooling layers. It is also demonstrated that from different random initialisations a variety of different pooling approaches can be learned that acheive similar performance. Use of a regularisation term the attempts to encourage time and space efficiency reduces this variability and allows accuracy to be traded off.

abstractText: Convolutional neural networks typically contain several downsampling operators, such as strided convolutions or pooling layers, that progressively reduce the resolution of intermediate representations. This provides some shift-invariance while reducing the computational complexity of the whole architecture. A critical hyperparameter of such layers is their stride: the integer factor of downsampling. As strides are not differentiable, finding the best configuration either requires crossvalidation or discrete optimization (e.g. architecture search), which rapidly become prohibitive as the search space grows exponentially with the number of downsampling layers. Hence, exploring this search space by gradient descent would allow finding better configurations at a lower computational cost. This work introduces DiffStride, the first downsampling layer with learnable strides. Our layer learns the size of a cropping mask in the Fourier domain, that effectively performs resizing in a differentiable way. Experiments on audio and image classification show the generality and effectiveness of our solution: we use DiffStride as a drop-in replacement to standard downsampling layers and outperform them. In particular, we show that introducing our layer into a ResNet-18 architecture allows keeping consistent high performance on CIFAR10, CIFAR100 and ImageNet even when training starts from poor random stride configurations. Moreover, formulating strides as learnable variables allows us to introduce a regularization term that controls the computational complexity of the architecture. We show how this regularization allows trading off accuracy for efficiency on ImageNet.

authors:
Dario Amodei
Sundaram Ananthanarayanan
Rishita Anubhai
Jingliang Bai
Eric Battenberg
Carl Case
Jared Casper
Bryan Catanzaro
Qiang Cheng
Guoliang Chen

title: Deep speech 2: End-toend speech recognition in english and mandarin

venue: In International conference on machine learning,

authors:
Bowen Baker
Otkrist Gupta
Nikhil Naik
Ramesh Raskar

title: Designing neural network architectures using reinforcement learning

venue: In 5th International Conference on Learning Representations,

authors:
Irwan Bello
William Fedus
Xianzhi Du
Ekin Dogus Cubuk
A. Srinivas
Tsung-Yi Lin
Jonathon Shlens
Barret Zoph

title: Revisiting resnets: Improved training and scaling strategies

authors:
Yoshua Bengio
Nicholas Léonard
Aaron Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

venue: arXiv preprint arXiv:1308.3432,

authors:
Simone Bianco
Rémi Cadène
Luigi Celona
Paolo Napoletano

title: Benchmark analysis of representative deep neural network architectures

venue: IEEE Access,

title: Online learning and stochastic approximations

venue: On-line learning in neural networks,

authors:
Y-Lan Boureau
Jean Ponce
Yann LeCun

title: A theoretical analysis of feature pooling in visual recognition

venue: In Proceedings of the 27th international conference on machine learning

authors:
S. Chopra
R. Hadsell
Y. LeCun

title: Learning a similarity metric discriminatively, with application to face verification

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition

authors:
Alexis Conneau
Holger Schwenk
Loı̈c Barrault
Yann

title: Lecun. Very deep convolutional networks for text classification

venue: In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers,

authors:
Zihang Dai
Hanxiao Liu
Quoc V Le
Mingxing Tan

title: Coatnet: Marrying convolution and attention for all data sizes

venue: arXiv preprint arXiv:2106.04803,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: In 2009 IEEE conference on computer vision and pattern recognition,

authors:
Alexey Dosovitskiy
Lucas Beyer
Alexander Kolesnikov
Dirk Weissenborn
Xiaohua Zhai
Thomas Unterthiner
Mostafa Dehghani
Matthias Minderer
Georg Heigold
Sylvain Gelly

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: In International Conference on Learning Representations,

authors:
Taffeta M Elliott
Frédéric E Theunissen

title: The modulation transfer function for speech intelligibility

venue: PLoS computational biology,

authors:
Jesse Engel
Cinjon Resnick
Adam Roberts
Sander Dieleman
Douglas Eck
Karen Simonyan
Mohammad Norouzi

title: Neural Audio Synthesis of Musical Notes with WaveNet Autoencoders

venue: Technical report,

authors:
Adeen Flinker
Werner K Doyle
Ashesh D Mehta
Orrin Devinsky
David Poeppel

title: Spectrotemporal modulation provides a unifying framework for auditory cortical asymmetries

venue: Nature human behaviour,

authors:
Eduardo Fonseca
Andrés Ferraro
Xavier Serra

title: Improving sound event classification by increasing shift invariance in convolutional neural networks

authors:
Pierre Foret
Ariel Kleiner
Hossein Mobahi
Behnam Neyshabur

title: Sharpness-aware minimization for efficiently improving generalization

title: Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position

venue: Biological Cybernetics,

authors:
Jonas Gehring
Michael Auli
David Grangier
Denis Yarats
Yann N Dauphin

title: Convolutional sequence to sequence learning

authors:
Xavier Glorot
Antoine Bordes
Yoshua Bengio

title: Deep sparse rectifier neural networks

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

title: Fractional max-pooling

venue: arXiv preprint arXiv:1412.6071,

authors:
Caglar Gulcehre
Kyunghyun Cho
Razvan Pascanu
Yoshua Bengio

title: Learned-norm pooling for deep feedforward and recurrent neural networks

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

title: Identity mappings in deep residual networks

venue: In European conference on computer vision,

authors:
Toni Heittola
Annamaria Mesaros
Tuomas Virtanen

title: TUT Urban Acoustic Scenes 2018

venue: Development dataset,

title: What’s wrong with convolutional nets. MIT Brain and Cognitive Sciences-Fall Colloquium Series, Dec 2014a

authors:
Andrew G. Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision

venue: applications. ArXiv,

authors:
Andrew G. Howard
Mark Sandler
Grace Chu
Liang-Chieh Chen
Bo Chen
Mingxing Tan
Weijun Wang
Yukun Zhu
Ruoming Pang
Vijay Vasudevan
Quoc V. Le
Hartwig Adam

title: Searching for mobilenetv3

venue: IEEE/CVF International Conference on Computer Vision (ICCV),

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Patrick W Hullett
Liberty S Hamilton
Nima Mesgarani
Christoph E Schreiner
Edward F Chang

title: Human superior temporal gyrus organization of spectrotemporal modulation tuning derived from speech stimuli

venue: Journal of Neuroscience,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

authors:
Chen Jin
Ryutaro Tanno
Thomy Mertzanidou
Eleftheria Panagiotaki
Daniel C. Alexander

title: Learning to downsample for segmentation of ultra-high resolution images, 2021

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In ICLR (Poster),

authors:
Qiuqiang Kong
Yin Cao
Turab Iqbal
Yuxuan Wang
Wenwu Wang
Mark D Plumbley

title: Panns: Large-scale pretrained audio neural networks for audio pattern recognition

venue: IEEE/ACM Transactions on Audio, Speech, and Language Processing,

title: Learning multiple layers of features from tiny images

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

authors:
Scinob Kuroki
Masataka Sawayama
Shin’ya Nishida

title: Haptic texture perception on 3d-printed surfaces transcribed from visual natural textures

venue: In International Conference on Human Haptic Sensing and Touch Enabled Computer Applications,

authors:
Yann LeCun
Bernhard Boser
John Denker
Donnie Henderson
Richard Howard
Wayne Hubbard
Lawrence Jackel

title: Handwritten digit recognition with a back-propagation network

authors:
Chen-Yu Lee
Patrick W Gallagher
Zhuowen Tu

title: Generalizing pooling functions in convolutional neural networks: Mixed, gated, and tree

venue: In Artificial intelligence and statistics,

title: Understanding Digital Signal Processing (2nd Edition)

venue: Prentice Hall PTR, USA,

authors:
Hannah Muckenhirn
M. Magimai.-Doss
S. Marcel

title: Towards directly modeling raw speech signal for speaker verification using cnns

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Biswajit Paria
Chih-Kuan Yeh
N. Xu
B. Póczos
Pradeep Ravikumar
I.E. Yen

title: Minimizing flops to learn efficient sparse representations

title: On the momentum term in gradient descent learning algorithms

venue: Neural networks : the official journal of the International Neural Network Society,

authors:
Antônio H. Ribeiro
Thomas B. Schön

title: How convolutional neural networks deal with aliasing

venue: IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP,

authors:
Oren Rippel
Jasper Snoek
Ryan P Adams

title: Spectral representations for convolutional neural networks

venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume

title: The statistics of natural images. Network: computation in neural systems

authors:
Faraz Saeedan
Nicolas Weber
Michael Goesele
Stefan Roth

title: Detail-preserving pooling in deep networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Tom Sercu
Christian Puhrsch
Brian Kingsbury
Yann LeCun

title: Very deep multilingual convolutional neural networks for lvcsr

venue: In 2016 IEEE international conference on acoustics, speech and signal processing (ICASSP),

authors:
Nandini C Singh
Frédéric E Theunissen

title: Modulation spectra of natural sounds and ethological theories of auditory processing

venue: The Journal of the Acoustical Society of America,

authors:
Dan Stowell
— Mike Wood
— Hanna Pamuła
Yannis Stylianou
Hervé Glotin

title: Automatic acoustic detection of birds through deep learning: the first Bird Audio Detection challenge

authors:
Sainbayar Sukhbaatar
Édouard Grave
Piotr Bojanowski
Armand Joulin

title: Adaptive attention span in transformers

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors:
Christian Szegedy
Wei Liu
Yangqing Jia
Pierre Sermanet
Scott Reed
Dragomir Anguelov
Dumitru Erhan
Vincent Vanhoucke
Andrew Rabinovich

title: Going deeper with convolutions

authors:
Marco Tagliasacchi
Beat Gfeller
Félix de Chaumont Quitry
Dominik Roblek

title: Self-supervised audio representation learning for mobile devices

venue: arXiv preprint arXiv:1905.11796,

authors:
Hossein Talebi
Peyman Milanfar

title: Learning to resize images for computer vision

venue: tasks. ICCV,

authors:
Mingxing Tan
Quoc Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

authors:
Mingxing Tan
Bo Chen
Ruoming Pang
Vijay Vasudevan
Mark Sandler
Andrew Howard
Quoc V Le

title: Mnasnet: Platform-aware neural architecture search for mobile

authors:
Aäron van den Oord
Nal Kalchbrenner
Lasse Espeholt
K. Kavukcuoglu
Oriol Vinyals
A. Graves

title: Conditional image generation with pixelcnn decoders

venue: In NIPS,

title: Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition

authors:
P Yin
J Lyu
S Zhang
S Osher
YY Qi
J Xin

title: Understanding straight-through estimator in training activation quantized neural nets

authors:
Neil Zeghidour
Qiantong Xu
Vitaliy Liptchinsky
Nicolas Usunier
Gabriel Synnaeve
Ronan Collobert

title: Fully convolutional speech recognition

venue: arXiv preprint arXiv:1812.06864,

authors:
Hao Zhang
Jianwei Ma

title: Hartley spectral pooling for deep learning

venue: arXiv preprint arXiv:1810.04028,

title: Making convolutional networks shift-invariant again

venue: In ICML,

authors:
Barret Zoph
Quoc V. Le

title: Neural architecture search with reinforcement learning. 2017

venue: URL https://arxiv.org/abs/1611.01578

authors: Tan Le

title: 2019), a lightweight model discovered by architecture

heading: 1 INTRODUCTION

text:
Convolutional neural networks (CNNs) (Fukushima, 1980; LeCun et al., 1989) have been the most widely used neural architecture across a wide range of tasks, including image classification (Krizhevsky et al., 2012; He et al., 2016a; Huang et al., 2017; Bello et al., 2021), audio pattern recognition (Kong et al., 2020), text classification (Conneau et al., 2017), machine translation (Gehring et al., 2017) and speech recognition (Amodei et al., 2016; Sercu et al., 2016; Zeghidour et al., 2018). Convolution layers, which are the building block of CNNs, project input features to a higher-level representation while preserving their resolution. When composed with non-linearities and normalization layers, this allows for learning rich mappings at a constant resolution, e.g. autogressive image synthesis (van den Oord et al., 2016). However, many tasks infer high-level low-resolution information (identity of a speaker (Muckenhirn et al., 2018), presence of a face (Chopra et al., 2005)) by integrating over low-level, high-resolution measurements (waveform, pixels). This integration requires extracting the right features, discarding irrelevant information over several downsampling steps. To that end, pooling layers and strided convolutions aggressively reduce the resolution of their inputs, providing several benefits. First, they act as a bottleneck that forces features to focus on information relevant to the task at hand. Second, pooling layers such as low-pass filters (Zhang, 2019) improve shift-invariance. Third, a reduced resolution implies a reduced number of floating-point operations and a higher receptive field in the subsequent layers.
Pooling layers can usually be decomposed into two basic steps: (1) computing local statistics densely over the whole input (2) sub-sampling these statistics by an integer striding factor. Past work has mostly focused on improving (1), by proposing better alternatives to max and average pooling that avoid aliasing (Zhang, 2019; Fonseca et al., 2021), preserve the important local details (Saeedan et al., 2018), or adapt to the training data distribution (Gulcehre et al., 2014; Lee et al., 2016). Ob-
serving that integer strides reduce resolution too quickly (e.g. a (2, 2) striding reduces the output size by 75%), Graham (2014) proposed fractional max-pooling, that allows for fractional (i.e. rational) strides, allowing for integration of more downsampling layers into a network. Similarly, Rippel et al. (2015) introduce spectral pooling which, by cropping its inputs in the Fourier domain, performs downsampling with fractional strides while emphasizing lower frequencies.
While fractional strides give more flexibility in designing downsampling layers, they increase the size of an already gigantic search space. Indeed, as strides are hyperparameters, finding the best combination requires cross-validation or architecture search (Zoph & Le, 2017; Baker et al., 2017; Tan et al., 2019), which rapidly become infeasible as the number of configurations grows exponentially with the number of downsampling layers. This led Zoph & Le (2017) not to search for strides in most of their experiments. Talebi & Milanfar (2021) and Jin et al. (2021) proposed a neural network that learns a resizing function for natural images, but the scaling factor (i.e. the stride) still required cross-validation. Thus, the nature of strides as hyperparameters — rather than trainable parameters — hinders the discovery of convolutional architectures and learning strides by backpropagation would unlock a virtually infinite search space.
In this work, we introduce DiffStride, the first downsampling layer that learns its strides jointly with the rest of the network. Inspired by Rippel et al. (2015), DiffStride casts downsampling in the spatial domain as cropping in the frequency domain. However, and unlike Rippel et al. (2015), rather than cropping with a fixed bounding box controlled by a striding hyperparameter, DiffStride learns the size of its cropping box by backpropagation. To do so, we propose a 2D version of an attention window with learnable size proposed by Sukhbaatar et al. (2019) for language modeling. On five audio classification tasks, using DiffStride as a drop-in replacement to strided convolutions improves performance overall while providing interpretability on the optimal per-task receptive field. By integrating DiffStride into a ResNet-18 (He et al., 2016a), we show on CIFAR (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) that even when initializing strides randomly, our model converges to the best performance obtained with the properly cross-validated strides of He et al. (2016a). Moreover, casting strides as learnable parameters allows us to propose a regularization that directly minimizes computation and memory usage.

heading: 2 METHODS

text: We first provide background on spatial and spectral pooling, and propose DiffStride for learning strides of downsampling layers. We focus on 2D CNNs since they are generic enough to be used for image (LeCun et al., 1989; Krizhevsky et al., 2012; He et al., 2016a) and audio (Amodei et al., 2016; Kong et al., 2020) processing (taking time-frequency representations as inputs). However, these methods are equally applicable to the 1D (e.g. time-series) and 3D (e.g. video) cases.

heading: 2.1 NOTATIONS

text:
Let x ∈ RH×W , its Discrete Fourier Transform (DFT) y = F(x) ∈ CH×W is obtained through the decomposition on a fixed set of basis filters (Lyons, 2004):
F(x)mn = 1√ HW H−1∑ h=0 W−1∑ w=0 xhwe −2πi(mhH + nw W ),∀m ∈ {0, . . . ,H − 1},∀n ∈ {0, . . . ,W − 1}.
(1)
The DFT transformation is linear and its inverse is given by its conjugate F(.)−1 = F(.)∗. The Fourier transform of a real-valued signal x ∈ RH×W being conjugate symmetric (Hermitiansymmetry), we can reconstruct x from the positive half frequencies for the width dimension and omit the negative frequencies (ymn = y∗(H−m)modH,(W−n)modW ). In addition, the DFT and its inverse are differentiable with regard to their inputs and the derivative of the DFT (resp. inverse DFT) is its conjugate linear operator, i.e. the inverse DFT (resp. DFT). More formally, if we consider L : CH×W −→ R as a loss taking as input the Fourier representation y, we can compute the gradient of L with regard to x, by using the inverse DFT:
x ∈ RH×W , y = F(x), ∂L ∂x = F∗(∂L ∂y ) = F−1(∂L ∂y ). (2)
We denote by L the total number of convolution layers in a CNN architecture and each layer is indexed by l. The ◦ symbol represents the element-wise product between two tensors, b.c is the floor operation and ⊗ the outer product between two vectors. S represents the stride parameters, and sg is the stop gradient operator (Bengio et al., 2013; Yin et al., 2019), defined has the identity function during forward pass and with zero partial derivatives.

heading: 2.2 DOWNSAMPLING IN CONVOLUTIONAL NEURAL NETWORKS

text: A basic mechanism for downsampling representations in a CNN is strided convolutions which jointly convolve inputs and finite impulse response filters and downsample the output. Alternatively, one can disentangle both operations by first applying a non-strided convolution followed by a pooling operation that computes local statistics (e.g. using an average, max (Boureau et al., 2010)) before downsampling. In both settings, downsampling does not benefit from the global structure of its inputs and can discard important information (Hinton, 2014; Saeedan et al., 2018). Moreover, and as observed by Graham (2014), the integer nature of strides only allows for drastic reductions in resolution: a 2D-convolution with strides S = (2, 2) reduces the dimension of its inputs by 75%. Furthermore, stride configurations are cumbersome to explore as the number of stride combinations grows exponentially with the number of downsampling layers. This means that cross-validation can only explore a limited subset of the stride hyperparameter configurations. This limitation is likely to translate into lower performance, as Section 3.2 shows that an inappropriate choice of strides for a ResNet-18 architecture can account for a drop of > 18% in accuracy on CIFAR-100.

heading: 2.3 SPECTRAL POOLING

text:
Energy of natural signals is typically not uniformly distributed in the frequency domain, with signals such as sounds (Singh & Theunissen, 2003), images (Ruderman, 1994) and surfaces (Kuroki et al., 2018) concentrating most of the information in the lower frequencies. Rippel et al. (2015) build on this observation to introduce spectral pooling which alleviates the loss of information of spatial pooling, while enabling fractional downsizing factors. Spectral pooling also preserves low frequencies without aliasing, a known weakness of spatial/temporal convnets (Zhang, 2019; Ribeiro & Schön, 2021).
We consider an input x ∈ RH×W and strides S = (Sh, Sw) ∈ [1, H) × [1,W ). First, the DFT is computed y = F(x) ∈ CH×W and for simplicity we assume that the center of this matrix is the DC component — the zero frequency. Then, a bounding box of size b HSh c × b W Sw c crops this matrix around its center to produce ỹ ∈ Cb H Sh c×b WSw c. Finally, this output is brought back to the spatial domain with an inverse DFT: x̃ = F−1(ỹ) ∈ Rb H Sh c×b WSw c. In practice, x is typically a multichannel input (i.e. x ∈ RH×W×C) and the same cropping is applied to all channels. Moreover, since x is real-valued and thanks to Hermitian symmetry (see Section 2.1 for more details), only the positive half of the DFT coefficients are computed, which allows saving computation and memory while ensuring that the output x̃ remains real-valued.
Unlike spatial pooling that requires integer strides, spectral pooling only requires integer output dimensions, which allows for much more fine-grained downsizing. Moreover, spectral pooling acts as a low-pass filter over the entire input, only keeping the lower frequencies i.e. the most relevant information in general and avoiding aliasing (Zhang, 2019). However, and similarly to spatial pooling, spectral pooling is differentiable with respect to its inputs but not with respect to its strides. Thus, one still needs to provide S as hyperparameters for each downsampling layer. In this case, the search space is even bigger than with spatial pooling since strides are not constrained to integer values anymore.

heading: 2.4 DIFFSTRIDE

text:
To address the difficulty of searching stride parameters, we propose DiffStride, a novel downsampling layer that allows spectral pooling to learn its strides through backpropagation. To downsample x ∈ RH×W , DiffStride performs cropping in the Fourier domain similarly to spectral pooling. However, instead of using a fixed bounding box, DiffStride learns the box size via backpropagation. The learnable boxW is parametrized by the shape of the input, a smoothness factor R and the strides.
We design this maskW as the outer product between two differentiable 1D masking functions (depicted in the lower right corner of Figure 1), one along the horizontal axis and one along the vertical axis. These 1D masks are directly derived from the adaptive attention span introduced by Sukhbaatar et al. (2019) to learn the attention span of self-attention models for natural language processing. Exploiting the conjugate symmetry of the coefficients, we only consider positive frequencies along the horizontal axis, while we mirror the vertical mask around frequency zero. Therefore, the two masks are defined as follows:
maskh(Sh,H,R)(m) = min
[ max [ 1
R (R+
H 2Sh − |H 2 −m|), 0
] , 1 ] ,m ∈ [0, H] (3)
maskw(Sw,W,R)(n) = min
[ max [ 1
R (R+
W
2Sw + 1− n), 0
] , 1 ] , n ∈ [0, W
2 + 1] (4)
where S = (Sh, Sw) are the strides and R an hyperparameter that controls the smoothness of the mask. We build the 2D differentiable maskW as the outer product between the two 1D masks:
W(Sh, Sw, H,W,R) = maskh(Sh,H,R) ⊗mask w (Sw,W,R) (5)
We useW in two ways: (1) we apply it to the Fourier representation of the inputs via an elementwise product, which performs low-pass filtering (2) we crop the Fourier coefficients where the mask is zero (i.e. the output has dimensions b HSh + 2×Rc × b W Sw + 2×Rc).
The first step is differentiable with respect to strides S, however the cropping operation is not. Therefore, we apply a stop gradient operator (Bengio et al., 2013) to the mask before cropping. This way, gradients can flow to the strides through the differentiable low-pass filtering operation, but not through the non-differentiable cropping. Finally, the cropped tensor is transformed back into the spatial domain using an inverse DFT. All these steps are summarized by Algorithm 1 and illustrated on a single channel image in the Figure 1.
During training we constrain strides S = (Sh, Sw) to remain in [1, H) × [1,W ). When x is a multi-channel input (i.e. x ∈ RH×W×C), we learn the same strides S for all channels to ensure uniform spatial dimensions across channels. In spatial and spectral pooling, strides are typically tied along the spatial axes (i.e. Sw = Sh), which we can also do in DiffStride by sharing a single learnable stride on both dimensions. However, our experiments in Section 3 show that learning
Algorithm 1: DiffStride layer Inputs : Input x ∈ RH×W , strides S = (Sh, Sw) ∈ [1, H)× [1,W ), smoothness factor R. Output: Downsampled output x̃ ∈ Rb H Sh +2×Rc×b WSw +2×Rc
specific strides for the vertical and horizontal axis is beneficial, not only when processing timefrequency representations of audio, but also — more surprisingly— when classifying natural images. Adding an hyperparameter R to each downsampling layer would conflict with the goal of removing strides as hyperparameters. Thus, not only we use a single R value for all layers, but we found no significant impact of this choice and all our experiments use R = 4. While we focus on the 2D case, using a single 1D mask allows deriving DiffStride in 1D CNNs, while performing the outer product between three 1D masks allows applying DiffStride to 3D inputs.

heading: 2.4.1 RESIDUAL BLOCK WITH DIFFSTRIDE

text: Unlike systems that only feed outputs of the lth layer to the (l + 1)th (Krizhevsky et al., 2012), ResNets (He et al., 2016a;b) introduce skip-connections that operate in parallel to the main branch. ResNets stack two types of blocks: (1) identity blocks that maintain the input channel dimension and spatial resolution and (2) shortcut blocks that increase the output channel dimension while reducing the spatial resolution with a strided convolution (see Figure 2a). We integrate DiffStride into these shortcut blocks by replacing strided convolutions by convolutions without strides followed by DiffStride. Besides, sharing DiffStride strides between the main and residual branches ensures that their respective outputs have identical spatial dimensions and can be summed (See Figure 2b).

heading: 2.4.2 REGULARIZING COMPUTATION AND MEMORY COST WITH DIFFSTRIDE

text:
The number of activations in a network depends on the strides and learning these parameters gives control over the space and time complexity of an architecture in a differentiable manner. This contrasts with previous work, as measures of complexity such as the number of floating-point operations (FLOPs) are typically not differentiable with respect to the parameters of a model and searching for efficient architectures is done via high-level exploration (e.g. introducing separable convolutions (Howard et al., 2017)), architecture search (Howard et al., 2019; Tan & Le, 2019) or using continuous relaxations of complexity (Paria et al., 2020).
A standard 2D convolution with a square kernel of size k2 and C ′ output channels has a computational cost of k2×C×C ′×H×W when operating on x ∈ RH×W×C . Its memory usage— in terms of the number of activations to store— is C ′ × H ×W . Considering a fixed number of channels and kernel size, both the computational complexity and memory usage of a convolution layer are thus linear functions of its input size H ×W . This illustrates our argument made in Section 1 that
downsampling does not only improve performance by discarding irrelevant information, but also reduces the complexity of the upper layers. More importantly, in the context of DiffStride the input size H l ×W l of layer l is determined as follows: H l ×W l = bH l−1
Sl−1h +2×Rc × bW
l−1
Sl−1w +2×Rc,
which is differentiable with respect to the strides at the previous layer Sl−1. Furthermore, it also depends on spatial dimensions at the previous layer H l−1×W l−1, which themselves are a function of Sl−2. By induction over layers, the total computational cost and memory usage are proportional to ∑l=L l=1 ∏l i=1
1 Sih×Siw . Since in the context of DiffStride the kernel size and number of channels remain constant during training, we can directly regularize our model towards time and space efficiency by adding the following regularizer to our training loss:
λJ((Sl)l=Ll=1 ) = λ l=L∑ l=1 l∏ i=1
1
Sih × Siw , (6)
where λ is the regularization weight. In Section 3.2, we show that training on ImageNet with different values for λ allows us to trade-off accuracy for efficiency in a smooth fashion.

heading: 3 EXPERIMENTS

text: We evaluate DiffStride on eight classification tasks, both on audio and images. For each comparison, we keep the same architecture and replace strided convolutions by convolutions with no stride followed by DiffStride. To avoid the confounding factor of downsampling in the Fourier domain, we also compare our approach to the spectral pooling of Rippel et al. (2015), which only differs from DiffStride by the fact that its strides are not learnable.

heading: 3.1 AUDIO CLASSIFICATION

text:
Experimental setup We perform single-task and multi-task audio classification on 5 tasks: acoustic scene classification (Heittola et al., 2018), birdsong detection (Stowell et al., 2018), musical instrumental classification and pitch estimation on the NSynth dataset (Engel et al., 2017) and speech command classification (Warden, 2018). The statistics of the datasets are summarized in Table A.1. The audio sampled at 16 kHz is decomposed into log-compressed mel-spectrograms with 64 channels, computed with a window of 25ms every 10ms.
A 2D-CNN, based on (Tagliasacchi et al., 2019) takes these spectrograms as inputs and alternates blocks of strided convolutions along time ((3×1) kernel) and frequency ((1×3) kernel). Each strided convolution is followed by a ReLU (Glorot et al., 2011) and batch normalization (Ioffe & Szegedy, 2015). The sequence of channels dimensions is defined as (64, 128, 256, 256, 512, 512) and the strides are initialized as ((2, 2), (2, 2), (1, 1), (2, 2), (1, 1), (2, 2) for all downsampling methods. The output of the CNN passes through a global max-pooling and feeds into a single linear classification layer for single-task, and multiple classification layers for multi-task classification. As examples vary in length, we train models on random 1 s windows with ADAM (Kingma & Ba, 2015) and a learning rate of 10−4 for 1M batches, with batch size 256. Evaluation is run by splitting full sequences into 1 s non-overlapping windows and averaging the logits over windows.
Results Table 1 summarizes the results for single-task and multi-task audio classification. In both settings, DiffStride improves over strided convolutions and spectral pooling, with strided convolutions only outperforming DiffStride for acoustic scene classification in the single task setting. Table 2 shows the strides learned by the first layer of DiffStride, which downsamples mel-spectrograms along frequency and time axes. Learning allows the strides to deviate from their initialization ((2, 2)) and to adapt to the task at hand. Converting strides to cut-off frequencies shows that the learned strides fall in a range showed by behavioral studies and direct neural recordings (Hullett et al., 2016; Flinker et al., 2019) to be necessary for e.g. speech intelligibility at 25Hz (Elliott & Theunissen, 2009). Moreover, DiffStride learns different strides for the time and frequency axes. Table A.7 shows the benefits of learning a per-dimension value rather than sharing strides. Another notable phenomenon is the per-task discrepancy on NSynth, with the pitch estimation requiring faster spectral modulations (as represented by a higher cutt-off frequency along the frequency axis). Finally, multi-task models do not converge to the mean of strides, but rather to a higher value that passes more frequencies not to negatively impact individual tasks.

heading: 3.2 IMAGE CLASSIFICATION

text:
Experimental setup We use the ResNet-18 (He et al., 2016a) architecture, comparing the original strided convolutions (see Figure 2a) to spectral pooling and DiffStride (both as in Figure 2b). We randomly sample 6 striding configurations for the three shortcut blocks of the ResNet-18, each stride being sampled in [1, 3], with (2, 2, 2) being the configuration of the original ResNet of He et al. (2016a). The horizontal and vertical strides are initialized equally at start. These random configurations simulate cross-validation of stride configurations to: (1) showcase the sensitivity of the architecture to these hyperparameters, (2) test our hypothesis that DiffStride can benefit from learning its strides to recover from a poor initialization. On Imagenet, as inputs are bigger than CIFAR we also allow the first ResNet-18 identity block to learn its strides which are 1 by default.
We first benchmark the three methods on the two CIFAR datasets (Krizhevsky, 2009). CIFAR10 consists of 32 × 32 images labeled in 10 classes with 6000 images per class. We use the official split, with 50,000 images for training and 10,000 images for testing. CIFAR100 uses the same images as CIFAR10, but with a more detailed labelling with 100 classes. We also compare the ResNet-18 architectures on the ImageNet dataset (Deng et al., 2009), which contains 1,000 classes. The models are trained on the official training split of the Imagenet dataset (1.28M images) and we report our results on the validation set (50k images). Here, we evaluate performance in terms of top-1 and top-5 accuracy. We train on all datasets with stochastic gradient descent (SGD) (Bottou et al., 1998) with a learning rate of 0.1, a batch size of 256 and a momentum (Qian, 1999) of 0.9. On CIFAR, we train models for 400 epochs dividing the learning rate by 2 at 200 epochs and again by 2 at 300 epoch, with a weight decay of 5.10−3. For CIFAR, we apply random cropping on the input images and left-right random flipping. On ImageNet, we train with a weight decay of 1.10−3 for 90 epochs, dividing the learning rate by 10 at epochs 30, 60 and 80. We apply random cropping on the input images as in (Szegedy et al., 2015) and left-right random flipping.
Results We report the results on the CIFAR datasets and Imagenet in Tables 3 and 4 respectively, with the accuracy of our baseline ResNet-18 (first row, Strided Conv.) being consistent with previous work (Bianco et al., 2018). First, we observe that strides are indeed critical hyperparameters for the performance of a standard ResNet-18 on the three datasets, with the accuracy on CIFAR100 dropping from 66.8% average to 48.2% between the best and worst configurations. Remarkably,
spectral pooling is much more robust to bad initializations than strided convolutions, even though its strides are also fixed. However, DiffStride is overall much more robust to poor choices of strides, converging consistently to a high accuracy on the three datasets, with a variance over initializations that is lower by an order of magnitude. This shows that backpropagation allows DiffStride to find a better configuration during training avoiding a cross-validation which would require 6,561 experiments for testing all combinations of strides in [1, 3] on Imagenet. Tables A.5 and A.6 confirm these observations on the EfficientNet-B0 (Tan & Le, 2019) architecture.
Learning dynamics and equivalence classes Figure 3 illustrates the learning dynamics of DiffStride on CIFAR10. Figure 3a plots the strides as a function of the epoch for a run with the baseline (2,2,2) configuration as initialization. The strides all deviate from their initialization while converging rapidly, with the lower layers keeping more information while higher layers downsample more drastically. Interestingly, we discover equivalence classes: despite converging to the same accuracy (as reported in Table 3) the various initializations yield very diverse strides configurations at convergence, both in terms of total striding factor (defined as the product of strides, see Figure 3c) and of repartition of downsampling factors along the architecture (see Figure 3b). We obtain similar conclusions on CIFAR100 and Imagenet (see Figures A.1 and A.2). In the non-regularized case, it could seem counter-intuitive that minimizing the training loss yields positive stride updates, i.e. dropping more information through cropping. It highlights that loss optimization is a tradeoff between preserving information (no striding, no cropping) and downscaling such that the next convolution kernel accesses a wider spatial context.
Regularizing the complexity The existence of equivalence classes suggests that DiffStride can find more computationally efficient configurations for a same accuracy. We thus train DiffStride on ImageNet using the complexity regularizer defined in Equation 6, with λ varying between 0.1 and 10, always initializing strides with the baseline ((1, 1), (2, 2), (2, 2), (2, 2)). Figure 4 plots accuracy versus computational complexity (as measured by the value of the regularization term at convergence) of DiffStride. For comparison, we also plot the models with strided convolutions with the random initializations of Table 4, showing that DiffStride finds configurations with a lower
computational cost for the same accuracy. Some of these are quite extreme, e.g. with λ = 10 a model converges to strides ((10.51, 32.23), (1.20, 2.68), (1.20, 2.04), (1.96, 4.53)) for a 58.57% top-1 accuracy. When training a ResNet-18 with strided convolutions using the closest integer strides (i.e. ((11, 32), (1, 3), (1, 2), (2, 5))), the model converges to a 24.54% top-1 accuracy. This suggests that performing pooling in the spectral domain is more robust to aggressive downsampling, which corroborates the remarkable advantage of spectral pooling over strided convolutions when using poor strides choices in Tables 3 and 4 despite both models having fixed strides.
Limitations Pooling in the spectral domain comes at higher computational cost than strided convolutions as it requires (1) computing a non-strided convolution and (2) a DFT and its inverse (see Table A.2). This could be alleviated by computing the convolution in the Fourier domain as an element-wise multiplication and summation over channels. Further improvements could be obtained by replacing the DFT by a real-valued counterpart, such as the Hartley transform (Zhang & Ma, 2018), which would remove the need for complex-valued operations that may be poorly optimized in deep learning frameworks. We also observe no benefits of DiffStride when training DenseNets (Huang et al., 2017), see Tables A.3 and A.4. We hypothesize that this is due to the limited number of downsampling layers, which reduces the space of stride configurations to a few, equivalent ones when sampling strides in [1; 3]. Finally, some hardware (e.g. TPUs) require a static computation graph. As DiffStride changes the spatial dimensions of intermediate representations— and thus the computation graph— between each gradient update, we currently only train on GPUs.

heading: 4 CONCLUSION AND FUTURE WORK

text: We introduce DiffStride the first downsampling layer with learnable strides. We show on audio and image classification that DiffStride can be used as a drop-in replacement to strided convolutions, removing the need for cross-validating strides. As we observe that our method discovers multiple equally-accurate stride configurations, we introduce a regularization term to favor the most computationally advantageous. In future work, we will extend the scope of applications of DiffStride, to e.g. 1D and 3D architectures. Moreover, learning strides by backpropagation opens new avenues in designing adaptive convolutional architectures, such as multi-scale models that would learn to operate at various scales in parallel by using independent branches with separate instances of DiffStride, or by predicting strides parameters of DiffStride on a per-example basis.

heading: 5 REPRODUCIBILITY STATEMENT

text: We describe DiffStride in details in the text as well as with Algorithm 1 and Figure 1. We mention all relevant hyperparameters to reproduce our experiments, as well as describe audio datasets in A.1. Moreover, we will release Tensorflow 2.0 code for training a ResNet-18 with strided convolutions, spectral pooling or DiffStride on CIFAR10 and CIFAR100, with DiffStride being implemented as a stand-alone, reusable Keras layer.

heading: A APPENDIX

text:
Analysis of strides learned on CIFAR100 and ImageNet In Figure A.1 (Figure A.2), we show the distributions of learned strides and the global striding factor at convergence on CIFAR100 (Imagenet), starting from random stride initializations. On CIFAR100, we observe equivalence classes, i.e. model that learns various stride configurations for a same accuracy. On Imagenet, even though we also observe a significant variance of the global striding factor, models tend to downsample only in the upper layers. Striding late in the architecture comes at a higher computational cost, which furthermore justifies regularizing DiffStride to reduce complexity as shown in Section 3.2.
Time and space complexity in practice While Figure 4 reports theoretical estimates of computational complexity based on stride configurations, both spectral pooling and DiffStride require computing a DFT and its inverse. Moreover, DiffStride requires accumulating gradients with respect to the strides during training. Table A.2 reports the duration and peak memory usage of the multitask architecture described in 3.1, for a single batch. Replacing strided convolutions with spectral pooling increases the wall time by 32% due to the DFT and inverse DFT, while the peak memory usage is almost unaffected. DiffStride furthermore increases the wall time (by 43% w.r.t strided convolutions) as the backward pass is more expensive. Similarly, it almost doubles the peak memory usage. However, in inference, DiffStride does not need to compute and store gradients w.r.t. the strides, thus the time and space complexity become identical to that of spectral pooling.
DenseNet experiments on CIFAR We also evaluate DiffStride in DenseNet (Huang et al., 2017), especially the DenseNet-BC architecture with a depth of 121 and a growth rate of 32. The DenseNet architecture halves spatial dimensions during transition blocks. We replace the 2D average pooling in the transition blocks by spectral pooling or DiffStride. The considered architecture for DenseNet has two downsampling steps. We run a similar experiment as in 3.2 with random strides between the dense blocks on the two CIFAR datasets. We observe that initializing strides randomly does not affect the performance of the standard Densenet-BC architecture with average pooling. Consequently, DiffStride does not improve over alternatives.
EfficientNet experiments on CIFAR We evaluate DiffStride in an EfficientNet-B0 architecture (Tan & Le, 2019), a lightweight model discovered by architecture search. This architecture has seven strided convolutions. Unlike Tan & Le (2019), we do not pre-train on ImageNet, but rather train from scratch on CIFAR, which explains the lower accuracy of the baseline. As the model has seven downsampling layers, we rescale the images from 32 × 32 to 128 × 128, and only sample strides in [1; 2]. We run a similar experiment as in 3.2 with random strides on the two CIFAR datasets. Consistently with the results obtained with a ResNet-18, spectral pooling is much more robust to poor strides than strided convolutions, with DiffStride outperforming all alternatives.
Ablation study: learning a per-dimension stride or a shared one We perform multi-task audio classification with either learning a single stride value for each DiffStride layer, or a different one for the time and frequency axes. The overall performance across tasks is improved when learning a different stride value for each dimension (See Table A.7).