Introduction
Graph Neural Networks (GNNs) apply deep neural network concepts directly to graph structures. In traditional graph embeddings, one vector holds static information. In GNNs, a vector acts like a dynamic vector — much like comparing a static array to a dynamic array—creating a supervector that contains its own data plus its neighbors' data. Adding non-linear activation functions (like ReLU) allows this dynamic vector trajectory to become flexible.
From a linear perspective:
Vector Addition: Adding two vectors connects the head of one to the tail of another, producing a resulting vector that completes the missing side of a triangle—this is how vectors bundle information.
Matrix Multiplication: Represents a sequence of linear transformations that shifts the coordinate system from right to left, streamlining data and discarding unused information.
GNNs preserve the original graph topology to maintain variety, breaking the rigid matrix rules where every item must have a fixed number of neighbors (like pixels in an image having exactly 8 neighbors).
Core GNN Tasks
Node-Focused Tasks (Node Classification): Focuses on individual objects, including identifying fraud accounts, or recommender shopping systems. It combines multiple pieces of information into single vectors to group nodes into specific areas for prediction. The total number of vectors stays unchanged—only the vector dimensions change.
Graph-Focus Tasks (Graph Classification): Focuses on global structure, such as analyzing molecular properties (CH2, CH4) or detecting malicious code sequences. It works like node-focus but adds a pooling step at the end to condense everything into a single vector inheriting all features.
GNNs can be accessed from two perspectives: Spectral-based (algebraic) and Spatial-based (geometric).
Spectral-based Graph Filters
This matrix method subtracts the degree matrix from the adjacency matrix (the Graph Laplacian), where diagonal entries are zero and non-neighbor values are negative, measuring vector interactions through wave oscillations.
Direct spatial convolutional on irregular graph topologies is mathematically challenging. Spectral filtering addresses this by transforming graph signals into the frequency domain via Graph Fourier Transform. In the frequency domain, complex convolutions convert into straightforward matrix multiplications. Once filtered, the signals are transformed back to the original spatial domain.
Converting graph data to a spectral space and back serves a clear purpose: human do not know how to draw wave oscillations, so deep learning converts the signal to adjust parameters ( ) in that transformed space until it finds the optimal result.
Chebyshev Polynomials & Cheby-Filter: Instead of giving the model a pen and letting it draw freely without instruction, Cheby-Filter hands the model a function—a ruler or geometric tool—so it draws structured shapes without overthinking. Using dynamic programming, level k inherits results from level k-1. Inputs shrink to the range [-1, 1] to save computational energy and prevent exploding values.
GCN-Filter: An upgraded, simplified Cheby-Filter. Instead of using complex curved rulers, circles, or triangles, GCN uses simple horizontal or cross lines to model wave oscillations. It assumes a maximum eigenvalue of $2$ to make calculations lighter, focusing purely on immediate 1-hop neighbors.
Spatial-based Graph Filters
Spatial filters operate directly in coordinate space using vector addition to combine information and matrix multiplication to filter it, making node updates much easier to implement.
Early Graph Filters: Used rigid, fixed calculation functions, making the model robot-like and lacking adaptability
GraphSAGE-Filter: Randomly picks a subset of neighboring nodes and zips their information. It uses clever tricks, priorizing nodes with high weights/degrees or running random walks to pick representative neighborhood nodes.
GAT-Filter: While GCN treats all graph structures uniformly, GAT evaluates specific nodes. Like a talent contest, neighbor nodes that fit better receive higher scores. GAT even employs multiple juges (multi-head attention) to rank neighbors from different perspectives.
ECC-Filter (Edge-Conditioned Convolution): Uses edge features to produce transformations for nodes.
Mo-Filter: Introduces pseudo-coordinates to make graph geometry flexible.
MPNN (Message Passing Neural Network): A General Serves as the overarching general framework summarizing all spatial filters.
Graph Pooling
Graph pooling shrinks all node vectors into a single graph-level vector (summarizing both feature of nodes and structure of graph). Because one vector must absorb massive amounts of data, information loss is a risk. Therefore, Hierarchical Graph Pooling is the solution to this problem:
- Hierarchical Graph Pooling: Similar to the Chuliu-Edmond algorithm for finding minimum spanning trees (with its contracting and expanding phases), this approach avoids collapsing everything at once. It condenses the graph step-by-step from local components to larger structures.
Parameter Learning for Graph Neural Networks
- Parameter Learning for Node Classification: Makes individual nodes smarter by training decision boundaries in localized classification areas.
- Parameter Learning for Graph Classification: Verifies whether global graph structures convey accurate collective information.
After-learning notes: The Laplacian matrix link back to Pierre-Simon Laplace and the concept of Laplace's Demon - a theoretical entity capable of predicting the future by calculating physical state data. Modern GNNs reflect a similar goal: by learning from past graph topologies, models predict future user purchase desires or gold price trends, almost as if attempting to recreate that demon.
