Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs
The paper introduces graph homomorphism distortion (dHD), a new metric that measures how much node features are distorted when mapping one graph to another via homomorphisms. This measure is inspired by metric geometry and aims to capture similarity between attributed graphs based on attribute distances. It proves dHD is a pseudo-metric, provides a structural encoding for graphs, and improves the performance of graph neural networks.