Graph Substructure Assembling Network with Soft Sequence and Context Attention

There has been a surge of researchers' interest in building predictive models over graphs. However, the overwhelming complexity of graph space often makes it challenging to extract interpretable and discriminative structural features for graph classification. In this work, we propose a new graph neural network model called Substructure Assembling Network (SAN) to learn graph representations for classification. The key innovation is a unified Substructure Assembling Unit (SAU), which is a variant of Recurrent Neural Network (RNN) designed to hierarchically assemble useful pieces of graph components so as to fabricate discriminative substructures. A key challenge is that SAUs need to process the neighbors of a node sequentially while no natural order is defined therein. SAN tries to make the model insensitive to neighborhood orders by randomly shuffling neighborhood sequences in training. However, this could suffer high variance, especially when the neighborhood size is large. Hence, we further propose to equip SAN with a novel module named Soft Sequence with Context Attention (SSCA). SAN-SSCA employs the proposed context attention technique to learn the best "soft" permutation of the neighbors w.r.t. classification. It helps the model achieve higher accuracy as well as lower variance. Experiments confirm the effectiveness of SAN-SSCA.