using triangles (as defined by three nodes) in GCN?

[errhernandez]

Let me state at the onset that I am a newbie taking my first steps in graph NNs and with relatively little experience thus far, so maybe this is a trivial question, and if so, I apologise.

I'd be interested to know if there is any experience in the community in working with graphs in which triangles, as well as nodes and edges, are used as graph features (triangle as defined by a node and two of its neighbours). This is hinted at at several points in the documentation, but I have not been able to find examples of this. In particular, I have in mind a regression problem in which such features could play a significant role in predicting a graph global feature. I'd be grateful for any pointers as to examples or previous experience on this.

Cheers!

[rusty1s]

The standard message passing formulation only includes message passing over edges. If you want to incorporate triangle features, you should look into graph convolution on hyper-graphs, in which you can define edges that point to more than just a pair of nodes. We provide (currently limited) support for hypergraphs in the HyperGraphConv operator, and creating the incidence matrix of hypergraphs is still the task of the users. Happy to chat more about it, but I currently cannot point you to an example of this in PyG.

[errhernandez]

Thanks for the hint; I will look into HyperGraphConv.

[errhernandez]

Dear Matthias,

First and foremost, happy new year. Second, and following up from our earlier exchange above: I have considered using HypergraphConv for my application; certainly the idea of hyper graphs seems very powerful, but I think it is not quite
adequate in its present form for the kind of applications I have in mind. I have some ideas on how to extend/modify the concept, and I am toying with the idea of implementing these and trying them out in PyG, but to be honest, I am not sure if I have the expertise to implement these in PyG (though I will try). Would you be interested in discussing these ideas and perhaps establish a collaboration in their implementation, if you think they are interesting enough?

[rusty1s]

I don't think I will have time for an in-depth collaboration, but please feel free to use this thread for any questions that may arise. Happy to discuss them with you :)

[errhernandez]

Of course. Well, let me explain what I would like to do, and if you have any comments or suggestions, they would be most welcome. In my problem as well as features, nodes have assigned Cartesian positions so it makes sense to consider Euclidean distance between nodes, or angles between edges, etc. What I would like to do is something as follows:

1. the hyper-graph object would be defined with reference to a standard undirected graph, where each edge of the graph would correspond to a hyper-edge in the hyper-graph.
2. a hyper-edge would have two main nodes (those defining the corresponding edge in the reference graph), plus the possible participation of near-by nodes, in a sense to be defined below.
3. hyper-edges will have their own features.
4. The incidence matrix will have entries of 1 for the main nodes, and real entries in the range [0,1] for other nodes as given by some decaying function of the distance between node and the centre of the edge between the main nodes. In other words, incidence will be lower (eventually decaying to 0) for nodes that are further away from the centre of the hyper-edge.

That is the general idea. Convolution on the hyper-graph would result in node embeddings that will be influenced by the hyper-edge features as well as by those of near-by nodes, with those further away having a smaller weight.

I think that I can implement this scheme relatively easily, but first, having not much experience in graph NNs and none in hyper-graph NNs, I would welcome any feedback you may have on the soundness of what I'm proposing, so any comments/questions you can think of would be very welcome.

Thanks.

[rusty1s]

Sorry for the late reply. I was mostly offline the last few days.

If I understand you correctly, you have a standard undirected graph, and want to lift that into the hypergraph setting in which nearby nodes are added to the hyper edge (based on distance to source and target nodes). This is an interesting idea.

My main question is as follows:

How is the graph defined in the first-place? Is it based on nearest neighbor? If your graph already encodes spatial distances between nodes, what information do you gain in the hypergraph scenario which you cannot obtain from multiple rounds of message passing on the original graph?

[errhernandez]

Hello again,

No problem about the timing of your reply, I quite understand and I'm grateful for your interest. You understood the idea, and your question is very pertinent. I think that there are alternative ways in which the problem I have at hand can be tackled, for example with CG_CONV, which is what I have done already. However CG_CONV only considers pairwise relationships, while experience shows that in my problem (in the context of chemical physics) nodes (atoms) as well as edges (chemical bonds) are sensitive to local environment. This is the reason why I started thinking about a hyper graph setting, because to my mind it is a nice way of accounting for the local environment of each node and edge. As far as I know this hasn't been tried before in the context that I am working in.

I read carefully your implementation of HYPERGRAPH_CONV and the paper describing it, and I came to the conclusion that it is not exactly what I need, but it was very instructive reading. I think what I need is something similar, but not quite the same, because I do need to take into account edge attributes. However, I do agree that one can work with a standard graph setting provided one uses appropriately designed node and edge features.

Well, if you are still interested after reading this, we can discuss further, but I perfectly understand if you consider this the end of the line. I will give it a try with hyper graphs and see how far I get, but given my as yet little experience with all things AI and (hyper)graph NNs in particular, being able to discuss with you would be a great asset. Thanks!

[rusty1s]

Ah, I think I understand better now. The hypergraph formulation may help you to craft better messages by taking the local environment around edges/nodes into account. Note that technically, this is what a GNN already does in all layers > 1, since node features already capture the local environment.

Nonetheless, I like your idea, and I'm interested to find out if it provides any significant performance gains in practice. Let me know if you have any questions implementing this.

[errhernandez]

Yes, I understand that GNN does this in all layers > 1, but by using a hyper graph description this could potentially be done with fewer layers, if my understanding is correct, because a hyper-edge links a node to several other nodes simultaneously, rather than to just one other node.

I couldn't work on it yet, but the idea I am toying with is implementing a variation of the hypergraph_conv that would read like this:

where D and B have the same meaning as in hypergraph_conv, $\mathcal{H}{i\varepsilon}$ is the (real) incidence matrix element (the weight with which node i participates in hyper-edge $\varepsilon$), and $z{j\varepsilon} = [x_j\mid u_\varepsilon]$, with $u_\varepsilon$ the feature tensor of hyper edge $\varepsilon$.

Do you think this makes sense? Any comments? Sorry! I appreciate I'm taking much of your time. (I was hoping that math form markdown would work here; it appears not to)

[rusty1s]

Yes, this looks good to me. One can always think about encoding spatial relations more elegantly than simply using distances, e.g., in a more sophisticated way as in the DimeNet paper, but otherwise, this should be a great starting point.