Continuous Function

Linear Algebra

Graph Theory Basics for GNNs and Graphical Models

Graphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

status: reviewimportance: criticaldifficulty 2/5math: undergraduateread: 18mlive demo
Back to Linear AlgebraNext: Graph Basics: Adjacency, Degree, and Laplacian (review)

Concept Structure

Graph Theory Basics for GNNs and Graphical Models

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

0prerequisites
3next concepts
4related links

Learner Contract

What this page should let you do.

You are here becauseGraphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

This Linear Algebra concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisNo hard prerequisite

No hard prerequisite is listed; start from the intuition and fill gaps only when the notation demands it.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Test the linkManipulate one control and predict the visible change.Then continue to Graph Basics: Adjacency, Degree, and Laplacian (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources5 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptGraph Theory Basics for GNNs and Graphical ModelsLinear AlgebraEquationGraph Theory Basics for GNNs and Graphical Models equation 1Exact equationCodeGraph Theory Basics for GNNs and Graphical Models runnable code 1Exact runnable codeDemoGraph Theory Basics for GNNs and Graphical Models interactive demoInteractive demoClaimA graph can be read as adjacency/degree matrices for ML geometry, whi...Exact claim checkSourceMIT 6.042J Mathematics for Computer Science: Graph TheoryExact source
ConceptGraph Theory Basics for GNNs and Graphical ModelsLinear Algebra
5 sources attachedLocal snapshot ready
concept:linear-algebra/graph-theory-basics
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

A graph is a way to say which things are allowed to talk to which other things.

The things are nodes or vertices. The connections are edges. Once you have those two ingredients, the same object can support several kinds of machine-learning reasoning:

  1. In graph neural networks, neighbors exchange messages.
  2. In spectral methods, the graph becomes matrices such as adjacency, degree, and Laplacian matrices.
  3. In Bayesian networks, a directed acyclic graph gives parent sets for local conditional probabilities.

That is why graph basics belong in the mathematical backbone. They are not decoration around the model. They decide which variables are local, which paths exist, which computations can be parallelized, and which factorizations are legal.

The first mental split is direction.

An undirected edge says two nodes are adjacent:

u−v.u - v.

A directed edge says information or dependence points one way:

u→v.u \to v.

Directed graphs can have directed cycles, such as

A→B→C→A.A\to B\to C\to A.

A directed acyclic graph, or DAG, has no directed cycle. DAGs are special because they can be ordered so every edge points forward. That order is called a topological order.

For probabilistic models, a DAG does one more job: it tells us the parents of each variable. If node XiX_i has parents pa(Xi)\mathrm{pa}(X_i), a Bayesian network uses the scaffold

P(x1,…,xd)=∏i=1dP(xi∣pa(xi)).P(x_1,\ldots,x_d) = \prod_{i=1}^{d}P(x_i\mid \mathrm{pa}(x_i)).

The graph does not magically choose the numbers in those conditional distributions. It chooses the local questions each conditional table, density, or neural conditional model must answer.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1V={v1,…,vn}.V=\{v_1,\ldots,v_n\}.Equation 2Aij={1,if there is an edge vi→vj,0,otherwise.A_{ij} = \begin{cases} 1, & \text{if there is an edge }v_i\to v_j,\\ 0, & \text{otherwise.} \end{cases}

Let G=(V,E)G=(V,E) be a graph. The node set is

V={v1,…,vn}.V=\{v_1,\ldots,v_n\}.

For an undirected graph, each edge is an unordered pair {u,v}\{u,v\}. For a directed graph, each edge is an ordered pair (u,v)(u,v), often drawn as u→vu\to v.

The adjacency matrix A∈{0,1}n×nA\in\{0,1\}^{n\times n} records edges:

Aij={1,if there is an edge vi→vj,0,otherwise.A_{ij} = \begin{cases} 1, & \text{if there is an edge }v_i\to v_j,\\ 0, & \text{otherwise.} \end{cases}

For an undirected graph, AA is symmetric. For a directed graph, AA need not be symmetric.

The out-degree and in-degree of node viv_i are

diout=∑j=1nAij,diin=∑j=1nAji.d_i^{\mathrm{out}}=\sum_{j=1}^{n}A_{ij}, \qquad d_i^{\mathrm{in}}=\sum_{j=1}^{n}A_{ji}.

For an undirected graph, the degree is usually just

di=∑j=1nAij.d_i=\sum_{j=1}^{n}A_{ij}.

The degree matrix is diagonal:

Dii=di.D_{ii}=d_i.

The combinatorial graph Laplacian is

L=D−A.L=D-A.

This matrix is one bridge from graph structure to linear algebra. If xix_i is a value placed on node ii, then a common smoothness quantity is

x⊤Lx=∑{i,j}∈E(xi−xj)2x^\top Lx = \sum_{\{i,j\}\in E}(x_i-x_j)^2

for the undirected version of the graph. The expression is small when adjacent nodes have similar values.

Now switch back to directed graphs. A directed path is a sequence

vi0→vi1→⋯→vikv_{i_0}\to v_{i_1}\to\cdots\to v_{i_k}

where every arrow is present. A directed cycle is a directed path that returns to a node already on the path.

A directed graph is a DAG if it has no directed cycle.

A topological order is an ordering of nodes such that every edge points from an earlier node to a later node. A finite directed graph has a topological order exactly when it is acyclic.

For a Bayesian-network DAG, the parent set of node XiX_i is

pa(Xi)={Xj:Xj→Xi}.\mathrm{pa}(X_i)=\{X_j:X_j\to X_i\}.

The graph supplies the factorization pattern

P(X1,…,Xd)=∏i=1dP(Xi∣pa(Xi)).P(X_1,\ldots,X_d) = \prod_{i=1}^{d}P(X_i\mid \mathrm{pa}(X_i)).

So the same graph object has two useful readings:

  1. matrix reading: adjacency, degree, Laplacian, neighborhoods;
  2. probabilistic reading: parent sets, topological order, local conditionals.
03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1nodes = ["Rain", "Sprinkler", "Wet", "Traffic", "Late"] edges = [("Rain","Sprinkler"), ("Rain...python
nodes = ["Rain", "Sprinkler", "Wet", "Traffic", "Late"]
edges = [("Rain","Sprinkler"), ("Rain","Wet"), ("Rain","Traffic"),
         ("Sprinkler","Wet"), ("Wet","Late"), ("Traffic","Late")]

idx = {node: i for i, node in enumerate(nodes)}
A = [[0] * len(nodes) for _ in nodes]
for u, v in edges:
    A[idx[u]][idx[v]] = 1

parents = {v: [u for u, w in edges if w == v] for v in nodes}
children = {u: [v for w, v in edges if w == u] for u in nodes}
undirected_degree = [
    sum(A[i][j] or A[j][i] for j in range(len(nodes))) for i in range(len(nodes))
]

def creates_cycle(candidate):
    graph = edges + [candidate]
    visiting, done = set(), set()
    def dfs(u):
        if u in visiting: return True
        if u in done: return False
        visiting.add(u)
        for a, b in graph:
            if a == u and dfs(b): return True
        visiting.remove(u); done.add(u)
        return False
    return any(dfs(node) for node in nodes)

print("parents:", parents)
print("children:", children)
print("undirected degree:", dict(zip(nodes, undirected_degree)))
print("Late -> Rain creates cycle?", creates_cycle(("Late", "Rain")))

The code has two views of the same graph. A and the degree list are the matrix view. parents and creates_cycle are the DAG view used by graphical models.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

The DAG Factorization Lab below hides the cycle result, topological order, and factorization ledger until you commit.

Choose one candidate edge. Predict whether adding it creates a directed cycle or keeps the graph acyclic. Then reveal:

  1. the adjacency and parent-set ledger;
  2. the directed path that proves a cycle, if one appears;
  3. a valid topological order when the graph is still a DAG;
  4. the Bayesian-network factorization scaffold for the current graph.

Live Concept Demo

Explore Graph Theory Basics for GNNs and Graphical Models

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 2/5undergraduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Graph Theory Basics for GNNs and Graphical Models should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Graphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Graph Theory Basics for GNNs and Graphical Models should make visible.

Visual Inquiry

Make the image answer a mathematical question

Graphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Graph Theory Basics for GNNs and Graphical Models easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

course-notes · 2010MIT 6.042J Mathematics for Computer Science: Graph TheoryLehman, Leighton, and Meyer

Grounds graph vocabulary including vertices, edges, adjacency, degree, paths, directed graphs, and connectivity.

Open source
course-notes · 2010MIT 6.042J Mathematics for Computer Science: Directed Acyclic Graphs and SchedulingLehman, Leighton, and Meyer

Supports DAG vocabulary, the no-directed-cycle condition, and topological-order scheduling intuition.

Open source
course-notes · 2026Stanford CS224W: Machine Learning with GraphsStanford CS224W

Curriculum anchor for graphs as ML objects represented by nodes, edges, neighborhoods, and adjacency structures.

Open source
course-notes · 2019Stanford CS224W: Spectral ClusteringStanford CS224W

Supports the degree matrix, adjacency matrix, and graph Laplacian as matrix views of graph structure.

Open source
course-notes · 2026Stanford CS228 Notes: Bayesian NetworksStanford CS228

Supports directed acyclic graphs as Bayesian-network structure and the product of local conditionals over parent sets.

Open source

Claim Review

Graphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources5 references

mit-6042-graph-theory, mit-6042-dags, cs224w-graph-representation, cs224w-spectral-clustering, cs228-bayesian-networks

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedA graph can be read as adjacency/degree matrices for ML geometry, while a directed acyclic graph also supplies parent sets and a topological order for Bayesian-network factorization.Claim metadata: source checked

The sources support the page's distinction between graph structure, matrix representation, path/cycle reasoning, DAG validity, topological orders, and using parents in a DAG to write a Bayesian-network product.

Sources: MIT 6.042J Mathematics for Computer Science: Graph Theory, MIT 6.042J Mathematics for Computer Science: Directed Acyclic Graphs and Scheduling, Stanford CS224W: Machine Learning with Graphs, Stanford CS224W: Spectral Clustering, Stanford CS228 Notes: Bayesian NetworksFinite five-node teaching graph only; excludes spectral graph theory beyond the first Laplacian identity, graph isomorphism, random graphs, advanced GNN message passing, and full Bayesian-network inference.A bounded review summary is present; still check caveats and exact reference scope.

Checked MIT graph notes for vertices, edges, adjacency, degree, paths, directed graph vocabulary, and DAG/topological-order intuition; checked CS224W context for graph ML representations and Laplacian matrices; checked CS228 for Bayesian-network DAGs and parent-set factorization. GPT Pro publication critique remains pending.

Reviewer: codex-local-source-review; reviewed 2026-07-02
source-span-mit-6042-graph-theorysource-span-cs224w-spectral-clusteringsource-span-cs228-bayesian-networksEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

course-notes 2010MIT 6.042J Mathematics for Computer Science: Graph Theory

Grounds graph vocabulary including vertices, edges, adjacency, degree, paths, directed graphs, and connectivity.

course-notes 2010MIT 6.042J Mathematics for Computer Science: Directed Acyclic Graphs and Scheduling

Supports DAG vocabulary, the no-directed-cycle condition, and topological-order scheduling intuition.

course-notes 2026Stanford CS224W: Machine Learning with Graphs

Curriculum anchor for graphs as ML objects represented by nodes, edges, neighborhoods, and adjacency structures.

course-notes 2019Stanford CS224W: Spectral Clustering

Supports the degree matrix, adjacency matrix, and graph Laplacian as matrix views of graph structure.

Mechanism checks

Equation 1
V={v1,…,vn}.V=\{v_1,\ldots,v_n\}.
Equation 2
Aij={1,if there is an edge vi→vj,0,otherwise.A_{ij} = \begin{cases} 1, & \text{if there is an edge }v_i\to v_j,\\ 0, & \text{otherwise.} \end{cases}
Runnable code 1nodes = ["Rain", "Sprinkler", "Wet", "Traffic", "Late"] edges = [("Rain","Sprinkler"), ("Rain...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Graphs are nodes plus edges; adjacency, degree, paths, cycles, DAGs, topological orders, and Laplacians are the shared vocabulary behind GNNs and graphical models.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Graph Theory Basics for GNNs and Graphical Models.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptGraph Theory Basics for GNNs and Graphical ModelsLinear Algebra
Runnable code comparisonGraph Theory Basics for GNNs and Graphical Models runnable code 1nodes = ["Rain", "Sprinkler", "Wet", "Traffic", "Late"] edges = [("Rain","Sprinkler"), ("Rain...Prediction before revealGraph Theory Basics for GNNs and Graphical Models interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Graph Theory Basics for GNNs and Graphical Models click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptLinear Algebra

Graph Theory Basics for GNNs and Graphical Models

Attached question

What is the smallest example that makes Graph Theory Basics for GNNs and Graphical Models click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Graph Theory Basics for GNNs and Graphical Models Selected item key: recorded for copy. Context: Linear Algebra Page anchor: recorded for copy. Open question: What is the smallest example that makes Graph Theory Basics for GNNs and Graphical Models click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/linear-algebra/graph-theory-basics concept:linear-algebra/graph-theory-basics