AI Glossary / Graphs and symbolic AI / Intermediate

Graph

Definition

A graph is a mathematical structure made of vertices, also called nodes, and edges that represent relationships between them. In AI, nodes can represent entities, states, variables, or other objects, while edges encode a chosen kind of connection. The meaning of the graph depends on what its creator chooses to model.

What it means

Graphs make relationships explicit. A table may describe each item separately; a graph can also describe which items connect, depend on one another, or interact. This supports tasks such as finding paths, identifying groups, and learning from linked data.
The word here does not mean a bar chart or simply the plotted curve of a function. A node-and-edge graph can be drawn, but the drawing is only one representation. Moving nodes around on the page does not change the underlying graph unless the modeled nodes or edges themselves change.

How it works

Specify the node set and the rule for creating edges. Choose whether edges are directed, whether repeated edges are allowed, and whether a node may connect to itself. Attach attributes when needed, such as a node category or an edge capacity.
An undirected edge expresses a symmetric connection. A directed edge distinguishes source from destination. Weighted graphs attach numbers to edges or nodes, but those numbers require interpretation: distance, similarity, cost, and capacity are different quantities. Algorithms consume a representation such as adjacency lists, an adjacency matrix, or an edge list, with tradeoffs in storage and access.

Three practical examples

• A recommendation model connects users with items they interacted with, preserving the interaction's defined meaning.
• A planning system represents states as nodes and possible transitions as directed edges.
• A knowledge representation stores entities and labeled relationships, supporting queries that follow specific kinds of links.

Think of it this way

Think of a map of locations connected by lines, where each line has a stated meaning. This captures entities and relationships. The analogy is limited because graph nodes need not be physical places, edges need not be roads, and geometric closeness in a drawing need not imply any connection or similarity in the data.

Worked example

Create a simple undirected graph with nodes A, B, C, and D and edges AB, AC, and BC. Nodes A, B, and C form a triangle, while D is isolated. Each triangle node has degree 2, and D has degree 0. The degree sum is 6, equal to twice the three edges because each undirected edge contributes at both endpoints.
There is a path from A to C, including the direct edge AC and the two-edge route A-B-C. There is no path from A to D. If only the three edge records are stored, D may disappear unless the node inventory is recorded separately.
Now interpret AB as the directed edge A → B. The direction matters: that edge alone permits following the relationship from A to B, but says nothing about a reverse B → A edge. A change in graph type can therefore change both the model and the answers to path queries.

Illustrative case study

In a fictional learning platform, the Birch team draws connections between lessons whenever they share a tag. A reviewer assumes the arrows mean prerequisite relationships and recommends a learning order that the graph never supported.
The team creates separate relation types for shared topics and prerequisites, documenting how each is obtained. It also retains lessons with no links rather than dropping them from the dataset. The invented case illustrates semantic clarity in graph construction. It does not claim that a particular graph representation improves learning outcomes.

Common misconceptions and mistakes

An edge does not automatically mean causation, similarity, or mutual influence. Its meaning must be defined. A missing edge can mean no relationship, an unobserved relationship, or a relation omitted by the construction rule.
Do not assume that every graph is connected, undirected, or simple. A tree is a particular kind of graph, not a synonym for all graphs. Also avoid interpreting a visually central node as mathematically central without specifying a centrality measure. Layout software can place nodes for readability rather than analytical meaning.

Business use

Graphs are useful when relationships are central to the question: dependencies, interactions, transitions, and associations can all be modeled explicitly. They can support explanation by showing a path or neighborhood relevant to a result.
The main modeling work is deciding what nodes and edges mean and how they are observed. Record direction, time range, duplicate handling, and attribute definitions. Before applying a graph algorithm, check that its assumptions match the representation. A shortest-path method using a similarity weight as though it were a distance may answer the wrong question even if the computation runs correctly.

People also ask

Does a graph need a visual drawing?

No. It can be stored and analyzed entirely as data.

Can two nodes have more than one edge between them?

In a multigraph, yes; a simple graph does not permit repeated edges of the same basic kind.

Are isolated nodes part of a graph?

Yes, if included in the node set. They have no incident edges but can still be meaningful entities.

Check your understanding

Why does the triangle example have four nodes but only three nodes visible in a bare edge list?

Answer: D is isolated and appears in no edge record. Preserving the full graph requires a separate node declaration or another representation that includes D explicitly.

Related terms

• Node
• Directed graph
• Undirected graph
• Weighted graph
• Path
• edge
• multigraph
• adjacency matrix
• connected component
• knowledge graph

Learn next

Learn next about graph representations. Store the example as an adjacency list and an adjacency matrix, keeping D visible in both. Then assign a meaning to an edge weight and explain whether a larger number should make a connection more attractive or more costly for the task you want to solve.

• Edge weight

More in Graphs and symbolic AI

• Goal test - A goal test is a procedure that determines whether a candidate state satisfies the goal of a search or planning problem.
• Gomory-Hu Tree - A Gomory-Hu tree is a weighted tree that compactly represents the minimum cut values between every pair of vertices in an undirected capacitated graph.
• Grammar - A grammar is a formal description of how valid expressions can be structured in a language.
• Graph clustering - Graph clustering groups data points represented as nodes of a graph using the relationships encoded by its edges.
• Graph coloring - Graph coloring assigns labels, traditionally called colors, to graph elements under specified compatibility rules.
• Graph Convolutional Network - A Graph Convolutional Network, or GCN, is a neural-network architecture that learns representations using a graph's connections together with features...

Sources

NetworkX official graph-class documentation: https://networkx.org/documentation/stable/reference/classes/index.html Aalto Dictionary of Machine Learning, graph-related definitions: https://aaltodictionaryofml.github.io/ADictML_Main.pdf

Previous: Granular computing Next: Graph clustering