![](https://csdnimg.cn/release/download_crawler_static/85431597/bg5.jpg)
A
C
B
A
C
B
BA C
BC A
B
A
C
A C A B
B C A B B C A C
Figure 1: Graphs
G
1
(left, 2 connected components) and
G
2
(middle) with node attributes indicated by
letters. The computation tree rooted at the node with arrow (right) agrees in both graphs, and likewise
for the other nodes. Hence, 1-WL and MPNNs cannot distinguish
G
1
and
G
2
. Figure adapted from [
40
].
computation trees. The tree
T (h
(t)
v
)
is constructed recursively: let
T (h
(0)
v
) = x
v
for all
v ∈ V
. For
t > 0
,
construct a root with label
x
v
and, for any
u ∈ N(v)
construct a child subtree
T (h
(t−1)
u
)
. Figure 1
illustrates an example.
Proposition 1. If for two nodes u 6= v, we have T (h
(t)
v
) = T (h
(t)
u
), then h
(t)
v
= h
(t)
u
.
Comparing computation trees directly implies that MPNNs cannot distinguish regular graphs. It
also shows further limitations with practical impact, as indicated in Figure 1, in particular for learning
combinatorial algorithms and for predicting properties of molecules, where functional groups are of key
importance. We say a class of models
F
decides a graph property if there exists an
F ∈ F
such that for
any two G, G
0
that differ in the property, we obtain F(G) 6= F(G
0
).
Proposition 2.
MPNNs cannot decide girth, circumference, diameter, radius, existence of a conjoint cycle, total
number of cycles, and existence of a k-clique [40]. MPNNs cannot count induced (attributed) subgraphs for any
connected pattern of 3 or more nodes, except star-shaped patterns [25].
Motivated by these limitations, generalizations of GNNs were proposed that provably increase their
representational power. Two main directions are to (1) introduce node IDs (Section 2.2), and (2) use
higher-order functions that act on tuples of nodes (Section 2.3).
2.2 Node IDs, local algorithms, combinatorial optimization and lower bounds
The major weaknesses of MPNNs arise from their inability to identify nodes as the origin of specific
messages. Hence, MPNNs can be strengthened by making nodes more distinguishable. The gained
representational power follows from connections with local algorithms, where the input graph defines
both the computational problem and the network topology of a distributed system: there, each node
v ∈ V
is a local machine and generates a local output, and all nodes execute the same algorithm, without
faults.
Approximation Algorithms.
Sato et al. [
94
] achieve a partial node distinction by transferring the
idea of a port numbering from local algorithms. Edges incident to each node are numbered as outgoing
ports. In each round, each node simultaneously sends a message to each port, but the messages can
differ across ports:
m
(t)
v
= f
(t)
Agg
{{(port(u, v), port(v, u), h
(t−1)
u
)}}
. (2.3)
Permutation invariance, though, is not immediate. This corresponds to the vector-vector consistent
(VV
C
) model for local algorithms [
51
]. The VV
C
analogy allows to transfer results on representing
approximation algorithms. CPNGNN is a specific VV
C
GNN model.
Theorem 3
([
94
])
.
There exists a CPNGNN that can compute a
(deg(G) + 1)
-approximation for the minimum
dominating set problem, a CPNGNN that can compute a 2-approximation for the minimum vertex cover problem,
but no CPNGNN can do better. No CPNGNN can compute a constant-factor approximation for the maximum
matching problem.
5