Learning Graph Representations with Maximal Cliques

Abstract

Non-Euclidean property of graph structures has faced interesting challenges when deep learning methods are applied. Graph convolutional networks can be regarded as one of the successful approaches to classification tasks on graph data, although the structure of this approach limits its performance. In this work, a novel representation learning approach is introduced based on spectral convolutions on graph-structured data in a semi-supervised learning setting. Our proposed method, COOL (COnvOlving cLiques), is constructed as a neighborhood aggregation approach for learning node representations using established graph convolutional network architectures. This approach relies on aggregating local information by finding maximal cliques. Unlike the existing graph neural networks which follow a traditional neighborhood averaging scheme, COOL allows for an aggregation of densely connected neighboring nodes of potentially differing locality. This leads to substantial improvements on multiple transductive node classification tasks.