Post #548

On "On Graph Neural Networks versus Graph-Augmented MLPs" There is a cool ICLR'21 paper"On Graph Neural Networks versus Graph-Augmented MLPs" by Lei Chen, Zhengdao Chen, and Joan Bruna, which studies a question I had in mind for some time: can we replace a graph with some statistics of graph, which we will later use with standard MLP, and not lose in quality? The answer is that for graph-level task, such as graph isomorphism, we can indeed capture much of what's needed from the graph to solve graph isomorphism problem at the same level as WL test. However, for node-level tasks, there are provably less functions on nodes that graph-augmented MLPs can identify than GNNs. Roughly, the reason is that GNNs process graph topology and node features at the same time, while graph-augmented MLPs first treat the graph topology and then process node features with MLP. So theoretically we lose expressive power when we use MLPs instead of GNNs on graph-structured data.