Publications

Graph Classification using Structural Attention

KDD

Published January 1, 2018

John Boaz Lee, Ryan A. Rossi, Xiangnan Kong

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. The model is equipped with an external memory component which allows it to integrate information gathered from different parts of the graph. Experimental results on multiple real-world datasets show that the proposed method is competitive against various well-known methods in the graph classification task even though these methods have access to the entire graph whereas we limit our method to only a portion of the graph.


Research Area:  AI & Machine Learning