AI Glossary / Graphs and symbolic AI / Intermediate
Graph Hashing
Definition
Graph hashing converts a graph's selected structural and attribute information into a compact identifier. The entry focuses on Weisfeiler-Lehman graph hashing, which repeatedly summarizes node neighborhoods before producing a graph-level digest. It is useful for grouping possible duplicates, but an equal hash does not prove that two graphs are identical or isomorphic.
What it means
A graph can be stored with different node names or insertion orders while representing the same relationships. A structural hash aims to ignore such incidental differences, subject to the method's assumptions. It can give a quick comparison key for a large collection of graph objects.
The word selected matters: ignored attributes cannot affect the result. A graph with red equipment and another with blue equipment may receive the same structural hash if equipment color is excluded. Decide whether the intended comparison concerns topology alone, labeled structure, or some other definition of equivalence before creating identifiers.
How it works
In the Weisfeiler-Lehman approach, each node starts with a label derived from chosen attributes or structural information. Each refinement round combines its current label with a summary of neighboring labels. Repeated rounds incorporate increasingly extended neighborhood information. A graph-level summary of the resulting labels is then hashed.
NetworkX exposes choices including node attributes, edge attributes, refinement iterations, and digest size. Store these settings with the result. Its documentation also records behavior changes affecting hashes across versions. Comparing outputs produced under different configurations or implementations may therefore be meaningless, even when the input graphs are equivalent.
Three practical examples
- A workflow library groups candidate duplicate dependency graphs by hash, then checks equivalence inside each group.
- A graph-dataset curator uses labeled structural fingerprints to find records that deserve closer duplication review.
- A development team tests whether renaming node identifiers changes a fingerprint that is intended to depend only on structure.
Think of it this way
Think of a graph hash as a compact filing label generated from a description of a structure. Different labels can quickly separate files, while matching labels send them to the same inspection tray. The analogy is limited because mathematical refinement rules determine the description, and two distinct structures can produce exactly the same description before the final hash is even applied.
Worked example
Construct graph A as a cycle of six nodes: 1-2-3-4-5-6-1. Construct graph B as two separate triangles: a-b-c-a and d-e-f-d. Both graphs have six nodes, six edges, and degree 2 at every node.
Use attribute-free neighborhood refinement initialized only with degree. At the start, every node in both graphs has the same label, representing degree 2. After one round, every node sees two neighbors with that same label. Every node therefore receives the same new label in both graphs. The argument repeats at every later round.
The two graphs produce matching label-count summaries under this basic refinement process, yet they are not isomorphic: A is connected and B has two connected components. This is a structural limitation of the summary, not merely an unlucky collision in the final digest. A connected-component check already separates this pair; a general duplicate-checking pipeline still needs an appropriate exact comparison when equality matters.
Illustrative case study
In a fictional project, Cedar Archive stores small process graphs. The team initially treats matching structural hashes as proof that two records can be merged. A reviewer introduces the six-cycle and two-triangle example, exposing the assumption.
The revised process uses the hash only to select candidate pairs. It then compares the relevant structure and attributes before merging records. The team also records configuration and library version alongside each fingerprint. This invented case illustrates a verification workflow and does not claim measured savings or a particular collision rate.
Common misconceptions and mistakes
A larger digest cannot fix every limitation. It can reduce accidental collisions in the final hashing stage, but it does not distinguish graphs that the preceding refinement maps to the same summary.
A graph hash is not a universal similarity score: two hexadecimal strings differing in one character are not necessarily more similar than strings differing in many characters. Nor does a matching structural fingerprint prove that two underlying business records refer to the same real-world entity. More iterations may reveal additional neighborhood differences, but they do not make basic Weisfeiler-Lehman refinement a complete isomorphism test.
Business use
Graph hashing can make graph collections easier to index, cache, compare, and audit. Its practical value depends on choosing a useful equivalence relation and an acceptable follow-up check. For example, a cache may require exact agreement on edge types and model settings, while a discovery interface may intentionally ignore selected attributes.
Define the canonical input preparation, attribute policy, and version information. Keep the original graph or a recoverable representation when later verification is required. Treat hash matches as evidence appropriate to the method, rather than as a substitute for a clearly defined identity policy.
People also ask
Does matching hash mean matching graph?
No. Both limitations of the graph summary and collisions in the final digest can produce matches.
Should node names be included?
Only if names are part of the equivalence being tested; arbitrary identifiers often should not determine structural equality.
Will increasing the number of refinement rounds always distinguish different graphs?
No. Some non-isomorphic graphs remain indistinguishable under basic neighborhood refinement regardless of the number of rounds.
Check your understanding
Why can the six-cycle and two separate triangles receive the same basic Weisfeiler-Lehman summary?
Answer: They have the same number of nodes, every node begins with degree 2, and every node repeatedly sees two neighbors with identical labels. The local refinement never reveals the connectivity difference.
Related terms
- Graph isomorphism
- Neighborhood
- Graph kernel
- graph fingerprint
- Weisfeiler-Lehman refinement
- node attribute
- hash collision
- canonical labeling
Learn next
Compare the worked pair using connected components, then study exact graph-isomorphism testing. Repeat a small hash experiment with and without a node attribute and record which differences the configuration preserves. This makes the gap between structural filtering and verified equality concrete.
More in Graphs and symbolic AI
- 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...
- Graph Convolutional Policy Network - Graph Convolutional Policy Network, or GCPN, is a model introduced for goal-directed graph generation using reinforcement learning.
- Graph of a function - The graph of a function is the set of all input-output pairs produced by that function over its specified domain.
- Graph search - Graph search is a family of problem-solving procedures that explore states and transitions while accounting for states reached more than once.
- Graphical degree sequence - A graphical degree sequence is a list of nonnegative integers that can be realized as the node degrees of a graph of the specified kind.
Sources
Sources: NetworkX, weisfeiler_lehman_graph_hash documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.graph_hashing.weisfeiler_lehman_graph_hash.html Shervashidze and colleagues, Weisfeiler-Lehman Graph Kernels: https://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf
Previous: Graph entropy Next: Graph isomorphism