This is concise implementation of Graph Convolution Network (GCN) for educational purpose using Numpy.
-
Adjacency Matrix
$A$ :- Represents the graph structure where
$A_{ij} = 1$ if there is an edge between nodes$i$ and$j$ , and$A_{ij} = 0$ otherwise.
- Represents the graph structure where
-
Input Feature Matrix
$X$ :- Represents node features where each row corresponds to a node and each column corresponds to a feature.
-
Weight Matrices
$W^{(l)}$ :- Initialize weight matrices for each layer
$l$ of the GCN.
- Initialize weight matrices for each layer
-
Bias Vectors
$b^{(l)}$ (optional):- Optionally, initialize bias vectors for each layer.
-
Normalized Graph Laplacian
$\tilde{L}$ :- Compute the normalized graph Laplacian:
$$\tilde{L} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$$
- Compute the normalized graph Laplacian:
-
Graph Convolution Operation:
- Compute the node representation matrix at layer
$l+1$ :$$H^{(l+1)} = \sigma(\tilde{L} H^{(l)} W^{(l)})$$
-
$\sigma$ is the activation function.
- Compute the node representation matrix at layer
-
Loss Function:
- Compute the loss function for node classification (which is our case, we used Categorical Cross-Entropy):
$$L = -\frac{1}{N} \sum_{i=1}^{N} \sum_{j=1}^{C} Y_{ij} \log(\hat{Y}_{ij})$$
- Compute the loss function for node classification (which is our case, we used Categorical Cross-Entropy):
-
Gradient Computation:
- Compute the gradients of the loss function with respect to the model parameters using backpropagation.
- Example:
$\frac{\partial L}{\partial W} = \frac{1}{N} (X^T A^T) (\hat{Y} - Y)$ .
-
Parameter Update:
- Update the model parameters using gradient descent or another optimization algorithm.
$$W_{new} = W_{old} - \alpha \frac{\partial L}{\partial W}$$
- Update the model parameters using gradient descent or another optimization algorithm.
- Iteration:
- Repeat steps 3-5 iteratively until convergence or for a fixed number of epochs.
- Clone the repo
$ git clone https://github.com/HamzaGbada/GCN-Numpy.git
- Install the requirement libraries
$ pip install -r requirements.txt
- Train
$ python train.py
We used Pytorch geometric to load the Zachary’s Karate Club graph dataset.
- Kipf, Thomas & Welling, Max. (2016). Semi-Supervised Classification with Graph Convolutional Networks.