Learning the graph structure ?

[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?

[dongkwan-kim]

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?

The first thing that comes to mind is using a k-nn graph. (https://pytorch-geometric.readthedocs.io/en/latest/modules/transforms.html#torch_geometric.transforms.KNNGraph) However, this method may produce suboptimal edges, and SuperGAT does not fundamentally correct them. Would you like to take a look at the papers below?

• https://arxiv.org/abs/2102.05034
• http://proceedings.mlr.press/v97/franceschi19a.html
• https://arxiv.org/abs/2005.10203

I am very new to GAT.... But do GAT normally requires the edges of the graph in computing the attention?

Yes. Many GNN models, as well as GATs, require edges. The case where there is no edge in the graph seems to be a special case. It would be good to look for set representation learning.

Will GAT work better if it considers all the possible pairs of edges or a restricted set of edges?

If you apply the GAT for all possible pairs of edges (|V|x|V|), mathematically this is equivalent to the Transformer. See https://graphdeeplearning.github.io/post/transformers-are-gnns/

In general, it is difficult to answer which one will do better. I first need to see datasets and understand actual use cases.

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?

SuperGAT doesn't seem appropriate for a graph that considers all |V|x|V| edge spaces. In this case, negative sampling, a key design in SuperGAT, might not be well defined (this is also described in the paper). If you give a little more context about your application, I can be of more help.

[GabbySuwichaya]

Thank so much for this wealth of information.

In general, it is difficult to answer which one will do better. I first need to see datasets and understand actual use cases.

I am trying methods that the corresponding keypoints in two images. Similar methods are such as (a) Superglue: learning feature matching with graph neural networks and (b) LoFTR: Detector-Free Local Feature Matching with Transformers....
I guess for these applications, the negative edges are the same as the edges that should not be matched.

When I looked carefully, I found that these two methods do not really focus on the edges of the GAT (the graph structure is not used), as you mentioned their design seems to be based on using a transformer where GAT is used to compute attention.

.. Could you advise what is the main difference between Transformer and GAT, especially why the GAT normally needs the edges and why the transformer can work without the edges?
(If this question sounds really fundamental I am so sorry. I would like to understand better....)

[dongkwan-kim]

I am trying methods that the corresponding keypoints in two images. Similar methods are such as (a) Superglue: learning feature matching with graph neural networks and (b) LoFTR: Detector-Free Local Feature Matching with Transformers....
I guess for these applications, the negative edges are the same as the edges that should not be matched.

I just skimmed two papers. Both the problem and models are interesting but note that I am not familiar with them. Using SuperGAT to cross attention between images makes sense, but I think there should be a rigorous study about negative sampling. Looking at Figure 4 of SuperGlue, it can be seen that keypoint matching is affected not only by the one point but also by several points around them. How to properly exclude them, that is how to extract negative edges, is not straightforward.

.. Could you advise what is the main difference between Transformer and GAT, especially why the GAT normally needs the edges and why the transformer can work without the edges?

I think that the link I posted above has already explained well. The point is that Transformers use the fully connected edges between entities, thus you can use them to no-edge-graphs. Next question is, why GATs compute attention over edges only? That is because leveraging edges usually gives more information to models. A further assumption that GATs have against Transformers is that message-passing is more useful when you use entities connected by edges rather than all entities.

[GabbySuwichaya]

You have given me lots of understanding..... Thanks so much. Yes, I think so that the negative edges in those works are not well extracted or interpreted...

I will close the issue. It has always been great to learn from you. :)

[dongkwan-kim]

I am really glad to hear you say so. Thank you for your attention. :)