Generalizing and Tensorizing Subgraph Search in the Supernet
Authors: Hansi Yang
quanming yao
Venue:  (2021)
Keywords: deep learning
neural architecture search
tensor decomposition

Abstract: Recently, a special kind of graph, i.e., supernet, which allows two nodes connected by multi-choice edges, has exhibited its power in neural architecture search (NAS) by searching better architectures for computer vision (CV) and natural language processing (NLP) tasks. In this paper, we discover that the design of such discrete architectures also appears in many other important learning tasks, e.g., logical chain inference in knowledge graphs (KGs) and meta-path discovery in heterogeneous information networks (HINs). Thus, we are motivated to generalize the supernet search problem on a broader horizon. However, none of the existing works are effective since the supernet's topology is highly task-dependent and diverse. To address this issue, we propose to tensorize the supernet, i.e. unify the subgraph search problems by a tensor formulation and encode the topology inside the supernet by a tensor network. We further propose an efficient algorithm that admits both stochastic and deterministic objectives to solve the search problem. Finally, we perform extensive experiments on diverse learning tasks, i.e., architecture design for CV, logic inference for KG, and meta-path discovery for HIN. Empirical results demonstrate that our method leads to better performance and architectures.


Under review as a conference paper at ICLR 2021
GENERALIZING AND SEARCH IN THE SUPERNET
TENSORIZING
SUBGRAPH
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, special kind of graph, i.e., supernet, which allows nodes connected by multi-choice edges, has exhibited its power in neural architecture search (NAS) by searching better architectures for computer vision (CV) and natural language processing (NLP) tasks. In this paper, we discover that the design of such discrete important architectures also appears in many other important learning tasks, e.g., logical chain inference in knowledge graphs (KGs) and meta-path discovery in heterogeneous information networks (HINs). Thus, we are motivated to generalize the supernet search problem on broader horizon. However, none of the existing works are effective since the supernet's topology highly task-dependent and diverse. To address this issue, propose to tensorize the supernet, i.e., unify the subgraph search problems by tensor formulation and encode the topology inside the supernet by tensor network. We further propose efficient algorithm that admits both stochastic and deterministic objectives to solve the search problem. Finally, we perform extensive experiments diverse learning tasks, i.e., architecture design for CV, logic inference for KG, and meta-path discovery for HIN. Empirical results demonstrate that our method leads better performance and architectures.
INTRODUCTION
Deep learning (Goodfellow et al., 2017) has been successfully applied in many applications. such as image classification for computer vision (CV) (LeCun al., 1998; Krizhevsky al., 2012; He et al., 2016; Huang et al., 2017) and language modeling for natural language processing (NLP) (Mikolov et al., 2013; Devlin al., 2018). While the architecture design of great importance to deep learning, manually designing proper architectures for certain task is hard and requires lots of human efforts or sometimes even impossible (Zoph & Lc, 2017: Baker et al., 2016).
Recently, neural architecture search (NAS) techniques (Elsken et al., 2019) have been developed to alleviate this issue, which mainly focuses on CV and NLP tasks. Behind existing NAS methods, a multi-graph (Skiena., 1992) structure, i.e., supernet (Zoph al., 2017; Pham al., 2018; Liu et al., 2018), where nodes are connected by edges with multiple choices, has played a central role. In such context, the choices on each edge are different operations, and the subgraphs correspond different neural architectures. The objective here is to find suitable subgraph in this supernet, i.c. better neural architectures for given task.
However, the supernet does not only arise in CV/NLP field and we find it also emerge in many other deep learning areas (see Table 1). An example is logical chain inference knowledge graphs (Yang et al., 2017; Sadeghian et al., 2019; Qu & Tang, 2019), where the construction logical rules can be modeled by supernet. Another example is meta-path discovery in heterogeneous information networks (Yun et al., 2019; Wan et al., 2020), where the discovery of meta-paths can also be modeled by a supernet. Therefore, we propose to broaden the horizon of NAS, i.e., generalize many deep learning fields and solve the new NAS problem under unified framework.
Since subgraphs are discrete objects (choices on each edge are discrete), it has been a common approach (Liu et al., 2018; Sadeghian et al., 2019; Yun et al., 2019) to transform it into a continuous optimization problem. Previous methods often introduce continuous parameters separately for each edge. However, this formulation cannot generalize different supernets as the topological structures of supernets are highly task- desendependent and diverse. Therefore, it will fail to capture the supernet's topology and hence be ineffective.

---

Under review as a conference paper at ICLR 2021
Table 1: A comparison of existing NAS/non-NAS works for designing discrete architectures based on our tensorized formulation for the supernet. "Topology" indicate topological structure of the supernet utilized or not.
supernet
optimization algorithm
representative method
domain
encoding
topology
existing
NASNet (Zoph et al., 2017)
CV
RNN
policy gradient
NAS works
ENAS (Pham al., 2018)
CV/NLP
RNN
policy gradient
DARTS (Liiu et al., 2018)
CV/NLP
rank-1 CP
X
gradient descent
SNAS (Xie et al., 2018)
CV
X rank-1 CP
gradient descent
NASP (Yao et al., 2020)
CV/NLP
rank-1 CP
X
proximal algorithm
non-NAS DRUM (Sadeghian et al., 2019)
KG
rank-n CP
X
gradient descent
works
GTN (Yun et al., 2019)
HIN
rank-1 CP
gradient descent X
gradient descent
proposed
TRACE
all
TN
In this paper, we propose a novel method TRACE to introduce a continuous parameter for each subgraph (all these parameters will form a tensor). Then, we propose construct tensor network (TN) (andrzej. et al., 2016; 2017) based on the topological structure of supernet. For different tensor networks, we introduce efficient algorithm for optimization on supernets. Extensive experiments are conducted on diverse deep learning tasks. Empirical results demonstrate that TRACE performs better than the state-of-the-art methods in each domain. As a summary, our contributions are as follows:
We broaden the horizon of existing supernet- based NAS methods. Specifically, we generalize the concept of subgraph search in supernet from NAS to other deep learning tasks that have graph-like structures and propose to solve them in unified framework by tensorizing the supernet.
While existing supernet- encode the supernet in topology-awan manner based the tensor network and propose an efficient algorithm to solve the search problem.
NAS methods ignore the topological structure of the supernet, we
We conduct extensive experiments on various learning tasks, i.e., architecture design for CV, logical inference for KG, and meta-path discovery for HIN. Empirical results demonstrate that our method can find better architectures, which lead to oate-offthe-ant performance on various applications.
RELATED WORKS
2.1 SUPERNET IN NEURAL ARCHITECTURE SEARCH (NAS)
There have been numerous algorithms proposed to solve the NAS problem. The first NAS work, NASRL (Zoph & Le, 2017), models the NAS problem as a multiple decision making problem and proposes use reinforcement learning (RL) (Sutton & Barto, 2018) to solve this problem. However, this formulation does not consider the repetitively stacked nature of neural architectures and very inefficient it has to train many different networks converge. To alleviate this issue, NASNet (Zoph et al., 2017) first models NAS as an optimization problem on supernet. The supernet formulation enables searching for transferrable architectures across different datasets and improves the searching efficiency. Later, based on the supernet formulation, ENAS (Pham et al., 2018) proposes weight-sharing techniques, which shares the weight of each subgraph in a supernet. This technique further improves searching efficiency and many different methods have been proposed under this framework (see Table 1), including DARTS (Liu et al., 2018), SNAS (Xie et al., 2018), and NASP (Yao et al., 2020). DARTS is the first to introduce deterministic formulation to NAS field, and SNAS uses a similar parametrized method with DARTS under stochastic formulation. NASP improves upon DARTS by using proximal operator (Parikh & Boyd, 2014) and activates only one subgraphs in each iteration to avoid co-adaptation between subgraphs.
2.2 TENSOR METHODS IN MACHINE LEARNING
A tensor (Kolda & Bader, 2009) is a multi-dimensional array as an extension to a vector or matrix. Tensor methods have found wide applications in machine learning, including network
2

---

Under review as a conference paper at ICLR 2021
compression (Novikov et al., 2015; Wang et al., 2018) and knowledge graph completion (Liu et al., 2020). Recently, andrzej. et al. (2016; 2017) have proposed a unified framework called tensor network (TN), which uses undirected graph represent tensor decomposition methods. By using different graphs, TN can cover many tensor decomposition methods as a special case, e.g., CP (Bro, 1997). Tucker (Tucker, 1966), tensor train (Oseledets, 201 1), and tensor ring decomposition (Zhao et al., 2016). However, it is not an easy task to construct a tensor network for given problem, as the topological structure of tensor network is hard to design (Li & Sun, 2020).
3 PROPOSED METHOD
Here, describe method for the supernet search problem. Section 3.1-3.2 introduce how fensorize the supernets. Section 3.3 propose an optimization algorithm for the search problem which be utilized for both stochastic and deterministic objectives. Finally, how supernet appears beyond existing NAS works and can be generalized to these new tasks are presented in Section 3.4.
In this paper, will use S to denote supernet, and P to denote subgraph in supernet. For supernet S with 7 edges, we let all edges be indexed by et, eT, and define C. to be the number of choices on edge e, with E [1,..., T). With subscript 11,...,, 'T denoted by i_ for short, Cr}. And we
Notations.
we use S to denote the subgraph with choices 1 E {l...., Ci)...,,iy E use softmax(o:) exp(o:)/ 2j exp(o;) to denote the softmax operation over a vector E RR".
3.1 A TENSOR FORMULATION FOR SUPERNET
While existing works (Liu et al., 2018; Zoph et al., 2017: Pham et al., 2018) introduce parameters separately for each edge 6t, since edges may correlate with each other, a more general and natural approach is to introduce continuous parameter directly for each subgraph P E S. Note that subgraph P can be distinguished by its choices on each edge, we propose to encode all possible choices into tensor T C xxx and take these choices as indices, i.e., i_. to the tensor T. As a consequence, the architecture of the subgraph P indexed as S., and T [0, represent how "good" p can be.
Choice
Choice
Suhnet Py = Syys
Supemet 8
Py 892z Tizs
Figure An example of supernet and two subgraphs with index i..
Let [w, P) stand for learning model with the parameter ur and subgraph P T, be the loss of ff on the training dataset Du. and J measure the performance of f on the validation set D Under above tensor formulation, the search objective here
1 (P)()) (P) arg min L (f(w, Dw) Σ. Te =1
max
(P), s.t. PET
(1)
Same as existing supernet search works, the subgraph P is searched in the upper-level, while the network weight w trained the lower-level. Dú is the training set and D is the validation set. However, we have the extra constraint >, T. here, which is to ensure that the sum of probabilities for all subgraphs is
Next, we show how P and T can be parameterized with topological information from the supernet in Section 3.2. Then, gradient-basee algorithm which can effectively handle the constrained bi-level optimization problem (1) is proposed Section 3.3.
3.2 ENCODING SUPERNET TOPOLOGY BY TENSOR NETWORK (TN)
Existing methods consider each edge separately and can be seen rank-1 factorization of the full tensor T (see Table !) under (1), i.e. T = 8) ... o where 8 E R is the continuous parameter for choice on edge t. However, this formulation ignores the topological structure of different supernets, as it uses the same decomposition method for all supernets. Motivated by such limitation, we propose introduce tensor network (TN) to better encode the topological structure of supernet. Our encoding
3

---

Under review as a conference paper at ICLR 2021
0
F1
(a) Linear supernet.
(b) for (a).
(c) Full supernet.
(d) for (c).
Figure 2: Some examalphaple of supernets and the corresponding tensor networks (TNs). Information flows in supernet (a) (c) follow the order of number blocks. Circles in (b) and (d) represent core tensors and edges represent indices. Edges connected by two circles indicate index summation
(1) or (t)) where N1 (1) (or N2(()) is the index of nodes supernet (1, 2 in (a) and 0, 1,2 in (c)). The formula of (b) is T2 = Enirz Pigy a (1, 0 13.72 and the formula of (d) is
T T2dd Era.ri.r a ro da
a a Paaiairo"
process is described in Algorithm 1, where ((S) to denotes the set of nodes in this supernet and (S) (S)) denotes the of nodes that are connected to more than one edge.
Specifically, we introduce a third-order tensor a' for each edge, which is based on previous methods (e.g.. DARTS and SNAS), but tensors instead of vectors allow more flexibility. And introduce hyper-parameters Rv, (1) and (t) which are corresponding to the rank of tensor network. Then, we use index summation reflect the topological structure (common nodes) between different edges, i.c.
Σ
Rn
II
T
of 107
PEN
We also give two examples in Figure to illustrate our tensorizing process for two specific supernets.
Algorithm 1 Supernet encoding process (a step-by-step and graphical illustration is in Appendix.Ci
Input:
Supernet S;
1: Introduce a² E "Rrcc XC2 Ayy(0 for edge e, which connects nodes (t) and N2(t);
2: Remove isolated nodes and obtain (S);
3: Compute T, by (2);
4: return encoded supernet T
The reason of using (8) instead of (S) is Proposition which shows that using (S) will not restrict the expressive power but allows the usage of less parameters.
Proposition 1. Any tensors that can be expressed by T:_ = LnnmeN(s) IT of of,, (o,,cord can also be expressed by T__ -mm.nEN'()) | Fo
Rn
3.3 SEARCH ALGORITHM
To handle subgraph search problems for various applications (Table 1), we need an algorithm that can solve the generalized supernet search problem in (1), which is parameterized by (2). However, the resulting problem is hard to solve, as we need to handle the constraint on T, i.e. Σ. Tr_ 1.
To address this issue, we propose to re- re-parameterize a in (2) using softmax trick, i.e.,
Tz_ 1/TTnex'(s R,,
II E
Rn
softmax ( (e
(3)
REN
Then, the optimization objective J in (1) becomes
max [z( (());
w w*()) arg min L ((f ((B))
(4)
Figure 2(b) and (d) also follow the diagram figure tensor network, reader may refer (andrzej. et al., 2017)
for more details.
All proofs are Appendix D.
4

---

Under review as a conference paper at ICLR 2021
where we have substitute discrete subgraphs P and normalization constraint on T with continuous parameters 3. As shown in Proposition 2, we can now solve a unconstrained problem on 3, while keeping the constraint on T satisfied.
Proposition 2. Σ._ T
L, where T is given in (3).
Thus, gradient-basee training strategies can be reused, which makes the optimization very efficient. The complete steps for optimizing (4) are presented in Algorithm 2. Note that, our algorithm can solve both deterministic and stochastic formulation (see Appendix A). After the optimization of is converged, we obtain Pa from tensor T and retrain the model to obtain wt.
Algorithm 2 TRACE: Proposed subgraph search algorithm.
Input: A subgraph search problem with training set Du, validation set Vall and supernet S; I: Tensorize the supernet T with Algorithm 1;
2: Re-parameterize T to T using (3);
3: while not converged do
4: Obtain a subgraph P from T (deterministic or stochastic);
5: Solve w (3) arg min,, & (J(w,, 13,, Dr))
6: Update supernet parameters by gradient ascending V VaJp:
7:
end while
8:
Obtain D S from the final T by setting i- arg max,, T
9: Obtain w²((") arg mi: & (f P=), Du) by retraining f(w. PT);
10: return Pd (searched architecture) and w" (fine-tuned parameters);
3.4 SUBGRAPH SEARCH BEYOND EXISTING NAS
Despite NAS, there are many important problems in machine learning that have a graph-like structure. Examples include meta- meta-path discovery (Yang et al., 2018; Yun et al., 2019; Wan et al., 2020), logical chain inference (Yang et al., 2017; Sadeghian et al., 2019) and structure learning between data points (Franceschi et al., 2019). Inspired by the recent work that exploits graph-like structures in NAS (Li et al., 2020; You et al., 2020), we propose to model them also as a subgraph search problem on supernets.
Meta-path discovery. Heterogeneous information networks (HINs) (Sun & Han, 2012; Shi et al., 2017) are networks whose nodes and edges have multiple types. HIN has been widely used in many real-world network mining scenarios, e.g., node classification (Wang al., 2019) and recommendation (Zhao et al., 2017). For a heterogeneous network, a meta-path (Sun et al., 2011) 1) path defined it with multiple edge types. Intuitively, different meta-paths capture different semantic information from a heterogeneous network and it is important to find suitable meta- meta-paths for different applications on HINs. However, designing a meta-path on a HIN not a trivial task and requires much human effort and domain knowledge (Zhao et al., 2017; Yang et al., 2018). Thus, we propose to automatically discover informative meta-paths instead to manually design.
To solve the meta-path discovery problem under the supernet framework, we first construct supernet (see Figure 2(a)) and subgraph P E will be meta-path on HIN. While GTN (Yun al., 2019) introduces weights separately for each edge, our model f(w, P) uses tensor T to model P as a whole. The performance metric 2(.) and MM-) will depend on the downstream task. In our experiments node classification, we use cross-entropy loss for C(-) and macro Fl score for M(-).
Logical chain inference. A knowledge graph (KG) (Singhal, 2012; Wang et al., 2017) is multi- relational graph composed of entities (nodes) and relations (different types of edges). KG has found wide applications in many different areas, including question answering (Lukovnikov et al., 2017) and recommendation (Zhang et al., 2016). An important method to understand semantics KG logical chain inference, which aims to find underlying logic rules in KG. Specifically, a logical chain a path on knowledge graph with the following form x x >1 different relations in the knowledge graph. And
> .. -> y. where
x, U, ... entities and B1, B2..... By logical chain inference is to use a logical chain to approximate relation in KG. Obviously, different logical chains can have critical influence on KG incorrect logic rules will lead wrong facts.
5

---

Under review as a conference paper at ICLR 2021
Table Comparison with NAS methods in stand-alone setting on NAS-Bench-201.
CIFAR-10
CIFAR-100
ImageNet-16-120
Method
validation
test
validation
test
validation
test
ResNet (He et al., 2016)
90.83
93.97
70.42
70.86
44.53
43.63
Random
90.93+00.36
93.70++0.36
70.60+
70.65+1.38
42.92++2.00
42.96=2.15
REINFORCE
91.0910.377
93.85.10.37
71.6111.12
71.71111.09
45.05-11.02
1..24
BOHIB
90.82.10.53
93.61100.52
70.74.1..29
70.85.11.28
1..26.11.36
1..4
REA
91.1911.311
93.92.10.30
71.8111.12
71.84-10.99
45.15.10.89
1.03
TRACE TRACE (Best)
91.33.10.19
94.20.10.17
73.26.10.22
73.29-10.20
46.19110.16
91.53
94.37
73.49
73.51
46.37
46.34
Best in Bench-201
91.61
94.37
73.49
73.51
46.77
47.31
However, directly solving the inference problem will have a exponential complexity as have to enumerate all relations (Hamilton et al., 2018). Thus, we propose to model it as supernet search problem to reduce complexity.
Since logical chain has a chain structure, we construct supernet as in Figure 2(a). Denote our target relation as Br, the adjacency matrix of relation B, as A, and the one-hot vector corresponding to entity as Our learning model f(w, P)) now has no model parameter w, and the original bi-level problem is reduced a single-level one with the following performance measure M (f(w, P), D) =
EB, B. (2,a)) 1 D V (TI AB, AB, which counts the number of pairs (I, y) that has relation B, and is predicted by logical chain x +, B Ba
B,y in the KG D.
4 EXPERIMENTS
All experiments are implemented on PyTorch (Paszke et al., 2017) except for the logical chain inference, which is implemented TensorFlow (Abadi et al., 2016) following DRUM (Sadeghian et al., 2019). We have done all experiments on a single NVIDIA RTX 2080 Ti GPU.
4.1 BENCHMARK PERFORMANCE COMPARISON
Here, we compare our proposed method with the state-of-the-art methods on three different applications that can be seen as subgraph search problems, i.e., neural architecture design for image classification, logical chain inference from KG, and meta-path discovery HIN.
4.1.1 DESIGNING CONVOLUTIONAL NEURAL NETWORK (CNN) ARCHITECTURES
We first apply TRACE the architecture design problem CNN for image classification, which is currently the most famous application for supernet-based methods. We consider the following two different settings for our NAS experiments: (i). Stand-alone (Zoph & Le, 2017: Zoph al., 2017): train each architecture to converge to obtain separate w w" (P); (ii). Weight-sharing (Liu et al., 2018; Xie et al., 2018; Yao et al.. 2020): share the same parameter w across different architectures during searching, And for both stand-alone and weight-sharing experiments, we repeat our method for five times and report the ttd of test accuracy of searched architectures.
Stand-alone setting. To enable comparison under stand-alone setting, we use the dataset (Dong Yang. 2020) where the authors exhaustively trained all subgraphs in supernet and obtain complete record of each subgraph's 's accuracy on three different datasets: CIFAR-10, CIFAR- 100 and ImageNet- 16-120 (details in Appendix E. 1). use the stochastic formulation and compare method with (i) Random Search (Yu et al., 2020); (ii) REINFORCE (policy gradient) (Zoph Lc, 2017); (ii) BOHB (Falkner et al., 2018) and (iv) REA (regularized evolution) (Real et al., 2018). Results are in Table 2, and we
that method achieves better results than all existing stand-alone NAS methods and even finds the optimal architecture on CIFAR-10 10 and CIFAR-100 dataset.
Weight-sharing setting, We use the deterministic formulation, construct supernet follows (Liu et al., 2018), and evaluate all methods CIFAR-10 dataset (details are in Appendix E. These the

---

Under review as a conference paper at ICLR 2021
Table 3: Comparison with NAS methods in weight-sharing setting on CIFAR-IO.
Architecture
Test Error
Params (M)
Search Cost
Search
(%)
(GPU Days)
Method
DenseNet-BC (Huang et al., 2017)
3.46
25.6
manual
ENAS (Pham et al., 2018)
2.89
4.6
0.5
RL
Random (Yu et al., 2020)
2.85110.08
random
DARTS (Ist) (Liu et al., 2018)
3.00.10..14
3.3
1.5
gradient
DARTS (2nd)
2.76+00009
3,3
4
gradient
SNAS (Xic al., 2018)
2.85+00022
2.8
1.5
gradient
GDAS (Dong Yang. 2019)
2,93
3.4
0.21
gradient
BayesNAS (Zhou et al., 2019)
2.81400.04
0.2
gradient
ASNG-NAS (Akimoto et al., 2019)
2.83:1..11
2.9
0.11
natural gradient
NASP (Yao et al., 2020)
2.83
3.3
0.1
proximal algorithm
R-DARTS (Zela al., 2020)
2.95+0.21
1.6
gradient
PDARTS (Chen al., 2019)
2.50
gradient
PC-DARTS (Xu et al., 2020)
2.57:10.07
3.6
0.1
gradient
TRACE
2.78110.12
3.3
0.6
gradient
TRACE PC
2.48:10.07
3.6
0.8
gradient
Table Comparison with NAS methods in weight-sharing setting on ImageNet.
Architecture
Top-1 Error
Top-5 Error
Params
FLOPS
(%)
(%)
(M)
(M)
ShuffleNet (Ma et al., 2018)
25.1
5
591
DARTS (Liu al., 2018)
26.7
8.7
4.7
514
SNAS (Xie et al., 2018)
27.3
4.3
522
GDAS (Dong & Yang, 2019)
26.0
8.5
5.3
581
BayesNAS (Zhou et al., 2019)
26.5
8.9
3.9
PDARTS (Chen et al., 2019)
24.4
7.4
4.9
557
PC-DARTS (Xu et al., 2020)
25.1
5.3
586
TRACE TRACE
26.5
8.6
4.7
520
24.2
5.0
563
most popular setups for weight-sharing NAS. Results are in Table 3 and 4, we can see that TRACE achieves comparable performances with existing weight-sharing NAS methods.
4.1.2 LOGIC CHAIN INFERENCE FROM KNOWLEDGE GRAPH (KG)
For logical chain inference, we use the deterministic formulation and compare our method with the following methods: Neural L.P (Yang et al., 2017), DRUM (Sadeghian et al., 2019), and Grall. (Teru et al., 2020). Neural LP and DRUM are restricted to logical chain inference, while Grall. considers more complex graph structures. We also compare our method with random generated rules to better demonstrate the effectiveness of the proposed method. We do not compare our method with embedding- based methods, e.g. RotatE (Sun et al., 2019) as those methods all need embeddings for entities and cannot generalize found rules to unseen entities.
Following the setting of DRUM, we conduct experiments on three KG datasets: Family, UMLS and Kinship (details are in Appendix E.2), and report the best mean reciprocal rank (MRR), Hits at 1,3, 10 across 5 different runs. Results are Table 5, which demonstrates that our proposed method achieves better results than all existing methods. Besides, case studies in Section 4.2 further demonstrate that TRACE can find more accurate rules than others.
4.1.3 META-PAPE PATH DISCOVERY HETEROGENEOUS INFORMATION NETWORK (HIN)
Finally, we apply TRACE to meta-path path discovery problem on HINs. Following existing works (Wang et al., 2019; Yun al., 2019), on three benchmark datasets: DBLP, ACM and IMDB (details are in Appendix E.3) and compare methods with the 1) baselines in GTN (Yun al., 2019), i.e., DeepWalk (Bryan al., 2014),
the deterministic formulation and conduct experiments
7

---

Under review as a conference paper at ICLR 2021
Table 5: Experiment results on logical chain inference.
Dataset
Family
UMLS
Kinship
Hits @
Hits @
Hits
MRR
10
3
MRR
10
MRR
10
3
Neural L.P
0.88
0.98
0.95
0.80
0.72
0.93
0.84
0.58
0.55
0.87
0.63
0.41
DRUM
0.95
0.99
0.98
0.91
0.80
0.98
0.94
0.66
0.59
0,91
0.68
0.44
GralL
0.87
0.96
0.95
0.79
0.73
0.94
0.86
0.55
0.57
0.89
0.65
0.45
Random
0.45
0.48
0.43
0.39
0.33
0.35
0.31
0.25
0.22
0.25
0.19
0.14
TRACE
0.92
0.99
0.98
0.92
0.81
0.98
0.95
0.67
0.61
0.91
0.69
0.45
Table 6: Evaluation results on the node classification task (FI score).
Dataset
DeepWalk
metapath2vee
GCN
GAT
HAN
GTN
Random
TRACE
DBLP
63.18
85.53
87.30
93.71
92.83
93.98
91.62
94,42
ACM
67.42
87.61
91.60
92.33
90.96
91.89
90.28
92.62
IMDB
32.08
35.21
56.89
58.14
56.77
58.92
57.12
61.31
metapath2vec (Dong al., 2017), GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2018), HAN (Wang et al., 2019) and 2) random generated meta-paths. Results on different datasets are in Table which demonstrate that TRACE performs better than other methods on different HINSs
4.2 CASE STUDY
Table 7: An example of top 3 rules obtained by each method on Family dataset.
To further investigate the performance of TRACE, we list the top rules found by TRACE and other methods in Ta- ble 7. This result demonstrates that our method can find more accurate logic rules than other baselines, which contributes to the superior performance of our method. We also give the architectures and meta-paths found by TRACE in Appendix F.
Son(C, A) +- brother(C. B), son(B. A)
Neural-LP
son( B, Aj +- brother(B. A)
son(C, A) son{ B), mothen B, A)
soníC, AJ <- nephew(
brother (B. A)
DRUM
son(C. A) <- brother(C. B), son(B, A)
son(C, A) <- brother(C, B), daughter(B, A)
son(C, A) son(C, B), wife(B, son(C, A) <- brother(C, B), son(B, A)
TRACE
son(C, A) f- nephew(C, B), brother(B, A)
4.3
ABLATION STUDY
4.3.1
IMPACT OF ENCODING APPROACH
We compare TRACE with the following encoding methods supernet: (i) DARTS, which introduces continuous parameters for each edge separately; (ii) RNN, which uses a RNN to compute the weights for each edge; (iii) CP decomposition, which generalizes DARTS higher rank; (iv) TRACE(Ful)),
which does not adopt Proposition in Algorithm 1. Results on DAS-Bench-201 using CIFAR-100 are shown in Figure ((a), and we can see that DARTS performs worse than other methods (CP and TRACE) due to insufficient expressive power. And TRACE achieves better results than CP by being topological aware. also shows that our simplified encoding scheme does not harm the final performance, as verified in Proposition 1.
22
TAY
DATTS
8.
(a) Encoding methods.
(b) TN ranks.
(c) Re-paramettizzation.
Figure 3: Ablation studies TAS-Bench-200 CIFAR-100 is used
8

---

Under review as a conference paper at ICLR 2021
4.3.2 IMPACT OF RANK OF TENSOR NETWORK
We also investigate the impact R which ranks tensor network (TN) on supernets. For simplicity, we restrict Rn to be equal for all nodes n E (S) and compare the performance of different ranks with previous that while the rank can influence the final performance, it is easy to set rank properly for TRACE to beat other methods. We also adopt R. 2 for all other experiments.
tiite-of-the-eeee art REA (see Table in Figure 3(b). Results demonstrate
4.3.3 OPTIMIZATION ALGORITHMS
Finally, we compare TRACE with proximal algorithm (Parikh & Boyd, 2014), which is a popular and general algorithm for constrained optimization. Specifically, proximal algorithm is used to solve (I) with the constraint Σ; T___ 1 without Proposition We solve the proximal step iteratively and numerically since there no closed- form solutions. The comparison is in Figure 3(c), and we can see that TRACE beats proximal algorithm by large margin, which demonstrates that the re-parameterized by Proposition is useful for optimization.
CONCLUSION
In this paper, we generalize supernet from neural architecture search (NAS) other machine learning tasks. To expressively model the supernet, introduce tensor formulation the supernet and represent by tensor network (tensorizing supernets). We further propose an efficient gradient- algorithm to solve the supernet search problem. Empirical results across various applications demonstrate that our approach has superior performance on these machine learning tasks.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: system for large-scale machine learning. In OSDI, 2016.
Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICML, 2019.
Cichocki andrzej.. Namgil. Lee, Ivan. Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part I low-rank tensor decompositions. Foundations and Trends in Machine Learning, 2016.
Cichocki andrzej.. Anh-Huy, Phan, Qibin. Zhao, Namgil. Lee, Ivan. Oseledets, Masashi. Sugiyama, and Danilo Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives. Foundations and Trends in Machine Learning, 2017.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. In ICLR, 2016.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. In ICML, 2018.
Rasmus Bro. PARAFAC tutorial and applications. Chemometrics and Intelligent Laboratory Systems, 1997.
Perozzi Bryan, Rami Al-Rfou, and Steven Skiena. representations. In KDD, 2014.
Deepwalk: Online learning of social
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In ICCV, October 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep
bidirectional transformers for language understanding. In NAACL, 2018.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. CVPR, June 2019.
Xuanyi Dong and Yi Yang. NAS-Bench-2011 Extending the scope of reproducible neural architecture search. In ICLR, 2020.
Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD, 2017.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In ICML, 2018.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, 2019.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2017.
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 ECCV, pp. 544-560. Springer, 2020.
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec, Embedding logical queries knowledge graphs. In NIPS, 2018.
10

---

Under review as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Gao Huang, Zhuang Liu, and Kilian Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Review, 2009.
Alex Krizhevsky, Ila Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Chao and Zhun Sun. Evolutionary topology search for tensor network decomposition. In ICML, 2020.
Wei Li, Shaogang Gong, and Xiatian Zhu. Neural graph embedding for neural architecture search. In AAAI, 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In ICLR, 2018
Yu Liu, Quanming Yao, and Yong Li. Generalizing tensor decomposition for n-ary relational knowledge bases. In WWW, 2020.
Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. Neural network- based question answering over knowledge graphs on word and character level. In WWW, 2017.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. ShuffleNet V2: Practical guidelines for efficient cnn architecture design. In ECCV, 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. NIPS, 2013.
Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing neural networks. In NIPS, 2015.
Ivan V. Oseledets. Tensor-train decomposition. SIAM Journal Scientific Computing, 2011.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3): 127-239, 2014.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito,o, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS Workshop, 2017.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In ICML, 2018.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In NeurIPS, 2019.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, 2018.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-to-end differentiable rule mining on knowledge graphs. In NIPS, 2019.
Chaun Shi, Yitong Li. Jiawei Zhang, Yizhou Sun, and Philip S. Yu. A survey of heterogencous information network analysis. IEEE Transactions on Knowledge and Data Engineering, 2017.
Amit Singhal. Introducing the knowledge graph: things, not strings. Official google blog, 5, 2012.

---

Under review as a conference paper at ICLR 2021
Steven Skiena. Implementing discrete mathematics: combinatorics and graph theory with mathematica. The Mathematical Gazette, 1992.
Yizhou Sun and Jiawei Han. Mining heterogeneous information networks: principles and methodologies. Synthesis Lectures on Data Mining and Knowledge Discovery, 2012.
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. PathSim: Meta path- path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, 2011.
Zhiqing Sun, Zhi-Hong Deng, Vian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Komal K. Teru, Etienne Denis, and William L.. Hamilton. Inductive relation prediction by subgraph reasoning. ICML,, 2020.
Ledyard Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 1966.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Guojia Wan, Bo Du, Shirui Pan, and Gholamreza Haffari. Reinforcement learning based meta-path discovery in large-scale heterogeneous information networks. In AAAI, 2020.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering, 2017.
Wenqi Wang, Yifan Sun, Brian Eriksson, Wenlin Wang, and Vaneet Aggarwal. Wide compression: Tensor ring nets. CVPR, June 2018.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip Yu. Heterogeneous graph attention network. In WWW, 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR, 2018.
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. In ICLR, 2020.
Carl Yang, Mengxiong Liu, Frank He, Xikun Zhang. Jian Peng, and Jiawei Han. Similarity modeling on heterogeneous networks via automatic path discovery. ECML-PKDD, 2018.
Fan Yang, Zhilin Yang. and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NIPS, 2017.
Quanming Yao, Ju Xu, Wei-Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In AAAI, 2020.
Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. In ICML, 2020.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020.
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. In NIPS, 2019.
Arber Zela, Thomas Elsken. Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei- Wei-Ying Ma. Collaborative knowledge base embedding for recommender systems. In KDD, 2016.
12

---

Under review as a conference paper at ICLR 2021
Huan Zhao, Quanming Yao, Jianda Li, Yangqiu Song, and Dik Lun Lee. Meta-grapa based recommendation fusion over heterogeneous information networks. In KDD, 2017.
Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Cichocki andrzej. Tensor Ring Decomposition. arXiv e-prints, pp.
June 2016.
Hongpeng Zhou, Minghao Yang. Jun Wang. and Wei Pan. BayesNAS: Bayesian approach for neural architecture search. In ICML, 2019.
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In ICCV, 2017.
13

---

Under review as a conference paper at ICLR 2021
A COMPLETE ALGORITHMS OF OPTIMIZATION ON TENSORIZED SUPERNET
Here, we give detailed description for algorithm under deterministic and stochastic formulation Algorithm 3 and 4, respectively. In our experiments, we use the stochastic formulation for NAS under standalone setting, and deterministic formulation for others.
Algorithm 3 TRACE (deterministic formulation with weight-sharing
Input: Training set Du. Validation set vall
1: Tensorize the supernet T with Algorithm 1;
2: Re-parameterize T to T using (3);
3: while not converged do
4: Update model parameters w(3) by gradient descending v (S(w, B), Dr))
5: Update supernet parameters by gradient ascending JJ
6: end while
7: Obtain P = from the final T by setting i_ = arg max, T
8: Obtain w" w""P" (P*) = arg min f (f P"), D.)) by retraining f(w, PT)):
9: return w" ,
Algorithm 4 TRACE (stochastic formulation)
Input: Training Dr, Validation set Daal
1: Tensorize the supernet T with Algorithm 1;
2: Re-parameterize T to T using (3);
3: while not converged do
4: Sample subgraph P from the probability distribution given by T
5: Solve w (P) = arg min L. (f(w,, P), Dr.)
6: Update supernet parameters by gradient ascending V/sTa
7: Save the best w0 (P), P so far
8: end while
9: return best 20 (P), P in Step 7;
B COMPARISON OF PARAMETERS FOR DIFFERENT METHODS
Here, we compare the number of parameters and computational cost (FLOPs) different methods for logic rule inference. We use as the length of logical chains, d as the dimension of embeddings, r as the rank of tensor networks and as the number of all relations. Results are Table 8. Since and is often significantly smaller than and d (typical values are 3, 2, d 128 and e Rs 20 30), TRACE has comparable number of parameters and computational cost with existing methods.
Table Comparison of number of parameters for different methods on KG.
Method
# of parameters
FLOPs
Neural LP
O(d")
O(nd
DRUM
O(rd
O(nrd)
GralL
(
Oledn)
TRACE
O(u)ee)
O(nr2e)
For comparison on HIN, we use n as the length of meta- peeta,patss, d as the dimension of embeddings, and as the rank of tensor networks. Results in Table 9. Note that is often relatively small compared with d (typical values are r and = 128), thus TRACE has the similar number of parameters and computational cost with existing methods.
14

---

Under review as a conference paper at ICLR 2021
Table 9: Comparison of number of parameters for different methods on HIN.
Method
DeepWalk ((nd)
metapath2vec
GCNIGAT/HAN
GTN
TRACE
# of parameters
((nd)
O(nd))
O(((r+dD)) O(nr)
0(n(r++d') O(nr²)
FLOPs
((n)
(nn)
O(n)
Table 10: Comparison on number of parameters for different encoding methods.
Method
Brief description
PDARTS PC-DARTS DropNAS
Progressively reduce number of operations and increase network depth Use -oonecccoonntioonn in channels to reduce memory cost Drop out operations avoid the Matthew effect
C REVIEW ON EXISTING METHODS THAT CAN BE COMBINED WITH TRACE
D PROOFS
D.1 PROPOSITION
Proof. Denote those nodes in supernet whose degree is greater than one (connected by more than one edges) (S). Thus, A(S) (S)) denotes all degree-1 nodes supernet. Suppose one node (1) is only connected by edge I, while N2 is not, 3 then we can rewrite T,
EAIeEN(s) II 05 5x,0))678220) as follows:
T
T=
Σ
II
or
PM (Ny (2) (e
(S)
T
Σ
Σ
II
a
()))EN Pn min (S)
T
Σ
Σ
I
Σ
()) [=1 Fm,
Σ
Σ
á
(()
TN1(0
Σ
(0)
(8)
where similar process is done for all edges. Thus, only nodes whose degree is greater than 1 is actually needed for index contraction. And for n E NN(S) (S)(S, we can simply set Rn without loss of expressive power.
'If N₁ (f) is only connected by edge (degree is 1), (t) cannot be only connected by edge unless the supernet has only edge t connecting two nodes (1()), Na(t), which is trivial case.
15

---

Under review as a conference paper at ICLR 2021
D.2 PROPOSITION 2
Proof. Following (3), we can have:
Rs
I
Th. IIE Rn
Σ
II
Σ, copsirts))
Tn. (S) t=1
Ra
T
explatm
Σ
II
HnE Bn
t=1
Ra
17
(IEA Rn E.)
II
R₂ 1.
ThEA' Rn nEN'(()
E EXPERIMENT DETAILS
E. NEURAL ARCHITECTURE SEARCH (NAS)
Stand-alone setting The supernet used in NAS-Bench-201 has 3 nodes, and each pair of nodes is connected by a directed edge, which gives 6 edges in total. And for each edge, we have different operations ("choices"), ) zero, skip connect, 1 convolution, 3 convolution and 3 x 3 average pooling. And the details of datasets used in NAS-Bench- are in Table 11.
Table 11: Dataset statistics of three image classification dataset for NAS.
Image size
Classes
Training
# Validation
# Test
CIFAR-I0
32x32
10
25K
25K
5K
CIFAR-100
32x32
100
50K
5K
5K
ImageNet-16-120
16x 16
120
151.7K
3K
3K
Weight-sharing setting Our construction of supernet follows (Liu et al., 2018). The supernet has nodes, where the first two nodes are the output from previous two cells, respectively, and the last node performs depthwise concatenation to the output of the rest four nodes. Thus, the supernet has 8 edges with multiple choices (operations), and for each edge, we consider different operations: zero, skip connect, 3 x 3 and 5 x 5 separable convolution, 3 x 3 and 5 x 5 dilated separable convolution, 3 x max pooling and 3 x average pooling. We evaluate all seight-sharing methods on CIFAR-10 dataset and the dataset division is the same in Table 11.
E.2 LOGIC CHAIN INFERENCE
In our experiments, we follow the setting in DRUM (Sadeghian et al., 2019) and set the max length of rules 7 to be 3 for all datasets. And set the rank L to be 4 in DRUM based on best validation performances. The details of KG datasets used in experiments are in Table 12.
Table 12: Dataset statistics for three KG dataset.
# Triplets
Relations
Entities
Family
28356
12
3007
UMLS
5960
46
135
Kinship
9587
104
E.3 META-PATH DISCOVERY
The details of HIN datasets used in experiments are in Table 13.
16

---

Under review as a conference paper at ICLR 2021
Table 13: Dataset statistics for three heterogencous information network dataset.
Nodes
# Edges
# Edge types
# Features
# Training
# Validation
Test
DBLP
18405
67946
4
334
800
400
2857
ACM
8994
25922
1902
600
300
2125
IMDB
12772
37288
1256
300
300
2339
F
MORE EXPERIMENT RESULTS
CORRELATION ANALYSIS
Indeed, the correlation good criterion to show the rationality of one-shot architecture search methods (Bender et al., 2018; Liu et al.. 2018; Yu et al., 2020; Guo et al., 2020). However, it is only sufficient not necessary condition. Specifically, the goal of tensor 7 here capture good subgraph in the whole supernet, thus we expect the possibilities of P; will concentrate on some top subgraphs, which is shown below Figure
Pituaiity
Prtuuiity
(a) CIFAR-10
(b) CIFAR-100
(c) ImageNet-16-
Figure 4: Correlation of and ground -ruut accuracy on MAS-Bench-201 for different datasets.
F.2 CASE STUDIES
skip, connect
(k-1)
nor conv 3x3
nor conv
(k)
nor nor_conv
_x3 3x3
nor canv. 3x3
nor con.covvv
(a) CIFAR-10
skip connect
(k-1)
nor conv 3x3
nor conv_333
ck)
nor.comm 3x3
nor cor_conv.c 3x3
3x3
(b) CIFAR-100
skip_connee connect
(_(k-)
conv
conv 3x3
[_)k)
3x3
1x1
(c) ImageNet-16-12
Figure 5: Architectures found by TRACE
for different datasets.
17

---

Under review as a conference paper at ICLR 2021
sep
dil conv 5x5
(_(k22
skip connect
sep_conv__ 3x3
[_(k)
sep_convv _333
Skip_
C (k(k-]
sep_conv 3x3
sep_conv conv 3x3
(a) Normal Cell
avg avg_pool 3x3
avg poo_pool___0 3x3
skip connectt
C (k-)
avg_pool_ 3x3
skip connect
C. (K)
skip connect avg pool 3x3, skip_ccoeepp connect
C (k-1)
(b) Reduction Cell
Figure 6: Architectures found by TRACE on weight-sharing setting.
Table 14: Meta- paths found by GTN and TRACE on different HIN.
Top-3 meta-paths
Dataset
predefined meta-path
GTN
TRACE
DBLP
APCPA, APA
CPCPA, APCPA, CP APAP, APA. SPAP
CPCA, APCPA, APA PSP, APAP, PAP
ACM
PAP, PSP
IMDB
MAM, MDM
DM, AM, MDM
MDM, MDMAM, MAM
F.3 RUNNING PLOTS
UNLS
0.5
1714
01344
035
07
034
00141
20141
054
016
082
Teu 3000
Family
(b) UMLS
(c) Kinship
Figure 7: Validation MRR during training three KG datasets.
18

---

Under review as a conference paper at ICLR 2021
02
(a) DBLP
(b) ACM
(c) IMDB
Figure 8: Validation macro score during training on three HIN datasets.
F.4
ABLATION STUDIES
LM0
TUCCOTUD
T2A
(a) Encoding methods
(b) TN ranks
(c) Algorithms
Figure 9: Ablation studies on NAS- AAS-Bench-201, CIFAR-10 10 is used
(MCC
CATSS
0
210
750
10:00
1203
1506
1750
2000
700
12:00
1250
1990
2906
(a) Encoding methods
(b) TN ranks
(c) Algorithms
Figure 10: Ablation studies on AAS-Bench-20) ImageNet-16- used
19

---

Under review as a conference paper at ICLR 2021
G
ILLUSTRATION OF TENSORIZATION PROCESS FOR SUPERNETS
Node 1
Edge
Edge 2
Edge 3
Edge 4
Node
Node 3
Node
Node 5
(a) A supernet example
Node 1
a
Common Node 3
Common Node 3
Node 2
Common Node
Common Node
Node
a
a
(b) Introduce a' for each edge and connect them nodes the supernet (step 1).
a²
Common Node
Common Node
Common Node 3
Common Node 4
a
a
a
(C) Remove isolated nodes (step 2).
i1
13
1'3
i4
a
Q
a
is
(d) Final tensor network (step 3).
Figure 11: A bysteb illustration of supernet encoding process (Algorithm 1).
20


Reviews:
[{"review_id": "lYqSf9sLnA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The idea of employing a tensor method to generalize NAS seems to be interesting. However, this paper suffers from a few problems: \n1. The presentation of this paper requires improvement. There are some confusion:\n\n- This paper has not clearly described the difference with previous works. Specifically, although this paper claims to give a unified method, it is difficult to distinguish what have been unified. And in the 10-th line of the Abstract, what is the concrete description of \"the above problems\"?\n- In Figure 2,  whether $\\alpha^{(1)}$ is the $\\theta^{1}$? If yes, in Figure 2(b), it would be better to use $\\theta^1$ to replace $\\alpha^{(1)}$ directly. And in the caption of Figure 2, what does \"$N_1(t)/N_2(t)$\" mean, a division or \"$N_1(t)$ or $ N_2(t)$\"?\n- In Algorithm 1, what is the meaning of $R_{N_1(t)}$? And how to choose the value of $R_{N_1(t)}$?\n- In Section **PROPOSED METHOD**, how to transform a supernet to a tensor graph?  It is highly suggested that adding more details about the transforming process.\n\n2. The experimental results are not good enough. For example,  in results on Cifar10, there are a number of competitive methods which obtained better results of the proposed one. \n\n| Model                                           | Err.      | #Params | Cost(GPU days) |\n| ----------------------------------------------- | --------- | ------- | -------------- |\n| TRACE(This paper)                               | 2.78±0.12 | 3.3     | 0.6            |\n| P-DARTS + cutout(Xin Chen et. al.. ICCV 2019.)  | 2.5       | 3.4     | 0.3            |\n| PC-DARTS + cutout(Yuhui Xu et. al.. ICLR 2020.) | 2.57±0.07 | 3.6     | 0.1            |\n\n3. The writing requires significant proofreading. There are plenty of grammar errors：\n\n- In the 2-nd line of Section 2.2, \"Tensor methods have found wide applications\" -> \"... have been  found in...\"\n- In the 5-th line of Section 3.1, \"Note that a subnet P can be distinguished by its choices on each edge, we propose....\" -> \"... each edge, and we propose....\"\n- In page 2,  \"it also emerge in\"\n- etc..", "extra_scores": {}, "extra_text": {}}, {"review_id": "eB5aHlKM-09", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tries to use tensorize the supernet. The supernet itself is a graph and NAS aims to search the operations on the edges. The 'TRACE' finds that path-discovery appears in a number of tasks and NAS is one of them. \n\nThis is an interesting topic and the experiments are conducted on vision/logic chain/node classification tasks. \n\n+) This paper is clear and easy to follow.\n\n+) The topic is interesting. It is charming to design a universal method that could solve a number of problems.\n\nHowever, there are still some concerns:\n\n-) Is the title appropriate? The gradient-based NAS finds an optimal path in the global search space. However, for other tasks mentioned in this paper, is 'architecture search' appropriate to describe them? Could it be named as 'path search' or some others? Are there any other works support the 'architecture search' in other tasks?\n\n-) The notations are not clear. The $\\mathcal{J}$, the $r_{N_1(t)}$, the $\\theta$ should all be described. However, I could not find them either in the 'annotation' paragraph or the first-mentioned sentences.\n\n-) Move notations to the beginning of section 3.\n\n-) What is $R_{N_1(t)}$ in Alg. 1? The $R$ has not been explained. However, I think this is important for the reader to understand the algorithm.\n\n-) The results on CIFAR-10 aim to show that 'TRACE' could accelerate searching without loss of accuracy? What will happen if searching for longer epochs? According to 'Motivated by the success of previous methods (e.g., DARTS, SNAS and ENAS), our TN should include their encoding methods as special cases.', what is the number of parameters used for modeling the architectures? \n\n-) ' their decomposition method does not consider the topological structure of supernets,'. For the cell-based NAS in Table. 1. Why the topological structure has not been considered?\n\n-) In Fig. 2, it's better to add a toy example based on Eq. 4 and add more explanations.\n\n-) Please report the cost in Table 4, 5. For example, the params/search cost/flops in Table 3.\n\n-) (minor) Lack of experiments on large-scale datasets, like ImageNet.\n\n-) The HIN task searches for the rank-1 CP (Table 1), and the CV task also searches for the rank-1 solution. So this HIN task is just adopting the standard solution on another dataset? Are there any other differences?\n\n-) What if the rank goes higher in Figure 3 (b)?\n\nBased on the quality of this paper, I don't think this paper creates something new. In my opinion, this paper describes the solutions from a novel/universal perspective. Some of the existing methods are special cases. So I selected 5 as the initial score. It would be nice if the authors emphasize the unique contribution more clear and address the concerns. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "UeExtMBTFGb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a new and general formulation for supernet, which encodes supernet with tensor network(TN). Based on TN, the topology of supernet can be encoded. Besides, this paper proposes a corresponding algorithm to solve the search problem. \n\nReasons for score:\n\nOverall, I vote for accepting marginally. My major concern is about the clarity of the paper and some additional experiments (see cons below). Hopefully the authors can address my concern in the rebuttal period.\n\nPros:\n\n1.In this paper, the authors introduce a new and general formulation for supernet. Due to its generalization, supernet-based NAS methods with it can be applied to many deep learning tasks. In addition, this formulation can encode the topology of supernet, which benefits the network search.\n\n2.Based on this formulation, this paper proposes a corresponding search algorithm. This algorithm can solve supernet search problem for both deterministic formulation and stochastic formulation. \n\n3.Experiments are well thought out and highlight the key advantages of the method over other NAS methods. \n\nCons:\n1.For recent NAS methods, they all validate their performances on ImageNet. In the experiments, there is only a experiment on ImageNet-16-120. Could you provide an experiment in weight-sharing setting on ImageNet dataset?\n\n2.For Table 3, it is a must to compare with more NAS methods, such as PDARTS and DropNAS. In this way, the effective of the proposed method can be validated fully.\n\n3.In section 3.2, $R^{n}$ in $\\mathcal{T}_{i-}$ is used without any definition. Are there some hints for it? If not, it would lead to some misunderstandings.\n\nQuestions during rebuttal period:\n\nPlease address and clarify the cons above\n\nSome typos:\n\nIntroduction, Notations, last line: a vector $\\textbf{o}_{i} \\in \\mathbb{R}^{n} $ -> $\\textbf{o} \\in \\mathbb{R}^{n} $", "extra_scores": {}, "extra_text": {}}, {"review_id": "4xG41W6lWj2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n+ This paper generalizes the supernet search problem on a broader horizon. Specifically, some of the current NAS methods use supernet to co-training different neural architectures for further architecture search. This paper does not just consider supernet as a tool for NAS, but also consider supernet as a graphical model and extend supernet to several general tasks in the form of graph data. (+)\n\n+ This paper unifies the above tasks by a tensor formulation and encodes the topology inside the supernet by a tensor network. Different from NAS, the topological structure of the supernet is utilized in this paper. (+)\n\n+ The paper further proposes an efficient algorithm that admits both stochastic and deterministic objectives to solve the search problem. (+)\n\n+ A wide range of machine learning tasks besides computer vision are used to evaluate the proposed method's effectiveness, such as logic chain inference on knowledge graphs and meta-path discovery for HIN. (+)\n\n- After reading the related work section, we notice that the authors have known some methods used in the NAS problem, but they are not aware of the current NAS's ineffectiveness problem. Specifically, the NAS's effectiveness is open to question, with its architecture rating is often inaccurate, especially in DARTS and some single-path one-shot NAS method. Two ICLR 2020 papers suggest that many NAS methods are not better than random architecture search. This paper borrows the concept from NAS but ignore the ineffectiveness/inefficiency of NAS. Therefore, the proposed method's effectiveness in this paper is questionable unless the authors provide an architecture rating analysis. (-)\n\nIn the context of chaotic phenomena in NAS nowadays, analyzing the architecture rating problem is of most importance. As there are many NAS papers published every year and their ineffectiveness may still be not widely recognized by the reviewers and the public, merely borrowing NAS methods to other domains (e.g., in this paper) is dangerous. This may cause more chaos in the new field. I think a NAS method's effectiveness should be sufficiently investigated before NAS can be generalized to a new domain.\n\n\n- As defined, Ti in [0, 1] represents how \"\"good\"\" P can be. Then, there must be a connection between T and M(f(w, P), D), which represents the performance of learning model f(w, P) on dataset D? My understanding is that the authors can use the CORRELATION BETWEEN EDGE IMPORTANCE AND MODEL ACCURACY in the following paper [reference] to measure the connection between T and M. In other words, as is formulated by the authors, \"Ti ∈ [0, 1] represent how \"good\" P can be,\" can the authors provide pieces of evidence showing the proposed method can actually have this effect? This is exactly related to the inaccurate architecture rating problem in NAS. Only can the authors answer this question will I be able to consider an acceptance of this paper. (-)\n\n\n[reference]\n@inproceedings{\nanonymous2021dots,\ntitle={{\\{}DOTS{\\}}: Decoupling Operation and Topology in Differentiable Architecture Search},\nauthor={Anonymous},\nbooktitle={Submitted to International Conference on Learning Representations},\nyear={2021},\nurl={https://openreview.net/forum?id=y6IlNbrKcwG},\nnote={under review}\n}\n\n\n+ The way to use routine (Algorithm 1) to tensorize the supernet is reasonable and correct. （+）\n\n\n- This paper is very difficult to understand. I must read very carefully (especially for the subscript notation) twice until I can understand the paper. I think the main idea of this paper is simple. But the authors use a complicated way to describe the method, which makes the article unreadable and thus mysterious. (-)\n\nOverall, this paper proposes a method that generalizes the idea from NAS to general tasks. However, it is open to question whether this generalization is appropriate as the supernet-based NAS's effectiveness is an active research topic.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new and general formulation for supernet, which encodes supernet with tensor network(TN). The idea is interesting and motivated.  However, the paper is well presented and the clarify needs to be further improved.  The effectiveness of algorithm is not well justified and experimental results are less convincing even after additional results provided in the revision. Most importantly, it is not clear that the 'TENSORIZING' method can solve the current NAS's ineffectiveness problem.  It is confirmed that the reference to ICLR-2021 paper is not used for the decision of paper. 
Decision: Reject