0
$\begingroup$

I am reading a paper on the K-WL GCN. I did not complete the paper yet but I just skimmed over it. There I am trying to understand the K-WL test (page 3 Weisfeiler-Leman Algorithm). I think my understanding is quite ambiguous, so I looking for an example problem that is solved using K-WL test. But I can't find any of them on the web.

Does anyone have any solved example problem on K-WL or can anyone explain to me how the K-WL test works?

Note: If anyone also explains how K-WL GCN uses the K-WL test, I will be thankful.

$\endgroup$
1
$\begingroup$

I never used a k-WL in practice, but I did apply weisfeiler-lehman for my graph tasks. As you can know, the WL provides the coloring by interactive procedure that's assign each node a 'color' (basically some kind of label reflecting the node neighborhood). Counting colors allows to compare two graphs on isomorphism, but it's not that important here, the key is that you have kind of feature for each node.

The k-WL make similar thing, but it operates not on graph, but in space of k-tuples of nodes. Basically, it's pairs or triplets of nodes. Then you define neighborhood as all pairs/triplets that differ in one element from the target pair/triplet. So, now you have have some kind of objects and defined neihgborhood for each of them, that's basically enough to apply the WL coloring.

Ok, now to k-GNN part. You repeat k-WL procedure on pairs of nodes, gets color for each of pair. You use one-hot encoded colors as input features and make graph convolution for pairs (with neighborhood defined as above), then getting some kind of embeddings for pairs. To get the node classification, you make average pooling by all pairs containing the node and then use usual fully-connected neural net.

As of the examples, the paper author provided several in article repo, you can try them.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. I have few questions regarding the answer:1)Is the neighborhood of a $K$-triplet must belong to the set $V^K$. 2) Does the ordering of the triplet (for example (a,b,c) or (b,c,a)) matter? 2)In K-WL GCN, How we define input features for $K$-triplet since we have only input features for each node? $\endgroup$ – Swakshar Deb Mar 25 at 17:01
  • $\begingroup$ 1. Yes 2.1. I think it shouldn't, but I don't know for sure, you could check the implementation 2.2. If you mean the features of the nodes I didn't see the precise procedure in paper, but from the code, as I can understand (hierarchical model): make node convolutions, get embeddings, average from the pair, concatenate the WL one hot encoded features $\endgroup$ – Kirill Fedyanin Mar 25 at 18:30
  • $\begingroup$ You could also try to ask questions in github issues of the repo, Matthias Fey (one of the authors) answers them there. $\endgroup$ – Kirill Fedyanin Mar 25 at 18:34

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.