## 3 Graph Clustering Methods
### Graph Neural Networks for Community Detection  
Graph Neural Networks (GNNs) represent a category of deep learning algorithms designed to extract features from graph data. Traditional deep learning methods are typically tailored for structured data. However, graphs can vary significantly in size, exhibit multimodal features, and possess intricate topologies. By leveraging node-level information, GNNs can directly facilitate predictions, classifications, or other analytical tasks.  
In leveraging graph data, GNNs operate under the assumption that significant amounts of node information are contained within their neighborhoods. In this way, the topology of the graph can be encoded in node embeddings. These node embeddings contain the initial data relating to the node itself, and neighborhood data thanks to the updating of the node embeddings carried out by the GNNs. Thus, a GNN uses a neural network on the neighbors of each node; this is referred to as a GNN layer.  
A single GNN layer compresses a set of embeddings into a single embedding in two steps: the message passing and the aggregation. Equation (4) presents a single layer of Graph Convolutional Network (GCN) [26] where the invariant aggregation function is a sum, and the message passing is a linear matrix operation with a weight matrix \(\mathrm{U}\).  
Formula (4) delineates the process by which input information, derived from both the target node \(h_{i}^{t}\) and its neighboring nodes \(h_{i}^{t}\), undergoes aggregation by neural networks to generate the updated representation \(h_{i}^{t+1}\). This mechanism is depicted in the gray and black blocks in Figure 3[45].  
\[h_{i}^{t+1}=\sigma\left(h_{i}^{t}W+\sum_{jN(i)}\frac{1}{c_{ij}}h_{j}^{t}U\right) \tag{4}\]  
* \(h_{i}^{t}\) represents the initial vector comprising the node features.
* \(h_{i}^{t+1}\) denotes the updated vector encompassing information regarding the node's neighbors and the graph's topology. This augmentation furnishes richer insights and enhances the representation of the node \(h_{i}\).
* \(W\) represents the weight matrix from a neural network, discerning significant elements to retain within the initial vector \(h_{i}^{t}\).
* \(U\) is another weight matrix originating from a neural network, tasked with processing the vectors of neighboring nodes \(h_{j}^{t}\).
* The expression \(\left(\sum_{j\in N(i)}\frac{1}{c_{ij}}\right)\) represents an aggregation function, which normalizes the representations of neighboring nodes in \(N(i)\). This necessitates a permutation-invariant function, as we must be agnostic to the order of neighbors to obtain consistent results regardless of their arrangement.
* \(\sigma\) denotes an activation function similar to sigmoid.  
To determine \(U\) and \(W\), supervised learning of a neural network involves adjusting the weights of the network to minimize the difference between the predictions and the expected outputs. This iterative process allows the network to gradually improve its ability to make accurate predictions on new data. However, this supervised learning requires data labeling.  
Graph clustering performs unsupervised learning without label data. Indeed, our goal is to do clustering with the new embeddings updated by GNNs to detect communities in the graph. So, GraphSAGE will be used to generate a labeled training sample that will be used to update the node's embeddings.