AI Glossary / Computer vision and multimodal AI / Beginner

Graph representation

Definition

A graph representation describes entities as vertices and relationships as edges, together with any relevant attributes. It can also refer to the data structure used to store that graph, such as an adjacency list or matrix. The representation determines what relationships a later algorithm can analyze.

What it means

A graph is not just a chart drawn with dots and lines. It is a model of connections. A vertex might represent a person, task, image region or road junction, while an edge records a relationship defined by the application.

There are two design questions. First, what should the vertices and edges mean? Second, how should the graph be stored and processed? A sensible storage format cannot repair a misleading model of the relationships.

The phrase is sometimes used for learned graph embeddings, which encode graph information into vectors. Those are related but different from the basic abstract graph and its storage. A clear explanation should state which meaning is intended.

How it works

The modeler defines the graph type: directed or undirected, weighted or unweighted, and whether multiple edges or self-loops are allowed. Attributes can attach information to vertices, edges or the graph as a whole.

An adjacency list stores each vertex's neighbors. An adjacency matrix stores connection information in a table indexed by vertex pairs. An edge list records edges directly. Each format offers different trade-offs for storage and access.

For a sparse graph with many possible but few actual connections, a dense matrix can waste memory. A list-based representation can store only existing relationships, though particular algorithms may prefer matrix operations. Conversions must preserve vertex identity, direction, weights and isolated vertices where required.

Three practical examples

1. Image analysis: Regions become vertices and shared boundaries become edges, allowing algorithms to reason about neighboring regions.

2. Workflow analysis: Tasks become vertices and dependencies become directed edges. Edge direction is essential because prerequisite and dependent are different roles.

3. Asset systems: Equipment and locations become typed vertices connected by installation or service relationships. The model distinguishes relationship types rather than treating every connection as equivalent.

Think of it this way

Think of a directory that lists each person and their relevant contacts. The directory can be displayed as a drawing or stored as a table without changing the underlying relationships.

The analogy is limited because not every edge is a social contact. Edges can be directional, weighted or typed, and the decision to include one is part of the model rather than an objective property of every dataset.

Worked example

Take an undirected graph with vertices A, B and C and edges A - B and B - C. Its adjacency lists are A: [B], B: [A, C] and C: [B].

With vertex order [A, B, C], its adjacency matrix is [[0, 1, 0], [1, 0, 1], [0, 1, 0]]. The symmetry reflects undirected edges. Its edge list can contain [(A, B), (B, C)].

These formats encode the same simple graph when their conventions are consistent. Add isolated vertex D, however, and an edge list alone does not mention it. The storage must include a separate vertex set or another convention to preserve D. This illustrates how an apparently harmless format conversion can lose information.

Illustrative case study

Fictional case: Willow Operations exports a dependency graph as a list of task pairs. A receiving tool assumes the pairs are undirected, so it can no longer distinguish which task must happen first. It also drops tasks with no dependencies because they never appear in the edge list.

The team revises the exchange specification to include all vertices, explicit edge direction and required attributes. It tests the round trip using a tiny graph with an isolated task and a one-way dependency. The case illustrates preservation of meaning during conversion, not a failure of graph methods themselves.

Common misconceptions and mistakes

A graph drawing is not the complete representation. Visual layout may omit attributes or suggest distances that have no meaning in the model.

Edges do not inherently mean similarity, causation or physical proximity. Their interpretation must be defined.

A numerical vertex identifier does not imply an ordering or distance between vertices. Renumbering should not accidentally change an algorithm's intended meaning.

A zero matrix entry needs a convention. It may mean no edge, while a weighted application could also permit an edge with zero cost. Multigraphs, directed edges and missing attributes require equally explicit handling.

Business use

Graph representations can reveal dependencies and relational structure that ordinary row-based views obscure. Their usefulness depends on capturing the relationships relevant to the decision without adding misleading connections.

Document the graph schema, attribute meanings and missing-data rules. Choose storage according to scale and access needs, and validate conversions with small known examples. Before adopting a graph-learning method, check whether its input representation preserves direction, types and isolated entities that matter to the application.

People also ask

Is every network diagram a graph representation?

It can depict a graph, but the underlying data and connection rules need to be specified for computation.

Which is better, an adjacency list or matrix?

It depends on graph density and the operations required. There is no universally best format.

Is a graph embedding the same as an adjacency matrix?

No. An embedding is a derived vector representation, often learned, while an adjacency matrix directly encodes pairwise connection information under defined conventions.

Check your understanding

A graph export contains only edges. Why might importing it lose a valid entity?

Answer: An isolated vertex appears in no edge, so the edge list may not record it. Preserving the full graph requires a vertex list or another explicit way to include isolated entities.

Related terms

• Directed graph
• vertex
• edge
• adjacency list
• adjacency matrix
• graph embedding
• attributed graph

Learn next

Represent the same small graph as a drawing, adjacency list, matrix and edge list. Include an isolated vertex, a directed edge and an attribute, then check which conventions each format needs. Use that exercise to define a graph schema before analyzing a larger dataset.

More in Computer vision and multimodal AI

• Gradient reversal - Gradient reversal is an image-processing artifact in which a local brightness change reverses direction after processing: a region that originally became...
• Gram matrix - A Gram matrix records the pairwise inner products of a set of vectors.
• Graph cut optimization - Graph cut optimization solves certain labeling problems by constructing a weighted graph whose cuts correspond to candidate solutions.
• Graph-cut segmentation - Graph-cut segmentation divides an image into labeled regions by constructing a weighted graph and finding a cut that minimizes a defined cost.
• Graph isomorphism - Graph isomorphism is a one-to-one correspondence between the vertices of two graphs that preserves their connections.
• Graph kernel - A graph kernel is a function that compares two graphs in a way suitable for kernel-based learning, typically corresponding to an inner product between their...

Sources

Primary documentation: NetworkX, introduction, https://networkx.org/documentation/stable/reference/introduction.html ; tutorial, https://networkx.org/documentation/latest/tutorial . Relevant returned descriptions of adjacency structures, graph types and attributes were reviewed. The three-vertex representation and isolated-vertex example are original illustrations, not a required software schema.

Previous: Graph partitioning Next: Graph search