Frequent Subgraph Mining¶

After generating multiple process graphs with the Process Mining module (only works with the Collaboration Instance Graphs (CIGs)), the resulting graphs can be processed using Frequent Subgraph Mining to extract patterns. To generate the frequent sub-graphs (the patterns), the following code can be used.

Collaboration Pattern Detection (CPD)¶

This module extracts frequent collaboration patterns from graphs created by the Collaboration Instance Graph Miner.

Algorithm Overview¶

The algorithm (called CPD - Collaboration Pattern Detection) works as follows:

1. Candidate Generation: Identifies all connected subgraphs with activity nodes between min_node and max_node count
2. Pattern Matching: Compares candidates across different traces using one of several matching algorithms
3. Frequency Counting: Counts exact and relaxed matches to determine support
4. Result Extraction: Returns subgraphs that meet the minimum support thresholds

Key Features¶

• Relaxed Pattern Matching: Patterns can match even when they are not identical, based on a similarity threshold. This allows finding similar collaboration patterns that may have minor differences in node labels.
• Object Node Preservation: Object nodes (e.g., resources, documents) and their relationships to activities are preserved in the discovered patterns, enabling analysis of the contextual context in which activities occur.
• Flexible Matching Algorithms: Multiple algorithms available:
• GraphEditDistance: Exact or approximate matching based on edit distance
• CosineGraphSimilarity: Distribution-based similarity matching
• VF2Isomorphism: Strict isomorphism detection
• Activity-Centric: Focuses on activity node connectivity while treating object nodes as contextual attributes

Pattern Matching Algorithms¶

Parameters¶

The execute_copisum function accepts the following parameters:

Example Usage¶

Basic usage with default settings:

from collaboration_detection.datastructures import GraphCollection
from collaboration_detection.subgraph_mining import copisum

# Load or mine graphs
graph_collection = GraphCollection().load("graphs.db")

# Execute COPISUM
patterns = copisum(
    graph_collection=graph_collection,
    min_node=3,
    max_node=5,
    support_exact=2,
    support_relaxed=2
)

# Patterns are now in the graph_collection
for graph_id, graph in patterns.graphs.items():
    print(f"Pattern {graph_id}: support={graph.metadata.get('support', 0)}")

Advanced usage with custom configuration:

from collaboration_detection.datastructures import GraphCollection
from collaboration_detection.subgraph_mining import copisum
from collaboration_detection.subgraph_mining.collaboration_process_instance_subgraph_mining.algorithm import (
    SubgraphMiningAlgorithm,
    PatternMatchingAlgorithm,
)

graph_collection = GraphCollection().load("graphs.db")

patterns = copisum(
    graph_collection=graph_collection,
    min_node=2,
    max_node=6,
    object_attributes={"org:resource", "spm:sdid"},
    activity_node_type="activity",
    node_type_metadata_attribute="v_type",
    matching_threshold=0.9,
    support_exact=3,
    support_relaxed=2,
    subgraph_mining=SubgraphMiningAlgorithm.RustImpl,
    pattern_matching_algorithm=PatternMatchingAlgorithm.CosineGraphSimilarity
)

Using Graph Edit Distance for exact matching:

patterns = copisum(
    graph_collection=graph_collection,
    min_node=3,
    max_node=5,
    matching_threshold=0,  # 0 = exact match for GED
    pattern_matching_algorithm=PatternMatchingAlgorithm.GraphEditDistance,
    support_exact=2
)

Rust Implementation¶

The default implementation uses a Rust binary (cpd) for efficient subgraph mining. The binary is included for Linux, macOS (Intel/ARM), and Windows. The algorithm automatically selects the correct binary based on the platform.

gSpan (Exact Frequent Subgraph Mining)¶

The gSpan algorithm is used for exact frequent subgraph mining.

Implementation¶

This package supports both Java and Rust implementations. - Java: Requires the gSpan Java implementation. The .jar file should be placed in the bin/ folder of the project. - Rust: Uses a pre-compiled Rust binary provided in the bin/ folder, automatically selected based on the operating system.

Parameters¶

The execute_gspan function accepts the following parameters:

Example Usage¶

from collaboration_detection.datastructures import GraphCollection
from collaboration_detection.subgraph_mining import gspan

# 1. Create a graph collection (import or by mining new graphs)
g_c = GraphCollection().load("graphs.db")

# 2. Execute the gspan algorithm
gspan(
    data=g_c,
    min_node=3,
    max_node=10,
    sup=20,
    remove_data_graphs=True
)
# 3. All sub-graphs are now stored in the graph collection
g_c.graphs.items()

Subdue (Frequent Subgraph Mining)¶

The Subdue algorithm is used for frequent subgraph mining. It is a powerful tool that finds frequent patterns by iteratively extending smaller patterns.

Implementation¶

This package uses a C implementation of Subdue. To use this module, the subdue binary must be installed on the system. The wrapper provides an automatic installation check: if the subdue binary is not found in the PATH, the system will attempt to clone the repository, compile it using make, and install it via make install.

Parameters¶

The execute_subdue function accepts the following parameters:

Example Usage¶

from collaboration_detection.datastructures import GraphCollection
from collaboration_detection.subgraph_mining import subdue

# 1. Create a graph collection
g_c = GraphCollection().load("graphs.db")

# 2. Execute the subdue algorithm
subdue(
    data=g_c,
    min_node=3,
    max_node=10,
    nsubs=5,
    beam=15
)
# 3. Results are stored in the graph collection
g_c.graphs.items()