AutoGEL: An Automated Graph Neural Network with Explicit Link Information
Authors: Zhili Wang
Shimin Di
Lei Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
automated graph neural network
link prediction

Abstract: Recently, Graph Neural Networks (GNNs) have gained popularity in a variety of real-world scenarios. Despite the great success, the architecture design of GNNs heavily relies on manual labor. Thus, automated graph neural network (AutoGNN) has attracted interest and attention from the research community, which makes significant performance improvements in recent years. However, existing AutoGNN works mainly adopt an implicit way to model and leverage the link information in the graphs, which is not well regularized to the link prediction task on graphs, and limits the performance of AutoGNN for other graph tasks. In this paper, we present a novel AutoGNN work that explicitly models the link information, abbreviated to AutoGEL. In such a way, AutoGEL can handle the link prediction task and improve the performance of AutoGNNs on the node classification and graph classification task. Moreover, AutoGEL proposes a novel search space containing various design dimensions at both intra-layer and inter-layer designs and adopts a more robust differentiable search algorithm to further improve efficiency and effectiveness. Experimental results on benchmark data sets demonstrate the superiority of AutoGEL on several tasks.

AutoGEL: An Automated Graph Neural Network with Explicit Link Information
Zhili WANG, Shimin DI", Lei CHEN Department of Computer Science and Engineering The Hong Kong University of Science and Technology {zwangeo, sdiaa, (eicche))&conneeeee .ut hk
Abstract
Recently, Graph Neural Networks (GNNs) have gained popularity in variety of real-world scenarios. Despite the great success, the architecture design GNNs heavily relies on manual labor. Thus, automated graph neural network (AutoGNN) has attracted interest and attention from the research community, which makes significant performance improvements in recent years. However, existing AutoGNN works mainly adopt an implicit way to model and leverage the link information in the graphs, which is not well regularized to the link prediction task on graphs, and limits the performance of AutoGNN for other graph tasks. In this paper, we present a novel AutoGNN work that explicitly models the link information, abbreviated to AutoGEL. In such a way, AutoGEL can handle the link prediction task and improve the performance of AutoGNNs on the node classification and graph classification task. Specifically, AutoGEL proposes a novel search space containing various design dimensions at both intra-layer and inter-layer designs and adopts more robust differentiable search algorithm to further improve efficiency and effectiveness. Experimental results on benchmark data sets demonstrate the superiority of AutoGEL. on several tasks.
1 Introduction
As one of ubiquitous data structures, graph G(E, V) contains the node-set V = {21,-- c..) and edge-set E ={e(v,, f 0;) Uy, E;
E VJ. which can represent a lot of real-world data sets, such as social networks [Bu et al. 2018 physical systems (Sanchez-Gonzalez et al. 2018]) protein-protein
interaction networks Yuee et al. 2020]. In recent years, Graph Neural Networks (GNNs) have been introduced for various graph tasks and achieve unprecedented success, such as node classification
Kipf and Welling 2016a| Hamilton et al. 2017 link prediction /ashishhh et al., 2019 Li et al.
2020), and graph classification [Niepert et al. 2016 Zhang al. 2018]. Generally, GNNs encode G(V, E) into the d-dimensional vector space (e.g.. V E RIVixd that preserves similarity in the original graph. Despite the great success, those GNNs are restricted to specific instances within GNN design space YYou et al. 2020 Different graph tasks usually require different GNN architectures [Gimmer et al. 2017]. For example, compared with the node classification task, GNNs for graph classification introduces an extra readout phase to obtain graph embeddings. However, architecture design for these GNNs remains a challenging problem due to the diversity of graph data sets. Given a graph task, GNN architecture performs well on one data set does not necessarily imply that it is also suitable for other data sets (You et al. 2020
Some pioneer works have been proposed to alleviate the above issue in GNN models. They introduce Neural Architecture Search (NAS) [Elsken al. 2019 approaches to automatically design suitable
"Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

GNN architecture for the given data set (i.e., AutoGNN) Zhou et al. 2019 Gao et al. 2020 Jiang and Balaprakash 2020, Zhao et al. 202T. Architectures identified by these AutoGNNs rival or surpass the best handcrafted GNN models, demonstrating the potential of AutoGNN towards better GNN architecture design. Unfortunately, the existing AutoGNNs are mainly designed for the node classification and graph classification task. Their designs do not include edge embeddings, ie.. modeling and organizing link information in an implicit way. First, it is difficult for existing AutoGNNs to handle another important graph task the edge-level, link prediction (LP) task. Second, lack of edge embedding makes them inexpressive to leverage the complex link information, such direction information of edges and different edge types in multi-relationa graphs. Especially, various edge types could impose different influence for encoding nodes into embeddings, which can further improve the model performance the nove-level and graph-level tasks. Therefore, new AutoGNN is desired to model link information explicitly on various data sets.
To bridge the aforementioned research gap, we propose AutoGEI., novel AutoGNN framework with Explicit Link information, which can handle the LP task and improve performance of AutoGNNs on other graph tasks. Specifically, AutoGEL explicitly learns the edge embedding in the message passing framework to model the complex link information, and introduces the several novel design dimensions into the GNN search space, enabling a more powerful GNN to be searched for any given graph data set. Moreover, AutoGEL adopts robust differentiable search algorithm to guarantee the effectiveness of searched architectures and control the computational footprint. We summarize the contributions this work as follows:
The design of existing AutoGNNs follows implicit way to leverage and organize the link information, which cannot handle the LP task and limits the performance of AutoGNNs on other graph tasks. In this paper, present novel method called AutoGEL to solve these issues through explicitly modeling the link information in the graphs.
AutoGEL introduces several novel design dimensions into the GNN search space at both the intra-layer and inter-layer designs, so as to improve the task performance. Moreover, motivated by one robust NAS algorithm SNAS, AutoGEL upgrades the search algorithm adopted in existing AutoGNNs to further guarantee the effectiveness of final derived GNN.
The experimental results demonstrate that AutoGEL can achieve better performance than manually designed models in the LP task. Furthermore, AutoGEL shows excellent competitiveness with other AutoGNN works on the node and graph classification tasks.
2
Related Work
2.1 General Message Passing Framework
The majority of GNNs follow the neighborhood aggregation schema [Gilmer et al. 2017). i.e., the Message Passing Neural Network (MPNN), which formulated as:
m k+1 AGG hy eh.) E N(v))), h ACT. m m +++)), (1)
: ý- R((h/lu G)),
(2)
where i denotes k-th layer, (Dv) denotes of neighboring nodes of h h denotes hidden embeddings for and respectively, et denotes features for edge e(v, u) (optional), m denotes the intermediate embeddings gathered from neighborhood N(v), M2 denotes the message function, AGG, denotes the neighborhood aggregation function, COM, denotes the combination function between intermediate embeddings and embeddings of node v itself from the last layer, ACT,, denotes activation function. Such message passing phase in [I repeats for L times (i.c., lo E {1, LL).. For graph-level tasks, it further follows the readout phase in where information from the entire graph G is aggregated through readout function R(.).
2.2
Automated Graph Neural Networks (AutoGNN)
In recent years, AutoGNN has emerged as promising direction towards better graph neural architec- ture design Zhoo et al.
2019
Gao et al., 2020 Jiang and Balaprakash 2020 You et al. 2020 Zhao 2021 To enable powerful GNN architecture to be searched, AutoGNNN
al. 202T Ding et al.
first propose the GNN search space in the intra-layer level, i.c., providing common choices for several

---

Here summarize candidate choices for Table I: Overview of Existing AutoGNN Works. The "Differ." denotes differentiable algorithm.
Graph
MPNN Space
Method
Search Algorithm
Task
#node/edge types he lintra
inter
GraphNAS
1/
X
X X
RL EA+RL
node
AGNN
2 1 -
node
SANE
2 1/ 2
eoyer_nntle agg
deterministic Differ.
node
NAS- JAS-GCN
1/
X
layer_on _cnt
EA random
graph
You et al. 2020
layer_ent
nodeledge/graph
AutoGEL
2//21 1
M
V
|layer_ccnil _tt___tttt___a_ _agg] stochastic Differ.
node/cdge/graph
important operators in one MPNN layer (see and those operators:
2
Message Function My: Existing AutoGNNs mainly focus on the node-level and graph-level task, thus edge embeddings are often not available. M2 hu, eva) is reduced to Mx (h h.). Typically, (h,,, h.) = agw Wha. where Oun denotes the attention scores, and W E Rdxd denotes the linear transformation matrix. Note that NAS-GCN (Jiang and Balaprakash 2020) only takes the edge feature ean. as input without learning edge embeddings. We next denote the edge embedding to h, for distinguishing.
Aggregation AGGx: It controls the way aggregate message from nodes' neighborhood. It can be any differentiable and permutation invariant functions, usually AGGs E [summ, mean, maa] And swm (-) = (v) M& (h h,), mean(.) EveN(.) M& (b., (n)/) and max()) denotes channel-wise maximum across the node dimension.
Combination COM;: It determines the way to merge messages between neighhorhood and node itself. In literature, COMs is selected from [concat, add, mlp], where c-)cat(-) = [h m
add(.) h + m and mlp(.) = (L +)+1) (MLP is Multi-laye Perceptron). Activation ACT: lidentity, sigmoid, tanh, relu, elu] are some of the most commonly used activation functions [Gao et al. 2020
Graph Pooling: The pooling operator has been introduced for the graph classification task, such
as Iglobal pool, global attention pool, flatten] [Jiang and Balaprakash 2020 Wei et al. 2021
In addition to the above intra-layer operators, several works You
2020 Zhao et al. 2021
Jiang and Balaprakash 2020 propose the idea of searching layer connectivity to combine hidden representations of different layers in a better way, i.e., inter-layer design. More details will be discussed in Sec. 3.1.2 After the search space design, AutoGNNs adopt various search algorithms to search the optimal architecture from the search space. AGNN [Zou et al. 2019 and GraphNAS [Gao et al. 2020] follow the reinforcement learning (RL) [Williams] 1992 way to search architectures. They utilize a recurrent neural network controller for architecture sampling, and update the controller to maximize the expected performance of sampled architectures. NAS-GCN [Tiang and Balaprakash 2020) adopt evolutionary algorithm (EA), where new architectures are generated by performing mutation from parent architectures and the population, i.e., the best performing architectures, are iteratively updated. However, both RL and EA algorithms require a large number of architectures to be sampled, which is inherently computational expensive. To improve the search efficiency. SANE [hhao et al. 2021] adopts a deterministic differentiable search algorithm DARTS [Liu et al. 2018), where a supernet containing all candidate operators is constructed and architecture parameters jointly optimized with network parameters through gradient descent. Unfortunately. it has been discussed in SNAS [Xie et al. 2018 that DARTS suffer from the unbounded bias issue towards its objective, which limits the performance of the final derived model. In Tab. | we summarize existing AutoGNNs from several perspectives: graph, MPNN space, search algorithm, and task scenario.
2.3 GNNs for Link Prediction Task
Even with the great effort invested into the construction and maintenance of networks, many graph data sets still remain incomplete (Schlichtkrull et al.] 2018). Therefore, the link prediction (LP) task one of the most crucial problems in the graph-struccti data, which aims to recover those missing links in graph [Zhang et al.) 2019 2020a i.e., predicting the missing node in e(v;, ?)
3

---

where ? denotes the target node that has the potential link with Recently, GNN models have been introduced handle the LP task (abbreviated GLP models), which can be roughly categorized based on its application scenarios: GLPP on homogeneous graphs (i.e., only one type of nodes and edges Yang et al., 2016)), and multi-relational graphs (i.e., graphs with multiple edge types Toutanova and Chen 2015)).
2.3.1 Link Prediction on Homogeneous Graphs
As of the classic approaches for LPP task such homogeneous graphs. heuristic methods predict link existence according to heuristic node similarity scores (Zhang et al., 2020b]. Despite its effectiveness in some scenarios, heuristic methods hold strong assumptions on the link formation mechanism, i.c., highly similar nodes have links. It would fail on those networks where their assumptions do not hold [Zhang and Chen 2018). Furthermore, latent feature- baated methods [Perozzi et al. 2014, Grover and Leskoved 2016 factorize some network matrices to learn node embeddings in a transductive way, which limits their generalization ability to unseen data.
Recently, several GL.P models have been proposed for the I.P task on homogeneous graphs. GAE (Kipt and Welling 2016b applies GNN model over the entire graph and aims to learn node embed- dings that minimize the graph reconstruction cost through:
H = GCN( A (HH
(3)
where X E R is the feature matrix of nodes, A | is the adjacency matrix, H is the learned node representations, (-) is the logistic sigmoid function, Å denotes the reconstructed adjacency matrix, whose entry A.. the predicted score (between 0-1) for target link euv. However, GAE focus on aggregating node attributes only.
SEAL Zhang and Chen 2018 and DE-GNN al 2020 propose to learn the link embedding 2020 considers feature of subgraph
from the subgraph structures. Specifically, DE-GNN Li et al.
structure X e for aggregation and utilize node-set level readout:
H GCN(X A sub), h R((b.lv E S)),
(4)
where 5 = (u, o} denotes two nodes in the link c(u, u) for LP task, and R(-) is snterrecee-polling in DE-DENNN i.e., R(.) hh, hy
2.3.2 Link Prediction on Multi-relational Graphs
Different from graph form GEE, V), the multi-relational graph G(E, V, R) usually contains different types of edges, where r(u, v) indicates the edge type r E R existing between and v. For example, recommendation system, users and items are nodes of the bipartite graph, and the edge between nodes could be "click" and "add_to tottoo_ceee to__art". In the knowledge graph (KG) scenario, nodes represent real-world entities and edges are relations between entities.
Recently, several GLP models have been developed for the LP task on KGs (Shlichtkrul et al. 2018 Vashishth et al., 2019]. Based on the MPNN framework in ① and Q. R-GCN SShhichtkrul et al. 2018) proposes to model different edge types through edge-specift weight matrix W for r R. where the MPNN in R-GCN is instantiated as:
h h = ACT r(a,))))
W W
(5)
Similar to R-GCN modeling, D-GCN Marcheggiani and Titoy 2017 and W-GCN (Shang et al.
2019 also restricted to learning embeddings for nodes only. Instead, CompGCN (Vshhishhh et al.
2019
propose to jointly learn entity and relation embeddings:
h h ACT2 Er(a..)
Wi+1 X(r) 6 ht))
where h denotes the embedding vector for the specific edge type r, and A(r) E |incoming, outgoing, _lopp] records information of directed edges. ó Rd x Rd + Rd can be any entity-re entity-relation composition operation, such as sub in TransE [Brddes et al. 2013
Compared with earlier approaches, GLP models bring remarkable performance gains, illustrating their superiority over LP task. However, exiting GLP models rely on manual and empirical graph neural architecture design, such as selecting proper ACT(-) and ((-). Thus, a data-aware GL.P model is desired.

---

operator
weight matrix
hidden embedding
intermediate embedding
hidden embedding after byer_cnnt
MPNN layer
W veyf
1n/p
h
layer
h:
AGG
COM
ACT,
ugg
W /W3
Intra-layer MPNN search.
(b) Inter-layer MPNN search.
Figure 1: The illustration to AutoGEL's search space: a) given representation ht in k-th layer (including edge embedding h available), AutoGEL searches for proper operators of Φ², W AGG,, COM&, ACT; in the intra-layer space, then outputs the hidden node representation h h Note that the dotted area will be activated in the scenario of multi-relational graphs.
3 AutoGEL: AutoGNN with Explicit Link Information
3.1 Search Space
In this subsection, AutoGEL explicitly models the link information in the MPNN space, and proposes several novel operators at both intra-layer (i.e., the message passing a specific layer) and inter-layer designs (i.e., the message passing across layers). The overflow of space is shown in Fig. [
3.1.1 Intra-layer Message Passing Design
As discussed in Sec. D and Sec. 2.2 existing AutoGNNs lack modeling of links, which only utilize the pure link information of the node neighborhood. Such implicit way fails to handle and leverage the complex link information. To solve this issue, we present a novel intra-layer message passing framework, which instantiates
m
k+1
AGG 6(u) h U (())),
k+1
AGG
M() of (h h N()))).
(8)
h +++ = ACTM hh, m ())),
(9)
where 7 and { aggregate neighbor information for homogeneous and multi-relational graphs, respectively. W paragraph. For multi-relational graphs, neighboring nodes from different edge types should impose different influence for the center node during message passing. Thus, we utilize the edge embedding h in (%) to further encode the type of links, where h is updated by h W ret Wh And we incorporate the composition operator o(-) to encode the relationship between edge embedding h with node embedding h We highlight the differences between the standard MPNN space (see 1 in Sec. 2.2) with
6(u) and W *(a)) encode parts of the link information as discussed in the following
and follows:
Linear Transformation W Given the hidden representation from the last layer, we first apply linear transformation towards embeddings. Z.. we assign neighborhood-yyp specific weight ma- trices W 6(m)' where 6(u) E {sel neigh]. neigh, W
self. W neigh are introduced for the node itself and neighbors respectively. This is a weak attention mechanism towards the basic link information for homogeneous graphs, which can distinguish edges between self-type and neighbor-type. In multi- relational graphs, we edge-aware filters W A(e) where A(e) {self_loop, original, inverse)
encodes the direction information of edge e. We use Wk. at W w// for self-loop. original, and inverse edge separately.
Composition Operator 6² and Edge Embedding h:: Following CompGCN Vashishth al.
2019], we utilize the composition operator o(h h3) capture message between the node and edge embeddings before aggregation step. While CompGCN empirically selects the most proper ((-) through grid search, introduce this novel design dimension into our search space, that

---

AutoGEL is able to search for the most suitable one together with other design dimensions in more efficient way. Specifically, we incorporate the candidate operators {sub, mult, corr). where sub(.) h h Bordes al. 2013), mult(-) h h YYagg al. 2014 corr(-) h h [Nickel et al. 2016]. Together with W A(e) the search design @ h h enables AutoGEL to
capture semantic meaningful edges by h and the interaction between nodes with edges by d(-).
That is why AutoGEL can handle the LP task on multi-relational graphs, while another edge-level
model You et al. 2020 cannot (see Tab.
3.1.2 Inter-Layer Message Passing Design
Traditional MPNNSs follows the way in (I i.e. the input of each MPNN layer is the output of last layer. Motivated by [Xu al. 2018a Sa Li al. 2019], it is beneficial use the combination of previous layers as input to each layer. In this paper, we also design the inter-layer search space to enables the flexible and powerful GNN architecture to be searched. Specifically, we provide two design dimensions: layer connectivity and layer aggregation.
The literature [Li 2019] have shown that incorporating skip connections (i.e., residual connections and dense connections) across MPNN layers can help alleviating the over- smoothing issue [Li et al., 2018) and empirically improve the model performance. In this work, we conduct systematical investigation towards the joint impact of skip connections together with other design dimension. We select the way of layer connectivity from the set (skip, le_sum, le_llle__oaa (e_oonca)). Moreover, the layer connectivity function is given as:
Layer Connectivity:
h+ skip, sum(h" " h++t), Ic lc_sum,
h A+1 +- layer__nn((h h**l)=
)
(10)
Weoncat(h bb+1), lc lc_concat,
where h denotes embeddings output from k-th MPNN intra-layer. As shown in Fig. (b). the representation h will be fed into k- + 1-th MPNN layer to learn h411, Then, AutoGEL. combines h with ++1 as in (TO) to form a new representation, which will be fed to the next layer. Note that another AutoGNN SANE Zhao et al. 2021 does not include le_concat.
2018a| shows that the layer-wise aggregation allows the adaptive representation learning. The set of candidate layer-wise aggregation defined in AutoGEL is (skip, la concat lo_ [a_max). Specifically, the layer aggregation function is defined as:
Layer Aggregation: JKNet [u et al.
h- skip,
h layer_agg(hi ..... h4) [l'll.. 11h),, la la_concat,
(11)
maa(h" ,..., h²²,, la_max.
Note that (ayer_agl) aggregates the representations generated from MPNN layers, i.c., those that have not been processed by layer ent (Fig. [ (b)). And previous AutoGNNs NAS-GCN (Jian
and Balaprakash 2020 and You et al. 2020 do not include this operator layer_agg.
3.1.3 Pooling
After the intra-layer (Sec.F 3.I.T and inter-layer (Sec. 3.1.2p message passing stages, pooling operation h
R(hh,/ / E ) induces high-level representations, where and X' depend on the given task.
For LP task on homogeneous graphs, the pooling operation outputs the representations links. In SEAL [Zhang and Chen 2018), subgraph-level sortpooling method is utilized to readout information from the entire enclosing subgraph for the target link. It is proved in [Srinivasan and Ribeiro 2019 that joint prediction task only requires joint structure representations of target node-set S. Thus, it is not necessary to introduce complex subgraph-leve pooling methods. We following DE-GNN Li et al. 2020] to learn link representations by readout only from target node-set, i.c., h. = R( (b E SJ.. Note that the original setting difference-pooling for R(-) in DE-GNN does not achieve competitive performance in the empirical study. Instead, we provide the powerful pooling operations (sum, max, concat) to be selected for R(.). As for multi-relational graphs, the pooling stage is not required since the edge embedding h. is learned in the intra-layer MPNN.

---

For the node classification task, AutoGEL simply removes R(-) from the search space as literature does. For the graph classification task, the pooling operation outputs high-level graph representation be = R (h / G}), and R(-) E {global_ lad___dd_ooooo global_mean_ globul _aaearl_________ [
3.2 Search Algorithm
Given a candidate set O for a specific operator (e.g., {sum, mean, max] for AGG²), let be the hidden vector to be fed into this operator, and (t, records the weight that operation o E O to be selected. Then the output from this operator is computed as o(x) Eoeo t, o(x), where 8s E {0, There are multiple operators in AutoGEL's space (see Sec.
including intra-layer level operators (i.e., of, AGG CO ACT,), inter-layer operators (i.e., layer_end, layeelaaaaaaoo _agg), and pooling operator R(-). Let denote the operation selection for all operators. The GNN search problem can be formulated maxe.w w f(0,, w: D), where f(-) evaluates the performance of GNN model θ with weight w on the graph data D.
As discussed in Sec. 2.2 the search algorithm adopted in existing AutoGNNs suffers from several issues. Especially, the most similar prior work SANE (Zhao et al. 2021 adopts DARTSS Liu et al. 2018). which directly relaxes O to be continuous and makes the objective f(O,, w: D) deterministic differentiable. However, several drawbacks brought by the mixed strategy of DARTS [Lu al, 2018 have been observed and discussed in the community of neural architecture search. The mixed strategy usually leads to the inconsistent performance issue, i.e., the performance of the derived child network at the end of the searching stage shows significant degradation compared with the performance of the parent network before architecture derivation. That is because the relaxed 9 cannot converge to one-hot vector (Zela et al., 2019| Chu al. 2020]. thus removing those operations at the end of search actually lead to a different architecture from the final searching result. Moreover, the mixed strategy must maintain all operators in the whole supernet, which requires more computational resources than the one-hot vector
Yao et al., 2020].
Fortunately, SNAS [Xie et al. 2018 leverages the concrete distribution (Maddison et al. 2016 Jang et al. 2016 to propose a stochastic differentiable algorithm, which enables the search objective differentiable with the reparameterization trick. Let a GNN model O being sampled from the distribution Pa (0) that parameterized by the structure parameter a as:
exp( o, log(- log((~oogU.)))) log(UU))))/)) 0. Eveo exp((log ao log( - log((log(U,))
(12)
where T is the temperature of softmax, and Uo is sampled from the uniform distribution, i.e.. Ug ~ f 1). It has been proven that p(iim- 02 =) / / LorE 0ao' [Maddison et al. 2016). This first guarantees that the probability of o being sampled (i.e., 6. = 1) is proportional to its weight a.., a., Besides, the one-hot property lim,-+ 0,- 1 makes the stochastic differentiable relaxation unbiased once converged [ie et al. 2018 Then the GNN searching problem is reformulated into maxa.w E.o (0) (O,, w; D)J, where E|. is the expectation. We leverage SNAS (Xie et al. 2018 to optimize the weight of GNN w and the weight of operator a.
4 Experiments
4.1 Experimental Setting
AutoGEl is implemented on top of code provided in DE-GNN
Li et al. 2020 and CompGCN 2019] All the experiments
Vashishth al. 2019] using Pytorch framework (Paszke al.
performed using one single RTX 2080 Ti GPU. More details about data sets, Hyper-parameter settings
and search space designs are introduced in Appendix A.I.I A.1.2 and A.1.3 respectively.
Task and Data sets. For LP task on homogeneous graphs, we follow /Zhang and Chen 2018 Li
et al. 2020) to utilize the datasets: NS (Newman 2006). Power [Watts and Strogatz, 1998 Router
[Spring et al. 2002), C.cle [aatts and Strogatz 1998]. USAir [Batagel] and Mrvar 2009 Yeast
Von Mering al. 2002) and PB [Ackland et al. 2005 As for the LP on multi-relational graphs,
we mainly adopt benchmark knowledge graphs (KGs), FB15k-237
[Touaaovva and Chen 2015 and
WN18RR (Dettmers et al. 2018
Code at hrt.ll/lktttttg//gtto//oooo/aaaa
7

---

Table 2: Average AUC (with standard deviation) for LP task on homogeneous graphs
Type
Model
NS
Power
Router
C.ele
USAir
Yeast
PB
CN
94.42=0.95
58.80+0.88
06.43+-0552
85.13=1.61
93.80=1.22
89.37=0.61
92.04=0.355
Heuristic
RA
94,45-0.93
58.79-10.88
56.43-10.51
1..49=1.41
95.77-00.22
89,45-00.2
92.46.10.37
Katz
94.85=1.10 65.39:1.59
38.62:+1.35
86.34=1.89
92.88=1.42
92.24=0.61
92.92=00335
SPC
89.94=2.39 91.78+0.61
68.79:+2.42
51.90=2.57
74.22+3.11
93.25+0.40
83.96+0.86
Latent
LINE
80.63=1.90 55.63+1.47
67.15:22.10
69.21=3.14
81.47:100771
87.4543.33
76.95=2.76
N2V
91.52=1.28 76.22=#0.92
65.46:40.86
84.11=1.27
91.44=1.78
93.67=0.46
85.79=0.78
VGAF
94.04+1.64
71.20+
61.51++1.22
81.80=2.18
89.28+1199
93.88+00221
90.70+0.53
PGNN
94.8
0.33
89.72:t0.32
GLP
SEAL
98.85=0.47 87.61+1557
96.38+11.4
90.30=1.a3
96.62=0.72
0..91=0.52
94.72=#0.46
DE-GNN
99.09=0.79
96.68+0.29
98.69++0.17
89.37=0.17
98.04+0.66
08.59+0.26
94.95+00.77
AutoGNN|
AutoGEL
99.89 0.06 98.00 1.000.0.. 10021 99.08
0.28 92,90 1.02
98.49 0.45
99.24 1.110
97.27 1..15
For the node classification task, we compare models on three popular citation networks [Sen et al. 2008), i.e., Cora, CiteSeer, and PubMed. For the graph classification task, we adopt four standard
benchmarks Yanardag and Vishwanathan 2013]: 1) social network datasets: IMDB-BINAR BINARY and
2) bioinformatics datasets: MUTAG and PROTEINS.
Evaluation Metries. For node classification and graph classification, we adopt average accuracy as measurement. We report AUC with standard deviation for LP task on homogeneous graphs. For LP on KGs, we adopt standard evaluation matrices:
Mean Reciprocal Ranking (MRR): [ 1/rank) where S and rank; denote test triples and ranking results, respectively
Hits@N: :: [Σ |9| 1((rnkk; S N))) where 1 denotes indicator function, and N {1,3, 10).
Baselines. For LP homogeneous graphs. use the following approaches baselines: I)
heuristic methods: CN (Bütün et al. 2018 RA [hou et al. 2009), and Katz [Katz] 1953] 2) latent
feature based methods: Spectral clustering (SPC) Tang and Liu 2011 LINE Tang et al. 2015 and
node2vec (N2V) Grrover and Leskoved 2016 3) GLP methods: VGAE Kipl and Welling 2016b
PGNN You et al. 2019]. SEAL Zhang and Chen 2018 and DE-GNN Li Li al. 2020
For LP on KGs, we compare AutoGEL with several KG embedding approaches: 1) the geometric models: TransF [Bordes et al. 2013) and RotatE (Sun et al. 2019], 2) bilinear models: DistMult
Yang et al. 2014] and ComplEx [Troillon et al. 2016). 3) GI.P models: R-GCN (Kipf and Welling 2016b]. SACN [Shang et al. 2019). VR-GCN Ye et al. 2019) and CompGCN [Vashishth et al.
2019]. 4) other NN-based models: ConvKB Nguyeen et al. 2017]. ConvE [Dettmers et al. 2018).
ConvR (Jiang et al. 2019 and HyperER Balazević et al.) 2019].
For the node classification task, we compare AutoGEL with the following baselines: 1) manually
designed GNNs: GCN [Kipf and Welling 2016a), GraphS [Hamilton et al. 2017]. GAT
(Veličković al., 2017 and GIN [Xu et al. 2018b]. , 2) AutoGNNs: GraphNAS [Gao al. 2020).
SANE Zhao et al. 2021 and You et al.) 2020 AGNN Zhou et al. [209 is not included due to no
available code.
For the graph classification task, we compare AutoGEL with the following baselines: 1) manually designed GNNs: PATCHY-SAN [Niepert et al. 2016. DGCNN [Zhang al.. 2018), GCN (Kipl
and Welling 201 GraphSAGE [aamlloon et al. 2017 and GIN [Xu et al. [0188 8b), 2) AutoGNNs:
Youu et al. 2020]. Note that NAS-GCN is specifically designed for molecular property prediction, which is not included in the comparison.
4.2 Comparison with GLP models
The model comparison for LP task on homogeneous graphs and knowledge graphs have been summarized in Tab. 2 and 3 respectively. As shown in Tab. 2 heuristic methods perform well on several datasets, but they fail to handle data sets Power and Router. Latent feature-based methods improve the performance on these two data sets but cannot achieve competitive results on other data sets. GLP models outperform heuristic methods and latent feature-based methods, showing their superiority towards LP task. Specifically, DE-GNN is our strongest baseline, where vanilla GCN is adopted to learn node representations for all datasets, then link representation is induced by pooling node embeddings in 4 However, DE-GNN fails to handle the data-diversity issue and
8

---

Table 3: MRR and @its@N N for LP task on knowledge graphs
Type
FB15k-237
WN18RR
Model
MRR
Hits@ 10
Hits@3
Hits@l
MRR
Hits@ 10
Hits@3
Hits@)
TransF
.294
.465
.226
Geometric
RotatE
.338
.533
.355
.241
.476
.71
.492
.428
DisMult
.241
.419
.263
.155
.430
.490
.440
.390
Bilinear
ComplEx
.247
.428
.275
.158
.440
.500
.460
.410
ConvKB
.243
.421
.371
.155
.249
.524
.417
.057
ConvE
.325
.501
.356
.237
.430
.520
.440
.400
NN-based
ConvR
.350
.528
.385
.475
.537
.489
.443
HyperER
.341
.520
.376
.252
.465
.522
.477
.466
R-GCN
.248
.417
.151
SACN
.350
.540
.390
.260
.470
.540
.480
.400
GLP
VR-GCN
.248
.432
.272
.159
CompGCN
355
.535
.390
.264
.479
.546
.494
443
AutoGNN
AutoGEL
.357
.538
.391
.266
.479
.549
.492
.444
Table 4: Average accuracy (%) for node classification and graph classification
Node Classification
Graph Classification
Type
Model
Cora CiteSeer Pubmed
IMDB-B IMDB-M MUTAG PROTEINS
PATCHYSAN DGCNN
71.00
45.20
92.60
75.90
70.00
47.80
85.80
75.50
Manual GNNs
GCN
88.11
76.66
88.58
74.00
51.90
85.60
76,00
GraphSAGE
87.41
75.99
88.34
72.30
50.90
85.10
75.90
GAT
87.19
75.18
85.73
GIN
86.00
73.40
87.99
75.10
52.30
89.40
76.20
GraphNAS
88.40
77.62
88.96
SANE
89.
78.59
90.47
AutoGNN
You et al. 2020
88.50
74.90
47.80
73.90
AutoGEL
89.89
77.66
89.68
81.20
56.80
94.74
82.68
cannot consistently achieve leading performance all data sets. In this paper, AutoGEL first adopts the pooling way in DE-GNN, then enables a more flexible way to select the most suitable pooling function R(-) (see Sec. 3.1.3 instead of the fixed pooling function in DE-GNN. Searching the pooling function and other operators make AutoGEL handle the data-diversity issue, and consistently achieve the state-of-the-ae performance for LP task on homogeneous graphs. Furthermore, we demonstrate the model performance of LP task on knowledge graphs in Tab. 3 Note that the improvements on KGs not as obvious as that on homogeneous graphs. In practice, GLP models run longer than Geometric and Bilinear models, which leads to the difficulty of tuning hyper-parameters (see more discussions in Appendix A.4)
Moreover, we present several cases of searched architectures Appendix A.2
And we show several
ablation studies provide some insights into the AutoGEL space design in Appendix A.3] including the impacts of the inter-level design, pooling operator, weight transformation matrices, and edge embedding.
4.3 Comparison with AutoGNN models
To compare with other AutoGNNs, we also demonstrate the performance of AutoGEL node-level and graph-level tasks. The empirical comparison on the node classification and graph classification task is shown in Tab. g AutoGEL shows the great generalization ability towards different graph tasks. AutoGEL outperforms all the manually designed GNN basclines and also achieves competitive results with existing AutoGNNs designed specifically for these tasks. The data for node classification task usually contains rich node features. AutoGEL simplifies the attention mechanism in existing GNNs for node classification from auv (see Sec. 2.2 W
6(u) in which leads to slightly inadequate performance. We notice that AutoGEI. brings more significant performance gains on the graph classification task. The data sets for graph classification have not sufficient node features

---

Table The search time (clock time in seconds) of AutoGNNs on the node classification task.
Model
Cora
Citeseer
PubMed
GraphNAS [Gao et al. SANE
2020
3240
3665
5917
Zhao et al. 2021
14
35
54
AutoGEL
12
16
19
I810 1918
860
BA 1AD 153 12>
66. 88 880 8.. 100 133
(a) task on NS
(b) LP task on FB15k-237
(c) NC task on Cora
(d) GC task on PROT
Figure 2: Performance frrquencyy statistics multiple runs for each task
as those data sets for node classification, which requires effective learning from graph structures. AutoGEL is more suitable for this task by learning from edges.
We also compare the search efficiency between AutoGNNs in Tab. 5 Statistics for other AutoGNNs
are taken from the start-of-the-ar SANE (hao et al. 202T) which sets search epochs to 200 for all the AutoGNN baselines. To reduce search cost in GraphNAS, SANE and AutoGEL leverages the idea of parameter sharing Pham et al. [2018] to avoid repeatedly training weights of different sampled GNN architectures. Moreover, AutoGEL adopts more advanced search algorithm compared with SANE (see Sec. 3.2 thereby further reduces the search cost. We show experimental results of variant AutoGEL in search algorithm in Appendix A.. And more details about search efficiency are reported in Appendix A.4
4.4 The Empirical Study on Robustness
All effectiveness results in the main context (Tab. Tab. 3 and Tab. are reported under the average of 4 runs. Note that Tab. D and Tab. do contain variance due space limits. To illustrate the robustness of AutoGEL, here report results after multiple runs of AutoGEL on several tasks in We set the number of different runs as 10 for FB15k-237 dataset and 50 for the rest, due the relative longer rumning time required for FB 15k-2237. We can see that even in the some worst cases, AutoGEL still rival or surpass its strongest baselines over all the tasks, its indicating the effectiveness.
Fig. 2
5
Conclusion
In this paper, we present a novel AutoGNN with explicit link information, named AutoGEL. Specifi- cally, AutoGEL incorporates the edge embedding the MPNN space, and proposes several novel design dimensions at intra-layer and inter-layer designs. Moreover, AutoGEL upgrades the search algorithm of AutoGNNs by leveraging a promising NAS algorithm SNAS. Experimental results well demonstrate that AutoGEL not only achieves the leading performance on the LP task, but also shows competitive results on the node and graph classification tasks.
For future works, one direction worth trying is to adapt AutoGNNs to the LP task on hyper-relational KGs, which contain a lot of hyper-relational facts r(u1,..... U,,), n > 2. First, the pioneer data-aware methods for LP tasks on KGs are mainly based on the bilinear models, such as AutoSF iZhang et al. 2020c and ERAS [Shimin et al., [021]. Introducing the MPNN space can promote a more comprehensive search space because the composition operator is not limited to the bilinear models. Second, using the multi-relational hypergraph could be a more natural way to model hyper-relational facts [Yadati] 2020 Di et al. 2021). Another interesting direction is to search GNN architectures on dynamic graph data sets. Note that search efficiency would the most challenging issue. One the
key points is to make full use of previous well-trained GNN controllers.
10

---

Acknowledgements
Lei Chen's work is partially supported by National Key Research and Development Program of China Grant No. 2018AAA0101 100, the Hong Kong RGC GRF Project 16202218, CRF Project C6030-18G, C1031-18G, C5026-188 18926,88G,10 RIF Project R6020-19, AOE Project AoB/E-603/18, Theme- based project TRS T41-603/20R, China NSFC No. 61729201, Guangdong Basic and Applied Basic Research Foundation 2019B15153001 Hong Kong ITC ITF grants ITS/044/18FX and ITS/4770/8FXX Microsoft Research Asia Collaborative Research Grant, HKUST-NAVERILINE Al joint research lab, HKUST-Webank joint research lab grants.
Lab,
References
Zhan Bu, Jie Cao, Hui-Jia Li, Guangliang Gao, and Haicheng Tao. Gleam: A graph clustering framework based on potential game optimization for large-scale social networks. Knowledge and Information Systems, 55(3):741-770, 2018.
Alvaro Sanchez-Gonzaler Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control. In ICML, pages 4470-4478 PMLR, 2018.
Xiang Yue, Zhen Wang, Jingong Huang, Srinivasan Parthasarathy, Soheil Moosavinasab, Yungui Huang. Simon M Lin, Wen Zhang, Ping Zhang, and Huan Sun. Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics, 36(4): 1241-12511111111 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks arXiv preprint Xiv: ww..::169.0022000 160.002977 201
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint arXiv: 1rXiv:1706.0223 706.02216. 2017.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-
relational graph convolutional networks. arXiv preprint 19Xv:1911.00008) 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. NeurIPS, 33, 2020.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In ICML, pages 2014-2023. PMLR, 2016.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, volume 32, 2018.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. NeurIPS, 33, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263-1272. PMLR, 2017.
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey. J. Mach. Learn. Res., 20 2019.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv: 1909.03199 2019.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In IJCAI, volume 20, pages 1403-1409, 2020.
Shengli Jiang and Prasanna Balaprakash. Graph neural network architecture search for molccular property prediction. arXiv preprint arXiv:2008.122 12187, 2020.
Huan Zhao, Quanming Yao, and Weiwei Tu. Search to aggregate neighborhood for graph neural network. ICDE, 2021.
11

---

Yuhui Ding, Quanming Yao, Huan Zhao, and Tong Zhang. Diffig: Differentiable meta graph search for heterogeneous graph neural networks. In SIGKDD, pages 279-288, 2021.
Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. CIKM, 2021.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning, 8(3-4))229-256, 1992.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint XrXiv: I 806.09055, 2018.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint 182.9999, 2018.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. European semantic web conference, pages 593-607, Springer, 2018.
Yonggi Zhang. Quanming Yao. Yingxia Shao, and Lei Chen. Nscaching: simple and efficient negative sampling for knowledge graph embedding. ICDE, pages 614-625. IEEE, 2019.
Yongqi Zhang, Quanming Yao, and Lei Chen. Interstellar: Searching recurrent architecture for knowledge graph embedding. NeurIPS, 33:10030 10040, 2020a.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, pages 40-48, PMLR, 2016.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57-66, 2015.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010. 16103, 2020b.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. arXiv preprint arXiv: 802.09691, 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, pages 701-710, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. SIGKDD, pages 855-864, 2016.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 16111111110000 107308. 2016b.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. arXiv preprint
2017.
Chao Shang, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. End-to-end structure- aware convolutional networks for knowledge base completion. In AAAI, volume 33, pages 3060-3067, 2019.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 1-9, 2013.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575, 2014.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic embeddings of knowledge graphs. In AAAI, volume 30, 2016.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML,, pages 5453-5462 PMLR, 2018a.
12

---

Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9267-9276, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, volume 32, 2018.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arXiv:1910.00452 2019.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Un- derstanding and robustifying differentiable architecture search. arXiv preprint arXiv: 9909099666 2019.
Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. Fair darts: Eliminating unfair advantages in differentiable architecture search. ECCV, pages 465-480. Springer, 2020.
Quanming Yao, Ju Xu, Wei- Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In AAAI, volume 34, pages 6664-6671 2020.
Chris J Maddison, Andriy Mnih, and Yee Whye Tch. The concrete distribution: continuous relaxation of discrete random variables. arXiv preprint 1XXiv:611.00011 2016.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softnax, arXiv
preprint XrX: 161 .01114,144 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint 1911v:1912.01703 2019.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks.. nature, 393 (6684):440-442, 1998.
Neil Spring, Ratul Mahajan, and David Wetherall. Measuring isp topologies with rocketfuel. SIGCOMM, 3334):33-144, 2002.
Vladimir Batagelj and Andrej Mrvar. Pajek datasets (2006), 2009.
Christian Von Mering, Roland Krause, Berend Snel. Michael Cornell, Stephen G Oliver, Stan- ley Fields, and Peer Bork. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 417(6887) 403, 2002.
Robert Ackland et al. Mapping the us political blogosphere: Are conservative bloggers more prominent? In BlogTalk Downunder 2005 Conference, Sydney. BlogTalk Downunder 2005 Conference, Sydney, 2005.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, volume 32, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In SIGKDD, pages 1365-1374, 2015.
Ertan Bütün, Mehmet Kaya, and Reda Alhajj. Extension of neighbor- link prediction methods for directed, weighted and temporal social networks. Information Sciences, 463:152-165 2018.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(4)6223-630 2009,
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-4) 1953.
13

---

Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23(3):447-77, 2011.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In WWW, pages 1067-1077,201
Jiaxuan You, Rex Ying. and Jure Leskovec. Position-aware graph neural networks. In ICML, pages 7134-7143. PMLR, 2019.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint 19Xiv:192.101999 2019.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, pages 207 10800. PMLR, 2016.
Rui Ye, Xin Li, Yujie Fang, Hongyu Zang, and Mingzhong Wang. A vectorized relational graph convolutional network for multi-relations network alignment. In IJCAL pages 4135 4141, 2019.
Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. A novel embedding model for knowledge base completion based on convolutional neural network. arXiv preprint arXiv:1712.02121,, 2017.
Xiaotian Jiang, Quan Wang, and Bin Wang. Adaptive convolution for In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume (Long and Short Papers), pages 2019.
learning.
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Hypernetwork knowledge graph em- beddings. In International Conference on Artificial Neural Networks, pages 553-565. Springer, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks, arXiv preprint 111.v11700.1903,
2017. 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0005. 2018b.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In ICML, pages 4095-4104. PMLR, 2018.
Yongqi Zhang, Quamming Yao, Wenyuan Dai, and Lei Chen. Autosf: Searching scoring functions for knowledge graph embedding. In ICDE, pages 433-444 IEEE, 2020c.
DI Shimin, YAO Quanming, Yongqi ZHANG, and CHEN Lei. Efficient relation- aware scoring function search for knowledge graph embedding. In ICDE, pages 110--1115, IEEE, 2021.
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hypergraphs. NeurIPS, 33, 2020.
Shimin Di, Quanming Yao, and Lei Chen. Searching to sparsify tensor decomposition for n-ary relational data. In Webconf, pages 4043-4054, 2021.
James Bergstra, Daniel Yamins, and David Cox. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. In ICML., pages 115-123. PMLR, 2013.
Mare Barthélémy and Luis A Nunes Amaral. Small-world networks: Evidence for a crossover picture. In The Structure and Dynamics of Networks, pages 304-307. Princeton University Press, 2011.
Matthew K Matlock, Arghya Datta, Na Le Dang, Kevin Jiang, and S Joshua Swamidass. Deep learning long-range information in undirected graphs with wave networks. In IJCNN, pages 1-8. IEEE, 2019.
Nima Dehmamy, graph neural networks learning graph topology. arXiv preprint arXiv: 1907.1197..00 000000 2019.
Barabási, and Rose Yu. Understanding the representation power of
14


Reviews:
[{"review_id": "yh7eyWg-yNc", "reviewer": "Reviewer_q5RS", "summary": "The authors propose an AutoGNN model that introduces more design dimensions in both inter- and intro-layer. It is a decent attempt for authors to take into consideration the edge embedding in MPNN and adopt a stochastic differentiable search algorithm, making the model be able to better handle the link prediction problem and get more efficiently optimized. ", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\nS1) The paper is well-written and organized, and the proposed model (AutoGEL) is technically sound. In AutoGEL, more design spaces are introduced to be learned both with intra- and inter-layer, which would intuitively make the trained model perform better than manually designed ones.\n\nS2) In AutoGEL authors explicitly learns the edge embedding in the message passing framework to model the complex link information, making AutoGNN-like model be generalized to the LP task.\n\nS3) Adopting differentiable search algorithm to optimize the GNN architecture parameters makes the model be able to be trained more efficiently and stably.\n\nS4) Extensive experiments are well organized to show the effectiveness and competitiveness of AutoGEL.\n\n\nWeaknesses:\n\nW1) As authors mentioned in Section 4.2, the more the design dimensions, the longer the model will run, which indeed would be the case. Although the running times are still rather low, explicitly showing the scalable would be worth including.\n\nW2) There are still critical structure components needing to be manually designed such as the number of layers of the model, which would have significant impact on the performance of model even after GNN operators being decided.\n\nW3) The problem is not as novel, but Table 1 did help frame and clarify the distinction of this work compared to other recent related autoGNN methods.  \n\n\nOther Comments/Questions/Typos:\n\n1) In the paper, the authors attempt to add edge embedding in MPNN to handle the LP task and also improve the performance of the model on other tasks. However, in the experiments section, it seems in the specific models that are used in node classification and graph classification are missing the edge embedding component (as demonstrated in Figures 4 and 5 in the appendix).\n\n2) In the ablation study, it seems better to add some experiments for testing the effectiveness of the edge embedding. (i.e., using model without the edge embedding component on LP tasks).\n\n3) \"The empirical comparison on the node classification and graph classification task is shown in Table 7.\" is mentioned, but there is no Table 7 and it also does not correspond to Table 7 in the supplemental file.\n\n4) For selecting an operation in an operator, would it be necessary for the operators to converge to a one-hot vector? What if not and just take the real-valued operator vector as a mixed strategy?\n\n5) How does the edge embedding matrix (i.e., h_e^x) update?\n\n6) I was thinking more design dimensions can be similarly regarded as more parameters (but in terms of structure not weight), thus it would somewhat make it easier for overfitting.\n\nPlease note that I have gone through the author response and other reviews/comments, but respectfully keep my score of 6 (i.e., unchanged).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There does not appear to be any negative societal impact of this work. In fact, it helps alleviates some of the impracticalness of some prior autoGNN work regarding the computational running time needed for slight performance improvements (when thinking from an environmental standpoint). ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UfLGl8NqdoX", "reviewer": "Reviewer_K8wz", "summary": "This paper proposes an automated Graph Neural Network (GNN) framework for link prediction tasks on graphs.\nThe experiment results suggest that the architecture search is useful.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper performs a GNN architecture search for link prediction tasks. \nThe proposed search space is specialized for link prediction tasks.\nThe experiment results suggest that the architecture search is useful, however it seems that the performance gain is marginal.\nIn terms of novelty, the framework for the proposed search space follows paper [1], with some specialization on link prediction tasks.\nOverall, the paper targets a useful problem in the graph learning community. \nMy main concerns are over (1) if the technical novelty is enough; (2) if the experimental results are sufficient.\n\nAdditionally, I have these specific comments for the authors to stress.\n\n(1) The search algorithm being used is very vague (Section 3.2).\nThe paper claims that \"AutoGEL adopts its stochastic differentiable search algorithm\".\nHowever, for discrete architectural choice, e.g., sum, mean, max for AGG, it is unclear how that is differentiable.\nThe authors should elaborate more on the search algorithm; otherwise, the correctness/novelty of the algorithm cannot be evaluated.\n\n(2) In paper [1], in fact, they have done an architecture search for link prediction tasks. That part of the results is shown in the Appendix (https://arxiv.org/pdf/2011.08843.pdf). The authors should correct the descriptions in Table 1 and corresponding discussions. Additionally, the author may want to emphasize more on the specialty of the proposed search space, compared to a standard GNN search space.\n\n(3) Regarding the limitations of the paper, the authors mention that \" In practice, GLP models run longer than Geometric and Bilinear models, which leads to the difficulty of tuning hyper-parameters\". I think this is a non-trivial limitation. How difficult it is to use AutoGLP? \n\n(4) I think the authors should report one important metric, that is how many models have been searched to get each of the experiment result. The AutoML approach naturally spends much more computing resources, therefore directly comparing the numbers is not meaningful.\n\n[1] Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.\nRegarding the limitations of the paper, the authors mention that \" In practice, GLP models run longer than Geometric and Bilinear models, which leads to the difficulty of tuning hyper-parameters\". I think this is a non-trivial limitation. How difficult it is to use AutoGLP?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SGCTg2YKD0L", "reviewer": "Reviewer_GtXj", "summary": "This paper proposes a neural architecture search method for using GNNs for link prediction. The proposed method explicitly models edge information in the search process, and proposes several novel design and search space choices for AutoGNN. Through a DARTS-like differentiable search method, the proposed method achieves state-of-the-art performance on various link prediction and node/graph classification tasks.", "questions": "", "limitations": "", "rating": 6, "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": "Originality: Link prediction on graphs is an important task yet receives less attention than node/graph classification. This paper extends AutoGNN to link prediction and obtains SoTA results, which is highly appreciated for the community. The related work is sufficient, especially for including some latest arxiv papers on GNN link prediction.\n\nQuality: The techincal part of the paper is ok. It is an application of an existing NAS algorithm SNAS with some novel design of search spaces. Nevertheless, the proposed search space choices are novel and reasonable to me.\n\nClarity: The paper is easy-to-understand and written in an intuitive way.\n\nSignificance: Through extensive experimental results, the proposed AutoGNN method demonstrates SoTA results across a number of tasks (not restricted to link prediction), outperforming manually designed models. This demonstrates the importance for explicit modeling edge information and link prediction in designing GNN architectures.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. One concern is the search efficiency (in general) for NAS methods. The paper discusses this issue in Section 4.3. Another concern is that the search space does not incorporate different node labeling methods for GNN link prediction, such as distance encoding, which are shown to be crucial for success of GNNs on link prediction. Thirdly, I suggest demonstrating one or two common findings from the searched architectures: what components of a GNN are most important for link prediction?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "QAjDYYPjLgs", "reviewer": "Reviewer_Gqb4", "summary": "The paper introduces an automated graph neural network model with explicit link information. The model is tested on link prediction task (both homogeneous and heterogenous graphs) and node classification task. It shows improvement compared with the baseline models selected.", "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": "The paper mostly focuses on explaining how it incorporates the link information (edges) and it can generate edge embeddings so it would be suitable for link prediction in multi-relational graphs, such as knowledge graphs. The proposed method is primarily based on existing approaches with a few incremental tweaks and combining different components from different approaches (e.g., combining intra-layer message passing and inter-layer message passing). However, in the experiments, it seems that the model has yet being compared with the most up-to-date models in the link prediction task with FB15k-237 dataset (https://paperswithcode.com/sota/link-prediction-on-fb15k-237). So the overall contribution is unclear. Although link prediction is a hard task considering that there are now a lot of high baseline models to compare, the selling point of this paper seems to be using link information to improve upon link prediction task. The paper does not seem to convince the readers on this aspect. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new autoGNN model that takes link information into considerations. The model has shown better performance compared to baselines. The reviewers had concerns on novelty and baselines, and suggested new experiments. The authors have done a good job in addressing reviewers’ concerns, which is reflected in the increase of some rating. The concerns regarding to KG link prediction tasks has been well addressed in the rebuttal, although the reviewer didn’t raise their rating. Overall, the paper extends an existing algorithm, by considering link prediction task and modeling edge information. Although the idea is incremental, the execution of this paper is solid. I thus recommend accept.
Decision: Accept (Poster)