扩展了图的偏谱方法，可处理带属性、多层和超图等复杂结构。
The Generalized Skew Spectrum of Graphs
- 基于群论与调和分析，构建新图不变量，支持多种图结构
- 在相同计算成本下提升表达能力，实验验证效果更优
- 适合需要高效且强大图表示的研究者，如图神经网络设计
本文提出一类新的置换不变图嵌入方法，对Kondor与Borgwardt（2008）提出的图偏谱进行了推广。该方法基于群论与调和分析，引入了一类图同构不变的新不变量，能够嵌入更丰富的图结构——包括带属性图、多层图和超图，而原始偏谱无法处理这些类型。本方法进一步定义了一个函数族，可在计算复杂度与表达能力之间进行权衡。通过应用保持泛化性的启发式策略，我们在不增加计算成本的前提下提升了偏谱的表达能力。我们正式证明了该推广的不变性，通过实验展示了其更强的表达能力，并讨论了高效计算方式。
原文摘要 · Abstract (English)
This paper proposes a family of permutation-invariant graph embeddings, generalizing the Skew Spectrum of graphs of Kondor & Borgwardt (2008). Grounded in group theory and harmonic analysis, our method introduces a new class of graph invariants that are isomorphism-invariant and capable of embedding richer graph structures - including attributed graphs, multilayer graphs, and hypergraphs - which the Skew Spectrum could not handle. Our generalization further defines a family of functions that enables a trade-off between computational complexity and expressivity. By applying generalization-preserving heuristics to this family, we improve the Skew Spectrum's expressivity at the same computational cost. We formally prove the invariance of our generalization, demonstrate its improved expressiveness through experiments, and discuss its efficient computation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。