Description

Answer:
To distinguish the two red nodes and ensure they have different GNN embeddings, we need more than k layers of message passing, where k is the minimum number of hops in their neighborhood structure that differ.
denote the number of layers of message passing needed to distinguish the two red nodes as k. After k layers, the difference in the embeddings of the two red nodes will be at most k, which means that they will have the same embedding.

Here is the explanation:
Since the GNN model uses a simplified version with no nonlinearity, no learned linear transformation, and sum aggregation, the embedding of each node at each layer is updated by summing the embeddings of its neighbors and its current embedding.

To analyze the propagation of information through the graph, let’s denote the embedding of node v at layer t as ℎ( ), and the set of neighbors of node v as N(v).

In each layer of message passing, the embedding of a node v is updated as follows:
ℎ( ) = ℎ( ) + 𝑠𝑢𝑚 ℎ( ) 𝑓𝑜𝑟 𝑢 𝑖𝑛 𝑁(𝑣)
Start with an initial feature vector 𝑥 = [1] for all nodes. Therefore, the initial embedding ℎ( ) for all nodes, including the red nodes will be [1].

To distinguish the two red nodes, their embeddings need to differ in at least one dimension. Since the initial feature vector is 1-dimensional, the embeddings of the two red nodes will differ by the sum of the values from their respective 5-hop neighborhood structures.

Answer:
To show that the node embedding ℎ( ) converges as 𝑙 approaches infinity, that can relate the message passing process to a random walk on the graph.

First, let’s consider the message passing operation as a random walk on the graph. Starting from a node u, taking a uniform random walk for one step is equivalent to the aggregation step in the GNN model. The expectation over the layer-l embeddings of nodes we can end up with is ℎ( ), which is exactly the embedding of u in the next GNN layer.

Now, let’s analyze the properties of the Markov chain corresponding to the message passing process. We can consider each GNN layer as a step in the Markov chain. In this case, the Markov chain is irreducible because the graph is assumed to be connected, meaning that we can reach any node from any other node through a sequence of transitions. Additionally, the Markov chain is aperiodic since the graph is assumed to have no bipartite components. This means that any node can return to itself in any number of steps with a non-zero probability.

Based on the properties of the Markov chain, we can apply the Markov Convergence Theorem. This theorem states that for an irreducible and aperiodic Markov chain, the chain will converge to a stationary distribution regardless of the initial state.

In the context of the GNN, the stationary distribution corresponds to the node embeddings reaching a stable state where they no longer change significantly with further message passing. In other words, the node embeddings ℎ( ) converge as 𝑙 approaches infinity.

However, over-smoothing can occur when all node embeddings converge to the same value. This limits the ability to distinguish between nodes and makes the node embeddings less useful for downstream tasks. To address over-smoothing, architectural choices such as using learnable weights, non-linearities, and other methods can be employed to introduce more expressiveness and preserve the discriminative power of the node embeddings.