Many real-world data sets are represented as graphs, such as citation links, social media, and biological interaction. The volatile graph structure makes it non-trivial to employ convolutional neural networks (CNN's) for graph data processing. Recently, graph attention network (GAT) has proven a promising attempt by combining graph neural networks with attention mechanism, so as to achieve massage passing in graphs with arbitrary structures. However, the attention in GAT is computed mainly based on the similarity between the node content, while the structures of the graph remains largely unemployed (except in masking the attention out of one-hop neighbors). In this paper, we propose an `````````````````````````````"ADaptive Structural Fingerprint" (ADSF) model to fully exploit both topological details of the graph and  content features of the nodes. 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 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.   Encouraging performance is observed on a number of benchmark data sets in node classification. Many real-world data set are represented naturally as graphs. For example, citation networks specify 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 as protein-protein-interaction (PPI). In these scenarios, the complex structures such as the graph topology or connectivities encode crucial domain-specific knowledge for the learning and prediction tasks. Examples include node embedding or classification, graph classification, and so on. The complexity of graph-structured 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 to accommodate local structure changes (LeCun & Kavukcuoglu, 2010) . More recently, CNN was used in natural language processing where the words of a sentence can be considered as a uniform chain, and showed great power in extracting useful semantic features (Kim, 2014) . However, extending CNN to deal with arbitrary structured graphs beyond uniform grids or chains can be quite non-trivial. To solve this problem, graph neural networks (GNN) were early proposed by Gori et al. (2005) and Sperduti (1997) , which adopt an iterative process and propagate the state of each node, followed by a neural network module to generate the output of each node, until an equilibrium state is reached. Recent development of GNN can be categorized into spectral and nonspectral approaches. Spectral approaches employ the tools in signal processing and transform the convolutional operation in the graph domain to much simpler operations 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 et al., 2016; Kipf & Welling, 2017) . Non-spectral approaches define convolutions directly on the graph within spatially close nodes. As a result, varying node structures have to be accommodated through various processing steps such as fixed-neighborhood size sampling (Hamilton et al., 2017) , neighborhood normalization (Niepert et al., 2016) , and learning a weight matrix for each node degree (Duvenaud et al., 2015) or neighborhood size (Hamilton et al., 2017) . More recently, the highway connection in residual network is further introduced in graph neural networks to improve the performance on graph data processing (Zhang & Meng, 2019) . Recently, graph attention network (GAT) proves a promising framework by combining graph neural networks with attention mechanism in handling graphs with arbitrary structures (Velickovic et al., 2017) . The attention mechanism allows dealing with variable sized input while focusing on the most relevant parts, and has been widely used in sequence modelling (Bahdanau et al., 2015; Devlin et al., 2019; Vaswani et al., 2017) , machine translation (Luong et 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 based on a self-attention strategy. State-of-theart performance has been obtained on tasks of node embedding and classification. The attention in GAT is computed mainly based on the content of the nodes; the structures of the graph, on the other hand, are simply used to mask the attention, e.g., only one-hop neighbors will be attended. However, we believe that rich structural information such as the topology or "shapes" of local edge connections should provide a more valuable guidance on learning node representations. For example, in social networks or biological networks, a community or pathway is oftentimes composed of nodes that are densely inter-connected with each other but several hops away. Therefore, it can be quite beneficial if a node can attend high-order neighbors from the same community, even if 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, we propose a new model called "adaptive structural fingerprints". The key idea is to contextualize each node within a 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". We then define interactions between two structural fingerprints, which will be used in conjunction with node feature similarities to compute a final 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. The rest of the paper is organized as follows. In Section 2, we introduce the proposed method, including limitation of content-based graph attention, construction of the adaptive structural fingerprints, and the whole algorithm workflow. In Section 3, we discuss related work. Section 4 reports empirical evaluations and the last section concludes the paper. In this work, we proposed an adaptive structural fingerprint model to encode complex topological and structural information of the graph to improve learning hidden representations of the nodes through attention. There are a number of interesting future directions. First, we will consider varying fingerprint parameters (such as decay profile) instead of sharing them across all the nodes; second, we will also consider applying the structural fingerprints in problems of graph partitioning and community detection, where node features might be unavailable and graph structures will be the main information for decisions; third, we will extend our approach to challenging problems of graph-level classification where node-types shall be taken into account in constructing structural fingerprint; finally, on the theoretical side, we will borrow existing tools in semi-supervised learning and study the generalization performance of our approach on semi-supervised node embedding and classification. Figure 7 : Performance of GAT (percent accuracy) for different neighborhood sizes.
Exploiting rich strucural details in graph-structued data via adaptive "strucutral fingerprints'' A graph structure based methodology to augment the attention mechanism of graph neural networks, with the main idea to explore interactions between different types of nodes of the local neighborhood of a root node. This paper extends the idea of self-attention in graph NNs, which is typically based on feature similarity between nodes, to include structural similarity.