Graph Classification using Structural Attention

By John Boaz Lee, Ryan A. Rossi, Xiangnan Kong. Knowledge Discovery and Data Mining, 2018

323 citations recorded by the source corpus.

Graph classification is a problem with practical applications in many different domains. To solve this problem, one usually calculates certain graph statistics (i.e., graph features) that help discriminate between graphs of different classes. When calculating such features, most existing approaches process the entire graph. In a graphlet-based approach, for instance, the entire graph is processed to get the total count of different graphlets or subgraphs. In many real-world applications, however, graphs can be noisy with discriminative patterns confined to certain regions in the graph only. In this work, we study the problem of attention-based graph classification. The use of attention allows us to focus on small but informative parts of the graph, avoiding noise in the rest of the graph. We present a novel RNN model, called the Graph Attention Model (GAM), that processes only a portion of the graph by adaptively selecting a sequence of "informative" nodes. Experimental results on multiple real-world datasets show that the proposed method is competitive against various well-known methods in graph classification even though our method is limited to only a portion of the graph.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/59d502851cd20f28af03eef1d15dc83d3a7bb300

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Materials Chemistry

Citations in the corpus

Attention Models in Graphs (2018, methodology): “In particular, the main advantages of using attention on graphs can be summarized as follows: (1) Attention allows the model to avoid or ignore noisy parts of the graph, thus improving the signal-to-noise (SNR) ratio [Lee et al. 2018; Mnih et al. 2014].”
Graph Learning: A Survey (2021, methodology): “Some other models such as graph attention model (GAM) were proposed for solving different problems [145].”
A Comprehensive Survey on Graph Neural Networks (2019, background): “There are other graph attention models which might be of interest [88], [89].”
GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks (2020, background): “Graph Attention Model (GAM) [14] processes only a portion of the graph by adaptively selecting a sequence of ”informative” nodes and is equipped with an external memory component, which allows it to integrate the information gathered from different parts of the graph.”
Deep Learning on Graphs: A Survey (2018, unknown): “GAM [119] applied RL to graph classification by using random walks.”
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, methodology): “[24] uses an attention-guided walk to find the most relevant parts for graph classification.”
Understanding Attention and Generalization in Graph Neural Networks (2019, background): “In graph neural networks (GNNs), attention can be deﬁned over edges [4, 5] or over nodes [6].”
Robust Graph Representation Learning via Neural Sparsification (2020, background): “…ﬁlters in the graph domain are proposed (Simonovsky & Komodakis, 2017; Niepert et al., 2016; Kipf & Welling, 2017; Veli ˇ ckovi ´ c et al., 2018; Xu et al., 2018), and a few studies (Hamilton et al., 2017; Lee et al., 2018) explore how to differentiate neighborhood ﬁltering by sequential models.”
Graph convolutional networks: a comprehensive review (2019, background): “Note that in the past few years, many other types of graph neural networks have been proposed, including (but are not limited to): (1) graph auto-encoder [21], (2) graph generative model [22, 23], (3) graph attention model [24, 25], and (4) graph recurrent neural networks [26, 27].”
Relational Pooling for Graph Representations (2019, background): “…et al., 2017; Bruna et al., 2013; Niepert et al., 2016; Defferrard et al., 2016; Du-venaud et al., 2015; Atwood & Towsley, 2016; Kipf & Welling, 2016; Hamilton et al., 2017a; Lee et al., 2018; Velickovic et al., 2017; Monti et al., 2017; Meng et al., 2018; Xu et al., 2018; Scarselli et al., 2009).”