really

If the problem is that the graph is not sparse enough / not a graph at all, adding more connections doesn't help.

edit: Why doesn't it help? They address this in the paper. There is computational infeasiability problem. The transformer decoder can't be a regular graph if you include masking.

Not necessarily. That is what this paper is about. From what I understand, they also consider graph attention networks.

1. The O(N^2*d) computation cost of the attention layers. For large graphs (millions of nodes) it's quickly too costly. And in some of the social network problems, the more data you feed the better is the inference on average (on a ~log scale).

2. As the paper suggests, in some cases the graph structure has important information. Flattening out everything, or fully connecting the nodes, a more accurate description of what goes on in an attention layer in this scenario, the structure is lost. The structure information can be introduced as a positional encoding -- I read in some paper a while back, I think in here: https://arxiv.org/pdf/2012.09699.pdf So remember to do that if you attempt the attention solution.

3. Then there is overfitting, already a big issue in GNNs. Fully connecting every node with attention has less of an "inductive bias" if you will, created by the graph structure. Not sure how much it matters ...