GCN Partitioning

Graph Partitoning Using Graph Convolutional Networks as described in GAP: Generalizable Approximate Graph Partitioning Framework

Loss Backward Equations

To handle large graphs, the loss function is implemented using sparse torch tensors using a custom loss class.

If $Z = (Y / \Gamma)(1 - Y)^{T} \circ A$ (1%20-%20Y)%5E%7BT%7D%20%5Ccirc%20A%20)

where Y_{ij} is the probability of node i being in partition j.

$L = \sum_{A_{lm} \neq 0} Z_{lm}$

Then the gradients can be calculated by the equations:

$\frac{\partial z_{i \alpha}}{\partial y_{ij}} = A_{i \alpha} \left(\frac{\Gamma_{j} (1 - y_{\alpha j}) - y_{ij}(1 - y_{\alpha j})D_{i}}{\Gamma_{j}^{2}}\right)$ %20-%20y%7Bij%7D(1%20-%20y%7B%5Calpha%20j%7D)D%7Bi%7D%7D%7B%5CGamma%7Bj%7D%5E%7B2%7D%7D%5Cright))

$\frac{\partial z_{\alpha i}}{\partial y_{ij}} = A_{\alpha i} \left(\frac{\Gamma_{j} (- y_{\alpha j}) - y_{\alpha j}(1 - y_{ij})D_{i}}{\Gamma_{j}^{2}}\right)$ %20-%20y%7B%5Calpha%20j%7D(1%20-%20y%7Bij%7D)D%7Bi%7D%7D%7B%5CGamma%7Bj%7D%5E%7B2%7D%7D%5Cright))

$\frac{\partial z_{i^{'} \alpha}}{\partial y_{ij}} = A_{i^{'} \alpha} \left(\frac{(1 - y_{\alpha j}) y_{i^{'}j}D_{i}}{\Gamma_{j}^{2}}\right) \;\;\; i^{'}, \alpha \neq i$ %20y%7Bi%5E%7B’%7Dj%7DD%7Bi%7D%7D%7B%5CGamma_%7Bj%7D%5E%7B2%7D%7D%5Cright)%20%5C%3B%5C%3B%5C%3B%20i%5E%7B’%7D%2C%20%5Calpha%20%5Cneq%20i)

Installation

Create a virtual environment using venv

python3 -m venv env

Source the virtual environment

source env/bin/activate

Use the package manager pip to install requirements.

pip install -r requirements.txt

Usage

python TrialModel.py

Limitations

Has only been tested on small custom graphs.

License

MIT