Graph Fundamentals - Vertices, Edges, Paths, and Graph Types in ML

Reading time: ~24 minutes | Level: Graph Theory Foundations → ML Engineering

You are building a drug discovery system. Each molecule is a graph: carbon, nitrogen, and oxygen atoms are nodes; single, double, and triple bonds are edges. You want a model that predicts binding affinity. Before you can design the GNN architecture, you need to answer: Is this graph directed or undirected? Weighted or unweighted? Are there cycles? Is it connected? How do these properties affect what your model can and cannot learn?

These are graph fundamentals questions. They are not abstract - they determine your data preprocessing, your GNN's message-passing scheme, and whether your model will converge.

What You Will Learn

• Formal definition of graphs: vertices, edges, directed vs undirected
• Graph properties: degree, weight, paths, cycles, connectivity
• Special graph types: complete, bipartite, trees, DAGs, multigraphs
• How each graph type maps to real ML applications
• Python implementations using NetworkX and NumPy

Part 1 - The Formal Definition

A graph $G = (V, E)$ consists of:

• $V = \{v_1, v_2, \ldots, v_n\}$: a set of vertices (also called nodes)
• $E \subseteq V \times V$: a set of edges (pairs of vertices)

The number of vertices is denoted $n = |V|$ and the number of edges $m = |E|$.

Directed vs undirected

Undirected graph: Edges are unordered pairs - $(u, v) = (v, u)$.

$G_{\text{undirected}}: \{u, v\} \in E \Leftrightarrow \{v, u\} \in E$

Directed graph (digraph): Edges are ordered pairs - $(u, v) \neq (v, u)$.

$G_{\text{directed}}: (u, v) \in E \text{ does not imply } (v, u) \in E$

import networkx as nx
import numpy as np

# Undirected graph: friendships (symmetric)
G_undirected = nx.Graph()
G_undirected.add_edges_from([
    ('Alice', 'Bob'),
    ('Bob', 'Charlie'),
    ('Alice', 'Charlie'),
    ('Charlie', 'Dave')
])
print(f"Undirected: {G_undirected.number_of_nodes()} nodes, {G_undirected.number_of_edges()} edges")

# Directed graph: citations (paper A cites paper B, not necessarily vice versa)
G_directed = nx.DiGraph()
G_directed.add_edges_from([
    ('Paper_A', 'Paper_B'),
    ('Paper_A', 'Paper_C'),
    ('Paper_B', 'Paper_D'),
    ('Paper_C', 'Paper_B')  # Different from Paper_B → Paper_C
])
print(f"Directed: {G_directed.number_of_nodes()} nodes, {G_directed.number_of_edges()} edges")

# In-degree and out-degree for directed graph
for node in G_directed.nodes():
    in_d = G_directed.in_degree(node)
    out_d = G_directed.out_degree(node)
    print(f"{node}: in-degree={in_d}, out-degree={out_d}")

Weighted graphs

A weighted graph assigns a numerical weight $w(u, v) \in \mathbb{R}$ to each edge:

$G_{\text{weighted}} = (V, E, w) \quad \text{where } w: E \to \mathbb{R}$

# Weighted graph: transportation network with distances
G_weighted = nx.Graph()
G_weighted.add_weighted_edges_from([
    ('NYC', 'Boston', 215),    # 215 miles
    ('NYC', 'DC', 225),
    ('Boston', 'DC', 440),
    ('DC', 'Atlanta', 640)
])

# Access weights
for u, v, data in G_weighted.edges(data=True):
    print(f"{u} -- {v}: {data['weight']} miles")

# Weighted adjacency matrix
A = nx.to_numpy_array(G_weighted)
print("Weighted adjacency matrix:")
print(A)

Part 2 - Degree and Degree Sequences

Vertex degree

The degree $\deg(v)$ of a vertex $v$ is the number of edges incident to it.

For an undirected graph: $\deg(v) = |\{u \in V : \{u, v\} \in E\}|$

Handshaking lemma: $\sum_{v \in V} \deg(v) = 2|E|$ (each edge contributes 2 to the total degree).

For directed graphs:

• In-degree $\deg^-(v)$: number of edges pointing to $v$
• Out-degree $\deg^+(v)$: number of edges pointing from $v$

import numpy as np
import networkx as nx

# Degree analysis of a graph
G = nx.karate_club_graph()  # Classic social network dataset
degrees = dict(G.degree())

print(f"Nodes: {G.number_of_nodes()}")
print(f"Edges: {G.number_of_edges()}")
print(f"Average degree: {np.mean(list(degrees.values())):.2f}")
print(f"Max degree: {max(degrees.values())}")
print(f"Min degree: {min(degrees.values())}")

# Degree sequence (sorted list of all degrees)
degree_sequence = sorted(degrees.values(), reverse=True)

# Degree distribution
from collections import Counter
degree_dist = Counter(degree_sequence)
print("\nDegree distribution:")
for d, count in sorted(degree_dist.items())[:8]:
    print(f"  degree {d}: {count} nodes")

ML connection: degree as a node feature

In GNNs, node degree is one of the most commonly used features:

import torch
from torch_geometric.data import Data
from torch_geometric.utils import degree

# Create a PyTorch Geometric graph
edge_index = torch.tensor([[0, 1, 1, 2, 2, 3],
                            [1, 0, 2, 1, 3, 2]], dtype=torch.long)

# Compute degree as node feature
row, col = edge_index
deg = degree(row, num_nodes=4)
print(f"Node degrees: {deg}")  # tensor([1., 2., 2., 1.])

# Use degree as initial node features
x = deg.unsqueeze(-1).float()  # Shape: (4, 1)
data = Data(x=x, edge_index=edge_index)

Part 3 - Paths, Walks, and Cycles

Walks, paths, and trails

A walk of length $k$ from $u$ to $v$: a sequence of vertices $u = v_0, v_1, \ldots, v_k = v$ where $(v_i, v_{i+1}) \in E$ for all $i$. Vertices and edges may repeat.

A trail: a walk where no edge is repeated (but vertices may repeat).

A path: a walk where no vertex is repeated (and therefore no edge is repeated).

A cycle: a walk that starts and ends at the same vertex, with no repeated vertices in between (except start = end).

Why paths and cycles matter in ML

import networkx as nx

G = nx.Graph()
G.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,0),(0,2)])

# Shortest path between nodes
shortest = nx.shortest_path(G, source=1, target=4)
print(f"Shortest path 1→4: {shortest}")  # [1, 0, 4] or [1, 2, 3, 4]

# Path length
length = nx.shortest_path_length(G, source=1, target=4)
print(f"Shortest path length: {length}")

# All simple paths (useful for feature extraction)
all_paths = list(nx.all_simple_paths(G, source=0, target=3, cutoff=4))
print(f"All simple paths 0→3 (length ≤ 4): {all_paths}")

# Check for cycles
print(f"Graph has cycles: {not nx.is_forest(G)}")
cycles = nx.cycle_basis(G)
print(f"Fundamental cycles: {cycles}")

ML connection - GNNs and path information: A GNN with $k$ layers aggregates information from $k$-hop neighborhoods. Paths of length $k$ between nodes determine what information flows. Understanding path structure helps design receptive field sizes.

Part 4 - Graph Connectivity

Connected components

A graph is connected if there is a path between every pair of vertices.

A connected component is a maximal connected subgraph.

import networkx as nx

# Graph with multiple components
G = nx.Graph()
G.add_edges_from([(0,1),(1,2),(2,0)])  # Component 1: triangle
G.add_edges_from([(3,4),(4,5)])         # Component 2: path

print(f"Connected: {nx.is_connected(G)}")

components = list(nx.connected_components(G))
print(f"Number of components: {len(components)}")
for i, comp in enumerate(components):
    print(f"Component {i+1}: nodes {comp}")

# Largest connected component (common preprocessing step)
largest_cc = max(nx.connected_components(G), key=len)
G_lcc = G.subgraph(largest_cc).copy()
print(f"Largest component: {G_lcc.number_of_nodes()} nodes")

Strong and weak connectivity (directed graphs)

For digraphs:

• Weakly connected: Connected when edge directions are ignored
• Strongly connected: Path exists from every vertex to every other vertex

G_dir = nx.DiGraph()
G_dir.add_edges_from([(0,1),(1,2),(2,0),(3,2)])  # 3→2 but not 2→3

print(f"Weakly connected: {nx.is_weakly_connected(G_dir)}")
print(f"Strongly connected: {nx.is_strongly_connected(G_dir)}")

# Strongly connected components (Tarjan's/Kosaraju's algorithm)
sccs = list(nx.strongly_connected_components(G_dir))
print(f"SCCs: {sccs}")  # [{0,1,2}, {3}]

Part 5 - Special Graph Types and Their ML Applications

Complete graphs

A complete graph $K_n$ has an edge between every pair of vertices: $|E| = n(n-1)/2$.

ML connection: Dense attention in transformers creates a complete directed graph over token positions - every token attends to every other token.

Bipartite graphs

A graph $G = (U \cup V, E)$ is bipartite if vertices can be split into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$ (no edges within $U$ or within $V$).

Equivalent characterization: A graph is bipartite if and only if it has no odd-length cycles.

import networkx as nx

# Bipartite: users on one side, items on the other
B = nx.Graph()
users = ['User1', 'User2', 'User3']
items = ['Item_A', 'Item_B', 'Item_C', 'Item_D']

# Add bipartite attribute for proper handling
B.add_nodes_from(users, bipartite=0)
B.add_nodes_from(items, bipartite=1)
B.add_edges_from([
    ('User1', 'Item_A'), ('User1', 'Item_B'),
    ('User2', 'Item_B'), ('User2', 'Item_C'),
    ('User3', 'Item_A'), ('User3', 'Item_D')
])

print(f"Is bipartite: {nx.is_bipartite(B)}")

# Bipartite projection: user-user graph (connected if they share an item)
from networkx.algorithms import bipartite
user_graph = bipartite.projected_graph(B, users)
print(f"User-user projection edges: {list(user_graph.edges())}")

# Weighted projection: weight = number of shared items
user_graph_weighted = bipartite.weighted_projected_graph(B, users)
for u, v, data in user_graph_weighted.edges(data=True):
    print(f"{u} - {v}: {data['weight']} shared items")

ML applications of bipartite graphs:

• Recommendation systems: user-item interactions
• Document-word co-occurrence: TF-IDF matrices
• Author-paper networks
• Customer-product purchase histories

Trees and DAGs

A tree is a connected acyclic graph: $|E| = |V| - 1$.

A directed acyclic graph (DAG) is a directed graph with no directed cycles.

import networkx as nx

# Tree (parse tree for NLP)
T = nx.DiGraph()
T.add_edges_from([
    ('S', 'NP'), ('S', 'VP'),
    ('NP', 'Det'), ('NP', 'N'),
    ('VP', 'V'), ('VP', 'NP2'),
    ('Det', 'the'), ('N', 'cat'),
    ('V', 'ate'), ('NP2', 'mouse')
])
print(f"Is tree (as directed): {nx.is_tree(T.to_undirected())}")

# DAG: computation graph in neural networks
dag = nx.DiGraph()
dag.add_edges_from([
    ('x1', 'layer1'), ('x2', 'layer1'),
    ('layer1', 'layer2'), ('layer1', 'skip_connection'),
    ('layer2', 'output'), ('skip_connection', 'output')
])
print(f"Is DAG: {nx.is_directed_acyclic_graph(dag)}")
print(f"Topological order: {list(nx.topological_sort(dag))}")

ML applications of DAGs:

• Computation graphs (neural networks, PyTorch autograd)
• Dependency graphs (scheduling tasks)
• Bayesian networks (directed probabilistic graphical models)
• Workflow pipelines (MLOps)

Multigraphs and heterogeneous graphs

A multigraph allows multiple edges between the same pair of vertices.

A heterogeneous graph has multiple types of nodes and/or edges.

import networkx as nx

# Heterogeneous graph: knowledge graph
# Entities can be people, organizations, places
# Relations can be "works_at", "lives_in", "founded_by"
KG = nx.MultiDiGraph()

KG.add_edge('Turing', 'Manchester', relation='works_at')
KG.add_edge('Turing', 'Cambridge', relation='studied_at')
KG.add_edge('Manchester', 'UK', relation='located_in')

# Multiple relations between same entities
KG.add_edge('DeepMind', 'Google', relation='acquired_by')
KG.add_edge('DeepMind', 'London', relation='headquartered_in')

print(f"Knowledge graph: {KG.number_of_nodes()} entities, {KG.number_of_edges()} relations")

# Query: what are all the relations from Turing?
for _, target, data in KG.out_edges('Turing', data=True):
    print(f"Turing --[{data['relation']}]--> {target}")

Part 6 - Graph Properties for ML Feature Engineering

Centrality measures

Centrality quantifies the "importance" of a node. Different definitions capture different notions of importance:

import networkx as nx
import numpy as np

G = nx.karate_club_graph()

# Degree centrality: fraction of nodes connected to v
degree_central = nx.degree_centrality(G)

# Betweenness centrality: fraction of shortest paths passing through v
betweenness_central = nx.betweenness_centrality(G)

# Closeness centrality: inverse average shortest path to all other nodes
closeness_central = nx.closeness_centrality(G)

# PageRank: probability of landing on node in random walk
pagerank = nx.pagerank(G, alpha=0.85)

# Eigenvector centrality: importance based on importance of neighbors
try:
    eigen_central = nx.eigenvector_centrality(G)
except nx.PowerIterationFailedConvergence:
    eigen_central = {v: 0 for v in G.nodes()}

# Combine into a feature vector per node
nodes = sorted(G.nodes())
features = np.array([
    [degree_central[n],
     betweenness_central[n],
     closeness_central[n],
     pagerank[n]]
    for n in nodes
])
print(f"Graph feature matrix shape: {features.shape}")  # (34, 4)
print(f"These can be used as node features in downstream ML")

Local graph features

import networkx as nx

G = nx.karate_club_graph()

def local_graph_features(G, node):
    """
    Compute local graph features for a node.
    These are standard features used in graph ML before GNNs.
    """
    neighbors = set(G.neighbors(node))
    deg = len(neighbors)

    # Clustering coefficient: fraction of neighbor pairs that are connected
    clustering = nx.clustering(G, node)

    # Triangle count: number of triangles the node participates in
    triangles = nx.triangles(G, node)

    # Average neighbor degree
    avg_neighbor_deg = np.mean([G.degree(n) for n in neighbors]) if deg > 0 else 0

    # Eccentricity: max shortest path to any other node
    try:
        eccentricity = nx.eccentricity(G, node)
    except nx.NetworkXError:
        eccentricity = -1  # Disconnected graph

    return {
        'degree': deg,
        'clustering': clustering,
        'triangles': triangles,
        'avg_neighbor_degree': avg_neighbor_deg,
        'eccentricity': eccentricity
    }

# Compute for all nodes
for node in list(G.nodes())[:5]:
    features = local_graph_features(G, node)
    print(f"Node {node}: {features}")

Part 7 - Graph Types in Production ML Systems

Citation networks

Used in academic paper recommendation, community detection, and link prediction:

# Citation network properties:
# - Directed (paper A cites paper B)
# - Acyclic (you can't cite a future paper - mostly DAG)
# - Temporal (edges have timestamps)
# - Node features: title/abstract embeddings, author info
# - Edge features: context of citation (background, comparison, etc.)

# Common datasets: Cora (2708 papers, 7 classes),
# CiteSeer (3312 papers, 6 classes), ogbn-arxiv (169K papers)

Molecular graphs

Used in drug discovery and materials property prediction:

from rdkit import Chem
import numpy as np

def mol_to_graph_features(smiles: str) -> dict:
    """
    Convert molecule SMILES to graph features.
    Used in molecular property prediction GNNs.
    """
    mol = Chem.MolFromSmiles(smiles)
    if mol is None:
        return None

    # Node features (atoms)
    atom_features = []
    for atom in mol.GetAtoms():
        features = {
            'atomic_num': atom.GetAtomicNum(),
            'degree': atom.GetDegree(),         # bond degree
            'formal_charge': atom.GetFormalCharge(),
            'is_aromatic': int(atom.GetIsAromatic()),
            'hybridization': int(atom.GetHybridization()),
        }
        atom_features.append(features)

    # Edge features (bonds)
    edge_list = []
    edge_features = []
    for bond in mol.GetBonds():
        i = bond.GetBeginAtomIdx()
        j = bond.GetEndAtomIdx()
        bond_type = int(bond.GetBondTypeAsDouble())  # 1, 2, 3

        # Undirected: add both directions
        edge_list.extend([(i, j), (j, i)])
        edge_features.extend([{'bond_type': bond_type}] * 2)

    return {
        'nodes': atom_features,
        'edges': edge_list,
        'edge_features': edge_features,
        'n_nodes': mol.GetNumAtoms(),
        'n_edges': len(edge_list)
    }

# Example: Aspirin
aspirin = mol_to_graph_features('CC(=O)Oc1ccccc1C(=O)O')
print(f"Aspirin: {aspirin['n_nodes']} atoms, {aspirin['n_edges']} bonds")

Interview Questions

Q1: What is the difference between a walk, a trail, and a path in graph theory? Why does this matter for GNNs?

Walk: A sequence of vertices $v_0, v_1, \ldots, v_k$ where $(v_i, v_{i+1}) \in E$. Vertices and edges may repeat. Example: $0 \to 1 \to 2 \to 1$ is a valid walk.

Trail: A walk where no edge is repeated, but vertices may repeat.

Path: A walk where no vertex is repeated (simplest - also means no edge repeats).

Cycle: A walk that starts and ends at the same vertex, no intermediate vertex repeats.

Why this matters for GNNs:

A $k$-layer GNN aggregates messages from the $k$-hop neighborhood. The information flowing through the network follows all walks of length $k$ from each node (not just simple paths). Two nodes connected by many short walks (even if they share paths) will have high mutual influence in the message-passing process.

This matters for over-smoothing analysis: in a graph with many short cycles (high clustering), messages from distant nodes can reach a target via many redundant walks, causing features to converge quickly - even in shallow GNNs. In tree-like graphs (no cycles), $k$-layer GNNs have a well-defined $k$-hop neighborhood - cleaner analysis.

The Weisfeiler-Leman graph isomorphism test (which bounds GNN expressiveness) also operates by detecting cycles and structural patterns - walks and paths are the unit of analysis.

Q2: Why are bipartite graphs especially important in recommendation systems?

A recommendation system fundamentally deals with interactions between two different types of entities: users and items. These naturally form a bipartite graph $G = (U \cup I, E)$ where:

• $U$: set of users
• $I$: set of items (products, movies, songs)
• $E$: user-item interactions (purchases, ratings, views)

Why bipartite structure matters:

1. No user-user or item-item edges in the raw interaction graph - users connect only through items and vice versa. This sparsity (most user-item pairs have no interaction) calls for sparse matrix representations.

2. Matrix factorization interpretation: The bipartite graph's biadjacency matrix $R$ (users × items) is the interaction matrix. Collaborative filtering decomposes $R \approx UV^T$ - finding latent representations for both sides simultaneously.

3. GNN approach: LightGCN and similar models propagate messages on the bipartite graph - users aggregate from their interacted items, items aggregate from their interacting users. Several rounds of propagation capture higher-order collaborative signals.

4. Cold start: New users/items have no edges - the bipartite graph makes the cold start problem explicit: isolated nodes with no connections cannot receive any graph-based information.

Bipartite projection: The user-user projection (connected if they share items) enables user similarity computation - this is the foundation of user-based collaborative filtering.

Q3: What is a directed acyclic graph (DAG) and where does it appear in ML systems?

A DAG is a directed graph with no directed cycles - you cannot start at a node and follow directed edges to return to the same node.

Key property: DAGs have a topological ordering - a linear ordering of vertices such that every edge goes from earlier to later in the ordering.

ML system appearances:

1. PyTorch/TensorFlow computation graphs: Every neural network's forward pass creates a DAG. Nodes are operations, edges are data flow. Backpropagation processes this DAG in reverse topological order.

2. Bayesian networks: Probabilistic graphical models where nodes are random variables and edges are direct dependencies. The DAG structure encodes conditional independence assumptions: $P(X_1, \ldots, X_n) = \prod_i P(X_i | \text{parents}(X_i))$.

3. MLOps pipelines: Data preprocessing → feature engineering → training → evaluation → deployment. Each step depends on previous steps - a DAG of tasks. Tools like Airflow, Kubeflow, and Metaflow model pipelines as DAGs.

4. Knowledge distillation: Teacher → student training with intermediate outputs creates a DAG of model dependencies.

5. Version control (git): Commits form a DAG - each commit has parent commits, no commit is its own ancestor.

Q4: What are the different centrality measures and when would you use each as a feature?

Centrality	Definition	Complexity	Use in ML
Degree	Number of neighbors	$O(1)$	Base feature for any node
Betweenness	Fraction of shortest paths passing through node	$O(n \cdot m)$	Identify broker/bridge nodes in knowledge graphs
Closeness	$1 / \text{avg. shortest path length}$	$O(n \cdot m)$	Access to information, propagation speed
PageRank	Random walk stationary probability	$O(k \cdot m)$	Importance in directed graphs, web/citation networks
Eigenvector	Importance based on neighbor importance	$O(n^2)$ iterative	Identify influencers in social networks

When to use each:

• Degree centrality: Always include. Cheap, informative. Degree 1 nodes (leaves) and high-degree hubs behave very differently in GNNs.

• Betweenness centrality: Use when "information bridge" role matters - detecting bottlenecks in communication networks, finding entities that connect communities in knowledge graphs. Expensive for large graphs - approximate with sampling.

• PageRank: Use for directed graphs where not all edges are equal (web links, citations). Captures recursive importance: a node is important if important nodes link to it.

• Clustering coefficient: Use in social/biological networks. High clustering = dense local community structure, which affects how GNN features propagate.

Feature engineering workflow: Compute centrality features → use as initial node features $X$ in GNN, or as features in XGBoost for non-GNN graph tasks.

Q5: How does the structure of a knowledge graph differ from a citation network, and what does this mean for GNN design?

Citation networks:

• Homogeneous: one node type (papers), one edge type (citations)
• Directed (A cites B)
• Mostly acyclic (temporal ordering)
• Node features: title/abstract text embeddings
• Task: node classification (research area), link prediction (will A cite B?)

Knowledge graphs:

• Heterogeneous: multiple node types (people, organizations, concepts, places)
• Multiple edge types (works_at, founded, located_in, etc.)
• Edges have semantics that distinguish them
• Task: link prediction (is relation r true between entity e1 and e2?)

GNN design consequences:

For citation networks: Homogeneous GNNs (GCN, GraphSAGE, GAT) work directly. Standard message passing over a single node/edge type.

For knowledge graphs: Heterogeneous GNNs are needed:

1. Relational GCN (RGCN): Separate weight matrix $W_r$ per relation type $r$ $h_v^{(l+1)} = \sigma\left(\sum_r \sum_{u \in \mathcal{N}_r(v)} \frac{1}{c_{v,r}} W_r^{(l)} h_u^{(l)}\right)$

2. HAN (Heterogeneous Attention Network): Meta-path based aggregation - define paths like "Paper-Author-Paper" and use attention over paths.

3. Transductive methods (TransE, RotatE): Represent entities and relations as vectors in a geometric space, not as GNNs at all - often more practical for pure link prediction.

The key insight: edge type information is lost in a simple adjacency matrix. You need either separate adjacency matrices per relation type, or edge features in the GNN.

Quick Reference

Graph Type	Key Property	ML Application
Undirected	$(u,v) = (v,u)$	Social networks, molecular graphs
Directed (digraph)	$(u,v) \neq (v,u)$	Citation networks, knowledge graphs
Weighted	$w: E \to \mathbb{R}$	Transportation, similarity networks
Complete $K_n$	All pairs connected	Dense attention
Bipartite	Two disjoint node sets	Recommendation, co-occurrence
Tree	Connected, acyclic	Parse trees, decision trees
DAG	Directed, acyclic	Computation graphs, Bayesian nets
Multigraph	Multiple edges between same pair	Knowledge graphs (multiple relations)

Property	Formal Definition	Check (NetworkX)
Connected	Path between every pair	nx.is_connected(G)
Acyclic	No cycles	nx.is_forest(G)
Bipartite	Two-colorable	nx.is_bipartite(G)
DAG	Directed + acyclic	nx.is_directed_acyclic_graph(G)

Next: Lesson 02: Graph Representations →

:::tip 🎮 Interactive Playground

Visualize this concept: Try the Graph Explorer demo on the EngineersOfAI Playground - no code required.

:::