Graphs and Graph Neural Nets

Graph Neural Nets and Graph Convolutional Nets

Graphs are very rich mathematical-defined data structures. Research on analysing graphs with machine learning has been receiving more and more attention because of the great expressive power of graphs. Some real-world problems do not fit into sequential data-related or grid structures like images. Due to graph structure, it enables relational reasoning and efficient representation learning for entities connected in a network. They excel in problems involving relationships between entities. Another thing is that it captures a variety of settings: supervised, semi-supervised and unsupervised.

---

Problems That GNNs and GCNs Are Particularly Good at Addressing:

Node Classification – Determining the labels of nodes by analyzing their features and neighbouring nodes (e.g., identifying fraud in financial transactions).

Link Prediction – Anticipating absent or upcoming connections among nodes (e.g., suggesting friends in social networks).

Graph Classification – Categorizing whole graphs (e.g., assessing whether a chemical compound is harmful or safe).

Clustering and Community Detection – Recognizing clusters within networks (e.g., identifying similar consumers in e-commerce).

Knowledge Graph Completion – Deducing absent relationships between entities within a knowledge base (e.g., systems for answering questions).

Applications

Biomedical Engineering. With the Protein-Protein Interaction Network, graph convolution and relation network for breast cancer subtype classification can be used and provide efficient results. In addition, a GCN-based model for polypharmacy side effects prediction. They can be used to model the drug and protein interaction network and separately deal with edges in different types.

Combinatorial optimization. Combinatorial optimization issues related to graphs comprise a collection of NP-hard challenges that draw significant interest from researchers across various disciplines. Certain well-known problems, such as the travelling salesman problem (TSP) and minimum spanning trees (MST), have seen numerous heuristic approaches developed. Lately, employing deep neural networks to tackle these problems has gained popularity, with some solutions additionally utilizing graph neural networks due to their inherent graph characteristics.

Traffic networks. Forecasting traffic conditions is a difficult undertaking due to the dynamic nature of traffic networks and their intricate dependencies. Certain studies have integrated GNNs with LSTMs to effectively model both spatial and temporal relationships. Moreover, the use of ST-Conv blocks, which incorporate spatial and temporal convolution layers along with residual connections and bottleneck techniques, has demonstrated excellent outcomes.

Other ones are the distribution of water or electricity as they require the shortest distance problem and graph framework poses as a great tool for solution.

Adjacency matrix

\[A = \begin{array}{c|cccccccc} & N_1 & N_2 & N_3 & N_4 & N_5 & N_6 & N_7 & N_8 \\ \hline N_1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ N_2 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ N_3 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ N_4 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ N_5 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ N_6 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ N_7 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ N_8 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}\]

Degree matrix

\[D = \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{pmatrix}\]

Laplacian matrix

\[L = \begin{array}{c|cccccccc} & N_1 & N_2 & N_3 & N_4 & N_5 & N_6 & N_7 & N_8 \\ \hline N_1 & 2 & -1 & -1 & 0 & 0 & 0 & 0 & 0 \\ N_2 & -1 & 3 & 0 & -1 & -1 & 0 & 0 & 0 \\ N_3 & -1 & 0 & 3 & 0 & 0 & -1 & -1 & 0 \\ N_4 & 0 & -1 & 0 & 2 & 0 & 0 & 0 & -1 \\ N_5 & 0 & -1 & 0 & 0 & 2 & 0 & 0 & -1 \\ N_6 & 0 & 0 & -1 & 0 & 0 & 2 & -1 & 0 \\ N_7 & 0 & 0 & -1 & 0 & 0 & -1 & 2 & 0 \\ N_8 & 0 & 0 & 0 & -1 & -1 & 0 & 0 & 2 \end{array}\]

The second part of the code implements a diffusion process on a graph using a symmetrically normalized adjacency matrix. This process simulates how information propagates across the nodes of the graph over multiple iterations.

Step-by-step explanation

Modified adjacency matrix $A^*$

The adjacency matrix $A$ represents the structure of the graph, where

\[A_{ij} = \begin{cases} 1, & \text{if there is an edge between nodes } i \text{ and } j, \\ 0, & \text{otherwise}. \end{cases}\]

To ensure that each node preserves part of its own information during propagation, self-loops are added to the graph. This leads to the modified adjacency matrix \(A^* = A + I\) where $I$ denotes the identity matrix.

Degree matrix $D^*$

The degree matrix (D^*) is a diagonal matrix whose entries correspond to the sum of each row of (A^*), i.e.,

\[D^*_{ii} = \sum_{j} A^\*\_{ij}.\]

Symmetrically normalized adjacency matrix $\tilde{A}$

Rather than using the modified adjacency matrix directly, a symmetric normalization is applied, inspired by spectral graph theory:

\[\tilde{A} = D^{\*-\frac{1}{2}} A^\* D^{\*-\frac{1}{2}}.\]

This normalization balances the influence of nodes with different degrees and ensures numerical stability during diffusion.

Propagation of information

A diffusion (or message-passing) process is simulated over the graph. At each iteration, node representations are updated according to \(H^{(t+1)} = \tilde{A} H^{(t)},\) where $H^{(t)}$ denotes the node information at iteration $t$. The representations at each iteration are stored for later analysis and visualization.

Visualization

The diffusion process is visualized using networkx for graph construction and matplotlib.animation for animation. Nodes are colored according to their information values, illustrating how the initial signal at node 0 spreads through the network over time.

Code implementations and experiments related to these algorithms are available in the accompanying repository.