Computer Science Artificial Intelligence Deep Learning Graph Neural Networks (GNNs) are a class of deep learning models designed specifically to perform inference on data structured as graphs, which consist of nodes (entities) and edges (relationships). Unlike traditional neural networks that require fixed-size, grid-like inputs, GNNs operate directly on the irregular structure of graphs by iteratively updating the representation of each node based on information aggregated from its neighbors—a process often called message passing or neighborhood aggregation. Through this mechanism, GNNs learn to encode not only the features of individual nodes but also the complex topological structure of their local and global environment, making them highly effective for tasks such as node classification, link prediction, and whole-graph classification in domains like social networks, molecular chemistry, and recommendation systems.
1.1.
Introduction to Graph Theory
1.1.1.
Definition of a Graph
1.1.1.1.1. Node Identifiers
1.1.1.1.2. Node Attributes
1.1.1.2.1. Edge Directionality
1.1.1.2.3. Edge Attributes
1.1.1.3. Graph Representation
1.1.1.3.1. Mathematical Notation
1.1.1.3.2. Set-theoretic Definition
1.1.2.
Types of Graphs
1.1.2.1.1. Directed Acyclic Graphs (DAGs)
1.1.2.1.2. Strongly Connected Graphs
1.1.2.2. Undirected Graphs
1.1.2.4. Unweighted Graphs
1.1.2.7. Homogeneous Graphs
1.1.2.8. Heterogeneous Graphs
1.1.2.8.1. Multiple Node Types
1.1.2.8.2. Multiple Edge Types
1.1.2.10. Attributed Graphs
1.1.2.11.1. Temporal Networks
1.1.2.11.2. Evolving Graphs
1.1.3.
Graph Representations
1.1.3.1.1. Dense Representation
1.1.3.1.2. Sparse Representation
1.1.3.1.3. Properties and Characteristics
1.1.3.2.1. Memory Efficiency
1.1.3.2.2. Traversal Operations
1.1.3.3.2. Storage Considerations
1.1.4.
Key Graph Properties
1.1.4.1.3. Degree Distribution
1.1.4.2.1. Adjacency Matrix Properties
1.1.4.2.3. Laplacian Matrix
1.1.4.2.3.1. Unnormalized Laplacian
1.1.4.2.3.2. Normalized Laplacian
1.1.4.2.3.3. Random Walk Laplacian
1.1.4.2.4. Spectral Properties
1.1.4.2.4.1. Eigenvalues and Eigenvectors
1.1.4.3.1. Connected Components
1.1.4.3.2. Strong Connectivity
1.1.4.3.3. Weak Connectivity
1.1.4.4. Paths and Distances
1.1.4.4.3. Distance Metrics
1.1.4.4.4. Geodesic Distance
1.1.4.5.1. Cycle Detection
1.1.4.5.3. Tree vs Cyclic Structures
1.1.4.6. Centrality Measures
1.1.4.6.1. Degree Centrality
1.1.4.6.2. Betweenness Centrality
1.1.4.6.3. Closeness Centrality
1.1.4.6.4. Eigenvector Centrality
1.1.4.7. Clustering Properties
1.1.4.7.1. Clustering Coefficient
1.1.4.7.2. Local Clustering
1.1.4.7.3. Global Clustering
1.1.4.9. Small World Properties
1.2.
Essential Mathematical Concepts
1.2.1.
Linear Algebra Foundations
1.2.1.1.1. Vector Operations
1.2.1.1.2. Linear Independence
1.2.1.1.3. Basis and Dimension
1.2.1.2. Matrix Operations
1.2.1.2.1. Matrix Multiplication
1.2.1.2.2. Matrix Transpose
1.2.1.3. Eigendecomposition
1.2.1.3.1. Eigenvalues and Eigenvectors
1.2.1.3.2. Spectral Decomposition
1.2.1.3.3. Diagonalization
1.2.1.4. Singular Value Decomposition
1.2.1.4.2. Low-rank Approximation
1.2.1.5. Sparse Matrix Operations
1.2.1.5.1. Sparse Storage Formats
1.2.1.5.2. Efficient Computations
1.2.2.
Calculus and Optimization
1.2.2.1. Derivatives and Gradients
1.2.2.1.1. Partial Derivatives
1.2.2.1.2. Gradient Vector
1.2.2.1.3. Directional Derivatives
1.2.2.2.1. Composite Functions
1.2.2.2.2. Backpropagation Foundations
1.2.2.3. Optimization Methods
1.2.2.3.1. Gradient Descent
1.2.2.3.2. Stochastic Gradient Descent
1.2.2.3.3. Mini-batch Gradient Descent
1.2.2.3.4. Momentum Methods
1.2.2.3.5. Adaptive Learning Rates
1.2.3.
Probability and Statistics
1.2.3.1. Probability Fundamentals
1.2.3.1.1. Sample Spaces and Events
1.2.3.1.2. Probability Distributions
1.2.3.1.3. Conditional Probability
1.2.3.2.1. Discrete Random Variables
1.2.3.2.2. Continuous Random Variables
1.2.3.2.3. Expectation and Variance
1.2.3.3. Statistical Inference
1.2.3.3.1. Parameter Estimation
1.2.3.3.2. Hypothesis Testing
1.2.3.3.3. Confidence Intervals
1.2.3.4.2. Prior and Posterior Distributions
1.2.3.4.3. Bayesian Inference
1.3.
Traditional Machine Learning on Graphs
1.3.1.
Graph Feature Engineering
1.3.1.1. Node-level Features
1.3.1.1.1. Structural Features
1.3.1.1.1.1. Degree-based Features
1.3.1.1.1.2. Centrality-based Features
1.3.1.1.1.3. Local Clustering Features
1.3.1.1.2. Attribute Features
1.3.1.1.2.1. Raw Node Attributes
1.3.1.1.2.2. Engineered Features
1.3.1.1.3. Position Features
1.3.1.1.3.1. Spectral Features
1.3.1.1.3.2. Random Walk Features
1.3.1.2. Edge-level Features
1.3.1.2.1. Edge Attributes
1.3.1.2.2. Structural Edge Features
1.3.1.2.3. Node Pair Features
1.3.1.3. Graph-level Features
1.3.1.3.1. Global Statistics
1.3.1.3.2. Spectral Features
1.3.1.3.3. Topological Features
1.3.2.
Traditional Graph Algorithms
1.3.2.1.1. Breadth-First Search
1.3.2.1.2. Depth-First Search
1.3.2.2. Shortest Path Algorithms
1.3.2.2.1. Dijkstra's Algorithm
1.3.2.2.2. Floyd-Warshall Algorithm
1.3.2.3. Community Detection
1.3.2.3.1. Modularity Optimization
1.3.2.3.2. Spectral Clustering
1.3.3.
Shallow Embedding Methods
1.3.3.1. Matrix Factorization Approaches
1.3.3.1.1. Adjacency Matrix Factorization
1.3.3.1.2. Laplacian Eigenmaps
1.3.3.1.3. Locally Linear Embedding
1.3.3.2. Random Walk Methods
1.3.3.2.1.1. Random Walk Generation
1.3.3.2.1.2. Skip-gram Training
1.3.3.2.1.3. Word2Vec Analogy
1.3.3.2.2.1. Biased Random Walks
1.3.3.2.2.2. Return Parameter (p)
1.3.3.2.2.3. In-out Parameter (q)
1.3.3.2.2.4. Hyperparameter Tuning
1.3.3.2.3.1. First-order Proximity
1.3.3.2.3.2. Second-order Proximity
1.3.3.2.3.3. Negative Sampling
1.3.3.3. Limitations of Shallow Methods
1.3.3.3.1. Fixed Representations
1.3.3.3.2. Lack of Generalization
1.3.3.3.3. Scalability Issues