\section{GNN Expressiveness (28 points)}


\textbf{For Q1.1, write down number of layers needed. For Q1.2, write down the transition matrix $M$ and the limiting distribution $r$. For Q1.3 and 1.4, write down the transition matrix w.r.t $A$ and $D$. For Q1.5, write down your proof in a few sentences (equations if necessary). For Q1.6, describe the message function, aggregate function, and update rule in a few sentences or equations.}

Graph Neural Networks (GNNs) are a class of neural network architectures used for deep learning on graph-structured data. Broadly, GNNs aim to generate high-quality embeddings of nodes by iteratively aggregating feature information from local graph neighborhoods using neural networks; embeddings can then be used for recommendations, classification, link prediction, or other downstream tasks. Two important types of GNNs are GCNs (graph convolutional networks) and GraphSAGE (graph sampling and aggregation).

Let $G = (V,E)$ denote a graph with node feature vectors $X_u$ for $u \in V$. To generate the embedding for a node $u$, we use the neighborhood of the node as the computation graph. At every layer $l$, for each pair of nodes $u \in V$ and its neighbor $v \in V$, we compute a message function via neural networks, and apply a convolutional operation that aggregates the messages from the node’s local graph neighborhood (Figure \ref{fig:Q4-gnn-architecture}), and updates the node’s representation at the next layer. By repeating this process through $K$ GNN layers, we capture feature and structural information from a node’s local $K$-hop neighborhood. For each of the message computation, aggregation, and update functions, the learnable parameters are shared across all nodes in the same layer.

\begin{figure}[!htb]
\centering
  \includegraphics[width=0.7\columnwidth]{gnn-architecture.png}
  \caption{GNN architecture}   
  \label{fig:Q4-gnn-architecture}
\end{figure}

We initialize the feature vector for node $X_u$ based on its individual node attributes. If we already have outside information about the nodes, we can embed that as a feature vector. Otherwise, we can use a constant feature (vector of 1) or the degree of the node as the feature vector.

These are the key steps in each layer of a GNN:
\begin{itemize}
    \item \textbf{Message computation}: We use a neural network to learn a message function between nodes. For each pair of nodes $u$ and its neighbor $v$, the neural network message function can be expressed as $M(h^k_u,h^k_v,e_{u,v})$. In GCN and GraphSAGE, this can simply be $\sigma(W h_v + b)$, where $W$ and $b$ are the weights and bias of a neural network linear layer. Here $h^k_u$ refers to the hidden representation of node $u$ at layer $k$, and $e_{u,v}$ denotes available information about the edge $(u, v)$, like the edge weight or other features. For GCN and GraphSAGE, the neighbors of $u$ are simply defined as nodes that are connected to $u$. However, many other variants of GNNs have different definitions of neighborhood.
    \item \textbf{Aggregation}: At each layer, we apply a function to aggregate information from all of the neighbors of each node. The aggregation function is usually permutation invariant, to reflect the fact that nodes’ neighbors have no canonical ordering. In a GCN, the aggregation is done by a weighted sum, where the weight for aggregating from $v$ to $u$ corresponds to the $(u,v)$ entry of the normalized adjacency matrix $D^{-1/2}AD^{-1/2}$.
    \item \textbf{Update}: We update the representation of a node based on the aggregated representation of the neighborhood. For example, in GCNs, a multi-layer perceptron (MLP) is used; Graph-SAGE combines a skip layer with the MLP.
    \item \textbf{Pooling}: The representation of an entire graph can be obtained by adding a pooling layer at the end. The simplest pooling methods are just taking the mean, max, or sum of all of the individual node representations. This is usually done for the purposes of graph classification.
\end{itemize}

We can formulate the Message computation, Aggregation, and Update steps for a GCN as a layer-wise propagation rule given by:
\begin{equation}
    h^{k+1} = \sigma(D^{-1/2} A D^{-1/2} h^k W^k)
\end{equation}

where $h^k$ represents the matrix of activations in the $k$-th layer, $D^{-1/2}AD^{-1/2}$ is the normalized adjacency of graph $G$, $W_k$ is a layer-specific learnable matrix, and $\sigma$ is a non-linearity function. Dropout and other forms of regularization can also be used.

We provide the pseudo-code for GraphSAGE embedding generation below. This will also be relevant to the questions below.

\begin{figure}[H]
\centering
  \includegraphics[width=1\columnwidth]{algorithm.png}
\end{figure}

In this question, we investigate the effect of the number of message passing layers on the expressive power of Graph Convolutional Networks. In neural networks, expressiveness refers to the set of functions (usually the loss function for classification or regression tasks) a neural network is able to compute, which depends on the structural properties of a neural network architecture.

.\\\\
\subsection{Effect of Depth on Expressiveness (4 points)}

Consider the following 2 graphs in figure~\ref{fig:Q4.1}, where all nodes have 1-dimensional initial feature vector $x = [1]$. We use a simplified version of GNN, with no nonlinearity,
no learned linear transformation, and sum aggregation. Specifically, at every
layer, the embedding of node $v$ is updated as the sum over the embeddings of
its neighbors ($N_v$) and its current embedding $h^t_v$ to get $h^{t+1}_v$. We run the GNN
to compute node embeddings for the 2 red nodes respectively. Note that the 2 red nodes have different 5-hop neighborhood structure (note this is not the minimum number of hops for which the neighborhood structure of the 2 nodes differs). How many layers of message passing are needed so that these 2 nodes can be distinguished (i.e., have different GNN embeddings)? Explain your answer in a few sentences.
\\\\\\\\
\begin{figure}[!htb]
\centering
  \includegraphics[width=0.6\columnwidth]{fig4-1.png}
  \caption{Figure for Question 1.1}
  \label{fig:Q4.1}
\end{figure}

.\\

\Solution{}

\subsection{Random Walk Matrix (4 points)}

Consider the graph shown below (figure~\ref{fig:Q4.2}).
\begin{enumerate}
    \item Assume that the current distribution over nodes is $r = [0,0,1,0]$, and after the random walk, the distribution is $M \cdot r$. What is the random walk transition matrix $M$, where each column of $M$ corresponds with the node ID of the node that you are transitioning from?
    \item What is the limiting distribution $r$, namely the eigenvector of $M$ that has an eigenvalue of 1 ($r = Mr$)? Write your answer in fraction form or round it to the nearest thousandth place and in the following form, e.g. $[1.200, 0.111, 0.462, 0.000]$. Note that before reporting you should normalize $r$ \textbf{Hint: $r$ is a probability distribution representing the random walk probabilities for each node after a large number of timesteps}.
\end{enumerate}

\begin{figure}[!htb]
\centering
  \includegraphics[width=0.5\columnwidth]{fig4-2.png}
  \caption{Figure for Question 1.2}
  \label{fig:Q4.2}
\end{figure}

\Solution{}


\subsection{Relation to Random Walk (i) (4 points)}

Let’s explore the similarity between message passing and random walks. Let $h^{(l)}_i$ be the embedding of node $i$ at layer $l$. Suppose that we are using a mean aggregator for message passing, and omit the learned linear transformation and non-linearity: $h^{(l+1)}_i = \frac{1}{|N_i|} \sum_{j \in N_i} h^{(l)}_j$. If we start at a node $u$ and take a uniform random walk for 1 step, the expectation over the layer-$l$ embeddings
of nodes we can end up with is $h^{(l+1)}_u$, exactly the embedding of $u$ in the next GNN layer. What is the transition matrix of the random walk? Describe the transition matrix using the adjacency matrix $A$, and degree matrix $D$, a diagonal matrix where $D_{i,i}$ is the degree of node $i$.

\Solution{}

\subsection{Relation to Random Walk (ii) (4 points)}

Suppose that we add a skip connection to the aggregation from Question 1.3:
$$h^{(l+1)}_i = \frac{1}{2}h^{(l)}_i + \frac{1}{2}\frac{1}{|N_i|} \sum_{j \in N_i} h^{(l)}_j$$
What is the new corresponding transition matrix?

\Solution{}

\subsection{Over-Smoothing Effect (5 points)}

In Question 1.1 we see that increasing depth could give more expressive power.
On the other hand, however, a very large depth also gives rise to the undesirable
effect of over smoothing. Assume we are still using the aggregation function
from Question 1.3: $h^{(l+1)}_i = \frac{1}{|N_i|} \sum_{j \in N_i} h^{(l)}_j$. Show that the node embedding $h^{(l)}$ will converge as $l \rightarrow \infty$. Here we assume that the graph is connected and has no bipartite components. We also assume that the graph is undirected.

Over-smoothing thus refers to the problem of node embedding convergence. Namely, if all node embeddings converge to the same value then we can no longer distinguish them and our node embeddings become useless for downstream tasks. However, in practice, learnable weights, non-linearity, and other architecture choices can alleviate the over-smoothing effect.

\textbf{Hint: Here are some properties that might be helpful: 
\begin{itemize}
    \item A Markov Chain is \textit{irreducible} if every state can be reached from every other state. 
    \item A state $i$ of a Markov Chain is \textit{periodic} if, for a certain $t>1$, it is only possible to travel from $i$ to $i$ in multiples of $t$ timesteps. A Markov Chain is \textit{aperiodic} if it has no periodic states. 
    \item If a Markov Chain is irreducible and aperiodic, it will converge to a unique stationary distribution regardless of the starting state. 
\end{itemize} You don’t need to be super rigorous with your proof.}

\Solution{}

\subsection{Learning BFS with GNN (7 points)}

Next, we investigate the expressive power of GNN for learning simple graph algorithms. Consider breadth-first search (BFS), where at every step, nodes that are connected to already visited nodes become visited. Suppose that we use GNN to learn to execute the BFS algorithm. Suppose that the embeddings are 1-dimensional. Initially, all nodes have input feature 0, except a source node which has input feature 1. At every step, nodes reached by BFS have embedding 1, and nodes not reached by BFS have embedding 0. Describe a message function, an aggregation function, and an update rule for the GNN such that it learns the task perfectly.

\Solution{}