Can I extend Graph Convolutional Networks to graphs with weighted edges?

Question

I'm researching spatio-temporal forecasting utilising GCN as a side project, and I am wondering if I can extend it by using a graph with weighted edges instead of a simple adjacency matrix with 1's and 0's denoting connections between nodes.

I've simply created a similarity measure and have replaced the 1's and 0's in the adjacency with it.

For example, let's take this adjacency matrix

$$A= \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} $$

It would be replaced with the following weighted adjacency matrix

$$ A'= \begin{bmatrix} 0 & 0.8 & 0 \\ 0.8 & 0 & 0.3 \\ 0 & 0.3 & 0 \end{bmatrix} $$

As I am new to graph NN's, I am wondering whether my intuition checks out. If two nodes have similar time-series, then the weight of the edge between them should be approximately 1, right? If the convolution is performed based on my current weights, will this be incorporated into the learning?

Answer 1

According to the definition of Graph Neural Networks taken from here GCN perfroms an operation of the form: $$ f (H^{(l)} ,A) = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)}) $$ Where $H^{(l)}$ is the input to GCN layer, $\tilde{A} = A + I$ is the adjacency matrix with self loops added and $\tilde{D}$ is a degree matrix, corresponding to the adjacency matrix $\tilde{A}$ (on the diagonals there are sums over the columns of $\tilde{A}$).

This definition is for matrix with $1$, if there is an edge between $i$ and $j$, and $0$ otherwise. For matrix of this form normalized Graph Laplacian $\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ is guaranteed to be positive semidefinite matrix.

One can extend the definition for arbitrary values of $a_{ij} \in A$. But there won't be guarantees, that graph Laplacian will be well-defined.

Answer 2

Graph attention network(GAN) exactly perform the same thing you are referring to . In chebnet, graphsage we have a fixed adjacency matrix that is given to us. Now, in GAN the authors try to learn the adjacency matrix via self-attention mechanism.

Graph Attention Network:

Let, $K$ be the number of attention heads, $h^{l+1}_i$ is the feature vector of node $i$ at $l+1$ layer, $e^{l}_{ij}$ is the attention weight between two adjacence node $i$ and $j$ at layer $l$.

Then the update rule for graph attention network is as follows: \begin{align} h^{l+1} &= \text{Concat}_{K=1}^{K}(\text{ELU}(\sum_{j \in \mathcal{N}_i} \underset{\text{scalar}}{e_{ij}^{K,l}} \underset{d \times d}{W_1^{K,l}} \underset{d \times 1}{h_j^l})) \end{align} where the $K$-th head attention weight is defined as:

\begin{align} \underset{\text{scalar}}{e^{K,l}_{ij}} &= \text{Softmax}_{\mathcal{N}_i}(\hat{e}^{K,l}_{ij}) \\ \hat{e}^{K,l}_{ij} &= \text{LeakyRelu}(W_{2}^{K,l} \text{Concat}(W_1^{K,l}h_i^l, W_1^{k,l}h_j^l)) \end{align}

Notice that in GAN we are learning anisotropic filters(treats each direction differently, since attention weight is different for each direaction) which are more powerful than isotropic filters(treat all the directions). For this reason, GAN are more powerful than isotropic graph convolutional network(GCN).

Spatio Temporal GCN(ST-GCN)

In stgcn, we first perform graph convolution(vanilla GCN or GAN) on the spatial domain then apply temporal convolution along the temporal direction. Here is an example of STGCN for human activity recognition here blurred skeleton indicate time axis.

In the aforementioned figure, color coding indicates attention weight.