10. Association, Sequence and Graph Mining

Introduction and Context

Data mining is concerned not merely with finding individual records, but with discovering relationships, structures, and regularities distributed across collections of data. Association mining identifies items or events that occur together. Sequence mining extends this idea by considering order and, often, time. Graph mining represents entities and their relationships explicitly, allowing analysts to study connectivity, communities, influence, and structural similarity.

These three forms of mining are particularly important because many organizational datasets are relational rather than independent. A retail transaction contains a set of products; a customer journey contains an ordered sequence of actions; a social or communication dataset contains users connected by relationships. Treating all such data as ordinary rows and columns can conceal the patterns that support effective decisions.

Association, sequence, and graph mining are related but not interchangeable. Association rules disregard the order in which items occur, whereas sequence mining models order and temporal constraints. Graph mining focuses on topology: which objects are connected, how strongly they are connected, and how the network is organized. Together, these techniques provide a foundation for recommendation, fraud detection, customer analysis, cybersecurity, bioinformatics, supply-chain intelligence, and knowledge discovery.

Learning Objectives

After studying this chapter, the reader should be able to:

• distinguish association, sequential, temporal, and graph mining problems;
• calculate and interpret support, confidence, lift, conviction, and related measures;
• explain the Apriori and FP-Growth approaches to frequent itemset discovery;
• formulate sequential patterns using sequence, time, gap, and support constraints;
• describe graph representations, centrality measures, link prediction, and community detection;
• select suitable mining techniques for practical organizational problems;
• evaluate computational, statistical, ethical, and governance risks; and
• interpret mining results critically rather than treating discovered patterns as automatically causal or useful.

Association Mining: From Co-occurrence to Rules

Association mining discovers combinations of attributes, items, or events that occur together more frequently than expected. The classic application is market-basket analysis, in which each transaction is represented as a set of purchased items. If many transactions contain bread and butter, the combination may be useful for store layout or promotion. A rule such as `{bread} → {butter}` expresses an implication in the data, not necessarily a causal relationship.

Let the transaction database be D, containing N transactions. An itemset X is a set of items. The support of X is:

support(X) = number of transactions containing X / N

For a rule X → Y, where X and Y are disjoint itemsets, support is the proportion of transactions containing X ∪ Y. Confidence measures the conditional frequency of Y among transactions containing X:

confidence(X → Y) = support(X ∪ Y) / support(X)

Confidence can be misleading when Y is common. Lift corrects for the baseline prevalence of Y:

lift(X → Y) = confidence(X → Y) / support(Y)

A lift greater than 1 indicates positive association, lift equal to 1 indicates independence under the measure, and lift below 1 indicates negative association. For example, suppose 20% of transactions contain coffee, 30% contain biscuits, and 12% contain both. The rule coffee → biscuits has confidence 0.12/0.20 = 0.60 and lift 0.60/0.30 = 2. A customer buying coffee is twice as likely as the average customer to buy biscuits. The result is useful for targeting, although it does not prove that coffee causes biscuit purchases.

Other measures support interpretation. Leverage is the difference between observed joint support and expected joint support under independence:

leverage(X → Y) = support(X ∪ Y) − support(X)support(Y)

Conviction compares the expected frequency of an antecedent occurring without the consequent with the observed frequency. A high conviction can indicate a strong directional implication, although it is unstable when the consequent is extremely common. Statistical significance tests, confidence intervals, and holdout validation can complement these measures.

Frequent Itemsets and the Downward-Closure Principle

A frequent itemset is an itemset whose support meets a chosen minimum support threshold. The central property used by many algorithms is downward closure, also called the Apriori property: every subset of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, every larger itemset containing it must be infrequent.

This property supports candidate pruning. If `{A, B}` fails the minimum-support threshold, there is no need to count `{A, B, C}`. The threshold is a modeling choice. A high threshold improves efficiency but may miss niche patterns; a low threshold may generate an overwhelming number of weak or accidental patterns.

Apriori and FP-Growth

The Apriori algorithm proceeds level by level. It first counts individual items and retains frequent one-itemsets. It then joins compatible frequent itemsets to generate candidate two-itemsets, scans the database to count them, and repeats the process for larger itemsets. Before counting a candidate, Apriori removes it if any required subset is known to be infrequent.

Apriori is conceptually clear but may require many database scans and may generate large candidate sets. FP-Growth addresses this problem by compressing the transaction database into an FP-tree. Common prefixes are shared, and conditional pattern bases are recursively mined without explicitly generating every candidate. FP-Growth is often more efficient on dense datasets, while Apriori remains valuable for teaching, controlled experiments, and situations where transparent candidate generation is useful.

In distributed environments, frequent-itemset mining may use partitioning, local counting, parallel tree construction, or specialized data-processing frameworks. Sampling and approximate counting can reduce cost, but approximation must be reported because rare-pattern results are especially sensitive to sampling error.

Interpreting Association Rules Carefully

A large rule set is not the same as a useful rule set. Rules should be filtered using minimum support, confidence, lift, business relevance, novelty, and validation on new data. Redundant rules can be removed when a more general rule conveys almost the same information. Analysts should also examine whether a rule is driven by a particular store, season, customer segment, or data-collection artifact.

Association rules are descriptive. Confounding variables may explain co-occurrence. A promotion may cause two products to appear together, or both products may be required by a particular recipe. If a decision involves intervention, causal methods, controlled experiments, or quasi-experimental designs are needed in addition to association mining.

Sequential and Temporal Pattern Mining

An itemset represents simultaneous or unordered presence; a sequence represents ordered events. A customer sequence might be ⟨search, product-view, comparison, purchase⟩. In healthcare, a sequence could represent diagnosis, treatment, and follow-up. In cybersecurity, it may describe login, privilege escalation, and data transfer.

A sequence database contains multiple sequences, each often associated with an entity such as a customer or device. A sequence pattern is frequent when it appears as a subsequence of at least a specified proportion of sequences. The sequence ⟨A, B⟩ occurs in ⟨A, C, B⟩ because the order is preserved, although the events need not be adjacent unless an adjacency constraint is imposed.

Temporal mining adds time information. Useful constraints include:

• minimum and maximum gap: the permitted time between successive events;
• window constraint: the entire pattern must occur within a specified duration;
• periodicity: events recur at regular or approximately regular intervals;
• absolute time constraints: patterns are associated with calendar periods; and
• event duration: an event occupies an interval rather than a single timestamp.

A rule such as ⟨login, failed-login, password-reset⟩ within ten minutes has a different operational meaning from the same sequence occurring over six months. Time granularity, clock synchronization, missing events, and delayed recording must therefore be considered before mining.

Methods for Sequential Discovery

The Generalized Sequential Pattern approach adapts candidate generation and pruning to ordered sequences. Like Apriori, it relies on the fact that a sequence cannot be frequent if one of its subsequences is infrequent. PrefixSpan uses prefix projection: instead of repeatedly scanning the entire database and generating broad candidate sets, it projects the database according to observed prefixes and grows patterns recursively. SPADE uses a vertical representation in which event occurrences are represented by identifier lists, enabling efficient joins under suitable conditions.

Sequential rules may be expressed as X ⇒ Y, where X precedes Y and the rule can be evaluated with support and confidence. However, sequence mining introduces additional choices: whether repeated events are allowed, whether simultaneous events form an itemset, how missing events are treated, and whether multiple occurrences within one entity count once or repeatedly.

Temporal patterns are vulnerable to the “many opportunities” problem. If thousands of possible patterns are tested, some will appear strong by chance. Minimum support alone is insufficient. Analysts should use statistical correction where appropriate, evaluate patterns on future periods, and compare them with suitable null or baseline models.

Applications include next-event recommendation, predictive maintenance, treatment pathway analysis, customer churn journeys, process conformance, and intrusion detection. In process mining, discovered sequences can be compared with an intended process model to identify deviations, bottlenecks, and rework. In predictive applications, leakage must be avoided: events occurring after the prediction point cannot be used as input to a model intended to operate before that point.

Graph Representations and Mining Tasks

A graph G = (V, E) consists of vertices V and edges E. Vertices may represent people, accounts, products, documents, devices, or biological entities. Edges may represent friendship, communication, ownership, purchase, citation, similarity, or physical connection. Graphs can be directed or undirected, weighted or unweighted, signed or unsigned, static or dynamic, and homogeneous or heterogeneous.

The choice of representation affects the result. A communication graph may contain a directed edge from sender to receiver, whereas a collaboration graph may use an undirected edge. A bipartite graph separates two types of vertices, such as customers and products. Projecting it into a customer-customer graph can reveal shared purchases but may also create dense, difficult-to-interpret connections. A heterogeneous graph preserves entity and relation types and is usually preferable when those distinctions matter.

Important graph-mining tasks include:

1. Node classification: predicting a label for a vertex, such as fraudulent or legitimate.

2. Link prediction: estimating whether an edge will form, disappear, or has been missed.

3. Community detection: identifying densely connected groups with relatively fewer external connections.

4. Centrality analysis: measuring structural importance or influence.

5. Subgraph and motif discovery: locating recurring local structures.

6. Graph clustering and similarity: grouping structurally or semantically similar entities.

7. Anomaly detection: finding unusual vertices, edges, or subgraphs.

Centrality and Link Analysis

Degree centrality counts a vertex’s incident edges; in directed graphs, in-degree and out-degree distinguish received from initiated connections. Betweenness centrality measures how often a vertex lies on shortest paths between other vertices and can indicate brokerage. Closeness centrality reflects the inverse distance from a vertex to others, although it is less reliable in disconnected graphs. Eigenvector centrality assigns greater importance to connections with important vertices.

PageRank is a related link-analysis method. It models a random surfer who follows links with a probability and occasionally jumps to another vertex. A page receives high score when it is linked by important pages. Variants are used in citation analysis, recommendation, and entity ranking. These measures are structural scores, not universal measures of competence, morality, or causal influence.

For link prediction, simple similarity measures include common neighbors, Jaccard similarity, and Adamic–Adar score. Preferential attachment predicts links partly from the product of endpoint degrees. More advanced methods use matrix factorization, probabilistic models, graph neural networks, or temporal representations. Evaluation should use time-aware splits when the intended task is future-link prediction; random splits may allow information from the future to leak into training.

Community Detection

A community is a group with comparatively dense internal connections or a meaningful shared role. Modularity-based methods compare observed internal connectivity with a null model. The Louvain and Leiden methods optimize modularity through iterative local movement and aggregation; Leiden generally improves the quality and connectivity of communities produced by the optimization process. Other approaches include spectral clustering, label propagation, stochastic block models, and overlapping community methods.

Community detection is not uniquely defined. Different algorithms, resolution parameters, random seeds, and graph projections may produce different partitions. Modularity also has a resolution limit: small meaningful communities can be merged into larger ones. Consequently, communities should be validated using domain knowledge, stability analysis, external labels, and downstream usefulness rather than accepted as objective natural entities.

An Illustrative Case: Detecting Coordinated Account Abuse

Background

Consider an illustrative online marketplace that allows users to create accounts, list products, communicate with buyers, and receive payments. The platform has transaction data, login histories, device identifiers, IP addresses, messages, and account relationships.

Situation and Problem

Losses increase because groups of accounts appear to create artificial demand, manipulate ratings, and move payments through linked accounts. A simple rule based on a single suspicious transaction generates too many false positives. The platform needs an investigation system that combines co-occurrence, temporal order, and network structure.

Analysis

Association mining is first applied to account-level events. Patterns such as `{new-device, high-value-listing, external-payment-message}` can identify combinations that deserve review, but support and lift are calculated within relevant segments because behavior differs between new and established sellers.

Sequential mining then examines event order. A suspicious pathway may be represented as ⟨account-created, listing-posted, related-account-purchase, rating-submitted, withdrawal-requested⟩ within a short interval. Minimum and maximum gaps prevent unrelated events from being joined into one pattern. The pattern is evaluated on later data rather than only on the period used to discover it.

A heterogeneous graph is constructed with account, device, IP, listing, payment, and review nodes. Edges represent login, shared device, shared payment instrument, purchase, rating, and communication. Community detection identifies clusters with unusually dense internal interaction. Centrality and link analysis highlight accounts that coordinate many apparently independent accounts. Graph features are then combined with temporal and transactional features in a risk-ranking model.

Approach and Outcome

The platform does not automatically block every account associated with a detected pattern. Instead, it creates a tiered workflow: low-risk cases receive monitoring, medium-risk cases undergo additional verification, and high-risk cases are sent to trained investigators. Analysts examine the evidence path, measure false-positive rates, and test whether performance remains stable across regions and customer groups.

This integrated approach is more informative than any single method. Association rules identify combinations, sequence mining captures the order of behavior, and graph mining exposes coordination. The outcome is a ranked investigation queue rather than an unreviewed automated judgment.

Learning Points

The case illustrates four principles. First, the data representation should match the question. Second, multiple signals are stronger when they are independently validated. Third, discovered patterns should support investigation and decision-making, not be confused with proof of misconduct. Fourth, monitoring, appeal, privacy controls, and performance auditing are part of a responsible mining system.

Challenges, Risks, and Professional Governance

The computational challenge is substantial. The number of possible itemsets, sequences, and subgraphs can grow exponentially. High-cardinality identifiers, dynamic networks, streaming data, and heterogeneous relations increase both storage and processing requirements. Approximation, pruning, sampling, parallelism, and incremental algorithms help, but each introduces assumptions that must be documented.

Data quality is equally important. Duplicate transactions inflate support; missing events break sequences; timestamp errors distort temporal patterns; bots create artificial activity; and changing business processes cause concept drift. Graphs may contain identity-resolution errors, producing false connections or incorrectly merging individuals.

A frequent mistake is selecting thresholds solely for convenience. Minimum support should reflect the population, cost of discovery, and business purpose. A rare but high-impact fraud pattern may be valuable even with low support, while a high-support rule may be operationally meaningless. Another mistake is interpreting confidence as probability of an intervention’s success. Association and sequence measures are observational unless supported by causal evidence.

Privacy and fairness require special attention. Graphs can reveal social relationships and sensitive affiliations even when individual attributes are removed. Re-identification may be possible through structural uniqueness. Access controls, data minimization, retention limits, encryption, purpose limitation, and audit trails should be built into the mining pipeline. If mining results affect credit, employment, healthcare, education, or access to services, organizations should provide human oversight, explanations appropriate to the decision, contest mechanisms, and bias assessments.

Ethical governance also concerns network externalities. Flagging one account may indirectly affect connected people who have not engaged in misconduct. Community labels can stigmatize groups, and centrality scores can be misused as measures of personal worth. Responsible practice therefore separates analytical evidence from final institutional decisions.

Technology and Emerging Directions

Modern systems increasingly combine structured mining with distributed processing, streaming analytics, and machine learning. Incremental frequent-pattern algorithms update results as transactions arrive. Temporal graphs support evolving relationships, while graph databases provide efficient traversal and neighborhood queries. Graph neural networks learn representations from topology and attributes, but their complexity and limited interpretability require careful validation.

Knowledge graphs connect entities and typed relations and can support semantic search, recommendation, question answering, and entity resolution. Hypergraphs represent relations involving more than two entities, such as a meeting involving several participants. Privacy-preserving mining explores differential privacy, secure multiparty computation, and federated analysis. These methods can reduce exposure of raw data, although privacy guarantees may reduce accuracy or obscure rare patterns.

Large language models can assist analysts in querying pattern repositories, explaining rules, or generating hypotheses, but they should not be treated as substitutes for statistically validated mining. Reproducible pipelines, versioned data, traceable thresholds, and independent evaluation remain essential.

Best Practices for Advanced Applications

A sound project begins with a precise analytical question and an explicit unit of analysis. The team should define what constitutes a transaction, sequence, event, vertex, and edge before choosing an algorithm. It should establish temporal boundaries and prevent future information from entering discovery or evaluation.

The next step is exploratory and quality-oriented: profile sparsity, missingness, duplicates, timestamp reliability, entity resolution, and population changes. Algorithms should be selected according to data density, scale, dynamism, and interpretability requirements. Results should be ranked using both statistical measures and domain value.

Patterns should be validated through holdout periods, subgroup analysis, stability tests, and, where possible, controlled interventions. Analysts should report thresholds, preprocessing choices, alternative specifications, false-positive and false-negative costs, and known limitations. Finally, deployment should include monitoring for drift, fairness, privacy incidents, and changing operational consequences.

Chapter Summary

Association mining discovers unordered co-occurrence through frequent itemsets and rules. Support measures prevalence, confidence measures conditional frequency, and lift compares observed association with a baseline of independence. Apriori exploits downward closure through candidate pruning, while FP-Growth compresses transactions to avoid extensive candidate generation.

Sequential mining incorporates order and can add temporal constraints such as gaps, windows, and periodicity. Prefix-based, vertical, and candidate-generation approaches discover recurring pathways, but temporal data requires careful treatment of missing events, leakage, multiple testing, and process change.

Graph mining models entities and relationships as vertices and edges. Centrality, PageRank, community detection, link prediction, motif discovery, and anomaly detection answer different structural questions. Graph representation choices strongly influence results, and communities or scores should be interpreted as analytical constructs rather than unquestionable facts.

Professional practice combines computational efficiency with validation, privacy, fairness, human oversight, and governance. Association, sequence, and graph methods are most powerful when integrated to address a clearly defined decision problem and when their descriptive findings are distinguished from causal conclusions.

Key Terms

Association rule: An implication of the form X → Y describing co-occurrence between itemsets.

Support: The proportion of records, transactions, or sequences containing a pattern.

Confidence: The proportion of cases containing X that also contain Y.

Lift: Confidence divided by the support of the consequent.

Leverage: Observed joint support minus expected joint support under independence.

Frequent itemset: An itemset whose support meets a specified minimum threshold.

Downward closure: The property that every subset of a frequent itemset is frequent.

Apriori: A level-wise frequent-itemset algorithm using candidate generation and pruning.

FP-Growth: An algorithm that mines frequent patterns from a compressed FP-tree.

Sequence: An ordered list of itemsets or events.

Sequential pattern: A recurring ordered pattern in a sequence database.

Temporal constraint: A restriction involving event time, duration, gap, or window.

Graph: A structure consisting of vertices and edges representing entities and relationships.

Directed graph: A graph whose edges have a specified direction.

Centrality: A family of measures describing structural importance of vertices.

PageRank: A link-analysis score based on the importance of incoming links.

Community detection: The identification of groups with comparatively dense internal connectivity.

Link prediction: Estimation of future, missing, or likely relationships in a graph.

Motif: A recurring small subgraph structure.

Concept drift: Change over time in data-generating behavior or relationships.

Review Questions

Short Answer Questions

1. Define support, confidence, and lift for an association rule.

2. State the downward-closure property used in frequent-itemset mining.

3. How does a sequence differ from an itemset?

4. Distinguish degree centrality from betweenness centrality.

5. Why can a high-confidence association rule still be misleading?

Long Answer Questions

1. Explain the Apriori algorithm and compare it with FP-Growth in terms of candidate generation, database scanning, and scalability.

2. Discuss the principal temporal constraints used in sequential pattern mining and explain why timestamp quality matters.

3. Describe major graph representations and explain how directed, weighted, bipartite, and heterogeneous choices affect analysis.

4. Explain community detection, including modularity, resolution problems, and the need for stability and domain validation.

5. Develop a complete mining strategy for detecting coordinated fraud using association, sequence, and graph data.

Analytical / Application Questions

1. In a database of 10,000 transactions, item A occurs in 2,000 transactions, item B in 3,000, and both in 900. Calculate confidence for A → B and its lift. Interpret both values.

2. A security team observes the sequence ⟨login, failed-login, password-reset⟩ in many records. Explain how a ten-minute window and a maximum-gap constraint could lead to different mining results.

3. A community-detection algorithm produces different groups after changing its resolution parameter. Propose a validation procedure to determine whether the groups are operationally meaningful.

22. Multiple Choice Questions with Answers

Question 1

A rule X → Y has support(X ∪ Y) = 0.12 and support(X) = 0.20. What is its confidence?

A. 0.06

B. 0.32

C. 0.60

D. 1.67

Correct Answer: C. 0.60

Question 2

If a rule has lift equal to 1, what does this indicate under the lift measure?

A. X and Y are necessarily causally related

B. X and Y occur independently relative to their supports

C. The rule has zero support

D. The consequent never occurs without the antecedent

Correct Answer: B. X and Y occur independently relative to their supports

Question 3

What allows Apriori to prune a candidate itemset before counting it?

A. Every superset of an infrequent itemset is infrequent

B. Every item must have identical frequency

C. Rules must have confidence below one

D. Graphs must be connected

Correct Answer: A. Every superset of an infrequent itemset is infrequent

Question 4

Which method primarily avoids extensive candidate generation by using a compressed transaction structure?

A. Apriori

B. FP-Growth

C. PageRank

D. Label propagation

Correct Answer: B. FP-Growth

Question 5

Which statement best distinguishes sequential mining from ordinary association mining?

A. Sequential mining ignores event timestamps

B. Sequential mining considers the order of events

C. Sequential mining can use only numerical data

D. Sequential mining never uses support

Correct Answer: B. Sequential mining considers the order of events

Question 6

A pattern occurs as ⟨A, C, B⟩. Which candidate is a subsequence under ordinary order-preserving semantics?

A. ⟨B, A⟩

B. ⟨C, A⟩

C. ⟨A, B⟩

D. ⟨B, C, A⟩

Correct Answer: C. ⟨A, B⟩

Question 7

Which graph measure is most directly associated with the frequency with which a vertex lies on shortest paths between other vertices?

A. Degree centrality

B. Betweenness centrality

C. In-degree

D. Jaccard similarity

Correct Answer: B. Betweenness centrality

Question 8

Why can a random train-test split be inappropriate for future link prediction?

A. It always removes all edges

B. It may allow future structural information to leak into training

C. It prevents graph construction

D. It guarantees low recall

Correct Answer: B. It may allow future structural information to leak into training

Question 9

A fraud analyst combines accounts, devices, payment instruments, and listings in one network. What type of graph best preserves these distinct entity types?

A. A homogeneous graph only

B. A heterogeneous graph

C. An unconnected graph

D. A transaction itemset

Correct Answer: B. A heterogeneous graph

Question 10

Which practice is most appropriate when a discovered graph community may affect access to services?

A. Automatically deny every member

B. Treat the community label as proof of misconduct

C. Use human oversight, validation, and an appeal mechanism

D. Remove all edges before making decisions

Correct Answer: C. Use human oversight, validation, and an appeal mechanism