Is structure mining always graph mining?

Graph mining is an important example, but structural patterns can also involve trees or sequences.

Is it the same as web structure mining?

Web link analysis is a more specific application area.

Does gSpan cover every structural task?

No. Its original task concerns frequent connected subgraphs in a graph dataset.

AI Glossary / Data science and analytics / Advanced

Structure mining

Definition

Structure mining is the discovery of useful patterns in data whose relationships, order or arrangement carry information. Examples include recurring subgraphs, tree shapes and sequences. The analysis considers how elements connect or occur together. Different applications require different definitions of a pattern and its occurrence.

What it means

Knowing that a document contains three headings says less than knowing which headings contain which subsections. Similarly, a list of components does not describe how those components connect. Structure mining retains relationships relevant to the question being investigated.
The term describes a family of tasks rather than one universal algorithm. Frequent subgraph mining, for example, searches for graph patterns that occur in enough graphs under a chosen counting rule. Other structural analyses can focus on trees or sequences, with different matching requirements.
A discovered pattern is a description of the represented data. Its usefulness depends on whether the representation captures meaningful relationships and whether the pattern helps answer the business or research question.

How it works

First choose a representation: nodes and edges for a graph, parent-child relationships for a tree, or ordered events for a sequence. Define labels and matching rules. A directed relationship from A to B need not match one from B to A, and labels may need to match exactly.
Next define what counts as support or another measure of interest. In a database of graphs, one common support count is the number of graphs containing a pattern. Multiple appearances inside one graph do not increase that graph's contribution under this convention.
Algorithms explore possible structures while avoiding redundant work. The gSpan research algorithm uses a canonical representation and depth-first pattern growth to find frequent connected subgraphs. This is one approach among many.
Finally, examine whether the discovered patterns are interpretable and useful. Repeated templates, incomplete relationships and inconsistent labels can strongly influence what the algorithm finds.

Three practical examples

A documentation team represents each guide as a tree of section types. It looks for recurring arrangements that may help design templates, while checking whether repeated structures reflect authoring rules rather than reader needs.
An engineering team represents assemblies as labeled graphs. It searches for recurring connected configurations to organize a collection for further review, without assuming that frequency proves a design is reliable.
A learning team represents activity records as ordered sequences. It investigates recurring progressions through resources, retaining the distinction between an observed order and evidence that one activity caused another.

Think of it this way

Structure mining resembles comparing floor plans instead of counting rooms. Two buildings may contain the same numbers of kitchens, bedrooms and corridors but connect them differently. Repeated arrangements can reveal a common design. Its usefulness still depends on the building's purpose and use.

Worked example

Suppose four fictional document graphs represent links between section types. A pattern P consists of an Overview node connected to an Example node, which connects to a Check node. The matching rule requires these labels and links but allows additional nodes and links elsewhere in the document graph.
P appears in documents D1, D2 and D4, but not D3. Its graph-level support count is three, and its relative support is 3 / 4 = 75%. With a minimum support of 50%, P qualifies as frequent in this collection.
If D1 contains two separate matches, its contribution remains one under the stated graph-level rule. Counting all matches would answer a different question and could give a different result. The 75% figure does not mean the structure improves learning by 75%, nor that it will appear in 75% of future documents. It describes prevalence in these four graphs under the chosen representation and rule.

Illustrative case study

In a fictional project, Cedar Guides wants to understand the organization of its technical tutorials. Editors convert headings and selected internal links into labeled graphs. They keep section roles such as explanation, example and exercise separate from the literal wording of headings.
The first results identify a common explanation-example-exercise pattern. Editors then discover that many matching guides were copied from one template. They group those origins during interpretation and inspect guides outside the dominant template rather than presenting the repeated pattern as independent evidence of effectiveness.
Cedar uses the findings to locate structural inconsistencies and propose templates for testing. Reader outcomes require a separate evaluation. This fictional case illustrates how structural patterns can support editorial investigation while still requiring attention to the process that produced the documents.

Common misconceptions and mistakes

Structure mining is not merely putting data into columns. A table can store a graph's edges, but the mining task concerns relationships represented by those records.
Frequent does not mean beneficial, unusual or causal. A routine template may dominate results, while an important rare configuration fails a frequency threshold. Choose the measure to fit the purpose.
Do not mix occurrence conventions. Graph-level support, total matches and overlapping matches are different quantities. Also specify whether extra edges between matched nodes are allowed: induced and non-induced matching can produce different answers.

Business use

Use structure mining when arrangement or connectivity matters to a decision. Possible uses include reviewing document organization, identifying recurring configurations and developing features for later analysis. Begin with a small, inspectable collection so subject experts can check the representation and matches.
Keep discovered patterns linked to their source records. Compare results under reasonable label and threshold choices, and assess whether duplicate structures dominate. If patterns feed a predictive model, evaluate that model separately; discovering a frequent pattern does not establish that it predicts a useful outcome.

Check your understanding

Why is P's support three despite two matches in D1?

Answer: Each containing graph counts once under the stated rule.

Why inspect the representation?

Answer: Missing or mislabeled relationships change the patterns that can be found.

What does frequent fail to establish?

Answer: That a pattern is useful or causes a desirable outcome.

Related terms

Subgraph isomorphism
Graph mining
frequent subgraph
sequence mining
tree mining
support
canonical labelling
pattern discovery
web structure mining

Learn next

Represent a few documents as labeled trees or graphs. Define a small pattern and count its support manually before comparing the result with an automated method.

Sources

Yan and Han, gSpan: Graph-Based Substructure Pattern Mining, 2002: primary algorithm paper and graph-database support convention. https://sites.cs.ucsb.edu/~xyan/papers/gSpan-short.pdf Han, Cheng, Xin and Yan, Frequent Pattern Mining: Current Status and Future Directions, 2007: research overview including structured patterns. https://sites.cs.ucsb.edu/~xyan/papers/dmkd07_frequentpattern.pdf The document graphs, calculations and Cedar Guides case are original illustrations, not reported research findings.

Previous: Structure learning Next: Structure tensor