提出新度量方法，用图同态扭曲度区分图结构与特征的相似性。
Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them
- 基于图同态设计最小最大扭曲度度量，融合结构与特征信息。
- 该度量可高效计算，且能补充1-WL等现有表达能力评估方法。
- 可用于构建结构编码，提升GNN的预测性能，适合图神经网络研究者。
图学习的复杂性很大程度上源于结构与特征之间的相互作用。然而，在分析图神经网络的表达能力时，现有方法倾向于忽略特征而仅关注结构，导致难以判断具有相近特征的两个图在多大程度上应被视为相似。为此，本文提出一种基于图同态的新（伪）度量。受度量几何思想启发，图同态扭曲度衡量将一个图映射到另一个图时，节点特征所承受的最小最坏情况扭曲。我们通过实验证明，该度量（i）在某些附加假设下可高效计算，（ii）可补充现有的表达能力度量如1-WL，（iii）支持定义结构编码，从而提升图神经网络的预测能力。
原文摘要 · Abstract (English)
A large driver of the complexity of graph learning is the interplay between structure and features. When analyzing the expressivity of graph neural networks, however, existing approaches ignore features in favor of structure, making it nigh-impossible to assess to what extent two graphs with close features should be considered similar. We address this by developing a new (pseudo-)metric based on graph homomorphisms. Inspired by concepts from metric geometry, our graph homomorphism distortion measures the minimal worst-case distortion that node features of one graph are subjected to when mapping one graph to another. We demonstrate the utility of our novel measure by showing that (i.) it can be efficiently calculated under some additional assumptions, (ii.) it complements existing expressivity measures like $1$-WL, and (iii.) it permits defining structural encodings, which improve the predictive capabilities of graph neural networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。