Graph Neural Networks: Why Message Passing Works - and Where It Breaks

Most machine learning assumes a table. Rows are independent, columns are fixed, and shuffling the rows changes nothing except the order of the output. Graphs break all three assumptions at once. A molecule is not a row. A social network is not a fixed-size vector. A citation graph has no natural ordering of neighbours, and the number of neighbours changes from node to node.

Graph neural networks (GNNs) are the attempt to build a neural model that respects that structure. Their core idea is disarmingly simple: a node learns about itself by listening to its neighbours, then those neighbours have already listened to theirs. Repeat that a few times, and every node carries a summary of its local neighbourhood. Almost everything interesting about GNNs, including their failures, follows from that one mechanism.

The intuition: representation by neighbourhood

Think of a single paper in a citation network.…