Comparing Graphs: Why Structure Matters

Comparing two graphs is not as straightforward as comparing two strings or
two literals since graphs are composed of nodes and relationships and they can
only be compared against their structure that is their essence. So, when you
compare two graphs, it is not the labels of their nodes that matters, but the
shape of their connections. There are many tools in graph theory that we can
use to detect when two graphs share the same structure or even where a single
graph contains repeated internal patterns. We will discuss two of them in detail
here: Graph Isomorphism and Graph automorphism while also listing the
others to be covered in other articles.

Graph Isomorphism — When Two
Graphs Are “The Same”

Graph isomorphism is a structural comparison between two graphs. Two graphs
𝐺 and H are isomorphic if you can rename the vertices of 𝐺 so that it becomes
exactly H. For example in Figure 1 below, the two graphs are isomorphic.

An isomorphic graph preserves adjacency even while the vertices are relabelled.
If one graph labels nodes as A-B-C, and another labels them 1-2-3, but the
connections match, they are isomorphic. Thus, from the figure, the
permutations remain the same:

1 → 4, 2 → 6, 3 → 2, 4 → 5, 5 → 1, 6 → 3

Analysis

Let us compare the adjacency structure of the two graphs in Figure 1:
The visible edges are 1-2, 1-3, 2-3, 3-5, 5-6, 6-4, 4-2

So, across the two graphs in Figure 1, we find one isomorphism. An isomorphism is just a specific (one among the many that are possible) mapping between the vertices of the two graphs. There could be many more.

In the left graph in Figure 1, vertices 2 and 3 play similar roles:
they both have degree 3, both belong to the triangle, both connect to the rest of the graph.

Why does isomorphism matter at all?

Because it tells you whether two datasets, networks, or shapes are fundamentally the same. It tells us whether two graphs are identical keep apart superficial differences like naming or ordering. It is similar to comparing to two tables or data frames and there are many use cases for this.

For instance, it is essential in Chemistry (same molecule, different drawing), pattern recognition, and canonical graph labelling for algorithms.

Graph Automorphism — Or the Symmetry within a Graph

Graph automorphism is an isomorphism from a graph to itself. An
automorphism is a vertex permutation that preserves all edges. In other words,
it is a symmetry of the graph.
If structurally equivalent vertices can be identified, algorithms can avoid
repeating identical calculations.

This graph is symmetric about its center. Swapping the following permutations
2 ↔ 3, 4 ↔ 5
while keeping 1 and 6 fixed is an automorphism highlighting the structural equivalence of the combination.

Why does it matter?

If structurally equivalent vertices can be identified, algorithms can avoid
repeating identical calculations.

• It reveals symmetry inside the graph.
• It helps identify repeated or interchangeable structures.
• Automorphism groups are used in:
  • detecting structural redundancy,
  • compressing graphs

How Isomorphisms and Automorphisms Help Identify
Similar Structures

The following are the many ways in which these two concepts help identify similar structures (there are other means that we will list later in the article, but elaborate with examples in other articles).

1. Comparing two graphs

Isomorphisms tell you whether two graphs represent the same
underlying structure.

2. Finding repeated patterns inside one graph

Automorphisms reveal which nodes or substructures are interchangeable. This
helps identify sub-nodes within a larger network for deeper analysis. This is critical in identifying some of the numerical features to analyse and compare graphs.

3. Detecting motifs

Isomorphisms between subgraphs help identify repeated motifs (e.g., triangles,
cycles). This is one of the central concept employed in financial fraud detection. We will be elaborating this in another article.

4. Canonical forms

Both concepts help convert graphs into a canonical representation, making
comparison easy when required as part of a larger workflow. If two graphs are actually the same structure (even if their nodes are labeled differently or drawn differently), converting them into a canonical form makes them look identical.

Normally, comparing two graphs directly can be difficult because:

• Nodes may have different names.
• The graphs may be drawn differently.
• The order of nodes and edges may vary.

By converting each graph into a canonical representation, you get a standardized version of each graph.

Graphlets

Now we come to next major building block in graph theory. Graphlets are small, fixed‐size induced subgraphs (typically 3–5 nodes) used to capture local structural patterns in a larger graph. They are widely used in
network biology, graph mining, and structural comparison. Automorphisms
also define the orbits of nodes inside graphlets, which is essential for
graphlet‐based comparison.

A graphlet is a small induced subgraph pattern. Examples include:

• 3‐node path
• 3‐node triangle
• 4‐node square
• 4‐node star
• 5‐node clique

Graphlets are used to characterize local structure. For example, in biology,
graphlets help compare protein‐interaction networks by counting how often
each pattern appears. The Figure 3 shows the most common graphlets that
are analysed.

Orbits: The Link Between
Automorphisms and Graphlets

Orbits are the bridge that connects symmetry (automorphisms) with pattern
analysis (graphlets). They tell us which nodes inside a graphlet are
structurally identical and which ones play distinct roles. Understanding
orbits help clarify how graphlets capture structural roles and why looking at
automorphisms matter.

What is an Orbit?

An orbit is a set of vertices that are interchangeable under the automorphisms of
a graph.
If two vertices lie in the same orbit, there exists an automorphism that maps
one to the other. This means they occupy equivalent structural positions.

Why Orbits matter?

Orbits tell us which nodes are structurally identical and which nodes are
fundamentally different. This is crucial for:

• distinguishing roles inside graphlets
• counting graphlets correctly
• building graphlet degree vectors
• comparing graphs using graphlet‐based methods
• understanding symmetry in networks

Without orbits, graphlets would lose their ability to differentiate subtle
structural patterns.

Orbits Inside Graphlets: Why they are important

When graphlets are counted, they are not considered as whole patterns. Instead,
each node in a graphlet belongs to a specific orbit, and it is the orbit that defines
the role that a node plays within the graphlet.

Graphlet Degree Vectors (GDVs)

A Graphlet Degree Vector (GDV) is a way of describing the local topology around
a node in a network. Within a graphlet, nodes can occupy different structural
positions called automorphism orbits (or simply orbits).

A GDV counts how many times a node in the large graph participates in each
orbit of each graphlet. This is far more expressive than simply counting motifs.

Visual Explanation

A GDV entry is not a property of the node itself . It is:

The number of graphlets of a particular type in which the node
appears in a particular position. So to compute any entry, you
enumerate the graphlets around the node and count how many
times the node occupies that orbit.
That’s why GDV is often described as a detailed structural fingerprint of
a node.

Why this matters

• Two nodes may participate in the same number of triangles, but in
  different roles.
• Orbits allow graphlets to capture these differences.
• This is why graphlets outperform motif counts in biological network comparison.

The Link between Orbits,
Automorphisms and Graphlets

The following helps understand the link between the concepts we discussed in
this article:

• Automorphisms describe the symmetries of a graphlet.
• These symmetries partition graphlet nodes into orbits.
• Orbits define distinct structural roles inside each graphlet.
• Graphlet‐based methods count how often each node in a large graph
  appears in each orbit.
• These orbit counts form graphlet degree vectors, which are used to
  compare graphs.
• Orbits are the glue that makes graphlets structurally meaningful

Summary and Next Steps

In this article, we explored the foundations of graph analysis and the role of canonical representations in simplifying graph comparison and structural interpretation. We also introduced graphlets as powerful building blocks for capturing local connectivity patterns within complex networks. By examining how graphlets characterize structural signatures that may not be evident through traditional network metrics, we highlighted their value in uncovering hidden relationships, anomalies, and behavioural patterns in graph data.

The concepts presented here provide the theoretical groundwork, the real power of graphlet analysis becomes apparent when applied to real-world datasets. As a follow-up, I will be discussing a hands-on exercise that demonstrates graphlet-based analysis in R using a financial fraud dataset.

This practical tutorial will guide you through constructing a transaction network, extracting graphlet features, interpreting graphlet distributions, and connect these structural patterns to potentially fraudulent behaviour. The exercise bridges theory and practice, offering a concrete example of how graphlet analytics can be used to derive actionable insights from complex financial networks.

Bibliography

1. Finotelli Paolo, P. C. ,. M. E. ,. D. P. (2021). A Graphlet-Based Topological
   Characterization of the Resting-State Network in Healthy People.
   Frontiers in Neuroscience, 15. https://doi.org/10.3389/fnins.2021.665544 ↩
2. Anida Sarajlić, V. J. N. S. D. R. P. (2013). Network Topology Reveals Key
   Cardiovascular Disease Genes. PLOS One.
   https://doi.org/https://doi.org/10.1371/journal.pone.0071537