WeisfeilerLehman goes Dynamic An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs

2025-05-06 0 0 5.77MB 22 页 10玖币

侵权投诉

Weisfeiler–Lehman goes Dynamic: An Analysis of the Expressive Power

of Graph Neural Networks for Attributed and Dynamic Graphs⋆

Silvia Beddar-Wiesinga,∗,1,Giuseppe Alessio D’Invernob,1,Caterina Grazianib,1,Veronica Lachib,1,

Alice Moallemy-Oureha,1,Franco Scarselliband Josephine Maria Thomasa

aGraphs in Artiﬁcial Intelligence and Neural Networks (GAIN) University of Kassel Germany

bSiena Artiﬁcial Intelligence Lab (SAILab) University of Siena Italy

ARTICLE INFO

Keywords:

Graph Neural Network

Dynamic Graphs

GNN Expressivity

Unfolding Trees

Weisfeiler-Lehman Test

ABSTRACT

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 Attributed Undirected Homogeneous Graphs (SAUHG) with node attributes. In contrast, real-life

applications often involve a much larger variety of graph types. In this paper, we conduct a theoretical

analysis of the expressive power of GNNs for two other graph domains that are particularly interesting

in practical applications, namely dynamic graphs and SAUGHs with edge attributes. Dynamic graphs

are widely used in modern applications; hence, the study of the expressive capability of GNNs in

this domain is essential for practical reasons and, in addition, it requires a new analyzing approach

due to the diﬀerence in the architecture of dynamic GNNs compared to static ones. On the other

hand, the examination of SAUHGs is of particular relevance since they act as a standard form for all

graph types: it has been shown that all graph types can be transformed without loss of information

to SAUHGs with both attributes on nodes and edges. This paper considers generic GNN models and

appropriate 1–WL tests for those domains. Then, the known results on the expressive power of GNNs

are extended to the mentioned domains: it is proven that GNNs have the same capability as the 1–WL

test, 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 is mostly

constructive and allows us to deduce hints on the architecture of GNNs that can achieve the desired

approximation.

1. Introduction

Graph data is becoming pervasive in many application

domains, such as biology, physics, and social network analy-

sis [

]. Graphs are handy for complex data since they allow

for naturally encoding information about entities, their links,

and their attributes. In modern applications, several diﬀerent

types of graphs are commonly used and possibly combined:

⋆

This work was partially supported by the Ministry of Education and

Research Germany (BMBF, grant number 01IS20047A) and partially by

INdAM GNCS group.

∗Corresponding author

s.beddarwiesing@uni-kassel.de (S. Beddar-Wiesing);

giuseppealessio.d@student.unisi.it (G.A. D’Inverno);

caterina.graziani@student.unisi.it (C. Graziani);

veronica.lachi@student.unisi.it (V. Lachi); amoallemy@uni-kassel.de (A.

Moallemy-Oureh); franco@diism.unisi.it (F. Scarselli);

jthomas@uni-kassel.de (J.M. Thomas)

www.gain-group.de (S. Beddar-Wiesing);

https://sailab.diism.unisi.it/people/giuseppe-alessio-dinverno/ (G.A.

D’Inverno); https://sailab.diism.unisi.it/people/caterina-graziani/ (C.

Graziani); https://sailab.diism.unisi.it/people/veronica-lachi/ (V.

Lachi); www.gain-group.de (A. Moallemy-Oureh);

https://sailab.diism.unisi.it/people/franco-scarselli/ (F. Scarselli);

www.gain-group.de (J.M. Thomas)

ORCID(s): 0000-0002-2984-2119 (S. Beddar-Wiesing);

0000-0001-7367-4354 (G.A. D’Inverno); 0000-0002-7606-9405 (C. Graziani);

0000-0002-6947-7304 (V. Lachi); 0000-0001-7912-0969 (A.

Moallemy-Oureh); 0000-0003-1307-0772 (F. Scarselli)

1These authors contributed equally.

graphs can be homogeneous or heterogeneous, directed or

undirected, have attributes on nodes and/or edges, and be

static or dynamic hyper- or multigraphs [

]. Considering the

diversity of graph types, it has recently been shown that Static

Attributed Undirected Homogenous Graphs (SAUHGs) with

both attributes on nodes and edges can act as a standard form

for graph representation, namely that all the common graph

types can be transformed into those SAUHGs without losing

their encoded information [3].

In the ﬁeld of graph learning, Graph Neural Networks

(GNNs) have become a prominent class of models used to

process graphs and address diﬀerent learning tasks directly.

For this purpose, most GNN models adopt a computational

scheme based on a local aggregation mechanism. It recur-

sively updates the local information of a node stored in an

attribute vector by aggregating the attributes of neighboring

nodes. After several iterations, the attributes of a node capture

the local structural information received from its

𝑘

–hop

neighborhood. At the end of the iterative process, the obtained

node attributes can address diﬀerent graph-related tasks by

applying a suitable readout function.

The Graph Neural Network model of [

], which is

called Original GNN (OGNN) in this paper, was the ﬁrst

model capable of facing both node/edge and graph-focused

tasks utilizing suitable aggregation and readout functions,

respectively. In the current research, a large number of new

Beddar-Wiesing et al.: Preprint submitted to Elsevier Page 1 of 22

arXiv:2210.03990v2 [cs.LG] 3 May 2024

Weisfeiler–Lehmann goes Dynamic

applications and models have been proposed, including Neu-

ral Networks for graphs [

], Gated Sequence Graph Neural

Networks [

], Spectral Networks [

], Graph Convolutional

Neural Networks [

], GraphSAGE [

], Graph Attention

Networks [

], and Graph Networks [

]. Another extension

of GNNs consisted of the proposal of several new models

capable of dealing with dynamic graphs [

], which can be

used, e.g., to classify sequences of graphs, sequences of nodes

in a dynamic graph or to predict the appearance of an edge

in a dynamic graph.

Recently, a great eﬀort has been dedicated to studying the

theoretical properties of GNNs [

]. Such a trend is motivated

by the attempt to derive the foundational knowledge required

to design reasonable solutions eﬃciently for many possible

applications of GNNs [

]. A particular interest lies in the

study of the expressive power of GNN models since, in many

application domains, the performance of a GNN depends on

its capability to distinguish diﬀerent graphs. For example, in

Bioinformatics, the properties of a chemical molecule may

depend on the presence or absence of small substructures;

in social network analysis, the count of triangles allows us

to evaluate the presence and the maturity of communities.

Similar examples exist in dynamic domains: the distinction

of substructures contributes signiﬁcantly to the successful

analysis of molecular conformations [

]; in studies of the

evolution of social networks [

], substructures in the form

of contextual knowledge can help to improve performance.

Formally, a central result on the expressive power of

GNNs has shown that GNNs are at most as powerful as the

Weisfeiler–Lehman graph isomorphism test (1–WL) [

]. The 1–WL test iteratively divides graphs into groups

of possibly isomorphic

graphs using a local aggregation

schema. Therefore, the 1–WL test exactly deﬁnes the classes

of graphs that GNNs can recognize as non-isomorphic.

Furthermore, it has been proven that the equivalence

classes induced by the 1–WL test are equivalent to the ones

obtained from the unfolding trees of nodes on two graphs [

]

[

], and hence, 1–WL and the unfolding equivalences can

be used interchangeably. An unfolding tree rooted at a node

is constructed by starting at the root node and unrolling the

graph along the neighboring nodes until it reaches a certain

depth. If the unfolding trees of two nodes are equal in the

limit, the nodes are called unfolding tree equivalent

. Fig. 1

visualizes the relations between the 1–WL, the unfolding tree

equivalences, and the GNN expressiveness.

Another research goal of the expressive power of GNNs

is to study the GNN approximation capability. Formally, it

has been proven in [

] that OGNNs can approximate in

probability, up to any degree of precision, any measurable

function

𝜏(𝐆, 𝑣)→ℝ𝑚

that respects the unfolding equiva-

lence. Such a result has been recently extended to a large

It is worth noting that the 1–WL test is inconclusive since there exist

pairs of graphs that the test recognizes as isomorphic even if they are not.

Currently, the concept underlying unfolding trees is widely used to

study the GNN expressiveness, even if they are mostly called

computation

graphs [21].

AUT

1-AWL

SGNN

Thm. 4.1.6

Thm. 5.1.3

Ring

Closure

DUT

1-DWL

DGNN

Thm. 4.2.5

Thm. 5.2.4

Ring

Closure

Figure 1: a) In Thm. 4.1.6, we prove the equivalence of

the attributed unfolding tree equivalence (AUT) and the

attributed 1–WL equivalence (1–AWL) for SAUHGs. Afterward

in Thm. 5.1.3, we show a result on the approximation capability

of static GNNs for SAUHGs (SGNN) using the AUT equivalence.

b) Analogously to the attributed case, we show similar results

for Dynamic GNNs (DGNN) which can be used on temporal

graphs.

class of GNNs [

] called message-passing GNNs, including

most contemporary architectures.

Despite the availability of the mentioned results on the

expressive power of GNNs, their application is still limited

to undirected static graphs with attributes on nodes. This

limitation is particularly restrictive since modern applica-

tions usually involve more complex data structures, such as

heterogeneous, directed, dynamic graphs and multigraphs.

In particular, the ability to process dynamic graphs is pro-

gressively gaining signiﬁcance in many ﬁelds such as social

network analysis [

], recommender systems [

], traﬃc

forecasting [

] and knowledge graph completion [

Several surveys discuss the usage of dynamic graphs in other

application domains [1,28,29,30,31].

Although GNNs are considered universal approximators

on the extended domains, it is uncertain which GNN archi-

tectures contribute to such universality. Moreover, an open

question is how the deﬁnition of the 1–WL test has to be

modiﬁed to cope with novel data structures and whether the

universal results fail for particular graph types.

In this paper, we propose a study on the expressive power

of GNNs for two domains of particular interest, namely

dynamic graphs and static attributed undirected homogeneous

graphs (SAUHGs) with node and edge attributes. On the

one hand, dynamic graphs are interesting from a practical

and a theoretical point of view and are used in several

application domains [

]. Moreover, dynamic GNN models

are structurally diﬀerent from GNNs for static graphs, and the

results and methodology required to analyze their expressive

power cannot directly be deduced from existing literature.

On the other hand, SAUHGs with node and edge attributes

are interesting because, as mentioned above, they act as a

standard form for several other types of graphs that can all

be transformed to SAUGHs [3].

First, we introduce appropriate versions of the 1–WL test

and the unfolding equivalence to construct the fundamental

theory for the domains of SAUHGs and dynamic graphs

and discuss their relation afterward. Then, we consider

generic GNN models that can operate on both domains

and prove their universal approximation capability modulo

Beddar-Wiesing et al.: Preprint submitted to Elsevier Page 2 of 22

Weisfeiler–Lehmann goes Dynamic

the aforementioned 1–WL/unfolding equivalences. More

precisely, the main contributions of this paper are as follows.

•

We present new versions of the 1–WL test and of

the unfolding equivalence appropriate for dynamic

graphs and SAUHGs with node and edge attributes,

and we show that they induce the same equivalences

on nodes. Such a result makes it possible to use them

interchangeably to study the expressiveness of GNNs.

•

We show that generic GNN models for dynamic

graphs and SAUHGs with node and edge attributes

are capable of approximating, in probability and up to

any precision, any measurable function on graphs that

respects the 1-WL/unfolding equivalence.

•

The result on approximation capability holds for graphs

with unconstrained attributes of reals and target func-

tions. Thus, most of the domains used in practical

applications are included.

•

Moreover, the proof is based on space partitioning,

which allows us to deduce information about the GNN

architecture that can achieve the desired approxima-

tion.

•

We validate our theoretical results conducting an exper-

imental validation. Our setups show that 1) suﬃciently

powerful DGNNs can approximate well dynamic

systems that preserve the unfolding equivalence and

2) using non–universal architectures can lead to poor

performances.

The rest of the paper is organized as follows. Section 2

illustrates the related literature. In section 3, the notation used

throughout the paper is described, and the main deﬁnitions

are introduced. In section 4, we introduce the 1–WL test

and unfolding equivalences suitable for dynamic graphs

and SAUHGs with node and edge attributes and prove that

those equivalences are equal. In section 5, the approximation

theorems for GNNs on both graph types are presented.

We support our theoretical ﬁndings by setting up synthetic

experiments in 6. Finally, section 7includes our conclusions

and future matter of research. All of the proofs are collected

in the appendix A.

2. Related Work

In the seminal work [

], it has been proven that standard

GNNs have the same expressive power as the 1–WL test. To

overcome such a limitation, new GNN models and variants

of the WL test have been proposed. For example, in [

], a

model is introduced where node identities are directly injected

into the aggregate functions. In [

], the k-WL test has been

taken into account to develop a more powerful GNN model,

given its greater capability to distinguish non-isomorphic

graphs. In [

], a simplicial-wise Weisfeiler-Lehman test

is introduced, and it is proven to be strictly more powerful

than the 1-WL test and not less powerful than the 3-WL

test; a similar test (called cellular WL test), proposed in [

is proven to be more powerful than the simplicial version.

Nevertheless, all these tests do not deal with edge-attributed

graphs and not with dynamic graphs.

In [

], the authors consider a GNN model for multi-

relational graphs where edges are labeled with types: it is

proven that such a model has the same computation capability

as a corresponding WL-test. The result is similar to our result

on SAUGH, but the way we aggregate the message on the

edges is diﬀerent. Additionally, our work extends [

] from

several points of view: the approximation capability of GNNs

is studied, a relationship between the 1-WL test and unfolding

trees is established, and edge attributes include more general

vectors of reals. Moreover, all those studies are extended to

dynamic graphs.

Moreover, the WL test mechanism applied to GNNs has

also been studied within the paradigm of unfolding trees [

[

]. An equivalence between the two concepts has been

established by [

], but it is limited to static graphs without

edge attributes.

Some studies have been dedicated to the approximation

and generalization properties of Graph Neural Networks. In

[

], the authors proved the universal approximation proper-

ties of the original Graph Neural Network model, modulo the

unfolding equivalence. The universal approximation is shown

for GNNs with random node initialization in [

], while,

in [

], GNNs are shown to be able to encode any graph with

countable input features. Moreover, the authors of [

] proved

that GNNs, provided with a colored local iterative procedure

(CLIP), can be universal approximators for functions on

graphs with node attributes. The approximation property

has also been extended to Folklore Graph Neural Networks

in [

] and Linear Graph Neural Networks, and general

GNNs in [

], both in the invariant and equivariant

case. Recently, the universal approximation theorem has been

proved for modern message-passing graph neural networks

by [

] giving a hint on the properties of the network

architecture (e.g., the number of layers, the characterization

of the aggregation function). A relation between the graph

diameter and the computational power of GNNs has been

established in [

], where the GNNs are assimilated to the

so–called LOCAL models and it is proved that a GNN with

a number of layers larger than the diameter of the graph can

compute any Turing function of the graph. Nevertheless, no

information on the aggregation function characterization is

given.

Despite the availability of universal approximation theo-

rems for static graphs with node attributes, the theory lacks

results about the approximation capability of other types of

graphs, such as dynamic graphs and graphs with attributes on

both nodes and edges. Therefore, this paper aims to extend

the results of the expressive power of GNNs for dynamic

graphs and SAUHGs with node and edge attributes.

Beddar-Wiesing et al.: Preprint submitted to Elsevier Page 3 of 22

Weisfeiler–Lehmann goes Dynamic

3. Notation and Preliminaries

Before extending the work about the expressive power of

GNNs to dynamic and edge-attributed graph domains, the

mathematical notation and preliminary deﬁnitions are given

in this chapter. In this paper, only ﬁnite graphs are under

consideration.

ℕnatural numbers

ℕ0natural numbers starting at 0

ℝreal numbers

ℝ𝑘ℝvector space of dimension 𝑘

ℕ𝑘ℕvector space of dimension 𝑘

ℤ𝑘ℤvector space of dimension 𝑘

𝟘= (0,…,0)⊤zero vector of corresponding size

𝑎absolute value of a real 𝑎

⋅norm on ℝ

⋅𝑝𝑝-norm on ℝ

⋅∞∞-norm on ℝ

𝑀number of elements of a set 𝑀

[𝑛], 𝑛 ∈ℕsequence 1,2,…, 𝑛

[𝑛]0, 𝑛 ∈ℕ0sequence 0,1,…, 𝑛

∅empty set

⟂undeﬁned; non-existent element

{⋅}set

{⋅}multiset, i.e. set allowing

multiple appearances of entries

(𝑥𝑖)𝑖∈𝐼vector of elements 𝑥𝑖

for indices in set 𝐼

[𝑣𝑤]stacking of vectors 𝑣, 𝑤

∧conjunction

∪union of two (multi)sets

⊆sub(multi)set

⊊proper sub(multi)set

×factor set of two sets

The following deﬁnition introduces a static, node/edge at-

tributed, undirected and homogeneous graph called SAUHG.

The reason for deﬁning and using it comes from [

]. Here, it is

shown that every graph type is bijectively transformable into

each other. Therefore, SAUHGs will be used as a standard

form for all structurally diﬀerent graph types as directed or

undirected simple graphs, hypergraphs, multigraphs, hetero-

geneous or attributed graphs, and any composition of those.

For a detailed introduction, see [3].

Deﬁnition 3.1 (Static Attributed Undirected Homogeneous

Graphs).

𝐺′

is called static, node/edge attributed, undi-

rected, homogeneous graph (SAUHG) if

𝐺′= (′,′, 𝛼′, 𝜔′)

with

′⊂ℕ

is a ﬁnite set of nodes,

′⊂{{𝑢, 𝑣}∣∀𝑢, 𝑣 ∈′}

is a ﬁnite set of edges and node and edge attributes are

determined by the mappings

𝛼′∶′→𝐴, 𝜔′∶′→𝐵

that map into the arbitrary node attribute set

𝐴

, and edge

attribute set

𝐵

. The domain of SAUGHs will be denoted as

′.

Remark 3.2. (Attribute sets) In the above deﬁnition of the

SAUHG, the node and edge attribute sets

𝐴

and

𝐵

can be

arbitrary. However, without loss of generality, we can assume

that the attribute sets are equal because they can be arbitrarily

extended to

𝐴′=𝐴∪𝐵

. Additionally, any arbitrary attribute

set

𝐴′

can be embedded into the

𝑘

-dimensional vector space

ℝ𝑘

. Since the attribute sets in general do not matter for the

theories in this paper and to support a better readability, in

what follows we consider

𝛼′∶′→ℝ𝑘, 𝜔 ∶′→ℝ𝑘

for

every SAUHG.

All the aforementioned graph types are static, but temporal

changes play an essential role in learning on graphs represent-

ing real-world applications; thus, dynamic graphs are deﬁned

in the following. In particular, the dynamic graph deﬁnition

here consists of a discrete-time representation.

Deﬁnition 3.3 (Dynamic Graph).Let

𝐼= [0,…, 𝑙]⊊ℕ0

be a set of timesteps. Then a (discrete) dynamic graph

can be considered as a vector of static graph snapshots, i.e.,

𝐺= (𝐺𝑡)𝑡∈𝐼, where 𝐺𝑡= (𝑡,𝑡) ∀𝑡∈𝐼. Furthermore,

𝛼𝑣(𝑡) ∶= 𝛼(𝑣, 𝑡), 𝑣 ∈𝑡and

𝜔{𝑢,𝑣}(𝑡) ∶= 𝜔({𝑢, 𝑣}, 𝑡),{𝑢, 𝑣} ∈ 𝑡

where

𝛼∶×𝐼→𝐴

and

𝜔∶×𝐼→𝐵

deﬁne

the vector of dynamic node/edge attributes. Further, let

∶= 𝑡∈𝐼𝑡

and

∶= 𝑡∈𝐼𝑡

the total node and edge set

of the dynamic graph.

In particular, when a node

𝑣

does not exist, its attributes

and neighborhood are empty, respectively. Moreover, let

Ω𝑛𝑒𝑣(𝑡) = 𝜔{𝑣,𝑥1}(𝑡),…, 𝜔{𝑣,𝑥𝑛𝑒𝑣(𝑡)}(𝑡)𝑡∈𝐼

be the sequence of dynamic edge attributes of the neigh-

borhood corresponding node at each timestep. Note that, as

in Rem. 3.2, in what follows, we assume the attribute sets to

be equal and corresponding to ℝ𝑘.

To prove the approximation theorems for SAUHGs and

dynamic graphs, we need to specify the GNN architectures

capable of handling those graph types. The standard Message-

Passing GNN for static node-attributed undirected homoge-

neous graphs is given in [

]. Here, the node attributes are

used as the initial representation and input to the GNN. The

update is executed by aggregation over the representations

of the neighboring nodes.

Given that a SAUHG acts as a standard form for all graph

types, the ordinary GNN architecture will be extended to

take also edge attributes into account. This can be done by

analogously including the edge attributes in the ﬁrst iteration

to the processing of the node information in the general GNN

framework as follows.

Deﬁnition 3.4 (SGNN).For a SAUHG

𝐺′= (′,′, 𝛼′, 𝜔′)

let

𝑢, 𝑣 ∈′

and

𝑒= {𝑢, 𝑣}

. The SGNN propagation scheme

for iteration 𝑖∈ [𝑙], 𝑙 > 0is deﬁned as

𝐡(𝑖)

𝑣=COMBINE(𝑖)𝐡(𝑖−1)

𝑣,AGGREGATE(𝑖){𝐡(𝑖−1)

𝑢}𝑢∈𝑛𝑒𝑣,{𝜔{𝑢,𝑣}}𝑢∈𝑛𝑒𝑣

Beddar-Wiesing et al.: Preprint submitted to Elsevier Page 4 of 22

Weisfeiler–Lehmann goes Dynamic

(1,2) a

(2,3)

time

Dynamic Graph G

(1,-)

(2,-)

(3,-)

[1,1,2]

[1,2,1]

[(1,2),(2,3),(2,3)]

[-,3,-]

Statified Graph G'

[(1,-),(2,-),(3,-)]

[(1,-),(2,-),(3,-)] [(-,-),(p,-),(q,-)]

(p,-) (q,-)

(-,-)

Figure 2: Illustration of the statiﬁcation of a dynamic graph. On the left, the temporal evolution of a graph, including non-existent

nodes and edges (gray), is given, and on the right, the corresponding statiﬁed graph with the total amount of nodes and edges

together with the concatenated attributes is shown.

The output for a node-speciﬁc learning problem after the last

iteration 𝑙respectively is given by

𝐳𝑣=READOUT 𝐡𝑙

𝑣,

using a selected aggregation scheme and a suitable READ-

OUT function, and the output for a graph-speciﬁc learning

problem is determined by

𝐳=READOUT {𝐡𝑙

𝑣∣𝑣∈′}.

For the dynamic case, we chose a widely used GNN

model that is consistent with the theory we built. Based on

[

], the discrete dynamic graph neural network (DGNN) uses

a GNN to encode each graph snapshot. Here, the model is

modiﬁed by using the previously deﬁned SGNN in place of

the standard one.

Deﬁnition 3.5 (Discrete DGNN).Given a discrete dynamic

graph

𝐺= (𝐺𝑡)𝑡∈𝐼

, a discrete DGNN using a continuously

diﬀerentiable recursive function

𝑓

for temporal modelling

can be expressed as:

𝐡1(𝑡),…,𝐡𝑛(𝑡) ∶= SGNN(𝐺𝑡) ∀ 𝑡≥0

𝐪1(0),…,𝐪𝑛(0) = 𝐡1(0),…,𝐡𝑛(0) ∶= SGNN(𝐺0)

𝐪𝑣(𝑡) ∶= 𝑓(𝐪𝑣(𝑡− 1),𝐡𝑣(𝑡)) ∀ 𝑣∈

(1)

where

𝐡𝑣(𝑡) ∈ ℝ𝑟

is the hidden representation of node

𝑣

at time

𝑡

of dimension

𝑟

and

𝐪𝑣(𝑡) ∈ ℝ𝑠

is an

𝑠

dimensional hidden representation of node

𝑣

produced by

𝑓

and

𝑓∶ℝ𝑠×ℝ𝑟→ℝ𝑠

is a neural architecture for temporal

modeling (in the methods surveyed in [

𝑓

is almost always

an RNN or an LSTM).

The stacked version of the discrete DGNN is then:

𝐻(𝑡) = SGNN(𝐺𝑡)

𝑄(0) = 𝐻(0) = SGNN(𝐺0)

𝑄(𝑡) = 𝐹(𝑄(𝑡− 1), 𝐻(𝑡))

(2)

where

𝐻(𝑡) ∈ ℝ𝑛×𝑟

𝑄(𝑡) ∈ ℝ𝑛×𝑠

𝐹∶ℝ𝑛×𝑠×ℝ𝑛×𝑟→ℝ𝑛×𝑠

being

𝑛

the number of nodes,

𝑟

and

𝑠

the dimensions of the

hidden representation of a node produced respectively by the

SGNN

and by the

𝑓

. Applying

𝐹

corresponds to component-

wise applying 𝑓for each node [1].

To conclude, a function

READOUTdyn

will take as input

𝑄(𝑡)

and gives a suitable output for the considered task, so

that altogether the DGNN will be described as

𝜑(𝑡, 𝐺, 𝑣) = READOUTdyn(𝑄(𝑡)).

Remark 3.6. The DGNN is a Message-Passing model

because the SGNN is one, by deﬁnition.

The GNNs expressivity is studied in terms of their

capability to distinguish two non-isomorphic graphs.

Deﬁnition 3.7 (Graph Isomorphism).Let

𝐺1

and

𝐺2

be two

static graphs, then

𝐺1= (1,1)

and

𝐺2= (2,2)

are

isomorphic to each other

𝐺1≈𝐺2

, if and only if there exists

a bijective function 𝜙∶1→2, with

1. 𝑣1∈1⇔𝜙(𝑣1) ∈ 2∀𝑣1∈1,

2. {𝑣1, 𝑣2} ∈ 1⇔{𝜙(𝑣1), 𝜙(𝑣2)} ∈ 2∀ {𝑣1, 𝑣2} ∈ 1

In case the two graphs are attributed, i.e.,

𝐺1= (1,1, 𝛼1, 𝜔1)

and

𝐺2= (2,2, 𝛼2, 𝜔2)

, then

𝐺1≈𝐺2

if and only if

additionally there exist bijective functions

𝜑𝛼∶𝐴1→𝐴2

and

𝜑𝜔∶𝐵1→𝐵2

with images

𝐴𝑖∶= im(𝛼𝑖)

and

𝐵𝑖∶= im(𝜔𝑖)

𝑖= 1,2.

1. 𝜑𝛼(𝛼1(𝑣1)) = 𝛼2(𝜙(𝑣1)) ∀ 𝑣1∈1,

2. 𝜑𝜔(𝜔1({𝑢1, 𝑣1})) = 𝜔2({𝜙(𝑢1), 𝜙(𝑣1)}) ∀ {𝑢1, 𝑣1} ∈ 1

If the two graphs are dynamic, they are called to be isomor-

phic if and only if the static graph snapshots of each timestep

are isomorphic.

Graph isomorphism (GI) gained prominence in the theory

community when it emerged as one of the few natural

problems in the complexity class NP that could neither be

classiﬁed as being hard (NP-complete) nor shown to be solv-

able with an eﬃcient algorithm (that is, a polynomial-time

algorithm) [

]. Indeed it lies in the class NP-Intermidiate.

However, in practice, the so-called Weisfeiler-Lehman (WL)

test is used to at least recognize non-isomorphic graphs

[

]. If the WL test outputs two graphs as isomorphic, the

isomorphism is likely but not given for sure.

The expressive power of GNNs can also be approached

from the point of view of their approximation capability.

It generally analyzes the capacity of diﬀerent GNN models

to approximate arbitrary functions [

]. Diﬀerent universal

approximation theorems can be deﬁned depending on the

model, the considered input data, and the sets of functions.

This paper will focus on the set of functions that preserve the

unfolding tree equivalence, deﬁned as follows.

Since the results in this section hold for undirected and

unattributed graphs, we aim to extend the universal approxi-

mation theorem to GNNs working on SAUHGs (cf. Def. 3.1)

and dynamic graphs (cf. Def. 3.3). For this purpose, in the

Beddar-Wiesing et al.: Preprint submitted to Elsevier Page 5 of 22

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Weisfeiler–LehmangoesDynamic:AnAnalysisoftheExpressivePowerofGraphNeuralNetworksforAttributedandDynamicGraphs⋆SilviaBeddar-Wiesinga,∗,1,GiuseppeAlessioD’Invernob,1,CaterinaGrazianib,1,VeronicaLachib,1,AliceMoallemy-Oureha,1,FrancoScarsellibandJosephineMariaThomasaaGraphsinArtificialIntelligenceandNe...

展开>> 收起<<

WeisfeilerLehman goes Dynamic An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

WeisfeilerLehman goes Dynamic An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: