Adaptive Structural Fingerprints for Graph Attention Networks
Authors: Kai Zhang
Yaokang Zhu
Jun Wang
Jie Zhang
Venue:  (2020)
Keywords: Graph attention networks
graph neural networks
node classification

Abstract: Graph attention network (GAT) is a promising framework to perform convolution and massage passing on graphs. Yet, how to fully exploit rich structural information in the attention mechanism remains a challenge. In the current version, GAT calculates attention scores mainly using node features and among one-hop neighbors, while increasing the attention range to higher-order neighbors can negatively affect its performance, reflecting the over-smoothing risk of GAT (or graph neural networks in general), and the ineffectiveness in exploiting graph structural details. In this paper, we propose an ``"adaptive structural fingerprint" (ADSF) model to fully exploit graph topological details in graph attention network. The key idea is to contextualize each node with a weighted, learnable receptive field  encoding rich and diverse local graph structures. By doing this, structural interactions between the nodes can  be inferred accurately, thus significantly improving subsequent attention layer as well as the convergence of learning. Furthermore, our model provides a useful platform  for different subspaces of node features and various scales of graph structures to ``cross-talk'' with each other through the learning of multi-head attention, being particularly useful in handling complex real-world data. Empirical results demonstrate the power of our approach in exploiting rich structural information in GAT and in alleviating  the intrinsic oversmoothing problem in graph neural networks.

Published as a conference paper at ICLR 2020
ADAPTIVE STRUCTURAL FINGERPRINTS FOR GRAPH ATTENTION NETWORKS
Kai Zhang
Yaokang Zhu & Jun Wang*
Department of Computer & Information Sciences Temple University
School of Computer Science and Technology East Chine Normal University, Shanghai China 521 8 84501 02 026ust....................uuu... ecnu. edu.cn Swangesei ecnu, edu. en
Philadelphia PA 19122, USA
82hang980@gmaiin com
Jie Zhang
Institute of Brain-Inspired Intelligence Fudan University, Shanghai China jzhang0 80@ gmail. com.
ABSTRACT
Graph attention network (GAT) a promising framework perform convolution and massage passing graphs. Yet, how to fully exploit rich structural informa- tion in the attention mechanism remains challenge. the current version, GAT calculates attention scores mainly using node features and among one-hop neigh- bors, while increasing the attention range to higher-order neighbors can negatively affect performance, reflecting the over-smoothing risk of GAT (or graph neural networks in general), and the ineffectiveness in exploiting graph structural details. In this paper, propose "adaptive structural fingerprint" (ADSF) model fully exploit graph topological details in graph attention network. The key idea is contextualize each node with weighted, learnable receptive field encod- ing rich and diverse local graph structures. By doing this, structural interactions between the nodes can be inferred accurately, thus significantly improving sub- sequent attention layer as well as the convergence of learning. Furthermore, our model provides useful platform for different subspaces of node features and var- ious scales of graph structures to "cross- talk" with each other through the learning multi-head attention, being particularly useful in handling complex real-world data. Empirical results demonstrate the power of our approach in exploiting rich structural information in GAT and in alleviating the intrinsic oversmoothing prob- lem in graph neural networks.
INTRODUCTION
Many real-world data set are represented naturally as graphs. For example, citation networks spec- ify the citation links among scientific papers; social media often need to explore the significant amount of connections between users; biological processes typically involve complex interactions such protein-protein irotein-interaationn (PPI). In these scenarios, the complex structures such the graph topology or connectivities encode crucial domain -mpnaff knowledge for the learning and prediction tasks. Examples include node embedding or classification, graph classification, and so on.
The complexity of graph-struetured data makes it non-trivial to employ traditional convolutional neural networks (CNN's). The CNN architecture was originally designed for images whose pixels are located on a uniform grids, and so the convolutional filters can be reused everywhere without having accommodate local structure changes (LeCun & Kavukcuoglu] 2010). However, extend- ing CNN to deal with arbitrary structured graphs can be non-trivial. To solve this problem, graph neural networks (GNN) were early proposed by Gori et al. (2005) and Sperduti (1997). which adopt
"Coressonning author 'Corrsponding author

---

Published as a conference paper at ICLR 2020
an iterative process to propagate the state of each node, followed by neural network module to generate the output until an equilibrium state is reached. Recent development of GNN can be cat- egorized into spectral and non-spectral approaches. Spectral approaches employ the tools in signal processing and transform the convolutional operation in the graph domain to much simpler opera- tions of the Laplacian spectrum (Bruna et al., 2014), and various approaches have been proposed to localize the convolution in either the graph or spectral domain (Henaff et al. 2015 Defferrard al. 2016 Kipf & Welling, 2017). Non-spectral approaches define convolutions directly on the neighboring nodes. As a result, varying node structures have to be accommodated through various processing steps such as need-heeghhooohoo size sampling (Hamilton et al., (017). neighborhood normalization (Niepert et al., 2016), or learning a weight matrix for each node degree (Duvenaud jet al. 2013) or neighborhood size (Hamilton et al.) 2017). Recently, residual network is also intro- duced to graph neural networks (Zhang & Meng 2019).
Recently, graph attention network (GAT) proves a promising framework by combining graph neural networks with attention mechanism (Velickovic et al. 2017). The attention mechanism allows deal- ing with variable sized input while focusing on the most relevant parts, and has been widely used in sequence modelling (Bahdanau et al., 2015), machine translation (Luong al., 2015), and visual processing (Xu et al. 2015). The GAT model further introduces attention module into graphs, where the hidden representation of the nodes are computed by repeatedly attending over their neighbors' features, and the weighting coefficients are calculated inductively hased on a self-attention strategy.
Despite the numerous success, how exploit structural information in GAT remains an challenge. Note that attention scores in GAT are computed mainly based on the content of the nodes; the structures of the graph are simply used mask the attention, e.g., only one-hop neighbors will be attended. When considering attention among higher order neighbors, however, the performance of GAT deteriorates (see experimental section for details). This is closely related to over-smoothing of GNN's s (Li et al., 2018) and reflects the weakness of GAT in effectively exploiting graph structural information. In this paper, we believe that the topology or "shapes" of local edge connections scan provide a valuable guidance on how to exploit rich structural information of graphs. For example, in social networks or biological networks, a community or pathway may be composed of nodes that are densely inter-connected with each other but several hops away. Therefore, it can be beneficial attend neighbors from the same community, even they show no direct connections. To achieve this, simply checking k-hop neighbors would seem insufficient and a thorough exploration of structural landscapes of the graph becomes necessary.
In order to fully exploit rich, high-order structural details in graph attention networks, propose a new model called "adaptive structural fingerprints". The key idea is to contextualize each node within local receptive field composed of its high-order neighbors. Each node in the neighborhood will be assigned a non-negative, closed-form weighting based on local information propagation procedures, and so the domain (or shape) of the receptive field will adapt automatically to local graph structures and the learning task. We call this weighted, tunable receptive field for each node its "structural fingerprint". The structural fingerprint encodes important structural details and will be used in conjunction with the node feature to compute an improved attention layer. Furthermore, our approach provides a useful platform for different subspaces of the node features and various scales of local graph structures to coordinate with each other in learning multi-head attention, being particularly beneficial in handling complex real-world graph data sets.
In Section 2, we introduce the proposed method, including limitation of content-based attention, construction of adaptive structural fingerprints, and the algorithm workflow. In Section 3, we discuss related work. Section 4 reports empirical evaluations and the last section concludes the paper.
2 EXPLOITING GRAPH STRUCTURAL DETAILS IN ATTENTION
2.1 LIMITATIONS OF CONTENT-BASER ATTENTION
The "closeness" between two nodes should be determined from both their content and structure. Here we illustrate the importance of detailed graph structures in determining node similarities. In Figure 1(a), suppose the feature similarity of node-pairs (A.B) and (A,C) similar. Namely, content- based attention will be similar for this two node pairs. However, from structural point of view, the attention between (A.B) should be much stronger than that for (A,C). This is because A
2

---

Published as a conference paper at ICLR 2020
and B are located in small, densely inter-connected community, and they share significant portion of common neighbors; while node A and does not have any common neighbor. Figure 1(b), node A and node B are not direct neighbors, and connecting them takes three edges. As result, their features will not directly affect each other in the message passing of GAT However, both A and B are strongly connected to dense community, and node B further connects to the community hub. Therefore, it is reasonable for A and B to directly affect each other.
A
B
A
(a) Common neighbors of two nodes
(b) Attachment the same community
Figure 1: Detailed graph structures provide important guidance in determining node attention.
In these examples, feature based similarity alone is insufficient in computing a faithful attention. One may need to take into account structural details of higher-order neighbors and how they interact with each other. In the literature, structural clues have long been exploited in solving problems of clustering, semi-supervised learning, and community detection For example, normalized cut minimizes edge connections between clusters for node partitioning (Shi & Malik (2000;: mean-shin uses density peaks to identify clusters (Comaniciu Meer y low-density separation (Chapelle & Zien 2005) assumes that class boundaries pass through low-density regions, leading to successful semi-supervised classification; in community detection, densely connected subgraphs are the main indicator of community (Girvan & Newman 2002).
In the following, we show how to build "adaptive structural fingerprint" to extract informative struc- tural clues to improve graph attention and henceforth node embedding and classification.
2.2 ADAPTIVE STRUCTURAL FINGERPRINTS
Key to exploiting the structural information is the construction of the so-called "adaptive structural fingerprints", by placing each node in the context of the its local "receptive field". Figure is an illustration. For any node i. consider a spanning process that locates local subgraph around i, for example, all the nodes within the k-hop neighbors of Denote the resultant subgraph as (V,, F.a, where V; and E; are the set of nodes (dark red) and edges (black) in this neighborhood. In the meantime, each node in will be assigned a non-negative weight, denoted by w; E R which specifies the importance of each node in shaping the receptive filed also determines the effective "shape" and size of the field. The structural fingerprint of node will be defined as F; = (V, w.).
2.3 CONSTRUCTION OF THE STRUCTURAL FINGERPRINTS
Intuitively, the weight of the nodes should decay with their distance from the center of the fingerprint. A simple idea is to compute the weight of the node j using a Gaussian function of its distance from
the center node i, l.e.,w(()) = exp( dis(i.g)?
2h which we call Gaussian decay. Alternatively, we can map the node distance levels [1, 2..,, ... k] to weight levels negative and monotonic; we call nonparametric decay, which is more flexible and will be used in experiments. In both cases, the decay parameter (Gaussian bandwidth h nonparametric decay profile u) can be optimized, making the structural fingerprint more adaptive to the learning process.
[Wi, U2, ... ux] which are non-
In practice, it is more desirable if node weights be automatically adjusted by local graph struc- tures (shapes or density of connections). To achieve this, we propose to use Random Walk with Restart (RWR). Random walks were first developed to explore global topology of network by simulating particle iteratively moving among neighboring nodes (Lovasz 1993). If the particle is
If one considers multiple message passing steps, higher-order neighhors may finally affect each other; hut this difficult analyze and convergence can he slower than interactions within one step.
3

---

Published as a conference paper at ICLR 2020
Node weights
Canter
04.
01
Node
Local graph patch
Figure 2: Structural fingerprint for given node i, denoted by F; (V, wi), where V; is the set of nodes in this local receptive field and w; the contributing weights of the nodes.
Gossoian
Gavosian
Local graph (structural fingerpeint)
Center
node
Randomwalk
Handomealt
Figure 3: Weights w, of toy structural fingerprint. Left: the local subgraph/fingerrrint, middle: visualization of the weights; right: contours of the weights. Gaussian decay and RWR(random walk with restart) decay leads different weight contours, the latter more adaptively adjusting the weights to structural details of the local graph.
forced to always restart in the same node (or set of "seedd" nodes), random walk with restart (RWR) can then quantify the structural proximity between the seed(s) and all the other nodes in the graph, which has been widely used in information retrieval (Tong et al. 2006 Pan et al.] 2004).
Consider a random walk with restart on a structural fingerprint centered around node with alto- gether n, nodes and adjacency matrix E, The particle starts from the center node i and randomly walks to its neighbors Vú with probability proportional to edge weights. In each step. also has certain probability return to the center node. The iteration be written
w ((+1) E.E. (t) (1-c)-oo
where E is the transition probability matrix by normalizing columns of E,, E [0, is a trade- off parameter between random walk and restart, and e; a vector of all zeros except the entry corresponding to the center node The converged solution be written in closed form as
w: =
(1)
The w, quantifies the proximity between the center node and all other nodes of the fingerprint, and in the meantime naturally reflects local structural details of the graph. The e controls the decaying rate (effective size) of the fingerprint: if 0, w: will all be zeros except the ith node; if c 1, w; will be the stationary distribution of a standard random walk on graph (V,, E,). In practice, c will be optimized that the fingerprint adapts naturally to both the graph structure and the learning task.
4

---

Published as a conference paper at ICLR 2020
In Figure 3. illustrate Gaussian-basee and RWR-based fingerprint weights. We created toy example of local receptive field, which for convenience a uniform grid but with a small denser "patch" on the right bottom. As can be expected, the Gaussian based weight decay has contours that are center-symmetric. In comparison, the RWR automatically takes into account salient local struc- tures and the contours will be biased towards the dense subgraph. This is particularly desirable in case the center node is close to (or residing in) a community; it will then be represented more closely by the nodes from community, achieving the effect of "structural attractor".
As can be seen, the "structural attractor" effect in building the fingerprint with RWR coincides well with commonly used clustering assumptions, namely, the structural fingerprint of node will em- phasize more on densely inter- coteeccd neighbors within predefined range. Since highly weighted nodes are more likely to come from the same cluster as the center node, the fingerprint of each node is supposed to provide highly informative guidance on its structural identity, thus improving evaluation of node similarites and finally the graph attention.
2.4 ALGORITHM DESCRIPTION
In this section we will exploit both the content and structural details of the graph in the GAT frame- work (Velickovic et al. 2017). Our algorithm is illustrated Figure 4.
Message passing
Transform
Structural fingerprint
Structural fingerprint
Node
Node
feature
feature
trructuall interaction
Content similarity
Attention Layer
Figure 4: The work flow of adaptive structural fingerprint model.
Suppose we want to compute attention coefficients between pair of nodes i and j. each with their features and structural fingerprints. Content-wise, features of the two nodes will be used to compute their content similarity; structure-wise, structural fingerprints of the two nodes will be used to evaluate their interaction. Both scores will be incorporated the attention layer, which will then be used in the message passing step to update node features. Following Velickovic et al. (017)). we also apply a transform on the features, and apply multiple steps of message passing.
More specifically, given graph of nodes G EV where V is the set of the nodes and E is the set of the edges; let (h. be the d-dimennional input features for each node. We will follow the basic structure of GAT algorithm (Velickovic al. 2017) and describe our algorithms follows.
Step I. Evaluate the content similarity between node and j as
Eij feo Wh;, Wh,)
(2)
where W E Raxd is the transformation that maps the node features to a latent space, and function A ()) computes similarity (or interaction) between feature h, and hj.
Afea(Wh, (Wh,, Wh;) a (Wh: (Wh;)
(3)
5

---

Published as a conference paper at ICLR 2020
Step 2. Evaluate structural interaction between the structural fingerprints of node and j.
Sij
(4)
where Astr(FFs F2) quantifies the interaction between two fingerprints. Let w, and wj be the node weights of the fingerprints for node i and j, as discussed in Section 2.3. Then we can adopt the weighted Jacard similarity to evaluate the structural interactions, as
Aatr F,) EpE(nUU)) min(Wip: Wjp)
Epe(YAUV,) max(Wapp Wjp)
Here, with an abuse of notations, we have expanded w, and w, to all the nodes in VUV, by filling zeros. We can consider the following smooth version, or other smooth alternative
max y) lim log(e" TM +e'²) min(r,y) =lim log(c" + (-(-)))
t
t
Step 3. Normalize (sparsify) feature similarities 2 and the structural interactions as
exp(LeakyRelu(ex))
exp(s1))
Eij
Sij"
(5)
Σ exp(LeakyRelu(ea.)
exp(8tt)
and then combine them to compute the final attention
EE + 8(3
aij a (( B(5,g)
(6)
Here ax-) and B(-) are transfer functions (such as Sigmoid) that adjust feature similarity and structure interaction scores before combining them. For simplicity (and in our experi- ments), use scalar and B, which leads to standard weighted average.
Step 4. Perform message passing to update the features of each node as
(++) h
Σ JEAG
OBS Wh
Our algorithm has a particular advantage when multi-head attention is pursued. Note that our model simultaneously calculates two attention scores: the content-based eij and structure-based sij, and combine them together. Therefore each attention head will accommodate two sets of parameters: (1) those of the content-based attention, W and (3). which explores the subspace of the node features, and (2) those of the structure- -asee attention, II which explores the decay rate of the structural
fingerprint. As result, by learning an optimal mixture of the two attention (6) our model provides flexible platform for different subspaces of node features and various scales of local graph structures to "cross-talk" with each other, which can be quite useful in exploring complex real-world data.
Computationally, the local receptive field will be confined within a k-hop neighborhood, which we call "fingerprint size"; on the other hand, both structural attention and content-based attention will be considered only when the center node of the two receptive fields have distance below the threshold k, which we call "attention range". In experiments we simply set = k' = 2, and use breadth- first-search (BFS) to localize the neighborhood. As result, the complexity involved in structure exploration will be (nn(Nrl),, where [Wer is the averaged k t'-hhop-neighhor size.
3 COMPARISONS WITH RELATED WORK
Note that in graph convolutional network (Kipf & Welling 2017), the node representation is updated by h ((+1) EjENa [D 1/2 AD/AAD-11 AD-1/1)) w) where is the adjacency matrix, D is the de- gree matrix, h; is representation of the ith node and W embedding matrix. Namely, the message
Astrr F,, F3) Σyeny "iwip--pp?" Epen, Wip "iptZpea where 7(2, y) denotes either the arithmetic geometric mean of and y, and where Ω Vg 2 Vi, and Fug V, V.V.

---

Published as a conference paper at ICLR 2020
Data
Nodes
Edges
# Features
# Classes
#Training
Validation
# #'lesting
Cora 2708
5429
1433
7
140
500
1000
Citeseer 3327
4732
3703
6
120
500
1000
Pubmed 19717
44338
500
3
60
500
1000
Table 1: Summary statistics of the benchmark graph-structure data sets used in the experiment.
passing is mainly determined by the (normalized) adjacency matrix. The GAT method (Velickovic al., 2017) replaces the fixed adjacency matrix with an inductive, trainable attention function that relies instead on the node features within one-hop neighbors. Our approach has a notable difference.
First, our message passing is determined by a mixed attention from both structure and content (6). Second, the structural component of our attention is not simply based the graph adjacency (Kipl & Welling 2017). or one-hop neighbor (Velickovic et al., 2017), but instead relies on a local recep- tive field whose "shapes" optimized adaptively through learning (T). Furthermore,
method
fully exploits structural details (e.g. density and topology of local connections). There are also a number of works that explore structures in graph classification (Lee al., 2018; Rossi al. (019). There, attention is used to identify small but discriminative parts of the graph, also called "graphlets" or "motifs" (Morris al. 2019). in order perform classification on the graph level.
EXPERIMENTS
In this section, we report experimental results of the proposed method and statc-of-the-art algorithms using baph-based benchmark data sets and transductive classification problem. Our codes can be downloaded from the anonymous Github link http://gittubcoom//iigoz..
4.1 EXPERIMENTAL SETTING AND RESULTS
We have reported results of the following baseline algorithms: Gaussian fields and harmonic func- tion (Gaussian Fields) (Zhu et al. 2003). manifold regularization (Manifold Reg.) (Belkin et al.) 2006;; Deep Semi-supervised learning (Deep-Semi) (Weston al. 2012); link-based classification (Link-based Lu & Getoor. (2003); ; skip gram based graph embedding (Deep- Walk) (Perozzi et al.,
2014 semi-supervised learning with graph embedding (Planetoid) (Yang et al.) (016); graph con- volutional networks (GCN) (Kipf & Welling 2017); high-order chebyshev filters with GCN (Cheby- shev) (Defferrard et al. 2016). and the mixture model CNN (Mixure-CNN) (Monti et al. 2016).
We have selected three benchmark graph- structured data set from (Sen et al. 2008), namely Cora, Citeseer, and Pubmed. The three data sets are all citation networks. Here, each node denotes one document, and an edge will connect two nodes if there is citation link between the two document; the raw features of each document are bags-of-words representations. Each node (document) will be associated with one label, and following the transductive setting in (Velickovic et al., a [2017] Yang eet al. (2016) we only use 20 labeled samples for each class but with all the remaining, unlabelled data for training. We split the data set into three parts: training, validation, and testing, in table 1. Algorithm performance will be evaluated on the classification precision on the test split. For algorithm using random initialization, averaged performance over 10 runs will be reported.
shown
The network structures of our methods follow the GAT method (Velickovic et al. 2017), with the following details. Altogether two layers of message passing are adopted. In the first layer, one transformation matrix W E Rdx8 is learned for each of altogether 8 attention heads; in the second layer, a transformation matrix W E R84xC is used on the concatenated features (from the 8 attention head from the first layer), and one attention head is adopted followed by softmax operator, where C' is the number of classes. The number of parameters 64(d + C). For the Pubmed data set, attention heads are used in the second layer due to the larger graph size. Adam SGD is used for optimization, with learning rate À = 5 x le 4. See more details in (Velickovic et al. 2017). Both the fingerprint size and the attention range is chosen 2-hop neighbors in our approach.
Results are reported in table 2. Our method has 2 variations, including ADSF NoSp-aonparmmttric where random-
learn non-parametric decay profile w.r.t. node distance; ADSF-RWR, where walk with re-start to build fingerprints. For both cases, we have used 2-hop neighbors, and the restart probability is simply chosen e 0.5. As can be seen, approach consistently improves the

---

Published as a conference paper at ICLR 2020
Methods
Cora
Citeseer
Pubmed
Gaussian Fields (Zhu et al., 2003)
68.0%
45.3%
63.0%
Deep-Semi (Weston et al., 2012)
59.0%.
59.6%
71.7%
Manifold Reg. (Belkin et al., 2003)
59.5%
60.1%
70.7%
Deep-Ward Walk (Perozzi et al., 2014)
67.2%
43.2%
65.3%
Link-based (Lu & Getoor, 2003)
75.1%
69.1%
73.9%
Planetoid (Yang et al., 2016)
75.7%
64.7%
77.2%
Chebyshev (Deffer rard al., 2016)
81.2%
69.8%
74.4%
GCN (Kipf & Welling et al., 2017)
81.5%
70.3%
79.0%
Mixture-CNN Monti et al., 2016)
81.7%
79.0%
GAT (Velickovic et al., 2017)
83.0+-0.7%
72.5++0.7%
79.0+-0.3%
ADSF-Nonparametrii
84.7%t0.%%
73.8+0.3%
79.4-t0.3%
ADSF-RWR
85.4+-0.%%
74.0=
81.2++0.3%
Table 2: Classification accuracy for different transductive methods on the benchmark data sets.
performance on all benchmark data sets. Since Velickovic et al. (2017) has performed an extensive set of evaluations in their work, will their reported results forbaseline methods. It is also worthwhile to note that our method only has a few more parameters compared with GAT (e.g.. non- parametric decay profile u. e RWR, and the mixing ratios in (6)). For example, for Cora data set, GAT model has about 91k parameters, while our method adds around 30 extra parameters on top of (about 0.03% of the original model size).
6.8
0.8
08
6.7
GAT Melsed Our Mechae
Testng bouumary
GAT Methol
Teeting Rosurer
0.7
GAT Methos
0.8
2.3
05
0.3
0.4
60
100
150
206
50
100
150
200
100
150
200
(a) Cora data set
Citeseer data set
(c) Pubmed data set
OAT Huur Mathoo
Netie Oia Mathas
DAT Machal
1.7
0.0
000 1.4
LO05
1.5
100K
0.8
1.4
0.7
1.2
0.
68
1.1
100
206
150
200
120
150
(d) Cora data set
(c) Citeseer data set
Pubmed data set
Figure 5: Convergence of the accuracy and loss of the proposed method and GAT method.
In Figure 5, we plot evolution of the testing accuracy and loss function (on the test split) for GAT and our method (ADSF-RWR). Since the loss functions of the methods are the same, they directly comparable. The accuracy of GAT fluctuates through iterations, while our approach is more stable and converges a higher accuracy. The objective value of our method also converges faster thanks to the utilization of higher-order neighborhood information through structural fingerprints.
4.2 ABLATION STUDIES
In this section, We further examined some interesting details the proposed method, all using the Cora data and the RWR fingerprint construction scheme.
8

---

Published as a conference paper at ICLR 2020
Hop
==
=
=3
Cora
83.0++0.%%
6..2++68%%
13.314.7%
Citeseer
72.5+0.7%
65.7+-4.5% 68.4+..1%
Pubmed
79.0+0.3%
78.2+0.5%
67.2+0.3%
Table 3: Performance of GAT under different choices of the neighborhood range.
Impact of the fingerprint size. Intuitively, the structural fingerprint should neither be too small or too large. We have two steps to control the effective size of the fingerprint. In constructing the fin- gerprint, we will first choose neighboring nodes within certain range, namely the k-hop neighbors; then we will fine-tune the weight of each node in the fingerprint, either through nonparametric decay profile or the e parameter in random walk. Here, for comparison, we have fixed c 0.5 and varied k as k = 1, 3. As shown in Figure 6(a), the optimal order of neighborhood is two in this setting.
Impact of the attention range. In GAT, only direct neighbors have attention to each other, namely the attention range is k' = 1. In our approach, the optimal choice is k' 2. The attention range determines the number of neighboring nodes involved message passing. the Cora dataset, the average Ist-order neighborhood size is [ 3.9, while for 2nd-order neighbors [NG] 42.5. Namely, our approach has involved 10 times more neighbors in message passing than GAT, yet the performance is improved instead. This is an evidence that our approach helps alleviate oversmooth- ing in GAT (or GNN's in general) by exploiting high-order structural details more effectively.
Gaussann decsy Loarned deaa prrfee
tmportecce bomppt))
aG
11 x
Paramiter mindandeeeal
(a) Impact of neighbor range
(b) Impact of re-start probability
(c) Learned decay template
Figure 6: Detailed studies of the adaptive structural fingerprint method.
Impract of the re-start probability in RWR. Figure 6(b), we plot the learning performance w.r.t. the choice of the parameter in RWR when fixing the neighborhood range k = 2. As can be seen, the best performance is around = 0.5, meaning that the "random walking" and "restarting" should be given similar chances within 2-hop neighbors. Empirically, to optimize the choice of c, which can be more adaptive to the choice of the k-hop neighbors.
always use back pock-propagation
Non- maramereettric decay profile. In Figure 6(c), plot the non-part non-parametric decay profile u learned by our method, when setting the neighborhood orders to = 3. As can be seen, the first-order and second-order neighbors have higher weights, while the third-order neighbors almost have zero weights, meaning that they almost make no contributions to computing the structural attention. This consistent our evaluations in Figure 5(a), and demonstrates the power of our method in identi- fying useful high-order neighbors.
4.3 IMPACT OF NEIGHBORHOOD RANGE IN GAT
As suggested by the anonymous reviewer, we perform an empirical study on the GAT performance when larger attention range considered. Note that in the original GAT by Velickovie et al. (2017), attention score is computed only for nodes that are direct neighbors with each other. Here, we in- crease the domain of interaction to up to 2-hop and 3-hop neighbors, with all other components remaining the same. As can be seen from Table 3, the performance of GAT is the best when choosing only lhhop neighbors to compute attention scores, and deteriorates rapidly when larger neighborhood is considered.

---

Published as a conference paper at ICLR 2020
We speculate that although larger attention range involves more neighbors and possibly useful nodes, it bring a significant number of noisy nodes as well. As a result, the GAT performance is negatively affected. This seems to indicate that caature-baset attention alone might not be sufficient in identifying noisy neighbors. In our approach, attention scores are computed from both node features and informative structural details, therefore it enables exploring wider collection of higher- order-neighbors while simultancously removing the impact of irrelevant nodes, validating the benefit of structure- based attention.
5 CONCLUSION AND FUTURE WORK
In this work, proposed adaptive structural fingerprint model encode complex topological and structural information the graph to improve graph representation learning. In the future, we will consider varying fingerprint parameters (e.g. decay profile) instead of sharing them across all the nodes; we will consider applying our approach to graph partitioning and community detection, where node features might be unavailable and graph structures will be the main source of informa- tion that can be explored; we will also extend our approach to the challenging problem of graph classification. On the theoretical side, we will borrow existing tools in semi-supervised learning and study the generalization performance of our approach on semi-supervisee node embedding and classification.
ACKNOWLEDGEMENT
We highly appreciate the valuable comments from anonymous reviewers, which allow to signifi- cantly improve both the presentation and experimental design of our work. This work is supported in part by the National Science Foundation of China No.61672236, National Science Foundation of China No.61573107, Shanghai National Science Foundation 172R1444200, Shanghai Municipal Science and Technology Major Project No. No.20118H72D7X01..
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 7:2399-2433 2006.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In International Conference on Learning Representations, 2014.
Olivier Chapelle and Alexander Zien. Semi-supervised classification by low density separation. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, 2005.
Dorin Comaniciu and Peet Meer. Mean shift: a robust approach toward feature space analysis. JEEE Transactions Pattern Analysis and Machine Intelligence, 24:603 619, 08 2002.
Michael Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances Neural Information Processing Systems, 2016.
David K. Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, 2015.
Michelle Girvan and Mark Newman. Girvan, newman, and biological networks. proc. natl acad. sei. usa 99, 7821-7826. Proceedings of the National Academy of Sciences of the United States of America, 99:7821-6, 07 2002.
community structure in social
10

---

Published as a conference paper at ICLR 2020
Marco Gori, Gabriele Monfardini, Gori ScarselliMarco, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. IEEE International Joint Conference on Neural Networks, 2005.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Neural Information Processing Systems, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. In 150..05500.056.... 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Yann LeCun and Clément Kavukcuoglu, Koray Farabet. Convolutional networks and applications in vision. In Proceedings of IEEE International Symposium on Circuits and Systems, 2010.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In 32nd AAAI Conference on Artificial Intelligence, 2018.
L. Lovasz. Random walks on graphs: survey. Combinatorics, 2:1-46, 1993.
Qing Lu and Lise Getoor. Link-based classification. In Proceedings of the 20th International Conference on Machine Learning, 2003.
Minh-TTang Luong, Hicu Pham, and Christoper Manning. Effective approaches to attention-base neural machine translation. 08 2015, doi: 18.18663/v 1/D35-11/
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In 161 1.08402, 2016.
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 AAAI Conference on Artificial Intelligence, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In In Proceedings of The 33rd International Conference on Machine Learning, 2016.
Yu Pan, HyungJeong Yang, Pinar Duygulu, and Christos Faloutsos. Automatic multimedia cross-modal correlation discovery. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014.
Ryan Rossi, Nesreen K. Ahmed, and Eunyee Koh. Higher-order network representation learning- In WWW Web Conference, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93, 2008.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22:888-9998 905, 2000.
A. Sperduti, A. andStarita. Trans. neur. netw. Supervised neural networks for the classification of structures., 8:714-735, 1997.
Hanghang Tong, Christos Faloutsos, and Jia-Yt Yu Pan. Fast random walk with restart and its applica- tions. In Proceedings the Sixth International Conference Data Mining, 2006.
11

---

Published as a conference paper at ICLR 2020
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2017.
Jason Weston, Frederic Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding, Neural Networks: Tricks of the Trade, pp. 639-655, 2012.
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. In Proceedings of the 32 nd International Conference on Machine Learning, 2015.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning. 2016.
Jiawei Zhang and Lin Meng. Gresnet: Graph residual network for reviving deep GNNs from sus- pended animation. In arXiv.org. 2019.
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference Machine learning, 2003.
12


Reviews:
[{"review_id": "HkxhtAD6KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---- Problem setting and contribution summary ----\nThe paper considers the problem of graph node classification in a semi-supervised learning setting. When classifying a node, the decision is based on the node’s features, as well as by a weighted combination of its neighbors (where the weights are computed using a learnt attention mechanism). The authors extend upon the recent Graph Attention Networks (GAT) paper by proposing a different way of computing the attention over the neighboring nodes. This new attention mechanism takes into account not just their feature similarity, but also extra structure information, which also enables their method to attend not only over direct neighbors, but also up to k-hop neighbors.\n\n---- Overall opinion ----\nWhile I believe the general idea indeed has merit and empirically shows great promise, I believe the paper in its current state is not ready for publication. However, I believe that a more thorough revision can lead to an a publication with potential impact on the applications side.\n\n---- Pros ----\n1. The paper is easy to read.\n2. I really appreciated the good visualizations (Figures 2,3,4) that indeed help in understanding the method.\n3. Really good empirical results on the 3 datasets that were presented.\n\n---- Major issues ----\n1. Motivation:  \nI believe the paper is not well motivated from an applications perspective. In section 2.1., the authors did a good job explaining the limitations of current approaches on a generic graph structure, but this is only under the main assumption that a node should attend more to neighbors in its denser community than other neighbors that not connected so strongly (Fig 1). The issue that I have with this is that:\n      a) Why should we take this assumption for granted? What are some concrete practical node classification problems where it is indeed better if a node attends to its neighbors in this way (as opposed to the GAT approach)?\n      b) Even if the above is proven true, suppose node A in Fig. 1(a) attends with equal weights to all its 4 neighbors. That means node C (which is outside its densest community) gets 1/4, while the nodes inside the dense community get a total of ¾. That means node A puts most of its attention to the dense community anyway. In what conditions is it necessary to bias this attention even further?\n\n2. Experiments: \nWhile the reported accuracies for the three datasets look good and also the authors have provided a link to their code (great to see that!), I believe the experimental section is missing an important amount of details for reproducibility purposes and also for explaining how certain parameters have been chosen:\n    a) There are no details on the model size and training procedure (hidden units, optimizer, learning rate schedule). \n    b) Maybe I am missing this, but I don’t see any reference on what alpha and beta from equation (6) were used in the experiments. \n    c) What is the value of k in Table 2? How did you choose it? I believe Figure 5 shows test accuracies for different k, but I hope the authors did not choose k based on the test set performance. \n    d) How did you select the structural fingerprint to be 3?\n     e) “...optimizing c through the learning process also gives very similar choice” → how did you optimize c exactly?\n     f) Fig 5 a) Why does increasing the number of hops to 3 or 4 decrease the performance so much? Shouldn’t the attention weights learn to ignore the further neighbors, if they are not useful?  \n\n\tAnother important question regarding experiments: since the ablation study shows that the optimal neighbor range is actually 2, a natural baseline to compare with would be something similar to GAT, where an attention weight is applied to all neighbors within two hops (basically skip the fingerprint step, and assume s_{ij} is 1 for all neighbors within 2 hops, and 0 otherwise).\n\n\tAlso regarding experiments, these 3 datasets, although common across many recent graph node classification papers, they are known to be quite limited (small in size and not very representative of real world). Since GAT is your main competitor, why not also show experiments on the PPI dataset they also test?\n\n3. Writing quality: \nWhile the language is clear and easy to follow, there are many grammatical mistakes throughout the paper (e.g. “benefitial”, subject-verb agreement).\n\n---- More minor issues ----\n    a) Section 2.1: One could argue that GAT also contains longer range node dependencies through the node embeddings it learns. Since the node embeddings is trained through gradient descent, and at each iteration the embedding of a node changes according to its neighbors, you could say that information does get propagated from the neighbor’s neighbors.\n     b) Why do you need a LeakyRelu in Equation (5) ? Also, aren’t e_{ij} non-negative anyway (in which case LeakyRelu doesn’t change anything)?\n     c) Why would a Sigmoid be a good choice for alpha and beta in Eq. (6)?\n     d) Section 3: A bag of words is typically represented as a binary vector, which is also categorical.\n     e) Please use \\citet when specifically referring to the authors of a paper as part of your sentence (e.g. “Following Velickovic et. al., 2017 we….” as opposed to “Following (Velickovic et al., 2017), we....”).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HklUNY5Htr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends the idea of self-attention in graph NNs, which is typically based on feature similarity between nodes, to include also structural similarity. This is done by computing for each node a value for each other node within its receptive field, calculated based on some distance metric from the node (either a Gaussian decay profile, or a learned weighting of number of hops distance, of based on fixed point of a random walk with restart). When evaluating the attention between two nodes, a function that compares the structural values between the two nodes (based on Jacard similarity) gives a score to the two nodes, which is further used for calculating the attention weight between them.\n\nI found the idea to be elegant and well-explained, and overall the paper is well-written. \nUsing the structural similarity makes a lot of sense, and the proposed method is both easy to implement, and flexible — the structural similarity profile can be learned, which seems important for getting this idea to work in practice.\n\nI wonder what happens if one uses only the structural similarity for the attention (without the feature similarity). Are there datasets where this would be sufficient? Even a toy task which is constructed such that the structure is more informative than the features could be a nice way to further demonstrate the idea of the paper.\n\nThe experiments show a clear yet small advantage to the proposed method over the conventional attention method (GAT).\n\nOverall, this seems to be a solid contribution (even if the empirical results are a bit incremental) and I recommend acceptance.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1eSNZHrKr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work suggests a graph structure based methodology to augment the attention mechanism of graph neural networks.\n\nThe main idea is to explore the interaction  between different types of nodes of the local neighborhood of a root node. One component of this \"fingerprinting\" is a node weighting (closeness) that is computed using various methods proposed in the paper. The fingerprint is the vector of weights of all nodes in the local neighborhood. \n\nFor computing a closeness metric, the paper suggests random walks with restart, which has generally been used for graph clustering. Once the relative closeness to a node in the neighborhood is measured, the symmetric \"structural interaction\" between the fingerprint of two nodes is given by the Jaccard similarity of their structural fingerprints (or a smooth alternative thereof).  This structural similarity will be then considered in a (multi-head) attention mechanism using learned transfer functions.\n\nThe efficacy of the proposed method is tested on the Cora, Citeseer and Pubmed node classification benchmarks and compares favorably to non-augmented graph neural networks, beating all baselines on those datasets. Also the results in the paper beat those of the GResNet on Cora, but not on PubMed and , which is a recent paper not cited by this work.\n\nIn general this work goes into the direction of adding hand-engineered features to DeepLearning approaches. I am not a big fan of these methods, especially without significant theoratical justification. The approach is well motivated but very heuristical. Still the results presents a significant improvement of SOTA on those benchmark and the paper presents ideas  that seem to be generally useful for processing large-scale, structure-rich graph date. Hence I am in the favor of acceptance of this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is consistently supported by all three reviewers during initial review and discussions. Thus an accept is recommended.
Decision: Accept (Poster)