Post #203

Beyond Weisfeiler-Lehman: using substructures for provably expressive graph neural networks This is the second post by Michael Bronstein, where he discussed his recent architecture of GNN. In one sentence, they append information about graph statistics, such as number of 4-cliques, to message-passing mechanism and show that it is theoretically equivalent to k-WL, with fraction of its cost. For more than 6 months, I wondered why do we try to design GNN that can solve graph isomorphism (GI), if in all cases we are at most as good as already known algorithms to GI. What if we just take a automorphism group of a graph and then append this information to GNN, hoping it will help for downstream tasks. This way we solve GI by default by using automorphism group, and just measure effectiveness of the GNN for the tasks that matter.