When: Sep 14th, 2022 – 11:00 – 11:45 AM
Where: Google meet link
Description
Weisfeiler-Lehman goes dynamic: an analysis of the expressive power of Graph Neural Network for Attributed and Dynamic Graphs
Graph Neural Networks (GNNs) are a large class of connectionist models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused their attention on two issues. On the one hand, it has been proved that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has also been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, it has been proved that GNNs are universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, those results only apply to Static Undirected Homogeneous Graphs (SUHG) with attributes on nodes. In contrast, real-life application domains often involve much more varied types of graphs, such as, for example, dynamic, heterogeneous, directed graphs, and multigraphs with attributes on nodes and edges. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for two types of graphs that are particularly interesting, namely dynamic graphs and static graphs with attributes on nodes and edges. The former type is widely used in modern applications, and its theoretical analysis requires a new methodology. The latter type can act as a standard form for all the graph types since it has been proved that all the graph types can be transformed to SUHG with attributes on nodes and edges without loss of
information. The study considers generic GNN models for those domains; consequently, appropriate 1-WL tests are proposed. Then, we extend the results on the expressive power of GNNs to the novel graph domains, proving that GNNs have the same capability of the 1-WL test in distinguish graphs, that the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo ‘1-WL/unfolding equivalence. Moreover, the proof of approximation capability holds for a very general class of graphs, which includes most of those used in practical applications, and it is constructive in nature so that it allows to deduce hints on the structure and the architecture of GNNs that can achieve the desired accuracy.