Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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 <em>pairs</em> (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.</p>
  <p>As of the examples, the paper author provided several in <a href="https://github.com/chrsmrrs/k-gnn/tree/master/examples" rel="nofollow noreferrer">article repo</a>, you can try them.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T17:01:53.117Z
Answers.Text: 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?
Answers.UserDisplayName: Swakshar Deb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T18:30:45.727Z
Answers.Text: 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
Answers.UserDisplayName: Kirill Fedyanin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T18:34:36.297Z
Answers.Text: You could also try to ask questions in github issues of the repo, Matthias Fey (one of the authors) answers them there.
Answers.UserDisplayName: Kirill Fedyanin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T14:54:55.400Z
Answers.LastActivityDate: 2021-03-25T14:54:55.400Z
Answers.UserDisplayName: Kirill Fedyanin
Body: <p>I am reading a paper on the <a href="https://arxiv.org/pdf/1810.02244.pdf" rel="nofollow noreferrer">K-WL GCN</a>. 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.</p>
  <p>Does anyone have any solved example problem on K-WL or can anyone explain to me how the K-WL test works?</p>
  <p>Note: If anyone also explains how K-WL GCN uses the K-WL test, I will be thankful.</p>
  
Tags: <papers><geometric-deep-learning><graph-neural-networks>
Title: How does the K-dimensional WL test work?
UserDisplayName: Swakshar Deb
ThreadText: # How does the K-dimensional WL test work?
  
  (Asked by: username_0 on 2021-03-24)
  
  I am reading a paper on the [K-WL GCN](https://arxiv.org/pdf/1810.02244.pdf). 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.
  
  **Tags:** papers, geometric-deep-learning, graph-neural-networks
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-25. Score: 3
  
  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](https://github.com/chrsmrrs/k-gnn/tree/master/examples), you can try them.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: 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  
  > **username_1**: You could also try to ask questions in github issues of the repo, Matthias Fey (one of the authors) answers them there.  
  
  ---
  
  