Diffusion-Convolutional Neural Networks
James Atwood and Don Towsley
College of Information and Computer Science
University of Massachusetts
Amherst, MA, 01003
{jatwood|towsley}@cs.umass.edu
Abstract
We present diffusion-convolutional neural networks (DCNNs), a new model for
graph-structured data. Through the introduction of a diffusion-convolution oper-
ation, we show how diffusion-based representations can be learned from graph-
structured data and used as an effective basis for node classification. DCNNs
have several attractive qualities, including a latent representation for graphical
data that is invariant under isomorphism, as well as polynomial-time prediction
and learning that can be represented as tensor operations and efficiently imple-
mented on the GPU. Through several experiments with real structured datasets, we
demonstrate that DCNNs are able to outperform probabilistic relational models
and kernel-on-graph methods at relational node classification tasks.
1 Introduction
Working with structured data is challenging. On one hand, finding the right way to express and
exploit structure in data can lead to improvements in predictive performance; on the other, finding
such a representation may be difficult, and adding structure to a model can dramatically increase the
complexity of prediction and learning.
The goal of this work is to design a flexible model for a general class of structured data that offers
improvements in predictive performance while avoiding an increase in complexity. To accomplish
this, we extend convolutional neural networks (CNNs) to general graph-structured data by introducing
a ‘diffusion-convolution’ operation. Briefly, rather than scanning a ‘square’ of parameters across a
grid-structured input like the standard convolution operation, the diffusion-convolution operation
builds a latent representation by scanning a diffusion process across each node in a graph-structured
input.
This model is motivated by the idea that a representation that encapsulates graph diffusion can provide
a better basis for prediction than a graph itself. Graph diffusion can be represented as a matrix power
series, providing a straightforward mechanism for including contextual information about entities
that can be computed in polynomial time and efficiently implemented on the GPU.
In this paper, we present diffusion-convolutional neural networks (DCNNs) and explore their per-
formance at various classification tasks on graphical data. Many techniques include structural infor-
mation in classification tasks, such as probabilistic relational models and kernel methods; DCNNs
offer a complementary approach that provides a significant improvement in predictive performance at
node classification tasks.
As a model class, DCNNs offer several advantages:
• Accuracy:
In our experiments, DCNNs significantly outperform alternative methods for
node classification tasks and offer comparable performance to baseline methods for graph
classification tasks.
29th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.
arXiv:1511.02136v6 [cs.LG] 8 Jul 2016