Graph Representations
Learning Objectives
- Understand why graphs are a universal language for relational data
- Choose appropriate graph representations for different domains
- Distinguish node-level, link-level, and graph-level ML tasks
- Recognize real-world applications of graph-based machine learning
1. Why Graphs?
Graphs are a general language for describing and analyzing entities with relations and interactions.
Many types of data are naturally graphs. Once you see this, you can’t unsee it:
| Domain | Nodes | Edges |
|---|---|---|
| Social Networks | People | Friendships, follows |
| Economic Networks | Companies, banks | Transactions, ownership |
| Communication Networks | Devices, routers | Data flow, connections |
| Citation Networks | Papers | Citations |
| The Internet | Web pages | Hyperlinks |
| Neural Networks (biological) | Neurons | Synapses |
Databases are Graphs!
Every relational database — commerce, finance, clinical trials — is a graph. Tables are node types, foreign keys are edges. An ER diagram is a graph schema.
This is not a metaphor: when you write a SQL JOIN, you are traversing edges in a graph.
Discussion: What graphs do you interact with daily?
Think about: your phone’s contact network, your music streaming recommendations, Google Maps routing, your university’s course prerequisite structure, your social media feed algorithm…
2. Graph Representation
A graph is a common language that can represent wildly different domains — actors and movies, social relationships, protein interactions — using the same formal structure.
A graph G = (V, E) consists of a set of nodes (vertices) V and a set of edges (links) E connecting pairs of nodes.
|N| = number of nodes, |E| = number of edges.
Directed vs. Undirected
| Undirected | Directed | |
|---|---|---|
| Links | Symmetrical, reciprocal | One-way (A → B ≠ B → A) |
| Examples | Friendships, co-authorship, protein interactions | Twitter follows, citations, web hyperlinks |
Other properties edges can have: weights (strength of connection), types (kind of relationship), attributes (timestamps, labels).
Heterogeneous Graphs
A graph where nodes and/or edges can have different types. Formally: G = (V, E, T, R) where T is a set of node types and R is a set of relation types.
Node types: Drug, Disease, Protein, Adverse Event, Pathway
Edge types: Treats, Causes, Associated With, Has Function
Example edge: (Fulvestrant, Treats, Breast Neoplasms)
Node types: Paper, Author, Conference, Title, Year
Edge types: cite, hasAuthor, pubWhere, pubYear, hasTitle
Example edge: (GraphSAGE, cite, NeurIPS)
Bipartite Graphs
A graph whose nodes can be divided into two disjoint sets U and V such that every edge connects a node in U to a node in V. The sets U and V are independent sets (no edges within a set).
| Example | Set U | Set V |
|---|---|---|
| Authors ↔ Papers | Authors | Papers they wrote |
| Actors ↔ Movies | Actors | Movies they appeared in |
| Users ↔ Movies | Users | Movies they rated |
| Recipes ↔ Ingredients | Recipes | Ingredients they contain |
Bipartite graphs can be projected into single-mode networks: e.g., two authors are connected if they co-authored a paper. Two movies are connected if the same user rated both.
What are the nodes? What are the edges? These choices are not always obvious.
- Sometimes there is a unique, unambiguous representation
- Often the representation is by no means unique
- The way you assign links determines the nature of the questions you can study
Choosing the right graph representation is a modeling decision that shapes everything downstream.
3. Graphs and Machine Learning
Complex domains have a rich relational structure, which can be represented as a relational graph. By explicitly modeling relationships we achieve better performance!
Main question: How do we take advantage of relational structure for better prediction?
Why Graphs are Hard for Standard ML
The modern deep learning toolbox is designed for simple sequences (text, audio → RNNs/Transformers) and grids (images → CNNs).
Networks are different:
- Arbitrary size and complex topological structure (no spatial locality like grids)
- No fixed node ordering or reference point
- Often dynamic and have multimodal features
Graphs are the frontier of deep learning — they require new architectures.
Three Levels of Tasks
Machine learning on graphs operates at different scales:
| Level | Question | Examples |
|---|---|---|
| Node-level | What is this node? | User churn prediction, lifetime value, categorizing users |
| Link-level | Should these two nodes be connected? | Recommender systems, product affinity, friend suggestions |
| Graph-level | What is this graph/subgraph? | Fraud detection, molecule property prediction, traffic ETA |
Node-Level: Classify Nodes
Goal: Characterize the structure and position of a node in the network.
Features include:
- Node degree — how many connections
- Node importance & position — e.g., number of shortest paths passing through a node, average shortest path length to other nodes
- Substructures around the node — local neighborhood patterns
Build a graph: Users ↔ Sales ↔ Products. Attach training labels (Churn/Active) with timestamps to user nodes. The graph structure helps predict which users will churn — users connected to many churning neighbors are themselves at risk.
Link-Level: Predict Missing Links
Task: Predict new, missing, or unknown links based on existing links.
At test time, node pairs (with no existing links) are ranked, and top-ranked pairs are predicted as future links.
Users interact with items (watch movies, buy products, listen to music).
- Nodes: Users and Items
- Edges: User-item interactions
- Goal: Recommend items users might like — predict missing edges in a bipartite graph
PinSage (Pinterest, KDD 2018): learns node embeddings on a graph of 3 billion nodes to recommend related pins. This is link prediction at industrial scale.
Graph-Level: Predict Properties of Entire Graphs
Goal: Make a prediction for an entire graph or a subgraph.
Model the road network as a graph:
- Nodes: Road segments
- Edges: Connectivity between segments
- Prediction: Time of Arrival (ETA)
Pipeline: Anonymized travel data → Supersegments → Graph Neural Network → ETA predictions → Google Maps routing. This is a graph-level task: you need the structure of the whole subgraph (route) to predict travel time.
Summary: ML in the Language of Graphs
| Level | Task Examples |
|---|---|
| Node-level | Churn, lifetime value, next best action |
| Link-level | Product affinity, recommendations |
| Graph-level | Fraud / money laundering detection, traffic prediction |