DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph
  Classification
  Graph data widely exist in many high-impact applications. Inspired by the
success of deep learning in grid-structured data, graph neural network models
have been proposed to learn powerful node-level or graph-level representation.
However, most of the existing graph neural networks suffer from the following
limitations: (1) there is limited analysis regarding the graph convolution
properties, such as seed-oriented, degree-aware and order-free; (2) the node's
degree-specific graph structure is not explicitly expressed in graph
convolution for distinguishing structure-aware node neighborhoods; (3) the
theoretical explanation regarding the graph-level pooling schemes is unclear.
  To address these problems, we propose a generic degree-specific graph neural
network named DEMO-Net motivated by Weisfeiler-Lehman graph isomorphism test
that recursively identifies 1-hop neighborhood structures. In order to
explicitly capture the graph topology integrated with node attributes, we argue
that graph convolution should have three properties: seed-oriented,
degree-aware, order-free. To this end, we propose multi-task graph convolution
where each task represents node representation learning for nodes with a
specific degree value, thus leading to preserving the degree-specific graph
structure. In particular, we design two multi-task learning methods:
degree-specific weight and hashing functions for graph convolution. In
addition, we propose a novel graph-level pooling/readout scheme for learning
graph representation provably lying in a degree-specific Hilbert kernel space.
The experimental results on several node and graph classification benchmark
data sets demonstrate the effectiveness and efficiency of our proposed DEMO-Net
over state-of-the-art graph neural network models.
