Graph Neural Network (GNN)

Inspired by CNNs for images, these models define a localized convolution operation on a graph's neighborhood structure. They aggregate features from a node's immediate neighbors to compute its new representation.

• Spectral Methods: Operate in the Fourier domain of the graph, using the graph Laplacian's eigenvectors to define filters. Early models like Spectral CNN were computationally heavy.
• Spatial Methods: Define convolution directly on the graph topology. Graph Convolutional Network (GCN) is the seminal example, using a simple, efficient first-order approximation of spectral convolution. GraphSAGE extends this by sampling and aggregating from a fixed-size neighborhood, enabling inductive learning on unseen graphs.

These architectures incorporate attention mechanisms to weigh the importance of neighboring nodes dynamically during aggregation, rather than treating all neighbors equally.

• Graph Attention Network (GAT): Assigns an attention coefficient to each edge, computed via a shared neural network. This allows the model to focus on the most relevant connections for a given node and task.
• Key Advantage: Provides interpretability (via attention weights) and handles nodes with highly variable degree (number of connections) effectively. Multi-head attention can stabilize the learning process.

Apply a recurrent neural network (RNN) style update across the graph, where node states are updated iteratively until a stable equilibrium is reached. This is based on the concept of message passing as a recurrent process.

• Graph Neural Network (Original): The foundational model by Scarselli et al. uses a contraction map to ensure convergence of the recurrent state.
• Gated Graph Neural Networks (GG-NN): Use gated recurrent units (GRUs) or LSTMs as the core recurrent function, allowing for more complex state transitions and better gradient flow. They are well-suited for tasks requiring multi-step reasoning over the graph structure.

Designed for dynamic graphs where both the node features and the graph structure can change over time. They model temporal dependencies by combining GNNs with sequence models.

• Core Architecture: Typically uses a GNN layer to capture spatial dependencies at each timestep, coupled with an RNN (e.g., LSTM) or a 1D temporal convolution to capture patterns across time.
• Applications: Traffic forecasting, social network evolution, and predictive maintenance on sensor networks. Models like DCRNN (Diffusion Convolutional RNN) and STGCN (Spatial-Temporal GCN) are prominent examples.

Unsupervised models that learn low-dimensional node embeddings or reconstruct the graph structure itself. They consist of an encoder (a GNN) and a decoder.

• Encoder: Maps nodes to a latent vector representation (embedding).
• Decoder: Reconstructs graph information from embeddings. Common tasks include link prediction (reconstructing adjacency matrix) or feature reconstruction.
• Variational Graph Autoencoders (VGAE): Introduce a probabilistic latent space, regularizing the embeddings and enabling the generation of new graph structures.

Adapt the Transformer architecture to graph-structured data by treating nodes as tokens. They aim to capture long-range dependencies across the graph without being limited by the localized message-passing of traditional GNNs.

• Key Modifications: Replace positional encodings with structural encodings that capture node centrality, shortest path distances, or other graph-theoretic properties.
• Challenges: The self-attention mechanism is computationally expensive on dense graphs (O(N²)). Techniques like neighbor sampling or leveraging graph sparsity are used for scalability.
• Use Case: Effective in molecular property prediction and tasks where global graph context is critical.

The core computational mechanism of a Graph Neural Network. In each layer, nodes aggregate feature vectors from their neighbors, update their own state, and then pass messages. This iterative process allows information to propagate across the graph structure.

• Aggregation: A node collects features from its neighboring nodes (e.g., via sum, mean, or max).
• Update: The node combines its own features with the aggregated neighbor information using a learned function, typically a neural network.
• This enables nodes to develop representations informed by their local graph topology, essential for tasks like predicting molecular properties or classifying nodes in a social network.

A seminal and widely used type of Graph Neural Network that applies a localized spectral filter to graph data. It simplifies the message-passing paradigm into a single, efficient layer operation.

• Operation: A GCN layer performs a normalized aggregation of neighbor features, followed by a linear transformation and a non-linear activation.
• Key Insight: It leverages the graph's adjacency matrix to define the convolution operation, allowing features to smooth over connected nodes.
• This architecture is foundational for node classification, link prediction, and graph-level classification tasks, forming the basis for many subsequent GNN variants.

A Graph Neural Network variant that introduces an attention mechanism to the message-passing process. Instead of treating all neighbors equally, GAT learns to assign different importance weights to each neighbor.

• Dynamic Weights: For a given node, the model computes attention coefficients for each of its neighbors, determining how much focus to place on each one's features during aggregation.
• Benefits: This allows the model to focus on the most relevant connections, improving representational capacity and interpretability. It is particularly useful in heterogeneous graphs where relationships have varying significance.

A specialized GNN architecture designed for data where both graph structure and node features change over time. This is critical for dynamic systems in robotics and perception.

• Application in Robotics: Models the evolving relationships between objects, agents, or map landmarks. For example, tracking multiple pedestrians (nodes) whose positions (features) and interactions (edges) change frame-by-frame.
• Mechanism: Combines standard GNN layers for spatial reasoning with recurrent neural networks (RNNs) or temporal convolutions to capture temporal dynamics.
• This enables forecasting, such as predicting future trajectories of vehicles or robots in a shared space.

A structured, graph-based representation of a visual scene, where objects are nodes and their relationships are edges. This is a primary data structure that GNNs process for high-level scene understanding.

• Structure: A node might be person, bicycle, road with attributes like position and size. Edges represent predicates like riding, on, next_to.
• Use Case: In Vision-Language-Action Models, a scene graph extracted from a camera feed provides a symbolic, relational understanding that can be grounded to language instructions (e.g., "pick up the cup to the left of the monitor").
• GNNs can reason over scene graphs to answer questions about relationships or predict missing elements.

A large-scale, heterogeneous graph representing real-world entities and facts. Nodes represent entities (e.g., Paris, Eiffel Tower), and edges represent their relationships (e.g., located_in).

• Role in AI: Serves as a massive, structured knowledge base that can be integrated with language models via GNNs for Retrieval-Augmented Generation (RAG).
• GNN Application: GNNs can perform link prediction (inferring missing relationships) or entity classification within knowledge graphs, enhancing their completeness and utility.
• For enterprise systems, this enables deterministic factual grounding, allowing agents to reason with verified organizational data rather than relying solely on a model's parametric memory.