Diffusion Convolutional Neural Network (DCNN)

A Diffusion Convolutional Neural Network (DCNN) is a Spatial Graph Convolutional Network that regards graph convolutions as a diffusion process.

• Context:
  • It was first introduced by Atwood & Towsley (2016).
• Example(s):
  • …
• Counter-Example(s):
  • a PATCHY-SAN,
  • a Message Passing Neural Network ,
  • a GraphSage,
  • a Learnable Graph Convolutional Network,
  • a Spectral Graph Convolutional Network,
  • a Graph Attention Network (GAT),
  • a Graph Recurrent Network (GRN),
  • a Graph Wavelet Neural Network (GWNN).
• See: Recurrent Neural Network, Feedforward Neural Network, Attention Mechanism.

---

---

References

2020a

• (Wu et al., 2020) ⇒ Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu (2020). "A Comprehensive Survey on Graph Neural Networks". In: IEEE transactions on neural networks and learning systems, 32(1), 4-24.
  • QUOTE: Diffusion Convolutional Neural Network (DCNN, Atwood & Towsley, 2016) regards graph convolutions as a diffusion process. It assumes information is transferred from one node to one of its neighboring nodes with a certain transition probability so that information distribution can reach equilibrium after several rounds. DCNN defines the diffusion graph convolution as

$\mathbf{H}^{(k)} = f\left(\mathbf{W}^{(k)}\odot \mathbf{P}^k\mathbf{X}\right)$,

(17)

where $f(\cdot)$ is an activation function and the probability transition matrix $\mathbf{P} \in \R^{n\times n}$ is computed by $\mathbf{P = D^{−1}A}$.

2020b

• (Zhou et al., 2020) ⇒ Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun (2020). "Graph neural networks: A review of methods and applications". AI Open, 1, 57-81.
  • QUOTE: DCNN. The diffusion convolutional neural network (DCNN) (Atwood and Towsley, 2016) uses transition matrices to define the neighborhood for nodes. For node classification, the diffusion representations of each node in the graph can be expressed as:

$\mathbf{H}= f\left(\mathbf{W}^{c}\odot \mathbf{P^*X}\right)\in \R^{N\times K \times F}$,

(10)

where $\mathbf{X}\in \R^{N\times F}$ is the matrix of input features ($F$ is the dimension). $\mathbf{P^*}$ is an tensor which contains the power series $\{\mathbf{P},\mathbf{P^2}, \ldots,\mathbf{P}^K \}$ of matrix $\mathbf{P}$. And $\mathbf{P}$ is the degree-normalized transition matrix from the graphs adjacency matrix $\mathbf{A}$. Each entity is transformed to a diffusion convolutional representation which is a $K \times F$ matrix defined by $K$ hops of graph diffusion over $F$ features. And then it will be defined by a weight matrix and a non-linear activation function $f$.

2016

• (Atwood & Towsley, 2016) ⇒ James Atwood, and Don Towsley (2016). "Diffusion-Convolutional Neural Networks". In: Proceedings of Advances in Neural Information Processing Systems 29 (NIPS 2016).
  • QUOTE: We present diffusion-convolutional neural networks (DCNNs), a new model for graph-structured data. Through the introduction of a diffusion-convolution operation, we show how diffusion-based representations can be learned from graph-structured data and used as an effective basis for node classification.

---