GNN operations

GNN operations

Two main operations in GNNs:

1. Graph filtering operation
2. Graph pooling operation

Graph filtering operation

Key Idea: Generate the node embeddings using not only the features of the node, but also the surrounding neighbors

Graph filtering operation is very similar to convolution operation

• The process of learning node features based on the node features and the graph structure
• This process usually refers of taking that node features and graph structure and generate a new set of features (higher dimension features) for that node
• There are two main approaches to conduct this convolutional operation: Spectral-based and Spatial-based

Spectral-based graph convolution

It is based on spectral graph theory

The study of the characteristics of a graph based on the characteristic polynomial, egienvalues and eigenvectors of the matrices associated with the graph

Basically, It is defined as a multiplication of a signal (node features) by a kernel.

Spectral graph convolution methods achieve great results in several domains, but…

• Processes the full graph simultaneously (impractical for large graphs with billions of nodes)
• Assumes fixed graph

Therefore, spectral-based graph conv is good for small graphs not large graphs.

Also, It is not recommended for changing graphs.

Spatial-based graph convolution

Generally, Spatial-based graph convolution is better than spectral-based.

In spatial graph convolution, the operations are performed directly in the graph by aggregating information from spatially close neighbors

• Weights can be shared across a different location of the graph
• The computation is done in subsets of nodes instead of the entire graph
• GraphSAGE is one of the most representative algorithms for spatial graph convolution

Graph pooling operation

For node-focused tasks, graph filtering is sufficient (well, stacked consecutively like convolutional layers in CNNs), however, we need other type of operation to generate features for the entire graph from node features

That is graph pooling operation

Pooling operation in CNN is focused on subsampling. Similarly, graph pooling operation is designed to generate graph level features from node features.

Generally speaking, graph pooling can be seeing as an operation that given an initial graph as input, generates a coarsened graph with fewer nodes.