Graph neural networks (GNNs) have become the \textit{de facto} standard for
representational learning in graphs, and have achieved state-of-the-art
performance in many graph-related tasks; however, it has been shown that the
expressive power of standard GNNs are equivalent maximally to 1-dimensional
Weisfeiler-Lehman (1-WL) Test. Recently, there is a line of works aiming to
enhance the expressive power of graph neural networks. One line of such works
aim at developing $K$-hop message-passing GNNs where node representation is
updated by aggregating information from not only direct neighbors but all
neighbors within $K$-hop of the node. Another line of works leverages subgraph
information to enhance the expressive power which is proven to be strictly more
powerful than 1-WL test. In this work, we discuss the limitation of $K$-hop
message-passing GNNs and propose \textit{substructure encoding function} to
uplift the expressive power of any $K$-hop message-passing GNN. We further
inject contextualized substructure information to enhance the expressiveness of
$K$-hop message-passing GNNs. Our method is provably more powerful than
previous works on $K$-hop graph neural networks and 1-WL subgraph GNNs, which
is a specific type of subgraph based GNN models, and not less powerful than
3-WL. Empirically, our proposed method set new state-of-the-art performance or
achieves comparable performance for a variety of datasets. Our code is
available at https://github.com/tianyao-aka/Expresive_K_hop_GNNs.

本研究探讨了基于图神经网络的 K-hop 传递模型的局限性，并提出了子结构编码函数，以提升其表达能力，并注入情境化子结构信息增强表达能力。实证结果表明，该方法在多个数据集上取得了新的最优表现或可比较的性能。

通过注入上下文化的子结构信息来提升 K - 跳消息传递 GNNs 的表现力

Improving the Expressiveness of $K$-hop Message-Passing GNNs by  Injecting Contextualized Substructure Information

Graph Neural Networks (GNNs) are a large class of relational models for graph
processing. Recent theoretical studies on the expressive power of GNNs have
focused on two issues. On the one hand, it has been proven that GNNs are as
powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish
graphs. Moreover, it has been shown that the equivalence enforced by 1-WL
equals unfolding equivalence. On the other hand, GNNs turned out to be
universal approximators on graphs modulo the constraints enforced by
1-WL/unfolding equivalence. However, these results only apply to Static
Undirected Homogeneous Graphs with node attributes. In contrast, real-life
applications often involve a variety of graph properties, such as, e.g.,
dynamics or node and edge attributes. In this paper, we conduct a theoretical
analysis of the expressive power of GNNs for these two graph types that are
particularly of interest. Dynamic graphs are widely used in modern
applications, and its theoretical analysis requires new approaches. The
attributed type acts as a standard form for all graph types since it has been
shown that all graph types can be transformed without loss to Static Undirected
Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study
considers generic GNN models and proposes appropriate 1-WL tests for those
domains. Then, the results on the expressive power of GNNs are extended by
proving that GNNs have the same capability as the 1-WL test in distinguishing
dynamic and attributed graphs, the 1-WL equivalence equals unfolding
equivalence and that GNNs are universal approximators modulo 1-WL/unfolding
equivalence. Moreover, the proof of the approximation capability holds for
SAUHGs, which include most of those used in practical applications, and it is
constructive in nature allowing to deduce hints on the architecture of GNNs
that can achieve the desired accuracy.

本文对静态无向同质图和动态图、属性图等不同类型的图中图神经网络（GNNs）的表达能力进行了理论分析，提出了适当的 1-WL 测试，并证明了 GNNs 与 1-WL 测试在区分动态图和属性图上具有相同的能力，且 GNNs 可以模拟 1-WL 测试，包括大多数实际应用中使用的静态无向同质图（SAUHGs）等。