Walk-Steered Convolution for Graph Classification

Abstract

Graph classification is a fundamental but challenging issue for numerous real-world applications. Despite recent great progress in image/video classification, convolutional neural networks (CNNs) cannot yet cater to graphs well because of graphical non-Euclidean topology. In this work, we propose a walk-steered convolutional (WSC) network to assemble the essential success of standard convolutional neural networks as well as the powerful representation ability of random walk. Instead of deterministic neighbor searching used in previous graphical CNNs, we construct multi-scale walk fields (a.k.a. local receptive fields) with random walk paths to depict subgraph structures and advocate graph scalability. To express the internal variations of a walk field, Gaussian mixture models are introduced to encode principal components of walk paths therein. As an analogy to a standard convolution kernel on image, Gaussian models implicitly coordinate those unordered vertices/nodes and edges in a local receptive field after projecting to the gradient space of Gaussian parameters. We further stack graph coarsening upon Gaussian encoding by using dynamic clustering, such that high-level semantics of graph can be well learned like the conventional pooling on image. The experimental results on several public datasets demonstrate the superiority of our proposed WSC method over many state-of-the-arts for graph classification.

arXiv comment13 pages, 6 figures, 3 tables

References in corpus (11)

• DeepWalk: Online Learning of Social Representations
• Spectral Networks and Locally Connected Networks on Graphs
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Deep Convolutional Networks on Graph-Structured Data
• Biological network comparison using graphlet degree distribution
• Diffusion-Convolutional Neural Networks
• Robust Spatial Filtering with Graph Convolutional Neural Networks
• Learning Graph Representations with Embedding Propagation
• Shift Aggregate Extract Networks
• Feature-Based Classification of Networks
• Dynamics Based Features For Graph Classification

Cited by in corpus (3)

• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
• Context-Dependent Diffusion Network for Visual Relationship Detection
• MathNet: Haar-Like Wavelet Multiresolution-Analysis for Graph Representation and Learning