1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ I think what you are referring is graph attention network arxiv.org/pdf/1710.10903.pdf $\endgroup$ Sep 3 at 18:48
  • $\begingroup$ "If two nodes have similar time-series then the weight of the edge between them should be ~ 1 right?" I am not sure about what you are referring here, why it should be 1? Normally the adjacency matrix is already given to you. $\endgroup$ Sep 3 at 18:51
  • $\begingroup$ "If the convolution is performed based on my current weights, will this be incorporated into the learning?" Convolution is not performed on the current weights(assuming vanilla GCN), node features are updated. $\endgroup$ Sep 3 at 18:53
  • $\begingroup$ @SwaksharDeb Thanks for that link. I hope to see more of these fundamental questions! $\endgroup$
    – DukeZhou
    Sep 4 at 6:37
  • $\begingroup$ @SwaksharDeb thanks so much. GAT seems like something I could be interested in too. Maybe I'm not clear with my question. Adjacency matrix with 1's simply denote a connection between two nodes. To model the strength of this connection between nodes could we use a number other than [1] to connect two nodes? $\endgroup$
    – richieeDS
    Sep 4 at 8:47
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

enter image description here

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.

enter image description here

In the aforementioned figure, color coding indicates attention weight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.