Title: SCALABLE GENERATIVE MODELS FOR GRAPHS WITH GRAPH ATTENTION MECHANISM Anonymous authors Paper under double-blind review

Abstract: Graphs are ubiquitous real-world data structures, and generative models that approximate distributions over graphs and derive new samples from them have significant importance. Among the known challenges in graph generation tasks, scalability handling of large graphs and datasets is one of the most important for practical applications. Recently, an increasing number of graph generative models have been proposed and have demonstrated impressive results. However, scalability is still an unresolved problem due to the complex generation process or difficulty in training parallelization. In this paper, we first define scalability from three different perspectives: number of nodes, data, and node/edge labels. Then, we propose GRAM, a generative model for graphs that is scalable in all three contexts, especially in training. We aim to achieve scalability by employing a novel graph attention mechanism, formulating the likelihood of graphs in a simple and general manner. Also, we apply two techniques to reduce computational complexity. Furthermore, we construct a unified and non-domain-specific evaluation metric in node/edge-labeled graph generation tasks by combining a graph kernel and Maximum Mean Discrepancy. Our experiments on synthetic and real-world graphs demonstrated the scalability of our models and their superior performance compared with baseline methods.

1. INTRODUCTION:

Graphs are ubiquitous and fundamental data structures in the real world, appearing in various fields, such as social science, chemistry, and biology. Moreover, in applications such as drug discovery and network simulation, graph generative models that can approximate distributions over graphs on a specific domain and derive new samples from them are very important. Compared with generation tasks for images or natural language, graph generation tasks are significantly more difficult; this is due to the necessity of modeling complex local/global dependencies among nodes and edges as well as the intractable properties of graphs themselves, such as discreteness, variable number of nodes and edges, and uncertainty of node ordering.

Among the several challenges involved in graph generation tasks described above, scalability is one of the most important for applications in a wide range of real-world domains. In this paper, we define scalability from three perspectives: graph scalability, data scalability, and label scalability. Graph scalability denotes scalability to large graphs with many nodes within the limit of practical time/space complexity, especially in training. Data scalability denotes scalability to large datasets containing many data. Label scalability denotes scalability to graphs with many node/edge labels. Besides these, it is possible to consider other viewpoints, such as edge number, graph diameter, and the total number of nodes in a dataset. However, because these are closely related to the above three defined perspectives, we consider them as a mutually exclusive and collectively exhaustive division.

In recent years, an increasing number of graph generative models based on machine learning have been proposed. They have demonstrated great performances in several tasks, such as link prediction, molecular property optimization, and network structure optimization (Li et al., 2018; You et al., 2018b; Grover et al., 2018; Luo et al., 2018; You et al., 2018a; Liu et al., 2018; Simonovsky & Komodakis, 2018; Wang et al., 2017; Li et al., 2018) . However, to the best of our knowledge, no proposed model is scalable in all three contexts. For example, DeepGMG (Li et al., 2018) can generate only small graphs, and GraphRNN (You et al., 2018b) cannot consider node/edge labels. Besides, both models have weak compatibility with parallel training, which is key to efficient training on a large dataset.

In this work, we propose the Graph Generative Model with Graph Attention Mechanism (GRAM) for generating graphs that is scalable in all three contexts, especially during training. Given a set of graphs, our model approximates their distribution in an unsupervised manner. To achieve graph scalability, we employ an autoregressive sequential generation process that is flexible to variable nodes and edges, and formulate the likelihood of graphs in a simple manner to simplify the generation process. Besides, we apply two techniques to reduce computational cost: breadth-first search (BFS) and zeroing attention weights in edge estimation. Regarding data scalability, we apply a novel graph attention mechanism that simply extends the attention mechanism used in natural language processing (Vaswani et al., 2017) to graphs. This graph attention mechanism does not include sequentially dependent hidden states as the recurrent neural network (RNN) does, which improves the parallelizability of training significantly. Compared with other graph attention mechanisms (Veličković et al., 2018; Abu-El-Haija et al., 2018; Ishiguro et al., 2019) , ours is architecturally simple, computationally lightweight, and general, i.e., its applicability is not limited to generation tasks. Finally, for label scalability, we formulate the likelihood of graphs assuming multiple node/edge labels. Also, we use graph convolution/attention layers, whose numbers of parameters do not depend directly on the number of labels.

Moreover, we introduce a unified non-domain-specific evaluation metric for generation tasks of node/edge-labeled graphs. Because such a method does not currently exist, prior works relied on domain-specific metrics or visual inspection, which made unified and objective evaluations difficult. Thus, we construct a unified evaluation metric that dispenses with domain-specific knowledge and considers not only the topology but also node/edge labels by combining a graph kernel and Maximum Mean Discrepancy (MMD) (Gretton et al., 2012) . Although a similar statistical test based on MMD via a graph kernel was used for schema matching of protein graphs in Kriegel et al. (2006) , to the best of our knowledge, this work is the first to use as an evaluation metric for graph generation tasks.

Our experiments on synthetic and real-world graphs demonstrated that our models can scale up to handle large graphs and datasets that previous methods had difficulty with; our models demonstrated superior results to those of baseline methods.

To summarize, the contributions of this work are as follows:

• We propose GRAM, a graph generative model that is scalable, especially in training.

• We propose a novel graph attention mechanism that is general and architecturally simple as a key portion of the generative model. • We define scalability in graph generation from three perspectives: number of nodes, data, and labels. • We construct a unified non-domain-specific evaluation metric for node/edge-labeled graph generation tasks by combining a graph kernel and MMD.

2. RELATED WORK:

Although there are several traditional graph generative models (Erdös & Rényi, 1959; Albert & Barabási, 2002; Leskovec et al., 2010; Robins et al., 2007; Airoldi et al., 2009) , we focus here on recent machine learning-based models, which have outperformed traditional models in various tasks.

In terms of their generation process, existing graph generative models can be classified into at least two types: tensor generation models and sequential generation models. Tensor generation models (Simonovsky & Komodakis, 2018; De Cao & Kipf, 2018; Grover et al., 2018) generate a graph by outputting tensors that correspond to the graph. These models are architecturally simple and easy to optimize for small graphs. However, they face difficulty in generating large graphs owing to the non-unique correspondence between a graph and tensors, limitations in the pre-defined maximum number of nodes, and the increasing number of parameters depending on the maximum graph size.

In contrast, sequential generation models, such as DeepGMG (Li et al., 2018) , GraphRNN (You et al., 2018b) , generate graphs by adding nodes and edges one-by-one, which alleviates the above problems and generates larger graphs. To achieve graph scalability, we employ the latter. However, to generate a graph with n nodes and m edges, DeepGMG requires at least O(mn 2 ) operations because of its complex generation process. GraphRNN reduces this time complexity to O(nM ) with a dataset-specific value M by utilizing the BFS. However, it cannot handle node/edge labels, mainly because it omits the feature extraction process, and relies mainly on the information in the hidden states of the RNN. Moreover, these models include sequentially dependent hidden states, which make training parallelization difficult. In contrast, our model employs a graph attention mechanism without sequentially dependent hidden states. This improves the parallelizability of training significantly. Also, by applying two approximation methods, we reduce the complexity to almost a linear order of n while conducting a rich feature extraction. A comparison of our models' and the baselines' complexities is given in Table 2 in Section A.1.

As another division, there are unsupervised learning approaches and reinforcement learning approaches. Given samples of graphs, unsupervised learning models (Li et al., 2018; You et al., 2018b; Simonovsky & Komodakis, 2018; Grover et al., 2018) approximate the distribution of them in an unsupervised manner. Reinforcement learning models (Luo et al., 2018; You et al., 2018a; De Cao & Kipf, 2018; Liu et al., 2018; Li et al., 2018) learn to generate graphs to maximize a given return, such as QED (Bickerton et al., 2012) . Although reinforcement learning approaches have demonstrated promising results on several tasks, such as molecular generation and network architecture optimization, we employ an unsupervised approach; this is because it is considered to be more advantageous when new samples that share certain properties with training samples are required or when the reward functions cannot be designed (e.g., a family of pharmaceutical molecules against a certain disease is known, but the mechanism by which they work is not entirely known).

3. PROPOSED METHOD:

An outline of this section is as follows: In Section 3.1, we first describe notations and define the considered graph generation task. In Section 3.2, we formulate the likelihood of graphs. In Section 3.3, we present our proposed graph attention mechanism, which is the key portion of our model and is used in feature extraction and edge estimation. In Section 3.4, we present our scalable graph generative model, GRAM. We describe two techniques to reduce the computational cost of edge estimation: BFS in Section 3.5.1 and zeroing attention weights in Section 3.5.2. In Section 3.6, we describe the training and propose an evaluation metric.

3.1. NOTATIONS AND PROBLEM DEFINITION:

In this work, we define a graph G = (V, E) as a data structure that consists of a node set V = {v 1 , ..., v n } and an edge set E = {e i,j |i, j ∈ {1, ..., n}}. For simplicity, we focus on undirected graphs. We assume nodes and edges are associated with node/edge labels and denote the number of them as a and b, respectively. For graph representation, we employ a tensor representation. Specifically, given node ordering π, we represent a pair of a graph and node ordering (G, π) as a pair of tensors (X π , A π ). Note that we assume the existence of node ordering in graphs, and π is a permutation function over {1, ..., n}. X π ∈ {0, 1} n×a , whose i-th row is a one-hot vector corresponding to the label of v π(i) , stores information about nodes. A π ∈ {0, 1} n×n×b , whose (i, j)-th element is a one-hot vector corresponding to the label of e π(i),π(j) , stores information about edges. If no edge exists between v π(i) and v π(j) , we replace it with a zero vector. An example is illustrated in Figure 3 in Section A.2. Note that (G, π) and (X π , A π ) are in unique correspondence. Finally, for simplicity, we do not consider self-looping or multiple edges. A possible extension to self-looping edges would involve adding a step to estimate them. For multiple or directed edges, we can prepare additional labels that correspond to them. In the remainder of this paper, for clear notation, we assume π(i) = i and omit the superscript π.

The target graph generation task is as follows: given samples from a distribution of graphs p(G), approximate the distribution (p ≈ p) such that we can derive new samples from it (G ∼ p(G)).

3.2. LIKELIHOOD FORMULATION OF GRAPHS:

To approximate distributions over graphs in an autoregressive manner, we formulate the likelihood of a pair of a graph and node ordering (G, π) and decompose it into a product of conditional probabilities. Because (G, π) uniquely defines (X, A) and vice versa, we have p(G, π) = p(X, A), which is decomposed into a product of conditional probabilities as p(X, A) = p(X 1 , A 1,1 ) n s=2 p(X s |X <s , A <s,<s )

s-1 t=1 p(A t,s |A <t,s , X s , X <s , A <s,<s ) (1) where A <s,<s ∈ R s-1×s-1×b represents a partial tensor A i,j (1 ≤ i, j < s), and other notations follow this. For simplicity, we omit the slice notation for the last dimension of each tensor. In addition, (X <s , A <s,<s ) uniquely defines a subgraph of G, which we denote as G <s . With this formulation, the likelihood of a graph G is defined as marginal, p(G) = π p(G, π) = π p(X, A). Also, we represent (X <s , A <s,<s ) as G <s in the following equations.

During training, given samples from p(G), our model approximates the joint probability p(X, A). More precisely, it approximates p(X, A) by approximating the conditional probabilities p(X s |G <s ) and p(A t,s |A <t,s , X s , G <s ). As for p(X 1 , A 1,1 ), we use a sampling distribution from the training data. Although the choice of π provides room for discussion, we adopt the BFS used in You et al. (2018b) .

On inference, we sequentially sample X s and A t,s (s = 2, ..., n, t = 1, ..., s -1) from the approximated distribution, and we get (X, A) when the EOS is output. This can be viewed as sampling from the approximated distribution (G, π) ∼ p(G, π). In particular, by focusing only on G, we can view it as sampling from the marginal G ∼ p(G).

3.3. GRAPH ATTENTION MECHANISM:

The aim of employing a graph attention mechanism is to efficiently take in the information of distant nodes by attention. Our graph attention mechanism extends the attention mechanism used in natural language processing (Vaswani et al., 2017) to graphs. However, one of the significant differences between graphs and sentences is that we cannot define absolute coordinates in a graph, which makes it difficult to embed positional information in nodes as in Vaswani et al. (2017) . To alleviate this problem, we focus on multi-head attention as in Vaswani et al. (2017) , and we use relative positional information between nodes: we introduce bias terms in projection to subspaces, which are functions of the shortest path length between two nodes. The operation of graph attention is illustrated in Figures 5 and 6 in Section A.4.

Following Vaswani et al. (2017) , we denote matrices into which n query, key, and value vectors are stacked as Q = (q 1 , ...,

q n ) T (∈ R n×d Q ), K = (k 1 , ..., k n ) T (∈ R n×d K ), and V = (v 1 , ..., v n ) T (∈ R n×d V )

, respectively. Note that we use V to represent the value matrix, not node set. Also, we assume that the i-th row of each matrix corresponds to the feature vector of node v i . Note that the operation of graph attention is permutation invariant. Denoting the dimensions of the output vector and the subspace as d O and d S , respectively, the graph attention mechanism is defined as

EQUATION

where H ) where H represents the number of projections to d S -dimensional subspaces. The operation of

head h = GAttention(Q, K, V ) (∈ R n×d S ) (h = 1, ...,

EQUATION

where

o i = n j=1 (c i ) j (W V v j + b V (v i , v j )) (∈ R d S ) (i = 1, ..., n) Each attention weight vector c i is calculated as c i = softmax(s i ) (∈ R n ) (i = 1, ..., n) (4)

where

(s i ) j = d K -1 2 (W Q q i + b Q (v i , v j )) T (W K k j + b K (v i , v j )) (∈ R) (j = 1, ..., n)

The parameters to be learned are four weight matrices -

W Q (∈ R d S ×d Q ), W K (∈ R d S ×d K ), W V (∈ R d S ×d V ), W O (∈ R Hd S ×d O ) -and three bias terms -b Q , b K , b V (∈ R d S )

. We used different parameters for each head.

To consider the geometric relation between two nodes, we used functions of the shortest path length between v i and v j as b Q (v i , v j ), b K (v i , v j ), and b V (v i , v j ). Furthermore, because path length is discrete, we used different weight parameters for each path length. Examples of other possible approaches include using network flow or functional approximation. Specifically, setting b Q = b K = b V = 0 yields the original multi-head attention. As in Vaswani et al. (2017) , we added a twolayer feedforward neural network (FNN), which is applied after the above operations. We denote these operations, including the FNN, as the graph attention mechanism in the following sections. 

) 3EFC (IEC3 EAC ) 3EFC (IEC3 E A A C3B AA -K K -3C K -3C C3B EE E A A (DE 3EAC ( (DE 3EAC X<s < l a t e x i t s h a 1 _ b a s e 6 4 = " b V A n t Z p X a c l o J b Z i F 8 7 Q e G I X y S 4 = " > A A A C h 3 i c h V G 7 S g N B F D 2 u z / i M 2 g g 2 w Z B g F W d V V M Q i Y m O p 0 T w g S t h d J 3 F 1 X + x O A r r 4 A 1 Z 2 o l Y K F m L v D 9 j 4 A x Z + g l g q 2 F h 4 d 7 M g K s Y 7 z M y Z M / f c O c N V H U P 3 B G N P b V J 7 R 2 d X d 0 + s t 6 9 / Y H A o P j x S 8 O y 6 q / G 8 Z h u 2 W 1 I V j x u 6 x f N C F w Y v O S 5 X T N X g R X V / J b g v N r j r 6 b a 1 K Q 4 c v m 0 q N U u v 6 p o i i C q U K v 6 S d 1 S J J 1 m G h Z H 4 D e Q I J B H F m h 2 / w x Z 2 Y E N D H S Y 4 L A j C B h R 4 N M q Q w e A Q t w 2 f O J e Q H t 5 z H K G X t H X K 4 p S h E L t P a 4 1 O 5 Y i 1 6 B z U 9 E K 1 R q 8 Y N F 1 S J p B i j + y G v b I H d s u e 2 c e f t f y w R u D l g H a 1 q e V O Z e h 4 b O P 9 X 5 V J u 8 D u l 6 q l Z 4 E q F k K v O n l 3 Q i b 4 h d b U N w 5 P X z c W c y k / z a 7 Y C / m / Z E / s n n 5 g N d 6 0 6 3 W e u 2 j h R y U v Q X v k n 8 3 4 D Q r T G X k m M 7 0 + m 8 y m o 0 b 1 Y B w T m K R u z C O L V a w h T 9 X 3 c I I z n E s x a U q a k x a a q V J b p B n F t 5 C W P w G I v J H a < / l a t e x i t > A<s,<s < l a t e x i t s h a 1 _ b a s e 6 4 = " U 8 r n K S X M f T f W u W l v W T X X z V w r H z o = " > A A A C i 3 i c h V H L S s N A F D 2 N r 1 p f V T e C m 2 J R X E i Z t I J S u l B E c G m r t c U H J Y n T G k y T k E w L N f g D r g U X o q D g Q t z 7 A 2 7 8 A R d + g r h U c O P C m z Q g K u o d Z u b M m X v u n O G q t q G 7 g r H H i N T R 2 d X d E + 2 N 9 f U P D A 7 F h 0 c 2 X K v h a L y o W Y b l l F X F 5 Y Z u 8 q L Q h c H L t s O V u m r w k r q / 5 N + X m t x x d c t c F y 2 b 7 9 S V m q l X d U 0 R R G 0 u V r y c O 5 P I u Y e V e J K l W B C J n 0 A O Q R J h r F r x W 2 x j F x Y 0 N F A H h

8 R N s p F N y J p X O z y Y X p s J G R T G O C U x T N + a w g B W s o k j V T R z j D O f S g J S R s l K u n S p F Q s 0 o v o S 0 / A E K f Z L m < / l a t e x i t > h G < l a t e x i t s h a 1 _ b a s e 6 4 = " L 9 p x 5 2 B o k j M u I T g F / g z F T R 8 D F R M = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J A w 6 8 i E f C S B p 6 w N f 6 F f a Q o I N f 8 D R x Q E X T R

M j M t Q k Y + b m 5 + Y X H J v x w I r q y u h c L r G 2 V T 6 x o S L U m a r B l V U T C p z F R a s p g l 0 6 p u U E E R Z V o R O 1 n n v N K j h s k 0 9 d j q 6 7 S h C G 2 V t Z g k W E h V 6 6 J i n w 1 O D p v h K E k Q t y L T g P d A F L z K a e F H q M M p a C B B F x S g o I K F W A Y B T H x q w A M B H b k G 2 M g Z i J h 7 T m E A A d R 2 s Y t i h 4 B s B 7 9 t 3 N U 8 V s W 9 M 9 N 0 1 R L + R c b X Q G U E Y u S F 3 J M x e S Y P 5 J V 8 / j n L d m c 4 X v q 4 i h M t 1 Z u h i 6 3 i x 7 8 q B V c L z r 5 V M z 1 b 0 I K U 6 5 W h d 9 1 l n F t I E 3 3 v / G p c T B d i d p z c k j f 0 f 0 N G 5 A l v o P b e p b s 8 L Q x n + B H R y w D j 4 X + H M Q 3 K y Q S / l 0 j m 9 6 O Z u B e U H 7 Z h B 3 Y x j Q P I w B H k o O S m c A l D u O a C H M + l u P S k l f N 5 m k 3 4 U V z 2 C 5 Z l k s A = < / l a t e x i t > H v < l a t e x i t s h a 1 _ b a s e 6 4 = " a i 4 O Z 6 U G z G H j J k n A F / s U R M o d L + Y = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J C y M f M h H A k j a + s C G f q V 9 N E H C H 3 B 0 c c B F E w f j 7 h 9 w 8 Q 8 4 8 B O M I y Y u D t 6 W J k a J e J v 2 n X f e P b f n 5 Y i G I l u M k L G P W 1 h c W l 7 x r w a C a + s b o f D m V s X S e 6 Z E y 5 K u 6 G Z N F C y q y B o t M 5 k p t G a Y V F B F h V b F b t Y 5 r 9 r U t G R d O 2 Z 9 g z Z V o a P J b V k S G F K 1 h q g O c s M T u x W O k g R x K z I L e A 9 E w a u 8 H n 6 E B p y C D h L 0 Q A U K G j D E C g h g 4 V M H H g g Y y D V h g J y J S

M k s p Q D h X N b 4 R g 7 1 B C c L T g Q Z U = " > A A A C h H i c h V G 7 S g N B F D 2 u G t 8 m a i P Y i C H B Q s L E B 4 q F B G w s T W I 0 E E P Y X S d x c F / s T g I a 8 g O C r R Z W C h Z i 7 w / Y + A M W f o J Y K t h Y e H e z I B q M d 5 i Z M 2 f u u X O G q z m G 8 C R j z z 1 K b 1 9 / Z G B w a H h k d G w 8 G p u Y 3 P X s u q v z g m 4 b t l v U V I 8 b w u I F K a T B i 4 7 L V V M z + J 5 2 t O n f 7 z W 4 6 w n b 2 p H H D i + b a s 0 S V a G r k q h 8 s e J V Y n G W Y k H M d o J 0 C O I I Y 9 u O 3 W M f B 7 C h o w 4 T H B Y k Y Q M q P B o l p M H g E F d G k z i X k A j u O V o Y J m 2 d s j h l q M Q e 0 V q j U y l k L T r 7 N b 1 A r d M r B k 2 X l L N I s C d 2 y 9 7 Y I 7 t j L + z z z 1 r N o I b v 5 Z h 2

r a 3 l T i V 6 O p 3 / + F d l 0 i 5 x + K 3 q 6 l m i i r X A q y D v T s D 4 v 9 D b + s b J x V t + P Z d o J t k 1 e y X / V + y Z P d A P r M a 7 f p P l u c s u f j T y 0 q L 2 p H 8 3 o x P s L q b S S 6 n F 7

H I 8 k w w b N Y g Z z G G e u r G K D L a w j Q J V r + E M 5 7 h Q I s q C s q S s t F O V n l A z h R + h b H w B h 2 q Q i A = = < / l a t e x i t > At,s < l a t e x i t s h a 1 _ b a s e 6 4 = " G y 3 t 6 p x 2 u p N F B u G y j X Q U G h 2 5 y l s = " > A A A C a 3 i c h V G 7 S g N B F D 1 Z 3 / G R q I 2 o R T A k W E i Y V U G x U m w s 4 y M a U A m 7 6 y Q O 2 R e 7 k 4 A u / o C l j U V s F E T E z 7 D x B y z 8 B B E r B R s L b z Y L o q L e Z X b O n L n n z p k 7 u m s K X z L 2 E F P a 2 j s 6 u 7 p 7 4 r 1 9 / Q O J 5 O D Q p u / U P I M X D M d 0 v K K u + d w U N i 9 I I U 1 e d D 2 u W b r J t / T q c n N / q 8 4 9 X z j 2 h j x w + a 6 l V W x R F o Y m i S o u l Q I 5 l f K P S s k 0 y 7 E w U j + B G o E 0 o s g 7 y S v s Y A 8 O D N R g g c O G J G x C g 0 / f N l Q w u M T t I i D O I y T C f Y 4 j x E l b o y x O G R q x V f p X a L U d s T a t m z X 9 U G 3 Q K S Y N j 5 Q p Z N g 9 u 2 Y v 7 I 7 d s E f 2 / m u t I K z R 9 H J A s 9 7 S c r e U O B 5 Z f / t X Z d E s s f + p + t O z R B n z o V d B 3 t 2 Q a d 7 C a O n r h 6 c v 6 w t r m S D L L t g T + T 9 n D + y W b m D X X 4 3 L V b 7 W Q J w e Q P 3 e 7 p 9 g c z q n z u S m V 2 f T i 9 n o K b o x h g l M U r / n s I g V 5 F E I + 3 y C B s 5 i z 8 q w M q q M t 1 K V W K Q Z x p d Q M h + k w Y x 5 < / l a t e x i t > (t = 1, ..., s 1)

< l a t e x i t s h a 1 _ b a s e 6 4 = " n q 6 L 0 h s {A⌧,s|⌧ = 1, ..., t 1}

X R W 7 Y o / S P 3 r Q H Q + O B T K k = " > A A A C d n i c h V H L S s N A F D 2 N 7 / q q u h E E C Z b 6 A A 0 3 K i i C I L h x 6 a s q q J Q k T j W Y J i G Z V r T 4 A / 6 A C 3 G h o C J + h h t / w I W f I C 4 V d O H C 2 z Q g K u o d Z u b M m X v u n J k x f c c O J d F D Q q m p r a t v a G x K N r e 0 t r W n O j p X Q q 8 Y W C J r e Y 4 X r J l G K B z b F V l p S 0 e s + Y E w C q Y j V s 3 d 2 c r + a k k E o e 2 5 y 3 L f F 5 s F Y 9 u 1 8 7 Z l S K Z y q Y 5 B q U 6 r + r C q a d q w G o 7 o Q 7 l U m j S K Q v 0 J 9 B i k E c e 8 l 7 r C B r b g w U I R B Q i 4 k I w d G A i 5 r U M H w W d u E 2 X m A k Z 2 t C 9 w i C R

< l a t e x i t s h a 1 _ b a s e 6 4 = " W t y D I O T f 7 g g X V Z X 5 p 6 + 4 3.4 GRAM: SCALABLE GENERATIVE MODELS FOR GRAPHS GRAM approximates a distribution over graphs in an autoregressive manner. It utilizes the graph attention mechanism to improve the parallelizability of training. The s-th step of the generation process is illustrated in Figure 1 ; a larger and more detailed version is given in Figure 4 in Section A.3. A detailed analysis of computational complexity is included in Section A.1.

x 3 u T v D c = " > A A A C i X i c h V F N L 8 R A G H 7 U 9 / p a X C Q u E 4 s 4 r G a K h E g k x M X R 1 y K x s m l r l k a 3 b d r Z T a j 9 A / 6 A g x O J i L i 4 c n X x B x z 8 B H E k c X H w t t t E E L y T m X n m m f d 5 5 5 k Z w 7 O t Q H L + W K f U N z Q 2 N b e 0 p t r a O z q 7 0 t 0 9 a 4 F b 9 k 2 R M 1 3 b 9 T c M P R C 2 5 Y i c t K Q t N j x f 6 C X D F u v G 3 n y 0 v 1 4 R f m C 5 z q r c 9 8 R W S d 9 x r K J l 6 p K o Q n o w H 8 4 V w r z U y 1 k W V N k h i y C b Y V q W q a q a Z X J U y 1 c L 6 Q x X e R z s J 9 A S k E E S i 2 7 6 A n l s w 4 W J M k o Q c C A J 2 9 A R U N u E B g 6 P u C 2 E x P m E r H h f o I o U a c u U J S h D J 3 a P x h 1 a b S a s Q + u o Z h C r T T r F p u 6 T k m G I P / B L / s L v + R V / 4 u + / 1 g r j G p G X f Z q N m l Z 4 h a 6 j v p W 3 f 1 U l m i V 2 P 1 V / e p Y o Y i r 2 a p F 3 L 2 a i W 5 g 1 f e X g + G V l e n k o H O Z n / J n 8 n / J H f k c 3 c C q v 5 v m S W D 5 B i j 5 A + / 7 c P 8 H a m K q N q 2 N L E 5 n Z 4 e Q r W t C P A Y z Q e 0 9 i F g t Y R I 7 O P c I 1 b n C r t C m a M q V M 1 1 K V u k T T i y + h z H 8 A s / u U q Q = = < / l a t e x i t >

p V m K O w = " > A A A C l H i c h V H L S s N A F D 3 G 9 7 N V Q Q Q 3 Y q n U h W W i g i I u B B F c i V p r B a 0 l i a M O 5 k W S V j T 0 B / w B F + J C Q U X c + w N u / A E X / Q R x q e D G h T d p Q L R Y 7 z A z Z 8 7 c c + c M V 7 V 1 4 X q M V R q k x q b m l t a 2 9 o 7 O r u 6 e W L y 3 b 8 O 1 i o 7 G s 5 q l W 8 6 m q r h c F y b P e s L T + a b t c M V Q d Z 5 T D x e C + 1 y J O 6 6 w z H X v 2 O Z 5 Q 9 k 3 x Z 7 Q F I + o Q r x 3 W z X 8 g 3 J B 7 P i l l D 4 u j 5 U L 8 Q R L s z C G a 4 E c g Q S i W L H i D 9 j G L i x o K M I A h w m P s A 4 F L o 0 t y G C w i c v D J 8 4 h J M J 7 j j I 6 S F u k L E 4 Z C r G H t O 7 T a S t i T T o H N d 1 Q r d E r O k 2 H l M N I s m d 2 x 9 7 Y E 7 t n L + z z z 1 p + W C P w c k y 7 W t V y u x A 7 H c x 8 / K s y a P d w 8 K 2 q 6 9 n D H m Z C r 4 K 8 2 y E T / E K r 6 k s n Z 2 + Z 2 b W k P 8 q u 2 C v 5 v 2 Q V 9 k g / M E v v 2 v U q X z u v 4 0 c l L 0 F 7 5 N / N q A U b E 2 l 5 M j 2 x O p W Y H 4 0 a 1 Y Y h j C B F 3 Z j G P J a w g i x V P 8 I F b n A r D U h z 0 o K 0 W E 2 V G i J N P 3 6 E t P w F D W y W V Q = = < / l a t e x i t > h v(l) i < l a t e x i t s h a 1 _ b a s e 6 4 = " I t Q / h J U N w v 1 J k B m X q a U f 9 K i L E O U = " > A A A C k n i c h V G 7 T g J B F L 2 s L 8 Q H + C h M b I g E g w 0 Z 0 E R D h a G x s O A h j w S Q 7 K 4 D T N h X d h c S 3 P A D / o A F l U Y K Y + 8 P 2 P g D F n y C s c T E x s K 7 y y Z G i X g 3 u 3 P m z D 1 3 z + Q I m s Q M k 5 C h h 5 u Z n Z t f 8 C 7 6 l p Z X V v 2 B t f W C o b Z 1 k e Z F V V L 1 k s A b V G I K z Z v M l G h J 0 y k v C x I t C q 2 U f V 7 s U N 1 g q n J m d j V a l f m G w u p M 5 E 2 k a g F / R Z C t Z q / G z q 1 O R N r r 1 Q I h E i V O B S d B z A U h c C u t B h 6 h A h e g g g h t k I G C A i Z i C X g w 8 C l D D A h o y F X B Q k 5 H x J x z C j 3 w o b a N X R Q 7 e G R b + G 3 g r u y y C u 7 t m Y a j F v E v E r 4 6 K o M Q J i / k n o z I M 3 k g r + T z z 1 m W M 8 P 2 0 s V V G G u p V v N f b e U + / l X J u J r Q / F Z N 9 W x C H Y 4 c

3.4.1. MODEL OVERVIEW:

In the following sections, we focus on the s-th step, i.e., the generation of v s and {e 1,s , ..., e s-1,s }.

The architecture of GRAM consists of three networks: feature extractor, node estimator, and edge estimator. The feature extractor calculates node feature vectors and a graph feature vector by summing them. The node estimator predicts the label of the new node v s . The edge estimator predicts the labels of new edges {e 1,s , ..., e s-1,s } between previously generated nodes {v 1 , ..., v s-1 } and the new node v s . In other words, the node estimator approximates p(X s |G <s ), and the edge estimator approximates p(A t,s |A <t,s , X s , G <s ) in Equation 1.

3.4.2. FEATURE EXTRACTOR:

Given a pair (X <s , A <s,<s ), the feature extractor calculates s -1 node feature vectors H v = (h v 1 , ..., h v s-1 ) T and a graph feature vector h G of the corresponding subgraph G <s . Here, h v i denotes the feature vector of node v i , and we use h v(l) i to represent the output vector of the l-th block. This consists of L feature extraction blocks and a graph pooling layer. In this work, we used L = 3.

A feature extraction block is composed of a graph convolution layer and a graph attention layer stacked in parallel, as illustrated in Figure 2 . We aim to extract local information by graph convolution layers and global information by graph attention layers. Although there are various types of graph convolutions, we employed the one used in Johnson et al. (2018) .1 Roughly speaking, this convolutes the features of neighboring nodes and edges into each node and edge in a graph. A graph attention layer operates self-attention, where query/key/value vectors are all node feature vectors. To reduce computational cost, we restricted the range of attention to path length r. Also, to exploit low-level features, we stacked degree and clustering coefficients, which are non-domain-specific statistics in graphs, into each input node vector. Calculation of these graph statistics and BFS is required only once before training and is relatively fast compared with training time.

The graph pooling layer computes a graph feature vector h G by summing all node feature vectors in the subgraph. To improve its expressive power in aggregation, we used a gating network as in Li et al. (2018) . Specifically, the operation in the graph pooling layer is defined as

h G = s-1 i=1 σ(g pool (h v i ))h v i (5)

where g pool is a two-layer FNN, and σ is a sigmoid function.

3.4.3. NODE ESTIMATOR:

The node estimator predicts the label of new node v s . More specifically, it predicts X s from h G as

X s = softmax(g N E (h G )) (∈ R a+1 ) (6)

where g N E is a three-layer FNN, and the output dimension, including the EOS, is a + 1. We terminate the generation process when the EOS is output.

3.4.4. EDGE ESTIMATOR:

The edge estimator predicts the labels of the new edges {e 1,s , ..., e s-1,s } between previously generated nodes {v 1 , ..., v s-1 } and the new node v s . More precisely, it predicts A t,s (t = 1, ..., s -1) from h v t , h G , h v s and previously predicted edge labels in this step as

A t,s = softmax(g EE (h v t , h G , h v s , h e <t )) (∈ R b+1 ) (t = 1, ..., s -1) (7)

where h v s is the embedded vector of the predicted label of v s , i.e., X s . The vector h e <t is calculated by a source-target attention in which the query vector is Concat(h v t , h v s ) and the key/value vectors are {Concat(h v τ , h v s , h e τ,s )|τ = 1, ..., t -1}, where h e τ,s is an embedded vector of the predicted label of e τ,s , i.e., A τ,s . Thereby, we aim to express the dependency on A <t,s in Equation 1. The operation is illustrated in Figure 6 in Section A.4. We use a three-layer FNN as g EE , where the output dimension is b + 1, including the "no edge" label. When the "no edge" label is output, we do not add an edge and we set A t,s = 0.

3.5. REDUCING COMPUTATIONAL COMPLEXITY IN EDGE ESTIMATION:

To generate a graph with n nodes, the edge estimation process requires O(n) operations for one edge, resulting in O(n 2 ) operations for one step and O(n 3 ) operations in total. This is a significant obstacle to achieving graph scalability. Here, we present two methods to reduce complexity in edge estimation: BFS and zeroing attention weights; these can be combined independently.

3.5.1. COMPLEXITY REDUCTION VIA BREADTH FRIST SEARCH:

As in You et al. (2018b) , we utilize the BFS node ordering, but our implementation gives a stricter upper bound. More precisely, when estimating new edge e t,s (t = 1, ..., s -1), nodes that can be connected to the new node v s are restricted to "frontier nodes"

V f = {v τ | min({i|v i is connected to v s-1 }) ≤ τ ≤ s -1} under π = BFS .

With this property, we need only consider V f instead of the whole {v 1 , ..., v s-1 } when estimating e t,s . This reduces the complexity of edge estimation to O(nβ 2 ), where β = |V f |. A proof and example are included in Section A.5. Finally, we denote this variant as GRAM-B.

3.5.2. COMPLEXITY REDUCTION VIA ATTENTION WEIGHTS ZEROING:

As another method, we use an approximation inspired by empirical observation. Specifically, our inspection of each attention weight during estimation of new edge e t,s (t = 1, ..., s-1) revealed that the nodes predicted to have no connection to v s (i.e., V noedge = {v τ |A τ,s = 0, τ = 1, ..., t -1}) have near-zero weights, while the nodes predicted to have connection (i.e., V haveedge = {v τ |A τ,s = 0, τ = 1, ..., t -1}) have larger weights. This suggests that among {v 1 , ..., v t-1 }, V haveedge are important to predict the new edge e t,s , while V noedge are not. Hence, we deterministically set the weights of the latter to zero, which means we do not consider them in graph attention. With this approximation, the complexity is reduced to O(n 2 α), where α = |V haveedge |. In addition, because α ≤ deg(v s ) holds, we can assume that α n when deg(v s ) n, which is often the case in many real-world graphs. A more detailed discussion and an example are included in Section A.6. Finally, we denote this variant as GRAM-A and the combination of the two as GRAM-AB, which has complexity O(nαβ).

3.6. TRAINING AND EVALUATION:

The loss function is the negative logarithm of Equation 1, and the training is done in the usual autoregressive manner. In particular, for one graph, forward/backward propagation of n node estimations and at most n(n-1)/2 edge estimations can be processed parallelly (i.e., in O(1) sequential operations) by using ground-truth labels and proper masking.

To evaluate the quality of generation, evaluation metrics based on MMD with graph statistics were used in You et al. (2018b) . However, these metrics cannot consider node/edge labels, and it is difficult to determine which one is important or not. Therefore, we construct a unified evaluation metric GK-MMD that can consider not only topology but also node/edge labels by combining a graph kernel and MMD.

MMD is a test statistic to determine whether two sets of samples from the distribution p and q are derived from the same distribution (i.e., whether p = q). When its function class F is a unit ball in a reproducing kernel Hilbert space (RKHS) H, we can derive the squared MMD as

EQUATION

where k(•, •) is the associated kernel function (Gretton et al., 2012) .

Graph kernels are kernel functions over graphs, and we used the neighborhood subgraph pairwise distance kernel (NSPDK) (Costa & Grave, 2010) , which measures the similarity of two graphs by matching pairs of subgraphs with different radii and distances. Because NSPDK is a positive-definite kernel (Costa & Grave, 2010) , it follows that it defines a unique RKHS H (Aronszajn, 1950) . This allows us to calculate the squared MMD using Equation 8.

Because NSPDK considers low/high-level topological features and node/edge labels, GK-MMD can be used as a unified evaluation metric for node/edge-labeled graph generation tasks.

4. EXPERIMENTS:

We performed experiments on four types of synthetic graphs and three types of real-world graphs with various topologies, graph sizes, dataset sizes, and numbers of node/edge labels. We evaluated the quality of generation and the actual computational cost required.

As synthetic graphs, we used four types of random graphs: grid, lobster, community (Fortunato, 2010) , and Barabási-Albert (B-A) (Barabási & Albert, 1999) . We generated 700 graphs with numbers of nodes in the range 50 ≤ |V | ≤ 100. We split them into training/test/validation data at 500:100:100. To make the problem more realistic, we deterministically labeled nodes and edges according to their properties, such as degree or distance from backbone. Detailed configurations, including model-specific parameters and node/edge labeling, are described in Section A.7.

We used three types of real-world graphs: molecular, ego, and protein. For the molecular graphs, we used 250k samples from the ZINC database (Sterling & Irwin, 2015) provided by Kusner et al. (2017) . The ego graphs are ego networks from the Citeseer networks (Sen et al., 2008) . The protein graphs represent protein structures with amino acids as nodes (Dobson & Doig, 2003) . For the ego and protein datasets, we used data provided by You et al. (2018b) .

We compared our models with DeepGMG (Li et al., 2018) , GraphRNN, and GraphRNN-S (You et al., 2018b) as recent deep learning-based baselines. We modified the GraphRNN and GraphRNN-S models so that they can output multiple node/edge labels. Because we target the unsupervised learning graph generation task and most of the datasets we used are node/edge-labeled, we did not conduct a comparison with reinforcement learning-based methods or traditional models, which are incapable of handling node/edge labels, except for GraphRNN and its variant.

To evaluate the quality of generation, we calculated squared GK-MMD score between generated graphs and test graphs. We also used the squared MMD score of the three types of graph statistics used in You et al. (2018b) : distributions of degree, clustering coefficient, and orbit count; however, these metrics do not consider node/edge labels. A lower MMD score indicates a better quality of approximation in terms of the given statistic. For the molecular graphs, we generated 10k samples and calculated the ratios of generated graphs that are valid as molecules (valid [%]), unique samples (unique [%]), and novel samples, i.e., valid, unique, and unseen in the training data (novel [%]). We also reported training time [hour] .

The results are listed in Table 1 . We did not train DeepGMG on the ego, protein and molecular datasets due to its impractical training time (estimated to take over 90 hours). Instead, for the molecular dataset, we used generated graphs provided by the author for evaluation. Although Deep-GMG achieved a high valid/unique score and low GK-MMD score in the molecular dataset, it failed for larger graphs. This is likely because its feature extraction method is based only on graph convolution, which gives only local information, so it works well only on small graphs, such as those of molecules. Moreover, its training is slow due to its sequentially dependent hidden states.

GraphRNN and its variant achieved low topological MMD scores for simple topology graphs like grid. However, their performances were poor on other graphs with more complex topologies or rules. This is likely because they do not calculate node/edge features, which limited their expressive power. In other words, the feature extraction process is inevitable for the generation of complex graphs.

In contrast, our models achieved overall lower MMD scores on most of the datasets, which means that the distance between the approximated distribution and the test set is relatively small in terms of topological and node/edge label features. Also, from the results on the molecular dataset, we can see that the generation is diverse while capturing the strict valence rule via unsupervised learning. This is likely due to the bias term of graph attention in edge estimation: it enables models to control the valence and type of rings. In terms of training time, there is a significant acceleration compared with the baselines. This is mainly owing to the graph attention mechanism, which reduces the number of sequential operations during training to almost constant and enables efficient parallelized training.

Besides, we can observe the impact of the two computational reduction techniques on the actual computational time. They were also more efficient in terms of memory usage, requiring less than half that of the original model. Surprisingly, although there is generally some trade-off between training speed and performance, GRAM-B performed better than the original model on the grid and ego datasets, and GRAM-A performed better on the molecular dataset. This is likely because each approximated model has its own strong topology for which both performance is boosted and computational cost is reduced. On average, the proposed models performed better on large graphs. More detailed discussions are included in Sections A.5 and A.6.

From the above results, we can see the scalability of our models for large graphs and datasets and multiple node/edge labels, which the baseline methods have difficulty in handling. Note that although our approximated models have some trade-off between performance and training speed, they still achieved superior or competitive results over the baselines in most cases. Also, we found an interesting correlation between GK-MMD score and topological MMD scores or visual similarity, which supports the validity of this metric. The detailed setting of the experiments, additional results, visualization, and an ablation study are included in Section A.7.

5. CONCLUSION:

In this work, we tackled the problem of scalability as it is one of the most important challenges in graph generation tasks. We first defined scalability from three perspectives, and then we proposed a scalable graph generative model named GRAM along with some variants. Also, we proposed a novel graph attention mechanism as a key portion of the model and constructed GK-MMD as a unified evaluation metric for node/edge-labeled graph generation tasks. In an experiment using synthetic and real-world graphs, we verified the scalability and superior performances of our models.

A APPENDIX A.1 COMPLEXITY ANALYSIS:

In this section, we compare the computational complexity of the training of our models with that of existing models. Following Vaswani et al. (2017) , we consider two factors: total computational complexity and minimum sequential operations with parallelization. Note that we assume all matrixvector products can be computed in constant time. Table 2 summarizes the results.

To generate a graph with n nodes and m edges, DeepGMG (Li et al., 2018) requires at least O(mn 2 ) operations. Because the initialization of the state of the new node depends on the state in the previous step, DeepGMG's minimum required sequential operations is O(n 2 ). On the other hand, GraphRNN (You et al., 2018b) requires O(nM ) operations with a dataset-specific constant value M , utilizing the properties of the BFS and relying mainly on the hidden states of the RNN. However, its minimum number of sequential operations is O(n + M ) because of the sequential dependency of the hidden states of the RNN; moreover, it cannot generate node/edge-labeled graphs.

Next, we evaluate GRAM and its variants. We denote the average number of nodes/edges within distance r of one node as N r /M r and reuse the α and β defined in Section 3.5.

In one step, the feature extractor requires O(m + nN r ) operations, considering a graph convolution layer requires O(m), and a graph attention layer requires O(nN r ). However, comparing the node features in G <s with those in G <s+1 (= G s ∪ v s ∪ {e 1,s , ..., e s-1,s }), only nodes within distance rL of v s change their features. Utilizing this property, we conduct feature extraction only for rLneighboring nodes of the previously added node and reuse features for the other nodes, by which the number of feature extraction operations is reduced to O(n(M rL + N rL N r )).

Also, the node estimator requires O(n) operations in total. In edge estimation, GRAM requires

O(n 3 ) operations, GRAM-B requires O(nβ 2 ), GRAM-A requires O(n 2 α), and GRAM-AB re- quires O(nαβ).

Therefore, the total complexity of GRAM is

O(n 3 + n(M rL + N rL N r )), that of GRAM-B is O(nβ 2 +n(M rL +N rL N r )), that of GRAM-A is O(n 2 α+n(M rL +N rL N r ))

, and that of GRAM-AB is O(nαβ+n(M rL +N rL N r )). Note that all the estimation operations of the node estimator and the edge estimator can be parallelized in training because our model has no sequentially dependent hidden states like the RNN does.

From the above analysis, we can see that our models require fewer operations than DeepGMG when N r n holds, which is the often case, while keeping rich feature extraction. In addition, assuming N rL and M rL are nearly constant and sufficiently smaller than n and m, respectively, the total complexities of GRAM-B and GRAM-AB can be regarded as almost linear in n, which is competitive with GraphRNN, but ours keep the feature extraction. More importantly, all estimation operations can be parallelized, which facilitates training using multiple computing nodes. Therefore, we can expect graph scalability and data scalability of our models. We also expect label scalability because our models are flexible to a variable number of labels by modifying only the dimensions of the input and output layers. 

O(mn 2 ) O(n 2 ) GraphRNN O(nM ) O(n + M ) GRAM O(n 3 + n(M rL + N rL N r )) O(1) GRAM-B O(nβ 2 + n(M rL + N rL N r )) O(1) GRAM-A O(n 2 α + n(M rL + N rL N r )) O(1) GRAM-AB O(nαβ + n(M rL + N rL N r ))

O(1)

A.2 EXAMPLE OF TENSOR REPRESENTATION:

An example of tensor representation is illustrated in Figure 3 . 4 m 3 a d 9 5 5 9 9 y e l y P q 

2EAS QE 1WSQACSOQ 2EAS QE 1WSQACSION .LOCK 3QAP OOLING 6 8ODE X <s < l a t e x i t s h a 1 _ b a s e 6 4 = " b V A n t Z p X a c l o J b Z i F 8 7 Q e G I X y S 4 = " > A A A C h 3 i c h V G 7 S g N B F D 2 u z / i M 2 g g 2 w Z B g F W d V V M Q i Y m O p 0 T w g S t h d J 3 F 1 X + x O A r r 4 A 1 Z 2 o l Y K F m L v D 9 j 4 A x Z + g l g q 2 F h 4 d 7 M g K s Y 7 z M y Z M / f c O c N V H U P 3 B G N P b V J 7 R 2 d X d 0 + s t 6 9 / Y H A o P j x S 8 O y 6 q / G 8 Z h u 2 W 1 I V j x u 6 x f N C F w Y v O S 5 X T N X g R X V / J b g v N r j r 6 b a 1 K Q 4 c v m 0 q N U u v 6 p o i i C q U K v 6 S d 1 S J J 1 m G h Z H 4 D e Q I J B H F m h 2 / w x Z 2 Y E N D H S Y 4 L A j C B h R 4 N M q Q w e A Q t w 2 f O J e Q H t 5 z H K G X t H X K 4 p S h E L t P a 4 1 O 5 Y i 1 6 B z U 9 E K 1 R q 8 Y N F 1 S J p B i j + y G v b I H d s u e 2 c e f t f y w R u D l g H a 1 q e V O Z e h 4 b O P 9 X 5 V J u 8 D u l 6 q l Z 4 E q F k K v O n l 3 Q i b 4 h d b U N w 5 P X z c W c y k / z a 7 Y C / m / Z E / s n n 5 g N d 6 0 6 3 W e u 2 j h R y U v Q X v k n 8 3 4 D Q r T G X k m M 7 0 + m 8 y m o 0 b 1 Y B w T m K R u z C O L V a w h T 9 X 3 c I I z n E s x a U q a k x a a q V J b p B n F t 5 C W P w G I v J H a < / l a t e x i t > A <s,<s < l a t e x i t s h a 1 _ b a s e 6 4 = " U 8 r n K S X M f T f W u W l v W T X X z V w r H z o = " > A A A C i 3 i c h V H L S s N A F D 2 N r 1 p f V T e C m 2 J R X E i Z t I J S u l B E c G m r t c U H J Y n T G k y T k E w L N f g D r g U X o q D g Q t z 7 A 2 7 8 A R d + g r h U c O P C m z Q g K u o d Z u b M m X v u n O G q t q G 7 g r H H i N T R 2 d X d E + 2 N 9 f U P D A 7 F h 0 c 2 X K v h a L y o W Y b l l F X F 5 Y Z u 8 q L Q h c H L t s O V u m r w k r q / 5 N + X m t x x d c t c F y 2 b 7 9 S V m q l X d U 0 R R G 0 u V r y c O 5 P I u Y e V e J K l W B C J n 0 A O Q R J h r F r x W 2 x j F x Y 0 N F A H h w l B 2 I A C l 8 Y W Z D D Y x O 3 A I 8 4 h p A f 3 H I e I k b Z B W Z w y F G L 3 a a 3 R a S t k T T r 7 N d 1 A r d E r B k 2 H l A l M s g d 2 z V 7 Y P b t h T + z 9 1 1 p e U M P 3 0 q J d b W u 5 X R k 6 G l t 7 + 1 d V p 1 1 g 7 1 P 1 p 2 e B K u Y D r z p 5 t w P G / 4 X W 1 j c P T l 7 W s o V J b 4 p d s m f y f 8 E e 2 R 3 9 w G y + a l d 5 X j j 9 w 4 9 K X v z 2 y N + b 8 R N s p F N y J p X O z y Y X p s J G R T G O C U x T N + a w g B W s o k j V T R z j D O f S g J S R s l K u n S p F Q s 0 o v o S 0 / A E K f Z L m < / l a t e x i t > h G < l a t e x i t s h a 1 _ b a s e 6 4 = " L 9 p x 5 2 B o k j M u I T g F / g z F T R 8 D F R M = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J A w 6 8 i E f C S B p 6 w N f 6 F f a Q o I N f 8 D R x Q E X T R y M u 3 / A x T / g w E 8 w j p i 4 O H h b m h g l

M j M t Q k Y + b m 5 + Y X H J v x w I r q y u h c L r G 2 V T 6 x o S L U m a r B l V U T C p z F R a s p g l 0 6 p u U E E R Z V o R O 1 n n v N K j h s k 0 9 d j q 6 7 S h C G 2 V t Z g k W E h V 6 6 J i n w 1 O D p v h K E k Q t y L T g P d A F L z K a e F H q M M p a C B B F x S g o I K F W A Y B T H x q w A M B H b k G 2 M g Z i J h 7 T m E A A d R 2 s Y t i h 4 B s B 7 9 t 3 N U 8 V s W 9 M 9 N 0 1 R L + R c b X Q G U E Y u S F 3 J M x e S Y P 5 J V 8 / j n L d m c 4 X v q 4 i h M t 1 Z u h i 6 3 i x 7 8 q B V c L z r 5 V M z 1 b 0 I K U 6 5 W h d 9 1 l n F t I E 3 3 v / G p c T B d i d p z c k j f 0 f 0 N G 5 A l v o P b e p b s 8 L Q x n + B H R y w D j 4 X + H M Q 3 K y Q S / l 0 j m 9 6 O Z u B e U H 7 Z h B 3 Y x j Q P I w B H k o O S m c A l D u O a C H M + l u P S k l f N 5 m k 3 4 U V z 2 C 5 Z l k s A = < / l a t e x i t > H v < l a t e x i t s h a 1 _ b a s e 6 4 = " a i 4 O Z 6 U G z G H j J k n A F / s U R M o d L + Y = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J C y M f M h H A k j a + s C G f q V 9 N E H C H 3 B 0 c c B F E w f j 7 h 9 w 8 Q 8 4 8 B O M I y Y u D t 6 W J k a J e J v 2 n X f e P b f n 5 Y i G I l u M k L G P W 1 h c W l 7 x r w a C a + s b o f D m V s X S e 6 Z E y 5 K u 6 G Z N F C y q y B o t M 5 k p t G a Y V F B F h V b F b t Y 5 r 9 r U t G R d O 2 Z 9 g z Z V o a P J b V k S G F K 1 h q g O c s M T u x W O k g R x K z I L e A 9 E w a u 8 H n 6 E B p y C D h L 0 Q A U K G j D E C g h g 4 V M H H g g Y y D V h g J y J S H b P K Q w h g N o e d l H s E J D t 4 r e D u 7 r H a r h 3 Z l q u W s K / K P i a q I x A j L y Q e z I h z + S B v J L P P 2 c N 3 B m O l z 6 u 4 l R L j V b o Y q f 0 8 a 9 K x Z X B 2 b d q r m c G b U i 5 X m X 0 b r i M c w t p q r f P r y a l d D E 2 i J N b 8 o b + b 8 i Y P O E N N P t d u i v Q 4 m i O H x G 9 D D E e / n c Y s 6 C S T P A H i W T h M J q J e 0 H 5 Y R f 2 Y B / T O I I M 5 C A P Z T e F S x j B N R f k e C 7 F p a e t n M / T b M O P 4 r J f t c e S z w = = < / l a t e x i t > v 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 8 U q v b K L 7 a S 3 q W s z 7 a W I j x Z 7 V c Q = " > A A A C h H i c h V G 7 S g N B F D 1 Z X / E d t R F s g i F i I W E 2 U R Q L E W w s 8 z B R i C H s r m M c 3 O w u u 5 O A h v y A Y K u F l Y K F 2 P s D N v 6 A R T 5 B L C P Y W H i z W R A V 4 x 1 m 5 s y Z e + 6 c 4 e q O K T z J W C u k 9 P U P D A 6 F h 0 d G x 8 Y n J i N T 0 w X P r r k G z x u 2 a b t 7 u u Z x U 1 g 8 L 4 U 0 + Z 7 j c q 2 q m 3 x X P 9 7 q 3 O / W u e s J 2 9 q R J w 4 v V b W K J Q 6 F o U m i c v W y W o 7 E W I L 5 E f 0 N 1 A D E E E T a j j x g H w e w Y a C G K j g s S M I m N H g 0 i l D B 4 B B X Q o M 4 l 5 D w 7 z m a G C F t j b I 4 Z W j E H t N a o V M x Y C 0 6 d 2 p 6 v t q g V 0 y a L i m j i L N n d s f a 7 I n d s x f 2 8 W e t h l + j 4 + W E d r 2 r 5 U 5 5 8 m w 2 9 / 6 v q k q 7 x N G X q q d n i U O s + V 4 F e X d 8 p v M L o 6 u v n 1 6 2 c + v Z e G O B 3 b B X 8 n / N W u y R f m D V 3 4 z b D M 9 e 9 f C j k 5 c m t U f 9 2 Y z f o J B M q K l E M r M c 2 1 w I G h X G H O a x S N 1 Y x S a 2 k U a e q l d w j g t c K o P K k p J S V r q p S i j Q z O B b K B u f O 2 6 Q Z A = = < / l a t e x i t > v 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " s K z 2 0 e D f d w g / n X s h h p Q J v j 1 I / u 8 = " > A A A C h H i c h V G 7 S g N B F D 1 Z X / G Z q I 1 g E w w R C w m T R F E s R L C x z M N E I Y a w u 4 5 x y G Z 3 2 Z 0 E N O Q H B F s t r B Q s x N 4 f s P E H L P I J Y h n B x s K b z Y K o G O 8 w M 2 f O 3 H P n D F e z D e F K x t o B Z W B w a H g k O D o 2 P j E 5 F Q p P z x R c q + 7 o P K 9 b h u X s a 6 r L D W H y v B T S 4 P u 2 w 9 W a Z v A 9 r b r d v d 9 r c M c V l r k r T 2 x e q q k V U x w J X Z V E 5 R r l Z D k c Z X H m R e Q 3 S P g g C j / S V v g B B z i E B R 1 1 1 M B h Q h I 2 o M K l U U Q C D D Z x J T S J c w g J 7 5 6 j h T H S 1 i m L U 4 Z K b J X W C p 2 K P m v S u V v T 9 d Q 6 v W L Q d E g Z Q Y w 9 s z v W Y U / s n r 2 w j z 9 r N b 0 a X S 8 n t G s 9 L b f L o b O 5 3 P u / q h r t E s d f q r 6 e J Y 6 w 7 n k V 5 N 3 2 m O 4 v 9 J 6 + c X r Z y W 1 k Y 8 1 F d s N e y f 8 1 a 7 N H + o H Z e N N v M z x 7 1 c e P R l 5 a 1 J 7 E z 2 b 8 B o V k P J G K J z M r 0 a 1 F v 1 F B z G M B S 9 S N N W x h B 2 n k q X o F 5 7 j A p T K s L C s p Z b W X q g R 8 z S y + h b L 5 C T 2 M k G U = < / l a t e x i t > v 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " W U g W m U E R R 7 O 9 N Z b L M A Y q 1 K 4 I Y g I = " > A A A C h H i c h V G 7 S g N B F D 1 Z N c b 4 S N R G s A k G g 4 W E S a I o F h K w s c z D R E E l 7 K 6 T u G R f 7 G 4 W Y s g P C L a m s F K w E H t / w M Y f s M g n i G U E G w t v N g u i Q b 3 D z J w 5 c 8 + d M 1 z J V B X b Y a w b E E Z G x 4 L j o Y n w 5 N T 0 T C Q 6 O 1 e 2 j Y Y l 8 5 J s q I Z 1 I I k 2 V x W d l x z F U f m B a X F R k 1 S + L 9 V 3 + v f 7 L r d s x d D 3 n K b J j z W x p i t V R R Y d o o p u J V O J x l m S e R E b B i k f x O F H z o g + 4 A g n M C C j A Q 0 c O h z C K k T Y N A 6 R A o N J 3 D F a x F m E F O + e o

N P 5 t X g 2 4 T c q h E U s Y Y W 6 s Y E s d p F D i a r X c I F L d I S g s C p k h P V B q h D w N f P 4 F s L 2 J z + q k G Y = < / l a t e x i t > v 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " k 0 M 1 n R m E a r b b k j H I k 8 h M i y V G o H Q = " > A A A C h H i c h V G 7 S g N B F D 1 Z X z G + o j a C T T A k W E i Y a E S x E M H G 0 i R G B Q 1 h d x 3 j 4 L 7 Y n S z E 4 A 8 I t l p Y K V i I v T 9 g 4 w 9 Y 5 B P E M o K N h T e b B d G g 3 m F m z p y 5 5 8 4 Z r u Y Y w p O M N S N K T 2 9 f / 0 B 0 M D Y 0 P D I 6 F h + f 2 P b s m q v z k m 4 b t r u r q R 4 3 h M V L U k i D 7 z o u V 0 3 N 4 D v a 8 X r 7 f s f n r i d s a 0 v W H V 4 2 1 a o l D o W u S q K K f i V X i S d Z h g W R 6 A b Z E C Q R x q Y d f 8 A + D m B D R w 0 m O C x I w g Z U e D T 2 k A W D Q 1 w Z D e J c Q i K 4 5 z h F j L Q 1 y u K U o R J 7 T G u V T n s h a 9 G 5 X d M L 1 D q 9 Y t B 0 S Z l A i j 2 z O 9 Z i T + y e v b C P X 2 s 1 g h p t L 3 X a t Y 6 W O 5 W x s 6 n i + 7 8 q k 3 a J o y / V n 5 4 l D r E c e B X k 3 Q m Y 9 i / 0 j t 4 / u W w V V w q p R p r d s F f y f 8 2 a 7 J F + Y P l v + m 2 e F 6 7 + 8 K O R l 1 N q T / Z n M 7 r B 9 n w m u 5 C Z z + e S a + m w U V F M Y w a z 1 I 0 l r G E D m y h R 9 S r O c Y F L p V + Z U x a U x U 6 q E g k 1 k / g W y u o n Q c i Q Z w = = < / l a t e x i t > v 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 l x h H j U M / e b d S U U P g g J J g Z i S g b k = " > A A A C h H i c h V G 7 S g N B F D 1 Z N c b 4 S N R G s B G D w U L C b G J Q L C R g Y x m N S Q Q N Y X c d 4 5 J 9 s b t Z i C E / I N i a w k r B Q u z 9 A R t / w C K f I J Y K N h b e b B Z E x X i H m T l z 5 p 4 7 Z 7 i y p a m O y 1 g 3 J A w N j 4 R H I 2 P R 8 Y n J q V h 8 e q b k m A 1 b 4 U X F 1 E x 7 X 5 Y c r q k G L 7 q q q / F 9 y + a S L m u 8 L N e 3 e v d l j 9 u O a h p 7 b t P i F V 2 q G e q x q k g u U Q W v m q 3 G E y z F / F j 4 D c Q A J B B E 3 o z f 4 x B H M K G g A R 0 c B l z C G i Q 4 N A 4 g g s E i r o I W c T Y h 1 b / n a C N K 2 g Z l c c q Q i K 3 T W q P T Q c A a d O 7 V d H y 1 Q q 9 o N G 1 S L m C J P b F b 9 s o e 2 R 1 7 Z h 9 / 1 m r 5 N X p e m r T L f S 2 3 q r G z u c L 7 v y q d d h c n X 6 q B n l 0 c Y 9 3 3 q p J 3 y 2 d 6 v 1 D 6 e u + 0 8 1 r Y 2 F 1 q J d k 1 e y H / V 6 z L H u g H h v e m 3 O z w 3 c s B f m T y 0 q b 2 i D + b 8 R u U 0 i k x k 0 r v r C Z y y a B R E c x j E c v U j T X k s I 0 8 i l S 9 h n N c o C O E h R U h I 2 T 7 q U I o 0 M z i W w i b n 0 P m k G g = < / l a t e x i t > G <s < l a t e x i t s h a 1 _ b a s e 6 4 = " b G J S D 7 E c v 4 l L j 5 d x 0 s M i Z E U G V r A = " > A A A C h 3 i c h V F N L w N B G H 6 s 7 / o q L h I X 0 W i c a r Y E E Q f i w J F W S 1 J N s 7 u m N e x X d r d N 2 P g D T m 6 C E 4 m D u P s D L v 6 A Q 3 + C O J K 4 O H h 3 u 4 n Q 4 J 3 M z D P P v M 8 7 z + R V b V 2 4 H m P 1 F q m 1 r b 2 j s 6 s 7 1 t P b 1 z 8 Q H x z K u 1 b V 0 X h O s 3 T L 2 V Y V l + v C 5 D l P e D r f t h 2 u G K r O t 9 S D l e B + q 8 Y d V 1 j m p n d o 8 6 K h V E x R F p r i E Z V f L f m L 7 n E p n m A p F s Z Y M 5 A j k E A U 6 1 b 8 H j v Y h Q U N V R j g M O E R 1 q H A p V G A D A a b u C J 8 4 h x C I r z n O E a M t F X K 4 p S h E H t A a 4 V O h Y g 1 6 R z U d E O 1 R q / o N B 1 S j m G C P b F b 9 s o e 2 R 1 7 Z h + / 1 v L D G o G X Q 9 r V h p b b p Y G T k e z 7 v y q D d g 9 7 X 6 o / P X s o Y z 7 0 K s i 7 H T L B L 7 S G v n Z 0 9 p p d y E z 4 S X b N X s j / F a u z B / q B W X v T b j Z 4 5 v I P P y p 5 C d o j / 2 x G M 8 i n U / J 0 K r 0 x k 1 h K R o 3 q w i j G M U n d m M M S 1 r C O H F X f x y n O c S F 1 S 1 P S r D T f S J V a I s 0 w v o W 0 / A l k a Z H J < / l a t e x i t > , v ⇡(1)

< l a t e x i t s h a 1 _ b a s e 6 4 = " j 5 C 2 y e X R T p l 2 i t 

I W I k G E P g I h W V 8 = " > A A A C j H i c h V H L S s N A F L 2 N r 1 q 1 r b o R 3 B R L S 9 2 U S S 0 o i l A Q x G U f 9 g F t K U k c 6 9 C 8 S N J A L f 0 B 9 + J C U B R c i H t / w I 0 / 4 K K f I C 4 r u H H h T R o Q L d Y b J n P m z D 1 3 z s w V d Z m Z F i F 9 H z c x O T U 9 4 5 8 N z M 0 v B E P h x a W S q b U N i R Y l T d a M i i i Y V G Y q L V r M k m l F N 6 i g i D I t i 6 0 9 Z 7 9 s U 8 N k m n p o d X R a V 4 S m y o 6 Z J F h I V e 1 G t 6 a z B L / e C z T C U Z I k b k R G A e + B K H i R 1 c K P U I M j 0 E C C N i h A Q Q U L s Q w C m P h V g Q c C O n J 1 6 C J n I G L u P o U e B F D b x i y K G Q K y L f w 3 c V X 1 W B X X T k 3 T V U t 4 i o z D Q G U E Y u S F

I = " > A A A C j H i c h V H L S s N A F L 2 N r 1 q 1 r b o R 3 B R L S 9 2 U S S 0 o i l A Q x G U f 9 g F t K U k c 6 9 A 0 C U k a q K E / 4 F 5 c C I q C C 3 H v D 7 j x B 1 z 0 E 8 R l B T c u v E k D o s V 6 w 2 T O n L n n z p m 5 o i Y z w y S k 7 + M m J q e m Z / y z g b n 5 h W A o v L h U M t S O L t G i p M q q X h E F g 8 p M o U W T m T K t a D o V 2 q J M y 2 J r z 9 k v W 1 Q 3 m K o c m l 2 N 1 t t C U 2 H H T B J M p K p W w 6 5 p L J F a 7 w U a 4 S h J E j c i o 4 D 3 Q B S 8 y K r h R 6 j B E a g g Q Q f a Q E E B E 7 E M A h j 4 V Y E H A h p y d b C R 0 x E x d 5 9 C D w K o 7 W A W x Q w B 2 R b + m 7 i q e q y C a 6 e m 4 a o l P E X G o a M y A j H y Q u 7 J g D y T B / J K P v + s Z b s 1 H C 9 d n M W h l m q N 0 N l K 4 e N f V R t n E 0 6 + V W M 9 m 3 A M W 6 5 X h t 4 1 l 3 F u I Q 3 1 1 u n F o L C d j 9 l x c k v e 0 P 8 N 6 Z M n v I F i v U t 3 O Z q / H O N H R C 8 9 b A / / u x m j o J R K 8 h v J V C 4 d z c S 9 R v l h F d Y g g d 3 Y h A w c Q B a K 7 n u e w x V c c 0 E u z e 1 w u 8 N U z u d p l u F H c P t f 2 d S T P Q = = < / l a t e x i t > v ⇡(3) < l a t e x i t s h a 1 _ b a s e 6 4 = " O d M a u x p 3 / K Z b 2 D o A k Z x F 5 h o 0 8 R w = " > A A A C j H i c h V H L S s N A F L 2 N r 1 q 1 r b o R 3 B R L S 9 2 U S V t Q F K E g i M s +

M G H 6 E K x 6 C C B B 1 o A w U F T M Q y C G D g V w E e C G j I 1 c B G T k f E n H 0 K P f C h t o N Z F D M E Z F v 4 b + K q 4 r I K r o c 1 D U c t 4 S k y D h 2 V I Y i Q F 3 J P B u S Z P J B X 8 v l n L d u p M f T S x V k c a a l W D 5 y t 5 T / + V b V x N u H k W z X R s w k N 2 H a 8 M v S u

J O J + M J 7 K p c D r q N s o L 6 7 A B M e z G F q T h E D J Q c N 7 z H K 7 g m v N z K W 6 X 2 x u l c h 5 X s w o / g j v 4 A t v 1 k z 4 = < / l a t e x i t > v ⇡(4) < l a t e x i t s h a 1 _ b a s e 6 4 = " y l A y K G C I j T E 2 N 4 + O N m B C q m A o E S s = " > A A A C j H i c h V H L S s N A F L 2 N r 1 q 1 r b o R 3 B R L S 9 2 U S S 0 o i l A Q x G U f 9 g F t K U k c 6 9 A 0 C U k a q K E / 4 F 5 c C I q C C 3 H v D 7 j x B 1 z 0 E 8 R l B T c u v E k D o s V 6 w 2 T O n L n n z p m 5 o i Y z w y S k 7 + M m J q e m Z / y z g b n 5 h W A o v L h U M t S O L t G i p M q q X h E F g 8 p M o U W T m T K t a D o V 2 q J M y 2 J r z 9 k v W 1 Q 3 m K o c m l 2 N 1 t t C U 2 H H T B J M p K p W w 6 5 p L J F e 7 w U a 4 S h J E j c i o 4 D 3 Q B S 8 y K r h R 6 j B E a g g Q Q f a Q E E B E 7 E M A h j 4 V Y E H A h p y d b C R 0 x E x d 5 9 C D w K o 7 W A W x Q w B 2 R b + m 7 i q e q y C a 6 e m 4 a o l P E X G o a M y A j H y Q u 7 J g D y T B / J K P v + s Z b s 1 H C 9 d n M W h l m q N 0 N l K 4 e N f V R t n E 0 6 + V W M 9 m 3 A M W 6 5 X h t 4 1 l 3 F u I Q 3 1 1 u n F o L C d j 9 l x c k v e 0 P 8 N 6 Z M n v I F i v U t 3 O Z q / H O N H R C 8 9 b A / / u x m j o J R K 8 h v J V C 4 d z c S 9 R v l h F d Y g g d 3 Y h A w c Q B a K 7 n u e w x V c c 0 E u z e 1 w u 8 N U z u d p l u F H c P t f 3 h a T P w = = < / l a t e x i t > v ⇡(5) < l a t e x i t s h a 1 _ b a s e 6 4 = " C A p F J k L 3 R 1 / V K M h U Z P M l 4 B a v x 3 Y = " > A A A C j H i c h V H L S s N A F L 2 N r 1 q 1 r b o R 3 B R L S 9 2 U a a 0 o i l A Q x G U f 9 g F t K U m c 1 q F p E p I 0 U E N / w L 2 4 E B Q F F + L e H 3 D j D 7 j o J 4 j L C m 5 c e J M G R I v 1 h s m c O X P P n T N z B V V i u k F I 3 8 N N T E 5 N z 3 h n f X P z C / 5 A c H G p q C s d T a Q F U Z E U r S z w O p W Y T A s G M y R a V j X K t w W J l o T W v r 1 f M q m m M 0 U + M r o q r b X 5 p s w a T O Q N p C p m 3 a q q L L a 5 3 v P V g 2 E S J 0 6 E R k H C B W F w I 6 M E H 6 E K x 6 C A C B 1 o A w U Z D M Q S 8 K D j V 4 E E E F C R q 4 G F n I a I O f s U e u B D b Q e z K G b w y L b w 3 8 R V x W V l X N s 1 d U c t 4 i k S D g 2 V I Y i Q F 3 J P B u S Z P J B X 8 v l n L c u p Y X v p 4 i w M t V S t B 8 5 W 8 h / / q t o 4 G 3 D y r R r r 2 Y A G b D t e G X p X H c a + h T j U m 6 c X g / x O L m J F y S 1 5 Q / 8 3 p E + e 8 A a y + S 7 e Z W n u c o w f A b 3 0 s D 2 J 3 8 0 Y B c V k P L E R T 2 Z T 4 X T U b Z Q X V m E N Y t i N L U j D I W S g 4 L z n O V z B N e f n U t w u t z d M 5 T y u Z h l + B H f w B e A 3 k 0 A = < / l a t e x i t > X ⇡ < l a t e x i t

I = " > A A A C h 3 i c h V G 7 S g N B F D 1 Z X 4 n P q I 1 g E w w R q z i r o m I V s b F M 1 M R A f L C 7 j n F 0 X + x O A j H k B 6 z s R K 0 U L M T e H 7 D x B y z 8 B L F U s L H w Z r M g K u o d Z u b M m X v u n O H q r i l 8 y d h j R G l r 7 + j s i s a 6 e 3 r 7 + g f i g 0 M F 3 6 l 4 B s 8 b j u l 4 R V 3 z u S l s n p d C m r z o e l y z d J O v 6 w d L z f v 1 K v d 8 4 d h r s u b y T U s r 2 2 J X G J o k q l D c 2 n B F Y j u e Z G k W R O I n U E O Q R B h Z J 3 6 L D e z A g Y E K L H D Y k I R N a P B p l K C C w S V u E 3 X i P E I i u O d o o J u 0 F c r i l K E R e 0 B r m U 6 l k L X p 3 K z p B 2 q D X j F p e q R M I M U e 2 D V 7 Y f f s h j 2 x 9 1 9 r 1 Y M a T S 8 1 2 v W W l r v b A 0 c j q 2 / / q i z a J f Y + V X 9 6 l t j F f O B V k H c 3 Y J q / M F r 6 6 u H J y + r C S q o + z i 7 Z M / m / Y I / s j n 5 g V 1 + N q x x f O f / D j 0 5 e G t Q e 9 X s z f o L C V F q d T k / l Z p K Z 8 b B R U Y x i D B P U j T l k s I w s 8 l R 9 H 8 c 4 x Z k S U y a V W W W + l a p E Q s 0 w v o S y + A H Y 8 J G H < / l a t e x i t > A ⇡ < l a t e x i t s h a 1 _ b a s e 6 4 = " T k f N o U 0 h 8 R + Q L 9 G R D I K z O x X 7 c X g = " > A A A C h 3 i c h V G 7 S g N B F D 2 u 7 2 e i N o J N M B i s 4 q y K B i v F x t J X o p D E s L t O d M y + 2 N 0 E Y v A H r O x E r R Q s x N 4 f s P E H L P I J Y h n B x s K 7 m w X R Y L z D z J w 5 c 8 + d M 1 z V 1 o X r M V b v k D q 7 u n t 6 + / o H B o e G R y L R 0 b G M a 5 U d j a c 1 S 7 e c P V V x u S 5 M n v a E p / M 9 2 + G K o e p 8 V y 2 t + f e 7 F e 6 4 w j J 3 v K r N 8 4 Z y a I q i 0 B S P q M z q f s 4 W s U I 0 z p I s i F g r k E M Q R x g b V v Q R O R z A g o Y y D H C Y 8 A j r U O D S y E I G g 0 1 c H j X i H E I i u O c 4 x Q B p y 5 T F K U M h t k T r I Z 2 y I W v S 2 a / p B m q N X t F p O q S M Y Z q 9 s H v W Y M / s g b 2 y z z 9 r 1 Y I a v p c q 7 W p T y + 1 C 5 G x i + + N f l U G 7 h 6 N v V V v P H o p I B V 4 F e b c D x v + F 1 t R X T i 4 a 2 8 t b 0 7 U E u 2 V v 5 P + G 1 d k T / c C s v G t 3 m 3 z r u o 0 f l b y c U n v k 3 8 1 o B Z m 5 p D y f n N t c i K 8 k w k b 1 Y R J T m K F u L G E F 6 9 h A m q o f 4 x y X u J L 6 p V l p U U o 1 U 6 W O U D O O H y G t f g G n y 5 F w < / l a t e x i t > (X ⇡ , A ⇡ ) < l a t e x i t s h a 1 _ b a s e 6 4 = " D 9 I D V s z Z d V 2 q J W v Z T Q g a O Q e n D E U = " > A A A C j 3 i c h V H L S s N A F D 3 G 9 7 O t b g Q 3 x d J S Q c q 0 C o o L q b j R X a v W F l o r S R x 1 a J q E J C 3 U 0 h / w B x R c V X A h 7 v 0 B N / 6 A C z 9 B X C q 4 c e F N G h A t 1 h s m 9 8 y Z e + 6 c 4 S q m J m y H s e c + q X 9 g c G h 4 Z H R s f G J y K h A M T e / b R s 1 S e U 4 1 N M M q K L L N N a H z n C M c j R d M i 8 t V R e N 5 p b L p n u f r 3 L K F o e 8 5 D Z M f V O U T X R w L V X a I K s c L 5 Z I p F s M b b l o 4 D E Z Y g n k R 7 g Z J H 0 T g R 8 Y I 3 q O E I x h Q U U M V H D o c w h p k 2 P Q V k Q S D S d w B m s R Z h I R 3 z t H C G G l r V M W p Q i a 2 Q v 8 T 2 h V 9 V q e 9 2 9 P 2 1 C r d o t G y S B l G l D 2 x W / b G H t k d e 2 G f f / Z q e j 1 c L w 3 K S k f L z c P A + e z u x 7 + q K m U H p 9 + q n p 4 d H G P V 8 y r I u + k x 7 i v U j r 5 + d v G 2 u 7 Y T b c b Y N X s l / 2 3 2 z B 7 o B X r 9 X b 3 J 8 p 2 r H n 4 U 8 t K i 8 S R / D 6 M b 7 K c S y a V E K r s c S c f 8 Q Y 1 g D v O I 0 z R W k M Y W M s h R d w u X a O N a C k k r 0 r q U 7 p R K f b 5 m B j 9 C 2 v 4 C A 9 K U K A = = < / l a t e x i t > (G, ⇡)

< l a t e x i t s h a 1 _ b a s e 6 4 = " 

+ j 5 o A k A 3 h w + / + y e 1 L 3 Y V B e J / 4 J k = " > A A A C i X i c h V F N S w J R F L 1 O X 6 a V V p u g j S S K Q c g b C x J X

W i C 4 v l E y t Y 4 h 0 a K k y Z p R E Q W T y k y l R Y t Z M q 3 o B h U U U a Z l s Z 2 x z 8 t d a p h M U 0 + s n k 7 r i t B S W Z N J g o V U J X a 0 F 6 r p b L c R D J M 4 c S o 0 D X g X h M G t r B Z 8 h B q c g g Y S d E A B C i p Y i G U Q w M S n C j w Q 0 J G r Q x 8 5 A x F z z i k M w I f a D n Z R 7 B C Q b e O

c C 2 Z s j Y E f Q A r X X h U 3 J U = " > A A A C g 3 i c h V G 7 S g N B F D 1 Z X z E + E r U R b I I h Q R D C b B Q U Q R A s t D S J e U A U 2 V 0 n c c m + 2 N 0 E N O Q H x F Y t r B Q s x N 4 f s P E H L P I J Y h n B x s K 7 m w V R M d 5 h Z s 6 c u e f O G a 5 s a a r j M t Y J C Q O D Q 8 M j 4 d H I 2 P j E Z D Q 2 N V 1 0 z I a t 8 I J i a q Z d l i W H a 6 r B C 6 7 q a r x s 2 V z S Z Y 2 X 5 P q m d 1 9 q c t t R T W P X P b b 4 v i 7 V D L W q K p J L V G 4 r f h B L s D T z I / 4 b i A F I I I g d M / a A P R z C h I I G d H A Y c A l r k O D Q q E A E g 0 X c P l r E 2 Y R U / 5 6 j j Q h p G 5 T F K U M i t k 5 r j U 6 V g D X o 7 N V 0 f L V C r

= " > A A A C g n i c h V F N L w N R F D 1 G U f V V b C Q 2 j Y a I R X O n J E Q s J D a W q q p N E J k Z D y + d r 8 x M m 1 T T P 8 C W W F i R W I i 9 P 2 D j D 1 j 0 J 4 g l i Y 2 F 2 + k k g u C + v P f O O + + e + 8 7 L 1 V 1 T + g F R s 0 P p j H V

+ q L N 4 D H H 6 q / v Q c Y B 8 L o V f J 3 t 2 Q a f 3 C a O u r R + c v + c X 1 y f o U X d E z + 7 + k J t 3 z D + z q q 3 G d E + s X f / j R 2 U u D 2 6 N + b 8 Z P s J n N q L O Z b G 4 u v T w V N S q O c U x g m r s x j 2 W s Y g 0 F r i 5 w g l O c K T F l R l G V 2 X a q 0 h F p R v E l l K U P r T e P u A = = < / l a t e x i t > a < l a t e x i t s h a 1 _ b a s e 6 4 = " F V + T M a R f q J 0 Z S 2 U k n 8 z j n B L + I M M = " > A A A C g n i c h V G 7 S g N B F D 1 Z 4 y u + o j a C T T A Y x C L c j Y I i F o K N p U n M A 1 R k d 5 3 E J Z v d Z X c T i M E f 0 F a x s F K w E H t / w M Y f s M g n i G U E G w t v N g u i Y r z D z J w 5 c 8 + d M 1 z V N n T X I 2 q F p L 5 w / 8 D g 0 H B k Z H R s f C I 6 O Z V 3 r Z q j i Z x m G Z Z T V B V X G L o p c p 7 u G a J o O 0 K p q o Y o q J X N z n 2 h L h x X t 8 w d r 2 G L / a p S N v W S r i k e U 2 n l I B q n J P k R + w 3 k A M Q R x L Y V f c A e D m F B Q w 1 V C J j w G B t Q 4 P L Y h Q y C

M + 8 L X W K v H A G R m H r f y Z Q J N f R U J e E = " > A A A C g n i c h V G 7 S g N B F D 1 Z 4 y u + o j a C T T A Y x C L c j Y I i F o K N p U n M A 1 R k d 5 3 E J Z v d Z X c T i M E f 0 F a x s F K w E H t / w M Y f s M g n i G U E G w t v N g u i Y r z D z J w 5 c 8 + d M 1 z V N n T X I 2 q F p L 5 w / 8 D g 0 H B k Z H R s f C I 6 O Z V 3 r Z q j i Z x m G Z Z T V B V X G L o p c p 7 u G a J o O 0 K p q o Y o q J X N z n 2 h L h x X t 8 w d r 2 G L / a p S N v W S r i k e U 2 n 1 I B q n J P k R + w 3 k A M Q R x L Y V f c A e D m F B Q w 1 V C J j w G B t Q 4 P L Y h Q y C z d w + m s w 5 j H T / X u A E E d b W O E t

= " > A A A C g n i c h V F N L w N R F D 1 G U f V V b C Q 2 j Y a I R X O n J E Q s J D a W q q p N E J k Z D y + d r 8 x M m 1 T T P 8 C W W F i R W I i 9 P 2 D j D 1 j 0 J 4 g l i Y 2 F 2 + k k g u C + v P f O O + + e + 8 7 L 1 V 1 T + g F R s 0 P p j H V

+ q L N 4 D H H 6 q / v Q c Y B 8 L o V f J 3 t 2 Q a f 3 C a O u r R + c v + c X 1 y f o U X d E z + 7 + k J t 3 z D + z q q 3 G d E + s X f / j R 2 U u D 2 6 N + b 8 Z P s J n N q L O Z b G 4 u v T w V N S q O c U x g m r s x j 2 W s Y g 0 F r i 5 w g l O c K T F l R l G V 2 X a q 0 h F p R v E l l K U P

= " > A A A C g n i c h V F N L w N R F D 1 G U f V V b C Q 2 j Y a I R X O n J E Q s J D a W q q p N E J k Z D y + d r 8 x M m 1 T T P 8 C W W F i R W I i 9 P 2 D j D 1 j 0 J 4 g l i Y 2 F 2 + k k g u C + v P f O O + + e + 8 7 L 1 V 1 T + g F R s 0 P p j H V 1 9 8 R 7 E 3 3 9 A 4 N D y e G R T d + p e I Y o G I 7 p e C V d 8 4 U p b V E I Z G C K k u s J z d J N U d T L K 6 3 7 Y l V 4 v n T s j a D m i h 1 L O 7 D l v j S 0 g K m c v Z t M U 4 b C S P 0 E a g T S i G L N S d 5 h G 3 t w Y K A C C w I 2 A s Y m N P g 8 t q C C 4 D K 3 g z p z H i M Z 3 g s 0 k G B t h b M E Z 2 j M l n k 9 4 N N W x N p 8 b t X 0 Q 7 X B r 5 g 8 P V a m M E m P d E M v 9 E C 3 9 E T v v 9 a q h z V a X m q 8 6 2 2 t c H e H j s f y b / + q L N 4 D H H 6 q / v Q c Y B 8 L o V f J 3 t 2 Q a f 3 C a O u r R + c v + c X 1 y f o U X d E z + 7 + k J t 3 z D + z q q 3 G d E + s X f / j R 2 U u D 2 6 N + b 8 Z P s J n N q L O Z b G 4 u v T w V N S q O c U x g m r s x j 2 W s Y g 0 F r i 5 w g l O c K T F l R l G V 2 X a q 0 h F p R v E l l K U P r T e P u A = = < / l a t e x i t >

Figure 3 : Example of tensor representation. n, a, and b denote the numbers of nodes, node labels, and edge labels, respectively. X π ∈ {0, 1} n×a , whose i-th row is a one-hot vector corresponding to the label of v , stores information about nodes. A π ∈ {0, 1} n×n×b , whose (i, j)-th element is a one-hot vector corresponding to the label of e π(i),π(j) , stores information about edges. If no edge exists between v π(i) and v π(j) , we replace it with a zero vector. Note that (G, π) and (X π , A π ) correspond uniquely.

A.3 DETAILED MODEL PIPELINE:

A detailed pipeline of GRAM is illustrated in Figure 4 . A <s,<s < l a t e x i t s h a 1 _ b a s e 6 4 = " U 8 

r n K S X M f T f W u W l v W T X X z V w r H z o = " > A A A C i 3 i c h V H L S s N A F D 2 N r 1 p f V T e C m 2 J R X E i Z t I J S u l B E c G m r t c U H J Y n T G k y T k E w L N f g D r g U X o q D g Q t z 7 A 2 7 8 A R d + g r h U c O P C m z Q g K u o d Z u b M m X v u n O G q t q G 7 g r H H i N T R 2 d X d E + 2 N 9 f U P D A 7 F h 0 c 2 X K v h a L y o W Y b l l F X F 5 Y Z u 8 q L Q h c H L t s O V u m r w k r q / 5 N + X m t x x d c t c F y 2 b 7 9 S V m q l X d U 0 R R G 0 u V r y c O 5 P I u Y e V e J K l W B C J n 0 A O Q R J h r F r x W 2 x j F x Y 0 N F A H h

F R M = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J A w 6 8 i E f C S B p 6 w N f 6 F f a Q o I N f 8 D R x Q E X T R

M j M t Q k Y + b m 5 + Y X H J v x w I r q y u h c L r G 2 V T 6 x o S L U m a r B l V U T C p z F R a s p g l 0 6 p u U E E R Z V o R O 1 n n v N K j h s k 0 9 d j q 6 7 S h C G 2 V t Z g k W E h V 6 6 J i n w 1 O D p v h K E k Q t y L T g P d A F L z K a e F H q M M p a C B B F x S g o I K F W A Y B T H x q w A M B H b k G 2 M g Z i J h 7 T m E A A d R 2 s Y t i h 4 B s B 7 9 t 3 N U 8 V s W 9 M 9 N 0 1 R L + R c b X Q G U E Y u S F 3 J M x e S Y P 5 J V 8 / j n L d m c 4 X v q 4 i h M t 1 Z u h i 6 3 i x 7 8 q B V c L z

Z 6 U G z G H j J k n A F / s U R M o d L + Y = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U g g T u Q V T S R M J C y M f M h H A k j a + s C G f q V 9 N E H C H 3 B 0 c c B F E w f j 7 h 9 w 8 Q 8 4 8 B O M I y Y u D t 6 W J k a J e J v 2 n X f e P b f n 5 Y i G I l u M k L G P W 1 h c W l 7 x r w a C a + s b o f D m V s X S e 6 Z E y 5 K u 6 G Z N F C y q y B o t M 5 k p t G a Y V F B F h V b F b t Y 5 r 9 r U t G R d O 2 Z 9 g z Z V o a P J b V k S G F K 1 h q g O c s M T u x W O k g R x K z I L e A 9 E w a u 8 H n 6 E B p y C D h L 0 Q A U K G j D E C g h g 4 V M H H g g Y y D V h g J y J S

J V r + E M 5 7 h Q I s q C s q S s t F O V n l A z h R + h b H w B h 2 q Q i A = = < / l a t e x i t > v 1

< l a t e x i t s h a 1 _ b a s e 6 4 = " 7 8 U q v b K L 7 a S 3 q W s z 7 a W I j x Z 7

V c Q = " > A A A C h H i c h V G 7 S g N B F D 1 Z X / E d t R F s g i F i I W E 2 U R Q L E W w s 8 z B R i C H s r m M c 3 O w u u 5 O A h v y A Y K u F l Y K F 2 P s D N v 6 A R T 5 B L C P Y W H i z W R A V 4

x 1 m 5 s y Z e + 6 c 4 e q O K T z J W C u k 9 P U P D A 6 F h 0 d G x 8 Y n J i N T 0 w X P r r k G z x u 2 a b t 7 u u Z x U 1 g 8 L 4 U 0 + Z 7 j c q 2 q m 3 x X P 9 7 q 3 O / W u e s J 2 9 q R J w

4 v V b W K J Q 6 F o U m i c v W y W o 7 E W I L 5 E f 0 N 1 A D E E E T a j j x g H w e w Y a C G K j g s S M I m N H g 0 i l D B 4 B B X Q o M 4 l 5 D w 7 z m a G C F t j b I 4 Z W j E H t N a o V M

x Y C 0 6 d 2 p 6 v t q g V 0 y a L i m j i L N n d s f a 7 I n d s x f 2 8 W e t h l + j 4 + W E d r 2 r 5 U 5 5 8 m w 2 9 / 6 v q k q 7 x N G X q q d n i 

U O s + V 4 F e X d 8 p v M L o 6 u v n 1 6 2 c + v Z e G O B 3 b B X 8 n / N W u y R f m D V 3 4 z b D M 9 e 9 f C j k 5 c m t U f 9 2 Y z f o J B M q K l E M r M c 2 1 w I G h X G H O a x S N 1 Y x S a 2 k U a e q l d w j g t c K o P K k p J S V r q p S i j Q z O B b K B u f O 2 6 Q Z A = = < / l a t e x i t > v 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " s K z 2 0 e D f d w g / n X s h h p Q J v j 1 I / u 8 = " > A A A C h H i c h V G 7 S g N B F D 1 Z X / G Z q I 1 g E w w R C w m T R F E s R L C x z M N E I Y a w u 4 5 x y G Z 3 2 Z 0 E N O Q H B F s t r B Q s x N 4 f s P E H L P I J Y h n B x s K b z Y K o G O 8 w M 2 f O 3 H P n D F e z D e F K x t o B Z W B w a H g k O D o 2 P j E 5 F Q p P z x R c q + 7 o P K 9 b h u X s a 6 r L D W H y v B T S 4 P u 2 w 9 W a Z v A 9 r b r d v d 9 r c M c V l r k r T 2 x e q q k V U x w J X Z V E 5 R r l Z D k c Z X H m R e Q 3 S P g g C j / S V v g B B z i E B R 1 1 1 M B h Q h I 2 o M K l U U Q C D D Z x J T S J c w g J 7 5 6 j h T H S 1 i m L U 4 Z K b J X W C p 2 K P m v S u V v T 9 d Q 6 v W L Q d E g Z Q Y w 9 s z v W Y U / s n r 2 w j z 9 r N b 0 a X S 8 n t G s 9 L b f L o b O 5 3 P u / q h r t E s d f q r 6 e J Y 6 w 7 n k V 5 N 3 2 m O 4 v 9 J 6 + c X r Z y W 1 k Y 8 1 F d s N e y f 8 1 a 7 N H + o H Z e N N v M z x 7 1 c e P R l 5 a 1 J 7 E z 2 b 8 B o V k P J G K J z M r 0 a 1 F v 1 F B z G M B S 9 S N N W x h B 2 n k q X o F 5 7 j A p T K s L C s p Z b W X q g R 8 z S y + h b L 5 C T 2 M k G U = < / l a t e x i t > v 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " W U g W m U E R R 7 O 9 N Z b L M A Y q 1 K 4 I Y g I = " > A A A C h H i c h V G 7 S g N B F D 1 Z N c b 4 S N R G s A k G g 4 W E S a I o F h K w s c z D R E E l 7 K 6 T u G R f 7 G 4 W Y s g P C L a m s F K w E H t / w M Y f s M g n i G U E G w t v N g u i Q b 3 D z J w 5 c 8 + d M 1 z J V B X b Y a w b E E Z G x 4 L j o Y n w 5 N T 0 T C Q 6 O 1 e 2 j Y Y l 8 5 J s q I Z 1 I I k 2 V x W d l x z F U f m B a X F R k 1 S + L 9 V 3 + v f 7 L r d s x d D 3 n K b J j z W x p i t V R R Y d o o p u J V O J x l m S e R E b B i k f x O F H z o g + 4 A g n M C C j A Q 0 c O h z C K k T Y N A 6 R A o N J 3 D F a x F m E F O + e o

N P 5 t X g 2 4 T c q h E U s Y Y W 6 s Y E s d p F D i a r X c I F L d I S g s C p k h P V B q h D w N f P 4 F s L 2 J z + q k G Y = < / l a t e x i t > v 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " k 0 M 1 n R m E a r b b k j H I k 8 h M i y V G o H Q = " > A A A C h H i c h V G 7 S g N B F D 1 Z X z G + o j a C T T A k W E i Y a E S x E M H G 0 i R G B Q 1 h d x 3 j 4 L 7 Y n S z E 4 A 8 I t l p Y K V i I v T 9 g 4 w 9 Y 5 B P E M o K N h T e b B d G g 3 m F m z p y 5 5 8 4 Z r u Y Y w p O M N S N K T 2 9 f / 0 B 0 M D Y 0 P D I 6 F h + f 2 P b s m q v z k m 4 b t r u r q R 4 3 h M V L U k i D 7 z o u V 0 3 N 4 D v a 8 X r 7 f s f n r i d s a 0 v W H V 4 2 1 a o l D o W u S q K K f i V X i S d Z h g W R 6 A b Z E C Q R x q Y d f 8 A + D m B D R w 0 m O C x I w g Z U e D T 2 k A W D Q 1 w Z D e J c Q i K 4 5 z h F j L Q 1 y u K U o R J 7 T G u V T n s h a 9 G 5 X d M L 1 D q 9 Y t B 0 S Z l A i j 2 z O 9 Z i T + y e v b C P X 2 s 1 g h p t L 3 X a t Y 6 W O 5 W x s 6 n i + 7 8 q k 3 a J o y / V n 5 4 l D r E c e B X k 3 Q m Y 9 i / 0 j t 4 / u W w V V w q p R p r d s F f y f 8 2 a 7 J F + Y P l v + m 2 e F 6 7 + 8 K O R l 1 N q T / Z n M 7 r B 9 n w m u 5 C Z z + e S a + m w U V F M Y w a z 1 I 0 l r G E D m y h R 9 S r O c Y F L p V + Z U x a U x U 6 q E g k 1 k / g W y u o n Q c i Q Z w = = < / l a t e x i t > v 5

< l a t e x i t s h a 1 _ b a s e 6 4 = " 8 l x h H j U M / e b d S U U P g g J

J g Z i S g b k = " > A A A C h H i c h V G 7 S g N B F D 1 Z N c b 4 S N R G s B G D w U L C b G J Q L C R g Y x m N S Q Q N Y X c d 4 5 J 9 s b t Z i C E / I N i a w k r B Q u z 9 A R t / w C K f I J Y K N h b e b B Z E x X i H m T l z 5 p 4 7 Z 7 i y p a m O y 1 g 3 J A w N j 4 R H I 2 P R 8 Y n J q V h 8 e q b k m A 1 b 4 U X F 1 E

x 7 X 5 Y c r q k G L 7 q q q / F 9 y + a S L m u 8 L N e 3 e v d l j 9 u O a h p 7 b t P i F V 2 q G e q x q k g u U 

Q W v m q 3 G E y z F / F j 4 D c Q A J B B E 3 o z f 4 x B H M K G g A R 0 c B l z C G i Q 4 N A 4 g g s E i r o I W c T Y h 1 b / n a C N K 2 g Z l c c q Q i K 3 T W q P T Q c A a d O 7 V d H y 1 Q q 9 o N G 1 S L m C J P b F b 9 s o e 2 R 1 7 Z h 9 / 1 m r 5 N X p e m r T L f S 2 3 q r G z u c L 7 v y q d d h c n X 6 q B n l 0 c Y 9 3 3 q p J 3 y 2 d 6 v 1 D 6 e u + 0 8 1 r Y 2 F 1 q J d k 1 e y H / V 6 z L H u g H h v e m 3 O z w 3 c s B f m T y 0 q b 2 i D + b 8 R u U 0 i k x k 0 r v r C Z y y a B R E c x j E c v U j T X k s I 0 8 i l S 9 h n N c o C O E h R U h I 2 T 7 q U I o 0 M z i W w i b n 0 P m k G g = < / l a t e x i t > G <s < l a t e x i t s h a 1 _ b a s e 6 4 = " b G J S D 7 E c v 4 l L j 5 d x 0 s M i Z E U G V r A = " > A A A C h 3 i c h V F N L w N B G H 6 s 7 / o q L h I X 0 W i c a r Y E E Q f i w J F W S 1 J N s 7 u m N e x X d r d N 2 P g D T m 6 C E 4 m D u P s D L v 6 A Q 3 + C O J K 4 O H h 3 u 4 n Q 4 J 3 M z D P P v M 8 7 z + R V b V 2 4 H m P 1 F q m 1 r b 2 j s 6 s 7 1 t P b 1 z 8 Q H x z K u 1 b V 0 X h O s 3 T L 2 V Y V l + v C 5 D l P e D r f t h 2 u G K r O t 9 S D l e B + q 8 Y d V 1 j m p n d o 8 6 K h V E x R F p r i E Z V f L f m L 7 n E p n m A p F s Z Y M 5 A j k E A U 6 1 b 8 H j v Y h Q U N V R j g M O E R 1 q H A p V G A D A a b u C J 8 4 h x C I r z n O E a M t F X K 4 p S h E H t A a 4 V O h Y g 1 6 R z U d E O 1 R q / o N B 1 S j m G C P b F b 9 s o e 2 R 1 7 Z h + / 1 v L D G o G X Q 9 r V h p b b p Y G T k e z 7 v y q D d g 9 7 X 6 o / P X s o Y z 7 0 K s i 7 H T L B L 7 S G v n Z 0 9 p p d y E z 4 S X b N X s j / F a u z B / q B W X v T b j Z 4 5 v I P P y p 5 C d o j / 2 x G M 8 i n U / J 0 K r 0 x k 1 h K R o 3 q w i j G M U n d m M M S 1 r C O H F X f x y n O c S F 1 S 1 P S r D T f S J V a I s 0 w v o W 0 / A l k a Z H J < / l a t e x i t > v s < l a t e x i t s h a 1 _ b a s e 6 4 = " Q F b 6 B f 0 + z Z t p Z 6 b J e H z v 9 y U Q C x s = " > A A A C h H i c h V G 7 S g N B F D 1 Z N c b 4 S N R G s A m G i I W E S a I o F h K w s c z D P C B K 2 F 0 n c c l m d 9 n d L M S Q H x B s T W G l Y C H 2 / o C N P 2 C R T x D L C D Y W 3 m w W R E W 9 w 8 y c O X P P n T N c y V A V y 2 a s 7 x P G x i f 8 k 4 G p 4 P T M 7 F w o P L 9 Q t P S W K f O C r K u 6 W Z Z E i 6 u K x g u 2 Y q u 8 b J h c b E o q L 0 m N v e F 9 y e G m p e j a g d 0 2 + F F T r G t K T Z F F m 6 i 8 U 7 W q 4 S i L M z c i P 0 H C A 1 F 4 k d H D 9 z j E M X T I a K E J D g 0 2 Y R U i L B o V J M B g E H e E D n E m I c W 9 5 + g i S N o W Z X H K E I l t 0 F q n U 8 V j N T o P a 1 q u W q Z X V J o m K S O I s S d

U v F k d i O a X v U a F c A y V r B G 3 d h C G v v I o E D V 6 z j H B X q C X 1 g X U s L m K F X w e Z p F f A l h 9 w P H K p C m < / l a t e x i t > e 1,s < l a t e x i t s h a 1 _ b a s e 6 4 = " L F 9 W d 2 4 o b v h + 6 B F G K M K E g 6 v N d x Q = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k g g F o b M o o m E i o T G k o c 8 E i R k d x 1 w w r 6 y O 5 A g 4 Q c s b S y w 0 c T C 2 P s D N v 6 A B Z 9 g L D G x s f D u s o l R I t 7 N 7 p w 5 c 8 / d M z m y q T K b E z L y C X P z C 4 t L / u V A c G V 1 L R R e 3 y j b R s d S a E k x V M O q y p J N V a b T E m d c p V X T o p I m q 7 Q i t 7 P O e a V L L Z s Z + j H v m b S u S S 2 d N Z k i c a S q t N E X 9 y L 2 o B G O k g R x K z I N R A 9 E w a u c E X 6 E E z g F A x T o g A Y U d O C I V Z D A x q c G I h A w k a t D H z k L E X P P K Q w g g N o O d l H s k J B t 4 7 e F u 5 r H 6 r h 3 Z t q u W s G / q P h a q I x A j L y Q e z I m z + S B v J L P P 2 f 1 3 R m O l x 6 u 8 k R L z U b o Y q v 4 8 a 9 K w 5 X D 2 b d q p m c O T U i 5 X h l 6 N 1 3 G u Y U y 0 X f P

Q f t m E H d j G N Q 8 j A E e S g 5 K Z w C U O 4 F o K C K K S E 9 K R V 8 H m a T f h R Q v Y L f N C S P A = = < / l a t e x i t > e 2,s < l a t e x i t s h a 1 _ b a s e 6 4 = " a Q 6 + Y g Q X Y v 4 L j s / H 0 O + m O d Q r r B o = " > A A A C i n i c h V G 7 S g N B F D 2 u 7 2 e i N o L N Y o h Y S J h d B V 9 N Q A t L X / G B S t h d J 3 H I v t j d B H T J D 9 h a W K i F g o X Y + w M 2 / o B F P k E s I 9 h Y e L N Z E B X 1 D j N z 5 s w 9 d 8 5 w d d c U f s B Y r U V q b W v v 6 O z q 7 u n t 6 x 9 I J A e H N n 2 n 7 B k 8 Z z i m 4 2 3 r m s 9 N Y f N c I A K T b 7 s e 1 y z d 5 F t 6 a b F x v 1 X h n i 8 c e y M 4 c v m + p R V t U R C G F h C 1 w / O h O i n 7 V T m f T L E M i 0 L + C Z Q Y p B D H i p O 8 x x 4 O 4 M B A G R Y 4 b A S E T W j w a e x C A Y N L 3 D 5 C 4 j x C I r r n q K K H t G X K 4 p S h E V u i t U i n 3 Z i 1 6 d y o 6 U d q g 1 4

x a X q k l J F m T + y W 1 d k j u 2 P P 7 P 3 X W m F U o + H l i H a 9 q e V u P n E y s v 7 2 r 8 q i P c D h p + p P z w E K m I 2 8 C v L u R k z j F 0 Z T X z k + q 6 / P r 6 X D c X b N X s j / F a u x B / q B X X k 1 b l b 5 2 v k f f n T y U q X 2 K N + b 8 R N s q h l l K q O u T q e y 4 3 G j u j C K M U x Q N 2 a Q x T J W k K P q F k 5 x g U u p T 1 K l O W m h m S q 1 x J p h f A l p 6 Q P q 6 5 J n < / l a t e x i t > e t,s < l a t e x i t s h a 1 _ b a s e 6 4 = " P n X 4 9

I E l x E S 6 D 1 4 Q V K J X 4 h u Y / Z 8 = " > A A A C i n i c h V G 7 S g N B F D 2 u r x h f U R v B Z j E o F h J m o + C r E b S w V G N 8 o B J 2 1 0 l c 3 B e 7 k 0 B c 8 g O 2 F h Z q o W A h 9 v 6 A j T 9 g k U 8 Q y w g 2 F t 7 d L I i K e o e Z O X P m n j t n u J p r G r 5 g r N 4 i t b a 1 d 3 Q m u p L d P b 1 9 / a m B w U 3 f K X s 6 z + u O 6 X j b m u p z 0 7 B 5 X h j C 5 N u u x 1 V L M / m W d r Q U 3 m 9 V u O c b j r 0 h q i 7 f t 9 S S b R Q N X R V E 7 f B C I C Z l v y Y X U m m W Y V H I P 4 E S g z T i W H V S 9 9 j D A R z o K M M C h w 1 B 2 I Q K n 8 Y u F D C 4 x O 0 j I M 4 j Z E T 3 H D U k S V u m L E 4 Z K r F H t J b o t B u z N p 3 D m n 6 k 1 u k V k 6 Z H S h l j 7 I n d s g Z 7 Z H f s m b 3 / W i u I a o R e q r R r T S 1 3 C / 0 n w 7 m 3 f 1 U W 7 Q K H n 6 o / P Q s U M R t 5 N c i 7 G z H h L / S m v n J 8 1 s j N r 4 8 F 4 + y a v Z D / K 1 Z n D / Q D u / K q 3 6 z x 9 f M / / G j k p U b t U b 4 3 4 y f Y z G a U q U x 2 b T q 9 O B 4 3 K o E R j G K C u j G D R a x g F X m q b u E U F 7 i U e q S s N C c t N F O l l l g z h C 8 h L X 8 A e A C S q Q = = < / l a t e x i t > A A t,s

< l a t e x i t s h a 1 _ b a s e 6 4 = " G y 3 t 6 p x 2 u p N F B u G y j X Q U G h 2 5 y l s = " > 

A A A C a 3 i c h V G 7 S g N B F D 1 Z 3 / G R q I 2 o R T A k W E i Y V U G x U

M q q M t 1 K V W K Q Z x p d Q M h + k w Y x 5 < / l a t e x i t > (t = 1, ..., s 1)

< l a t e x i t s h a 1 _ b a s e 6 4 = " n q 6 L 0 h s In its s-th step, given a subgraph G <s , our model estimates the new node v s and new edges {e 1,s , ..., e s-1,s } to add next. Specifically, it takes a tensor pair (X <s , A <s,<s ) as input and predicts the label of the new node X s and the labels of the new edges A t,s (t = 1, ..., s -1). In detail, first, the feature extractor calculates s -1 node feature vectors H v = (h v 1 , ..., h v s-1 ) T and a graph feature vector h G from a tensor pair (X <s , A <s,<s ). Next, the node estimator predicts the label of the new node X s from the graph feature vector. When the EOS is output, the generation is terminated. Finally, the edge estimator predicts the labels of the new edges A t,s (t = 1, ..., s -1) from the node feature vectors, the graph feature vector, the embedded vector of the predicted node label, and the embedded vectors of previously predicted edge labels in this step.

X R W 7 Y o / S P 3 r Q H Q + O B T K k = " > A A A C d n i c h V H L S s N A F D 2 N 7 / q q u h E E C Z b 6 A A 0 3 K i i C I L h x 6 a s q q J Q k T j W Y J i G Z V r T 4 A / 6 A C 3 G h o C J + h h t / w I W f I C 4 V d O H C 2 z Q g K u o d Z u b M m X v u n J k x f c c O J d F D Q q m p r a t v a G x K N r e 0 t r W n O j p X Q q 8 Y W C J r e Y 4 X r J l G K B z b F V l p S 0 e s + Y E w C q Y j V s 3 d 2 c r + a k k E o e 2 5 y 3 L f F 5 s F Y 9 u 1 8 7 Z l S K Z y q Y 5 B q U 6 r + r C q a d q w G o 7 o Q 7 l U m j S K Q v 0 J 9 B i k E c

A.4 ILLUSTRATION OF GRAPH ATTENTION:

The graph attention mechanism in feature extraction (self attention) is illustrated in Figure 5 and that in edge estimation (source target attention) is illustrated in Figure 6 . 

F C G EAC , G EACD BFE 3EFC G EACD q 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " S X t S d K 9 o R n T G m Z s x q s a x B g t T d u I = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W T S R

U u h J c V Q D a s q S z Z V m U 5 L n H G V V k 2 L S p q s 0 o p 8 m h 2 f V 7 r U s p m h H / G e S R u a 1 N Z Z i y k S R 6 p a l z X n r N 8 U m + E Y S R C 3 I t N A 9 E A M v M o Z 4 U e o w z E Y o E A H N K C g A 0 e s g g Q 2 P j U Q g Y C J X A M c 5 C x E z D 2 n 0 I c A a j v Y R b F D Q v Y U v 2 3 c 1 T x W

x / 1 4 p u 2 q F f y L i q + F y g j E y Q u 5 J y P y T B 7 I K / n 8 c 5 b j z h h 7 6 e E q T 7 T 

U b I Y u t o o f / 6 o 0 X D m c f K t m e u b Q g p T r l a F 3 0 2 X G t 1 A m + u 7 5 1 a i Y L s S d H X J L 3 t D / D R m S J 7 y B 3 n 1 X 7 v K 0 M J j h R 0 Y v f Y x H / B 3 G N C g n E + J e I p n f j 2 W i X l B + 2 I Y o 7 G I a B 5 C B Q 8 h B y U 3 h E g Z w L Q Q F U U g J 6 U m r 4 P M 0 m / C j h O w X e + W S s A = = < / l a t e x i t > k 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " Y E x U W O 5 0 m U J W v S E P s y H q u K g 1 B C s = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W T S R U J D S W P O S R A C G 7 6 4 A T 9 p X d g Q Q 3 / I C l j Q U 2

o f D m V t k 2 u p Z C S 4 q h G l Z V l m y q M p 2 W O O M q r Z o W l T R Z p R W 5 k 5 2 c V 3 r U s p m h n / C + S R u a 1 N Z Z i y k S R 6 p a l z W n M 2 i K z X C M J I h b k V k g e i A G X u W M 8 C P U 4 R Q M U K A L G l D Q g S N W Q Q I b n x q I Q M B E r g E O c h Y i 5 p 5 T G E A A t V 3 s o t g h I d v B b x t 3 N Y / V c T + Z a b t q B f + i 4 m u h M g J x

b k C W + g 9 9 6 V u z w t D O f 4 k d H L A O M R f 4 c x C 8 r J h H i Q S O Y P Y 5 m o F 5 Q f d i E K + 5 j G E W T g G H J Q c l O 4 h C F c C 0 F B F F J C e t o q + D z N N v w o I f s F b x + S q g = = < / l a t e x i t > k 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " I 2 4 k / f H r g 1 x z R t r g V o g G O z a 9 C J k = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W T S R U J D S W P O S R A C G 7 6 4 A T 9 p X d g Q Q J P 2 B p Y 4 G N J h b G 3 h + w 8 Q c s + A R j i Y m N h X

o f D m V t k 2 u p Z C S 4 q h G l Z V l m y q M p 2 W O O M q r Z o W l T R Z p R W 5 k 3 X O K z 1 q 2 c z Q T 3 j f p A 1 N a u u s x R S J I 1 W t y 9 q g M 2 w m m + E Y S R C 3 I r N A 9 E A M v M o Z 4 U e o w y k Y o E A X N K C g A 0 e s g g Q 2 P j U Q g Y C J X A M G y F m I m H t O Y Q g B 1 H a x i 2 K H h G w H v 2 3 c 1 T x W x 7 0 z 0 3 b V C v 5 F x d d C Z Q T i 5 I X c k w l 5 J g / k l X z + O W v g z n C 8 9 H G V p 1 p q N k M X O 8 W P f 1 U a r h z O v l V z P X N o Q c r

E k Q = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W T C R U J D S W P O S R A C G 7 6 6 A T 9 p X d g Q Q 3 / I C l j Q U 2

f D m V s U 2 u p Z C y 4 q h G l Z N l m y q M p 2 W O e M q r Z k W l T R Z p V W 5 k 5 u c V 3 v U s p m h H / O + S Z u a d K q z N l M k j l S t I W t O Z 9 B K t c I x k i B u R W a B 6 I E Y e J U 3 w o / Q g B M w Q I E u a E B B B 4 5 Y B Q l s f O o g A g E T u S Y 4 y F m I m H t O Y Q A B 1 H a x i 2 K H h G w H v 6 e 4 q 3 u s j v v J T N t V K / g X F V 8 L l R G I k x d y T 8 b k m T y Q V / L 5 5 y z H n T H x 0 s d V n m q p 2 Q p d 7 J Q + / l V p u H I 4 + 1 b N 9 c y h D W n X K 0 P v p s t M b q F M 9 b 3 z q 3 E p U 4 w 7 e + S W v K H / G z I i T 3 g D v f e u 3 B V o c T j H j 4 x e B h i P + D u M W V B J J s R U I l k 4 i G W j X l B + 2 I U o 7 G M a h 5 C F I 8 h D 2 U 3 h E o Z w L Q Q F U U g L m W m r 4 P M 0 2 / C j h N w X c 1 u S r A = = < / l a t e x i t > k 4

< l a t e x i t s h a 1 _ b a s e 6 4 = " 5 j i b + t i Y b E 7 / i P k 4 q m w g 4 t J g / e 0 = " > A 

A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W S S

f D m V s U 2 u p Z C y 4 q h G l Z N l m y q M p 2 W O e M q r Z k W l T R Z p V W 5 k 5 u c V 3 v U s p m h H / O + S Z u a d K q z N l M k j l S t I W t O Z 9 B K t c I x k i B u R W a B 6 I E Y e J U 3 w o / Q g B M w Q I E u a E B B B 4 5 Y B Q l s f O o g A g E T u S Y 4 y F m I m H t O Y Q A B 1 H a x i 2 K H h G w H v 6 e 4 q 3 u s j v v J T N t V K / g X F V 8 L l R G I k x d y T 8 b k m T y Q V / L 5 5 y z H n T H x 0 s d V n m q p 2 Q p d 7 J Q + / l V p u H I 4 + 1 b N 9 c y h D W n X K 0 P v p s t M b q F M 9 b 3 z q 3 E p U 4 w 7 e + S W v K H / G z I i T 3 g D v f e u 3 B V o c T j H j 4 x e B h i P + D u M W V B J J s S D R L K Q i m W j X l B + 2 I U o 7 G M a h 5 C F I 8 h D 2 U 3 h E o Z w L Q Q F U U g L m W m r 4 P M 0 2 / C j h N w X d X m S r Q = = < / l a t e x i t > k 5

< l a t e x i t s h a 1 _ b a s e 6 4 = " S 5 r 3 

S O W y 7 Y z 0 r h v / M / L c z V 6 B b Y U = " > A A A C i X i c h V G 7 T g J B F L 2 s L w Q V 1 M b E h k A w V m Q W N R I q E h p L H v J I

U u h J c V Q D a s q S z Z V m U 5 L n H G V V k 2 L S p q s 0 o r c z o 7 P K 1 1 q 2 c z Q j 3 n P p A 1 N O t V Z i y k S R 6 p a l z W n 3 W 8 e N M M x k i B u R a a B 6 I E Y e J U z w o 9 Q h x M w Q I E O a E B B B 4 5 Y B Q l s f G o g A g E T u Q Y 4 y F m I m H t O o Q 8 B 1 H a w i 2 K H h G w b v 6 e 4 q 3 m s j v v x T N t V K / g X F V 8 L l R G I k x d y T 0 b k m T y Q V / L 5 5 y z H n T H 2 0 s N V n m i p 2 Q x d b B U / / l V p u H I 4 + 1 b N 9 M y h B S n X K 0 P v p s u M b 6 F M 9 N 3 z q 1 E x X Y g 7 O + S W v K H / G z I k T 3 g D v f u u 3 O V p Y T D D j 4 x e + h i P + D u M a V B O J s S 9 R D K / H 8 t E v a D 8 s A 1 R 2 M U 0 D i E D R 5 C D k p v C J Q z g W g g K o p A S

= " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U A w T u Q V T S R M J C y O f M h H A o S 0 9 Y E v 9 C t t a Y I N f 8 D R x Q E X T R

M j M t Q s Y B b m F x a X k l u B o K r 6 1 v R K K b W 1 V T 6 x s S r U i a r B l 1 U T C p z F R a s Z g l 0 7 p u U E E R Z V o T e 3 n 3 v G Z T w 2 S a e m I N d N p S h K 7 K O k w S L K T q T V F x 7 G G b b 0 c T J E W 8 i s 0 C 3 g c J 8 K u g R R + h C a e g g Q R 9 U I C C C h Z i G Q Q w 8 W k A D w R 0 5 F r g I G c g Y t 4 5 h S G E U N v H L o o d A r I 9 / H Z x 1 / B Z F f f u T N N T S / g X G V

i i E w z C 3 9 X n d F V 2 v N L z Q + 9 U 9 Q = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U A w T u Q V T C R M J C y O f M h H A o S 0 9 Y E v 9 i t t a Y I N f 8 D R x Q E X T R

M j M t Q s Y B b m F x a X k l u B o K r 6 1 v R K K b W z V T 6 x s S r U q a r B k N U T C p z F R a t Z g l 0 4 Z u U E E R Z V o X z w r u e d 2 m h s k 0 9 d g a 6 L S t C D 2 V d Z k k W E g 1 W q L i 2 M N O p h N N k B T x K j Y L e B 8 k w K + i F n 2 E F p y A B h L 0 Q Q E K K l i I Z R D A x K c J P B D Q k W u D g 5 y B i H n n F I Y Q Q m 0 f u y h 2 C M i e 4

b e H u 6 b P q r h 3 Z 5 q e W s K / y P g a q I x B k r y Q e z I h z + S B v J L P P 2 c 5 3 g z X y w B X c a q l e i d y s V P 5 + F e l 4 G r B 6 b d q r m c L u p D 1 v D L 0 r n u M e w t p q r f P r y a V X D n p 7

J F b 8 o b + b 8 i Y P O E N V P t d u i v R 8 m i O H x G 9 D D E e / n c Y s 6 C W T v G Z V L p 0 k M j H / a C C s A t x 2 M c 0 D i E P R 1 C E q p f C J Y z g m g t z P J f l c t N W L u B r t u F H c Y U v i s a S t w = = < / l a t e x i t > v 4

< l a t e x i t s h a 1 _ b a s e 6 4 = " B y 1 / e Y 2 T n i 8 K s 3

x E L F 0 d D 8 X l b n Q = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U A w T u Q V S S R M J C y O f M h H A o S 0 9 Y E v 9 i t t a Y I N f 8 D R x Q E X T R y M u 3 / A

x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

M j M t Q s Y B b m F x a X k l u B o K r 6 1 v R K K b W z V T 6 x s S r U q a r B k N U T C p z F R a t Z g l 0 4 Z u U E E R Z V o X z w r u e d 2 m h s k 0 9 d g a 6 L S t C D 2 V d Z k k W E g 1 W q L i 2 M N O p h N N k B T x K j Y L e B 8 k w K + i F n 2 E F p y A B h L 0 Q Q E K K l i I Z R D A x K c J P B D Q k W u D g 5 y B i H n n F I Y Q Q m 0 f u y h 2 C M i e 4

b e H u 6 b P q r h 3 Z 5 q e W s K / y P g a q I x B k r y Q e z I h z + S B v J L P P 2 c 5 3 g z X y w B X c a q l e i d y s V P 5 + F e l 4 G r B 6 b d q r m c L u p D 1 v D L 0 r n u M e w t p q r f P r y a V X D n p 7

J F b 8 o b + b 8 i Y P O E N V P t d u i v R 8 m i O H x G 9 D D E e / n c Y s 6 C W T v E H q X Q p k 8 j H / a C C s A t x 2 M c 0 D i E P R 1 C E q p f C J Y z g m g t z P J f l c t N W L u B r t u F H c Y U v j O S S u A = = < / l a t e x i t > v 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " J 0 M e H W n k w d f k D Z V m 3 v O A v 3 f u + c g = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U A w T u Q V N R I m E h Z H P u Q j A U L a + t A X + p W 2 N M G G P + D o 4 o C L J g 7 G 3 T / g 4 h 9 w 4 C c Y R 0 x c H L w t T Y w S 8 T b t O + + 8 e 2 7 P y x F 1 m Z k W I a M A N z e / s L g U X A 6 F V 1 b X I t H 1 j a q p 9 Q y J V i R N 1 o y 6 K J h U Z i q t W M y S a V 0 3 q K C I M q 2 J 3 b x 7 X r O p Y T J N P b b 6 O m 0 p w q n K O k w S L K T q T V F x 7 E H 7 o B 1 N k B T x K j Y N e B 8 k w K + C F n 2 E J p y A B h L 0 Q A E K K l i I Z R D A x K c B P B D Q k W u B g 5 y B i H n n F A Y Q Q m 0 P u y h 2 C M

h 2 8 X u K u 4 b P q r h 3 Z 5 q e W s K / y P g a q I x B k r y Q e z I m z + S B v J L P P 2 c 5 3 g z X S x 9 X c a K l e j t y s V 

t L V N J Q i T c N X z 5 z z 0 = " > A A A C i X i c h V E 9 T 8 J Q F L 3 U L w Q V 1 M X E h U A w T u Q V T S R M J C y O f M h H A o S 0 9 Y E v 9 C t t a Y I N f 8 D R x Q E X T R y M u 3 / A

x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

M j M t Q s Y B b m F x a X k l u B o K r 6 1 v R K K b W 1 V T 6 x s S r U i a r B l 1 U T C p z F R a s Z g l 0 7 p u U E E R Z V o T e 3 n 3 v G Z T w 2 S a e m I N d N p S h K 7 K O k w S L K T q T V F x 7 G E 7 3 Y 4 m S I p 4 F Z s F v A 8 S 4 F d B i z 5 C E 0 5 B A w n 6 o A A F F S z E M g h g 4 t M A H g j o y L X A Q c 5 A x L x z C k M I o b a P X R Q 7 B G R 7 + O 3 i r u G z K u 7 d m a a n l v A v M r 4 G K m O Q J C / k n k z I M 3 k g r + T z z 1 m O N 8 P 1 M s B V n G q p 3

o 5 c 7 J Q / / l U p u F p w 9 q 2 a 6 9 m C D m Q 8 r w y 9 6 x 7 j 3 k K a 6 u 3 z q 0 k 5 W 0 o 6 e + S W v K H / G z I m T 3 g D 1 X 6 X 7 o q 0 N J r j R 0

Q v Q 4 y H / x 3 G L K i m U / x B K l 0 8 T O T i f l B B 2 I U 4 7 G M a R 5 C D Y y h A x U v h E k Z w z Y U 5 n s t w 2 W k r F / A 1 2 / C j u P w X i K i S t g = = < / l a t e x i t > AE BCA F E DA E 3I EE E A ED (c 1 ) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " v B H 8 w 8 W B q 7 y M P I e l n A e d n n B 0 6 / c = " > A A A C k 3 i c h V H L S s N A F D 3 G V 6 2 P R k U Q 3 I i l o p s y q Y K i m 6 I u 3 A j V W h W q h C S O G p o X S V q o I T / g D 7 j Q j Y K C u P c H 3 P g D L v w E c V n B j Q t v 0 4 C o q H e Y m T N n 7 r l z h q s 6 h u 7 5 j D 2 1 C e 0 d n V 3 d i Z 5 k b 1 / / Q E o c H N r y 7 K q r 8 Z J m G 7 a 7 o y o e N 3 S L l 3 z d N / i O 4 3 L F V A 2 + r V a W m / f b N e 5 6 u m 1 t + n W H 7 5 n K o a U f 6 J r i E y W L Y j C 1 q 5 q B F s q B F E 6 H s i S L a Z Z l U Y z / B F I M 0 o i j Y I t 3 2 M U + b G i o w g S H B Z + w A Q U e j T I k M D j E 7 S E g z i W k R / c c I Z K k r V I W p w y F 2 A q t h 3 Q q x 6 x F 5 2 Z N L 1 J r 9 I p B 0 y X l O D L s k d 2 w B n t g t + y Z v f 9 a K 4 h q N L 3 U a V d b W u 7 I q Z P R 4 t u / K p N 2 H 0 e f q j 8 9 + z j A f O R V J + 9 O x D R / o b X 0 t e P T R n F h I x N M s k v 2 Q v 4 v 2 B O 7 p x 9 Y t V f t a p 1 v n P 3 h R y U v I b V H + t 6 M n 2 A r l 5 V m s r n 1 2 X R + I m 5 U A m O Y w B R 1 Y w 5 5 r K K A E l W v 4 R x X u B Z G h E V h S V h p p Q p t s W Y Y X 0 J Y + w A u g Z X 0 < / l a t e x i t > (c 1 ) 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " x B 6 q 8 z s t p F H Z y y A + Y 3 m i N Z f N C L M = " > A A A C k 3 i c h V H L S s N A F D 2 N 7 2 e j I g h u p E X R T Z l U Q d F N U R d u B K u 2 C i o h i d M a z I s k L d S Q H / A H X O h G o Y K 4 9 w f c + A M u + g n i U s G N C 2 / T g K i o d 5 i Z M 2 f u u X O G q z q G 7 v m M N R J C W 3 t H Z 1 d 3 T 2 9 f / 8 B g U h w a L n p 2 x d V 4 Q b M N 2 9 1 V F Y 8 b u s U L v u 4 b f N d x u W K q B t 9 R j 1 e a 9 z t V 7 n q 6 b W 3 7 N Y c f m E r Z 0 k u 6 p v h E y a I Y T O + r Z q C F c i C F M 6 G c l c U 0 y 7 A o J n 4 C K Q Z p x L F h i 3 f Y x y F s a K j A B I c F n 7 A B B R 6 N P U h g c I g 7 Q E C c S 0 i P 7 j l C 9 J K 2 Q l m c M h R i j 2 k t 0 2 k v Z i 0 6 N 2 t 6 k V q j V w y a L i k n M M k e 2 Q 1 7 Y Q / s l j 2 x 9 1 9 r B V G N p p c a 7 W p L y x 0 5 e T q 2 9 f a v y q T d x 9 G n 6 k / P P k p Y i L z q 5 N 2 J m O Y v t J a + e n L 2 s r W 4 O R l M s S v 2 T P 4 v W Y P d 0 w + s 6 q t W z / P N 8 z / 8 q O Q l p P Z I 3 5 v x E x S z G W k 2 k 8 3 P p X O p u F H d G E c K 0 9 S N e e S w h g 0 U q H o V F 6 j j W h g V l o R l Y b W V K i R i z Q i + h L D + A T C f l f U = < / l a t e x i t > (c 1 ) 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " i f H A F x O A x 4 B H u N M 7 d a z l e d Z A 7 M 8 = " > A A A C k 3 i c h V H L S s N A F D 2 N r 1 p f U R E E N 2 K p 6 K Z M W k H R j a g L N 0 J 9 9 A E q I Y m j B v M i S Q s 1 5 A f 8 A R e 6 U a g g 7 v 0 B N / 6 A C z 9 B X C q 4 c e F t G h A V 9 Q 4 z c + b M P X f O c F X H 0 D 2 f s c e E 0 N b e 0 d m V 7 E 7 1 9 P b 1 D 4 i D Q y X P r r o a L 2 q 2 Y b s V V f G 4 o V u 8 6 O u + w S u O y x V T N X h Z P V p u 3 p d r 3 P V 0 2 9 r y 6 w 7 f N Z U D S 9 / X N c U n S h b F Y G p H N Q M t l A M p n A 7 l v C y m W Z Z F M f 4 T S D F I I 4 6 C L d 5 i B 3 u w o a E K E x w W f M I G F H g 0 t i G B w S F u F w F x L i E 9 u u c I k S J t l b I 4 Z S j E H t F 6 Q K f t m L X o 3 K z p R W q N X j F o u q Q c R 4 Y 9 s G v 2 w u 7 Z D X t i 7 7 / W C q I a T S 9 1 2 t W W l j v y w M n o 5 t u / K p N 2

H 4 e f q j 8 9 + 9 j H X O R V J + 9 O x D R / o b X 0 t e P T l 8 3 5 j U w w y S 7 Z M / m / Y I / s j n 5 g 1 V 6 1 x j r f O P v D j 0 p e Q m q P 9 L 0 Z P 0 E p l 5 X y 2 d z 6 < l a t e x i t s h a 1 _ b a s e 6 4 = " g Z T f w

T H p x I m 5 U E m O Y w B R 1 Y x a L W E U B R a p e w z k a u B J G h A V h S V h p p Q q J W D O M L y G s f Q A y v Z X 2 < / l a t e x i t > (c 1 ) 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " B 5 S y s K i M 4 0 L d n O l U b j l f N Q p y y K c = " > A A A C k 3 i c h V H L S s N A F D 2 N 7 / q K i i C 4 k R a l b s p E B U U 3 o i 7 c C G 2 1 K m g J S Z z W Y F 4 k a U F D f s A f c K E b h Q r i 3 h 9 w 4 w + 4 8 B P E Z Q U 3 L r x N A 6 K i 3 m F m z p y 5 5 8 4 Z r u o Y u u c z 9 p Q Q 2 t o 7 O r u 6 e 5 K 9 f f 0 D g + L Q 8 L Z n V 1 2 N F z X b s N 1 d V f G 4 o V u 8 6 O u + w X c d l y u m a v A d 9 W i 1 e b 9 T 4 6 6 n 2 9 a W f + z w k q l U L L 2 s a 4 p P l C y K Q W Z f N Q M t l A M p n A 7 l O V l M s y y L Y u I n k G K Q R h w 5 W 7 z D P g 5 g Q 0 M V J j g s + I Q N K P B o 7 E E C g 0 N c C Q F x L i E 9 u u c I k S R t l b I 4 Z S j E H t F a o d N e z F p 0 b t b 0 I r V G r x g 0 X V J O Y J I 9 s h v W Y A / s l j 2 z 9 1 9 r B V G N p p d j 2 t W W l j v y 4 O n Y 5 t u / K p N 2 H 4 e f q j 8 9 + y h j I f K q k 3 c n Y p q / 0 F r 6 2 s l Z Y 3 O x M B l M s S v 2 Q v 4 v 2 R O 7 p x 9 Y t V e t n u e F 8 z / 8 q O Q l p P Z I 3 5 v x E 2 z P Z K X Z 7 E x + L r 2 c i h v V j X G k k K F u z G M Z 6 8 i h S N V r u E A d 1 8 K o s C S s C G u t V C E R a 0 b w J Y S N D z T b l f c = < / l a t e x i t > (c 1 ) 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " A K k 1 W f v L g B 1 A G c V 1 W S n I K F T c I k I = " > A A A C k 3 i c h V H L S s N A F D 3 G V 6 2 P R k U Q 3 I h F q Z s y q Y q i G 1 E X b o T 6 q A p a Q h J H D c 2 L J A 3 U k B / w B 1 z o R k F B 3 P s D b v w B F 3 6 C u F R w 4 8 L b N C A q 6 h 1 m 5 s y Z e + 6 c 4 a q O o X s + Y 4 9 N Q n N L a 1 t 7 q i P d 2 d X d k x F 7 + z Y 9 u + p q v K T Z h u 1 u q 4 r H D d 3 i J V / 3 D b 7 t u F w x V Y N v q Z X F + v 1 W w F 1 P t 6 0 N v + b w s q k c W P q + r i k + U b I o h r l d 1 Q y 1 S A 6 l a D y S p 2 Q x y / I s j u G f Q E p A F k k U b f E W u 9 i D D Q 1 V m O C w 4 B M 2 o M C j s Q M J D A 5 x Z Y T E u Y T 0 + J 4 j Q p q 0 V c r i l K E Q W 6 H 1 g E 4 7 C W v R u V 7 T i 9 U a v W L Q d E k 5 j F H 2 w K 7 Z C 7 t n N + y J v f 9 a K 4 x r 1 L 3 U a F c b W u 7 I m e P B 9 b d / V S b t P g 4 / V X 9 6 9 r G P m d i r T t 6 d m K n / Q m v o g 6 O T l / X Z t d F w j F 2 w Z / J / z h 7 Z H f 3 A C l 6 1 y 1 W + d v q H H 5 W 8 R N Q e 6 X s z f o L N Q l 6 a y B d W J 7 P z I 0 m j U h j C C H L U j W n M Y x l F l K h 6 g D N c 4 k o Y E O a E B W G p k S o 0 J Z p + f A l h 5 Q M 2 + Z X 4 < / l a t e x i t > ⇥ < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 Y T q + n 0 N 3 G K j 0 V e q s 0 7 3 e n 2 G A b A = " > A A A C h 3 i c h V F N L 0 N B F D 1 9 v l p f L T Y S m 6 Y N s a p 5 J Y h V x c Y S 1 Z I g 8 t 4 z r d H 3 l f e m T W j 6 B 6 z s B C s S C 7 H 3 B 2 z 8 A Q s / Q S w r s b F w + / o S Q X A n M 3 P m z D 1 3 z u T q r i l 8 y d h T R O n o 7 O r u i c Z 6 + / o H B u O J o e G i 7 1 Q 9 g x c M x 3 S 8 T V 3 z u S l s X p B C m n z T 9 b h m 6 S b f 0 C t L r f u N G v d 8 4 d j r 8 t D l O 5 Z W t k V J G J o k q r g t h c X 9 3 U S a Z V g Q y Z 9 A D U E a Y a w 4 i T t s Y w 8 O D F R h g c O G J G x C g 0 9 j C y o Y X O J 2 U C f O I y S C e 4 4 G e k l b p S x O G R q x F V r L d N o K W Z v O r Z p + o D b o F Z O m R 8 o k x t k j u 2 F N 9 s B u 2 T N 7 / 7 V W P a j R 8 n J I u 9 7 W c n c 3 f j y a f / t X Z d E u s f + p + t O z R A n z g V d B 3 t 2 A a f 3 C a O t r R 6 f N / M L a e H 2 C X b E X 8 n / J n t g 9 / c C u v R r X q 3 z t 4 g 8 / O n l p U H v U 7 8 3 4 C Y r Z j D q d y a 7 O p H O p s F F R j C G F S e r G H H J Y x g o K V P 0 A J z j D u R J T p p R Z Z b 6 d q k R C z Q i + h L L 4 A c v O k f Y = < / l a t e x i t > ( E D BCA F E DF W Q , b Q < l a t e x i t s h a 1 _ b a s e 6 4 = " m Q a c I I r P E / S c d J 4 E L r f m 6 n z h F M g = " > A A A C j 3 i c h V G 7 S g N B F D 1 Z X z E + k m g j 2 A R D x E L C J A o R C w n Y a J e H M U I e s r u O c c m + 2 N 0 E Y o g f 4 A 8 o W C V g I f b + g I 0 / Y J F P E E s F G w t v N g u i o t 5 h Z s 6 c u e f O G a 5 k q o r t M N b 3 C S O j Y + M T / s n A 1 P T M b D A U n t u 3 j Y Y l 8 4 J s q I Z 1 I I k 2 V x W d F x z F U f m B a X F R k 1 R e l O r b g / t i k 1 u 2 Y u h 7 T s v k F U 2 s 6 c q x I o s O U d V i N b s a O S t L W l v q V L O H o S i L M z c i P 0 H C A 1 F 4 k T F C d y j j C A Z k N K C B Q 4 d D W I U I m 0 Y J C T C Y x F X Q J s 4 i p L j 3 H B 0 E S N u g L E 4 Z I r F 1 W m t 0 K n m s T u d B T d t V y / S K S t M i Z Q Q x 9 s h u 2 A t 7 Y L f s i b 3 / W q v t 1 h h 4 a d E u D b X c P A y e L + T f / l V p t D s 4 + V T 9 6 d n B M T Z c r w p 5 N 1 1 m 8 A t 5 q G + e X r z k N 3 O x 9 j L r s W f y 3 2 V 9 d k 8 / 0 J u v 8 n W W 5 6 7 + 8 C O R l w 6 1 J / G 9 G T / B f j K e W I s n s + v R 9 J L X K D 8 W s Y Q V 6 k Y K a e w g g w J V t 3 C J L n p C W E g J W 0 J 6 m C r 4 P M 0 8 v o S w + w F o v p T M < / l a t e x i t > W K , b K < l a t e x i t s h a 1 _ b a s e 6 4 = " B I J E v b Y n 5 L A 4 d 2 G 7 l / v l L C X c 6 S k = " > A A A C j 3 i c h V G 7 S g N B F D 1 Z 3 / E V t R F s g i F i I W F W B c V C A j a K j R r z g M S E 3 X U S l + y L 3 U 1 A l / g B / o C C l Y K F 2 P s D N v 6 A h Z 8 g l h F s L L y 7 W R A V 4 x 1 m 5 s y Z e + 6 c 4 c q W p j o u Y 8 8 R o a e 3 r 3 9 g c C g 6 P D I 6 N h 6 b m M w 5 Z s N W e F Y x N d M u y J L D N d X g W V d 1 N V 6 w b C 7 p s s b z c n 3 D v 8 8 3 u e 2 o p r H v H l v 8 Q J d q h l p V F c k l q p w v b y / E T 0 u y 7 s m t 8 n Y l l m A p F k T 8 N x B D k E A Y O 2 b s H i U c w o S C B n R w G H A J a 5 D g 0 C h C B I N F 3 A E 8 4 m x C a n D P 0 U K U t A 3 K 4 p Q h E V u n t U a n Y s g a d P Z r O o F a o V c 0 m j Y p 4 0 i y J 3 b L 2 u y R 3 b E X 9 v F n L S + o 4 X s 5 p l 3 u a L l V G T + b z r z / q 9 J p d 3 H 0 p e r q 2 U U V q 4 F X l b x b A e P / Q u n o m y f n 7 c z a X t K b Y 9 f s l f x f s W f 2 Q D 8 w m m / K z S 7 f u + z i R y Y v L W q P + L M Z v 0 F u M S U u p R Z 3 l x P p 2 b B R g 5 j B L O a p G y t I Y x M 7 y F J 1 G x e 4 w r U w I a w I 6 0 K 6 k y p E Q s 0 U v o W w 9 Q l P F J T A < / l a t e x i t > W V , b V < l a t e x i t s h a 1 _ b a s e 6 4 = " g T f J F F O I j 4 F V b l k + X G p O 8 g D k f D Y = " > A A A C k 3 i c h V G 7 S g N B F D 2 u r x g f W R V B s F k S I h Y S J i o o 2 g S 1 s B H U m E S I G n b X S V z c F 7 u b Q A z x A / w B C 2 0 U I o i 9 P 2 D j D 1 j k E 8 R S w c b C m 8 2 C q K h 3 m J k z Z + 6 5 c 4 a r 2 L r m e o w 1 O 4 T O r u 6 e 3 l B f u H 9 g c C g i D o 9 k X a v s q D y j W r r l 7 C i y y 3 X N 5 B l P 8 3 S + Y z t c N h S d 5 5 S j l d Z 9 r s I d V 7 P M b a 9 q 8 z 1 D L p l a U V N l j 6 i C K O b 2 s 9 L 0 i S T t K k Z N q e 9 n C 2 K M J Z g f 0 k + Q D E A M Q W x Y 4 h 1 2 c Q A L K s o w w G H C I 6 x D h k s j j y Q Y b O L 2 U C P O I a T 5 9 x x 1 h E l b p i x O G T K x R 7 S W 6 J Q P W J P O r Z q u r 1 b p F Z 2 m Q 0 o J c f b I b t g L e 2 C 3 7 I m 9 / 1 q r 5 t d o e a n S r r S 1 3 C 5 E T s f T b / + q D N o 9 H H 6 q / v T s o Y g F 3 6 t G 3 m 2 f a f 1 C b e s r x 2 c v 6 c W t e G 2 S X b F n 8 n / J m u y e f m B W X t X G J t 8 6 / 8 O P Q l 7 q 1 J 7 k 9 2 b 8 B N m Z R H I 2 M b M 5 F 0 t F g 0 a F M I E o p q g b 8 0 h h D R v I U P U K L t D A t T A m L A n L w m o 7 V e g I N K P 4 E s L 6 B + E a l V s = < / l a t e x i t > CA E A EA DF DB3 D W O < l a t e x i t s h a 1 _ b a s e 6 4 = " O 6 F 2 X c 3 / V 2 p J k R F 8 E Q r V m G G i b l w = " > A A A C h H i c h V G 7 S g N B F D 2 u G m N 8 R W 0 E m 5 A Q s Z A w i Y p i I Q E b O / M w D 4 g x 7 K 6 T u L j Z X X Y 3 g R j y A 4 K t K a w U L M T e H 7 D x B y z y C W I Z w c b C m 8 2 C a D D e Y W b O n L n n z h m u Z K i K Z T P W G R F G x 8 Y 9 E 9 5 J 3 9 T 0 z O y c f 3 4 h a + k 1 U + Y Z W V d 1 M y + J F l c V j W d s x V Z 5 3 j C 5 W J V U n p P O 9 n r 3 u T o 3 L U X X D u 2 G w Y t V s a I p Z U U W b a L S u e O D k j / E I s y J w C C I u i A E N x K 6 / x F H O I E O G T V U w a H B J q x C h E W j g C g Y D O K K a B J n E l K c e 4 4 W f K S t U R a n D J H Y M 1 o r d C q 4 r E b n X k 3 L U c v 0 i k r T J G U A Y f b C 7 l m X P b M H 9 s o + / 6 z V d G r 0 v D R o l / p a b p T m L p b S H / + q q r T b O P 1 W D f V s o 4 x t x 6 t C 3 g 2 H 6 f 1 C 7 u v r 5 + 1 u e i c V b q 6 w W / Z G / m 9 Y h z 3 R D 7 T 6 u 3 y X 5 K n r I X 4 k 8 t K i 9 k R / N 2 M Q Z G O R 6 H o k l t w I x Y N u o 7 x Y R h C r 1 I 0 t x L G P B D J U v Y J L X K E t e I Q 1 Y V 3 Y 7 K c K I 6 5 m E T 9 C 2 P 0 C N b + Q X g = = < / l a t e x i t > CA E A EA AFEBFE DB3 FEBFE 3EFC G EAC h v(l) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " V u N 5 w f W o w D + B F f 3 0 B + W a e c F M I / M = " > A A A C k n i c h V H J T s J Q F L 3 U C X G g D g s T N w S C w Q 1 5 R R M N K w w b F y 4 Y Z E g A S V s f 0 N A p b S H B h h / w B 1 y w 0 s j C u P c H 3 P g D L v g E 4 x I T N y 6 8 L U 2 M G v E 2 7 T v v v H t u z 8 s R d F k y L U J G P m Z m d m 5 + w b 8 Y W F p e W Q 2 y a + t F U + s Y I i 2 I m q w Z Z Y E 3 q S y p t G B J l k z L u k F 5 R Z B p S W i n n f N S l x q m p K m n V k + n N Y V v q l J D E n k L q T o b r A q K 3 e r X u T O 7 G 5 N 3 + 3 U 2 Q u L E r d B v w H k g A l 5 l N P Y B q n A O G o j Q A Q U o q G A h l o E H E 5 8 K c E B A R

I m i 5 h l F z H U + c P 1 F / e 8 R 5 R M = " > A A A C l H i c h V H L S s N A F D 2 N r 1 o f b R V E c C O W i i 4 s k y o o 4 k I Q w Z W 0 a r X Q a k n i q M G 8 S N J K D f 0 B f 8 C F u F B Q E f f + g B t / w I W f I C 4 V 3 L j w J g 2 I i n q H m T l z 5 p 4 7 Z 7 i y p a m O y 9 h j R G h p b W v v i H b G u r p 7 e u O J Z N + 6 Y 1 Z t h R c U U z P t o i w 5 X F M N X n B V V + N F y + a S L m t 8 Q 9 5 f 8 O 8 3 a t x 2 V N N Y c + s W 3 9 S l X U P d U R X J J a q S S J Z l 3 d t r V M Q t r z a m T Y j j j U o i x T I s i O G f Q A x B C m H k z M Q t y t i G C Q V V 6 O A w 4 B L W I M G h U Y I I B o u 4 T X j E 2 Y T U 4 J 6 j g R h p q 5 T F K U M i d p / W X T q V Q t a g s 1 / T C d Q K v a L R t E k 5 j D R 7 Y N f s h d 2 z G / b E 3 n + t 5 Q U 1 f C 9 1 2 u W m l l u V + N H g 6 t u / K p 1 2 F 3 u f q j 8 9 u 9 j B T O B V J e 9 W w P i / U J r 6 2 u H x y + r s S t o b Z e f s m f y f s U d 2 R z 8 w a q / K R Z 6 v n P z h R y Y v f n v E 7 8 3 4 C d a z G X E y k 8 1 P p e Z H w k Z F M Y Q R j F E 3 p j G P J e R Q o O o H O M U l r o Q B Y U 5 Y E B a b q U I k 1 P T j S w j L H 5 O h l h k = < / l a t e x i t > h v(l 1) 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " Q D Q y 3 g Y / i i C R q P 2 + x V B k L e p X 4 Z E = " > A A A C l H i c h V H L S s N A F D 2 N r / p s V R D B T b E o u r B M q q C I C 0 E E V 2 K r V c F

H S e J U g 3 m R p J E a + g P + g A t x o a A i 7 v 0 B N / 6 A C z 9 B X C q 4 c e F N G h A t 1 j v M z J k z 9 9 w 5 w 5 U t T X V c x p 5 j Q l N z S 2 t b v L 2 j s 6 u 7 J 5 H s 7 V t 3 z L K t 8 I J i a q a 9 K 

U s O 1 1 S D F 1 z V 1 f i m Z X N J l z W + I R 8 u B P c b H r c d 1 T T W 3 I r F d 3 R p 3 1 B L q i K 5 R B W T v d u y 7 h 9 U i 9 l d 3 x v T J s T x a j G Z Z h k W R q o e i

I Q x j j L o x j X k s Y Q U F q n 6 E c 1 z j R h g Q 5 o Q F Y b G W K s Q i T T 9 + h L D 8 B Z X I l h o = < / l a t e x i t > h v(l 1) 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " r I G U J S j 2 y L x R 7 P P o m 5 v j 4 d E B M C Q = " > A A A C l H i c h V H L S s N A F D 2 N r 1 o f b R V E c C M t i i 4 s E x U U c S E U w Z X U R 6 v g o y R x t K F 5 k a Q V D f 0 B f 8 C F u F B Q E f f + g B t / w E U / Q V x W c O P C m z Q g K u o d Z u b M m X v u n O H K l q Y 6 L m P 1 i N D S 2 t b e E e 2 M d X X 3 9 M Y T y b 6 C Y 1 Z s h e c V U z P t T V l y u K Y a P O + q r s Y 3 L Z t L u q z x D b m c 9 e 8 3 q t x 2 V N N Y d 4 8 s v q N L B 4 a 6 r y q S S 1 Q x k d y W d a 9 U K 0 7 t e t U x b U I c r x U T a Z Z h Q Q z / B G I I 0 g g j Z y b u s Y 0 9 m F B Q g Q 4 O A y 5 h D R I c G l s Q w W A R t w O P O J u Q G t x z 1 B A j b Y W y O G V I x J Z p P a D T V s g a d P Z r O o F a o V c 0 m j Y p h z H C n t g t a 7 B H d s e e 2 f u v t b y g h u / l i H a 5 q e V W M X 4 y u P b 2 r 0 q n 3 U X p U / W n Z x f 7 m A 2 8 q u T d C h j / F 0 p T X z 0 + b a z N r Y 5 4 o + y S v Z D / C 1 Z n D / Q D o / q q X K 3 w 1 b M / / M j k x W + P + L 0 Z P 0 F h M i N O Z S Z X p t M L q b B R U Q w h h T H q x g w W s I Q c 8 l T 9 E O e 4 x o 0 w I M w L W W G x m S p E Q k 0 / v o S w / A G X 7 5 Y b < / l a t e x i t > h v(l 1) 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " o l h S N / W 5 X 8 / C n j h b b M g Z m c g 3 D F k = " > A A A C l H i c h V H L S s N A F D 2 N r 1 o f r Q o i u J E W R R e W i R Y U c S E U w Z X U R 6 v g o y R x t K F 5 k a Q V D f 0 B f 8 C F u F B Q E f f + g B t / w E U / Q V x W c O P C m z Q g K u o d Z u b M m X v u n O H K l q Y 6 L m P 1 i N D S 2 t b e E e 2 M d X X 3 9 M Y T f f 0 F x 6 z Y C s 8 r p m b a m 7 L k c E 0 1 e N 5 V X Y 1 v W j a X d F n j G 3 I 5 6 9 9 v V L n t q K a x 7 h 5 Z f E e X D g x 1 X 1 U k l 6 h i o m 9 b 1 r 1 S r Z j Z 9 a r j 2 q Q 4 U S s m U i z N g h j 5 C c Q Q p B B G z k z c Y x t 7 M K G g A h 0 c B l z C G i Q 4 N L Y g g s E i b g c e c T Y h N b j n q C F G 2 g p l c c q Q i C 3 T e k C n r Z A 1 6 O z X d A K 1 Q q 9 o N G 1 S j m C U P b F b 1 m C P 7 I 4 9 s / d f a 3 l B D d / L E e 1 y U 8 u t Y v x k a O 3 t X 5 V O u 4 v S p + p P z y 7 2 M R t 4 V c m 7 F T D + L 5 S m v n p 8 2 l i b W x 3 1 x t g l e y H / F 6 z O H u g H R v V V u V r h q 2 d / + J H J i 9 8 e 8 X s z f o L C V F q c T k + t Z F I L y b B R U Q w j i X H q x g w W s I Q c 8 l T 9 E O e 4 x o 0 w K M w L W W G x m S p E Q s 0 A v o S w / A G a F p Y c < / l a t e x i t > h v(l 1) 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " u h x Q K F O Z G B e L 2 2 F y R e j e x N z 2 h I E = " > A A A C l H i c h V H L S s N A F D 2 N r / p s q y C C m 2 J R 6 s I y 8 Y E i L o Q i u B K r V g u t l i R O N Z g X S V r R 0 B / w B 1 y I C w U V c e 8 P u P E H X P g J 4 l L B j Q t v 0 o C o q H e Y m T N n 7 r l z h i t b m u q 4 j D 1 G h K b m l t a 2 a H t H Z 1 d 3 T y y e 6 F 1 3 z K q t 8 L x i a q Z d k C W H a 6 r B 8 6 7 q a r x g 2 V z S Z Y 1 v y H t Z / 3 6 j x m 1 H N Y 0 1 9 8 D i m 7 q 0 Y 6 g V V Z F c o s r x R E n W v d 1 6 e W r L q 6 W 1 M X G 0 X o 6 n W I Y F k f w J x B C k E M a y G b 9 F C d s w o a A K H R w G X M I a J D g 0 i h D B Y B G 3 C Y 8 4 m 5 A a 3 H P U 0 U H a K m V x y p C I 3 a N 1 h 0 7 F k D X o 7 N d 0 A r V C r 2 g 0 b V I m M c w e 2 D V 7 Y f f s h j 2

x 9 1 9 r e U E N 3 8 s B 7 X J D y 6 1 y 7 G h g 9 e 1 f l U 6 7 i 9 1 P 1 Z + e X V Q w E 3 h V y b s V M P 4 v l I a + d n j 8 s j q 7 M u y N s H P 2 T P 7 

P 2 C O 7 o x 8 Y t V f l I s d X T v 7 w I 5 M X v z 3 i 9 2 b 8 B O v j G X E i M 5 6 b T M 0 P h Y 2 K Y h B D S F M 3 p j G P R S w j T 9 X 3 c Y p L X A n 9 w p y Q F R Y a q U I k 1 P T h S w h L H 5 w 9 l h 0 = < / l a t e x i t >

K = V = H v = (h v(l-1) 1 , ..., h v(l-1)

s-1 ) T ) (self attention). For simplicity, we focused on one query/output vector and one subspace.

F C G EAC , G EACD C G AFD C3E D E D DE B 3 F G EACD AE BCA F E DA E 3I EE E A ED ⇥

< l a t e x i t s h a 1 _ b a s e 6 4 = " 4 Y T q + n 0 N 3 G K j 0 V e q s 0 7 3 e n 2 G A 

b A = " > A A A C h 3 i c h V F N L 0 N B F D 1 9 v l p f L T Y S m 6 Y N s a p 5 J Y h V x c Y S 1 Z I g 8 t 4 z r d H 3 l f e m T W j 6 B 6 z s B C s S C 7 H 3 B 2 z 8 A Q s / Q S w r s b F w + / o S Q X A n M 3 P m z D 1 3 z u T q r i l 8 y d h T R O n o 7 O r u i c Z 6 + / o H B u O J o e G i 7 1 Q 9 g x c M x 3 S 8 T V 3 z u S l s X p B C m n z T 9 b h m 6 S b f 0 C t L r f u N G v d 8 4 d j r 8 t D l O 5 Z W t k V J G J o k q r g t h c X 9 3 U S a Z V g Q y Z 9 A D U E a Y a w 4 i T t s Y w 8 O D F R h g c O G J G x C g 0 9 j C y o Y X O J 2 U C f O I y S C e 4 4 G e k l b p S x O G R q x F V r L d N o K W Z v O r Z p + o D b o F Z O m R 8 o k x t k j u 2 F N 9 s B u 2 T N 7 / 7 V W P a j R 8 n J I u 9 7 W c n c 3 f j y a f / t X Z d E u s f + p + t O z R A n z g V d B 3 t 2 A a f 3 C a O t r R 6 f N / M L a e H 2 C X b E X 8 n / J n t g 9 / c C u v R r X q 3 z t 4 g 8 / O n l p U H v U 7 8 3 4 C Y r Z j D q d y a 7 O p H O p s F F R j C G F S e r G H H J Y x g o K V P 0 A J z j D u R J T p p R Z Z b 6 d q k R C z Q i + h L L 4 A c v O k f Y = < / l a t e x i t > ( E D BCA F E DF W Q , b Q < l a t e x i t s h a 1 _ b a s e 6 4 = " m Q a c I I r P E / S c d J 4 E L r f m 6 n z h F M g = " > A A A C j 3 i c h V G 7 S g N B F D 1 Z X z E + k m g j 2 A R D x E L C J A o R C w n Y a J e H M U I e s r u O c c m + 2 N 0 E Y o g f 4 A 8 o W C V g I f b + g I 0 / Y J F P E E s F G w t v N g u i o t 5 h Z s 6 c u e f O G a 5 k q o r t M N b 3 C S O j Y + M T / s n A 1 P T M b D A U n t u 3 j Y Y l 8 4 J s q I Z 1 I I k 2 V x W d F x z F U f m B a X F R k 1 R e l O r b g / t i k 1 u 2 Y u h 7 T s v k F U 2 s 6 c q x I o s O U d V i N b s a O S t L W l v q V L O H o S i L M z c i P 0 H C A 1 F 4 k T F C d y j j C A Z k N K C B Q 4 d D W I U I m 0 Y J C T C Y x F X Q J s 4 i p L j 3 H B 0 E S N u g L E 4 Z I r F 1 W m t 0 K n m s T u d B T d t V y / S K S t M i Z Q Q x 9 s h u 2 A t 7 Y L f s i b 3 / W q v t 1 h h 4 a d E u D b X c P A y e L + T f / l V p t D s 4 + V T 9 6 d n B M T Z c r w p 5 N 1 1 m 8 A t 5 q G + e X r z k N 3 O x 9 j L r s W f y 3 2 V 9 d k 8 / 0 J u v 8 n W W 5 6 7 + 8 C O R l w 6 1 J / G 9 G T / B f j K e W I s n s + v R 9 J L X K D 8 W s Y Q V 6 k Y K a e w g g w J V t 3 C J L n p C W E g J W 0 J 6 m C r 4 P M 0 8 v o S w + w F o v p T M < / l a t e x i t > W K , b K < l a t e x i t s h a 1 _ b a s e 6 4 = " B I J E v b Y n 5 L A 4 d 2 G 7 l / v l L C X c 6 S k = " > A A A C j 3 i c h V G 7 S g N B F D 1 Z 3 / E V t R F s g i F i I W F W B c V C A j a K j R r z g M S E 3 X U S l + y L 3 U 1 A l / g B / o C C l Y K F 2 P s D N v 6 A h Z 8 g l h F s L L y 7 W R A V

v H l v 8 Q J d q h l p V F c k l q p w v b y / E T 0 u y 7 s m t 8 n Y l l m A p F k T 8 N x B D k E A Y O 2 b s H i U c w o S C B n R w G H A J a 5 D g 0 C h C B I N F 3 A E 8 4 m x C a n D P 0 U K U t A 3 K 4 p Q h E V u n t U a n Y s g a d P Z r O o F a o V c 0 m j Y p 4 0 i y J 3 b L 2 u y R 3 b E X 9 v F n L S + o 4 X s 5 p l 3 u a L l V G T + b z r z / q 9 J p d 3 H 0 p e r q 2 U U V q 4 F X l b x b A e P / Q u n o m y f n 7 c z a X t K b Y 9 f s l f x f s W f 2 Q D 8 w m m / K z S 7 f u + z i R y Y v L W q P + L M Z v 0 F u M S U u p R Z 3 l x P p 2 b B R g 5 j B L O a p G y t I Y x M 7 y F J 1 G x e 4 w r U w I a w I 6 0 K 6 k y p E Q s 0 U v o W w 9 Q l P F J T A < / l a t e x i t > W V , b V < l a t e x i t s h a 1 _ b a s e 6 4 = " g T f J F F O I j 4 F V b l k + X G p O 8 g D k f D Y = " > A A A C k 3 i c h V G 7 S g N B F D 2 u r x g f W R V B s F k S I h Y S J i o o 2 g S 1 s B H U m E S I G n b X S V z c F 7 u b Q A z x A / w B C 2 0 U I o i 9 P 2 D j D 1 j k E 8 R S w c b C m 8 2 C q K h 3 m J k z Z +

EQUATION

< l a t e x i t s h a 1 _ b a s e 6 4 = " j P q V p p d j i s e 0 U Y h i e a e s I D j

V 5 m E = " > A A A C i 3 i c h V G 7 S g N B F D 2 u 7 2 h M 1 E a w k Y S I V Z i N g h I s B B E s T W J M M I l h d 5 0 k i / t i d 7 O g I T 9 g L V i I g o K F 2 P s D N v 6 A R T 5 B L B V s L L z Z L I i K e o e Z O X P m n j t n u L K l q Y 7 L W K d P 6 B 8 Y H B o e G Q 2 N j Y c n I t H J q R 3 H b N o K z y u m Z t p F W X K 4 p h o 8 7 6 q u x o u W z S V d 1 n h B P l j v 3 h c 8 b j u q a W y 7 h x a v 6 F L d U G u q I r l E 7 Z Z l v d V o V 8 U 9 r x q N s y T z Y + 4 n E A M Q R x B b Z v Q O Z e z D h I I m d H A Y c A l r k O D Q K E E E g 0 V c B S 3 i b E K q f 8 / R R o i 0 T c r i l C E R e 0 B r n U 6 l g D X o 3 K 3 p + G q F X t F o 2 q S c Q 4 I 9 s h v 2 w h 7 Y L X t i 7 7 / W a v k 1 u l 4 O a Z d 7 W m 5 V I 8 c z u b d / V T r t L h q f q j 8 9 u 6 h h x f e q k n f L Z 7 q / U H p 6 7 + j 0 J Z f O J l r z 7 I o 9 k / 9 L 1 m H 3 9 A P D e 1 W u M z x 7 9 o c f m b y 0 q T 3 i 9 2 b 8 B D u p p L i Y T G W W 4 m u x o F E j m E U M C 9 S N Z a x h E 1 v I U 3 U D J z j H h R A W F o W 0 s N p L F f o C z T S + h L D x A X t g k 4 8 = < / l a t e x i t > h v 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " / U M X + u p g G u K s F 8 + v u Q J B M / 3 u i 0 E = " > A A A C i 3 i c h V H L S s N A F D 2 N r 1 o f r b o R 3 B S L 4 q p M W k E p L g Q R X F Z r b d H W k s R R Q / M i S Q M a + g O u B R e i o O B C 3 P s D b v w B F 3 6 C u F R w 4 8 K b N C A q 6 h 1 m 5 s y Z e + 6 c 4 c q W p j o u Y 4 8 x o a u 7 p 7 c v 3 p 8 Y G B w a T q Z G R j c c s 2 U r v K y Y m m l X Z c n h m m r w s q u 6 G q 9 a N p d 0 W e M V u b k U 3 F c 8 b j u q a a y 7 B x a v 6 9 K e o e 6 q i u Q S t V m T d X + / 3 c h t e 4 1 U h m V Z G O m f Q I x A B l E U z d Q t a t i B C Q U t 6 O A w 4 B L W I M G h s Q U R D B Z x d f j E 2 Y T U 8 J 6 j j Q R p W 5 T F K U M i t k n r H p 2 2 I t a g c 1 D T C d U K v a L R t E m Z x h R 7 Y N f s h d 2 z G / b E 3 n + t 5 Y c 1 A i 8 H t M s d L b c a y a P x 0 t u / K p 1 2 F / u f q j 8 9 u 9 j F f O h V J e 9 W y A S / U D p 6 7 / D k p V R Y m / K n 2 S V 7 J v 8 X 7 J H d 0 Q 8 M 7 1 W 5 W u V r p 3 / 4 k c l L m 9 o j f m / G T 7 C R y 4 r 5 b G 5 1 N r M 4 G T U q j g l M Y o a 6 M Y d F r K C I M l U 3 c I w z n A t D Q l 4 o C A u d V C E W a c b w J Y T l D 3 2 A k 5 A = < / l a t e x i t > h v 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 g S R J 7 k S a B e c z K c 0 Z x l / D x 8 7 u a E = " > A A A C i 3 i c h V H L S s N A F D 2 N r / q o r b o R 3 I h F c V U m t q C I i 4 I I L l u 1 V n y V J I 4 1 N C + S N K C h P + B a c C E K C i 7 E v T / g x h 9 w 0 U 8 Q l x X c u P A m D Y i K 9 Q 4 z c + b M P X f O c G V L U x 2 X s W Z M 6 O r u 6 e 2 L 9 w 8 M D i W G k 6 m R 0 U 3 H r N s K L y m m Z t p b s u R w T T V 4 y V V d j W 9 Z N p d 0 W e N l u b Y c 3 J c 9 b j u q a W y 4 x x b f 0 6 W q o R 6 q i u Q S t b 0 r 6 / 5 R o 5 L b 9 y q p N M u w M C Z / A z E C a U R R M F M P 2 M U B T C i o Q w e H A Z e w B g k O j R 2 I Y L C I 2 4 N P n E 1 I D e 8 5 G h g g b Z 2 y O G V I x N Z o r d J p J 2 I N O g c 1 n V C t 0 C s a T Z u U k 5 h m z + y O t d g T u 2 c v 7 O P P W n 5 Y I / B y T L v c 1 n K r k j w d X 3 / / V 6 X T 7 u L o S 9 X R s 4 t D L I R e V f J u h U z w C 6 W t 9 0 7 O W + u L a 9 P + D L t h r + T / m j X Z I / 3 A 8 N 6 U 2 y J f u + j g R y Y v D W q P + L M Z v 8 H m X E b M Z u a K u X R + K m p U H B O Y w i x 1 Y x 5 5 r K K A E l U 3 c I Z L X A k J I S s s C k v t V C E W a c b w L Y S V T 4 H A k 5 I = < / l a t e x i t > h v 5 < l a t e x i t s h a 1 _ b a s e 6 4 = " V b t 3 w 2 J R t R 5 s G u P p 5 d O K k M j V z g 8 = " > A A A C i 3 i c h V H L S s N A F D 3 G d 3 1 V 3 Q h u i k V x V S Z V U Y o L Q Q S X f V g V b S 1 J n L b B v E j S Q A 3 9 A d e C C 1 F Q c C H u / Q E 3 / o A L P 0 F c K r h x 4 U 0 a E B X 1 D j N z 5 s w 9 d 8 5 w Z U t T H Z e x x w 6 h s 6 u 7 p 7 e v P z Y w O D Q 8 E h 8 d 2 3 T M h q 3 w o m J q p r 0 t S w 7 X V I M X X d X V + L Z l c 0 m X N b 4 l H 6 w G 9 1 s e t x 3 V N D b c p s X L u l Q z 1 K q q S C 5 R O y V Z 9 + u t y s K e V 4 k n W Y q F k f g J x A g k E U X W j N + i h H 2 Y U N C A D g 4 D L m E N E h w a u x D B Y B F X h k + c T U g N 7 z l a i J G 2 Q V m c M i R i D 2 i t 0 W k 3 Y g 0 6 B z W d U K 3 Q K x p N m 5 Q J T L M H d s 1 e 2 D 2 7 Y U / s / d d a f l g j 8 N K k X W 5 r u V U Z O Z o o v P 2 r 0 m l 3 U f 9 U / e n Z R R V L o V e V v F s h E / x C a e u 9 w 5 O X Q i Y / 7 c + w S / Z M / i / Y I 7 u j H x j e q 3 K V 4 / n T P / z I 5 K V F 7 R G / N + M n 2 E y n x L l U O j e f X J m K G t W H S U x h l r q x i B W s I 4 s i V T d w j D O c C 0 P C n J A R l t u p Q k e k G c e X E N Y + A I P g k 5 M = < / l a t e x i t > h v s < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 N t g h L i v + R 1 q S B S / 2 2 o X j F + l w J A = " > A A A C i 3 i c h V H L S s N A F D 3 G V 6 2 P V t 0 I b q R F c V U m V l C K i 4 I I L v u w K r 5 K E s c a m h d J G q i h P + B a c C E K C i 7 E v T / g x h 9 w 0 U 8 Q l w p u X H i T B k R F v c P M n D l z z 5 0 z X N n S V M d l r N 0 l d P f 0 9 v X H B u K D Q 8 M j i e T o 2 L p j N m y F V x R T M + 1 N W X K 4 p h q 8 4 q q u x j c t m 0 u 6 r P E N u b 4 c 3 G 9 4 3 H Z U 0 1 h z m x b f 1 a W a o R 6 o i u Q S t b U j 6 / 5 h q + r s e d V k m m V Y G F M / g R i B N K I o m M k 7 7 G A f J h Q 0 o I P D g E t Y g w S H x j Z E M F j E 7 c I n z i a k h v c c L c R J 2 6 A s T h k S s X V a a 3 T a j l i D z k F N J 1 Q r 9 I p G 0 y b l F K b Z I 7 t h L + y B 3 b I n 9 v 5 r L T + s E X h p 0 i 5 3 t N y q J o 4 n y m / / q n T a X R x + q v 7 0 7 O I A i 6 F X l b x b I R P 8 Q u n o v a P T l 3 K u N O 3 P s C v 2 T P 4 v W Z v d 0 w 8 M 7 1 W 5 L v L S 2 R 9 + Z P L S o v a I 3 5 v x E 6 z P Z c R s Z q 4 4 n 8 6 n o k b F M I k U Z q k b C 8 h j F Q V U q L q B E 5 z j Q h g W s k J O W O q k C l 2 R Z h x f Q l j 5 A A e v k 9 E = < / l a t e x i t > h e 1,s < l a t e x i t s h a 1 _ b a s e 6 4 = " h F a c X 4 1 9 J w c z 2 9 W n 9 6 Q U Y 9 2 0 I m c = " > A A A C j 3 i c h V H L S s N A F D 3 G V 6 2 P V t 0 I b q R F c S F l U g X F h R T c 6 K 4 + W g W t J Y n T N j Q v k r S g I T / g D y i 4 a s G F u P c H 3 P g D L v w E c a n g x o U 3 a U C 0 W O 8 w M 2 f O 3 H P n D F e 2 N N V x G X v u E / o H B o e G Y y P x 0 b H x i U R y c q r o m A 1 b 4 Q X F 1 E z 7 U J Y c r q k G L 7 i q q / F D y + a S L m v 8 Q K 5 v B v c H T W 4 7 q m n s u 2 c W L + l S 1 V A r q i K 5 R J 0 c y 7 p X 8 8 u e u O T 4 J 7 y c T L M M C 2 O u G 4 g R S C O K v J m 8 x z F O Y U J B A z o 4 D L i E N U h w a B x B B I N F X A k e c T Y h N b z n 8 B E n b Y O y O G V I x N Z p r d L p K G I N O g c 1 n V C t 0 C s a T Z u U c 5 h n T + y W v b F H d s d e 2 O e f t b y w R u D l j H a 5 o + V W O X E x s / f x r 0 q n 3 U X t W 9 X T s 4 s K 1 k K v K n m 3 Q i b 4 h d L R N 8 8 v 3 / b W d + e 9 B d Z m r + S / x Z 7 Z A / 3 A a L 4 r N z t 8 9 7 q H H 5 m 8 + N Q e 8 X c z u k E x m x G X M 9 m d l X Q u F T U q h l m k s E j d W E U O W 8 i j Q N V t X K G F t j A p r A o b Q q 6 T K v R F m m n 8 C G H 7 C 1 2 8 l T 0 = < / l a t e x i t > h e 2,s

< l a t e x i t s h a 1 _ b a s e 6 4 = " r M j h w Z W 0 g u L X d j b z 9 V g J u L / 0 2 p 0 

= " > A A A C j 3 i c h V H L S s N A F D 3 G V 6 2 P V t 0 I b q R F c S F l U g X F h R T c 6 M 5 X H 2 A f J H F a g 3 m R p A U N + Q F / Q M F V B R f i 3 h 9 w 4 w + 4 8 B P E p Y I b F 9 6 k A d F i v c P M n D l z z 5 0 z X N n S V M d l 7 L l P 6 B 8 Y H B q O j c R H x 8 Y n E s n J q Y J j N m 2 F 5 x V T M + 2 S L D l c U w 2 e d 1 V X 4 y X L 5 p I u a 7 w o n 2 w G 9 8 U W t x 3 V N A 7 c U 4 t X d K l h q H V V k V y i q m V Z 9 4 7 9 m p d d c v w q r y X T L M P C m O s G Y g T S i G L H T N 6 j j C O Y U N C E D g 4 D L m E N E h w a h x D B Y B F X g U e c T U g N 7 z l 8 x E n b p C x O G R K x J 7 Q 2 6 H Q Y s Q a d g 5 p O q F b o F Y 2 m T c o 5 z L M n d s v e 2 C O 7 Y y / s 8 8 9 a X l g j 8 H J K u 9 z R c q u W O J / Z / / h X p d P u 4 v h b 1 d O z i z r W Q q 8 q e b d C J v i F 0 t G 3 z i 7 e 9 t f 3 5 r 0 F d s 1 e y X + b P b M H + o H R e l d u d v n e V Q 8 / M n n x q T 3 i 7 2 Z 0 g 0 I 2 I y 5 n s r s r 6 V w q a l Q M s 0 h h k b q x i h y 2 s I M 8 V b d x i T a u h U l h V d g Q c p 1 U o S / S T O N H C N t f X 9 + V P g = = < / l a t e x i t > h v t < l a t e x i t s h a 1 _ b a s e 6 4 = " / f I L j z G R W t Z X R 5 Q d x 0 Q W s R h K y x o = " > A A A C i 3 i c h V G 7 S g N B F D 2 u r x g f i d o I N m J Q r M L E C E q w E E S w z M O o a G L Y X c e 4 Z F / s T h Z 0 y Q 9 Y C x a i o G A h 9 v 6 A j T 9 g 4 S e I p Y K N h T e b B d F g v M P M n D l z z 5 0 z X M X W N V c w 9 t w l d f f 0 9 v V H B q K D Q 8 M j s f j o 2 K Z r 1 R 2 V F 1 V L t 5 x t R X a 5 r p m 8 K D S h 8 2 3 b 4 b K h 6 H x L q a 0 2 7 7 c 8 7 r i a Z W 6 I I 5 u X D b l q a g e a K g u i d k q K 4 R 8 2 K m L P q 8 Q T L M m C m G o H q R A k E E b W i t + j h H 1 Y U F G H A Q 4 T g r A O G S 6 N X a T A Y B N X h k + c Q 0 g L 7 j k a i J K 2 T l m c M m R i a 7 R W 6 b Q b s i a d m z X d Q K 3 S K z p N h 5 R T m G F P 7 J a 9 s U d 2 x 1 7 Y 5 5 + 1 / K B G 0 8 s R 7 U p L y + 1 K 7 G S i 8 P G v y q B d 4 P B b 1 d G z w A G W A q 8 a e b c D p v k L t a X 3 j s / e C p n 8 j D / L r t k r + b 9 i z + y B f m B 6 7 + p N j u f P O / h R y E u D 2 p P 6 3 Y x 2 s D m f T K W T 8 7 m F x M p 0 2 K g I J j G N O e r G I l a w j i y K V N 3 E K S 5 w K Q 1 L a S k j L b d S p a 5 Q M 4 4 f I a 1 9 A Q n P k 9 I = < / l a t e x i t > Concat(h v t , h v s ) < l a t e x i t s h a 1 _ b a s e 6 4 = " E b n 1 2 h + c C v n + 7 x v x k n V / U 1 H Y + a g = " > A A A C q n i c h V G 7 S g N B F D 2 u r / i O 2 g g 2 w R A f E M J E B c U q Y G O p 0 Z h I E s P u Z j S L + 2 J 3 s q B L f k C w t

Q O D Q 9 H h k U 3 X q j s q z 6 m W b j k F R X a 5 r p k 8 J z S h 8 4 L t c N l Q d J 5 X 9 p a b 9 3 m P O 6 5 m m R t i 3 + Z l Q 9 4 1 t R 1 N l Q V R l e h U y Z B F z T H 8 Z c s k r j F d U g y / 1 q i I b S 8 Z C 7 G 7 7 c 1 U o n G W Y k H E f o J 0 C O I I Y 9 W K X q O E K i y o q M M A h w l B W I c M l 0 Y R a T D Y x J X h E + c Q 0 o J 7 j g Z 6 S V u n L E 4 Z M r F 7 t O 7 S q R i y J p 2 b N d 1 A r d I r O k 2 H l D E k 2 A O 7 Y C /

s n l 2 y J / b + a y 0 / q N H 0 s k + 7 0 t J y u z J 0 O L b + 9 q / K o F 2 g 9 q n 6 0 7 P A D h Y D r x p 5 t w O m + Q u 1 p f c O j l / W l 7 I J f 5 K d s W f y f 8 o e 2 R 3 9 w P R e 1 f M 1 n j 3 5 w 4 9 C X h r U n v T 3 Z v w E m 7 O p 9 F x q d m 0

+ n p k I G x X B O C Y w T d 1 Y Q A Y r W E W O q h / h C j e 4 l Z J S V t q S i q 1 U q S 3 U j O J L S N U P Q a C g K A = = < / l a t e x i t > Concat(h v 1 , h v s , h e 1,s ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 k P K l q m a C 0 / C 7 i 0 s L Z h 8 m K A R X f 4 = " > A A A C u 3 i c h V G 7 S g N B F D 2 u 7 / i K 2 g g 2 w a A o S J h V w S A I g o 1 l Y o w K R p f d d T S r + 2 J 3 E o j L / o A / Y C E I C h Z i 7 w 9 o Y a O d h Z 8 g l g o 2 F t 5 s F k R F v c P M n D l z z 5 0 z X M 0 1 D V 8 w 9 t g k N b e 0 t r V 3 d C a 6 u n t 6 + 5 L 9 A 6 u + U / F 0 X t Q d 0 / H W N d X n p m H z o j C E y d d d j 6 u W Z v I 1 b X + x f r 9 W 5 Z 5 v O P a K q L l 8 0 1 J 3 b W P H 0 F V B l J L M l i x V l D 0 r W H R s 4 s L x k m Y F 5 V C R t 6 q T q R j 7 n 3 i L K 4 E 8 m f L D C S W Z Z h k W R e o n k G O Q R h w 5 J 3 m F E r b h Q E c F F j h s C M I m V P g 0 N i C D w S V u E w F x H i E j u u c I k S B t h b I 4 Z a j E 7 t O 6 S 6 e N m L X p X K / p R 2 q d X j F p e q R M Y Z Q 9 s A v 2 w m 7 Z J X t i 7 7 / W C q I a d S 8 1 2 r W G l r t K 3 + F Q 4 e 1 f l U W 7 Q P l T 9 a d n g R 1 k I 6 8 G e X c j p v 4 L v a G v H h y 9 F O a W R 4 M x d s a e y f 8 p e 2 T X 9 A O 7 + q q f 5 / n y 8 R 9 + N P I S U n v k 7 8 3 4 C V a n M v J 0 Z i o / k 1 4 Y i R v V g W G M Y J y 6 M Y s F L C G H I l U / w Q 3 u c C / N S 7 q 0 J 5 m N V K k p 1 g z i S 0 i V D 9 e m p n A = < / l a t e x i t > Concat(h v 2 , h v s , h e 2,s )

< l a t e x i t s h a 1 _ b a s e 6 4 = " g I 0 t Y l q S t D x S l D J r Z M a 4 l O R w F r 0 r l V 0 / X V K r 2 i 0 3 R I O Y s Y e 2 K 3 7 I 0 9 s j v 2 w j 7 / r O X 5 N V p e a r Q r b S 2 3 C + G L 6 f 2 P f 1 U G 7 Q K n 3 6 q u n g W K W P O 9 a u T d 9 p n W L 9 S 2 v n r e e N t f 3 4 t 5 8 + y a v Z L / J n t m D / Q D s / q u 3 u z y v c s u f h T y U q f 2 J H 4 3 o x N k F u O J p f j i 7 n I 0 O R c 0 K o Q Z z G G B u r G K J F L Y Q Z q q n 6 G B K z S l i L Q i b U p b 7 V S p J 9 B M 4 U d I q S / w Q J U T < / l a t e x i t >

P u d D E T o a N 8 T x q Y J H o = " > A A A C u 3 i c h V G 7 S g N B F D 2 u 7 3 f U R r A J B k V B w i Q K B k E Q 0 l g m a l Q w u u y u Y 7 K 6 L 3 Y n g b j s D / g D F o K g Y C H 2 / o A W N t p Z + A l i q W B j

Figure 6 : Operation of graph attention in the estimation of the new edge e t,s (s = 6, t = 3). The query vector is Concat(h v t , h v s ), and the value and key vectors are {Concat(h v τ , h v s , h e τ,s )|τ = 1, ..., t -1}, where h v t is the feature vector of the node v t , h v s is the embedded vector of the predicted label of the new node v s , X s , and h e τ,s is the embedded vector of the predicted label of the new edge e τ,s , A τ,s . In other words, Q = Concat(h v t , h v s ) T , K = V = (Concat(h v 1 , h v s , h e 1,s ), ..., Concat(h v t-1 , h v s , h e t-1,s )) T (source target attention).

A.6 GRAM-A: ZEROING ATTENTION WEIGHTS Here, we provide an additional discussion on the actual computational complexity reduction by this approximation and its strong graph types. Figure 9 illustrates the attention weight zeroing in edge estimation.

Figure 8 shows the two distributions of attention weights in one step of edge estimation (i.e., in the calculation of h e <t ) on the grid dataset. The blue represents the distribution of weights for nodes that are predicted to have no connection to the new node v s (i.e., {v τ |A π τ,s = 0, τ = 1, ..., t-1}), and the orange represents the distribution of weights for those predicted to have connection to the new node (i.e., {v τ |A π τ,s = 0, τ = 1, ..., t -1}). From this figure, we can see that the former distribution is sharper around zero compared with the latter, most of whose weights take near-zero values. Similar results were observed for the other datasets.

The average values of α for each dataset are listed in Talbe 3. In both the synthetic and real-world graphs, we can see that α is less than 4 and approximately 1/100 ∼ 1/20 of n. Thus, considering the results in Table 2 , the computational cost of GRAM-A is estimated to be approximately 1/100 ∼ 1/20 that of GRAM on average, which is a dramatic reduction.

In the experiment, GRAM-A performed better than GRAM on the molecular dataset. This is likely because these graphs have strict rules or distinct patterns in incident edges to a node, such as the valence rule, and focusing only on the actual generated edges is both sufficient and makes the problem simpler. Thus, we expect that GRAM-A will demonstrate better performance when the graphs follow a certain strict rule on incident edges of their nodes. Here, the detailed configurations of the synthetic graphs are described. Samples from each synthetic graph dataset are illustrated in Figures 10, 11, 12, and 13 (color is best) . Different color corresponds to different node/edge labels on each dataset.

Grid We used 2D grid graphs with the number of nodes in the range 50 ≤ |V | ≤ 100. Each node was labeled according to its degree, yielding 3 types of node labels: "corner", "edge", and In evaluation, we reported an average of 3 runs for each score. To calculate GK-MMD score for the molecular dataset, we used 100 samples from the generated graphs and 100 samples from the test set for fast evaluation. We reported an average of 10 runs.

A.7.3 ADDITIONAL EXPERIMENT RESULT:

The results on the lobster dataset are listed in Table 4 . As on other datasets, GRAM and its variants demonstrated competitive results in terms of topological MMDs, and better performance in terms of GK-MMD. Lobster (500, 100, 3, 4) deg.

clus. orbit GK time DeepGMG 0.958 8e-5 0.035 0.527 13.5 GraphRNN 1e-4 0 0 0.203 2.2 GraphRNN-S 0.020 0.023 4e-4 0.221 1.4 GRAM 0.001 5e-4 6e-5 0.049 0.9 GRAM-A 0.001 0.001 8e-4 0.043 0.8 GRAM-B 0.001 8e-5 2e-4 0.048 0.7 GRAM-AB 0.001 2e-5 7e-5 0.047 0.7

In addition, considering that the molecular dataset is a subset of the druglike category in ZINC database (Sterling & Irwin, 2015) , we reported the average QED scores (Bickerton et al., 2012) of the training samples and the generated samples. QED score measures the drug likeliness of the molecular.

Table 5 summarizes the results. We can see the generated molecular graphs of our models have higher QED compared with those of baselines, and near to that of the training set. Note that our models do not rely on reinforcement learning methods and utilize neither the information of QED nor valence rule; they learned only through unsupervised learning. To examine the effectiveness of the bias terms in the graph attention mechanism, we conducted an ablation study. Specifically, we evaluated two variants: GRAM without bias terms of graph attention in edge estimation, and GRAM without bias terms of graph attention in feature extraction.

The results are listed in Table 6 . On all the synthetic graph datasets, removing bias terms in edge estimation degraded its performance. From this, we can see the importance of the bias terms in edge estimation for the better quality of generation. Also, removing bias terms in feature extraction degraded the performance on the B-A dataset. This is likely because its expressive power is limited.

On the other hand, the drop in the performance by removing bias terms in feature extraction is minor on the grid, lobster and community dataset. Considering the properties of these random graphs, this is likely because only local features were enough for these cases. 10, 11, 12, 13 and 14 (color is best) . We used the same visualization method for all graphs. Different color corresponds to different node/edge labels on each dataset.

The graphs generated by GraphRNN are quite similar to those in the training set in terms of their topology. However, they completely failed to capture node/edge label patterns in most cases.

In contrast, the graphs generated by GRAM are similar to training samples in terms of both topology and node/edge label pattens.

A.8 LIMITATIONS AND FUTURE WORK:

While our models demonstrated superior performance on most of the datasets, they have some limitations. For example, on inference, one wrong prediction of node/edge label may collapse all the following generation processes, resulting in a bizarre graph generated. This is a deficit of its rich feature extraction process. A possible solution to this problem is, for example, to employ beam search. By applying beam search on inference, we can get rid of samples with a quite lower likelihood and avoid the above undesirable situations.

Additionally, although we reduced the computational complexity of the models by a significant amount, the feature extraction process still requires a large amount of computation. To this challenge, some methods proposed in the field of image processing and natural language processing would help to alleviate it. 

:

Because Johnson et al. (2018) assume directed graphs as input, we ignore go in Figure3of that paper.

Figures and Tables:

w l B 2 I A C l 8 Y W Z D D Y x O 3 A I 8 4 h p A f 3 H I e I k b Z B W Z w y F G L 3 a a 3 R a S t k T T r 7 N d 1 A r d E r B k 2 H l A l M s g d 2 z V 7 Y P b t h T + z 9 1 1 p e U M P 3 0 q J d b W u 5 X R k 6 G l t 7 + 1 d V p 1 1 g 7 1 P 1 p 2 e B K u Y D r z p 5 t w P G / 4 X W 1 j c P T l 7 W s o V J b 4 p d s m f y f 8 E e 2 R 3 9 w G y + a l d 5 X j j 9 w 4 9 K X v z 2 y N + b

y M u 3 / A x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

H b P K Q w h g N o e d l H s E J D t 4 r e D u 7 r H a r h 3 Z l q u W s K / K P i a q I x A j L y Q e z I h z + S B v J L P P 2 c N 3 B m O l z 6 u 4 l R L j V b o Y q f 0 8 a 9 K x Z X B 2 b d q r m c G b U i 5 X m X 0 b r i M c w t p q r f P r y a l d D E 2 i J N b 8 o b + b 8 i Y P O E N N P t d u i v Q 4 m i O H x G 9 D D E e / n c Y s 6 C S T P A H i W T h M J q J e 0 H 5 Y R f 2 Y B / T O I I M 5 C A P Z T e F S x j B N R f k e C 7 F p a e t n M / T b M O P 4 r J f t c e S z w = = < / l a t e x i t > Xs < l a t e x i t s h a 1 _ b a s e 6 4 = " / 5 P

r i 5 w l O M N g d p f H b V 6 t x 6 z L 6 0 r N M F J b f I r D P W C l i g z d 0 z U 9 0 x 3 d 0 C O 9 / 1 q r H N W o e N n n 2 a x q h Z 9 r P + p e e v 1 X V e B Z Y u d T 9 a d n i T w m I 6 8 2 e / c j p n I L q 6 o v H R w / L 0 0 t Z s r 9 d E 5 P 7 P + M H u i W b + C W X q y L B b F 4 g i R / g P 7 9 u X + C l V F N H 9 N G F 8 b T M / 3 x V z S i B 3 0 Y 5 P e e w A z m M I 8 s n 7 u H U 1 z i K v G m 9 C o Z Z a C a q i R i T R e + h E I f x T q N n w = = < / l a t e x i t >

Figure 1: s-th step of the generation process.

Figure 2: l-th feature extraction block.

4 0 w a R u U x S l D J L Z O a 4 1 O h z 6 r 0 7 l f 0 / b U M r 2 i 0 r R I G c M y e 2 Z 3 r M e e 2 D 1 7 Y R + / 1 m p 5 N f p e m r R L A y 0 3 K 5 H z h e L 7 v y q N d g e n X 6 o / P T u o Y t P z q p B 3 0 2 P 6 v 5 A H e v e s 0 y t u F Z Z b C X b D X s n / N e u y R / q B 7 r 7 J t 3 l e u P r D j 0 R e 2 t S e 1 M 9 m D I N y O p n K J

3 J M B e S Y P 5 J V 8 / l m r 6 9 Z w v H R w F o d a q j d C Z y u F j 3 9 V C s 4 W n H y r x n q 2 4 B i 2 X K 8 M v e s u 4 9 x C G u r t 0 4 t B Y T s f 6 8 b J L X l D / z e k T 5 7 w B q r 9 L t 3 l a P 5 y jB 8 R v f S w P f z v Z o y C U i r J b y R T u X Q 0 E / c a 5 Y d V W I M E d m M T M n A A W S i 6 7 3 k O V 3 D N B b k 0 t 8 P t D l M 5 n 6 d Z h h / B 7 X 8 B 1 7 O T P A = = < / l a t e x i t > v ⇡(2)< l a t e x i t s h a 1 _ b a s e 6 4 = " V X u V O d / q 8 o S + t Y Z f J I k 8 / e U s 8 0

7 A P a U p I 4 r U P T J C R p o I b + g H t x I S g K L s S 9 P + D G H 3 D R T x C X F d y 4 8 D Y N i B b r D Z M 5 c + a e O 2 f m i p r M D J O Q v o e b m p 6 Z n f P O + x Y W l / y B 4 P J K 0 V A 7 u k Q L k i q r e l k U D C o z h R Z M Z s q 0 r O l U a I s y L Y m t / e F + y a K 6 w V T l y O x q t N Y W m g p r M E k w k a p Y d b u q s V h y s + e r B 8 M k T p w I j Q P e B W F w I 6

O c z w F t J I b 5 1 e D P I 7 u Y g d J b f k D f 3 f k D 5 5 w h s o 1 r t 0 l 6 W 5 y w l + R P T S w / b w v 5 s x D o q

s h a 1 _ b a s e 6 4 = " M a e d d P o X r R n b D i e p d 9 5 / W w G D O 1

g o t a + p E f o C I z 0 9 M e z h c z o 2 D i H 2 j Z p o V t C l p E + / 5 A m / 5 A C 3 9 C t D R o 0 6 I 7 4 0 C U Z H e Y e e e d d 8 + d 8 z i i L j P T I m T k 4 e b m F x a X v M s + / 8 r q

3 h b u q y 6 q 4 t 2 e a j l r C v 8 j 4 G q g M Q Y S 8 k H s y J s / k g b y S z z 9 n 9 Z 0 Z t p c e r u J ES / V G 4 G K r 8 P G v S s H V g r N v 1 U z P F j Q h 6 X h l 6 F 1 3 G P s W 0 k T f P b 8 a F 1 L 5 S D 9 K b s k b + r 8 h I / K E N 1 C 7 7 9 J d j u a H M / y I 6 G W A 8 f C / w 5 g G p U S c 3 4 8 n c g f h d N Q N y g v b s A M x T O M Q 0 n A M W S g 6 K V z C E K4 5 P 8 d z S S 4 1 a e U 8 r m Y T f h S X + Q J C o 5 G p < / l a t e x i t > G < l a t e x i t s h a 1 _ b a s e 6 4 = " R L x m r H 7 q

2 g 0 b V L G k W T P 7 I 5 1 2 R O 7 Z y / s 4 8 9 a L b +G 5 + W Y d r m n 5 d Z B 9 H Q 2 / / 6 v S q f d x d G X q q 9 n F 1 W s + l 5 V 8 m 7 5 j P c L p a d v n l x 2 8 2 u 5 Z C v F b t g r + b 9 m H f Z I P z C a b 8 p t l u e u + v i R y U u b 2 i P + b M Z v U M y k x a V 0 J r u c 2 E g F j Q p j D v N Y o G 6 s Y A P b 2 E G B q l d x h n N c C E P C o p A R l n u p Q i j Q z O B b C O u fx C q P u w = = < / l a t e x i t > n < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 D 6 P w G j s w e c y W Z b N x S j 6 1 o H A J w I

1 9 8 R 7 E 3 3 9 A 4N D y e G R T d + p e I Y o G I 7 p e C V d 8 4 U p bV E I Z G C K k u s J z d J N U d T L K 6 3 7 Y l V 4 v n T s j a D m i h 1 L O 7 D l v j S 0 g K m c v Z t M U 4 b C S P 0 E a g T S i G L N S d 5 h G 3 t w Y K A C C w I 2 A s Y m N P g 8 t q C C 4 D K 3 g z p z H i M Z 3 g s 0 k G B t h b M E Z 2 j M l n k 9 4 N N W x N p 8 b t X 0 Q 7 X Br 5 g 8 P V a m M E m P d E M v 9 E C 3 9 E T v v 9 a q h z V a X m q 8 6 2 2 t c H e H j s f y b /

z d w + m s w 5 j H T / X u A E E d b W O E t w h s J s h d c y n 3 Y D 1 u R z p 6 b r q z V + x e D p s D K G e X q m O 2 r T E 9 3 T C 3 3 8 W a v p 1 + h 4 a f C u d r X C P p g 4 n c m + / 6 u q 8 u 7 h 6 E v V 0 7 O H E l Z 9 r z p 7 t 3 2 m 8 w u t q 6 8 f X 7 a z a 5 n 5 Z o J u 6 J X 9 X 1 O L H v k H Z v 1 N u 0 2 L z F U P P y p 7 O e H 2 y D + b 8 R v k U 0 l 5 K Z l K L 8 c 3 E k G j h j C L O S x w N 1 a w g S 1 s I 8 f V B c 5 w j g s p L C 1 K s r T U T Z V C g W Y a 3 0 J a / w S R s Y + r < / l a t e x i t > b < l a t e x i t s h a 1 _ b a s e 6 4 = "

w h s J s h d c y n 3 Y D 1 u R z p 6 b r q z V + x e D p s D K G e X q m O 2 r T E 9 3 T C 3 3 8 W a v p 1 + h 4 a f C u d r X C P p g 4 n c m + / 6 u q 8 u 7 h 6 E v V 0 7 O H E l Z 9 r z p 7 t 3 2 m 8 w u t q 6 8 f X 7 a z a 5 n 5 Z o J u 6 J X 9 X 1 O L H v k H Z v 1 N u 0 2 L z F U P P y p 7 O e H 2 y D + b 8 R v k U 0 l 5 K Z l K L 8 c 3 E k G j h j C L O S x w N 1 a w g S 1 s I 8 f V B c 5 w j g s p L C 1 K s r T U T Z V C g W Y a 3 0 J a / w S T z 4 + s < / l a t e x i t > n < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 D 6 P w G j s w e c y W Z b N x S j 6 1 o H A J w I

1 9 8 R 7 E 3 3 9 A 4N D y e G R T d + p e I Y o G I 7 p e C V d 8 4 U p bV E I Z G C K k u s J z d J N U d T L K 6 3 7 Y l V 4 v n T s j a D m i h 1 L O 7 D l v j S 0 g K m c v Z t M U 4 b C S P 0 E a g T S i G L N S d 5 h G 3 t w Y K A C C w I 2 A s Y m N P g 8 t q C C 4 D K 3 g z p z H i M Z 3 g s 0 k G B t h b M E Z 2 j M l n k 9 4 N N W x N p 8 b t X 0 Q 7 X Br 5 g 8 P V a m M E m P d E M v 9 E C 3 9 E T v v 9 a q h z V a X m q 8 6 2 2 t c H e H j s f y b /

r T e P u A = = < / l a t e x i t > n < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 D 6 P w G j s w e c y W Z b N x S j 6 1 o H A J w I

t e x i t s h a 1 _ b a s e 6 4 = " b V A n t Z p X a c l o J b Z i F 8 7 Q e G I X y S 4 = " > AA A C h 3 i c h V G 7 S g N B F D 2 u z / i M 2 g g 2 w Z B g F W d V V M Q i Y m O p 0 T w g S t h d J 3 F 1 X + x O A r r 4 A 1 Z 2 o l Y K F m L v D 9 j 4 A x Z + g l g q 2 F h 4 d 7 M g K s Y 7 z M y Z M / f c O c N V H U P 3 B G N P b V J 7 R 2 d X d 0 + s t 6 9 / Y H A o P j x S 8 O y 6 q / G 8 Z h u 2 W 1 I V j x u 6 x f N C F w Y v O S 5 X T N X g R X V / J b g v N r j r 6 b a 1 K Q 4 c v m 0 q N U u v 6 p o i i C q U K v 6 S d 1 S J J 1 m G h Z H 4 D e Q I J B H F m h 2 / w x Z 2 Y E N D H S Y 4 L A j C B h R 4 N M q Q w e A Q t w 2 f O J e Q H t 5 z H K G X t H X K 4 p S h E L t P a 4 1 O 5 Y i 1 6 B z U 9 E K 1 R q 8 Y N F1 S J p B i j + y G v b I H d s u e 2 c e f t f y w R u D l g H a 1 q e V O Z e h 4 b O P 9 X 5 V J u 8 D u l 6 q l Z 4 E q F k K v O n l 3 Q i b 4 h d b U N w 5 P X z c W c y k / z a 7 Y C / m / Z E / s n n 5 g N d 6 0 6 3 W e u 2 j h R y U v Q X v k n 8 3 4 D Q r T G X k m M 7 0 + m 8 y m o 0 b 1 Y B w T m K R u z C O L V a w h T 9 X 3 c I I z n E s x a U q a k x a a q V J b p B n F t 5 C W P w G I v J H a < / l a t e x i t >

w l B 2 I A C l 8 Y W Z D D Y x O 3 A I 8 4 h p A f 3 H I e I k b Z B W Z w y F G L 3 a a 3 R a S t k T T r 7 N d 1 A r d E r B k 2 H l A l M s g d 2 z V 7 Y P b t h T + z 9 1 1 p e U M P 3 0 q J d b W u 5 X R k 6 G l t 7 + 1 d V p 1 1 g 7 1 P 1 p 2 e B K u Y D r z p 5 t w P G / 4 X W 1 j c P T l 7 W s o V J b 4 p d s m f y f 8 E e 2 R 3 9 w G y + a l d 5 X j j 9 w 4 9 K X v z 2 y N + b8 R N s p F N y J p X O z y Y X p s J G R T G O C U x T N + a w g B W s o k j V T R z j D O f S g J S R s l K u n S p F Q s 0 o v o S 0 / A E K f Z L m < / l a t e x i t > h G< l a t e x i t s h a 1 _ b a s e 6 4 = " L 9 p x 5 2 B o k j M u I T g F / g z F T R 8 D

y M u 3 / A x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

r 5 V M z 1 b 0 I K U 6 5 W h d 9 1 l n F t I E 3 3 v / G p c T B d i d p z c k j f 0 f 0 N G 5 A l v o P b e p b s 8 L Q x n + B H R y w D j 4 X + H M Q 3 K y Q S / l 0 j m 9 6 O Z u B e U H 7 Z h B 3 Y x j Q P I w B H k o O S m c A l D u O a C H M + l u P S k l f N 5 m k 3 4 U V z 2 C 5 Z l k s A = < / l a t e x i t > H v < l a t e x i t s h a 1 _ b a s e 6 4 = " a i 4 O

H b P K Q w h g N o e d l H s E J D t 4 r e D u 7 r H a r h 3 Z l q u W s K / K P i a q I x A j L y Q e z I h z + S B v J L P P 2 c N 3 B m O l z 6 u 4 l R L j V b o Y q f 0 8 a 9 K x Z X B 2 b d q r m c G b U i 5 X m X 0 b r i M c w t p q r f P r y a l d D E 2 i J N b 8 o b + b 8 i Y P O E N N P t d u i v Q 4 m i O H x G 9 D D E e / n c Y s 6 C S T P A H i W T h M J q J e 0 H 5 Y R f 2 Y B / T O I I M 5 C A P Z T e F S x j B N R f k e C 7 F p a e t n M / T b M O P 4 r J f t c e S z w = = < / l a t e x i t > X s < l a t e x i t s h a 1 _ b a s e 6 4 = " / 5 P M k s p Q D h X N b 4 R g 7 1 B C c L T g Q Z U = " > A A A C h H i c h V G 7 S g N B F D 2 u G t 8 m a i P Y i C H B Q s L E B 4 q F B G w s T W I 0 E E P Y X S d x c F / s T g I a 8 g O C r R Z W C h Z i 7 w / Y + A M W f o J Y K t h Y e H e z I B q M d 5 i Z M 2 f u u X O G q z m G 8 C R j z z 1 K b 1 9 / Z G B w a H h k d G w 8 G p u Y 3 P X s u q v z g m 4 b t l v U V I 8 b w u I F K a T B i 4 7 L V V M z + J 5 2 t O n f 7 z W 4 6 w n b 2 p H H D i + b a s 0 S V a G r k q h 8 s e J V Y n G W Y k H M d o J 0 C O I I Y 9 u O 3 W M f B 7 C h o w 4 T H B Y k Y Q M q P B o l p M H g E F d G k z i X k A j u O V o Y J m 2 d s j h l q M Q e 0 V q j U y l k L T r 7 N b 1 A r d M r B k 2 X l L N I s C d 2 y 9 7 Y I 7 t j L + z z z 1 r N o I b v 5 Z h 2 r a 3 l T i V 6 O p 3 / + F d l 0 i 5 x + K 3 q 6 l m i i r X A q y D v T s D 4 v 9 D b + s b J x V t + P Z d o J t k 1 e y X / V + y Z P d A P r M a 7 f p P l u c s u f j T y 0 q L 2 p H 8 3 o x P s L q b S S 6 n F 7 H I 8 k w w b N Y g Z z G G e u r G K D L a w j Q

4 0 w a R u U x S l D J L Z O a 4 1 O h z 6 r 0 7 l f 0 / b U M r 2 i 0 r R I G c M y e 2 Z 3 r M e e 2 D 1 7 Y R + / 1 m p 5 N f p e m r R L A y 0 3 K 5 H z h e L 7 v y q N d g e n X 6 o / P T u o Y t P z q p B 3 0 2 P 6 v 5 A H e v e s 0 y t u F Z Z b C X b D X s n / N e u y R / q B 7 r 7 J t 3 l e u P r D j 0 R e 2 t S e 1 M 9 m D I N y O p n K J

2 y w b s k d 2 x Z / b + a 6 2 O W 2 P o p U 2 7 N N J y o x o 6 W 8 q / / a t q 0 m 7 j 5 F P 1 p 2 c b N W y 7 X h X y b r j M 8 B f y S O + c 9 g b 5 n V y s s 8 q u 2 Q v 5 v 2 J 9 9 k A / 0 J x X + S b L c 5 d / + J H I S 5 f a k / j e j J + g m I w n

r 8 b F d C H W j 5 N b 8 o b + b 8 i I P O E N 9 O 6 7 c p e n h e E M P z J 6 c e I R f 4 c x D c r J h L i f S O Y P o p m 4 F 5

m w s 4 y M a U A m 7 6 y Q O 2 R e 7 k 4 A u / o C l j U V s F E T E z 7 D x B y z 8 B B E r B R s L b z Y L o q L e Z X b O n L n n z p k 7 u m s K X z L 2 E F P a 2 j s 6 u 7 p 7 4 r 1 9 /Q O J 5 O D Q p u / U P I M X D M d 0 v K K u + d w U N i 9 I I U 1 e d D 2 u W b r J t / T q c n N / q 8 4 9 X z j 2 h j x w + a 6 l V W x R F o Y m i S o u l Q I 5 l f K P S s k 0 y 7 E w U j + B G o E 0 o s g 7 y S v s Y A 8 O D N R g g c O G J G x C g 0 / f N l Q w u M T t I i D O I y T C f Y 4 j x E l b o y x O G R q x V f p X a L U d s T a t m z X 9 U G 3 Q K S Y N j 5 Q p Z N g 9 u 2 Y v 7 I 7 d s E f 2 / m u t I K z R 9 H J A s 9 7 S c r e U O B 5 Z f / t X Z d E s s f + p + t O z R B n z o V d B 3 t 2 Q a d 7 C a O nr h 6 c v 6 w t r m S D L L t g T + T 9 n D + y W b m D X X 4 3 L V b 7 W Q J w e Q P 3 e 7 p 9 g c z q n z u S m V 2 f T i 9 n o K b o x h g l M U r / n s I g V 5 F E I + 3 y C B s 5 i z 8 q w

Figure4: s-th step of the generation process (s = 6, t = 3). In its s-th step, given a subgraph G <s , our model estimates the new node v s and new edges {e 1,s , ..., e s-1,s } to add next. Specifically, it takes a tensor pair (X <s , A <s,<s ) as input and predicts the label of the new node X s and the labels of the new edges A t,s (t = 1, ..., s -1). In detail, first, the feature extractor calculates s -1 node feature vectors H v = (h v 1 , ..., h v s-1 ) T and a graph feature vector h G from a tensor pair (X <s , A <s,<s ). Next, the node estimator predicts the label of the new node X s from the graph feature vector. When the EOS is output, the generation is terminated. Finally, the edge estimator predicts the labels of the new edges A t,s (t = 1, ..., s -1) from the node feature vectors, the graph feature vector, the embedded vector of the predicted node label, and the embedded vectors of previously predicted edge labels in this step.

U J D S W P O S R A C G 7 6 4 A T 9 + X u Q I I b f s D S x g I b T S y M v T 9 g 4 w 9 Y 8 A n G E h M b C y / L J k a J e D e 7 c + b M P X f P 5 M i m y m x O y N A n z M 0 v L C 7 5 l w P B l d W 1 U H h 9 o 2 w b H

m l g Y e 3 / A x h + w 4 B O M J S Y 2 F l 6 W T Y w S 8 W 5 2 5 8 y Z e + 6 e y Z F N l d m c k J F P W F h c W l 7 x r w a C a + s b

8 k L u y Z g 8 k w f y S j 7 / n O W 4 M y Z e + r j K U y 0 1 m 6 G L n e L H v y o N V w 5 n 3 6 q 5 n j m 0 I O V 6 Z e j d d J n J L Z S p v n d + N S 6 m C 3 F n j 9 y S N / R / Q 0

e X T Y w S 8 W 5 2 5 8 y Z e + 6 e y Z F N l d m c k L F P W F h c W l 7 x r w a C a + s b

1 y t C 7 6 T L O L Z S p v n d + N S m m C / H B H r k l b + j / h o z J E 9 5 A 7 7 0 r d 3 l a G M 3 x I 6 O X I c Y j / g 5 j F p S T C f E g k c w f x j J R L y g / 7 E I U 9 j G N I 8 j A M e S g 5 K Z w C S O 4 F o K C K K S E 9 L R V 8 H m a b f h R Q v Y L c T 2 S q w = = < / l a t e x i t > k 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " A e s a 3 + c 0 b v a 5 V B 8 / p j p O h U D 0

m l g Y e 3 / A x h + w 4 B O M J S Y 2 F l 6 W T Y w S 8 W 5 2 5 8 y Z e + 6 e y Z F N l d m c k J F P W F h c W l 7 x r w a C a + s b o

R U J D S W P O S R A C G 7 6 6 A T 9 p X d g Q Q 3 / I C l j Q U 2 m l g Y e 3 / A x h + w 4 B O M J S Y 2 F l 6 W T Y w S 8 W 5 2 5 8 y Z e + 6 e y Z F N l d m c k J F P W F h c W l 7 x r w a C a + s b o

g J D d d d A J + 8 r u Q I I b f s D S x g I b T S y M v T 9 g 4 w 9 Y 8 A n G E h M b C y / L J k a J e D e 7 c + b M P X f P 5 M i m y m x O y N A n z M 0 v L C 7 5 l w P B l d W 1 U H h 9 o 2 w b H

0 p N W w e d p N u F H C d k v d 5 e S r g = = < / l a t e x i t > 3 F G EACD v 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " G I o O r n w 4 P j J 6 j T M 2 A p U v D L d d 1 h s

y M u 3 / A x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

8 D l T F I k h d y T y b k m T y Q V / L 5 5 y z H m + F 6 G e A q T r V U b 0 c u d s o f / 6 o U X C 0 4 + 1 b N 9 W x B B z K e V 4 b e d Y 9 x b y F N 9 f b 5 1 a S c L S W d P X J L 3 t D / D R m T J 7 y B a r 9 L d 0 V a G s 3 x I 6 K X I c b D / w 5 j F l T T K f 4 g l S 4 e J n J x P 6 g g 7 E I c 9 j G N I 8 j B M R S g 4 q V w C S O 4 5 s I c z 2 W 4 7 L S V C / i a b f h R X P 4 L h o q S t Q = = < / l a t e x i t > v 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " W B r

y M u 3 / A x T / g w E 8 w j p i 4 O H h b m h g l 4 m 3 a d 9 5 5 9 9 y e l y P q

X + + F e l 4 G r B 2 b d q p m c L O p D x v D L 0 r n u M e w t p o r f P r 8 b l b C n p 7 J B b 8 o b + b 8 i I P O E N V P t d u i v S 0 n C G H x G 9 D D A e / n c Y 0 6 C a T v F 7 q X R x P 5 G L + 0 E F Y R v i s I t p H E I O j q A A F S + F S x j C N R f m e C 7 D Z S e t X M D X b M K P 4 v J f j w K S u Q = = < / l a t e x i t > v 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " e 3 4 d 4 l T y N I 3

6 4 G N n I G I s k 9 p 9 C H A G o 7 2 E W x g 0 e 2 j d 8 m 7 i o e q + L e m W m 6 a h H / I u N r o D I E U f J M 7 s i Y P J F 7 8k I + / p x l u z M c L z 1 c h Y m W 6 v X g 5 V b + / V + V g q s F r S / V V M 8 W N O D Q 9 S q h d 9 1 l n F u I E 3 3 3 4 m q c T + a i 9 g 6 5 I a / o / 5 q M y C P e Q O 2 + i c M s z Q 2 m + B H Q i x M P 9 z O M 3 6 C Y i H N 7 8 U R 2 P 5 I K e 0 H 5 Y R v C E M M 0 D i A F x 5 C B g p v Y A G5 h y G w y S e a I S U 9 a G Z + n 2 Y B v x Z x 8 A n Y 1 l a c = < / l a t e x i t > h v(l 1) 1

B F I I 4 o V M 3 m P b e z B h I I y d H AY c A l r k O D Q 2 I I I B o u 4 H f j E 2 Y T U 8 J 6 j i g 7 S l i m L U 4 Z E 7 C G t + 3 T a i l i D z k F N J 1 Q r 9 I p G 0 y Z l C i P s i d 2 y N / b I 7 t g L + / y z l h / W C L x U a J d r W m 4 V Ey e D q x / / q n T a X R x 8 q x p 6 d l H C T O h V J e 9 W y A S / U G p 6 7 / j 0 b X U 2 P + K P s k v 2 S v 4 v 2 D N 7 o B 8 Y 3 r t y l e P 5 s w Z + Z P I S t E f 8 3 Y x 6 s J 7 N i J O Z b G 4 q P T 8 c N S q O

Figure 5: Operation of graph attention in the l-th feature extraction block, where query, key, and value vectors are all node feature vectors (i.e., Q =K = V = H v = (h

4 x 1 m 5 s y Z e + 6 c 4 c q W p j o u Y 8 8 R o a e 3 r 3 9 g c C g 6 P D I 6 N h 6 b m M w 5 Z s N W e F Y x N d M u y J L D N d X g W V d 1 N V 6 w b C 7 p s s b z c n 3 D v 8 8 3 u e 2 o p r H

6 5 c 4 a r 2 L r m e o w 1 O 4 T O r u 6 e 3 l B f u H 9 g c C g i D o 9 k X a v s q D y j W r r l 7 C i y y 3 X N 5 B l P 8 3 S + Y z t c N h S d 5 5 S j l d Z 9 r s I d V 7 P M b a 9 q 8

r B S s B B L w U o r G 3 / A w k 8 Q S w U b C 2 8 2 C 6 K i 3 m F m z p y 5 5 8 4 Z r m L r m i s Y e 2 y T 2 j s 6 u 7 o j P b 1 9 /

4 c 1 m I a i o d 5 i Z M 2 f u u X O G q z q G 7 g n G n l q k 1 r b 2 j s 6 u 7 p 7 e v v 6 B w d j Q 8 L p n V 1 y N F z T b s N 1 N V f G 4 o V u 8 I H R h 8 E 3 H 5 Y q p G n x D P c j W 7 z e q 3 P V 0 2 1 o T N Y d v m 0 r J 0 v d 0 T R F E y b F M 0 V R E 2 T X 9 r G 0 R F 0 w V V d M v B 3 J 6 p z o T j 7 D X x D t c 9 t M z c S + Y l m M J l m R hx H + C V A Q S i C J n x 6 5 R x C 5 s a K j A B I c F Q d i A A o / G F l J g c I j b h k + c S 0 g P 7 z k C 9 J C 2 Q l m c M h R i D 2 g t 0 W k r Y i 0 6 1 2 t 6 o V q j Vw y a L i n j m G C P 7 J K 9 s j t 2 x Z 7 Z x 6 + 1 / L B G 3 U u N d r W h 5 Y 4 8 e D S 6 + v 6 v y q R d o N x U / e l Z Y A + Z 0 K t O 3 p 2 Q q f 9 C a + i r h 8 e v q w s r E / 4 k O 2 c v 5 P + M P b E b + o F V f d M u 8 n z l 5 A 8 / K n k J q D 2 p 7 8 3 4 C d b T y d R s M p 2 f S y y N R 4 3 q w h j G M U X d m M c S l p F D g a q f 4 h b 3 e J A W J U 3 a l 4 x G q t Q S a U b w J a T K J 9 w H p n I = < / l a t e x i t >Concat(h v 1 , h v s , h e 1,s ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 k P K l q m a C 0 / C 7 i 0 s L Z h 8 m K A R X f 4 = " > A A A C u 3 i c h V G 7 S g N B F D 2 u 7 / i K 2 g g 2 w a A o S J h V w S A I g o 1 l Y o w K R p f d d T S r + 2 J 3 E o j L / o A / Y C E I C h Z i 7 w 9 o Y a O d h Z 8 g l g o 2 F t 5 s F k R F v c P M n D l z z 5 0 z X M 0 1 D V 8 w 9 t g k N b e 0 t r V 3 d C a 6 u n t 6 + 5 L 9 A 6 u + U / F 0 X t Q d 0 / H W N d X n p m H z o j C E y d d d j 6 u W Z v I 1 b X + x f r 9 W 5 Z 5 v O P a K q L l 8 0 1 J 3 b W P H 0 F V B l J L M l i x V l D 0 r W H R s 4 s L x k m Y F 5 V C R t 6 q T q R j 7 n 3 i L K 4 E 8 m f L D C S W Z Z h k W R e o n k G O Q R h w 5 J 3 m F E r b h Q E c F F j h s C M I m V P g 0 N i C D w S V u E w F x H i E j u u c I k S B t h b I 4 Z a j E 7 t O 6 S 6 e N m L X p X K / p R 2 q d X j F p e q R M Y Z Q 9 s A v 2 w m 7 Z J X t i 7 7 / W C q I a d S 8 1 2 r W G l r t K 3 + F Q 4 e 1 f l U W 7 Q P l T 9 a d n g R 1 k I 6 8 G e X c j p v 4 L v a G v H h y 9 F O a W R 4 M x d s a e y f 8 p e 2 T X 9 A O 7 + q q f 5 / n y 8 R 9 + N P I S U n v k 7 8 3 4 C V a n M v J 0 Z i o / k 1 4 Y i R v V g W G M Y J y 6 M Y s F L C G H I l U / w Q 3 u c C / N S 7 q 0 J 5 m N V K k p 1 g z i S 0 i V D 9 e m p n A = < / l a t e x i t > Concat(h v 2 , h v s , h e 2,s )< l a t e x i t s h a 1 _ b a s e 6 4 = " g I 0 t Y l q S t DP u d D E T o a N 8 T x q Y J H o = " > A A A C u 3 i c h V G 7 S g N B F D 2 u 7 3 f U R r A J B k V B w i Q K B k E Q 0 l g m a l Q w u u y u Y 7 K 6 L 3 Y n g b j s D / g D F o K g Y C H 2 / o A W N t p Z + A l i q W B j 4 c 1 m I a i o d 5 i Z M 2 f u u X O G q z q G 7 g n G n l q k 1 r b 2 j s 6 u 7 p 7 e v v 6 B w d j Q 8 L p n V 1 y N F z T b s N 1 N V f G 4 o V u 8 I H R h 8 E 3 H 5 Y q p G n x D P c j W 7 z e q 3 P V 0 2 1 o T N Y d v m 0 r J 0 v d 0 T R F E y b F M 0 V R E 2 T X 9 r G 0 R F 0 w V V d M v B 3 J 6 p z o T j 7 D X x D t c 9 t M z c S + Y l m M J l m R h x H + C V A Q S i C J n x 6 5 R x C 5 s a K j A B I c F Q d i A A o / G F l J g c I j b h k + c S 0 g P 7 z k C 9 J C 2 Q l m c M h R i D 2 g t 0 W k r Y i 0 6 1 2 t 6 o V q j Vw y a L i n j m G C P 7 J K 9 s j t 2 x Z 7 Z x 6 + 1 / L B G 3 U u N d r W h 5 Y 4 8 e D S 6 + v 6 v y q R d o N x U / e l Z Y A + Z 0 K t O 3 p 2 Q q f 9 C a + i r h 8 e v q w s r E / 4 k O 2 c v 5 P + M P b E b + o F V f d M u 8 n z l 5 A 8 / K n k J q D 2 p 7 8 3 4 C d b T y d R s M p 2 f S y y N R 4 3 q w h j G M U X d m M c S l p F D g a q f 4 h b 3 e J A W J U 3 a l 4 x G q t Q S a U b w J a T K J 9 w H p n I = < / l a t e x i t > h e <t < l a t e x i t s h a 1 _ b a s e 6 4 = " W 0 K F T y 3 R 9 o g f 6 bC F Y 8 m S K g A t O V A = " > A A A C j n i c h V G 7 S g N B F D 2 u r / h M 1 E a w E U P E K k x U V E Q x Y J P S V x L B x L C 7 T u K S f b k 7 C c Q l P + A P p L A x g o X Y + w M 2 / o C F n y C W C j Y W3 m w W R I P x D j N z 5 s w 9 d 8 5 w F V v X X M H Y c 4 / U 2 9 c / M B g a G h 4 Z H R s P R y Y m M 6 5 V c V S e V i 3 d c g 4 V 2 e W 6 Z v K 0 0 I T O D 2 2 H y 4 a i 8 6 x S 3 m 7 d Z 6 v c c T X L P B A 1 m + c N u W R q R U 2 V B V H 5 n G J 4 p / W C t y H q x 7 w Q i b I 4 8 2 O 2 E y Q C E E U Q O 1 b k H j m c w I K K C g x w m B C E d c h w a R w h A Q a b u D w 8 4 h x C m n / P U c c w a S u U

Figure 8: Distributions of attention weights in edge estimation on the grid dataset. The blue represents the distribution of nodes predicted to have no connection to the new node, and the orange represents that of nodes predicted to have connection. More than 90 % of attention weights are less than 0.05 for the former distribution, whereas approximately 70 % of attention weights are less than 0.05 and more than 15 % are larger than 0.95 for the latter. Note that the scale of the y-axis is different between the top and halves.

Results on lobster dataset. Dataset size N , maximum graph size |V | max , and the number of node/edge labels a, b are shown as (N, |V | max , a, b).

Figure 10: Generated graphs (grid).

Figure 14: Generated molecular graphs.

Results on synthetic graphs (top) and real-world graphs (bottom). The dataset size N , maximum graph size |V | max , and the number of node/edge labels a, b are shown as (N, |V | max , a, b). AB 0.269 0.182 0.249 0.017 2.0 0.046 0.049 0.111 0.010 4.7 94.9 99.8 94.8 0.0206 8.4

Table content: <table><tr><td/><td/><td colspan="3">Grid (500, 100, 3, 2)</td><td/><td colspan="5">Community (500, 100, 4, 2)</td><td>B-A (500, 100 , 2, 3)</td></tr><tr><td/><td colspan="11">deg. clus. orbit GK time deg. clus. orbit GK time deg. clus. orbit GK time</td></tr><tr><td>DeepGMG</td><td colspan="11">1.315 1e-5 0.682 0.409 15.9 1.515 1.074 1.118 0.233 9.2 1.839 1.568 1.075 0.257 9.1</td></tr><tr><td>GraphRNN</td><td>5e-4</td><td>0</td><td colspan="9">2e-5 0.289 1.9 0.011 0.121 0.024 0.061 3.9 0.359 0.096 0.130 0.025 3.4</td></tr><tr><td colspan="12">GraphRNN-S 0.040 8e-4 0.001 0.287 1.1 0.633 0.195 0.427 0.062 2.5 0.581 0.159 0.158 0.037 2.6</td></tr><tr><td>GRAM</td><td colspan="11">0.105 0.002 0.013 0.287 0.8 0.011 0.025 0.009 0.016 1.0 0.034 0.009 0.024 0.015 1.0</td></tr><tr><td>GRAM-A</td><td colspan="11">0.314 0.007 0.099 0.295 0.7 0.031 0.004 0.038 0.016 0.9 0.061 0.094 0.045 0.015 1.0</td></tr><tr><td>GRAM-B</td><td colspan="11">0.029 0.002 0.011 0.287 0.7 0.029 0.056 0.015 0.019 0.9 0.063 0.005 0.031 0.015 1.0</td></tr><tr><td colspan="12">GRAM-AB 0.357 0.015 0.126 0.309 0.7 0.164 0.080 0.080 0.020 0.9 0.044 0.015 0.031 0.020 0.9</td></tr><tr><td/><td/><td colspan="3">Ego (605, 399, 1, 1)</td><td/><td/><td colspan="3">Protein (734, 500, 89, 1)</td><td/><td>Molecular (250k, 38, 9, 3)</td></tr><tr><td/><td colspan="11">deg. clus. orbit GK time deg. clus. orbit GK time valid unique novel GK time</td></tr><tr><td>DeepGMG</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td colspan="2">-84.5 99.1 83.8 0.0201 -</td></tr><tr><td colspan="12">GraphRNN 0.117 0.615 0.043 0.028 16.0 0.040 1.256 0.506 0.011 22.4 11.1 100.0 11.1 0.0284 20.5</td></tr><tr><td colspan="12">GraphRNN-S 0.306 0.337 0.314 0.067 11.4 0.523 1.247 0.123 0.019 13.7 26.2 99.9 26.2 0.0551 12.4</td></tr><tr><td>GRAM</td><td colspan="11">0.141 0.160 0.058 0.034 2.5 0.154 0.232 0.257 0.013 6.9 92.7 100.0 92.7 0.0198 9.5</td></tr><tr><td>GRAM-A</td><td colspan="11">0.139 0.268 0.062 0.031 2.0 0.224 0.569 0.425 0.011 4.9 95.0 100.0 95.0 0.0198 9.4</td></tr><tr><td>GRAM-B</td><td colspan="11">0.108 0.083 0.033 0.017 2.0 0.154 0.247 0.040 0.010 4.6 94.3 100.0 94.2 0.0206 8.5</td></tr><tr><td>GRAM-</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Total computational complexity and minimum sequential operations during training.

Table content: <table><tr><td>Method</td><td>Total Complexity</td><td>Minimum Sequential Operations</td></tr><tr><td>DeepGMG</td><td/><td/></tr></table>

Average QED score.

Table content: <table><tr><td/><td>QED</td></tr><tr><td>Train</td><td>0.732</td></tr><tr><td>DeepGMG</td><td>0.644</td></tr><tr><td>GraphRNN</td><td>0.563</td></tr><tr><td colspan="2">GraphRNN-S 0.496</td></tr><tr><td>GRAM</td><td>0.722</td></tr><tr><td>GRAM-A</td><td>0.722</td></tr><tr><td>GRAM-B</td><td>0.691</td></tr><tr><td>GRAM-AB</td><td>0.694</td></tr><tr><td>A.7.4 ABLATION STUDY</td><td/></tr></table>

Results of ablation study. .009 0.024 0.015 0.001 5e-4 6e-5 0.049 w/o bias in feature extraction 0.034 0.020 0.033 0.016 0.003 1e-4 2e-4 0.054 w/o bias in edge estimation 0.050 0.035 0.042 0.017 0.002 3e-4 8e-5 0.054 A.7.5 VISUALIZATION OF GENERATED GRAPHS Visualizations of generated graphs on each dataset are shown in Figures

Table content: <table><tr><td/><td/><td colspan="2">Grid</td><td/><td/><td colspan="2">Community</td></tr><tr><td/><td>deg.</td><td>clus.</td><td>orbit</td><td>GK</td><td>deg.</td><td>clus.</td><td>orbit</td><td>GK</td></tr><tr><td>GRAM</td><td colspan="8">0.105 0.002 0.013 0.287 0.011 0.025 0.009 0.016</td></tr><tr><td colspan="9">w/o bias in feature extraction 0.111 0.001 0.009 0.287 0.006 0.007 0.016 0.016</td></tr><tr><td>w/o bias in edge estimation</td><td colspan="8">0.247 0.272 0.190 0.306 0.066 0.037 0.038 0.017</td></tr><tr><td/><td/><td colspan="2">B-A</td><td/><td/><td colspan="2">Lobster</td></tr><tr><td/><td>deg.</td><td>clus.</td><td>orbit</td><td>GK</td><td colspan="3">deg. clus. orbit</td><td>GK</td></tr><tr><td>GRAM</td><td colspan="2">0.034 0</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
# Response to rebuttal I would like to thank their authors for their rebuttal. After reading the other reviews, the author response and the revised manuscript, I have decided to keep my score of weak reject for the time being. In short, while I appreciate the effort the authors put in partly addressing some of the most important comments raised during the review process, I think the paper would greatly benefit from some additional work. In particular: (1) Given the emphasis on scalability, I still believe the authors should carry out more thorough experiments to characterize the runtime of their approach with respect to different characteristics of the graphs. While the result provided in the response to Reviewer #3 is a first step, I recommend the authors to extend it by (1) varying graph size (in terms of nodes and edges); (2) varying graph type and (3) reporting the speedup with respect to other baselines. (2) To the best of my knowledge, the ablation experiment in Section A.7.4 does not provide results for the setting in which no graph attention mechanism is used at all, neither for the case where the graph attention mechanism used is identical to GAT (restricted to 1-step neighbourhoods). (3) While NSPDK might be a reasonable choice, I still am of the opinion that the choice of graph kernel for this purpose is highly arbitrary and, thus, should be investigated further. Given that such a choice is being used to define a performance metric, which moreover is being highlighted as a contribution, the authors should study the robustness of the metric to the choice of graph kernel, as well as its sensitivity to known perturbations. (4) Finally, I did not see any error bars added to the main results in the paper. Despite these shortcomings, I would like to reiterate that I believe the proposed approach is promising and, with some additional work, would be a contribution definitely worth publishing. Therefore, I would like to encourage the authors to further revise the manuscript. # Summary In this paper, the authors propose an auto-regressive deep generative model for graph-structured data, motivated by the goal of scalability with respect to graph size, graph density and sample size. In a nutshell, the approach follows closely the ideas in [1, 2], which model graph generation as an auto-regressive process after fixing or sampling an ordering for the nodes. Unlike [1, 2], however, the proposed method makes use of graph convolutions and a graph attention mechanism, closely related to GAT [3], to parametrize the conditional distributions of node/edges given the previously generated graph elements. The performance of the proposed approach is evaluated in comparison to [1, 2] in several synthetic and real-world datasets, using MMD [4] between generated and held-out test graphs as metric. Unlike [2], which applies MMD on three graph statistics (degree, clustering coefficient and average orbit counts), this manuscript proposes to evaluate MMD using a graph kernel as well [5]. # High-level assessment The main contribution in this paper is to combine a graph attention mechanism, which can be seen as a simplification of GAT [3], with deep autoregressive graph models, such as DeepGMG [1] or GraphRNN [2]. In this way, the manuscript has a large conceptual overlap with the method in [6], which can be nevertheless be regarded as concurrent rather than prior work. From a methodological perspective, I believe the contribution is sound and sufficiently novel, although perhaps slightly on the incremental side. However, the current version of the manuscript has shortcomings regarding (i) lack of clarity in the exposition of the method’s relation to prior work, low-level implementation details and experimental setup and (ii) insufficient experimental results to back up some of the authors’ claims. Nonetheless, I believe the proposed approach is promising, and encourage the authors to address or clarify these issues during the author discussion phase. # Major points / suggestions 1. The manuscript presents the proposed approach in a way that does not clearly differentiate between prior work and original contributions. In particular, I believe that the ideas in Section 3.1 and 3.2 are almost identical to those in [1, 2], the graph attention mechanism in Section 3.3 can be seen as a minor modification of GAT [3], and Section 3.4 also has a strong conceptual overlap with [1, 2]. I would encourage the authors to be more clear with respect to what is novel and what is borrowed from prior work. Moreover, when slightly departing from prior work (e.g. the modifications applied to the graph attention mechanism in Section 3), I would also encourage the authors to focus on explaining what specifically has changed and what is the rationale behind those design choices, rather than explaining the entire mechanism “from scratch”, leaving up to the reader to figure out what is novel. 2. The paper’s clarity could be improved, with some parts presented in an unnecessarily complicated manner (e.g. the graph attention mechanism) and others without sufficient detail (e.g. the edge estimator module, the zero-ing heuristic for attention or the generation of graphs based on “seed graphs”, which is only mentioned in the appendix). For example, regarding the graph attention mechanism, I would recommend: (i) explaining more clearly what the “feature vector of node ” is exactly in relation to the notation of Section 3.1; (ii) if the query, key and value matrices are identical, as the text seems to imply, I would rewrite the equations directly in terms of which would simplify the notation significantly; (iii) perhaps most importantly, the bias functions , and should be defined mathematically and discussed in greater detail and (iv) the output FNN should also be described mathematically. Finally, as mentioned above, I would emphasise the differences between the proposed attention mechanism and GAT. The edge estimator mechanism is described too imprecisely in Section 3.4.4. While Section A.4 definitely helps, I would recommend defining the entire operation mathematically in Section 3.4.4 as well. Likewise, a precise mathematical definition of GRAM-A in Section 3.5.2 would also be helpful. Finally, as mentioned in this forum by Prof. Ranu prior to this review’s writing, the graph generation procedure described in Section A.7.2 seems unconventional. I would encourage the authors to both clarify what they mean by “for the convenience of implementation” and to investigate whether the experimental conclusions are affected by this departure from prior practices. 3. Key details about the experimental setup, such as the hyperparameter selection protocol for the proposed approach and baselines, as well as the resulting architectures, seems to be missing, making it difficult to assess if the experimental setup is “fair”. In particular, all methods should be allowed to use a similar number of parameters or, alternatively, have their hyperparameters tuned equally carefully for each dataset separately. 4. Most importantly, I believe the experimental results are insufficient to back up some of the claims made in the introduction. 4.1. Despite the focus on scalability throughout the motivation, there are no experiments systematically exploring how the runtime at train and test time of the proposed approach and the main baselines scales with respect to sample size, number of nodes per graph and graph density. Moreover, no results are provided for large graphs (e.g. ~5k nodes as in [6]). 4.2. The graph attention mechanism was claimed to be an original contribution. However, no results are provided to evaluate its advantages with respect to the different GAT variants nor ablation studies to see its usefulness relative to a variant of the proposed approach using only graph convolutions. 4.3 The idea of using MMD in conjunction with graph kernels as a performance metric is interesting. However, there is no investigation of key aspects such as (i) its relation to other metrics and (ii) the impact that the choice of graph kernel, among the many available, and/or of graph kernel hyperparameters has on the resulting metric (see [7] for a comprehensive review on graph kernels). 4.4. Finally, the results have been reported without error bars, making it difficult to quantify the statistical significance of the observed performance differences between approaches. # Minor points / suggestions 1. I strongly believe the authors should adapt the manuscript to mention [6] and related/concurrent work. Ideally, including it as an additional baseline would be even better, but not necessary given the limited rebuttal time. Nevertheless, this point was not taken into consideration when scoring the manuscript, given how recent [6] is. # References [1] Li, Yujia, et al. *Learning deep generative models of graphs.* *International Conference on Machine Learning.* 2018. [2] You, Jiaxuan, et al. *Graphrnn: Generating realistic graphs with deep auto-regressive models.* *International Conference on Machine Learning.* 2018. [3] Veli?kovi?, Petar, et al. *Graph attention networks.* *International Conference on Learning Representations*. 2018. [4] Gretton, Arthur, et al. *A kernel method for the two-sample-problem.* Advances in Neural Information Processing Systems. 2007. [5] Costa, Fabrizio, and Kurt De Grave. *Fast neighborhood subgraph pairwise distance kernel.* Proceedings of the 26th International Conference on Machine Learning. Omnipress; Madison, WI, USA, 2010. [6] Liao, Renjie, et al. *Efficient Graph Generation with Graph Recurrent Attention Networks.* *Advances in Neural Information Processing Systems.* 2019. [7] Kriege, Nils M., Fredrik D. Johansson, and Christopher Morris. *A Survey on Graph Kernels.* *arXiv preprint arXiv:1903.11835* (2019).