Graph Theory

Graph theory studies relationships. A graph is a set of nodes (entities) and edges (connections). Many ML problems are naturally graphs: social networks, molecules, knowledge graphs, recommendation systems, and dependency structures in language.

Basic Definitions

• Nodes: items (users, atoms, documents).
• Edges: relationships (friendship, bonds, citations). May be directed or undirected, weighted or unweighted.
• Adjacency matrix A: matrix view of edges.

Graph Neural Networks (GNN) Intuition

GNNs learn node representations by repeatedly mixing a node’s features with its neighbors’ features (message passing). After several rounds, information can travel multiple hops.

Why Graphs Are Hard

• No fixed ordering of nodes (permutation invariance).
• Variable size (graphs can have very different numbers of nodes/edges).
• Long-range dependencies can require many message-passing steps.

Common Tasks

• Node classification (label each node)
• Link prediction (predict missing edges)
• Graph classification (classify whole graphs, e.g. molecules)
• Community detection and clustering