Learning the graph structure for link prediction

[GabbySuwichaya]

Hi, I am working on the application of classification/link prediction. So, far I have looked at the code such as SuperGAT. I have noticed is that the dataset used in SuperGAT (e.g., Citations) seems to already have the graph structure (the set of edges to be considered in training and testing).

However, in my application, all I have is the data attributes .....without the edges or adjacent matrix or mask to identify which nodes may be connected to which.

My questions are

1. Do you have any recommended way to estimate the edges/adjacent matrix? I am looking for time-efficient methods to solve the problem as well?
2. I am very new to GAT.... But do GAT normally requires the edges of the graph in computing the attention?
3. Will GAT work better if it considers all the possible pairs of edges or a restricted set of edges?
4. I have tried to extend SuperGAT to connect all the possible pairs, but the training results are not so good. So, how other works normally handle the training of all the possible pairs?
5. Also, just to make sure.... is my observation correct ... did I misunderstand anything?

[rusty1s]

Thanks for your interest.

1. In general, a GNN operates on a pre-defined graph-structure. We assume that a graph is given, and learn from features and structures in an end-to-end fashion in order to derive at some predictions. In case you do not have any graph-structure, one can also operate on the fully-connected graph (in that case GAT models a Transformer model). As such, attention scores can be interpreted as learning a soft adjacency matrix per layer. However, keep in mind that this package is more suited towards sparse graph-structured data rather than fully-connected graphs.
2. Yes, GAT computes an attention score per edge.
3. This depends. As mentioned earlier, considering all possible pairs of edges will yield a Transformer model. GAT can be seen as a sparse and local variant of such models.
4. I don't think extending SuperGAT for fully-connected graphs makes a lot of sense, since the link prediction objective can not sample negative node pairs.

[rusty1s]

The fully-connected transformer just attends to all other nodes, i.e., it tries to find nodes that are important for the central node itself to make more accurate predictions. In that sense, the transformer tries to learn a graph structure by itself. I think this is the most reasonable approach to tackle this problem in case you do not have further knowledge about node relationships. However, since the Transformer has to learn everything from scratch (without any inductive bias), it will take longer to train and needs a lot more data.

[GabbySuwichaya]

@rusty1s Thanks so much.... Your explanation does help me a lot. I would like to ask one last question ....
Do people use any positional encoder with GAT? Or they just use it with the transformer due to the lack of knowledge about node relationships?

[rusty1s]

In general, one does not use positional encoding in GAT/GNNs since there is no notion of "position" in (most) graphs. There exists some work on this topic though, see, e.g., here.

[shahinghasemi]

The fully-connected transformer just attends to all other nodes, i.e., it tries to find nodes that are important for the central node itself to make more accurate predictions. In that sense, the transformer tries to learn a graph structure by itself. I think this is the most reasonable approach to tackle this problem in case you do not have further knowledge about node relationships. However, since the Transformer has to learn everything from scratch (without any inductive bias), it will take longer to train and needs a lot more data.

I have the same problem. Does calculating the adjacency matrix using some similarity algorithms e.g. Jaccard or Cosine make sense? Let's say we have a binary feature matrix X of (n, f) then we calculate adj = Jaccard(X) now adj is (n, n) which somehow simulates the relations between pairs of nodes.

[zcaicaros]

The fully-connected transformer just attends to all other nodes, i.e., it tries to find nodes that are important for the central node itself to make more accurate predictions. In that sense, the transformer tries to learn a graph structure by itself. I think this is the most reasonable approach to tackle this problem in case you do not have further knowledge about node relationships. However, since the Transformer has to learn everything from scratch (without any inductive bias), it will take longer to train and needs a lot more data.

I have the same problem. Does calculating the adjacency matrix using some similarity algorithms e.g. Jaccard or Cosine make sense? Let's say we have a binary feature matrix X of (n, f) then we calculate adj = Jaccard(X) now adj is (n, n) which somehow simulates the relations between pairs of nodes.

As mentioned by @rusty1s , I guess the best way is to use the transformer to learn a soft adjacent matrix, such that we can utilize the power of neural nets to explore the whole adj space to find the most suitable one. I guess this will be stronger than a hard-coded one, such as Jaccard or Cosine?

[taghizad3h]

If you have some prior knowledge about the structure of adjacency matrix e.g sparsity, smoothness of input, etc. you can use these unsupervised objectives to learn the initial graph. For more details refer to this paper Exploring Structure-Adaptive Graph Learning for Robust Semi-Supervised Classification.