Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings

arXiv:2312.05905v2 Announce Type: replace
Abstract: We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match …

abstract arxiv boost cs.ai cs.lg edge encoding family features gnns graph graph neural networks graphs improving network networks neural networks node novel type via