用球面拓扑表征图神经网络,生成可比对的低维指纹。
A Topological Characterization of Graph Neural Networks via Stochastic Block Model Embeddings on the n-Sphere

- 将图神经网络映射到单位球面,构造问题无关的拓扑指纹。
- 任意精度下,训练后的MPNN可近似为复杂度受限的分段图信号。
- 支持模型检索与可视化,适用于大模型跨任务迁移研究。
我们提出一种拓扑框架,通过将消息传递神经网络(MPNN)在图核-信号空间中诱导的随机块模型(SBM)映射到单位n-球面$ Sphere^{n-1}sub eals^n$,实现对训练后图神经网络(GNN)的比较。该方法基于三大经典理论:图核空间$( ext{Wo}, ext{cut-dist})$的紧致性、Frieze-Kannan弱正则性引理及其图核-信号扩展,以及MPNN对割距离的Lipschitz连续性。对于任意给定容差$>0$,当图足够大时,训练后的MPNN $Φ$ 可在误差$$内分解为一个复杂度有界的分段图核-信号。我们构造了一个显式的保测映射$Ψ_n: [0,1] \to \sphere^{n-1}$,将SBM区域放置于互不重叠的球帽上。该过程产生一种无需重新训练即可用于模型库中最近邻搜索和视觉分析的通用低维指纹,支持迁移学习候选检索。我们讨论了高维集中现象对大型语言模型嵌入的制约,并提出五个未来方向:双曲与格拉斯曼流形替代方案、基于格罗莫夫-瓦瑟斯坦距离的等距自由替代方法、信息几何(费舍尔)重构图核-信号流形、层间嵌入云的持久同调指纹,以及源自图核特征分解的谱距离基线。
原文摘要 · Abstract (English)
We propose a topological framework for comparing trained Graph Neural Networks (GNNs) by mapping the Stochastic Block Models (SBMs) induced on the graphon-signal space of a Message Passing Neural Network (MPNN) onto the unit $n$-sphere $\sphere^{n-1}\subset\R^n$. The construction rests on three classical pillars: the \emph{compactness} of the cut-distance graphon space $(\Wo,\cutdist)$ \citep{lovasz2006limits,lovasz2012large}, the Frieze--Kannan \emph{weak regularity lemma} together with its graphon-signal extension due to \citet{levie2023graphon}, and the Lipschitz continuity of MPNNs with respect to the cut-distance. We show that, for any prescribed tolerance $\varepsilon>0$, a trained MPNN $Φ$ acting on a sufficiently large graph factors (up to $\varepsilon$) through a step-graphon-signal of bounded complexity, and we construct an explicit measure-preserving map $Ψ_n\colon[0,1]\to\sphere^{n-1}$ that places the SBM regions on disjoint spherical caps. This produces a problem-agnostic, low-dimensional ``fingerprint'' of a trained GNN that is amenable to visual inspection and to nearest-neighbour search across model zoos, enabling \emph{transfer-learning candidate retrieval} without retraining. We discuss the obstruction posed by concentration of measure in high dimension -- a phenomenon directly relevant to LLM-scale embeddings. We close with five concrete future research directions: hyperbolic and Grassmannian alternatives to the spherical model, Gromov--Wasserstein distances on graphon-signals as an isometry-free alternative to the $n$-sphere map, an information-geometric (Fisher) reformulation of the SBM manifold, persistent-homology fingerprints of layer-wise embedding clouds, and a spectral-distance baseline derived from the graphon eigendecomposition.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。