Despite the celebrated popularity of Graph Neural Networks (GNNs) across
numerous applications, the ability of GNNs to generalize remains less explored.
In this work, we propose to study the generalization of GNNs through a novel
perspective - analyzing the entropy of graph homomorphism. By linking graph
homomorphism with information-theoretic measures, we derive generalization
bounds for both graph and node classifications. These bounds are capable of
capturing subtleties inherent in various graph structures, including but not
limited to paths, cycles and cliques. This enables a data-dependent
generalization analysis with robust theoretical guarantees. To shed light on
the generality of of our proposed bounds, we present a unifying framework that
can characterize a broad spectrum of GNN models through the lens of graph
homomorphism. We validate the practical applicability of our theoretical
findings by showing the alignment between the proposed bounds and the
empirically observed generalization gaps over both real-world and synthetic
datasets.

通过分析图同态性的熵，我们提出了一种新的视角来研究图神经网络的泛化能力，并通过将图同态性与信息论度量联系起来，得出了适用于图和节点分类的泛化界限。通过我们提出的界限，能够捕捉到各种图结构的细微差别，包括但不限于路径、环和完全子图。通过图同态性，我们呈现了一个统一的框架，能够揭示广谱 GNN 模型的特性。通过在真实世界和人工合成数据集上观察到的泛化差距，我们验证了理论发现的实际可应用性。

基于同态性的图神经网络泛化

Generalization of Graph Neural Networks through the Lens of Homomorphism

In this paper, we study the graph classification problem from the graph
homomorphism perspective. We consider the homomorphisms from $F$ to $G$, where
$G$ is a graph of interest (e.g. molecules or social networks) and $F$ belongs
to some family of graphs (e.g. paths or non-isomorphic trees). We show that
graph homomorphism numbers provide a natural invariant (isomorphism invariant
and $\mathcal{F}$-invariant) embedding maps which can be used for graph
classification. Viewing the expressive power of a graph classifier by the
$\mathcal{F}$-indistinguishable concept, we prove the universality property of
graph homomorphism vectors in approximating $\mathcal{F}$-invariant functions.
In practice, by choosing $\mathcal{F}$ whose elements have bounded tree-width,
we show that the homomorphism method is efficient compared with other methods.

本文从图同态的角度研究了图分类问题，提出了使用同态数作为嵌入映射的自然不变量，在近似不变函数的时候证明了同态向量的普适性，特别是在选择树宽有限的元素族时，同态方法比其他方法更有效率。