For an undirected and unlabeled graph, the function computed in each layer of a Graph Neural Network must respect certain properties so that the same function $($with shared weights$)$ can be used across different nodes of the graph. Suppose for a specific node $i$ in the graph, $h_i^{(l-1)}$ represents the state computed for this node in the previous layer, while the messages from the $n_i$ neighbors of node i from the previous layer are denoted by $m_{i,j}^{(l-1)},$ where $j$ ranges from $1$ to $n_i.$ We use subscripts and superscripts to denote learnable weights. If there is no superscript, the weights are shared across layers. Assume all dimensions are compatible. Explain which of these functions are valid for computing the next message $h_i^{(l)}$ for this node. For any choice that is invalid, briefly state why.

Note: Validity means they must satisfy the invariance and equivariance properties required for use as a GNN on an undirected graph.

$($a$)h_i^{(l)}=w_1{h}_i^{(l-1)}+\frac{w_2}{n_i}{\displaystyle \underset{j=1}{\overset{n_i}{}}}{m}_{i,j}^{(l-1)}$

$($b$)h_i^{(l)}=$max$(w_1{h}_i^{(l-1)},w_2{m}_{i,1}^{(l-1)},w_3{m}_{i,2}^{(l-1)},$dots,$w_{n_i-1}{m}_{i,n_i}^{(l-1)})$

where max operates element$-$wise on vectors.

$($c$)h_i^{(l)}=$max$(w_1{h}_i^{(l-1)},w_2{m}_{i,1}^{(l-1)},w_2{m}_{i,2}^{(l-1)},$dots,$w_2{m}_{i,n_i}^{(l-1)})$

where max operates element$-$wise on vectors.