Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results

Behrooz Tahmasebi, Derek Lim, Stefanie Jegelka

While message passing Graph Neural Networks (GNNs) have become increasingly popular architectures for learning with graphs, recent works have revealed important shortcomings in the…