# Graph is all you need? Lightweight data-agnostic neural architecture search
without training

Zhenhan Huang
Rensselaer Polytechnic Institute
&Tejaswini Pedapati
IBM Research
&Pin-Yu Chen
IBM Research
&Chunhen Jiang
Rensselaer Polytechnic Institute
&Jianxi Gao
Rensselaer Polytechnic Institute
Corresponding author<EMAIL_ADDRESS>
###### Abstract

Neural architecture search (NAS) enables the automatic design of neural
network models. However, training the candidates generated by the search
algorithm for performance evaluation incurs considerable computational
overhead. Our method, dubbed NASGraph, remarkably reduces the computational
costs by converting neural architectures to graphs and using the average
degree, a graph measure, as the proxy in lieu of the evaluation metric. Our
training-free NAS method is data-agnostic and light-weight. It can find the
best architecture among 200 randomly sampled architectures from NAS-Bench201
in 217 CPU seconds. Besides, our method is able to achieve competitive
performance on various datasets including NASBench-101, NASBench-201, and NDS
search spaces. We also demonstrate that NASGraph generalizes to more
challenging tasks on Micro TransNAS-Bench-101.

##  1 Introduction

Neural architecture search (NAS) aims to automate the process of discovering
state-of-the-art (SOTA) deep learning models. The objective of NAS is to find
an optimal neural architecture $a^{*}=\arg\min_{a\in\mathcal{A}}f(a)$, where
$f(a)$ denotes the performance (e.g., a task-specific loss function) of the
neural architecture $a$ trained for a fixed number of epochs using a dataset,
and $\mathcal{A}$ is the search space. Previous NAS techniques achieve
competitive performance in various applications such as image classification
[1], object detection [2] and semantic segmentation [3]. The pioneering work
[4] based on reinforcement learning is resource intensive, requiring more than
20k GPU days. In particular, training the generated neural architecture
candidates to evaluate their performance is the most computationally expensive
step. To accelerate the search process, various proposals have been made,
including weight sharing [5, 6], progressive complexity search stage [7],
gradient descent in the differentiable search space [8], predictor-based NAS
techniques [9], etc. The recent emergence of training-free NAS [10, 11] pushes
the boundary of efficient NAS techniques further and greatly eases the
computational burden. Training-Free NAS computes a proxy metric in place of
accuracy to rank the candidate architectures. The proxy metric is obtained by
a single forward/backward propagation using a training dataset.

In this paper, we take a novel perspective on mapping neural networks to
graphs: we treat inputs to neural components as graph nodes and use
relationship between inputs to neighboring graph components to determine the
connectivity between pairs of graph nodes. In this way, we are able to convert
a neural architecture to a DAG $G(V,E)$ where node set
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and edge set $E=\\{e_{ij}\\}\;\forall i,j$
s.t. there exists an edge from $v_{i}$ to $v_{j}$. After establishing the
mapping, we extract the associated graph measures as NAS metrics to rank
neural architectures. We note that the entire process is training-free and
data-agnostic (i.e. do not require any training data).

We summarize our main contributions as follows:

  * •

We propose NASGraph, a training-free and data-agnostic method for NAS.
NASGraph maps the neural architecture space to the graph space. To our best
knowledge, this is the first work to apply graph theory for NAS.

  * •

Using the extracted graph measures for NAS, NASGraph achieves competitive
performance on NAS-Bench-101, NAS-Bench-201, Micro TransNAS-Bench-101 and NDS
benchmarks, when compared to existing training-free NAS methods. The analysis
of bias towards operations in the benchmarks indicates that NASGraph has the
lowest bias compared to those methods.

  * •

In comparison to existing training-free NAS techniques, we show that the
computation of NASGraph is lightweight (only requires CPU).

Figure 1: An overview of the NASGraph framework: the connectivity of graph
nodes is determined by the forward propagation of the corresponding graph
blocks. In the toy example shown in the bottom of the figure, if the output
from the forward propagation is all-zeros matrix $\mathds{O}$, there is no
connection. Otherwise, the connection is built between a pair of graph nodes.
The orange rectangles in (b) and (c) mark how a subgraph generated by a single
forward propagation constitutes a part of the whole graph.

##  2 Related Work

One-shot NAS. One-shot NAS constructs a supernet subsuming all candidate
architectures in the search space. In other words, subnetworks of the supernet
are candidate architectures. The supernet method is faster than the
conventional NAS methods because it enables weight sharing among all the
candidate architectures in the search space. The first one-shot NAS algorithm
[5] considers the operations at each edge to be a discrete decision. DARTS [8]
devises a continuous relaxation by formulating the value of the operation
applied to an edge as a weighted sum of all the operations. Several works,
e.g.[12], [13], [14] were developed to improve some shortcomings of DARTS such
as memory consumption, DARTS collapse and increase in the validation loss
after the discretization step. [15] demonstrated the discrepancy between the
ranking of architectures sampled from a trained supernet and that of the same
architectures when trained from scratch. To alleviate co-adaptation among the
operations, works such as [16], [17], recommend uniformly sampling the
candidate architectures while others recommended pruning the search space
during the search [18]. To accelerate the search process, EcoNAS [19] proposes
a hierarchical proxy strategy that uses a faster proxy for less promising
candidates and a better but slower proxy for more promising candidates.

Training-Free NAS. Training-Free NAS uses models with randomly initialized
weights to obtain the saliency metrics that rank these models. Since there is
no need for training models, this routine is considerably faster even compared
to one-shot NAS. NASWOT [10] applies the theory on the linear regions in deep
networks [20] to achieve NAS without training. The saliency metrics for the
pruning-at-initialization work in network pruning are also found to be
effective in zero-cost NAS [11]. In addition, TENAS [21] uses metrics from the
condition number of neural tangent kernel and the number of linear regions. A
comparison of saliency metrics [22] finds that these metrics might contain
complementary information and hence a combination of metrics can be helpful in
NAS.

##  3 NASGraph: A Graph-Based Framework for Data-Agnostic and Training-Free
NAS

Figure 1 shows an overview of our proposed NASGraph framework. A neural
architecture is uniquely mapped to a DAG, i.e. $a\mapsto G(V,E)$. After the
conversion, graph measures are computed to rank the performance of the
corresponding neural architectures. We also note that our notion of graph
refers to the specific graph representation of a neural architecture $a$ via
our proposed graph conversion techniques, instead of the original computation
graph of $a$.

Graph block. The basic element in the NASGraph framework is the graph block.
We use the notation $f^{(l)}(\mathbf{x}^{(l)};\mathbf{\theta}^{(l)})$ to
represent the $l$-th graph block, where $\mathbf{x}^{(l)}$ is the input to the
graph block and $\mathbf{\theta}^{(l)}$ is the model parameter. We combine
several neural components (e.g. Conv and ReLU) to a graph block such that the
output of the graph block
$y^{(l)}=f^{(l)}(\mathbf{x}^{(l)};\mathbf{\theta}^{(l)})$ is non-negative.

Conversion method. Inspired by the iterative re-evaluation method in the
network pruning [23, 24], we apply conversion to each graph block
independently. Similarly, we also use all-ones matrix as the input to the
graph block $\mathbf{x}^{(l)}=\mathds{1}^{C^{(l-1)}\times H^{(l-1)}\times
W^{(l-1)}}$ in the forward propagation process, where $C^{(l-1)}$ is the
number of channels, $H^{(l-1)}$ is the image height, and $W^{(l-1)}$ is the
image width for the input to $l$-th graph block. This helps us get an unbiased
estimate of the contribution of the input to the output. Further, to determine
the contribution of the $c$-th channel of the input on the channels of the
output for the $l$-th graph block, we apply a mask $\mathcal{M}^{(l)}_{c}$ to
the input so that only the $c$-th channel
$(\mathbf{x}^{(l)}_{d_{1}d_{2}d_{3}})_{d_{1}=c}$ is an all-ones matrix
$\mathds{1}^{H^{(l-1)}\times W^{(l-1)}}$ and other channels are zero matrices
$\mathds{O}^{H^{(l-1)}\times W^{(l-1)}}$. A toy example is shown in the bottom
of Figure 1. We evaluate the contribution of the $c$-th channel
$(\mathbf{x}^{(l)}_{d_{1}d_{2}d_{3}})_{d_{1}=c}$ to the output
$\mathbf{y}^{(l)}$ by performing a forward propagation as described by:

$\mathbf{y}_{c}^{(l)}=f^{(l)}(\mathcal{M}^{(l)}_{c}\odot\mathbf{x}^{(l)};\mathbf{\theta}^{(l)})$
(1)

where $f^{(l)}(\cdot)$ is the $l$-th graph block, $\odot$ is the Hadamard
product, and $\mathbf{\theta}^{(l)}$ is the parameters of the $l$-th graph
block. The score $\omega_{i^{(l-1)}j^{(l)}}$ for the edge $e_{ij}$ between
node $i^{(l-1)}$ and $j^{(l)}$ is determined by:

$\omega_{i^{(l-1)}j^{(l)}}=\sum_{d_{2}=1}^{H^{(l)}}\sum_{d_{3}=1}^{W^{(l)}}(({y_{i}^{(l)}})_{d_{1}d_{2}d_{3}})_{d_{1}=j}$
(2)

If $\omega_{i^{(l-1)}j^{(l)}}$ is larger than 0, we build an edge between node
$i^{(l-1)}$ and node $j^{(l)}$ that indicates the relationship between $i$-th
channel of the input $\mathbf{x}^{(l)}$ and $j$-th channel of the output
$\mathbf{y}^{(l)}$. We use a virtual input graph block of identity operation
to take the input to the neural architecture into consideration. After looping
though all graph blocks, we can uniquely construct a graph.

Analysis of the proposed method. We consider a neural component consisting of
convolution and ReLU activation function. We use $\mathcal{F}$ to represent
the neural component, $\mathcal{F}(\mathbf{x})=h\circ f(\mathbf{x})$. The
function $f(\cdot)$ is the convolution operation and $h(\cdot)$ is the ReLU
activation function.

######  Theorem 1.

Let $\mathbf{x}$ be the input to $\mathcal{F}$. $\mathcal{F}$ is converted to
a graph $G(V,E)$ using NASGraph framework: the input to $\mathcal{F}$ has
$\mathds{1}\in\mathbb{R}^{H^{(0)}\times W^{(0)}}$ for the channel $i$ and
$\mathds{O}\in\mathbb{R}^{H^{(0)}\times W^{(0)}}$ for rest of channels. There
is no edge between node i and node j if and only if the output for the channel
j is all-zeros matrix $\mathds{O}\in\mathbb{R}^{H^{(1)}\times W^{(1)}}$.

We provide the proof in Appendix A.1. Recall that we use $\mathds{1}$ as input
to $\mathcal{F}$ to make an unbiased estimate on the contribution of the input
to the output. Hence, an output of $\mathds{O}$ means there exists a
contribution from the input to the output, which is inferior to the
performance of neural architecture. Theorem 1 indicates that the connectivity
between graph nodes is associated with the neural architecture performance.
Hence, we can use graph measures that are sensitive to node connectivity as
the metrics to rank neural architectures.

Table 1: Comparison of the ranking correlation between NASGraph and training-
free NAS methods using single metric on NAS-Bench-201. Correlations are
calculated between the metrics and test accuracies.

Method | Metric |  | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
---|---|---|---|---|---|---|---
| $\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$
NASWOT | naswot |  | 0.76 | 0.57 |  | 0.79 | 0.61 |  | 0.71 | 0.55
ZiCo‡ | zico |  | 0.74 | 0.55 |  | 0.78 | 0.58 |  | 0.76 | 0.56
TENAS | NTK |  | - | - |  | - | -0.42 |  | - | -
NLR | - | - |  | - | -0.50 |  | - | - | -
Zero-Cost NAS | grad_norm |  | 0.58 | 0.42 |  | 0.64 | 0.47 |  | 0.58 | 0.43
snip |  | 0.58 | 0.43 |  | 0.63 | 0.47 |  | 0.58 | 0.43
grasp |  | 0.48 | 0.33 |  | 0.54 | 0.38 |  | 0.56 | 0.40
fisher |  | 0.36 | 0.26 |  | 0.39 | 0.28 |  | 0.33 | 0.25
synflow |  | 0.74 | 0.54 |  | 0.76 | 0.57 |  | 0.75 | 0.56
jacob_cov |  | 0.73 | 0.55 |  | 0.71 | 0.55 |  | 0.71 | 0.54
Ours | avg_deg |  | 0.78 | 0.58 |  | 0.80 | 0.60 |  | 0.77 | 0.57

  * •

$\ddagger$ Original implementation of ZiCo uses cutout data augmentation. To
make a fair comparison, we recalculate the correlation without cutout data
augmentation.

Improving the search efficiency of NASGraph. To reduce computational overhead,
NAS typically uses a training-reduced proxy to obtain the performance of
neural architectures. A systematic study is reported in EcoNAS [19] where four
reducing factors are analyzed: (1) number of epochs, (2) resolution of input
images, (3) number of training samples, (4) number of channels for Convolution
Neural Networks (CNNs). Following their convention, to accelerate NASGraph, we
also consider the surrogate models, i.e. models with computationally reduced
settings. We dub the surrogate model NASGraph(h, c, m), where $h$ is the
number of channels, $c$ is the number of search cells in a module, and $m$ is
the number of modules. The ablation study on the effect of using a surrogate
model is discussed in Appendix A.5.

After converting the neural architectures to graphs, we use the average degree
as the graph measure to rank neural architectures. In addition to the average
degree, we also examine the performance of other graph measures. The result is
included in the Appendix A.7.

##  4 Performance Evaluation

Table 2: Comparison of Kendall’s Tau ranking correlations $\tau$ between test
accuracies and training-free NAS metrics on the NDS benchmark.

Metric | AMOEBA | DARTS | ENAS | NASNet | PNAS
---|---|---|---|---|---
grad_norm | -0.12 | 0.22 | 0.06 | -0.05 | 0.15
snip | -0.09 | 0.26 | 0.10 | -0.02 | 0.18
grasp | 0.02 | -0.04 | 0.03 | 0.18 | -0.01
fisher | -0.12 | 0.19 | 0.04 | -0.07 | 0.14
jacov_cov | 0.22 | 0.19 | 0.11 | 0.05 | 0.10
synflow | -0.06 | 0.30 | 0.14 | 0.04 | 0.21
naswot | 0.22 | 0.47 | 0.37 | 0.30 | 0.38
avg_deg (Ours) | 0.32 | 0.45 | 0.41 | 0.37 | 0.40

Table 3: Comparison of Spearman’s ranking correlations $\rho$ between
validation accuracies and training-free NAS metrics on micro TransNAS-
Bench-101. The baseline performance is extracted from [22]. Note that synflow
and avg_deg are data-agnostic. CO is class_object, CS is class_scene, RL is
room_layout, SS is segment_semantic.

Metric | Micro TransNAS-Bench-101
---|---
CO | CS | RL | SS
plain | 0.34 | 0.24 | 0.36 | -0.02
grasp | -0.22 | -0.27 | -0.29 | 0.00
fisher | 0.44 | 0.66 | 0.30 | 0.12
epe_nas | 0.39 | 0.51 | 0.40 | 0.00
grad_norm | 0.39 | 0.65 | 0.25 | 0.60
snip | 0.45 | 0.70 | 0.32 | 0.68
synflow | 0.48 | 0.72 | 0.30 | 0.00
l2_norm | 0.32 | 0.53 | 0.18 | 0.48
params | 0.45 | 0.64 | 0.30 | 0.68
zen | 0.54 | 0.72 | 0.38 | 0.67
jacob_cov | 0.51 | 0.75 | 0.40 | 0.80
flops | 0.46 | 0.65 | 0.30 | 0.69
naswot | 0.39 | 0.60 | 0.25 | 0.53
zico | 0.55 | 0.68 | 0.26 | 0.61
avg_deg (Ours) | 0.55 | 0.70 | 0.37 | 0.66

###  4.1 Experiment Setup

NAS benchmarks. To examine the effectiveness of our proposed NASGraph, we use
neural architectures on NAS-Bench-101 [25], NAS-Bench-201 [26], TransNAS-
Bench-101 [27] and Network Design Space (NDS) [28]. NAS-Bench-101 is the first
NAS benchmark consisting of 423,624 neural architectures trained on the
CIFAR-10 dataset [29]. The training statistics are reported at 108th epoch.
NAS-Bench-201 is built for prototyping NAS algorithms. It contains 15,625
neural architectures trained on CIFAR-10, CIFAR-100 [29] and ImageNet-16-120
[30] datasets. The training statistics are reported at 200th epoch for these
three datasets. In addition to standard NAS benchmarks, we also examine the
performance of NASGraph on TransNAS-Bench-101, specifically the micro search
space. The micro (cell-level) TransNAS-Bench-101 has 4,096 architectures
trained on different tasks using the Taskonomy dataset [31]. The NDS benchmark
includes AmoebaNet [32], DARTS [8], ENAS [33], NASNet [4] and PNAS search
spaces [34].

We convert neural architectures with Gaussian initialization to graphs
$G(V,E)$. The conversion is repeated 8 times with different random
initializations. We find the difference in the rankings among 8
initializations is considerably marginal as shown in Appendix A.6.

We use AMD EPYC 7232P CPU in the computation of NASGraph. To compute the
performance of baselines requiring GPUs, a single NVIDIA A40 GPU is used. We
reduce the number of channels to be 16 and the number of cells to be 1, i.e.
NASGraph(16, 1, 3) is used as the surrogate model.

Baselines. We use metrics in training-free NAS as our baselines. zico [35] is
based on the theory of Gram Matrix [36]. relu_logdet (also dubbed naswot) [10]
applies the theory on the number of linear regions to represent the model
expressivity. jacob_cov [10] is based on the correlation of Jacobians with
inputs. grad_norm [11] sums the Euclidean norm of the gradients. snip [37] is
related to the connection sensitivity of neural network model. grasp [38] is
based on the assumption that gradient flow is preserved in the efficient
training. fisher [39] estimates fisher information of model parameters,
synflow [24] preserves the total flow of synaptic strength.

Table 4: Comparison of the ranking correlations using multiple metrics with
training-free NAS methods on NAS-Bench-201. Correlations between the combined
metric and NAS Benchmark performance are reported. TENAS [21] combines
rankings by NTK and NLR. Zero-Cost NAS [11] takes a majority vote among the
three metrics: synflow, jacob_cov and snip. Our method combines the rankings
of avg_deg and jacob_cov.

Method | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
---|---|---|---|---|---
$\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$
TENAS | Rank combine | - | - |  | - | 0.64 |  | - | -
Zero-Cost NAS | Voting | 0.82 | - |  | 0.83 | - |  | 0.82 | -
Ours | Rank combine | 0.85 | 0.66 |  | 0.85 | 0.67 |  | 0.82 | 0.64

Table 5: Comparison of the accumulated frequency difference between training-
free NAS methods and GT on top 10% architectures of the NAS-Bench-201. GT
ranks architectures ranked by test accuracies. Lower value means less bias
(i.e. closer to GT).

Metric | CIFAR-10 | CIFAR-100 | ImageNet-16-120 | Average bias
---|---|---|---|---
relu_logdet | 0.3 | 0.27 | 0.19 | 0.25
grad_norm | 0.32 | 0.3 | 0.24 | 0.29
snip | 0.31 | 0.29 | 0.24 | 0.28
grasp | 0.31 | 0.28 | 0.24 | 0.28
fisher | 0.52 | 0.52 | 0.53 | 0.52
synflow | 0.22 | 0.18 | 0.27 | 0.22
jacob_cov | 0.39 | 0.42 | 0.22 | 0.34
Our method
avg_deg | 0.22 | 0.14 | 0.27 | 0.21
comb_rank | 0.17 | 0.17 | 0.12 | 0.15

###  4.2 Scoring neural architectures using average degree

The distribution of the average degree of graphs vs the performance of neural
architectures is plotted in Figure 2 (a)-(l). Colorbar indicates the number of
architectures in logarithmic base 10. We compute both Spearman’s ranking
correlation $\rho$ and Kendall’s Tau ranking correlation $\tau$ between them.
In Table 1 we compare the performance of average degree against all the
baselines on NAS-Bench-201 benchmark. Our method can rank architectures
effectively and outperforms the baselines on most of the datasets.

We also evaluate our method on the NDS benchmark. The result is summarized in
Table 2. Similar to NASWOT [10], we use 1000 randomly sampled architectures.
Same subset of architectures is used for all methods.

Figure 2: The ranking correlation between the performance of neural
architecture $a$ and the graph measures of the corresponding graph $G(V,E)$.
In the NASGraph framework, each neural architecture is uniquely mapped to a
graph, i.e. $a\mapsto G(V,E)$.

To explore the generality of the proposed NASGraph framework, we examine the
performance of the graph measure on micro TransNAS-Bench-101. The comparison
is shown in Table 3. As reported in [22], there is a pronounced variation in
the ranks of training-free proxies when changing NAS benchmarks. For the
class_object downstream task, the average degree gives the best performance.
For other downstream tasks, our method also exhibits a competitive
performance. We notice that other graph measure wedge gives a consistently
higher performance compared to avg_deg. The comparison of different graph
measures can be found in Appendix Table 10.

###  4.3 Combining NASGraph metrics with data-dependent NAS metrics improves
prediction

In addition to using single metric, we examine the performance of combining
graph measures with existing metrics. Specifically, two metrics are combined
by the summation of rankings of neural architectures by two metrics. We use a
combination of avg_deg and jacob_cov, i.e. rank(avg_deg) + rank(jacob_cov).
For the case of tied ranking, the average of the ranking is used. Similar to
density and average degree, the combined metrics manifest a positive
correlation with test accuracy. By combining our metrics with jacob_cov, the
$\rho$ boosts to $0.85$ on CIFAR-10 and CIFAR-100 and the $\tau$ reaches
$0.66$ on CIFAR-10, $0.67$ on CIFAR-100. On ImageNet-16-120, the $\rho$
increases to $0.82$ and $\tau$ is $0.64$. The comparison with existing
combined metrics is shown in Table 4. Our combined metrics can outperform all
existing methods reported in [21, 11], which demonstrates the effectiveness of
complementary nature of our proposed graph measures for NAS. The detailed
plots of combined ranks against test accuracy are shown in Appendix A.8.

###  4.4 Training-Free architecture search using NASGraph

We evaluate the performance of our metric when used as an alternative to
validation accuracy during random search. $N=100$ and $N=200$ architectures
are randomly sampled from NAS-Bench-201 and the training-free metrics are used
to perform the search. We repeat the search process 100 times, and the mean
and the standard deviation are reported in Table 6. Ground truth (GT)
indicates the highest validation accuracy and the highest test accuracy for
the validation and the test columns respectively. It is essential to highlight
the fact that all the metrics in baselines are computed based on single A40
GPU (in GPU second) while NASGraph score is calculated on single CPU (in CPU
second). NASGraph using the surrogate model NASGraph(16, 1, 3) can outperform
the other training-free metrics on CIFAR-10 and CIFAR-100 datasets with a
higher mean value and a lower standard deviation. At a small cost of
performance, the surrogate model NASGraph(1, 1, 3) can have a significant
improvement in the computation efficiency.

Table 6: Comparison of training-free NAS metrics using random search method.
The same subset of architectures is randomly chosen from NAS-Bench-201 for all
metrics. GT reports the performance of the best architecture in that subset.

Metric | Running time | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
---|---|---|---|---|---|---
validation | test |  | validation | test |  | validation | test
N = 100
relu_logdet |  $52.72$ GPU sec. | $89.51\pm 0.96$ | $89.22\pm 1.03$ |  | $69.48\pm 1.44$ | $69.58\pm 1.50$ |  | $42.92\pm 2.41$ | $43.27\pm 2.62$
grad_norm |  $364.68$ GPU sec. | $88.28\pm 1.42$ | $87.94\pm 1.48$ |  | $65.96\pm 3.11$ | $66.13\pm 3.10$ |  | $34.97\pm 6.82$ | $34.96\pm 7.06$
snip |  $363.71$ GPU sec. | $88.29\pm 1.42$ | $87.95\pm 1.48$ |  | $66.14\pm 2.96$ | $66.32\pm 2.97$ |  | $35.44\pm 6.49$ | $35.44\pm 6.72$
grasp |  $377.29$ GPU sec. | $88.06\pm 1.55$ | $87.74\pm 1.58$ |  | $66.27\pm 3.50$ | $66.38\pm 3.55$ |  | $35.20\pm 6.76$ | $35.19\pm 6.93$
fisher |  $315.57$ GPU sec. | $84.08\pm 6.68$ | $83.70\pm 6.67$ |  | $61.77\pm 7.26$ | $61.89\pm 7.44$ |  | $30.80\pm 8.02$ | $30.49\pm 8.33$
synflow |  $360.15$ GPU sec. | $89.91\pm 0.87$ | $89.67\pm 0.88$ |  | $70.03\pm 1.79$ | $70.17\pm 1.79$ |  | $41.89\pm 4.13$ | $42.23\pm 4.24$
jacob_cov |  $360.48$ GPU sec. | $88.68\pm 1.56$ | $88.32\pm 1.59$ |  | $67.45\pm 2.91$ | $67.57\pm 3.03$ |  | $40.64\pm 3.54$ | $40.76\pm 3.77$
avg_deg (NASGraph(1, 1, 3)) |  $7.78$ CPU sec. | $89.74\pm 0.77$ | $89.53\pm 0.75$ |  | $69.90\pm 1.38$ | $70.01\pm 1.43$ |  | $42.00\pm 2.80$ | $40.73\pm 4.14$
avg_deg (NASGraph(16, 1, 3)) |  $106.18$ CPU sec. | $89.95\pm 0.49$ | $89.73\pm 0.52$ |  | $70.17\pm 1.06$ | $70.29\pm 1.10$ |  | $42.72\pm 2.33$ | $43.15\pm 2.29$
GT | - | $90.98\pm 0.36$ | $90.77\pm 0.31$ |  | $71.48\pm 0.86$ | $71.69\pm 0.81$ |  | $45.45\pm 0.67$ | $45.74\pm 0.65$
N = 200
relu_logdet |  $90.39$ GPU sec. | $89.64\pm 0.81$ | $89.33\pm 0.84$ |  | $69.65\pm 1.36$ | $69.87\pm 1.33$ |  | $43.25\pm 2.22$ | $43.62\pm 2.37$
grad_norm |  $644.23$ GPU sec. | $88.23\pm 1.51$ | $87.87\pm 1.53$ |  | $65.46\pm 3.34$ | $65.67\pm 3.42$ |  | $35.08\pm 7.05$ | $35.00\pm 7.26$
snip |  $712.58$ GPU sec. | $88.23\pm 1.51$ | $87.87\pm 1.54$ |  | $65.68\pm 3.16$ | $65.89\pm 3.21$ |  | $35.08\pm 7.05$ | $35.00\pm 7.26$
grasp |  $692.74$ GPU sec. | $88.31\pm 1.35$ | $87.96\pm 1.37$ |  | $65.97\pm 3.21$ | $66.16\pm 3.28$ |  | $34.83\pm 6.63$ | $34.74\pm 6.81$
fisher |  $622.92$ GPU sec. | $85.55\pm 4.91$ | $85.24\pm 4.92$ |  | $61.69\pm 5.62$ | $61.86\pm 5.77$ |  | $29.39\pm 6.38$ | $29.04\pm 6.65$
synflow |  $742.74$ GPU sec. | $89.87\pm 0.85$ | $89.61\pm 0.85$ |  | $69.93\pm 1.84$ | $70.05\pm 1.89$ |  | $41.54\pm 3.76$ | $41.93\pm 3.77$
jacob_cov |  $688.77$ GPU sec. | $88.34\pm 1.67$ | $88.00\pm 1.71$ |  | $67.39\pm 2.93$ | $67.55\pm 3.05$ |  | $40.95\pm 3.24$ | $41.04\pm 3.41$
avg_deg (NASGraph(1, 1, 3)) |  $15.98$ CPU sec. | $89.92\pm 0.61$ | $89.69\pm 0.62$ |  | $70.25\pm 1.20$ | $70.42\pm 1.21$ |  | $41.96\pm 2.44$ | $42.48\pm 2.39$
avg_deg (NASGraph(16, 1, 3)) |  $217.21$ CPU sec. | $89.96\pm 0.38$ | $89.73\pm 0.43$ |  | $70.22\pm 0.99$ | $70.45\pm 0.98$ |  | $42.27\pm 2.36$ | $42.76\pm 2.36$
GT | - | $91.14\pm 0.25$ | $90.91\pm 0.24$ |  | $71.84\pm 0.76$ | $72.04\pm 0.72$ |  | $45.72\pm 0.54$ | $46.01\pm 0.50$

###  4.5 Analysis of Operation Preference in NAS Methods

To study the bias in architecture preference in NAS, we count the frequency
(histogram) of different operations appearing in the top 10% architectures
(ranked by different metrics) on NAS-Bench-201. The visualization of the
frequency distribution of operations and the details on frequency counting are
given in Appendix A.2. The overall result is shown in Table 5. The ground
truth (GT) ranks architecture using the test accuracy. A perfect metric is
expected to have the same frequency distribution of operations as GT and thus
achieve zero bias. We compute the accumulated difference in the frequency
(also called bias) between a NAS metric and GT across all five operations in
NAS-Bench-201. The avg_deg from NASGraph has the lowest bias when using a
single metric. The combined metric (conm_rank) introduced in Section 4.3,
which is rank(avg_deg) + rank(jacob_cov), can further reduce the bias. The low
bias towards operations can also explain why our method can have a high rank
correlation in NAS via NASGraph.

All of the baselines except synflow rely on a few mini-batches of data. Thus,
their score varies based on the input data being used to evaluate their proxy
scores. In contrast, our metric is data-agnostic and is not sensitive to the
input data. Furthermore, our technique is also lightweight: it can run on a
CPU and the running time is faster than most of training-free proxies running
on GPU.

##  5 Discussion

In this paper, we proposed NASGraph, a novel graph-based method for NAS
featuring lightweight (CPU-only) computation and is data-agnostic and
training-free. Extensive experimental results verified the high correlation
between the graph measure of NASGraph and performance of neural architectures
in several benchmarks. Compared to existing NAS methods, NASGraph provides a
more stable and accurate prediction of the architecture performance and can be
used for efficient architecture search. We also show that our graph measures
can be combined with existing data-dependent metrics to further improve NAS.
We believe our findings provide a new perspective and useful tools for
studying NAS through the lens of graph theory and analysis.

Our method addresses some limitations in current NAS methods (e.g. data
dependency, GPU requirement, and operation preference) and attains new state-
of-the-art NAS performance. The authors do not find any immediate ethical
concerns or negative societal impacts from this study.

## References

  * [1] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697–8710, 2018.
  * [2] Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun.  Detnas: Backbone search for object detection.  Advances in Neural Information Processing Systems, 32, 2019.
  * [3] Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei.  Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 82–92, 2019.
  * [4] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.
  * [5] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean.  Efficient neural architecture search via parameters sharing.  In International conference on machine learning, pages 4095–4104. PMLR, 2018.
  * [6] Xiangxiang Chu, Bo Zhang, and Ruijun Xu.  Fairnas: Rethinking evaluation fairness of weight sharing neural architecture search.  In Proceedings of the IEEE/CVF International Conference on computer vision, pages 12239–12248, 2021.
  * [7] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy.  Progressive neural architecture search.  In Proceedings of the European conference on computer vision (ECCV), pages 19–34, 2018.
  * [8] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  arXiv preprint arXiv:1806.09055, 2018.
  * [9] Colin White, Willie Neiswanger, and Yash Savani.  Bananas: Bayesian optimization with neural architectures for neural architecture search.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35 of 12, pages 10293–10301, 2021.
  * [10] Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley.  Neural architecture search without training.  In International Conference on Machine Learning, pages 7588–7598. PMLR, 2021.
  * [11] Mohamed S Abdelfattah, Abhinav Mehrotra, Łukasz Dudziak, and Nicholas D Lane.  Zero-cost proxies for lightweight nas.  arXiv preprint arXiv:2101.08134, 2021.
  * [12] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong.  Pc-darts: Partial channel connections for memory-efficient architecture search.  arXiv preprint arXiv:1907.05737, 2019.
  * [13] Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh.  Rethinking architecture selection in differentiable NAS.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
  * [14] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter.  Understanding and robustifying differentiable architecture search.  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [15] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann.  Evaluating the search phase of neural architecture search.  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [16] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVI, volume 12361 of Lecture Notes in Computer Science, pages 544–560. Springer, 2020\.
  * [17] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc V. Le.  Understanding and simplifying one-shot architecture search.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 549–558. PMLR, 2018.
  * [18] Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik.  ASAP: architecture search, anneal and prune.  In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 493–503. PMLR, 2020.
  * [19] Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang.  Econas: Finding proxies for economical neural architecture search.  In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pages 11396–11404, 2020.
  * [20] Boris Hanin and David Rolnick.  Complexity of linear regions in deep networks.  In International Conference on Machine Learning, pages 2596–2604. PMLR, 2019.
  * [21] Wuyang Chen, Xinyu Gong, and Zhangyang Wang.  Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective.  arXiv preprint arXiv:2102.11535, 2021.
  * [22] Arjun Krishnakumar, Colin White, Arber Zela, Renbo Tu, Mahmoud Safari, and Frank Hutter.  Nas-bench-suite-zero: Accelerating research on zero cost proxies.  arXiv preprint arXiv:2210.03230, 2022.
  * [23] Stijn Verdenius, Maarten Stol, and Patrick Forré.  Pruning via iterative ranking of sensitivity statistics.  arXiv preprint arXiv:2006.00896, 2020.
  * [24] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  Advances in neural information processing systems, 33:6377–6389, 2020.
  * [25] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter.  Nas-bench-101: Towards reproducible neural architecture search.  In International Conference on Machine Learning, pages 7105–7114. PMLR, 2019.
  * [26] Xuanyi Dong and Yi Yang.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  arXiv preprint arXiv:2001.00326, 2020.
  * [27] Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li.  Transnas-bench-101: Improving transferability and generalizability of cross-task neural architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5251–5260, 2021.
  * [28] Ilija Radosavovic, Justin Johnson, Saining Xie, Wan-Yen Lo, and Piotr Dollár.  On network design spaces for visual recognition.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 1882–1890, 2019.
  * [29] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  Technical report, Univeristy of Toronto, 2009.
  * [30] Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter.  A downsampled variant of imagenet as an alternative to the cifar datasets.  arXiv preprint arXiv:1707.08819, 2017.
  * [31] Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese.  Taskonomy: Disentangling task transfer learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3712–3722, 2018.
  * [32] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In Proceedings of the aaai conference on artificial intelligence, volume 33, pages 4780–4789, 2019.
  * [33] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean.  Efficient neural architecture search via parameters sharing.  In International conference on machine learning, pages 4095–4104. PMLR, 2018.
  * [34] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy.  Progressive neural architecture search.  In Proceedings of the European conference on computer vision (ECCV), pages 19–34, 2018.
  * [35] Guihong Li, Yuedong Yang, Kartikeya Bhardwaj, and Radu Marculescu.  Zico: Zero-shot nas via inverse coefficient of variation on gradients.  arXiv preprint arXiv:2301.11300, 2023.
  * [36] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  arXiv preprint arXiv:1810.02054, 2018.
  * [37] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr.  Snip: Single-shot network pruning based on connection sensitivity.  arXiv preprint arXiv:1810.02340, 2018.
  * [38] Chaoqi Wang, Guodong Zhang, and Roger Grosse.  Picking winning tickets before training by preserving gradient flow.  arXiv preprint arXiv:2002.07376, 2020.
  * [39] Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferenc Huszár.  Faster gaze prediction with dense networks and fisher pruning.  arXiv preprint arXiv:1801.05787, 2018.
  * [40] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11976–11986, 2022.
  * [41] Jianxi Gao, Baruch Barzel, and Albert-László Barabási.  Universal resilience patterns in complex networks.  Nature, 530(7590):307–312, 2016.
  * [42] Rishi Gupta, Tim Roughgarden, and Comandur Seshadhri.  Decompositions of triangle-dense graphs.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 471–482, 2014.

##  Appendix A Appendix

###  A.1 Proof of Theorem 1

######  Theorem 1.

Let $\mathbf{x}$ be the input to $\mathcal{F}$. $\mathcal{F}$ is converted to
a graph $G(V,E)$ using NASGraph framework: the input to $\mathcal{F}$ has
$\mathds{1}\in\mathbb{R}^{H^{(0)}\times W^{(0)}}$ for the channel $i$ and
$\mathds{O}\in\mathbb{R}^{H^{(0)}\times W^{(0)}}$ for rest of channels. There
is no edge between node i and node j if and only if the output for the channel
j is all-zeros matrix $\mathds{O}\in\mathbb{R}^{H^{(1)}\times W^{(1)}}$.

Proof: $y_{i}^{(1)}=\mathcal{F}(\mathbf{x})$, and
$(y_{i}^{(1)})_{d_{1}d_{2}d_{3}}\in\mathbb{R}$ is computed by:

$\displaystyle(y_{i}^{(1)})_{d_{1}d_{2}d_{3}}=\rm{ReLU}($ (3)
$\displaystyle\sum_{a=0}^{f_{k_{1}}^{(0)}}\sum_{b=0}^{f_{k_{2}}^{(0)}}\sum_{c=0}^{C^{(0)}}\mathbf{w}_{a,b,c}^{(0),d_{3}}\mathbf{x}^{(0)}_{a+(d_{1}-1)s_{l},b+(d_{2}-1)s_{l},c}+\mathbf{b}^{(0),d_{3}})$

where $f^{(0)}_{k_{1}}$ is the kernel height, $f^{(0)}_{k_{2}}$ is the kernel
width, and $s_{l}$ is the convolution stride. Since
$(y_{i}^{(1)})_{d_{1}d_{2}d_{3}}\geq 0$, according to Equation 2,
$\omega_{i^{(l-1)}j^{(l)}}=0$ implies $(y_{i}^{(1)})_{d_{1}d_{2}d_{3}}=0$. The
reverse implication is obvious: when
$(y_{i}^{(1)})_{d_{1}d_{2}d_{3}}=0,\;\forall d_{1},d_{2}\text{ s.t. }0\leq
d_{1}\leq H^{(1)},0\leq d_{2}\leq W^{(1)}$, then the summation
$\omega_{i^{(l-1)}j^{(l)}}=0$. This completes our proof.

###  A.2 Bias in NAS methods

Figure 3: (a)-(c) Spearman’s ranking correlation $\rho$ between pair of
metrics and (e)-(f) the preference for different operations on NAS-Bench-201.
GT is the operation distribution of top architectures ranked by test accuracy.

We rank architectures in NAS-Bench-201 using different metrics and compute the
$\rho$ of architecture ranks for each pair of metrics. Figure 3 (a)-(c) show
the pairwise ranking correlation between metrics. Both avg_deg and synflow are
data-agnostic approach and the correlation between these two metrics is high.
Besides, the correlations between these two metrics do no change across
datasets. The correlation between avg_deg and jacob_cov is comparably small,
but a combination of these two metrics can have the best ranking correlation
between the metrics and the performance of neural architectures. Because of
rounding number, grad_norm and snip have the $\rho$ of 1. But they do not give
the exactly same rankings of neural architectures. When we check the
architecture rankings precisely using these two metrics, we find $\rho=0.9982$
on CIFAR-10, $\rho=0.9984$ on CIFAR-100 and $\rho=0.9988$ on ImageNet-16-120.

We extract top 10% neural architectures on NAS-Bench-201 and count the
frequency of each operation (avg_pool, none, nor_conv_1$\times$1,
nor_conv_3$\times$3, skip_connect) appearing in the selected subset. Figure 3
(e)-(f) show the frequency of different operations on different datasets.
There is no pronounced difference in the distribution across different
datasets for GT. This is reasonable when we examine the distribution of test
accuracy in CIFAR-10, CIFAR-100 and ImageNet-16-120 datasets (Figure 2 (f))
where test accuracy is positively correlated among datasets. These facts
indicate the same architecture generally have a similar performance on
different datasets. Therefore, the data-agnostic NAS methods (avg_deg and
synflow) can be effective to search neural architectures across different
datasets.

Based on the distribution of operation preference, we find our metric avg_deg
has a distribution similar to the GT. Similar to synflow, our metric has a
relatively low preference for skip_connect while jacob_cov has a high
preference for skip_connect. That might explain the reason why a combination
of avg_deg and jacob_cov gives the highest correlation between test accuracy
and combined metrics. Another reasoning is related to the definition of
jacob_cov. The Jacobian for the $i$-th neuron in the output of the layer $L$
with parameter $\theta_{\alpha}$ valuated at a point x is defined as [10]:

$J_{i\alpha}(\mathbf{x})=\partial_{\mathbf{\theta}_{\alpha}}z^{(L)}_{i}(\mathbf{x})$
(4)

The jacob_cov metric takes gradient of model parameters into consideration,
i.e., it focuses on the backward propagation process. The NASGraph framework,
on the other hand, considers the forward propagation for each graph block.
They are complementary to each other. Hence, Combining avg_deg with jacob_cov
leads to a higher ranking correlation. comb_rank is rank(avg_deg) +
rank(jacob_cov). The frequency distribution of comb_rank is very close to GT
as shown in Figure 3 (e)-(g).

The relu_logdet metric exhibits the highest preference for convolution with
small kernel size while GT indicates the best neural architectures prefer
convolution with large kernel size. relu_logdet might have a problem when the
search space $\mathcal{A}$ includes convolution with large kernel size.
ConvNeXt [40] has shown the advantage of modern design using convolution with
large kernel size. fisher has the highest preference for none operation, and
it has the lowest correlation in the NAS-Bench-201.

###  A.3 Output combination from preceding graph blocks

When there are multiple graph blocks connected to the same graph block, there
are two ways to combine the outputs from preceding graph blocks: summation and
concatenation, as illustrated in the middle of Figure 1. In the case of
summation, we do the forward propagation for each channel of all branches. In
the case of concatenation, however, the outputs of the preceding graph blocks
do not match the input dimension of the current graph block. We add virtual
channels to the outputs of the preceding graph blocks such that the output
dimension matches the input dimension, and hence we can do the conversion in
the block-wise fashion. We want to emphasize that the summation or
concatenation is determined by the original neural architecture. The graph
block just combines components in the neural architecture such as Conv and
ReLU. $w.l.o.g.$ we examine the case of concatenation and the case of
summation of two preceding graph blocks connecting to the $l$-th graph block
as shown in Figure 4. In the case of summation, two graph blocks connect to
the $l$-th graph block. The output of each graph block has 4 channels. The
input of $l$-th graph block has 4 channels. In the case of concatenation, two
outputs from the preceding graph blocks have 2 channels while the input of
$l$-th graph block has 4 channels.

Summation The summation requires that outputs of the preceding graph blocks
have the same dimension as the input of the current graph block. We perform
forward propagation for each channel of the outputs of the preceding graph
blocks. Hence, there are 8 forward propagations in the case shown in Figure 4.
Each forward propagation determines the scores between the “activated” channel
and all the output channels of $l$-th graph block.

Concatenation The concatenation requires that outputs of the preceding graph
blocks have the same dimension as the input of the current graph block except
for the channel dimension, and the summation of the channel size of the
outputs of the preceding graph blocks equal to the channel size of the input
of the current graph block. Because we do the conversion in the block-wise
fashion, there will be dimension mismatch if we do forward propagation using
the dimension of the preceding outputs. So we add virtual channels to make
sure two dimensions match. The number of added channels is
$C^{(l)}-C^{(l-1)}$. In the case of Figure 4, two virtual channels are added
for each input. We do not activate “virtual channels” in any forward
propagation, so there are 4 forward propagations in total.

Figure 4: An illustration of converting one graph block of the neural
architecture to subgraph in the case of summation and concatenation. Channels
in dashed line mean virtually concatenated channels. These channels become
zero matrix after applying a mask. Connection is established if the score
between two graph nodes is non-zero.

###  A.4 Parallel computing for graph blocks

The direct way to compute the weight of a graph edge is to do forward
propagation as many times as the number of input channels, and in this case,
the batch size of the input is one. In other words, to compute the score
$\omega_{i^{(l-1)}j^{(l)}}$, the input $\mathcal{M}_{c}^{(l)}\odot x^{(l)}$
has the batch dimension of one. To enable parallel computing of scores, we
concatenate inputs for the same graph block on the batch dimension
$[\mathcal{M}_{1}^{(l)}\odot x^{(l)},\ldots,\mathcal{M}_{c}^{(l)}\odot
x^{(l)}]$ so that scores can be computed independently and in parallel. The
batch size, under this condition, is equal to the input channel size. Using
this approach, the batch size dimension has a different meaning compared to
the standard definition in batch normalization. Moreover, the effective batch
dimension is essentially one as we only use the same input $\mathbf{x}^{(l)}$
to determine scores. Therefore, during graph conversion, we remove batch
normalization in the entire neural architecture. For example, Conv-BN-ReLU
becomes Conv-ReLU.

###  A.5 Albation Study

We use ablation study to analyze the effect of using surrogate models. There
are two reducing factors: (1) number of channels, (2) number of search cells
within one module. The random search result on NAS-Bench-201 is listed in
Table 7 for the case $N=100$ and $N=200$. GT reports the highest test accuracy
of neural architectures within the selected subset in the random search
process. In both $N=100$ and $N=200$ cases, we do not find a significant
variation of the performance of surrogate models except for the efficiency. As
we decrease the number of cells or number of channels, there is a significant
improvement in the efficiency. We use a grid routine to systematically study
the effect of number of channels and number of cells on the performance of the
surrogate model. Figure 5 shows the effect of varying number of channels and
number of cells within the same module on NAS-Bench-201 using random search
algorithm. The number of sampled architectures is 100 and each search process
is repeated for 100 times.

Number of channels Along $x$ axis in Figure 5 shows the effect of varying the
number of channels. We find as the number of channels increase, the
performance of the surrogate models either does not change or improves. This
is expected because decreasing the number of channels make the equivalent
neural architecture has less model complexity (number of model parameters
decrease) compared to the original one.

Number of cells Along $y$ axis in Figure 5 shows the effect of changing the
number of cells within a module. We find there is no monotonous increase nor
decrease in the performance as the number of cells varies. We believe it is
related to the way we bridge neural architecture space and graph space.
Because we convert neural architectures in the block-wise fashion and input is
independent of other graph blocks, the conversion of one graph block is
independent of other graph blocks. Besides, the cell structure is the same
within the same module. Considering the cell structure that corresponds to a
subgraph, the module consisting of a linear stack of cell structures
corresponds to a stack of identical subgraphs. Therefore, graph measures using
surrogate models that decrease the number of cells is expected to not impose a
significant effect on the graph measures, and hence rankings of the original
neural network models.

Overall, we find that there is no remarkable difference in the accuracies
using the random search algorithm. However, we can vastly boost the efficiency
by the means of surrogate models. We choose the surrogate model NASGraph(16,
1, 3) to compute graph measures on different NAS benchamrks.

Table 7: Comparison of different surrogate models on NAS-Bench-201. avg_deg is
used as the metric to score architectures. Reported results are averaged over
100 runs, and both mean values and standard deviations are recorded. GT
records the highest accuracies of the randomly sampled architectures.

Method | Time | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
---|---|---|---|---|---|---
validation | test |  | validation | test |  | validation | test
N = 100
NASGraph(1, 1, 3) |  $7.78$ sec. | $89.74\pm 0.77$ | $89.53\pm 0.75$ |  | $69.90\pm 1.38$ | $70.01\pm 1.43$ |  | $42.00\pm 2.80$ | $40.73\pm 4.14$
NASGraph(4, 1, 3) |  $19.23$ sec. | $89.91\pm 0.49$ | $89.70\pm 0.52$ |  | $70.05\pm 1.16$ | $70.22\pm 1.18$ |  | $42.60\pm 2.43$ | $43.00\pm 2.42$
NASGraph(8, 1, 3) |  $62.61$ sec. | $89.96\pm 0.46$ | $89.74\pm 0.49$ |  | $70.15\pm 1.01$ | $70.28\pm 1.05$ |  | $42.72\pm 2.33$ | $43.15\pm 2.30$
NASGraph(16, 1, 3) |  $106.18$ sec. | $89.95\pm 0.49$ | $89.73\pm 0.52$ |  | $70.17\pm 1.06$ | $70.29\pm 1.10$ |  | $42.72\pm 2.33$ | $43.15\pm 2.29$
NASGraph(1, 5, 3) |  $25.63$ sec. | $89.78\pm 0.64$ | $89.58\pm 0.65$ |  | $69.93\pm 1.23$ | $70.06\pm 1.30$ |  | $41.80\pm 2.66$ | $42.22\pm 2.63$
NASGraph(4, 5, 3) |  $89.68$ sec. | $89.84\pm 0.53$ | $89.62\pm 0.55$ |  | $69.88\pm 1.07$ | $70.04\pm 1.13$ |  | $42.22\pm 2.56$ | $42.66\pm 2.56$
NASGraph(8, 5, 3) |  $258.03$ sec. | $89.84\pm 0.52$ | $89.62\pm 0.55$ |  | $69.90\pm 1.07$ | $70.07\pm 1.14$ |  | $42.18\pm 2.57$ | $42.65\pm 2.57$
GT | - | $90.98\pm 0.36$ | $90.77\pm 0.31$ |  | $71.48\pm 0.86$ | $71.69\pm 0.81$ |  | $45.45\pm 0.67$ | $45.74\pm 0.65$
N = 200
NASGraph(1, 1, 3) |  $15.98$ sec. | $89.92\pm 0.61$ | $89.69\pm 0.62$ |  | $70.25\pm 1.20$ | $70.42\pm 1.21$ |  | $41.96\pm 2.44$ | $42.48\pm 2.39$
NASGraph(4, 1, 3) |  $61.60$ sec. | $89.95\pm 0.38$ | $89.73\pm 0.42$ |  | $70.17\pm 1.01$ | $70.42\pm 0.99$ |  | $42.25\pm 2.33$ | $42.73\pm 2.32$
NASGraph(8, 1, 3) |  $186.21$ sec. | $89.97\pm 0.37$ | $89.74\pm 0.42$ |  | $70.25\pm 0.89$ | $70.47\pm 0.87$ |  | $42.40\pm 2.11$ | $42.87\pm 2.13$
NASGraph(16, 1, 3) |  $217.21$ sec. | $89.96\pm 0.38$ | $89.73\pm 0.43$ |  | $70.22\pm 0.99$ | $70.45\pm 0.98$ |  | $42.27\pm 2.36$ | $42.76\pm 2.36$
NASGraph(1, 5, 3) |  $50.33$ sec. | $89.80\pm 0.59$ | $89.61\pm 0.59$ |  | $70.05\pm 1.15$ | $70.18\pm 1.23$ |  | $41.47\pm 2.50$ | $41.97\pm 2.51$
NASGraph(4, 5, 3) |  $196.08$ sec. | $89.89\pm 0.45$ | $89.68\pm 0.49$ |  | $70.05\pm 0.93$ | $70.21\pm 1.05$ |  | $41.91\pm 2.04$ | $42.45\pm 2.05$
NASGraph(8, 5, 3) |  $413.47$ sec. | $89.88\pm 0.45$ | $89.66\pm 0.49$ |  | $70.05\pm 0.95$ | $70.23\pm 1.07$ |  | $42.01\pm 2.07$ | $42.53\pm 2.09$
GT | - | $91.14\pm 0.25$ | $90.91\pm 0.24$ |  | $71.84\pm 0.76$ | $72.04\pm 0.72$ |  | $45.72\pm 0.54$ | $46.01\pm 0.50$

Figure 5: 3D-Bar chart for the reducing factors. The number of channels $h$
and number of cells $c$ within a module change in the ablation study. We
examine 4 different number of channels along the $x$ axis:
$h\in\\{1,4,8,10\\}$ and 5 different number of cells along the $y$ axis:
$c\in\\{1,2,3,4,5\\}$. The $z$ axis is the test accuracies of neural
architectures.

###  A.6 Variation in Rankings Using Different Parameter Initialization

Because the training-free NAS methods do a single forward/backward propagation
on models with randomly initialized parameters, it is potentially subjected to
different random initialization. To examine the variation in rankings due to
different initialization of model parameters, we repeat the computation of
metrics for 8 times. Each time, a different initialization is used, and the
initialization follows normal distribution. We use the pair rank difference to
indicate the variation in the rankings for a pair of two random processes. The
pair rank difference is defined by:

$\rm{pair\;rank\;difference}=\sum_{k=0}^{n}|\rm{rank}_{i}(a_{k})-\rm{rank}_{j}(a_{k})|$
(5)

where $n$ is the total number of neural architectures, on NAS-Bench-201
benchmark, $n=15,625$. $\rm{rank}_{i}(a_{k})$ and $\rm{rank}_{j}(a_{k})$ are
the ranking of $k$-th architecture in the $i$-th and $j$-th random
initialization processes, respectively. Considering the computational
overheads, we choose NASWOT, a NAS method requires training dataset, to
compute the variation in rankings in comparison with our method. We use 8
random seeds and compute the pair rank difference. Figure 6 shows the pair
rank difference on NAS-Bench-201 and different datasets. Because our method is
data-agnostic, it has the same mean and standard deviation across different
datasets. Our metric has a contiguously smaller variation in the rankings of
neural architectures. We believe one of the reasons is that the NASWOT method,
or other data-dependent NAS methods, has a random selection of minibatches and
the random initialization of model parameters. Our method, on the other hand,
is not subjected to the random selection of minibatches by using fixed inputs.
When we compute ranking correlations between the performance of neural
architectures and graph measures, we find there is negligible difference among
8 random initialization. So we believe that our method is not significantly
subjected to the different random initialization.

Figure 6: The variation of the architecture rankings using relu_logdet and
avg_deg as the ranking metric. The mean value and standard deviation is
calculated over 8 random seeds.

###  A.7 Evaluation of Different Graph Measures on NAS Benchmarks

In addition to average degree, we also examine other graph measures in the
training-free NAS. Those graph measures even exhibit a better performance than
the average degree on some benchmarks.

Graph measures. After converting neural architectures to graphs $G(V,E)$
($|V|=n$ and $|E|=m$) using NASGraph, we compute four graph measures as new
metrics to rank neural architectures in NAS benchmarks, namely, average
degree, density, resilience parameter, and wedge count. ① The average degree
$\bar{k}$ calculates the average number of edges for one graph node. To
compute the average degree for a DAG, we ignore the direction of the graph
edges. We have $\bar{k}=\frac{1}{n}\sum_{i\in V}k_{i}$, where $k_{i}$ is the
degree of node $i$. ② The density $d_{G}$ measures the ratio of the total
number of edges to the maximum number of possible edges,
$d_{G}=\frac{m}{n(n-1)}$. ③ The resilience parameter $\beta_{\rm{eff}}$ of a
DAG [41] is defined by
$\beta_{\rm{eff}}=\frac{\mathbf{1}^{T}\mathbf{A}\mathbf{s}^{\rm{in}}}{\mathbf{1}^{T}\mathbf{A}\mathbf{1}}=\frac{\langle
s^{\rm{out}}s^{\rm{in}}\rangle}{\langle s\rangle}$, where
$\mathbf{1}=(1,\ldots,1)^{T}$ is the all-ones vector,
$\mathbf{s}^{\rm{in}}=(s^{\rm{in}}_{1},\ldots,s^{\rm{in}}_{n})$ is the vector
of incoming degrees, and $\mathbf{A}$ is the adjacency matrix of the graph. ④
The wedge count $\mathcal{W}_{G}$ counts the number of wedges [42], and a
wedge is defined as a two-hop path in an undirected graph. It is related to
the triangle density of an undirected graph. To compute the wedge count of a
DAG, we ignore the edge direction and use $\mathcal{W}_{G}=\sum_{i\in
V}\frac{1}{2}k_{i}(k_{i}-1)$. Table 8 summarizes these graph measures and
their computation complexity.

Table 8: Definition and computation complexity of the four graph measures used
in NASGraph.

| Average degree | Density | Resilience parameter [41] | Wedge count [42]
---|---|---|---|---
Definition | $\displaystyle\bar{k}=\frac{1}{n}\sum_{i\in V}k_{i}$ | $\displaystyle d_{G}=\frac{m}{(n-1)}$ | $\displaystyle\beta_{\rm{eff}}=\frac{\mathbf{1}^{T}\mathbf{A}\mathbf{s}^{\rm{in}}}{\mathbf{1}^{T}\mathbf{A}\mathbf{1}}$ | $\displaystyle\mathcal{W}_{G}=\sum_{i\in V}\begin{pmatrix}k_{i}\\\ 2\end{pmatrix}$
Time complexity | $O(m+n)$ | $O(m+n)$ | $O(n^{2}+m)$ | $O(m+n)$

Figure 2 shows the evaluation on average degree and density. The ranking
correlations for all 4 graph measures (average degree $\bar{k}$, density
$d_{G}$, resilience parameter $\beta_{\rm{eff}}$ and wedge count
$\mathcal{W}_{G}$) on NAS-Bench-101 and NAS-Bench-201 are shown in Figure 7.
The surrogate model we use is NASGraph(16, 1, 3). On NAS-Bench-101, density is
the best graph measure. On NAS-Bench-201, average degree is the best graph
measure across different datasets. The ranking correlation for the same graph
measure does not change significantly across three datasets on NAS-Bench-201,
indicating the good generality of these graph measures. The average degree and
density are correlated since they are all related to the number of graph edges
within a unit (total number of graph nodes or maximum number of possible
edges). On NAS-Bench-201, the difference in the ranking correlation between
average degree and density is marginal. However, the difference becomes larger
on NAS-Bench-101. The density essentially consider the graph $G(V,E)$ as
directed graph while the average degree take it as undirected graph (since we
remove directionality of the graph edge). As the NAS benchmark size increases,
considering $G(V,E)$ as undirected graph might be inferior given the fact that
information flow in the neural architecture is directional and acyclic (Note:
we are not discussing recurrent neural networks in this paper).

Figure 7: The ranking correlations between graph measures of the converted
graphs and test accuracy of the corresponding neural architectures on NAS-
Bench-201. 3 graph measures (NASGraph metrics) are examined: average degree
(avg_deg), density (density), resilience parameter (resilience) and wedge
count (wedge). Table 9: Comparison between the surrogate models NASGraph(16,
1, 3) and NASGraph(4, 5, 3) across different benchmarks and datasets.

Methods | Metric | NAS-Bench-101 |  | NAS-Bench-201
---|---|---|---|---
CIFAR-10 |  | CIFAR-10 |  | CIFAR-100 |  | ImageNet-16-120
|  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$
NASGraph(4, 5, 3)† | density | 0.50 | 0.35 |  | 0.75 | 0.56 |  | 0.77 | 0.57 |  | 0.75 | 0.55
avg_deg | 0.38 | 0.27 |  | 0.76 | 0.57 |  | 0.78 | 0.58 |  | 0.76 | 0.56
resilience | 0.34 | 0.23 |  | 0.74 | 0.54 |  | 0.75 | 0.55 |  | 0.73 | 0.53
wedge | 0.34 | 0.24 |  | 0.76 | 0.57 |  | 0.78 | 0.58 |  | 0.76 | 0.56
NASGraph(16, 1, 3) | density | 0.45 | 0.31 |  | 0.77 | 0.57 |  | 0.78 | 0.59 |  | 0.75 | 0.56
avg_deg | 0.38 | 0.26 |  | 0.78 | 0.58 |  | 0.80 | 0.60 |  | 0.77 | 0.57
resilience | 0.31 | 0.21 |  | 0.68 | 0.49 |  | 0.69 | 0.50 |  | 0.67 | 0.48
wedge | 0.33 | 0.23 |  | 0.77 | 0.57 |  | 0.79 | 0.59 |  | 0.76 | 0.56
Optimal single metric | 0.50 | 0.35 |  | 0.78 | 0.58 |  | 0.80 | 0.60 |  | 0.77 | 0.57

  * •

$\dagger$ Number of cells within one module is 3 on NAS-Bench-101 while 5 on
NAS-Bench-201. Because we only reduce the number channels, the surrogate model
for NAS-Bench-101 is NASGraph(4, 3, 3) instead of NASGraph(4, 5, 3) on NAS-
Bench-201.

Table 10: Ranking correlations $\rho$ between the validation accuracies and
NASGraph metrics using different surrogate models. Because the structure of
modules and cells is encoded in the arch string such as 64-41414-1_02_333 (we
refer the reader to [27] for details on the arch string), we only change the
number of channels.

Metric | Micro TransNAS-Bench-101
---|---
class_object |  | class_scene |  | room_layout |  | segment_semantic
$\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$ |  | $\rho$ | $\tau$
4 Channels
avg_deg | 0.56 | 0.39 |  | 0.71 | 0.51 |  | 0.38 | 0.25 |  | 0.67 | 0.48
density | 0.54 | 0.37 |  | 0.68 | 0.49 |  | 0.37 | 0.24 |  | 0.60 | 0.43
resilience | 0.62 | 0.44 |  | 0.75 | 0.55 |  | 0.47 | 0.31 |  | 0.33 | 0.23
wedge | 0.60 | 0.42 |  | 0.74 | 0.54 |  | 0.43 | 0.28 |  | 0.68 | 0.49
16 Channels
avg_deg | 0.55 | 0.38 |  | 0.70 | 0.50 |  | 0.37 | 0.24 |  | 0.66 | 0.47
density | 0.53 | 0.36 |  | 0.68 | 0.48 |  | 0.35 | 0.22 |  | 0.55 | 0.39
resilience | 0.62 | 0.43 |  | 0.74 | 0.54 |  | 0.47 | 0.31 |  | 0.34 | 0.24
wedge | 0.59 | 0.41 |  | 0.74 | 0.54 |  | 0.42 | 0.27 |  | 0.68 | 0.49

As indicated in Figure 5, decreasing number of cells or number of channels
does not cause a huge effect on the rankings of graph measures. In addition to
reduce the number of cells (the surrogate model NASGraph(16, 1, 3)), we also
examine the effect of reducing the number of channels (the surrogate model
NASGraph(4, 5, 3)). The comparison of the ranking correlation using different
surrogate models is shown in the Table 9. These two surrogate models, as
expected, have a similar ranking correlation across NAS-Bench-101 and NAS-
Bench-201.

In addition to these two benchmarks, we also examine the performance of
different surrogate model on TransNAS-Bench-101. Because the number of cells
and modules are fixed in the arch string (the way to represent neural
architecture on the benchmark), we only change the number of channels. Table
10 shows the evaluation of two surrogate models. There are only marginal
difference between two graph measures across three tasks.

Overall, as indicated in the ablation study, decreasing number of channels and
decreasing number of cells do not have a significant change in the rankings of
graph measures. Based on graph theory, decreasing number of cells is
preferred.

###  A.8 Combination of Training-free NAS Metrics

We combine graph measure with training-free NAS metrics (rank(avg_deg) +
rank(jacob_cov)) to boost the ranking correlation between metrics and
performance of neural architectures. Figure 8 shows the relationship between
combined ranks and test accuracies across CIFAR-10, CIFAR-100 and
ImageNet-16-120 datasets. We note that avg_deg is data-agnostic while
jacob_cov is data-dependent.

Figure 8: Combined rank (rank(avg_deg) + rank(jacob_cov)) of neural
architectures of NAS-Bench-201 vs test accuracy. (a) CIFAR-10. (b) CIFAR-100.
(c) ImageNet-16-120.

###  A.9 Random Search in NAS

Algorithm 1 shows the process of random search using a single metric. A total
number of $N$ neural architectures are randomly sampled from the same NAS
benchmark such as NAS-Bench-101. Metrics are computed as the score by a single
forward/backward propagation of neural architectures with randomly initialized
parameters. In the NASGraph framework, we convert neural architectures to
graphs and then compute graph measures such as average degree to rank neural
architectures. The performance, e.g. test accuracy, of the neural architecture
with the highest graph measure is extracted as the performance of the metric.
The highest performance of the selected $N$ architectures are used as GT.

Algorithm 1 Random Search Algorithm Using Single Metric

1: net_generator = RandomGenerator()

2: score_highest, net_best = None, 0

3: for $i=1:N$ do

4: net = net_generator.pick_net()

5: score = ComputeMetric(net)

6: if score $>$ score_highest then

7: score_highest = score

8: net_best = net

9: end if

10: end for

11: acc_best = ExtractAccFromBenchmark(net_best)

###  A.10 Cell Structure

We visualize the best and the worst cell structures ranked by avg_deg on NAS-
Bench-201 as shown in Figure 9. Edge with none operation is not shown for
better visualization. The best cell structure found by our metric is same as
synflow. The worst cell structures share a same feature: there is an isolated
node of cell structure. The isolated node in NAS-Bench-201 means extracted
features from preceding neural layers are disregarded, and the effective depth
of neural architecture becomes shallower. Therefore, it is expected those
architectures have a poor performance.

Figure 9: The top 6 best and top 6 worst cell structures ranked by average
degree of NASGraph on NASBench-201. Architectures are ranked by the graph
measure avg_deg.

###  A.11 Special NASGraphs

Figure 10 shows the visualization of the converted graphs using the surrogate
model NASGraph(4, 3, 5) corresponding to the best architecture and the worst
architecture (ranked by the test accuracy) in NAS-Bench-101 and NAS-Bench-201.
Instead of ranking architectures by the graph measures (as the ranking metric
in Figure 2), we rank architectures by the test accuracy. As indicated by
graph measures, the best graph is much denser compared to the worst graph.

Figure 10: The converted graphs corresponding to the best architecture and the
worst architecture on NAS-Bench-101 and NAS-Bench-201. Architectures are
ranked by the test accuracy.

###  A.12 Supplementary Results on NAS Benchmarks

In addition to NAS-Bench-201, TransNAS-Bench-101 and NDS, we also compare our
method with NAS-Bench-101, the result is shown in the Table 11. Our proposed
method has a performance close to the SOTA method.

Table 11: Comparison of the ranking correlation between NASGraph and training-
free NAS methods on the NAS-Bench-101 benchmark.

Method | Metric | NAS-Bench-101
---|---|---
CIFAR-10
|  | $\rho$ | $\tau$
NASWOT | relu_logdet | - | 0.31
ZiCo | zico | 0.45 | 0.31
Zero-Cost NAS | grad_norm | 0.20 | -
snip | 0.16 | -
grasp | 0.45 | -
fisher | 0.26 | -
synflow | 0.37 | -
jacob_cov | 0.38 | -
Ours | avg_deg | 0.38 | 0.26


# Cross-Modality Gated Attention Fusion for Multimodal Sentiment Analysis

Ming Jiang
Aalto University, Finland
<EMAIL_ADDRESS>
&Shaoxiong Ji
Aalto University, Finland
<EMAIL_ADDRESS>

###### Abstract

Multimodal sentiment analysis is an important research task to predict the
sentiment score based on the different modality data from a specific opinion
video. Many previous pieces of research have proved the significance of
utilizing the shared and unique information across different modalities.
However, the high-order combined signals from multimodal data would also help
extract satisfied representations. In this paper, we propose CMGA, a Cross-
Modality Gated Attention fusion model for MSA that tends to make adequate
interaction across different modality pairs. CMGA also adds a forget gate to
filter the noisy and redundant signals introduced in the interaction
procedure. We experiment on two benchmark datasets in MSA, MOSI, and MOSEI,
illustrating the performance of CMGA over several baseline models. We also
conduct the ablation study to demonstrate the function of different components
inside CMGA.

##  1 Introduction

With the vast popularity of social media in recent years, we can get a
connection with more kinds of content, not only the text and figures but also
the videos. Videos, including movies, TV shows, and short-form video streams,
naturally consist of multimodal data types: the content of the text, visual
(video frames), and acoustic (voice of speakers). Moreover, many of them
usually have specific sentiment tendencies, which express the current
emotional status of the speakers. It is essential to understand these
sentiment tendencies.

Across different modalities, there would be some shared and some unique
information. Given an opinion video, its text is a pure statement of the
opinion and contains semantic information. The visual modality exposes
speakers’ expressions. The acoustic modality captures the tone of voice. These
latter two types of information can not only be supplementary to understand
the video better but also correct the misleading information in the textual
modality (Ngiam et al., 2011). As a result, the features contained in
different modalities could help predict a more accurate sentiment score.

Figure 1: Multimodal Sentiment Prediction Pipeline. An opinion video includes
three modalities: text, video, and audio. The interaction among modalities is
useful for the prediction of an accurate sentiment score.

Many researchers have implemented deep learning methods on the multimodal data
with good results achieved, illustrating the advantages of utilizing
multimodal data beyond one single modality. As for the Multimodal Sentiment
Analysis (MSA) problem, it is crucial to fuse the shared information across
different modalities and keep the unique information of a single modality.
Some research methods focus on finding a vector space that contains these two
kinds of signals simultaneously. For example, Zadeh et al. (2017) makes the
three modalities interact with each other by extending the respective vector
space into a shared tensor space with the 3-fold Cartesian product. However,
it is difficult for these methods to distinguish the unique signals inside
different modalities from the common interacted vector space. The extended
common interacted vector space would contain the noisy and redundant signals,
which are misleading and not valid for the downstream classification task.
Other methods aim to learn the two kinds of information separately. For
example, Hazarika et al. (2020) proposes a model to learn two different
subspaces of the three modalities, one of which is the shared encoder space.
At the same time, the other one is the private space for maintaining unique
signals. However, it lacks adequate interaction across the extracted
information in subspaces of different modalities.

We propose a Cross-Modality Gated Attention (CMGA) fusion model to alleviate
these issues. CMGA aims to learn the cross-modality features that best
summarize the interaction signals across different modalities and maintain the
signals that are effective for MSA. Specifically, we first divide the three
modalities into three different pairs and generate the cross-modality
attention feature maps of them, which are motivated by the design of the
attention mechanism proposed by Vaswani et al. (2017). After this, CMGA pass
the cross-attention maps into a forget gate designed to filter the noisy and
redundant signals contributing little to the downstream prediction task. We
use a residual connection proposed by He et al. (2016) to enhance the original
modality signal and avoid the degradation problem. Finally, we input the
cross-modality interaction features into a transformer-based fusion layer to
predict sentiment scores. We evaluate the performance of CMGA on two famous
benchmark datasets, CMU-MOSI and CMU-MOSEI, collected by Zadeh et al. (2018b).
Experiments show that CMGA outperforms several baseline models in most of the
evaluation metrics. In addition, we also conduct two ablation studies on CMGA
to illustrate the role of different components and the role of different
modality data.

##  2 Methodology

###  2.1 Problem Setup and Feature Extraction

Given an utterance $U=\\{u_{m}\\}_{m\in\\{t,v,a\\}}$, its raw feature vectors
contains three modalities in form of text, video and audio. Our goal is to
find the optimal interacted feature $h_{(t,v,a)}$ cross the three modalities
that best represent the original utterance $U$ and predict the sentiment score
$\tilde{y}$ that close to the ground truth $y\in\mathbb{R}$.

We utilize pre-trained BERT (Devlin et al., 2018) as the feature extractor for
the textual inputs and obtain the final embedding of textual features by
averaging the tokens’ representations across the hidden states. The visual and
acoustic features are obtained by a stacked bi-directional Long Short Term
Memory (bi-LSTM) (Hochreiter and Schmidhuber, 1997). Here, we get the
embedding of the two modalities $u_{v}$ and $u_{a}$ by projecting the final
state of LSTM into a fully-connected (FC) layer. We project each modality’s
features with a linear layer to obtain the representations of each modalities
$\mathbf{z}_{m\in\\{t,v,a\\}}\in\mathbb{R}^{d_{k}}$ with the same dimension
size $d_{k}$.

###  2.2 Modality Interaction

####  2.2.1 Cross-modality Attention

Figure 2: Architecture of CMGA. The multimodal features are separately
extracted from respective models, and calculated the cross-modality
interaction features within modality pairs. The fusion layer is a transformer
encoder layer followed by a fully-connected layer.

The cross-modality attention aims to get the interacted signals across
different modalities. Every two modalities would be one pair of inputs, i.e.,
i) from text to visual; ii) from visual to acoustic; iii) from text to
acoustic. Here, we define the modality pair as a set
$P=\\{(t,v),(v,a),(t,a)\\}$.

The interaction feature generator inputs a pair of modalities
$\mathbf{z_{(i,j),(i,j)\in P}}$. The first one is utilized to generate key and
value matrices, while the second modality is used to generate the query
matrix, i.e., $\mathbf{Q_{(i,j)}}=\mathbf{z_{j}}\mathbf{W^{Q_{j}}}$,
$\mathbf{K_{(i,j)}}=\mathbf{z_{i}}\mathbf{W^{K_{i}}}$, and
$\mathbf{V_{(i,j)}}=\mathbf{z_{i}}$. Then, the cross-modality attention
$\mathbf{a}_{(i,j)}$ of modalities pair $(i,j)$ is transformed via a scaled
dot-product (Vaswani et al., 2017). We obtain the cross-modality attention
features $\mathbf{A}=\\{\mathbf{a}_{(i,j)}\\}_{(i,j)\in P}$ from each
modality.

####  2.2.2 Cross-modality Forget Gate

The cross attention maps enables the model to capture the interaction between
different modalities. However, $\mathbf{a}_{(i,j)}$ of a pair modality $(i,j)$
also contains plenty of redundant and noisy information. This part of
information can obscure the instrumental interaction signals, leaving the
original information of each modality still dominating the classification
results in the downstream classification task. As a result, we might not fully
exploit and utilize the additional interaction information across different
modalities. Therefore, motivated by the gated unit (Cho et al., 2014), we add
a cross-modality forget gate to filter the redundant information and activate
the useful cross-modality signal. As shown in Fig. 3, the gate received the
cross-modality attention generated in Section. 2.2.1, and pass it through a
forget cell to generate the filtered cross-modality features. Specifically,
the cross-modality attention map, which contains the modality pair’s
interacted signal, would first be used to generate a forget vector. The forget
vector controls the information flow that would be memorized for the
downstream classification tasks. The forget vector ${f}_{(i,j)}$ of modality
pair $(i,j)$ is defined in Eq. 1.

$\mathbf{f}_{(i,j)}=\sigma([\mathbf{a}_{(i,j)}\oplus\mathbf{z_{j}}]\mathbf{W^{f}}+\mathbf{b^{f}})$
(1)

Next, the filtered features of modality pair $(i,j)$ are calculated as
follows:

$\mathbf{h}_{(i,j)}=\operatorname{ReLU}(\mathbf{z_{i}}+(\mathbf{a}_{(i,j)}\mathbf{W^{m}}+\mathbf{b^{m}})\odot\mathbf{f}_{(i,j)}),$
(2)

where $\odot$ is the element-wise product between two vectors, $\oplus$
denotes the concatenation, and $\mathbf{W^{f}}$, $\mathbf{W^{m}}$,
$\mathbf{b^{f}}$, $\mathbf{b^{m}}$ are trainable parameters. In addition, in
Eq. 2, we keep $z_{i}$ to enhance the signal of original modality, which is
motivated by the architecture of residual connection in ResNet proposed by He
et al. (2016).

Figure 3: Cross-modality interaction architecture with one of the three
modality pairs ($i,j$) for illustration

####  2.2.3 Fusion Layer

The output of the forget gate consists of two parts: i) the original modality
feature; as well as ii) the filtered cross-modality interaction. We obtain
three pairs of outputs every two types of modalities:
$\mathbf{H=\\{h_{i,j}\\}_{i,j\in t,v,a}^{i\neq j}}$. In this part, we stack
$H\in\mathbb{R}^{3\times d_{h}}$ across the three pairs and perform a multi-
head self-attention on them to make each representation perceive the potential
information remained in other cross-modality vector space, where $d_{h}$ is
the dimension size of each cross-modality features through the forget gate.
For each head $n$, we generate $\mathbf{Q_{n}}=\mathbf{HW^{q}_{n}}$,
$\mathbf{K_{n}}=\mathbf{HW^{k}_{n}}$ and $\mathbf{V_{n}}=\mathbf{HW^{v}_{n}}$,
where $\mathbf{Q},\mathbf{K},\mathbf{V}\in\mathbb{R}^{3\times d_{h}}$ and
$\mathbf{W^{q}_{n}}$, $\mathbf{W^{k}_{n}}$ and $\mathbf{W^{v}_{n}}$ are
trainable parameters. Through the transformer fusion layer, we could obtain a
new matrix $\tilde{H}$ via a scaled dot-product attention in Eq. 3.

$\tilde{\mathbf{H_{n}}}=\operatorname{Softmax}(\frac{\mathbf{Q_{n}}\mathbf{K_{n}^{\top}}}{\sqrt{d_{h}}})\mathbf{V_{n}}$
(3)

The final output after fusion layer is
$\tilde{y}=\tilde{\mathbf{H}}\mathbf{W^{o}}$, where
$\tilde{\mathbf{H}}=(\tilde{\mathbf{H_{1}}}\oplus...\oplus\tilde{\mathbf{H_{n}}})$,
and $\mathbf{W^{o}}\in\mathbb{R}^{3\times d_{h}\times 1}$ is trainable
parameter.

##  3 Experiments

Models | MOSI | MOSEI
---|---|---
MAE | corr | F-score | Acc-2 | Acc-7 | MAE | corr | F-score | Acc-2 | Acc-7
TFN | 0.901 | 0.698 | 80.7 | 80.8 | 34.9 | 0.593 | 0.700 | 82.1 | 82.5 | 50.2
LMF | 0.917 | 0.695 | 82.4 | 82.5 | 33.2 | 0.623 | 0.677 | 82.1 | 82.0 | 48.0
MFM | 0.877 | 0.796 | 81.6 | 81.7 | 35.4 | 0.568 | 0.717 | 84.3 | 84.4 | 51.3
ICCN | 0.860 | 0.710 | 83.0 | 83.0 | 39.0 | 0.565 | 0.713 | 84.3 | 84.2 | 51.6
MISA | 0.783 | 0.761 | 83.4 | 83.6 | 42.3 | 0.555 | 0.756 | 85.5 | 85.3 | 52.2
TFN∘ | 0.893 | 0.705 | 79.6 | 80.3 | 35.6 | 0.609 | 0.712 | 81.9 | 82.3 | 50.0
MISA∘ | 0.792 | 0.757 | 82.3 | 82.6 | 41.8 | 0.551 | 0.761 | 84.8 | 84.9 | 52.1
CMGA | 0.790 | 0.759 | 82.3 | 82.7 | 43.3 | 0.545 | 0.762 | 85.0 | 85.3 | 53.0
Table 1: Performance comparison of baselines and CMGA on MOSI and MOSEI
datasets. ∘ means the performance of reproduced model. For those without the
mark, the results are copied from the corresponding paper. The results of MISA
are the best scores from the original paper.

We experiment with two benchmarks with three modalities (language, visual, and
acoustic) in each utterance. The CMU-MOSI dataset (Zadeh et al., 2018b)
collects 2199 opinion video clips, each of which is annotated with a
continuous sentiment score in the range of [-3, 3]. The value of the score
represents the opinion attribution, where a smaller value close to -3 stands
for negative sentiment and a larger value close to +3 is more positive. The
CMU-MOSEI dataset (Zadeh et al., 2018b) is an advanced version of the CMU-MOSI
dataset, which collects more utterances from various speakers and topics. This
dataset has 23,453 sentence utterance videos from more than 1000 online
YouTube speakers with 250 different topics.

We compare the performance of CMGA with the following baseline models. TFN
(Zadeh et al., 2017) utilizes the tensors’ Cartesian space to calculate the
multiplicative interactions between different modalities. LMF (Liu et al.,
2018) uses a low-rank tensor to generate the representation of multimodal
inputs efficiently. MFM (Tsai et al., 2018) introduces the joint generative-
discriminative vector space, which factorizes representations into two sets of
independent factors. MISA (Hazarika et al., 2020) generates two independent
vector subspaces to capture the shared and unique information of different
modalities. ICCN (Sun et al., 2020) calculates the outer products between
text, acoustic and text, visual features, and then implements a Canonical
Correlation Analysis network for prediction.

In the LSTM models for acoustic and visual modalities, we implement a 2-layer
bidirectional with 512-dimensional hidden states and layer norm between
different layers. We implement a 12-layer transformer of 768-dimensional
hidden states with 12 heads in the BERT model for textual modality. We use the
pre-trained BERT tokenizers. After extracting different modalities, we project
them into the same size dimension of 128 by a fully-connected layer. We use
Mean Square Loss (MSE) and Adam optimizer (Kingma and Ba, 2014). Our initial
learning rate is 1e-4, and the model is trained on Tesla V100 GPUs.

###  3.1 Main Results

Table 1 shows the predictive performance. CMGA outperforms all other models
and has the most obvious improvement on acc-7 metric. CMGA outperforms MFM,
MISA and ICCN, demonstrating the importance of learning the adequate
interaction between different modalities.

###  3.2 Analysis of Modalities and Neural Modules

Table 2 shows the performance of CMGA without one specific modality. On both
MOSI and MOSEI datasets, the textual modality $u_{t}$ plays the most important
role. The performance drops sharply without $u_{t}$, showing that language
conveys rich information for accurate prediction. We divide our modality
interaction architecture into two separate parts, as described in Section 2.2.
Table 2 also shows the quantitative results of our model without one of the
two components.

Models | MOSI | MOSEI
---|---|---
MAE | Acc-7 | MAE | Acc-7
CMGA | 0.790 | 43.29 | 0.545 | 53.03
(-) text $u_{t}$ | 1.591 | 30.51 | 0.818 | 45.08
(-) video $u_{v}$ | 0.804 | 41.10 | 0.547 | 52.81
(-) audio $u_{a}$ | 0.812 | 42.10 | 0.550 | 52.79
(-) cross-attention | 0.845 | 41.55 | 0.587 | 52.02
(-) forget gate | 0.856 | 41.47 | 0.594 | 51.55
(+) bi-directional $h$ | 0.792 | 43.01 | 0.550 | 53.01
Table 2: Ablation study on the importance of modality and neural modules. (-)
represents missing for the mentioned factors, which include specific modality
or model component. (+) means add specific factors.

###  3.3 Roles of Modality Interaction

We reverse each modality pair and check the performance of CMGA to further
evaluate the order of modality pairs. Table 3 shows that the order between
video and audio does not affect the performance obviously, while the order of
textual modality is critical. As illustrate in Section 2.2.1, the first
modality $i$ in a pair $(i,j)$ is used to generate the key matrix
$\mathbf{K_{(i,j)}}$ and value matrix $\mathbf{V_{(i,j)}}$. Inside the
calculation of the attention map, we align the information of modality $j$
with modality $i$.

Models | MOSI | MOSEI
---|---|---
MAE | Acc-7 | MAE | Acc-7
CMGA | 0.790 | 43.29 | 0.545 | 53.03
$\sim$(text, video) | 0.814 | 41.22 | 0.561 | 52.13
$\sim$(video, audio) | 0.791 | 43.27 | 0.547 | 53.01
$\sim$(text, audio) | 0.804 | 42.27 | 0.551 | 52.84
Table 3: Performance comparison with different orders of modality pairs.
($\sim$) represents to reverse the mentioned modality pair ($i,j$) into
($j,i$).

##  4 Related Work

Sentiment analysis is a long-lasting research problem with many tasks such as
aspect level sentiment analysis (Lin et al., 2019), emotion recognition in
conversations (Li et al., 2022) and multimodal sentiment analysis (Soleymani
et al., 2017). Our paper focuses on multimodal sentiment analysis. This
section reviews the modality interaction methods, which is trying to find the
cross-modality features for different data modalities. Instead of the unimodal
features, recent research has proved the significance of utilizing both the
verbal and nonverbal information in multimodal sentiment analysis, such as the
video and acoustic. Zadeh et al. (2017) proposed the tensor fusion network
(TFN) to obtain a cross-view feature by calculating a 3-fold Cartesian
product. Verma et al. (2020) implemented convolution calculation on the
different cross-modality Cartesian spaces and fused them for the
classification task. Arevalo et al. (2017) placed a gated multimodal unit for
modalities fusion. Wang et al. (2020a) utilized channel exchanging to make
features of different modalities adequately integrated. Yu et al. (2021)
jointly training the multimodal and unimodal tasks, in which different
modalities would be aligned in the unimodal tasks and interact with each other
in the multimodal task.

Motivated by the success of transformers in many Natural Language Processing
tasks, Wang et al. (2020b) proposed an end-to-end transformer-based model for
sentiment analysis. This work proved the performance of transformer
architecture in modality interaction. A transformer is built on the attention
mechanism, whose intention to find the importance weights for different
feature maps is suitable for the cross-fusion of different modalities. In
addition, Zadeh et al. (2018a) implemented a Gated Memory Unit in the sequence
learning to summarize the cross-view interactions learned through the
attention units. In our work, the transformer-based model motivates the cross-
modality interaction component. The attention mechanism idea proposed by
Vaswani et al. (2017) comes from the query system, which is suitable for
different modalities to interact with each other in MSA tasks. In addition,
different from the previous works, we aim to filter the noisy and redundant
information that might be introduced in the modality interaction part.

##  5 Conclusion

This paper proposes CMGA, a multimodal learning framework that tends to
predict sentiment scores by generating cross-modality interaction features. We
combine the cross-attention map with the forget gate mechanism, which is
helpful to get adequate interaction among different modality pairs and
maintain the instrumental signals to represent the multimodal inputs. Our
experiments show that CMGA achieves competitive predictive performance in most
of the metrics. We evaluate the roles of importance for different modality
features and the components inside the cross-modality interaction learning
architecture, showing the importance of modality interaction.

## References

  * Arevalo et al. (2017) John Arevalo, Thamar Solorio, Manuel Montes-y Gómez, and Fabio A González. 2017.  Gated multimodal units for information fusion.  _arXiv preprint arXiv:1702.01992_.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014\.  On the properties of neural machine translation: Encoder-decoder approaches.  _arXiv preprint arXiv:1409.1259_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Hazarika et al. (2020) Devamanyu Hazarika, Roger Zimmermann, and Soujanya Poria. 2020.  Misa: Modality-invariant and-specific representations for multimodal sentiment analysis.  _arXiv preprint arXiv:2005.03545_.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Li et al. (2022) Wei Li, Wei Shao, Shaoxiong Ji, and Erik Cambria. 2022.  BiERU: Bidirectional emotional recurrent unit for emotion detection in conversations.  _Neurocomputing_ , 467:73–82.
  * Lin et al. (2019) Peiqin Lin, Meng Yang, and Jianhuang Lai. 2019.  Deep mask memory network with semantic dependency and context moment for aspect level sentiment classification.  In _IJCAI_ , pages 5088–5094.
  * Liu et al. (2018) Zhun Liu, Ying Shen, Varun Bharadhwaj Lakshminarasimhan, Paul Pu Liang, AmirAli Bagher Zadeh, and Louis-Philippe Morency. 2018.  Efficient low-rank multimodal fusion with modality-specific factors.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2247–2256, Melbourne, Australia. Association for Computational Linguistics.
  * Ngiam et al. (2011) Jiquan Ngiam, Aditya Khosla, Mingyu Kim, Juhan Nam, Honglak Lee, and Andrew Y Ng. 2011.  Multimodal deep learning.  In _ICML_.
  * Soleymani et al. (2017) Mohammad Soleymani, David Garcia, Brendan Jou, Björn Schuller, Shih-Fu Chang, and Maja Pantic. 2017.  A survey of multimodal sentiment analysis.  _Image and Vision Computing_ , 65:3–14.
  * Sun et al. (2020) Zhongkai Sun, Prathusha Sarma, William Sethares, and Yingyu Liang. 2020.  Learning relationships between text, audio, and video via deep canonical correlation for multimodal language analysis.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8992–8999.
  * Tsai et al. (2018) Yao-Hung Hubert Tsai, Paul Pu Liang, Amir Zadeh, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2018.  Learning factorized multimodal representations.  _arXiv preprint arXiv:1806.06176_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Verma et al. (2020) Sunny Verma, Jiwei Wang, Zhefeng Ge, Rujia Shen, Fan Jin, Yang Wang, Fang Chen, and Wei Liu. 2020.  Deep-hoseq: Deep higher order sequence fusion for multimodal sentiment analysis.  In _2020 IEEE International Conference on Data Mining (ICDM)_ , pages 561–570. IEEE.
  * Wang et al. (2020a) Yikai Wang, Wenbing Huang, Fuchun Sun, Tingyang Xu, Yu Rong, and Junzhou Huang. 2020a.  Deep multimodal fusion by channel exchanging.  _Advances in Neural Information Processing Systems_ , 33:4835–4845.
  * Wang et al. (2020b) Zilong Wang, Zhaohong Wan, and Xiaojun Wan. 2020b.  Transmodality: An end2end fusion method with transformer for multimodal sentiment analysis.  In _Proceedings of The Web Conference 2020_ , pages 2514–2520.
  * Yu et al. (2021) Wenmeng Yu, Hua Xu, Ziqi Yuan, and Jiele Wu. 2021.  Learning modality-specific representations with self-supervised multi-task learning for multimodal sentiment analysis.  _arXiv preprint arXiv:2102.04830_.
  * Zadeh et al. (2017) Amir Zadeh, Minghai Chen, Soujanya Poria, Erik Cambria, and Louis-Philippe Morency. 2017.  Tensor fusion network for multimodal sentiment analysis.  _arXiv preprint arXiv:1707.07250_.
  * Zadeh et al. (2018a) Amir Zadeh, Paul Pu Liang, Navonil Mazumder, Soujanya Poria, Erik Cambria, and Louis-Philippe Morency. 2018a.  Memory fusion network for multi-view sequential learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Zadeh et al. (2018b) Amir Zadeh, Paul Pu Liang, Soujanya Poria, Prateek Vij, Erik Cambria, and Louis-Philippe Morency. 2018b.  Multi-attention recurrent network for human communication comprehension.  In _Thirty-Second AAAI Conference on Artificial Intelligence_.