Attentive Walk-Aggregating Graph Neural Networks
Authors: Mehmet F Demirel
Shengchao Liu
Siddhant Garg
Zhenmei Shi
Yingyu Liang
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) have been shown to possess strong representation power, which can be exploited for downstream prediction tasks on graph-structured data, such as molecules and social networks. They typically learn representations by aggregating information from the $K$-hop neighborhood of individual vertices or from the enumerated walks in the graph. Prior studies have demonstrated the effectiveness of incorporating weighting schemes into GNNs; however, this has been primarily limited to $K$-hop neighborhood GNNs so far. In this paper, we aim to design an algorithm incorporating weighting schemes into walk-aggregating GNNs and analyze their effect. We propose a novel GNN model, called {\AWARE}, that aggregates information about the walks in the graph using attention schemes. This leads to an end-to-end supervised learning method for graph-level prediction tasks in the standard setting where the input is the adjacency and vertex information of a graph, and the output is a predicted label for the graph. We then perform theoretical, empirical, and interpretability analyses of {\AWARE}. Our theoretical analysis in a simplified setting identifies successful conditions for provable guarantees, demonstrating how the graph information is encoded in the representation, and how the weighting schemes in {\AWARE} affect the representation and learning performance. Our experiments demonstrate the strong performance of {\AWARE} in graph-level prediction tasks in the standard setting in the domains of molecular property prediction and social networks. Lastly, our interpretation study illustrates that {\AWARE} can successfully capture the important substructures of the input graph. The code is available on \href{https://github.com/mehmetfdemirel/aware}{GitHub}.

Published in Transactions on Machine Learning Research (08/2022)
Attentive Walk-Aggregating Graph Neural Networks
Mchmet F. Demirel
Cemmrel@cs.uisc..oom
Deportment of Computer Sciences University of Wisconsin-Madisn Madison
Shengchao Liu
liusheng@miiaa, quebec
Quebec AI Institute (Mila)
Siddhant Garg Amazon Aleza AI
sidgerggaamazon.coo
Zhenmei Shi
zhmeishi@cs wwwp::iiwwwsssss.ccoomm. edu
Deportment of Computer Sciences University of Wiscoonin-Madison
Yingyu Liang
yliang Ccs. wisc. edu
Department of Computer Sciences University of Wisconsin-Mudison
Reviewed on OpenReview: https: openreview. net/ forum? id= TWSTy
Abstract
Graph neural networks (GNNs) have been shown to possess strong representation power, which can be exploited for downstream prediction tasks on graph-structured data, such as molccules and social networks. They typically learn representations by aggregating information from the K K-hop neighborhood of individual vertices from the emumerated walks in the graph. Prior studies have demonstrated the effectiveness of incorporating weighting schemes into GNNs; however, this has been primarily limited to K-hop neighborhood GNNs so far. In this paper, we aim to design an algorithm incorporating weighting schemes into walk-aggregating GNNs and analyze their effect. We propose novel GNN model, called AWARE, that aggrogates information about the walks in the graph using attention schemes. This leads to an end-to-end supervised learning method for graph-level prediction tasks in the standard setting where the input is the adjacency and vertex information of graph, and the output is predicted label for the graph. We then perform theoretical, empirical, and interpretability analyses of AWARE. Our thcoretical analysis in simplified setting identifies successful conditions for provable guarantees, demonstrating how the graph information is encoded in the representation, and how the weighting schemes in AWARE affect the reprosentation and Icarning performance. Our experiments demonstrate the strong performance of AWARE in graph-level prediction lasks in the standard set the domains of molecular property prediction and social networks. Lastly, our interpretation study illustrates that AWARE can successfully capture the important substructures of the input graph. The code is available on GitHub.
1 Introduction
The increasing prominence of machine learning applications for graph-structured data has lead to the popularity of graph neural networks (GNNs) in several domains, such as social networks (Kipf Welling, 2016), molecular property prediction (Duvenaud et al., 2015), and recommendation systems (Ying al., 2018). Several empirical and theoretical studies (e.g., (Duvenand et al., 2015; Kipf & Welling, 2016; Xu

---

Published in Transactions on Machine Learning Research (08/2022)
et al., 2019; Dehmamy et al., 2019)) have shown that GNNs can achieve strong representation power by constructing representations encoding rich information about the graph.
A popular approach of learning GNNs involves aggregating information from the K-hop neighborhood of individual vertices in the graph (e.g., (Kipf & Welling, 2016; Gilmer et al.; 2017; Xu et al., 2019)). An alternative approach for learning graph representations via walk aggregation (e-g., (Vishwanathan et al., 2010; Shervashidze et al., 2011; Perozzi al., 2014)) that enumerates and encodes information of the walks in the graph. Existing studies have shown that walk-aggreegtingg GNNs can achieve strong empirical performance with concrete analysis of the encoded graph information (Liu et al., 2019a). The results show that the approach can encode important information about the walks in the graph. This can potentially allow emphasizing and aggregating important walks to improve the quality of the representation for downstream prediction tasks.
Weighting important information has been a popular strategy in recent studies on representation learning. It is important to note that the strong representation power of GNNs may not always translate to learning the best. representation amongst all possible ones for the downstream prediction tasks. While the strong representation power allows encoding all kinds of information, a subset of the encoded information that is not relevant for prediction may interfere or even overwhelm the information useful for prediction, leading to sub-optimal performance. A particularly attract ive approach to address this challenge is by incorporating weighting schernes into GNNs, which is inspired by the strong empirical performance of attention mechanisms (Bahdanau et al., 2014; Luong et al., 2015; Xu et al., 2015; Vaswani et al., 2017; Shankar et al., 2018; Deng et al., 2018) for natural language processing (e.g., (Devlin al., 2019)) and computer vision tasks (e.g., (Dosovitskly et al., 2020)). In the domain of graph representation learning, recent studies (Gilmer et al., 2017; Veličković et al., 2017; Yun et al., 2019; Maziarka. et al., 2020; Rong et al., 2020) have used the attention mechanism to improve the empirical performance of GNNs by learning to select important information and removing the irrelevant ones. These studies, however, have only explored using attention schemes for K K-hop neighborhood GNNs, and there has been no corresponding work exploring this idea for walk-nggrogating GNNs.
In this paper, we propose to theoretically and empirically examine the effect of incorporating weighting schemes into walk-aggregating GNNs. To this end, we propose a simple, interpretable, and end-to-end supervised GNN model, called AWARE (Attentive Walk-Aggregating GRaph Neural NEtwork), for graph-level prediction in the standard setting where the input. is the adjacency and vertex information of graph, and the output is a predicted label for the graph. AWARE aggregates the walk information by weighting schemes at distinct levels (vertex-, walk-, and graph-level). At the vertex (or graph) level, the model weights different directions in the vertex (graph, respectively) embedddng space to emphasize important feature in the embedding space. At the walk level, weights the embeddings for different walks in the graph according to the embeddings of the vertices along the walk. By virtue of the incorporated weighting schemes at these different levels, AWARE can emphasize the information important for prediction while diminishing the irrelevant ones meading to representations that can improve learning performance. We perform an extensive three-fold analysis of AWARE as summarized below:
We analyze AWARE in the simplified setting when the weights depend only on the latent, vertex representations, identifying conditions when the weighting schemes improve learning. Prior weighted GNNs (e.g., (Veličković et al., 2017; Maziarka et al., 2020)) do not enjoy similar theoretical guarantees, making this the first provable guarantee on the learning performance of weighted GNNs to the best of our knowledge. Furthermore, current understanding of weighted GNNs typically focuses only on the positive effect of weighting on their representation power. In contrast, we also explore the limitation scenarios when the weighting does not translate to stronger learning power.
Theoretical Analysis:
Empirical Analysis: We empirically evaluate the performance of AWARE on graph-level prediction tasks from two domains: molecular property prediction (61 tasks from 11 popular benchmarks) and social networks (4 tasks). For both domains, AWARE overall outperforms both traditional graph representation methods as well as recent GNNs (including the ones that use attention mechanisms) in the standard setting.
Interpretabilityy Analysis: We perform an interpretation study to support our design for AWARE as well the theoretical insights obtained about the weighting schemes. We provide a visual illustration that
2

---

Published in Transactions on Machine Learning Research (08/2022)
AWARE can extract the important sub-graphs for the prediction tasks. Furthermore, we show that the weighting scheme in AWARE can align well with the downstream predictors.
2 Related Work
Graph neural networks (GNNs). GNNs have been the predominant method for capturing information of graph data (Li et al., 2015; Duvenaud et al., 2015; Kipf & Welling, 2016; Kearnes et al., 2016; Gilmer et al., 2017). A majority of GNN methods build graph representations by aggregating information from the K-hop neighborhood of individual vertices (Duvenaud et al., 2015; Li et al., 2015; Battaglia et al., 2016; Kearnes et al., 2016; Xu et al., 2019; Yang et al., 2019). This is achieved by maintaining a latent representation for every vertex, and iteratively updating it to capture information from neighboring vertices that are K-hops away. Another popular approach is enumerating the walks the graph and using their information (Vishwanathan et al., 2010; Shervashidze et al., 2011; Perozzi et al., 2014). Liu et al. (2019a) use the motivation of aggregating information from the walks by proposing GNN model that can achieve strong empirical performance along with concrete theoretical analysis.
Theoretical studies have shown that GNNs have strong representation power (Xu et al., 2019; Dehmamy et al., 2019; Liu et al., 2019a), and have inspired new disciplines for improving their represent at further (Morris et al., 2019; Azizian& & mare lelarge, 2021). To this extent, while the standard setting of GNNs has only vertex features and the adjacency information as inputs (sce Section 3), many recent GNNs (Kearnes et al., 2016; Gilmer et al., 2017; Coors al., 2018; Yang et al., 2019; Klicpera et al., 2020; Wang et al., 2021) exploit extra information, such as edge features and 3D information, in order to gain stronger performance. In this work; however, we focus on analyzing the effect of applying attention schemns for representation learning, and thus want to perform this analysis in the standard setting.
GNNs with attention. The empirical effectiveness of attention mechanisms has been demonstrated on language (Martins & Astudillo, 2016; Devlin et al., 2019; Raffel et al., 2020) and vision tasks (Ramachandran
et al., 2019; Dosovitskiy et al., 2020; Zhao et al., 2020). This has also been extended to the K-hop GNN research line where the main motivation is to dynamically learn a weighting scheme at various granularities, c.g.; vertex-, edge- and graph-level. Graph Attention Network (GAT) (Veličković et al., 2017) and Molocule Atlention Transformer (MAT) (Maziarka et al., 2020) utilize the atlention idea in their message passing functions. G'raanformer (Rong et al., 2020) applies an attention mechanism at both vertex- and edge-levels to better capture the structural information in molecules. ENN-S2S (Gilmer ct al., 2017) adopts an attention module (Vinyals et al., 2015) as a readout function. However, all such studies are based on K-hop GNNs, and to the best of our knowledge, our work the first to bring attention schemes into walk-aggregation GNNs.
3 Preliminaries
Graph data. We assume an input graph G-(V, A) consisting of vertex attributes V and an adjacency matrix A. The vertices are indexed by [m]-(1,..., m... Suppose each vertex has C discrete-valued attributes, 1 and the jth attribute takes values in a set of size ky. Let h/= 1 be the one-hot encoding of the jth attribute for vertex i. The vertex is represented as the concatenation of C attributes, i.e., hy=[h/; :.:::...;;: : E {0, 1 where K= E ky. Then V is the set {hr
We denote the adjacency matrix by AE (0, 1] 1 where A1,==1 indicates that vertices i and j are connected. We denote the set containing the neighbors of vertex by [iim)[jj(m] : -1,
Although many GNNs exploit extra input information like edge attributes and 3D information, our primary focus is on the effect of weighting schemes. Hence, we perform our analysis in the standard setting that only has the vertex attributes and the adjacency matrix of the graph as the input.
Description of Vertex Attributes. For molecular graphs, vertices and edges correspond to atoms and bonds, respectively. Each vertex E [m] will then possess useful attribute information, such as the atom symbol and whether the atom is acceptor or donor. Such vertex attributes are folded into a vertex attribute
I Note that the vertex attributes are discrete-valued in general. there are numeric attributes, they can simply be padded to the learned embedding for the other attributes.
3

---

Published in Transactions on Machine Learning Research (08/2022)
matrix R {0,1)mxC where C' is the number of attributes on each vertex [m]. Here is concrete example:
R., - 1 Ri...... Ri,7, Ri,8) atom symbol R1,1 E C,,, atom degrec R1 E (0,1,2,3,4,5,6)
acceptor R,,7 {0, 1}: is donor R4s {0,
The matrix R can then be translated into the vertex attribute vector set V using one-hot vectors for the altribules.
For social network graphs, vertices and edges correspond to entities (actors, online posts) and the connections between them, respectively. For the social network graphs in our experiments, we follow existing work and utilize the vertex degree as the vertex attribute (i.e., C' = 1).
Vertex embedding. We define an r-dimensional embedding of vertex by:
Wh,,
(1)
where :=!:::...;
and WieRexk, is the embedding matrix for each attribute j E [C]. We denote the embedding corresponding to V by F = :m:
Walk aggregation. Unlike the typical approach of aggregating K-hop neighborhood information, walk aggregation enumerates the walks in the graph, and uses their information (e.g., (Vishwanathan al., 2010; Perozzi et al., 2014)). Liu et al. (2019a) utilize the walk-aggregation strategy by proposing the N-gram graph GNN, which can achieve strong empirical performance, allow for fine-grained theoretical analysis, and potentially alleviate the over-squahhig problem in K-hop GNNs, The N- N-gram graph views the graph as a Bag-of- Walks. It learns the vertex embeddings F Equation (1) in a self-supervised manner. It then enumerates and embeds walks in the graph. The embedding of a particular walk p, denoted as fps is the element-wise product of the embeddings of all vertices along this walk. The embedding for the n-gram walk set (walks of length n),, denoted as f(n): is the sum of the embeddings of all walks of length n. Formally, given the vertex embedding fs for vertex i,
fp = O.. S.. SpP
J(m) = Σ fp:
(2)
p-n-gram
where Oiep is the wise product over all the vertices in the walk p, and Epa-gram is the sum over all the walks p in the n-gram walk set. It has been shown that the method is equivalent to message-passing
GNN described as follows: set F(1) = F [fi:..:: and f()) = 11n1=Eeemm fú, and then for 2 2 T:
F()) = (F() @ F()). and f()) = F(m)
(3)
where @ is the clement-wise product and denotes a vector of ones in T The final graph embedding is given by the concatenation of all f(n) 's, ie., (rr f(ry).
Compared to K-hop aggregation strategies, this formulation explicitly allows analyzing representations different granularitics of the graph: verticos, walks, and the entire graph. This provides motivation for capitalizing the N-gram walk-aggregation strategy for incorporating and analyzing the elfect of weighting schemes on valkk-aggregatio GNNs. The principled design facilitates theoretical analysis of conditions under which the weighting schemes can be beneficial. Thus, in this paper, we analyze the effect of incorporating attention weighting schemes on the N-gram aalk-agggooattin GNN.
4 AWARE: Attentive Walk- Balk--Aggeggatig Graph Neural Network
We propose AWARE, an end-to-end fully supervised GNN for learning graph embeddings by aggregating information from walks with learned weighting schemes. Intuitively, not all walks in graph equally
4

---

Published in Transactions on Machine Learning Research (08/2022)
important for downstream prediction tasks. AWARE incorporates attention mechanism to assign different contributions to individual walks as well as assigns feature weightings at the vertex and graph embedding levels. These weights are learned in a supervised fashion for prediction. This enables AWARE to mitigate the shortcomings of its unweighted counterpart (Liu et al., 2019a), which computes graph emboddings in an unsuperoised manner only using the graph topology.
At a high level, AWARE first computes vertex embed- dings F, and initializes latent vertex representa- tion Fay by incorporating feature weighting at the vertex level. It then iteratively updates the latent representation F(n) using attention at the walk level, and then performs a weighted summarization at the f(x) for walk sets of length n. The f())s 's are concatenated to produce the graph embedding ftr (G) for the ream task. We now provide more details.
Algorithm 1 AWARE (W, We, W Wg)
Require: Graph G=(V,A), max walk length T 1: Compute vertex embeddings by Eqn (1)
2: F(1) = FW
3: for each [] do
graph level to obtain embeddings
4: Compute Sn using Equ (7)
5: F(n)) (Fo-)((( @ Sn)) @ F(1)
6: end for
7: Set f(n) := a (W
9 (m)) for T 8: Set ftr](G) == [fnj.... ... f(m]
Weighted vertex embedding. Intuitively, some directions in the vertex embedding space are likely to be more important for the downstream prediction task than others. In the extreme case, the prediction task may depend only on a subset of the vertex attributes (corresponding some directions in the embedding space), while the rest may be inconsequential and hence should be ignored when constructing the graph embedding. AWARE weights different vertex features using W, I by computing the initial latent vertex representation F() as:
Ensure: The graph embedding fGm(G)
F(z F), where is computed using Equation (1)
(4)
where a is an activation function, and r' is the dimension of the weighted vertex embedding.
Walk attention. AWARE computes embeddings corresponding to walks of length n in an iterative manner, and updates the latent vertex representations in each iteration using such walk embeddings. When aggregating the embedding of a walk, cach vertex in the walk bound to have a different contribution towards the downstream prediction task. For instance, in molecular property prediction, the existence of chemical bonds between certain types of atoms in the molecule may have more impact on the property to be predicted than others. To achieve this, in iteration n, AWARE updates the latent representations for vertex i from [Fim-1)]s to [F()) by taking an element-wise product of [Fin-))ls with a weighted sum of the latent representation vectors of its neighbors j E (i). Such a weighted update of the latent representations implicitly assigns a different importance to cach neighbor j for vertex i. Assuming that the importance of vertex j for vertex depends on their latent representations, we consider a score function corresponding to the update from vertex j to i as:
Sn : SUs,
(5)
While our theoretical analysis is for weighting schemes defined in Equation (5), in practice one have more flexibility, e.g., one can allow the weights to depend on the neighbors and the iterations. To allow different weights (S(m) j for different iterations n by using the latent representations for vertices from the previous iteration (n- In particular, we use the self-attention mechanism:
[Zmn]s=s = ((in-)) W [F(((1)))
(6)
where [F(n-1) is the latent vector of vertex i at iteration n-1, and W''e''''r' is parameter matrix to be learned. We then define the attention weighting matrix used at iteration n as:
elZem)h-
[S,1js
(7)
EkENTO) elonlee
5

---

Published in Transactions on Machine Learning Research (08/2022)
Using this attention matrix Sn, perform the iterative update to the latent vertex representations via weighted sum of the latent representation vectors of their neighbors:
F(n) (Fie- s.)) F())
This update simple and efficient, and automatically aggregates important information from the verlex neighbors for the downstream prediction task. In particular, it does not have the typical projection operation for aggregating information from neighbors. Instead, it computes the weighted sum and then the element-wise product to aggregate the information.
Weighted summarization. Since the downstream task may selectively prefer certain directions in the final graph embedding space, AWARE learns a weighting W, E R" xr' to compute a weighted sum of latent vertex representations for obtaining walk set embeddings of length n as follows:
(()) (Wy)F()))
(9)
where 1 denotes a vector of ones in R", Walk set embeddings up to length are then concatenated to produce the graph embedding (ir](G) (fa).....
End-to-end supervised training. We summarize the different weighting schemes and steps of AWARE as pseudo-code in Algorithm 1. The graph embeddings produced by AWARE can be fed into any properly-choser predictor he parametrized by 0, so as to be trained end-to-end and a labeled data set S = {(G,, M where G,'s are graphs and yi's are their labels, AWARE can learn the parameters (W, We, Ww, Wg) and the predictor by optimizing the loss
labeled data. For given loss function C,
LAWARE
Σ ho (E[M)
(10)
The N-Gram walk aggregation strategy termed as the N-Gram Graph (Liu et al., 2019a) operates two steps: first to learn a graph embedding using the graph topology without any supervision, and then use a predictor on the embedding for the downstream task. In contrast, AWARE is end-to-end fully supervised, and simultancously learns the vertex/grape embeddings for the downstream task along with the weighting schemes to highlight the important information in the graph and suppress the irrelevant and/or harmful ones. Secondly, the weighting schemes of AWARE allow for the use of simple predictors over the graph embeddings (e.g., logistic regression or shallow fully-connected networks) for performing end-to-end supervised learning. contrast, N-Gram Graph requires strong predictors such as XGBoost (with thousands trees) to exploit the encoded information the graph embedding.
5 Theoretical Analysis
interested in the following two fundamental questions: (1) what representation can it obtain and (2) under what conditions can the weighting scheme improve the prediction performance? In this section, we provide theoretical analysis of the walk weighting scheme.? We consider the simplified case when the weights depend only on the latent embeddings of the vertices along the walk:
For the design of our walk-nggregation GNN with weighting schemes,
Assumption 1. The weights are Sij defined in Equation (5).
First, in Section 5.1 and 5.2, we answer the above two questions under the following simplifying assumption: Assumption 2. W,- W, = I, the number of attributes is C = and the activation is linear (<)) 2.
Forr the other weighting schemes W. and Wg, we know W, weights the vertex embeddings fcr and W, weights the final embeddings F(n), emphasizing important directions in the corresponding space. If W, has singular vector decomposition W. UTVT then will relatively emphasize the singular vector directions with large singular values. Similar for W,- See Section 7 for some visualization.

---

Published in Transactions on Machine Learning Research (08/2022)
In this simplified case, the only weighting is Sty computed by Ww, which allows our analysis to focus on its effect. We further assume that the number of attributes on the vertices is C = 1 to simplify the notations. We will show that the weighting scheme can highlight important information, and reduce irrelevant information for the prodiction, and thus improve learning. To this end, we first analyze what information can be encoded in our graph representation, and how they are weighted (Theorem 1). We then examine when and why the weighting can help learning a predictor with better performance (Theorem 3).
Next, in Section 5.3, we provide analysis for the general setting where W, and W may not be the identity matrix, C² 1, and is the leaky rectified linear wnit (ReLU). The analysis leads to guarantees (Theorem 4 and Theorem 5) that are similar to those in the simplified sctting.
5.1 The Effect of Weighting on Representation
We will show that the oppresenatioon/mmeeddee f(n) is linear mapping of a high dimension vector ((x) into the low dimension embedding space, where the vector C(n) records the statistics about the walks in the graph.
First, we formally define the walk statistics C(n) (a variant of the count statistics defined in (Liu et al., 2019a)). Recall that we assume the number of attributes is C==1= 1. K is the number of possible attribute values, and the columns of the vertex embedding parameter matrix W E R=* are embeddings for different attribute values Let (uu) denote the column for value u, i.e., W (n)= = Wh(u) where h(u) is the one-hot vector of u. Definition 1 (Walk Statistics). A walk lype of length is a sequence of n allribule values where each vi is an attribute value. The walk statistics vector (Gn)GG) E RK" is the histogram of all walk types of length n in the graph G, i.c., each entry is indered by a walk type v and the entry value is the number of walks with sequence of attribute values v in the graph. Furthermore, let ((r(GG) be the concatenation of (r)(()).....()))))
(v), '2,-.. ,u,)
When G is clear from the context, we write C(n) and c[T) for short.
Note that the walk statistics ((n) may not completely distinguish any two different graphs, ie., there can exist two different graphs with the same walk statistics C(n) for any given Figure 1 shows such an example where the given two graphs are isomorphically different despite having the same walk statistics (())+(2)) and (3)- On the other hand, such indistinguishable cases are highly unlikely in practice. We also acknowledge other well-known statistics for distinguishability that have been used for analyzing GNNs, in particular, the Weisfeiler-Lehman isomorphism lest. (e.g., Xu el al. (2019)). Nevertheless, it is crucial noting here that the goal of our theoretical analysis is very different. Namely, while the Weisfeiler-Lehmal test has been used as an important tool to analyze the representation power of GNNs, the goal of our analysis is the prediction performance. As pointed out in the introduction, strong representation power may not always translate to good prediction performance. In fact, very strong representation power emphasizing too much on graph distinguishability is harmful rather than beneficial for the prediction. For example, a good representation for prediction should emphasize the effective features related to class labels and remove irrelevant features and/or noise. II two graphs only differ some features irrelevant to the class label, then it is preferable to get the same representation for them, rather than insisting on graph distinguishabilityy Weighting schemes can potentially down-weight or remove the irrelevant information and improve the prediction performance.
Next, we introduce the following notation for the linear mapping projecting C(n) to the representation S(())- Definition 2 (e-way Column Product). Let A be a d x N matria, and let E be a natural integer. The E-way column product of A is a d x N' matric denoted as Ale,, whose column indezed by a sequence (i1, ie) is the wlsment-wise product of the .1,ū2,...,44" columns of A, i.e., (ūz, ii)) column in Al is AG, @ A,, ① .... Ai, where A₁ for E [N] is the j-th column in A, and O is the element- wise product.
In particular, W(n) is an by K matrix, whose columns are indexed by walk types (01, (21. 1., ,2) and equal W(r)) @ ((22) @... @ W(..).
Definition 3 (Walk Weights). The weight of a walk type v = (v1,-.., vp) is
X(e) II
((W())) ((41))
(1I)
i=1
where S()))) is the weight function in Equation (5).
7

---

Published in Transactions on Machine Learning Research (08/2022)
A
B
B
B
B
(a)
A
B
B
B
B (b)
B
B
B
Figure 1: Two diffeernnt graphs with the same walk-statistics C(1), C(2), and G(3)- Vertices with the same letters have entirely identical altribute values. All edges undirected and identical.
The following theorem then shows that f(n) can be viewed as a compressed version (linear mapping) of the walk statistics, weighted by the attention weights S.
Thcorem Assume Assumption 1 and 2. The embedding ((n) is a linear mapping of the walk statistics C(n)
f(n) = (m)
(12)
where M(n) Will is matriz depending only on W, and A(n) is K" (""-dimensional diogonal matriz whose columns indexed by walk types and have diagonal entries M(v). Therefore,
= fm==Accp
(13)
where M is a diago-ala matriz with diagonal blocks Mez, ...,, Mery, and A is block diagonal with blocks A(1)- A(g)....... A(T).
Proof. It sufficient prove the first statement with M(n) W/ll, as the second one directly follows. To this end, we will first prove the following lemma.
Lemma Let Psm be the set of walks starting from vertex i and of length n. Then the latent vector on verter is:
[F()):=
Σ ((pp)
(14)
DEP
kEP
where M(e)) is the weight for the sequence of allribute values on p, and (Feyl is the element-wise product of all the [Feyl&'s on p.
Proof. We prove the lemma by induction. For n 1, it is trivially true.
Suppose the statement is true for n 1. Then recall that [Fmy]s is constructed by weighted-suumiing up all the latent vectors [F(n-))]s from the neighbors of i, and then element-wise product with [Fay]e = ft. That
is,
Σ Syil Foi(Foni)) JEN,
(Fa))i-
(15)
8

---

Published in Transactions on Machine Learning Research (08/2022)
So letting Nr denote the set of neighbors of i, we have by induction
[(m))s
Σ
@ [F())
(16)
JENS
E
Sji
Σ
((mp)
OLFEDDl keP
[Fail
(17)
JEN, pEP
O O(F()) 1) kEP
Σ iEN, PEP 3-
Σ
Sjo((pp)
[Rwyle
(18)
By coucatenating to the walks p E Pin-1 for all neighbors j E NG, we obtain the set of walks starting from and of length n, ie., Pi,.. Furthermore, for path obtained by concatenating and p Pj,n-1 the weight is exactly Sjz {(tp). Therefore,
OIFUUlA) )) kep
[F(n)L== = E Σ JENi PEPsin-1
Sys M(p)
[Fal o
(19)
= Σ
M(p))
(20)
PEP
kEP
By induction, we complete the proof.
We now use Lemma to prove the theorem statement. Recall that h& is the hot vector for the attribute on vertex k. Let ep E 1)K" be the onc-hot vector for the walk type of walk p.
f(m) = Fin)
(21)
m
(22)
m
Σ
Σ
((ep)
OFFal
(23)
pEP
kEP
Σ
A(1p)
(24)
powalks of length
kEP
M(ep)
OWhkk)
(25)
powalks of longth
kEP
Σ
A(1,))
(26)
pewalks of length
W/n)
Σ
A(pp)e
(27)
powalles of length
Win C(n)-
(28)
The third line follows from Lemma 1. The forth line follows from that the union of Pi,. for all is the set of walks of length n. The sixth line follows from the definition of Wini and ep. The last line follows from the definitions of A(n) and C())-
Remark. Theorem 1 shows that the embedding f(n) can encode a compressed version of the weighted walk statistics An)) Note that similar to A(n), C(n) is in high dimension K". Its entries indexed

---

Published in Transactions on Machine Learning Research (08/2022)
by all possible sequences of the attribute values (.1,..., 22), and the entry value is just the count of the corresponding sequence in the graph. (n)) is thus an entry-wise weighted version of the counts, iee, weighting the walks with walk type v (Vi,..., 2x) by the corresponding weight A(v).
In words, ((n) is first weighted by our weighting scheme where the count of each walk type v is weighted by the corresponding walk weight A(u), and then compressed from the high dimension RK" to the low dimension R". Ideally, we would like to have relatively larger weights on walk types important for the prediction task and smaller for those not important. This provides the basis for the focus of our analysis: the effect of weighting for the learning performance.
The N-gram graph method is a special case of our method, by setting the message weights S(,,) to be always (and thus An) being an identity matrix). Then we have fin) Wl Our method thus enjoys greater representation power, since it can be viewed as generalization that allows to weight the features. What is more important, and is also the focus of our study, is that this weighting can potentially help learn a predictor with better prediction performance. This is analyzed in the next subsection.
Remark. The weighted walk statistics (m) is compressed from a high dimension to a low dimension by multiplying with W(n), For the unweighted case, the analysis in (Liu et al., 2019a) shows that there cxists a large family of W (c.g.. the entrics of W are independent Rademacher variables) such that W(n] has the Restricted Isometry Properly (RIP) and thus ((x) can be recovered from f(x) by compressive sensing techniques (see the review in Appendix A.1), i.e. fin) encodes C(n).
A similar result holds for our weighted case. In particular, it is well known in the compressive scnsing literature that when WIn] has RIP, and (n)) is sparse, then (1))())) can be recovered from S(m), i.e., f(x preserves the information of (n)) However, it is unclear if there exists W such that Win) can have RIP. We show that a wide family of W satisfy this and thus (()) can be recovered from S(m)-
Theorem 2. Assume Assumption 1 and 2. Ifr = Q((ns log K)/²²) where 8n is the sporsity of c(n), then there is a prior distribution over W such that with probability 1- cxp(- (x)() Winl satisfies (8p, CRIP.. Therefore, r = Anss log K) and (n) is the sporsest vector satisfying f(n) Will then with probability 1 - exp( 1xexp(
1/3))) (())(()) can be recovered from fin).
Proof. The first statement follows from Theorem 8 in Appendix A.2, and the second follows from Theorem in Appendix A.1.
The distribution of W satisfying the above can be that with (properly scaled) i.idd Rademacher entries or Gaussian entries. Since this is not the focus of our paper, below we simply assume that Win) (and thus M) has RIP and focus analyzing the effect of the weighting on the learning over the representations.
5.2 The Effect of Weighting on Learning
Since have shown that the embedding f(r) can be viewed as linear mapping of the weighted walk statistics to low dimensional representations, we are now ready to analyze if the weighting can potentially improve the learning.
We now illustrate the intuition for the benefit of appropriate weighting. First, consider the case where we learn over the weighted features Acrr (instead of learning over J[r](G)= = MAezz which has an additional M). Suppose that the label is given by linear function on C[T) with parameter 8*, i.c,, y y= (8*, <(r)) If A is invertible, the parameter A -13 on Acyr has the same loss as 8 on ciz). So we only need to learn A -B' The sample size needed to learn A -3 on Acty will depend on the factor is potentially smaller than || [|alleryl12 for the unweighted case. This means fewer data samples are needed (equivalently, smaller loss for a fixed amount of samples).
lla, which
Now, consider the case of learning over firy (G) = MAci that has an extra M. We note that cir) can be sparse compared to its high dimension (since likely only very small fraction of all possible walk types will appear in a graph). Well-established results from compressive sensing show that when M has the Restrictod Isometry Property (RIP), learning over MAcrr is comparable to learning over Acgj- Indeed, Theorem 2
10

---

Published in Transactions on Machine Learning Research (08/2022)
shows when W is random and the embedding dimension is large enough, there are families of distributions of W such that M has RIP for Acyr)- Thus, we assumne M has RIP and focus the analysis of how W.. affects the weighting and the learning. In practice, our method is more general and the parameters are learned over the data. Still, the analysis the special case under the assumptions can provide useful insights for understanding our method, particular, how the weighting can affect the learning of predictor over the embeddings.
However, the above intuition is only for learning challenge is to incorporate the learning of W in the analysis, which now address. Formally, learning W from hypothesis class W, and let A(Ww) ) and ftr] (G; Ww) denote the weights and representation given by W For prediction, we consider binary classification with the logistic loss {gg y) = log(1 (1 + exp(-9gv) where g is the prediction and y is the true label. Let (D(0, Ww) be the risk a linear classifier with a parameter on firj Ww) over the data distribution D, and let Es(0, Ww) denote the risk over the training dataset S. Suppose have dataset S (G) v:) of M i.i.d. sampled from D, and ô and W.. the parameters learned via lg-regularization with regularization coefficient Bg:
fixed weighting A induced by fixed W Our key
consider
M
8, W. = arg min W.EW, WWW 1ell
W..) = M Σ & (00 W.)..
1
(29)
To derive error bounds, suppose W is equipped with norm ||- and let N(W. e) be the e-covering number of W w.r.t. the norm || || (other complexity measures W, such as VC-dimension, can also be used). Suppose Jiy (G; Wi) is Ly-Lipschitz w.r.t. the norm let 3* denote the best linear classifier on etr), and let E denote its risk.
on W and the l2 norm on the representation. Furthermore,
Theorem 3. Assume Assumption 1 and Assume cirj is s-sparse, M satisfies (2s, -RP, A(Ww) is invertible and fi (G; Ww) is Ly-Lipschitz over W. For any d, E (0, 1), there regularization coefficient values Bg such that with probability 2 d:
rT (rT+Cc VTT
( min B(Ww) xO x coo C(W) W.EW
1o(0,W.) 26+0
(30)
where
c (W ) + log 1 C.(W):= = log.N (w:
B(Ww) = max | ( GrDD
(31)
8BaL,
Proof. Since 0 = O(W..) where ((Ww)) w) is defined in Lemma 2, by Lemma 2.(1), have
(v rT log. (w,
8BBLs ( ) log ! 1)) +
(0 W.) 5 kss +0
(32)
Furthermore, since 0, W., are the optimal solution for the regularized regression, then for any Ww W,
Ls ls(0, S (s(0(W..,, W.).
(33)
Then by Lemma 2.(2), we have
((((W.).Wa)) $ ((Wa)) + M
log log.N (w. c
)) +
(34)
Combining the above inequalities proves the theorem.
11

---

Published in Transactions on Machine Learning Research (08/2022)
Lemma 2. Suppose frn Ww) is Ly- Lipsschhit w.r.t. the norm || || on W and the &g norm the represenlation. Let
M
((Ww) = arg min SB M
Σ
(10 (w):))))..))
(35)
be the optimal solution for a fized W (1) For any e, E (0,1), with probability least 1 ö, for any W E W,
(KD(0(WW)..al) (ss W.)l so (v ( rT (
(w. ( log
+ log 1 +
(36)
&BoLs
(2) Assume that M satisfies the (2s, 6o) -RIP, and Crr 8-sparse. Also assume that A (W is invertible over W. Then for any e, 8 E (0, 1), there erists an appropriate choice of regularization coefficient Bg, such that with probability at least 6, for any Ww EW,
(B(wa) 6n
)) te. log log.N W, 8
),,,,,,)))
(o(((Ww), Ww)) S 6 o
(37)
M
Proof. (1) We apply net argument W. Let X' be an e/8 of W, |al S N((W, Then for the given M, any W E X and any 0 satisfios:
(D(0, W.) - Es(O, (C so (1/
rT + log (W, ( 8BBL
+log loog
(38)
M
Then for any W E W, there exists a Wi E X' such that |W - -w. s c/8BoT... Then letting denote O(WW), we have
(lD(0, ls(0, W (0, W.)) - (o W..)
(39)
+ (eD(0, Ww) - Ls(0, Ww)) + (s((, Ww) Ls(0, W
(40)
(41)
For any G with label y, we have
le((0, (G))) E(10, fm (C: v))
(42)
< (0.fm/(G:W..) - (0, (m: W!
(43)
KO. (rn(G;
(44)
110 [m WW)l
(45)
I BoL W
(46)
(47)
Then
E rT + log.N (w, 8BBL, KD, - Es(0, (s(0) ww)l < +0 (v
+ log 1
e
+
(48)
M
8
8"
This proves the first statement.
(2) Let X be the set of Acm for G from the data distribution. Since crr is s-sparse, Acm is also s-sparse. Then (Gr - Acpr (G') is 2s-sparse for any G and G', M satisfies (AX, R)-IIP Then thcorem for learning over compressive sensing data. In particular, for a fixed W., we apply Theorem 4.2 in (Arora et al., 2018). (The theorem is included as Theorem in Section A.1 for completeness. Note that choosing an appropriate À in that theorem is equivalent to choosing an appropriate Bg by standard Lagrange multiplier theory.) The statement follows from that the logistic loss function 1-Lipschitz and convex, and that the optimal solution over A(W))om is A A- A''(W.) with the same loss as H* over cpjj. Combining with net argument similar above proves the statement.
apply the
12

---

Published in Transactions on Machine Learning Research (08/2022)
Remark. Theorem 3 shows that the learned model has risk comparable to that of the best linear classifier on the walk statistics, given sufficient data. To see the benefit of weighting schemes, let us now compare to the unweighted case. In the unweighted case, A is the identity matrix, log (W, 8BgL, reduces to O, and ((W,) ) reduces to
Bo = max llm (2) GDD
(49)
Therefore, our method needs extra samples learn Ww: leading to the extra error terms related to log.V (W, (BoL.) On the other hand, the benefit of weighting is replacing the factor Bo above with minw. B(Ww). If there is W v with B(W < Bo, the error is significantly reduced. Therefore, there is a trade-off bet ween the reduction of error for learning classifiers on an appropriate weighted representation and the additional samples needed for learning an appropriate weighting.
The benefit of weighting can be significant in practice. minw.. B(Ww) can be much smaller than Bo, especially when some features (i.e., walk types) in erry are important while others are not, which is true for many real-world applications.
For a concrete example, suppose Cry(G) (G) is s-sparse with each non-zero entry being some constant c. Suppose only a few of the features are useful for the prediction. In particular, f is p-sparse with each non-zero entry being some constant b, and p < s. Suppose there is a weighting W that leads to weight on the entries corresponding to the p important features (i.e., the non-zero entries in 3²), and weight v for the other features where [u] << [T]. Then it can be shown that
Bo sc ppb bo
(50)
min B(W VP(T)) + (s - ()(cc) W
(51)
and thus
minB(WW.. m0
Ww
(1- 2) (
(52)
Bo
Since P < s and |u] <
MT min B(W.)) is much smaller than Bu, so the weighting can significantly reduce We
the error. This demonstrates that with proper weighting highlighting important features and suppressing irrelevant features for prediction, the error can be much smaller than the error for without weighting.
5.3 Analysis for the General Setting
Here we analyze the more general case where W. and Wg may not be the identity matrix I and the number of attributes C 22 1. We assume that the activation function is the leaky rectified linear unit:
(z) =
=} for some a E [0, 1).
(53)
This includes the following special cases: (1) the linear activation analyzed above corresponds to = 1; (2) the commonly used rectified lincar unit (RcLU) corresponds to a = 0. We also note that while our analysis is for the leaky rectified linear unit, it can casily be generalized to any piece-wise lincar function.
We will need to generalize the notations. Recall that C is the number of attributes, ky is the number of possible values for the j-th altribute. Let Ke = I kj denote the number of possible altribute value vector. Also, Af E {0, 1)*t is the one hot vector for the j-th attribute on vertex h; denotes the one hot vector for vertex i, which is the concatenation [h].... [ {0, 1)K The ê-th column of the embedding parameter matrix Wi E xg is an embedding vector for the E-th value of the j-th attribute, and the parameter matrix W with K ΣS= ky. Finally, given attribute "..,., I where ui is the value for the j-th attribute, let Let W(u) denote the embedding for u, i.c., (uu) Wh(u) where h(w) = [h(u"), h(u?). ... h(w")] and h(u²) is the onc-hot voctor of u².
W ReEK is the concatenation W = [W'WW"...
vector u = [u², ..,,...,'
We define the walk statisties (/yy for each vertex i and the walk statistics ((a) for the whole graph as follows.
13

---

Published in Transactions on Machine Learning Research (08/2022)
Definition 4 (Walk Statistics for the General Case). A walk type of length is sequence of attribute vectors (01 V2, 12,-.. vn) where each vs is an alfribule veclor of C' altributes. The walk statistics vector ( Rka for vertex i E [m] is the histogram of all walk types of length n beginning from in the graph G, L.c.,, each entry is indezed by a walk type v and the entry value is the number of walks beginning from verler with sequence of altribbue value veclors v in the graph. Furthermore, let c(r((G the concalenation of én, (rr,...,Crr)( (G), and let ((n)(G) Evelm (G) and Crr(G) = -Eiell (nn (G). When G is clear from the context, we write (n)) Cmy C(n),
Cm)) C(T) for short.
So the definition is similar to that for the simplified case, except that now the walk statistics for each vertex is also defined, and walk type considers all C' attributes. When C 1, the C(a) and Ciry here reduces to those defined in the simplified setting. Similarly, the definition of the walk weight is the same as that in the simplified setting, except that it is defined over the generalized walk types.
The Effect of Weighting on Representation. We will first consider the representation power, showing that F((.) =- (ma)s is a linear mapping of inny This is based on the observation that for the leaky ReLU unit, we have (22) = T()) where [(2) = all(z < 0] + + 2 0j. This inspires the following notation.
Definition 5. Given a vector E R,,, define diagonal matric [(u) R''xr' with diagonal entries
[(4]a: = aTlu, < 0] + Mu 2 0].
(54)
Let (W.W)(m) be a matriz with K2 column corresponding to all possible length-n walk types, with the column indexed by walk type v (vI,...,%,) being gi 92 ...... In with 9: ((W,W((;)) W. (wW(r.).
The following theorem then shows that F(n) can be a compressed version of the walk statistic for vertex i, weighted by the weighting parameter matrix We, Wg and also by the attention scores
Theorem 4. Assume Assumption 1. The embedding Fi) [WyFimls is linear mapping of the walk
stotistics (nn) for any E [m]:
F = WWWWW) (n) Am)
(55)
where (n) KG- dimdenensio diagonal matris, whose columns are indered by walk types u and have diagonal entries X()). Therefore,
Ji Σ (MAc(
(56)
where M is block-diagondl matriz with diagonal blocks W, (W,,W)) W,, (,W ...., ..... "..,,,,,,,,) and A is block-diagon diagonal with blocks A(1y, A..)....AAAT))
Proof. The proof is similar to that of Theorem
First, we note that Lemma 1 still applies the general case, so can be used to prove the theorem statement. Recall that he is the one-hot vector for the attributes vertex k. Let ep {0, K2 be the one-hot vector for the walk type of walk p. By the definition of Fi,, and by Lemma 1,
Fi, = [Wpl
(57)
(y(F(m)ls
(58)
W Σ A(wp) PEP...
O (Fa)) kep
(59)
14

---

Published in Transactions on Machine Learning Research (08/2022)
Then by the definition of F(I):
F(n) = Wg Σ {(ep)
O
Do(W Whi))
(60)
PEPi,n
kEP
W Σ 1(ep)
OT(W,WWha) Whwh))
(61)
PEP,,
kEP
W Σ (WoW)inn
(62)
p.P...
WWWWWW) (n)
M(ep)c
(63)
PEPi..
WWWW, (n) (m))
(64)
The second line follows from the property of a and the definition of r. The third line follows from the definitions of (W,W) and ep- The last line follows from the definition of An) and dny
The theorem shows that in the general case, before applying the last activation, the embedding Fe (n) is a linear mapping of the walk statistics Lny, with a more complicated mapping W W,W,, A(n]- On the other hand, the final graph embedding f(rj is no longer a linear mapping of the walk statistics in general, but is a sum of the nonlincar transformation of the lincar embedding Fi., 's.'s. Only when a is the identity function, fJr: = (MMA())) = E MAcm = EM cr MA becomes linear mapping, and recovers the result in the simplified sctting. Finally, similarly as before, with properly set W W., W, the linear mapping M can satisfy RIP. We will assume this in the following analysis.
The Effect of Weighting on Learning. Now we are ready to analyze the learning performance. Suppose we learn classifier h on top of SIz together with the parameters W, W., Ww, W3 in the model.
Formally, let Wall == (W, W., Ww, Wg). We consider learning Wal from a hypothesis class W, and learning the classifier h from a classifier hypothesis class H = {ho] with a parameter A. Let A(Wau) and for (G: Wau) denote the weights and representation given by Wan- For prediction, we consider binary classification with the logistic loss E(g. y) = log(1 + exp(-gy)) where g is the prediction and y is the true label. Let (0, W..) be the risk of a classifier with parameter 0 on frr](G; Wan) over the data distribution D, and let (0(0, Wal)) denote the risk over the training dataset S. Recall that En denote the risk of the best linear classifier on C[T]. Suppose we have a dataset. $ = W of M i.i.d. sampled from D, and 0, Wan are the parameters learned via (gregularizztion:
1 M M 1=1
8, Wall
arg min WanEW.heEH
(0, Wau) = Σ E (ho (Gm Wau)) v.).
(65)
A technical challenge is that for is no longer linear mapping, so cannot directly apply the guarantees about regression on RIP linear mappings. To address this challenge, we compare the power of our nonlinear learning to the linear learning. Formally, let (G; Wal) be the linear mapping induced by Wan:
din (an) = MAc
(66)
and let Glln and Wiln be the parameters learned via ezrrguularization with regularization coefficient Bg:
1 M
Olin Whin
arg min
(0, Wan) M
Σ
el ( (in Wau)).
(67)
W.
1=1
15

---

Published in Transactions on Machine Learning Research (08/2022)
We introduce the following notation to measure the power of the classifier from H. on firy compared to that of linear classifier on the linear mapping {
H, Bb) == min WoREW
Es(0, Wan)
min W.n.
pii (0, W Wan).
(68)
Theorem 5. Assume Assumplion 1. Assume eyr is s-sparse, M salisfies (2s, en)- RIP, A(Wan) is invertible and frn(G;; Wal) is Lipischhttz over W. For any d, e (0, 1), there are regularization coefficient values BB such that with probability 2 5:
PT (WV)
min B(Wal) x (Neot w.eW
C.(W) M
(o Wan) S S 2
+ 8s(,, H, Bo) (69)
M
where
8BoL, + log 1 ((Wan) max (
C.(W) = N W.
(70)
8
(71)
Proof. The proof is similar to that the simplified selting. First, following the same proof for Lemma 2.(1) with Ww replaced by Wall, we have
(o( Wan) < Wan) + (v M rT + log.V (w.
8BoL, )
e ) + log 1)) +
(72)
Furthermore, since 0, Wall are the optimal solution for the regression on for and @lin, Wihn are that for the regression on f we have
(s Wan) cism (0tn Wiin) +
(73)
and for any Wall E W,
(i ( Will s ei (0th (Wau), Wal).
(74)
Finally, following the same proof for Lemma 2.( with Ww replaced by Walls we have
(W Wan) S +
[(Waalye
M log + log.N (w, (eee((.sssss (
+
(75)
Combining the above inequalities proves the theorem.
The theorem shows a similar conclusion as that in the simplified setting. In particular, when a is the identity function and is the class of linear classifiers with norms bounded by Bg, we have 5(W, H, Bo) = 0, and thus the bound here reduces to the bound in the simplified setting. In the general case, when we choose powerful enough classifier class H. and the nonlinear embedding f(r] preserves enough information, then there exists 0, Wan that achieves better predictions than the linear counterparts 0lin Wiin This leads to small (or even negative) 5(W, H. Bo), and thus the theorem for the general case gives a similar or better bound than that in the simplified case.
6 Experiments
6.1 Experimental Setup
Datasets. We perform experiments on graph-level prediction tasks from two domains: molecular property prediction (61 tasks from 11 benchmarks) and social networks (4 benchmarks). 3 Specifically, consider 37
16

---

Published in Transactions on Machine Learning Research (08/2022)
Table Details on the benchmark datasets used our experiments
Dataset
# of Tasks
Type
Domain
IMDB BIBBBBIIARR (Yanardag & Vishwanathan, 2015)
Classification
Social Network
IMDB-MULTI (Yanardag Vislwanathan, 2015)
Classification
Social Network
REDDIT REDDIT-BINARY BINARY (Yanardag Vishwanathan, 2015)
Classification
Social Network
COLLAB (Yonardag & Vishwanathen, 2015)
Classification
Social Network
MUTAGENICITY (Kazius et al., 2005)
Classification
Chemistry
Tox21 (Tox21 Data Challenge, 2014)
12
Classification
Chemistry
CLINTOX (Artemov et al., 2016; Gayvert et al,, 2016)
Classification
Chemistry
HIV (AIDS Antiviral Streen Data, 2017)
Classification
Chemistry
MUV (Rohrer & Baumann, 2009)
Classification
Chemistry
DELANEY (Delaney, 2004)
Regression
Chemistry
MALARIA (Gamo al., 2010)
Regression
Chemistry
CEP (Hachmann et al., 2011)
Regression
Chemistry
QM7 (Blum & Reymond, 2009)
Regression
Chemistry
QM8 (Ramakrishnan et al., 2015)
Regression
Chemistry
QM9 (Ruddigkeit et al., 2012)
12
Regression
Chemistry
classification (33 molccular + social networks) and 28 regression (on molecular) tasks in total. Table provides details about the datasets used in our experiments.
Baseline methods. We consider WL kernels (Shervashidze et al., 2011), Morgan fingerprints (Morgan, 1965), and N-Gram Graph (Liu et al., 2019a) baselines for graph representation learning. For the predictor top of the representations, we use SVM for WL kernels, and Random Forest and XGBoost (Chen & Guestrin, 2016) for Morgan fingerprints and N-Gram Graph. We also consider several recent end-to-end trainable GNNs that are commonly used, including GCNN (Duvenaud et al., 2015), GAT (Veličković et al., 2017), GIN (Xu et al., 2019), Attentive FP (Xiong et al., 2019), and PNA (Corso et al., 2020). Note that we do not consider recent GNN models that use extra edge/3D information or self-supervised pre-training as baselines in order to avoid unfair comparison AWARE since our analysis throughout this paper focuses on the standard setting (sce Section 3). Attentive FP and PNA were rum without using extra edge information this is not their main contribution.
Evaluation. We perform single-task learning for each task in each dataset. Each dataset is randomly split into training, validation, and lest sets with a ratio of 8:1:1, respectively. We report the average performance across 5 runs (datasets are split independently for each run). We select optimal hyperparameters using grid search. We present the full hyperparameter details as well as an ablation study on their effects below. For the molecular property prediction tasks, we use evaluation metrics from the benchmark paper (Wu al., 2018), except for the MUV dataset for which Rong et al., 2020). For the social network tasks, we follow the evaluation metrics from (Xu et al., 2019).
ROC-AUC following recent studies (Hu et al., 2019;
Hyperparameter Tuning. For AWARE, we carefully perform a hyperparameter sweeping on the different candidate values listed in Table
Table 2: Hyperparameter sweeping for AWARE
Hyperparametors
Candidate values
Learning rate
1e-3, le-4
of linear layers in the predictor: L
2,
Maximum walk length:
3, 6, 9, 12 100, 300, 500
Vertex embedding dimension: Random dimension: y' Optimizer
100, 300, 500
Adam
3Qur code be accessed https:// nttps://githbb gighgtt....... httpe////gtttbccccc///eettttttte htt..//nchneeetfdmiiree//osooeee
17

---

Published in Transactions on Machine Learning Research (08/2022)
Table 3: Overall performance on all 15 datasets (65 tasks). We report (# tasks with top-1 performance, # tasks with top-3 performance). Models with no top-3 performance on a dataset are left blank. Models that are too slow, not well tuned, or not run due to model/dataset /ataseet incompatibility are marked with "_*, For full rosults with error bounds, see Tables 4, and 6.
Dataset
Tasks
Metrie
Morgon FP WL Kernel
GCNN
GAT
GIN
Attentive FP
PNA
N-Gram Craph
AWARE
IMDE BINARY
(0.1)
[0.1]
(1.1)
INDE-MULTI
ACC
(0.1)
[0.1]
01
REDDIT BINARY
ACC
[0.1]
[0.1]
(1.1)
COLLAB
ACC
(0,1)
[0. 1]
(1.3)
MUTAGENICITY
ACC
(1.1)
[0.
(0,
Tox21
(0.4)
(0.2)
(0.5)
[1.3]
[4.11)
[7,11)
CLINTOX
2
ROC
(1.1)
[0.1]
(0.1)
(0.1)
(1, 2)
HIV
(1.1)
[0.1)
[0.
MUV
17
ROC
(2.7)
(3.
(0.8)
(0.1)
[0.3)
(1.2)
(1,6)
(1,4)
(9, 16)
DELANEY
1
RMSE
(0.1)
(0, 17
0,
MALAIIA
RASE
(1.1)
[0.
(0, 13
CEP
1
RMSE
[1.1)
(0.1)
(0.1)
QM7
MAR
(0.1)
(1,1)
QM8
12
MAE
(5.66
[1.7)
(0.1)
(0.
11)
QM9
MAE
(3.12)
[4.7)
(1.
(4.66
Tital
65
(4, 13)
(3.
[9) 27:
(1,2)
(6. (2)
(1)
(2, 18)
(6,41)
(33,
For all the molecular bascline methods other than GAT, Attentive FP, and PNA, the hyperparameter search strategy outlined in (Liu al., 2019a) has been adopted. For GAT, we use their reported optimal hyperparameters (Veličković et al., 2017; Yang et al., 2019). For Attentive FP and PNA, we performed a hyperparameter tuming that included their reported optimal hyperparameters. For social network experiments, we perform hyperparameter tuning on PNA and Attentive FP, and use the optimal hyperparameters reported for the other baseline methods. In addition, for some of the social network datasets, we remove graphs with vertices more than a certain threshold (REDDIT-BINARY. 200, COLLAB: 100), because they have many vertices with lot of neighbors and do not fit into memory for methods using onc-hot fcature encoding.
Training Details. We train AWARE on classification and 6 regression datasets, each of which consisting of multiple tasks, resulting in a total of 37 classification and 28 regression tasks. Each dataset is split into 5 different sets of training, validation, and test sets (i.e., 5 different random seeds) with respective ratio of 8:1:1. We train the model for 500 epochs and use early stopping on the validation set with patience of 50 epochs. No learning rate scheduler is used.
GPU Specifications. In general, an NVIDIA GeForce GTX 1080 (8GB) GPU model was used in the training process to obtain the main experimental results, For some of the bigger datasets, we used an NVIDIA A100 (40 GB) GPU model.
6.2 Results
Prediction Performance. For a quick overview, we present the relative performance of AWARE compared to the baseline methods in Table 3. We observe that AWARE achieves the best performance in 33 out of the 65 tasks, while being ranked in the top-3 performing methods for 53 tasks. In particular, AWARE (even with a simple fully-connected predictor) significantly outperforms N-Gram Graph (which uses a powerful RF or XGB predictor) in 44 lasks, and achieves comparable performance in all other tasks. This indicates that AWARE can successfully learn weighting scheme to selectively focus on the graph information that is important for the downstream prediction task.
We also present complete results for all lasks with error bounds in Tables 4, 5, and 6. These allow for more fine- aie-ggraiedd inspection. For example, we observe in Tables 5 and 6 that both N-Gram Graph and AWARE give overall stronger performance compared to other baselines across the Tox21 tasks in Table and QM8 tasks in Table 6. This suggests that the tasks from these two datasets rely hcavily on walk information, which can be well-exploted by approaches using walk-level aggregation. AWARE, being able to highlight. important walk types, can further improve the performance of N-Gram Graph observed in Tables 5 and 6.
The Effect of Hyperparameters. We also analyze the effect of different hyperparameters on the prediction performance. Figure 2 demonstrates the effect of the maximum walk length 7' and the latent dimension r',
18

---

Published in Transactions on Machine Learning Research (08/2022)
Table 4: In this table, we present the performance of 8 models on classification tasks in the domain of social networks (Morgan FP excluded as it works only on molecular graphs). Experiments are run on 5 different random seeds, and the average of the reported for each task along with their standard deviation in the subscript. The top-3 models in each task are highlighted in gray and the best one is highlighted in blue Higher is better.
Task IMDE-BINARY IMDE-MULTT
# of Classes
Metric
WL Kernel
GONN
GAT
GIN
Attentive FP
PNA
N-Gram Graph
AWARE
2 ACC
am
0.568
S47
0.606_a.077
0.716
0.700g0001
0.522 noi
0. 0.0000000
ACC
0.403
0.473_4.001 6.006
a.
0.343.
REDDIT-BINARY 2
ACC
0.89220m0 40
g.000
0.804 are
0.50820.000
0.784 mn
0.949 20004
COLLAB
ACC
0.880
0.616_..000
0 0.609
0.65
0.675
0.376
0.739 a..
Table 5: In this table, we present the performance of 9 models on 33 classification tasks from the domain of molecular property prediction. Experiments are run on 5 different random seeds, and the average of the 5 run results is reported for each task along with their standard deviation in the subscript. The top-3 models in each task are highlighted in gray and the best one is highlighted in blue (breaking ties by checking more digits in the average result). We mark incompatible task/ model pairs with a Higher is better.
Datawe//Tad
Matric
Morgan
WL. Kernel
GONN
GAT
GIN
Attentive
PNA
N-Gram Graph
AWARE
MUTAOENICITY
ACC
0.684gamss
0. 0.758
0.601 g0.0 som1
0.747aaa
a.637
0.753gams
0.506gam
0.757
T TON21 masker
NR-AR
ROC
0.703
g.701
0.70223.05
0.764
0.769
8.788gures
0.786
0.770gurss
0.786
NR-AR-LBD
ROC
0.88
0.861_aass
0.544
0.800ga
0,800
0.87H
0.865
NR ABR
ROC
0,800_amia
0.676a0m1
0.830
0.820
0
0:901:0 013
0.807
0 4.800
NR-AROMATASE
ROC
a.82
0.828
0.7Maa
0,760aca13
0.846aamus
a.857
0.852.0.011
0.86 10.03
NR-ER
ROC
0.726
0,704
0.737=22
0.706
0.747gumm
0.758:00000
0.76420.022
0. 7.766
NR-ER-LBD
ROC
0,88 2m1
0.764gamm
0. 0.8524..0m omo
SPAR GAMMA
ROC
0.8455
0.810
0.758
0.780gaaas
0.868
0,847 0.807220005
0.862
SD-ARE
ROC
1.820 mis
a.800
0.735
0.794aca3
a..09
0.821
0.851
SR-ATADS
ROC
0,50
0.81420
0.81
0.827a30012
0.754
0.800
0.807 2000T
0.521 20.0ss
0.853
0.84 22n.2s
SR-HSE
ROC
0.774
0.066gaus
0.740
a
0.778-a0er
0.8088 20
0.820.ju.am
SR MMP
ROC
0.890
0.87
0
0.84
0.890 mis
0.506 2.505
0.966 10.1
SR P53
ROC
0,842
0.818
0.739,ax0:
0.177
0.863.
0,860
0.852
CLINTON TOX Boaks
CT TOX
ROC
0.81320
0.850
0.500
0.828
0.83320003
0.805gamm
0.905
FDA APPROVED
ROC
0.795 064
2.802
0.506
0,800.0003
0.883
0.870
0.879an100
0.8024004
0.800
IIV
ROC
0.856-o.n
0.811
0.813
0.780
0.829
0.796
0.8222n.0us
0.825
MUV RoSeS
MUV-166
ROC
00142
10.08
0.749ac.ase
0.008
0.574
0.713
0.726
0.850
MUV-548
ROC
0.953
2.917
0.900
0.764
0.750 0.700
0.92520001
0.976:20014
MUV-600
ROC
0.52li me
0.G3lign to0
0.437 0.570
0.576
0.508 1os
0.68014 111
0X670 me
11687
644
ROC
0,893 ma
0.9444_n
0.70220 10:
0.749g0a04
0.776 158
0.913
0,799
MUV-652
ROC
0.725
0.655 Lan
0 0.400
0.645a277
0.505
0.659.0.224
0.088
0.810
MUV-689
ROC
0.676 277
0.671 06.71 20.257
0.368
0.775
0.4522n:220
0.606
MUV-602
ROC
0 0.698 109
2.4
0.226
0.D8)
0.618
0.606
0.63020:194
MUV-7712
ROC
0.22 en re
0.3085g ros
0.700ga wo
0.77d
0.940.. eao
0.882gn 116
0.122 wa
0.931 rae
MUV 713
ROC
0.55
0.787
0.731
0.566
0.567
0.520
0.648
0.715
0.781.
MUV-733
ROC
0.700_..01
2.707.0.10
0.751
2.677
0.558 acusss
0.664
0.63220:16
0.600
0.819
MUV-737
ROC
0.791 20
2.773
0.706
0.670
0.723
0.794ances
0.80
0.879
0.917
MUV-810
ROC
0.718 111
0.8
1.7
0.288 res
0.782 188.
MUV 832
ROC
0.966 m.1
0.920
0.9231anna
0918
0.714
a.900
0.909
a.973
MUV-846
ROC
0.877
0,88410000
0.
0 0.800
0 0.78aaai
0.857 an.c4
0.000
0,781
MUV-852
RCC
0.867g0.10
0.748 0.882an0e0
7.55
0.850ancee
0.834
0.917a000
MUV-858
ROC
0.701
0.6772n
0.600l
0.740
0. 4.700.0 110
0.630l
0.657
MUV-839
ROC
0,530g0 oe
0.5
0.613
0.409ga.0s
6.08110.0s
0.724.0 145
0.853 186
and Figure3 3 shows the impact of the number of layers L in the final predictor and the vertex embedding dimension r. In general, the performance is quite stable across different hyperparameter values. This indicates that our algorithm is friendly towards hyperparameter tuning.
6.3 Ablation Studies
In this section, we perform three different ablation studics to further explore our method. First, we perform a study to examine the impact of each weighting component W., W., and W3 in AWARE. We individually remove one component from the model and compare its performance to the full model. We also compare our full model to the version with lincar o, i.c., (2) = 2. Table 7 shows that the weighting components mostly lead to better performance even though there are cases in which they may not. We see that all three weighting components contribute to improved performance for most tasks. Notably, there exist tasks for
19

---

Published in Transactions on Machine Learning Research (08/2022)
Table 6: In this table, we present the performance of 9 models on 28 regression tasks from the domain of molecular property prediction. Experiments are run on different random seeds, and the average of the 5 run results are reported for each task along with their standard deviation in the subscript. The top-3 models in each task are highlighted in gray and the best one is highlighted in blue (breaking ties by chocking more digits in the average result). Models that are too slow are left. blank. Lower is better.
Dataset/ Tass
Metric
Morgan FP
WL Kerael
GCNN
GAT
GIN
Atsentive PP
PNA
N-Gram Graph
AWARE
DRLANEY
RMSE
1.061 sourrs
1.160
0.702amcss
0. 0.054aa.15:
0.810
0.022
O 0.58610.042
MAlABIA
RMSE
1.102
1.136ge
1.080
10000
1.156
CEP
RMSE
oz
1,457 io
1.3
108
1.158gnee
1.002
1.233 am
QUI
MAE
118 2
173
70.000
2:
82 88.81
74 717llla
108. p0..9
29 097
E1-C02
MAR
0,003 2011
0.007 suttnn
0.012
4.012
8.008
0.007 en0
0.007.00000
E2-0C2
MAE
0,001
0.024_1100
0.007
0.013g0
0.100..
0.0018
0.010
0.001
0.020
4.014
2.0
0.015
0.015
0.01339.00
F2-CC2
MAE
0 g.
0.060=2:00
0. 0.058
0.051 2n.
0.009
0.052ge ne:
0.000ga
0500
EL PBEO
MAE
g.00
0.004_33000
0
0.015
DLOUT
0.01220
0.00S_
0.0017
1,0077
E2- PBEO
MAE
a.00
a.009
0 007 cme
0.012
0.008 w0.000
0.01220.oo
0.009
0.007 c0.
0.008, 10.c0
P1-PRP0
MAF
0.
0.05721:011
0.01220
0.016
0:01
0.017an
0.013
0. 0.01220
0.01
12-PBE0
MAE
0.078-33.000
a.024
2.081
0.0244...co
0.022.0.000
EI-CAM
MAE
0.009
0:003
0 10.0010.001
0.012ua.003
0.007
0.01220000
0.007
0.0 2.006
0. 0.006...coo
E2-CAM
MAE
0.000
0.026:2..01
0.01 20:00:
20.00
0.0182uma
0.009
a.007
F1-CAM
MAE
0.005
0,072 03.72
2.0122
0.017
0.013
0.013
0.012 001
F2 CAM
MAE
00000
0.080
a.027
0.0344
0,005
0.026
0:024.0
QMO tacks
MU
MAE
0.825
0.500fgg
0.654
0:476
0,062
B. B.575gm
0.505
ALPHA
MAE
3.318
0.503:0..es
1.153
1076
8.
0,505
0.774.c..03
RONSO
MAE
0.007
0.004g
0.008
0.009
0. 0.007 20vors
0. g.005
0.00 0.006
LUMO
MAF
0.000
O 0.00
0.009
3.004.g
0.009
0. 0.008_ga-te
0.00520
0.0 0.006
GAP
MAE
0.010.33.00
4.00
a.005 oco
0.012.0.cm
0.010
24.000
R2
MAE
07. 767
30. 788
100.900
36 555
80.2 23.265aa
97. 405 nor
56.7762934
63. $5,000 20
MAE
0.008-2.000
0LE01
0.008_...a.
CV
MAE
1.422
O 0.229 10.014
a.542
a.208
0.521
1. 1.3188.0.20
0.3844
0.5o66...044
00
MAP
14:857
0.906
1.898
2. 2.253 567
2.715
22. 3.0933
0.427
0.090,0u
1298
MAE
1.12
6.130u5.477
2.0022.0.455
2.883 ura
21. u1.965
0.086, aoe
K298
MAE
14.600.a.14
0. 0,785
2.066
2.308
2.90022100
20.590
0.429
0. 0.098..
6208
MAE
11.651g9199
0.6 0.6466gur
2.576
2.200
4.014.1
19.794gx.0
2.427
0.086
Table 7: Ablation study I: Change in performance on removing/modiffing components of AWARE. "+' indicate relatively cotter/worse performance respectively.
Dataset
Task
No W.
No We
No Wg
No W., Ww W,
Linear
IMDB-BINARY
IMDE-BINARY
5.03%
+ +1.12%
1.96%
-7.54%
10.06%
Tox21
NR-AR
1.32%
0.76%
I 0.67%
0.37%
1.12%
CLiNTx
CT CT_TOX
TOX
-9.00%
-2.09%
+0.70%
-3.07%
-10.35%
CLNNTX
FDA APPROVED
-7.83%
-2.99%
+1.38%
-4.16%
-10.40%
M
MUV-466
20.08%
-16.70%
-7.4%%
+1.80%
-18,73%
DELANEY
DELANEY
228.45%
-0.18%
-4.69%
57.800%
-6..17%
MALARIA
MALARIA
0..83
+2.10%
-1.5%
-2.32%
-5.66%
QM7
QM7
-1.59%
+3.74%
-18.45%
-71.3%%
-85.21%
Table 8: Ablation study 1l: Change in AWARE's performance when the vertex embedding matrix W is randomly initialized and non-trainable, with linear a. Underline indicates better performance.
Dataset
Task
Metric
Trainable
Fixed Random W
MMDB-BINARY
IMDB-BINARY
ACC
0.716
0.660
Tox21
NR-AR
ROC-AUC
0.776
0.774
CLINTOX
CT TOX
ROC-AUC
0.889
0.764
CLINTOX
FDA APPROVED
ROC-AUC
0.869
0.774
DELANRY MALARIA
DELANEY
RMSE
0.612
1.162
MALARIA
RMSE
1.062
1.126
QM7
QM7
MAE
41.280
96.675
which specific weights lead to drop in performance. Aligning with Theorems 1 and in Section 5, this
20

---

Published in Transactions on Machine Learning Research (08/2022)
1=100
<= 300
~' 500
NR-AR
NR-AR-LBD
NR-ARR
1.0
1.0
ROC-AUC
0.9
0.9
0.9
0.8
0.8
0.8
0.7
NR-Aromatase
NR-ER
NR-ER-LBD
1.0
ROC-AVC
0.9
0.9
0.9
0.8
0.8
0.8
0.7
12
3
12
6
NR- gaa-PaaR
SR-ARE
SR-ATADS
1.0
ROC-AUC
0.9
0.9
0.9
0.0
0.8
0.8
0.7
0.7
0.7
6
12
3
9
12
SR-HSE
SR-MMP
SR-p53
1.0
ROC-AUC
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
6
12
3
9
12
12
T
Figure 2: Effect of T and r' on the prediction performance on the 12 lasks the Tox21 dataset. For each pair of T and r' hyperparameter values, the model was run on different seeds of data and the average of the 5 runs is reported. Higher is better.
100
r= 300
500
CT_ TO_
FDA APPROVED
1.0
1.0
ROC-AUC
0.9
0.9
0.8
0.8
0.7
0.7
2
3
Figure 3: Effect of the number of linear layers L in the fully connected neural network for graph-level prediction and the vertex embedding dimension r on the prediction performance on the tasks in the CLiNTOX dataset. For cach pair of L and hyperparameter values, the model was 5 different seeds of data and the average of the runs is reported. Higher is better.
21

---

Published in Transactions on Machine Learning Research (08/2022)
Table 9: Ablation study I1I: Change in AWARE's performance when the final predictor is changed from a multiple layer NN a lincar predictor. Underline indicates better performance.
Dataset
Task
Metric
Multiple layers
Linear predictor
BIDD-
IMDB-BINARY
ACC
0.716
0.678
Tox21
NR-AR
ROC-AUC
0.776
0.759
CLINTOX
CT TOX
ROC-AUC
0.889
0.880
CLINTOX
FDA APPROVED
ROC-AUC
0.869
0.870
DELANEY
DELANEY
RMSE
0.612
0.640
MALARIA
MALARIA
RMSE
1.062
1.070
QM7
QM7
MAE
41,280
415.155
indicates that weighting schemes are successful in learning important artifacts for the downstream task only under specific conditions. Furthermore, we can also observe the advantage of using a non-linear activation function over a linear one.
Second, we analyze the change in performance when non-trainable vertex embedding matrix W and linear are used. Table 8 demonstrates using a trainable random vertex embedding matrix W and a non-lincar a gives overall better performance. It also shows that even with random W and a linear our method can still get decent performance praviiidinn justification for the simplification assumptions in our theoretical analysis.
Third, we examine the advantage of using a fully-connected neural network with multiple linear layers as a predictor over using a simple linear predictor. Table 9 suggests that using multiple layers in the final predictor leads to better performance in general.
7 Interpretation and Visualization
AWARE uses an attention mechanism at the walk level ) to aggregate crucial information from the neighbors of each vertex (Section 4). While we have demonstrated the empirical effectiveness of this in Section 6, we now focus on validating our analysis that AWARE can highlight important substructures of the input graph for the prediction task.
For this analysis, we use the MUTAGENICITY dataset (Kazius et al., 2005), which comes with the ground-truth information that molecules that contain specific chemical groups (-NO2,NNHz) are much more likely to be assigned a 'mutagen' label (Debnath et al., 1991). This datasel has been introduced for the purpose of increasing accuracy and reliability in mutagenicity predictions for molecular compounds. Mutagenicity of a molccular compound, among many other attributes, is known to impede its ability to become a usable drug. A mutagen is a physical or chemical factor that has the potential to alter the DNA of an organism, which in turn increases the possibility of mutations. The dataset contains 4337 molecular structures with 2401 labeled as "mutagen". Molecular structures in this dataset contain around 30 atoms on average.
To find substructures that AWARE uses for its prediction, compute the importance score for each bond (edge) of the molecule by using the attention scores computed via Equation (7) (Specifically for an edge i-j, we use (Sey) + (S(y)):) Accordingly, we visualize two randomly chosen 'mutagenic' molecules in Figure 4 and the important substructures as attributed by different interpretation techniques. Figures 4b and 4c depict the interpretation of the GIN model (Xu et al., 2019) using Grad and GNNExplainer techniques (Ying et al., 2019). The former computes gradients with respect to the adjacency matrix and vertex features, while the latter extracts substructures with the closest property prediction to the complete graph. In the first molecule, although both of these techniques are able to highlight the two NH₃ groups important for the final prediction, they fail to highlight the NO, group. In the second molecule, while Grad fails to identify the NO₃ atom group, GNNExplainer marks majority of the bonds (edges) in the molecule as important, which should not be the case.
In contrast, AWARE can successfully highlight both the NH, and NO, groups as important in the first molecule as well as the NO, group in the second one, as can be seen in Figure 4d. This provides further evidence that AWARE is able to identify substructures in the graph that significant (or insignificant) for
22

---

Published in Transactions on Machine Learning Research (08/2022)
(a) Molecule
(b) Grad
(c) GNNExplainer
(d) AWARE
(e) edge importance
Figure 4: Visualization of two random mutagen molecules from MUTAGENICITY and their important substructures for accurate prediction captured by different interpretation techniques. Different node colors indicate different atom types. (a) depicts the original molecules with important mutagenic atom groups circled in red, such as NO₂ and NH2. (b), (c), and (d) demonstrate important substructures detected by different methods. (e) is heatmap for the edge importance scores computed by AWARE.
Art Pory
1.00
0.75
0.25
0.00
0.2
0.4
Figure 5: Interpretation of graph-level attention W for the NR-AR classification task.
given downstream prediction task (In the examples given in Figure 4, we set a threshold (21.0) the importance scores computed by AWARE to highlight important substructures in the molecules).
Interpretation for Wg. AWARE uses Wg to selectively weight the embeddings at the graph level for the prediction task (Section 4). Towards interpreting W,, we want to analyze how well aligns with the predictor for the downstream task. Specifically, we train AWARE for the binary classification NR-AR task (Tox21 dataset) using linear predictor with parameter (without non-linear activation function). We randomly sample 200 data points, and compute their graph embeddings (Gr(G) from AWARE. We denote the top three left singular vectors of W by [u1, N2, uz). For particular ue, we define [u;, ui.... (T times) to bring to the same-dimensional space as fiz (G). Finally, we plot {"1, 02 UsJ, and the embeddings fiy for all 200 samples in Figure 5 using PCA with = components.
We observe that W 's largest singular vector diroction aligns very well with the parameter w of the downstream predictor that the model has learned. This suggests that this weight can successfully emphasize the directions in the graph embedding space that are important for the prediction.
23

---

Published in Transactions on Machine Learning Research (08/2022)
8 Conclusion
In this work, we present and analyze a novel altentive walk-aggregating GNN, AWARE, providing the first provable guarantees on the learning performance of weighted GNNs by identifying the specific conditions under which weighting can improve the learning performance in the standard setting. Our experiments on 65 graph-level prodiction tasks from the domains of molecular property prediction and social networks demonstrate that AWARE overall outperforms Iraditional and recent. baselines in the standard setting where only adjacency and vertex attribute information are used. Our interpretability study lends support to our algorithm design and theoretical insights by providing concrete evidence that the attention mechanism works in favor of emphasizing the important walks in the graph while diminishing the others. Lastly, our ablation studies show the importance of the different components and design choices of our model. Supported with the strong representation power by AWARE, we believe that it can be further explored for wide range of lasks, including but not limiled to multi-task learning (e.g., Liu et al. (2019b; 2022b)), self-supervised pretraining (e.g., Liu et al. (2022a;c)), few-shot learning (e.g., Altae- Altae-Tran& et al. (2017)). etc.
We would also like to briefly touch on the ethical impacts and weaknesses of our method here. Though AWARE can be used for graph-structured data from distinct data domains, we will be highlighting the ethical implications of our method for the important domain of molecular property prediction. Having strong empirical performance for the molecular property prediction domain, AWARE can potentially be used for ellicient drug development process. Physical experiments for this task can be expensive and slow, which can be alleviated by using AWARE for an initial virtual screening (selecting high-confident candidates from large pool before physical screening). A strong empirically performing model like AWARE can help speed up the process, and provide tremendous cost savings for this important task. However, deploying an automatic ML prediction model for such a highly critical task must be done extremely carefully. As evidenced by Section 6, AWARE does not achieve the best performance for all molecular property prediction tasks. Thus, AWARE may fail to identify promising chemicals for drug development, and/or make erroneous selections. While the former may increase the time and cost of the process, the latter might lead to failures in developing the drug. Nevertheless, with sufficient physical experimentation performed by human experts, such unwanted events can be minimized while still enjoying the benefits of using AWARE.
9 Acknowledgement
The work is partially supported by Air Force Grant FA9550-18-1-0166, the National Science Foundation (NSF) Grants 2008559-IIS, CCF-2046710, and 2023239-DMS.
References
AIDS Antiviral Screen Data. Aids antiviral screen data. attps://wike http:/wwiiiwiiiiii.....i....ct.t .nh. /tt.g///dsssplly//iiittaaa///// 2017. Accessed: 2020-12-20. 17, 32
ALDS+hntiviraa++Screnni
Han Altae-Tran, Bharath Ramsundar, Aneesh S Pappu, and Vijay Pande. Low data drug discovery with one-shot learning. ACS Central Science, 3(4):283 293, 2017. 24
Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, and Kiran Vodrahalli. A compressed sensing view of unsu- pervised text emboddings, bag-of-n-grams, and lstm. International Conference on Learning Representations, 2018. 12, 30
Artem V Artemov, Evgeny Putin, Quentin Vanhaelen, Alexander Aliper, Ivan V Ozerov, and Alex Zhavoronkov. Integrated deep learned transcriptomic and structure-based predictor of clinical trials outcomes. bioRwie, pp. 095653, 2016. 17
Waiss Azizian and mare lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https: htttps://pperrviiie net/forrmmid 1xHgXXYi4bwl. 3
24

---

Published in Transactions on Machine Learning Research (08/2022)
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate, 2014. URL http://arxivv http:////axxiv.ooaaa////sss www.:or/////b/////// 1409. 0473. cite 10xiv11409.04775Commen. Accepted at ICLR 2015 as oral presentation. 2
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 2016. 3
Lorenz C Blum and Jean-Louis Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database gdb-13. Journal of the American Chemical Society, 131(25):8732 8733, 2009. 17, 32
Robert Calderbank, Sina Jafarpour, and Robert Schapire. Compressed learning: Universal sparse dimension- ality reduction and learning in the measurement. domain. Techical Report, 2009. 30
Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing. Comples rendus mathematique, 846(9-10):558) 592, 2008. 29
Emmanuel Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, (111):4403342215, 2005. 29
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledgge Discovery and Dala Mining, pp. 2016. 17
ACM,
Benjamin Coors, Alexandru Paul Condurache, and Andreas Geiger. Spherenet: Learning spherical representa- tions for detection and classification in omnidirectional images. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 518 503, 2018.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Newral Information Processing Systems, 33, 2020. 17
Asim Kumar Debnath, Rosa L, Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity, Journal of medicinal chemistry, 34(2):786-777 1991.
22
Nima Dehmamy, Albert-Taszlo Barabasi, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. Advances in Neurol Information Processing Systems 32 (NIPS
2019), 2019. 2,
John S. Delaney. ESOL: Estimating Aqueous Solubility Directly from Molecular Structure. Journal of Chemical Information and Computer Sciences, 44(3):1000-14 1005, May 2004. ISSN 0095-2338. doi: c0.1022/ci034444xx 17, 32
Yuntian Deng, Yoon Kim, Justin Chiu, Demi Guo, and Alexander M. Rush. Latent alignment and variational altention. In Proceedings of the 32nd International Conference on Newral Information Prucessing Systems, NIPS'18, pp. 9735-9747, 9747, Red Hook, NY, USA, 2018. Curran Associates Inc 2
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova, BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapler of the Association for Compulalional Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: (0.18653/vll 11t//////1111191111 1423. URL https: http:://wwwwwawwwwee aclweb. org awgg//nthooogyy//o/ooog (Ntpeeloggyyyy111111 NN1 1423. 2, 3
Alexcy Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image worth 16x16 words: Transformers for image recognition al scale. Xiv preprint ar arxiv:2010. 1929, 2020. 2, 3
25

---

Published in Transactions on Machine Learning Research (08/2022)
David K Duvenaud, Dongal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224 2232, 2015. 1, 3, 17
Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sensing. Bull. Am. Math, 54:151 165, 2017. 29
Francisco-Javier Gamo, Laura M. Sanz, Jaume Vidal, Cristina de Cozar, Emilio Alvarez, Jose- Lavandera, Dana E. Vanderwall, Darren V. S. Green, Vinod Kumar, Samiul Hasan, James R. Brown, Catherine E. Peishoff, Lon R. Cardon, and Jose F. Garcia Bustos. Thousands of chemical starting points for antimalarial lead identification. Nature, 465(7296):305-311 310, May 2010. ISSN 1476-4687. doi: 10.1038/non 10088/atuue00917.. 17, 32
Kaitlyn M Gayvert, Neel S Madhukar, and Olivier Elemento. A data-driven approach to predicting successes and failures of clinical trials. Cell chemical biology, 23(1)):1294 1301, 2016. 17, 32
Justin Gilmer, Samuel $ Schocnholz, Patrick F Riley Oriol Vinyals, and Gcorge Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.0122) 2017. 2,
Johannes Hachmann, Roberto Oliyar Sule Atahan-Evrenk, Carlos Amador-Bodolla, Roel S. Sánchez- Carrera, Aryeh Gold-Parker, Leslie Vogt, Anna M. Brockway, and Alán Aspuru-Guzik. The Harvard Clean Energy Project: Large-Scale Computational Screening and Design of Organic Photovoltaics on the World Community Grid. The Journal of Physical Chemistry Letters, 2(17):2241 2251, September 2011. ISSN 1948-7185. doi: 10. 10.1021 10011)2200866s.. 17, 32
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXic:1905. 12265, 2019. 17
Shiva Prasad Kasiviswanathan han and Mark Rudelson. Restricted isometry property under high correlations. arXiv preprint 1rXii:1904.088 05510, 2019. 30
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312- 30,,220,, 2005. 17, 22, 32
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8):595 608, 2016. 3
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint XrXi::1609. 029007 2016. 1, 3
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs.
arxiv preprint Xix::20003. 03123, 2020. 3
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks.
arxiv preprint arXiv:1511.05,, 2015. 3
Shengchao Liu, Mehmet F Demirel, and Yingyu Liang, N-gram graph: Simple unsupervised representation for graphs, with applications to molecules. In Advances in Neural Information Processing Systems, pp. 8466- 8478, 2019a. 2, 3, 4, 5, 6, 7, 10, 17, 18, 29
Shengchao Liu, Yingyu Liang, and Anthony Gitter. Loss-balanced task weighting to reduce negative transfer in multi-task learning. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp.
9977-9978, 2019b. 24
Shengchao Liu, Hongyu Guo, and Jian Tang. Molecular geometry pretraining with se (3)-invariant denoising distance matching. arXis preprint ar Xiv::2206. 13602, 2022a. 24
Shengchao Liu, Meng Qu, Zuobai Zhang, Huiyu Cai, and Jian Tang. Structurod multi-task learning for molecular property prediction. In International Conference on Artificial Intelligence and Statistics, pp. 8906 8920. PMLR, 2022b. 24
26

---

Published in Transactions on Machine Learning Research (08/2022)
Shengchao Liu, Hanchen Wang, Weiyang Liu, Joan Lasenby, Hongyu Guo, and Jian Tang. Pre-training molecular graph representation with 3d geometry. In International Conference on Learning Representalions, 2022c. URL
24
Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention-base neural machine translation. arXiv preprint 1rXi::158.00025, 2015. 2
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi- label classification. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1614-1623, New York, New York, USA, 20-22 22 Jun 2016. PMLR. URL http://proceedings mlr.
gress//44/martinns/ html. 3
Tukasz Maziarka, Tomasz Danel, Slawomir Mucha, Krzysztof Rataj, Jacek Tabor, and Stanislaw Jastrzkebski. Molecule attention transformer. arXiv preprint (kki:2002.082000 2020. 2, 3
HL Morgan. The generation of unique machine description for chemical structures-a technique developed at chemical abstracts service. Journal of Chemical Documentation, 5(2):107-113, 1965. 17
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAT Conference on Arlificial Intelligence, volume 33, pp. 1602-4609, 2019. 3
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014. 2, 3,
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL http: / http:///tt..oopprss///s////s/ httm///442./00.......l. 3
Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jonathon Shlens.
Stand-alone self-attention in vision models. arXiv preprint ar ar:iv:1906.00 05999999000999, 2019. 3
Raghunathan Ramakrishnan, Mia Hartmann, Enrico Tapavicza, and O Anatole Von Lilienfeld. Electronic spectra from (ddft and machine learning in chemical space. The Journal of chemical physics, 188411,,1111,, 2015. 17, 32
Sebastian G Rohrer and Knut Baumann. Maximum unbiased validation (muv) data sets for virtual screening based pubchem bioactivity data. Journal of chemical information and modeling, 49(2):169- 184, 2009. 17, 32
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Grover: Self-supervised message passing transformer on large-scale molccular data. arXie preprint 2rX2:2207.02835,
2020. 2, 3, 17
Lars Ruddigkeit, Rund Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumcration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of chemical information and modeling, 52(11):2864 2875, 2012. 17, 32
Mark Rudelson, Roman Vershynin, et al. Sanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013. 32
Shiv Shankar, Siddhant Garg, and Sunita. Sarawagi. Surprisingly easy hard-attention for sequence to sequence learning. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 640 645, Brussels, Belgium, October-November 2018. Association for Computational Linguisties. doi: 1065. URL httpps://wet hwwp///www///w/////o//. aclweb. www.waawwwwwaaaaa..e.........eaa wwwrg//atholooy/Diee.
2
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-ehmman graph kernels. Journal of Machine Learning Research, 12(Sep):2539 226-1,,1,,,, 2011. 2, 3, 17
27

---

Published in Transactions on Machine Learning Research (08/2022)
Tox21 Data Challenge. Tox21 data challenge 2014.
2014. 17, 32
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Newral Information. Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint SSN::11100.1000 2017. 2, 3, 17, 18
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint (rXto:151100330) 2015. 3
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. The Journal of Machine Learning Research, 11:1201-1242, 2010. 2, 3,
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural networks. Zhi-Hua Zhou (ed.), Proceedings of the Thirlieth International Joinl Conference on Artificial Intelligence, IJCAI-21, pp. 3089 3096. International Joint Conferences on Artificial Intelligence Organization, 8 2021. hja/ijjccaaiaaa doi: 10.24963 11/96///jcai.220 (jcaai.2221/42221 URL https://dol oww/10.o////.../ 24963 cai 20212202/422
Main Track. 3
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9
(2):513-530 2018. 17
Zhaoping Xiong, Dingyan Wang, Xiaohong Liu, Feisheng Zhong, Xiaozhe Wan, Xutong Li, Zhaojun Li, Xiaomin Luo, Kaixian Chen, Hualiang Jiang, et al. Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism. Journal of medicinal chemistry, 63() 8760, 2019. 17
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2048-2057, Lille, France, 07-09 Jul 2015.
PMLR. URL http: http:////oceeeenneeemeem mlr. mwr.mmrrreeeseee ptw.peee///////// 11177/xc15..tt. html.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019. URL https / // openrevieeeeeeeeee ryGa61A5Km. 1, 2, 3, 7, 17, 22
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015. 17, 32
Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Muzman--erez, Timothy Hopper, Brian Kelley, Miriam Mathea, et al. Analyzing learned molecular representations for property prediction. Journal of chemical information and modeling, 59(8))3370-3388 -388,, 2019. 3, 18
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombalchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Eamp; Data Mining, pp. 974 983, 2018. 1
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in neural information processing systems, pp. 9244 9255, 2019. 22
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jacwoo Kang, and Hyunwoo Kim. Graph transformer networks. Tn Advances Neural Information Processing Systems, pp. 11983 11993, 2019. 2
Hengshmang Zhao, Jiaya Jia, and Vladlen Koltun. Exploring self-attention for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10076-10088 2020. 3
28

---

Published in Transactions on Machine Learning Research (08/2022)
Appendix
Attentive Walk-Aggregating Graph Neural Networks
A Toolbox for Theoretical Analysis
A.1 Toolbox from Compressive Sensing
For completeness, here we include the review from (Liu et al., 2019a) about related concepts in the field of compressed sensing that are important for our analysis. Please refer to (Foucart & Rauhut, 2017) for more details.
The primary goal of compressed sensing is to recover a high-dimensional k-sparse signal IRN from few linear measurements. Here, being k-sparse means that x has at most zerozero entries, i.., |alo k. In the noiseless case, we have design matrix A RaxN and the measurement vector is Ar. The optimization formulation is then
minimize
||z'lo subject to Ar' =
(76)
where ||o'|lo is to norm of z', i.e., the number of non-zero entries in x'. The assumption that is the sparsest vector satisfying Ax = = is equivalent to that x the optimal solution for (76).
Unfortunately, the fo-minimization in (76) is NP-hard. The typical approach compressed sensing is consider its convex surrogate using & m:mmimmmzattio::
minimize ||a/|] subject to Ax'=
(77)
where ||='|1 E, |a/] is the l norm of x', The fundamental question is when the optimal solution of (76) is equivalent to that of (77), i.e., when exact recovery is guaranteed.
A.1.1 The Restricted Isometry Property
One common condition for recovery is the Restricted Isometry Property (RIP): Definition 6. A E EdxN (X,e)-RII for some subset X' E if for any a e X,
(1 [)=a\\l=|la ||rT|2 (1 + +)]l=112
(78)
We will abuse notation and say (RIP) if is the set of all k-sparse a RRN.
Introduced by (Candes Tao, 2005), RIP has been used to show to guarantee exact recovery.
Theorem (Restatement of Theorem 1.1 in (Candes, 2008)). Suppose A is (2k, R)-RIP for an 6 v2 - 1. Let & denote the solution to (77), and let F denote the vector x with all but the k-largest entries set zero. Then
|| æ111 I Colla æ|11
(79)
and
| æ|12 < Cok 1ok-11211ar, - x|11
(80)
In particular, if is k-sparse, the recovery is exact.
N Furthermore, it has been shown that A is (k, RIP with overwhelming probability when d = Ω(k log +
and vdA. AO j) or vdA, u(-1, j). There are also many others types of A with RIP: see (Foucart & Rauhut, 2017).
29

---

Published in Transactions on Machine Learning Research (08/2022)
A.1.2 Compressed Learning
Given that Ar preserves the information of sparse x when A is RIP, it is then natural to study the performance of a linear classifier learned on Ar compared to that of the best linear classifier on a. Our analysis will use a theorem from (Arora et al., 2018) that generalizes that of (Calderbank et al., 2009).
Let X C RV denote
X x= (= | S k. ||a|2 S B}.
(81)
Let ((,,, y)) be a set of M samples i..d. from some distribution over X' x (-1,1}. Let denote a Xr-Lipschitz convex loss function. Let (0() denote the risk of lincar classifier with weight R i.c,, (0) ((e((0, y)l, and let H* denote a minimizer of (Ø)).. Let ( denote the risk of linear classifier with weight E Id over Ar, i.e, (8(0)) = (,, Ax), w)], and let Ō denote the weight learned with Eg-regularization over {(Ars, H:));
M Σ
0 = arg min
((10, Azt). Mi) + A|101|2
(82)
0 M
where À is the regularization coefficient.
Theorem 7 (Restatement of Theorem 4.2 in (Arora et al., 2018)). Suppose A is c)-IP. Then with probability at least 6,
(S(O,) $00))(l(000) (lx(0) +0 (NABI107Iy
1 M
log )
(83)
for appropriate choice of A. Here, AX = fo - x, x E2} for any X C
A.2 Tools for the Proof of Theorem 2
For the proof, we concern about whether the 4-way column product of W has RIP. Existing results in the literalure do not directly apply in our case. But following the ideas in Theorem 4.3 in (Kasiviswanathhan & Rudelson, 2019), we are able to prove the following theorem for our purpose.
Theorem 8. Let X be an n x d matris, and let R be a d x N random matric with independent entries Raj such that [[,, = O, [[ = 1, and |Rall S t almost surely. Let t 2 be constant. Let E (0, 1), and let & be an integer satisfying sT(X) N Crtcp log k for some universal constant least 1 - exp(pcce x (k2 for some universal constant e >> 0, the matriz X XR(0 [F is (k, -)-I..
0. Then with probability at
Here, sr(X)= = | is the stable rank of X. In our case, we will apply the theorem with X being Laxd/ Vd where Iaxa d is the identity matrix.
Proof of Theorem 8. The proof follows the idea in Theorem 4.3 in (Kasiviswanathan & Rudelson, 2019). However, their analysis is for a different type of matrices (e-way Column Hadamard Product). We thus include a proof for our case for completeness.
Lot u E dd be a vector with sparsity k; and its entries indexed by sequences (11, .2. E [d] Let E [p), and define
yt =
Σ
U (i
II Rey j=1
(84)
(61 (dd
Note that the random variables (e E (p)) are independent. We will now estimate the 4ormorm of ye and then use the Hanson- Wright incquality (and its corollaries) with net argument establish the concentration for the norm of X RLC u Xy where y (V1,-.. (y1.-...up)
30

---

Published in Transactions on Machine Learning Research (08/2022)
Let supp(u) be the support of u. By the triangle inequality,
llvellas
Σ
(a
II
Rei;
(85)
jml
222
E
U(i (1) Rei
(86)
jml
(7'Ilul)))))
(87)
=
(88)
Next, we choose an (1/2C2)-net N in the set of all k-sparse vectors in Odd' such that
W < (d' ( sexp
Aloo (Cod" k
(89)
Note that for any k-sparse vector u E Cd'-1, y R! (yi...., .p)) random vector with independent coordinates such that for any l E [p],
Elyal = 0, E[v²l = 11ul22. and llvello S C CT'V/|llull.
(90)
Then by Corollary 1, for any fixed u E Cill -1 with [supp(u)] S k (and y = R(ll)),
(-mawe livell I sT(X)) s exxp (- (-x
Ce
Ci
Pr Irll ||||||| > [[] s exp
(91)
Together with the union bound over M and using the assumption on sr(X), have
Codd
)) 2 2exp k
(-
(-Crre
Pr Tu E NC II |X]| x|||| S Sexp (klog
(92)
Finally, we extend the above argument from the net to all k-sparse vectors. From Corollary 2, we have
Pr 3I S o [X] = k. || > C2c & exp (-
(-oppp--ep -41 (())))
9e
(93)
First assume that the events in equation 92 and equation 93 happen. Any k-sparse vector u can be written as u = a + b, where E N, and satisfies [supp(b) < k and [|b|[2 S 1/(2C)). Let Io = supp(b) C [d]or and let i be b restricted to To. Let R/ be the submatrix of Rld with columns indexed by I.. Then
XR w/I2
| X
(94)
||X a || b112
(95)
|| A||2 + R /, b|12
(96)
||XR a|12 + || / ||
(97)
1
< (1 + ++++)|XX|] + 2C²
| RR!
(98)
<
(99)
where the bound on ||X is from equation 92 and the spectrum norm bound for [| ll is from equation 93. Similarly,
|R (1- (1-
(100)
Adjusting the constants and removing the conditioning completes the proof.
31

---

Published in Transactions on Machine Learning Research (08/2022)
For proving the above Theorem 8, the Hanson- Wannhn-Wright Inequality and its corollaries useful. We thus include them here for completeness.
Theorem 9 (Hanson- Wright Inequality (Rudelson et al., 2013)). Let (#1 In) E R be random vector with independent components zi which satisfy B[x;] 0 and || I K. Let M be on X a matriz. Then for every 1 2 0,
t² M K2IIM })
Pr [ Mx - E(r Ma]] > t] < 2xxp -cmin
(101)
Corollary 1 (Subgaussian Concentration (Rudclson et al., 2013)). Let M be a fixed n x d matriz. Let x == (x),..., E IK" be a random veclor with independent. components Is which salisfies E[r.] = 0, E[ and | S K. Then for every 2 0,
ct2
Mr e > t S exx
(102)
K K
Corollary 2 (Spectrum Norm of the Product (Rudelson et al., 2013)). Let B be fixed n x matriz, and let G GGg) be a x d matrir with independent entries that satisfy: E|G,,] = 0, B[G = 1, and [Giilllv S K. Then for any a, b > 0,
Pr|1BG||2> (K<(| + < 2exp (ra²sr(B) - -bdd)
(103)
B Dataset Licenses.
The Delancy (Delancy, 2004), CEP (Hachmann al., 2011), QM7 (Blum & Reymond, 2009), QM9 (Ruddigkeit et al., 2012), MUV (Rohrer & Baumann, 2009), and MUTAGENICITY (Kazius al., 2005) datasets are all licensed under the Copyright @ of the American Chemical Society (ACS) which allows free usage of the data and materials appearing in public domain articles without any permission. The QM8 (Ramakrishnan et al., 2015) dataset is under Creative Commons Attribution (CC BY) license of the American Institute of Physics (ATP) Publishing LLC requiring no permission from the authors and publisher for using publicly released data from the paper. The ClinTox (Gayvert al., 2016) dataset under the Copyright of Elsevier Ltd. which permits usage of public domain works and open access content without author permissions. The Malaria (Gamo et al., 2010) dataset is licensed under Copyright c of Macmillan Publishers Limited that allows usage for personal and noncommercial use. The Tox21 (Tox21 Data Challenge, 2014) dataset was released by NIH National Center for Advancing Translational Sciences for free public usage a part of a d'crowdsourced' data analysis challenge. The HIV (AIDS Antiviral Screen Data, 2017) datasel was released by NIH National Cancer Institute (NCI) for public usage without any confidentiality agreement which allows access to chemical structural data on compounds. The IMDB-BINARY, IMDB-MULTI, REDDIT- BIN ARY, COLLAB (Yanardag & Vishwanathan, 2015) datasets licensed under ACM Copyright @ 2015 under Creative Commons License that allows free usage for non-commercial academic purposes.
32


Reviews:
[{"review_id": "2R5Ucc0uda", "reviewer": "Reviewer_pDMn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Overview**\n \nOverall, the paper is easy to understand. The motivation appears to be filling the lack of attention-based walk-aggregating GNNs, aiming to achieve more accurate models with some theoretical guarantees. It seems that the proposed approach lies inside the framework of MP-GNNs with additional design choices (residuals connections, etc.). This connection should be clarified in the paper. I also have some concerns regarding the correctness of the theoretical formalization. Lastly, the experimental setup would benefit from considering recent benchmarks to position the proposal in terms of SOTA GNNs.\n\nStrengths:\n+ Good empirical results\n+ Easy to read\n+ Simplicity of the proposed model\n\nWeaknesses:\n- Lack of a strong motivation\n- Limited novelty\n- Possible mistake in the theoretical analysis\n- The empirical evaluation should consider more recent benchmarks\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes AWARE --- a new approach for representation learning on graphs based on attentive walk-aggregating schemes. The authors also present a theoretical analysis of the attention-based weighting scheme, formalizing conditions on which the proposed method would provide performance gains. Experiments on a series of graph-level prediction tasks assess the effectiveness of the proposal. Additional empirical illustrations highlight the potential of the proposal toward more interpretable graph models. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Here I provide detailed comments:\n\n**Regarding the proposed method**\n\nFollowing the framework of message-passing GNNs, the proposal seems to apply an attention-based neighborhood aggregation and identity update scheme with shared parameters: \n - The representation of each node is modified by a convex combination of the previous-layer representation of its neighbors. And the convex combination is defined via attention. The model applies the same aggregation function (same $W_w$ parameters) at different layers.\n - The motivation behind taking the point-wise product with the first representation $F_{(1)}$ (first equation after Eq. 3) is not clear. \n - The weighted summarization scheme seems to correspond to using concatenation-based residual connections and a sum-based readout layer.\n\nIs the analogy above correct?  Can the proposed method be cast into the framework of message-passing GNNs (aggregation and update functions at each layer) with residual connections?\n\nIn the second equation after Eq. (3), $\\bf{1}$ is an $m \\times m$ matrix. Is it correct?\n\nThe 1-WL isomorphism test has been a key tool for analyzing the power of GNNs. How does the proposal compare with existing GNNs in terms of 1-WL? Pure attention layers (without positional embeddings) are known to be proportion invariant. Does it limit the power of the proposed method?\n\n**Regarding the theoretical analysis**\n\nPart of the theoretical analysis derives from unrolling the computation tree of MP-GNNs and treating them as sets of attributed walks. \n\nI have a concern regarding Definition 3. Consider the graph $V=\\\\{a, b, c, d\\\\}$ and $E = \\\\{(a,b), (a,c), (b, d)\\\\}$, where $v_a = v_b = v_c$, and $v_d \\neq v_a$, where $v_i$ denote the attribute value of node $i$. Then, we can have a single walk type $v = (v_a, v_b, v_a) = (v_a, v_c, v_a)$ associated with two different weights since $b$ has degree 2 but $c$ has degree 1. The point is that the attention mechanism (unlike Eq. 2) does not depend only on latent representations ($f_j$ and $f_i$) but also on its neighbors (since attention is normalized --- see Eq. (3)). Is this correct? If so, it might cause some side effects in the results as you can not consider that identical attributed walks will have the same weights.\n\nIn addition, given the similarities between the theoretical results for the general case (5.3) and the simplified one (5.1 and 5.2), the authors should consider keeping only one of them in the main paper and moving the other one to the supplementary material.\n\n**Regarding the evaluation setup**\n\nPrevious works [1,2] have reported some problems in evaluating GNNs using some of the datasets employed in this paper. I would suggest authors consider more recent benchmarks (e.g., Open Graph Benchmarks).\n\nIt is also possible to observe differences between numbers in the original papers and the ones reported in the Tables. For instance, from the GIN paper, we get 0.75 vs. 0.69 on IMDB, 0.669 vs. 0.802 on COLLAB, etc. Do these discrepancies come from differences in the evaluation setup? Which differences?\n\nThe community (see [3]) has raised some concerns regarding the limitation of attention weights to be treated as explanations. I believe the paper does not provide sufficient evidence to support the interpretability aspect of AWARE. \n\n[1] https://arxiv.org/abs/1912.09893\n\n[2] https://arxiv.org/abs/1811.05868\n\n[3] https://arxiv.org/abs/1902.10186", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8UItQbegYo", "reviewer": "Reviewer_wz9z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "With regards to the proposed architecture, in my view, the paper seems to be proposing an incremental contribution for the graph representation learning community. In fact the proposed model is an instance of the family of message passing neural networks, and is thus very similar to existing models. The main strength of the paper lies in the provided theoretical results. I am not though sure how useful those results are. For instance, for the first set of results to hold, it is necessary that $W_v$ and $W_g$ are both identity matrices and $\\sigma()$ the linear function. In such a case, the emerging model contains only a few trainable matrices, while as shown in Table 7 achieves much worse performance in most cases. The good empirical performance is another strength of the paper. Indeed, the model outperform the baselines in most cases, while it is also interpretable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors present AWARE, a graph neural network for graph-level learning tasks. The model uses an attention mechanism which allows nodes to put more emphasis on specific neighbors. The model computes the sum of the nodes' latent representations to produce a vector representation for the entire graph. The authors provide some theoretical results about the representations learned by the proposed model and also some guarantees on the model's learning performance. The proposed model is evaluated on several graph classification and graph regression datasets where in most cases it outperforms the baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Major issues\n\n- It is not directly clear to the reader how the proposed model aggregates random walks. One needs to read section 5 (that contains the theoretical results) to get some intuition. I would suggest the authors make clear in sections 3 and 4 how walks are taken into account by the model. Furthermore, since each node updates its representation by aggregating the representations of its neighbors and combining them with its initial representation, there is no doubt that the model falls into the category of message passing neural networks. Thus, I would suggest the authors also discuss how the model is related to this family of models.\n\n- To compute a representation for the entire graph, the model obtains walk set embeddings of length $n$ as follows: $f_{(n)} = \\sigma(W_g F_{(n)}) 1$ where $1$ is the $m \\times m$ matrix of ones. I would expect $f_{(n)}$ to be a vector, but since $F_{(n)} \\in \\mathbb{R}^{r' \\times m}$ and $W_g \\in \\mathbb{R}^{r' \\times r'}$, then $f_{(n)} \\in \\mathbb{R}^{r' \\times m}$. Perhaps $1$ has to actually be the $m \\times 1$ vector of ones such that the node representations are aggregated. Furthermore, the authors mention that the proposed model learns $W_g$ to compute a weighted sum of latent vertex representations. To my understanding, $W_g$ just performs a linear transformation of the node representations and no sum across nodes is performed. I would like the authors to comment on that.\n\n- To compute new node features, the authors propose the following update rule: $F_{(n)} = \\big( F_{(n-1)} (A \\odot S_n)\\big) \\odot F_{(1)}$. It seems thus that the node features that emerge from the different iterations of the algorithm have all the same size. Could this have a negative impact on the performance of the model (e.g., underfitting or overfitting) in case of the number of rows of $F_{(1)}$ is relatively small or large?\n\n- For two datasets, the authors remove graphs whose number of nodes is greater than some threshold. It is not clear to me what is the reason behind that. Does this imply that the proposed model cannot be applied to datasets that contain large graphs? If this is the case, this is a major limitation of the proposed model, and I would like the authors to comment on that.\n\n- For the evaluation, each dataset is split into 5 different sets of training, validation and test sets with a ratio of 8-1-1. I am not sure whether this is a good practice since some of the samples might not occur in any of the test sets. Moreover, previous studies commonly perform 10-fold cross validation in the case of datasets for which no splits are available (e.g., IMDB-BINARY, etc.). And since some of the datasets are small, the 10-fold cross validation could be performed multiple times. I would suggest the authors use an evaluation protocol such as the one discussed above such that the reported results are also comparable to those of previous studies. For instance, the accuracies achieved by GIN and the WL kernel in Table 4 are different from the ones reported in previous studies.\n\n\nMinor issues\n\n- Notation is a bit confusing. Bold font is used for some matrices (e.g, $S_n$) and not for others (e.g., $W_v$). The authors should make sure that notation is consistent throughout the manuscript and easy to follow.\n\n- Figures 1 and 2 are a bit hard to read. It would strengthen the paper if barplots were replaced with line charts.\n\n- The paper is very well-written and easy to read. However, there are some typos:\\\np.4 \"and then perform\" -> \"and then performs\"\\\np.12 \"This demonstrate\" -> \"This demonstrates\"\\\np.12 \"is $h_i$, the concatenation\" -> \", $h_i$ is the concatenation\"", "broader_impact_concerns": "There is a Broader Impact Statement in the last section that discusses the ethical implications of the work and addresses concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UT9XgxsV5J", "reviewer": "Reviewer_T127", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "** After writing this review, I find that I interchangeably use 'nodes' and 'vertices'. Please note.  **\n\n# Pros: \n1.  The paper is well-written and easy to follow. \n2.  Under assumptions provided by the authors, he theoretical analysis is extensive, detailed and sound. \n3.  The empirical results are very extensive. The proposed AWARE compares favorably against a good range of baselines. \n4.  The visualization and interpretation results, including both the substructure identification, and the singular vectors, are interesting pluses to the proposed model. It may bring insights to molecule learning and drug discovery. \n\n# Cons: \n1. I personally don't think that the claims of \"weighting\" are well justified. The authors claim that there are three levels of weighting (node, walk, and graph). However, I find the node level and the graph level unconvincing. First, in Section 4, paragraph \"Weighted vertex embedding\", the authors use the scheme $F_{(1)} = \\sigma(W_vF)$, which is basically a linear projection which holds for all nodes and attributes. However, by 'weighting', we generally require that different nodes/attributes should get different projections (which is what attention does). Similarly, the \"weighted summarization\" is also doubtful as it does similar things as the \"weighted node embedding\". Basically, the same linear projection is used for all walks. \n2. The theoretical results require very strong assumptions on RIP.  In the theoretical analysis, the authors assume that $\\mathcal{M}, W^{[n]}$ is RIP. However, as far as I know, $W$ is RIP requires that the singular values of $W$ lie in $[1-\\varepsilon, 1+\\varepsilon]$, which is a very strong assumption on $W$'s condition. Although the authors state in Theorem 2 that \"there is a prior distribution over $W$ such that w.h.p. $W^{[n]}$ is RIP\", what the prior distribution looks like is unknown, and thus, Theorem 2 does not tell whether the assumption holds in reality. ** Please correct me if I make mistakes in the assessment. **\n3. The effect of walk statistics is not clear. The authors establish the theoretical analysis based on $c_{(n)}$, the walk statistics (Remark on Page 11). However, it is not clear what can be derived from the walk statistics. Specifically, it is not clear whether walk statistics encompass the commonly used WL-test in GNNs' abilities (Xu et al. 2019), (Morris et al. 2019). Some attempts to relate walk statistics to graph distinguishability or WL test should be done to better theoretically justify AWARE. \n4. The authors may want to discuss and compare AWARE and GCKN (Chen et al. 2020). GCKN with walk kernels can be walk-aggregating GNNs, and is also theoretically justified. Moreover, GCKN reports 75.9, 53.4, 81.7 for IMDB-B, IMDB-M, and COLLAB respectively, while AWARE reports 74, 49.9, 73.9, which seems inferior to GCKN. Finally, GCKN also has the ability to interpret important substructures in MUTAG. Thus, GCKN is a relevant baseline and should be discussed and compared. \n5. Please number all equations. \n6. Comparing with existing GNNs such as GCN and GAT, the authors seem to remove all projection matrices (e.g. the $W$ in $X^{(l+1)} = AX^{(l)}W$ in GCN), and use simple concatenation as the readout (i.e. the aggregation from node/walk embeddings to graph embeddings), which seems to greatly simplify the model. Is that true? If it is, then I would appreciate that the authors justify why they make that choice, as it is against the common practices. \n\nHow powerful are graph neural networks? Xu. et al. ICLR 2019. \n\nWeisfeller and Lehman goes neural: Higher-order graph neural networks. Morris et al. AAAI 2019. \n\nConvolutional Kernel Networks for Graph-Structured Data. Chen et al. ICML 2020. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an attention based graph neural networks (AWARE) to learn graph representations for end-to-end supervised graph learning tasks. The authors claim to build AWARE upon walk-aggregation GNNs (e.g. the N-gram graph in Liu et al. 2019) by adding proper weighting mechanisms via node, walk, and graph level attention. The authors derive theoretical results on the ability of AWARE under assumptions, and provide extensive empirical results on a large set of graph learning tasks compared to a good set of baselines. Moreover, the authors demonstrate that their proposed AWARE is interpretable in capturing indicative substructures in molecule graphs. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Important: \n1. Discuss and compare with GCKN (Chen et al. 2020) as a closely related baseline. \n2. Discuss the distinguishability of walk statistics. It would be favorable if the authors can relate it to the WL-test. \n\nLess important: \n1. Discuss why AWARE removes all projection matrices and the graph readout function, and its potential impact. \n2. Change the claims about the three-level weighting, as the node- and graph-levels are somewhat against what is commonly said. ", "broader_impact_concerns": "Not applicable. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a walk-aggregating GNN called AWARE, with added attention weighting of the edges.  Theoretical analysis of the representation power and the learning capabilities of this model are presented, together with strong empirical results.

The authors have addressed reviewers’ questions in the discussion and have also made revisions to clarify issues pointed out by the reviewers.

Two things stand out from the reviews that the authors have tried to address, but I think can still be improved:

1. The derivation of Eq (2) as walk-aggregation.  This confused more than 1 reviewer and is worth addressing a bit more.  In the revision the authors added a paragraph to explain this but it might be better to have a short derivation from the walk-aggregation perspective for clarity.

2. The representation power of the walk statistics.  This was pointed out by all reviewers.  Two sentences were added in the revision on page 7.  But it would be good to expand on this a bit more.  If it is not easy to make formal claims it would be good to give some examples to make this more intuitive, for example a pair of graphs that cannot be distinguished using walk statistics would be quite helpful here.

Overall I would recommend accepting this paper, and addressing the above two things would make this paper better.
Decision: Accept (poster)