Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

1

Mining Various Kinds of Patterns

• Mining Multilevel Associations
• Mining Multidimensional Associations
• Mining Quantitative Association Rules
• Mining High-dimensional Data
• Mining Rare Patterns and Negative Patterns

2

Mining Multiple-Level Frequent Patterns

• Items often form hierarchies
• Milk: Dairyland 2% milk
• Bread: Wonder wheat bread

​

• Min-support thresholds for items following concept hierarchies
• Uniform min-support across multiple levels (reasonable?)
• Level-reduced min-support:
• Items at the lower level are expected to have lower support
• Efficient mining: Shared multi-level mining
• Use the lowest min-support to pass down the set of candidates

​

3

Redundancy Filtering at Mining Multi-Level Associations

• Redundancy filtering: redundant due to “ancestor” relationships
• milk ⇒ wheat bread [support = 8%, confidence = 70%] (1)
• 2% milk ⇒ wheat bread [support = 2%, confidence = 72%] (2)
• Suppose the 2% milk sold is about ¼ of milk sold in gallons
• (2) should be able to be “derived” from (1)

​

• In general: A rule is redundant if its support is close to the “expected” value, according to its “ancestor” rule, and it has a similar confidence as its “ancestor”

Q: If rule (1) is an ancestor of rule (2), which one to prune?

4

Customized Min-Supports for Different Kinds of Items

• We have used the same min-support threshold for all the items or item sets to be mined in each association mining
• In reality, some items (e.g., diamond, watch, …) are valuable but less frequent
• It is necessary to have customized min-support settings for different kinds of items
• One Method: Use group-based “individualized” min-support
• E.g., {diamond, watch}: 0.05%; {bread, milk}: 5%; …
• How to mine such rules efficiently?
• Existing scalable mining algorithms can be easily extended to cover such cases

5

Mining Multi-Dimensional Associations

• Single-dimensional rules (e.g., items are all in “product” dimension)
• buys(X, “milk”) ⇒ buys(X, “bread”)
• Multi-dimensional rules (i.e., items in ≥ 2 dimensions or predicates)
• Inter-dimension association rules (no repeated predicates)
• age(X, “18-25”) ∧ occupation(X, “student”) ⇒ buys(X, “coke”)
• Hybrid-dimension association rules (repeated predicates)
• age(X, “18-25”) ∧ buys(X, “popcorn”) ⇒ buys(X, “coke”)
• Attributes can be categorical or numerical
• Categorical Attributes (e.g., profession, product: no ordering among values): Data cube for inter-dimension association
• Quantitative Attributes: Numeric, implicit ordering among values—discretization, clustering, and gradient approaches

​

6

Mining Quantitative Associations

• Mining associations with numerical attributes
• E.g.: Numerical attributes: age and salary
• Methods
• Static discretization based on predefined concept hierarchies
• Discretization on each dimension with hierarchy
• age: {0-10, 10-20, …, 90-100} → {young, mid-aged, old}
• Dynamic discretization based on data distribution
• Clustering: Distance-based association
• First one-dimensional clustering, then association
• Deviation analysis:
• Gender = female ⇒ Wage: mean=$7/hr (overall mean = $9)

7

Mining Extraordinary Phenomena in Quantitative Association Mining

• Mining extraordinary (i.e., interesting) phenomena
• E.g.: Gender = female ⇒ Wage: mean=$7/hr (overall mean = $9)
• LHS: a subset of the population
• RHS: an extraordinary behavior of this subset
• The rule is accepted only if a statistical test (e.g., Z-test) confirms the inference with high confidence

​

• Subrule: Highlights the extraordinary behavior of a subset of the population of the super rule
• E.g.: (Gender = female) ^ (South = yes) ⇒ mean wage = $6.3/hr
• Rule condition can be categorical or numerical (quantitative rules)
• E.g.: Education in [14-18] (yrs) ⇒ mean wage = $11.64/hr

​

Efficient methods have been developed for mining such rules (e.g., Aumann and Lindell@KDD’99)

8

Rare Patterns vs. Negative Patterns

• Rare patterns
• Very low support but interesting (e.g., buying Rolex watches)
• How to mine them? Setting individualized, group-based min-support thresholds for different groups of items
• Negative patterns
• Negatively correlated: Unlikely to happen together
• Ex.: Since it is unlikely that the same customer buys both a Ford Expedition (an SUV car) and a Ford Fusion (a hybrid car), buying a Ford Expedition and buying a Ford Fusion are likely negatively correlated patterns
• How to define negative patterns?

9

Defining Negative Correlated Patterns

• A support-based definition
• If itemsets A and B are both frequent but rarely occur together, i.e.,
• sup(A U B) << sup (A) × sup(B)
• Then A and B are negatively correlated
• Is this a good definition for large transaction datasets?
• Ex.: Suppose a store sold two needle packages A and B 100 times each, but only one transaction contained both A and B
• When there are in total 200 transactions, we have
• s(A U B) = 0.005, s(A) × s(B) = 0.25, s(A U B) << s(A) × s(B)
• But when there are 10⁵ transactions, we have
• s(A U B) = 1/10⁵, s(A) × s(B) = 1/10³ × 1/10³, s(A U B) > s(A) × s(B)
• What is the problem here?

—Null transactions: The support-based definition is not null-invariant!

Does this remind you the definition of lift?

10

Defining Negative Correlation: Need Null-Invariance in Definition

• A good definition on negative correlation should be null-invariant!
• Intuition: Whether two itemsets A and B are negatively correlated should not be influenced by the number of null-transactions
• A Kulczynski measure-based definition
• If itemsets A and B are frequent but (s(A U B)/s(A) + s(A U B)/s(B))/2 < є,

then A and B are negatively correlated

• For the same needle package problem:
• No matter there are in total 200 or 10⁵ transactions
• If є = 0.01, we have

(s(A U B)/s(A) + s(A U B)/s(B))/2 = (0.01 + 0.01)/2 < є

є is a negative

pattern threshold

11

Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

12

Mining Compressed Patterns

• Why mining compressed patterns? Too many scattered patterns but not so meaningful
• Pattern distance measure

​

• δ-clustering: For each pattern P, find all patterns which can be expressed by P and whose distance to P is within δ (δ-cover)
• All patterns in the cluster can be represented by P

• Closed patterns
• P1, P2, P3, P4, P5
• Emphasizes too much on support
• Max-patterns
• P3: information loss
• Desired output (a good balance):
• P2, P3, P4

13

Redundancy-Aware Top-k Patterns

• Desired patterns: high significance & low redundancy

• Method: Use MMS (Maximal Marginal Significance) for measuring the combined significance of a pattern set
• Xin et al., Extracting Redundancy-Aware Top-K Patterns, KDD’06

14

Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

15

Why Constraint-Based Mining?

• Pattern mining in practice: Often a user-guided, interactive process
• User directs what to be mined using a data mining query language (or a graphical user interface), specifying various kinds of constraints

​

• What is constraint-based mining?
• Mine together with user-provided constraints

​

• Why constraint-based mining?
• User flexibility: User provides constraints on what to be mined
• Optimization: System explores such constraints for mining efficiency
• E.g., Push constraints deeply into the mining process

16

Various Kinds of User-Specified Constraints in Data Mining

• Knowledge type constraint—Specifying what kinds of knowledge to mine
• E.g.: Classification, association, clustering, outlier finding, …
• Data constraint—using SQL-like queries
• E.g.: Find products sold together in NY stores this year
• Dimension/level constraint—similar to projection in relational database
• E.g.: In relevance to region, price, brand, customer category
• Interestingness constraint—various kinds of thresholds
• E.g.: Strong rules: min_sup ≥ 0.02, min_conf ≥ 0.6, min_correlation ≥ 0.7
• Rule (or pattern) constraint
• E.g.: Small sales (price < $10) triggers big sales (sum > $200)

The focus of this study

17

Pattern Space Pruning with Pattern Anti-Monotonicity

• A constraint c is anti-monotone
• If an itemset S violates constraint c, so does any of its superset
• That is, mining on itemset S can be terminated
• Ex. 1: c₁: sum(S.price) ≤ v is anti-monotone
• Ex. 2: c₂: range(S.profit) ≤ 15 is anti-monotone
• Itemset ab violates c₂ (range(ab) = 40)
• So does every superset of ab
• Ex. 3. c₃: sum(S.Price) ≥ v is not anti-monotone
• Ex. 4. Is c₄: support(S) ≥ σ anti-monotone?
• Yes! Apriori pruning is essentially pruning with an anti-monotonic constraint!

min_sup = 2

Note: item.price > 0

Profit can be negative

18

Pattern Monotonicity and Its Roles

• A constraint c is monotone: If an itemset S satisfies the constraint c, so does any of its superset
• That is, we do not need to check c in subsequent mining
• Not as beneficial as anti-monotone
• E.g. 1: c₁: sum(S.Price) ≥ v is monotone

​

• E.g. 2: c₂: min(S.Price) ≤ v is monotone

​

• E.g. 3: c₃: range(S.profit) ≥ 15 is monotone
• Itemset ab satisfies c₃
• So does every superset of ab

min_sup = 2

19

Apriori for Pattern Anti-Monotone Constraint

Database D

Scan D

C₁

F₁

F₂

C₂

C₂

Scan D

C₃

F₃

Scan D

Min_sup=2

Constraint:

Sum{S.price} < 5

Can be chopped early

20

Convertible Constraints: Ordering Data in Transactions

• Convert tough constraints into (anti-)monotone by proper ordering of items in transactions

​

• Examine c₁: avg(S.profit) > 20
• Order items in (profit) value-descending order
• <a, g, h, b, f, d, c, e>
• An itemset ab violates c₁ (avg(ab) = 20)
• So does ab* (i.e., ab-projected DB)
• C₁: anti-monotone if patterns grow in the right order!

min_sup = 2

21

Can item-reordering work for Apriori?

• avg(gf) = 12.5 < 20, avg(af) = 17.5 < 20, avg(ag) = 35 > 20
• But avg(agf) = 21.7 > 20
• Apriori will not generate “agf” as a candidate

​

min_sup = 2

F₁

F₂

Chopped too early

constraint: avg(S.profit) > 20

22

Data Space Pruning with Data Anti-Monotonicity

• A constraint c is data anti-monotone: In the mining process, if a data entry t cannot satisfy a pattern p under c, t cannot satisfy p’s superset either
• Data space pruning: Data entry t can be pruned
• Ex. 1: c₁: sum(S.Profit) ≥ v is data anti-monotone
• Let constraint c₁ be: sum(S.Profit) ≥ 25
• T₃₀: {b, c, d, f, g} can be removed since none of their combinations can make an S whose sum of the profit is ≥ 25
• Ex. 2: c₂: min(S.Price) ≤ v is data anti-monotone
• Consider v = 5 but every item in a transaction, say T₅₀ , has a price higher than 10
• Ex. 3: c₃: range(S.Profit) > 25 is data anti-monotone

min_sup = 2

23

Data Space Pruning Should Be Explored Recursively

• Example. c₃: range(S.Profit) > 25
• We check b’s projected database
• But item “a” is infrequent (sup = 1)

​

​

• After removing “a (40)” from T₁₀
• T₁₀ cannot satisfy c₃ any more
• Since “b (0)” and “c (−20), d (−15), f (−10), h (5)”
• By removing T₁₀, we can also prune “h” in T₂₀

min_sup = 2

b’s-proj. DB

b’s-proj. DB

24

Data Space Pruning Explored Recursively (Continued)

Recursive

Data

Pruning

b’s FP-tree

single branch: cdfg: 2

Constraint:

range{S.profit} > 25

Only a single branch “cdfg: 2” to be mined in b’s projected DB

• Note: c₃ prunes T₁₀ effectively only after “a” is pruned (by min-sup) in b’s projected DB

b’s-proj. DB

25

Succinctness: Pruning Both Data and Pattern Spaces

• Succinctness: If the constraint c can be enforced by directly manipulating the data
• E.g. 1: To find those patterns containing item i
• Mine only i-projected DB (data space pruning)
• E.g. 2: To find those patterns without item i
• Remove i from DB and then mine (pattern space pruning)
• E.g. 3: c₃: min(S.Price) ≤ v is succinct
• Start with only items whose price ≤ v and remove transactions with high-price items only (pattern + data space pruning)
• E.g. 4: c₄: sum(S.Price) ≥ v is not succinct
• It cannot be determined beforehand since sum of the price of itemset S keeps increasing

26

Constrained FP-Growth: Push a Succinct Constraint Deep

Remove

infrequent

length 1

1-Projected DB

No Need to project on 3 or 5

2-Projected DB

Min_sup=2

Constraint:

min{S.price} <= 2

27

Different Kinds of Constraints Lead to Different Pruning Strategies

• In summary, constraints can be categorized as pattern space pruning constraints vs. data space pruning constraints

​

28

How to Handle Multiple Constraints?

• It is beneficial to use multiple constraints in pattern mining
• But different constraints may require potentially conflicting item-ordering
• If there exists conflict ordering between c₁ and c₂
• Try to sort data and enforce one constraint first (which one?)
• Then enforce the other constraint when mining the projected databases
• E.g. c₁: avg(S.profit) > 20, and c₂: avg(S.price) < 50
• Assum c₁ has more pruning power
• Sort in profit descending order and use c₁ first
• For each project DB, sort trans. in price ascending order and use c₂ at mining

29

Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

30

Sequential Pattern Mining

• Sequential Pattern and Sequential Pattern Mining
• GSP: Apriori-Based Sequential Pattern Mining
• SPADE: Sequential Pattern Mining in Vertical Data Format
• PrefixSpan: Sequential Pattern Mining by Pattern-Growth
• CloSpan: Mining Closed Sequential Patterns
• Constraint-Based Sequential-Pattern Mining

​

31

Sequential Pattern Mining

• What kind of patterns are sequential?
• Sequential: The order really matters
• You cannot swap two items in a sequence and have the same sequence
• Example: The English language is sequential: Subject → Verb → Object

​

• Other points:
• For Sequential Pattern Mining, the time which the items occur is not considered
• Time Series Analysis does take into account the time in which an item occurred

32

Sequential Pattern Examples

• Application of Sequential pattern Mining
• Customer shopping: Purchase a laptop first, then a digital camera, and then a smartphone
• Medical treatments: Go to see a doctor, get drugs, doctor monitors progress, doctor reacts accordingly → more/less drugs
• Natural disasters: Before the disaster, during the disaster, after the disaster
• Scientific Experiments: Step 1, Step 2, Step 3
• Stocks Markets: A set of stocks go up and down together
• Biological sequences, DNA /Protein: If you change the order of a protein, it likely results in a different gene

33

Sequential Pattern and Sequential Pattern Mining

• Sequential pattern mining: Given a set of sequences, find the complete set of frequent subsequences (i.e., satisfying the min_sup threshold)

A sequence database

• An element may contain a set of items (also called events)

* Items within an element are unordered and we list them alphabetically

element (unordered within “(..)”)

34

Sequential Pattern and Sequential Pattern Mining

• Sequential pattern mining: Given a set of sequences, find the complete set of frequent subsequences (i.e., satisfying the min_sup threshold)

<a(bc)dc> is a subsequence of <a(abc)(ac)d(cf)>

​

• Given support threshold min_sup = 2, <(ab)c> is a sequential pattern

A sequence database

35

Sequential Pattern Mining Algorithms

• Algorithm requirement: Efficient, scalable, finding complete set, incorporating various kinds of user-specific constraints
• The Apriori property still holds: If a subsequence s₁ is infrequent, none of s₁’s super-sequences can be frequent
• Representative algorithms
• GSP (Generalized Sequential Patterns): Srikant & Agrawal @ EDBT’96)
• Vertical format-based mining: SPADE (Zaki@Machine Leanining’00)
• Pattern-growth methods: PrefixSpan (Pei, et al. @TKDE’04)
• Mining closed sequential patterns: CloSpan (Yan, et al. @SDM’03)
• Constraint-based sequential pattern mining

36

GSP: Apriori-Based Sequential Pattern Mining

• Initial candidates: All 8-singleton sequences
• <a>, <b>, <c>, <d>, <e>, <f>, <g>, <h>
• Scan DB once, count support for each candidate

min_sup = 2

x

GSP (Generalized Sequential Patterns): Srikant & Agrawal @ EDBT’96)

37

GSP: Apriori-Based Sequential Pattern Mining

• Example: Generate length-2 candidate sequences

min_sup = 2

• w/o pruning (includes g and h):

8*8 + 8*7/2 = 92

length-2 candidates

• w/ pruning:

6*6 + 6*5/2 = 51

length-2 candidates

singleton * singleton – Total: (6 * 6)

Sets (unordered) – Total: (6*5) / 2

Apriori Pruning

38

GSP Mining and Pruning

min_sup = 2

• Remove Candidates not in DB or Candidates < min_sup

6*6 + 6*5/2 = 51

length

5

​

4

​

3

​

2

​

1

​

• Repeat, starting at k = 1 until k <= length
• Scan DB to find “length-k” frequent sequences
• Generate “length-(k+1)” candidate sequences from “length-k” frequent sequences using Apriori
• set k = k+1
• Until no frequent sequence or no candidate can be found

The GPS algorithm

39

Sequential Pattern Mining in Vertical Data Format: The SPADE Algorithm

Ref: SPADE (Sequential PAttern Discovery using Equivalent Class) [M. Zaki 2001]

min_sup = 2

• A sequence database is mapped to: <SID, EID>
• Grow the subsequences (patterns) one item at a time by Apriori candidate generation

EID (b) < EID (a):

Corresponds to:

<a(abc)(ac)d(cf)>

40

PrefixSpan: A Pattern-Growth Approach

• PrefixSpan Mining: Prefix Projections
• Step 1: Find length-1 sequential patterns
• <a>, <b>, <c>, <d>, <e>, <f>
• Step 2: Divide search space and mine each projected DB
• <a>-projected DB,
• <b>-projected DB,
• …
• <f>-projected DB, …

• Prefix and suffix
• Given <a(abc)(ac)d(cf)>
• Prefixes: <a>, <aa>, <a(ab)>, <a(abc)>, …
• Suffix: Prefixes-based projection

PrefixSpan (Prefix-projected Sequential pattern mining) Pei, et al. @TKDE’04

min_sup = 2

“_” is placeholder for prefix

41

PrefixSpan: Mining Prefix-Projected DBs

prefix <a>

Length-1 sequential patterns

<a>, <b>, <c>, <d>, <e>, <f>

prefix <aa>

…

prefix <af>

…

prefix <b>

prefix <c>, …, <f>

… …

Major strength of PrefixSpan:

• No candidate subseqs. to be generated
• Projected DBs keep shrinking

min_sup = 2

Length-2 sequential

patterns

<aa>, <ab>, <(ab)>,

<ac>, <ad>, <af>

42

Implementation Consideration: Pseudo-Projection vs. Physical Projection

• Major cost of PrefixSpan: Constructing projected DBs
• Suffixes largely repeating in recursive projected DBs
• When DB can be held in main memory, use pseudo projection

• No physically copying suffixes
• Pointer to the sequence
• Offset of the suffix
• But if it does not fit in memory
• Physical projection
• Suggested approach:
• Integration of physical and pseudo-projection
• Swapping to pseudo-projection when the data fits in memory

2 5

Pointers save memory usage

43

CloSpan: Mining Closed Sequential Patterns

• A closed sequential pattern s: There exists no superpattern s’ such that s’ כ s, and s’ and s have the same support
• Which ones are closed? <abc>: 20, <abcd>:20, <abcde>: 15

• Why directly mine closed sequential patterns?
• Reduce # of (redundant) patterns
• Attain the same expressive power
• Property P: Given two sequences s and s’, if s is a subsequence of s’, then the projected database of s = the projected database of s’ iff the size of the two projected databases are the same.
• Explore Backward Subpattern and Backward Superpattern pruning to prune redundant search space
• Greatly enhances efficiency (Yan, et al., SDM’03)

44

CloSpan: When Two Projected DBs Have the Same Size

<e>

<a>

<f>

<b>

<b>

<f>

• Exploring Property P for closed pattern mining
• When two projected sequence DBs have the same size?
• Here is one example:

Only need to keep size = 12 (including parentheses)

size = 6

Backward subpattern pruning

Backward superpattern pruning

min_sup = 2

45

Constraint-Based Sequential-Pattern Mining

• Share many similarities with constraint-based itemset mining
• Anti-monotonic: If S violates c, the super-sequences of S also violate c
• sum(S.price) < 150; min(S.value) > 10
• Monotonic: If S satisfies c, the super-sequences of S also do so
• element_count (S) > 5; S ⊇ {PC, digital_camera}
• Data anti-monotonic: If a sequence s₁ with respect to S violates c₃, s₁ can be removed
• c₃: sum(S.price) ≥ v
• Succinct: Enforce constraint c by explicitly manipulating data
• S ⊇ {i-phone, MacAir}
• Convertible: Projection based on the sorted value not sequence order
• value_avg(S) < 25; profit_sum (S) > 160
• max(S)/avg(S) < 2; median(S) – min(S) > 5

46

Timing-Based Constraints in Seq.-Pattern Mining

• Order constraint: Some items must happen before the other
• {algebra, geometry} → {calculus} (where “→” indicates ordering)
• Anti-monotonic: Constraint-violating sub-patterns pruned
• Min-gap/max-gap constraint: Confines two elements in a pattern
• E.g., mingap = 1, maxgap = 4
• Succinct: Enforced directly during pattern growth
• Max-span constraint: Maximum allowed time difference between the 1^st and the last elements in the pattern
• E.g., maxspan (S) = 60 (days)
• Succinct: Enforced directly when the 1^st element is determined
• Window size constraint: Events in an element do not have to occur at the same time: Enforce max allowed time difference
• E.g., window-size = 2: Various ways to merge events into elements

47

Episodes and Episode Pattern Mining

• Episodes and regular expressions: Alternative to seq. patterns
• Serial episodes: AB
• Parallel episodes: A|B
• Regular expressions: (A|B)C*(DE)
• E.g. Given a large shopping sequence database, one may like to find
• Suppose the pattern order follows the template (A|B)C*(D E), and
• Sum of the prices of A, B, C*, D, and E is greater than $100, where C* means C appears *-times
• How to efficiently mine such episode patterns?

a partial order relationship: A and B can be in any order

a total order relationship: first A then B

(DE) means D, E happen in the same time window

48

Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

49

What Is Graph Pattern Mining?

• Chem-informatics:
• Mining frequent chemical compound structures

​

​

​

​

• Social networks, web communities, tweets, …
• Finding frequent research collaboration subgraphs

50

Frequent (Sub)Graph Patterns

• Given a labeled graph dataset D = {G₁, G₂, …, G_n), the supporting graph set of a subgraph g is D_g = {G_i | g ⊆ G_i, G_i ∈D}
• support(g) = |D_g|/ |D|
• A (sub)graph g is frequent if support(g) ≥ min_sup
• Ex.: Chemical structures

min_sup = 2

support = 67%

• Alternative:
• Mining frequent subgraph patterns from a single large graph or network

51

Applications of Graph Pattern Mining

• Bioinformatics
• Gene networks, protein interactions, metabolic pathways
• Chem-informatics: Mining chemical compound structures
• Social networks, web communities, tweets, …
• Cell phone networks, computer networks, …
• Web graphs, XML structures, Semantic Web, information networks
• Software engineering: Program execution flow analysis
• Building blocks for graph classification, clustering, compression, comparison, and correlation analysis
• Graph indexing and graph similarity search

52

Graph Pattern Mining Algorithms: Different Methodologies

• Generation of candidate subgraphs
• Apriori vs. pattern growth (e.g., FSG vs. gSpan)
• Search order
• Breadth vs. depth
• Elimination of duplicate subgraphs
• Passive vs. active (e.g., gSpan [Yan & Han, 2002])
• Support calculation
• Store embeddings (e.g., GASTON [Nijssen & Kok, 2004], FFSM [Huan, Wang, & Prins, 2003], MoFa [Borgelt & Berthold, ICDM’02])
• Order of pattern discovery
• Path 🡪 tree 🡪 graph (e.g., GASTON [Nijssen & Kok, 2004])

53

Apriori-Based Approach

• The Apriori property (anti-monotonicity): A size-k subgraph is frequent if and only if all of its subgraphs are frequent
• A candidate size-(k+1) edge/vertex subgraph is generated if its corresponding two k-edge/vertex subgraphs are frequent
• Iterative mining process:
• Candidate-generation 🡪 candidate pruning 🡪 support counting 🡪 candidate elimination

54

Candidate Generation: �Vertex Growing vs. Edge Growing

• Generating new graphs with one more vertex
• AGM (Inokuchi, Washio, & Motoda, PKDD’00)
• Generating new graphs with one more edge
• FSG (Kuramochi & Karypis, ICDM’01)
• Performance shows via edge growing is more efficient

• Methodology: Breadth-search, Apriori joining two size-k graphs
• Many possibilities at generating size-(k+1) candidate graphs

55

Pattern-Growth Approach

• Depth-first growth of subgraphs from k-edge to (k+1)-edge, then (k+2)-edge subgraphs

• Major challenge
• Generating many duplicate subgraphs
• Major idea to solve the problem
• Define an order to generate subgraphs
• DFS spanning tree: Flatten a graph into a sequence using depth-first search
• gSpan (Yan & Han, ICDM’02)

56

gSPAN: Graph Pattern Growth in Order

• Right-most path extension in subgraph pattern growth
• Right-most path: The path from root to the right-most leaf (choose the vertex with the smallest index at each step)
• Reduce generation of duplicate subgraphs
• Completeness: The enumeration of graphs using right-most path extension is complete
• DFS code: Flatten a graph into a sequence using depth-first search

57

Why Mine Closed Graph Patterns?

• 2ⁿ subgraphs -> closed frequent subgraphs
• A frequent graph G is closed if there exists no supergraph of G that carries the same support as G

​

​

​

​

• Lossless compression: Does not contain non-closed graphs, but still ensures that the mining result is complete
• Algorithm CloseGraph: Mines closed graph patterns directly

​

If this subgraph is closed in the graph dataset, it implies that none of its frequent super-graphs carries the same support

58

CloseGraph: Directly Mining Closed Graph Patterns

…

G

G₁

G₂

G_n

k-edge

(k+1)-edge

​

At what condition can we

stop searching their children,

i.e., early termination?

​

• CloseGraph: Mining closed graph patterns by extending gSpan (Yan & Han, KDD’03)

• Suppose G and G₁ are frequent, and G is a subgraph of G₁
• If in any part of the graph in the dataset where G occurs, G₁ also occurs, then we need not grow G (except some special, subtle cases), since none of G’s children will be closed except those of G₁

59

Experiment and Performance Comparison

• The AIDS antiviral screen compound dataset from NCI/NIH
• The dataset contains 43,905 chemical compounds
• Discovered patterns: The smaller minimum support, the bigger and more interesting subgraph patterns discovered

​

20%

10%

5%

Minimum support

Number of patterns

# of Patterns: Frequent vs. Closed

Run time (sec)

Runtime: Frequent vs. Closed

Minimum support

60

Application of Pattern Mining I: Graph Indexing

• Graph query: Find all the graphs in a graph DB containing a given query graph

Graph DB:

(a)

(b)

(c)

Path-indices: C, C-C, C-C-C, C-C-C-C cannot prune (a) & (b)

Only graph (c) contains Q

Query Q:

• Index should be a powerful tool
• Path-index may not work well
• Solution: Index directly on substructures (i.e., graphs)

61

gIndex: Indexing Frequent and Discriminative Substructures

• Why index frequent substructures?
• Too many substructures to index
• Size-increasing support threshold
• Large structures will likely be indexed well by their substructures
• Why discriminative substructures?

• Reduce the index size by an order of magnitude
• Selection: Given a set of selected structures f₁, f₂, .. f_n, and a new structure x, the extra indexing power is measured by

​

when Pr(x|f₁, f₂, …, f_n) is small enough, x is a discriminative structure and should be included in the index

• Experiments show that gIndex is small, effective, and stable

62

Application II: Support Substructure Similarity Search

• Find graphs in a graph DB containing substructures similar to a given query graph

(a)

(b)

(c)

• Ex. Data: A chemical compound DB
• A query graph q:

​

• How to do similarity search efficiently?
• No indexing? – Sequential scan + computing subgraph similarity – too costly!

​

• Build graph indices to support approximate search?
• Need an explosive number of subgraphs to cover all the similar subgraphs!
• An elegant solution (Yan, Yu, & Han, SIGMOD’05):
• Keep the graph index structure, but select features in the query space

63

Feature-Based Similarity Search

• Decompose a query graph into a set of features

• Feature-based similarity measure
• Each graph is represented as a feature vector X = {x₁, x₂, …, x_n}
• Similarity is defined by the distance of their corresponding vectors

• If graph G contains the major part of a query graph q, G should share a number of common features with q
• Given a relaxation ratio, one can calculate the maximal number of features that can be missed!

Assume: Query graph has 5 features

Relaxation threshold: Can miss at most 2 features

Then: G₁, G₂, G₃ are pruned

Graphs in database

features

A feature-graph matrix

64

Pattern Mining: Advanced Methods

• Mining Various Kinds of Patterns
• Mining Compressed or Approximate Patterns
• Constraint-based Pattern Mining
• Mining Sequential Patterns
• Mining Subgraph Patterns
• Pattern Mining: Application Examples
• Summary

65

Pattern Mining Application I: Software Bug Detection

• Mining rules from source code
• Bugs as deviant behavior (e.g., by statistical analysis)
• Mining programming rules (e.g., by frequent itemset mining)
• Mining function precedence protocols (e.g., by frequent subsequence mining)
• Revealing neglected conditions (e.g., by frequent itemset/subgraph mining)
• Mining rules from revision histories
• By frequent itemset mining
• Mining copy-paste patterns from source code
• Find copy-paste bugs (e.g., CP-Miner [Li et al., OSDI’04]) (to be discussed here)
• Reference: Z. Li, S. Lu, S. Myagmar, Y. Zhou, “CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code”, OSDI’04

66

Application Example: Mining Copy-and-Paste Bugs

• Copy-pasting is common
• 12% in Linux file system
• 19% in X Window system
• Copy-pasted code is error-prone
• Mine “forget-to-change” bugs by sequential pattern mining
• Build a sequence database from source code
• Mining sequential patterns
• Finding mismatched identifier names & bugs

void __init prom_meminit(void)

{

……

for (i=0; i<n; i++) {

total[i].adr = list[i].addr;

total[i].bytes = list[i].size;

total[i].more = &total[i+1];

}

……

for (i=0; i<n; i++) {

taken[i].adr = list[i].addr;

taken[i].bytes = list[i].size;

taken[i].more = &total[i+1];

}

(Simplified example from linux-2.6.6/arch/sparc/prom/memory.c)

Code copy-and- pasted but forget to change “id”!

Courtesy of Yuanyuan Zhou@UCSD

67

Building Sequence Database from Source Code

• Statement 🡪 number
• Tokenize each component
• Different operators, constants, key words 🡪 different tokens
• Same type of identifiers 🡪 same token
• Program 🡪 A long sequence
• Cut the long sequence by blocks

Map a statement to a number

Final sequence DB:�(65)�(16, 16, 71)�…�(65)�(16, 16, 71)

Courtesy of Yuanyuan Zhou@UCSD

(mapped to)

68

Sequential Pattern Mining & Detecting “Forget-to-Change” Bugs

• Modification to the sequence pattern mining algorithm
• Constrain the max gap

​

• Composing Larger Copy-Pasted Segments
• Combine the neighboring copy-pasted segments repeatedly
• Find conflicts: Identify names that cannot be mapped to the corresponding ones
• E.g., 1 out of 4 “total” is unchanged, unchanged ratio = 0.25
• If 0 < unchanged ratio < threshold, then report it as a bug
• CP-Miner reported many C-P bugs in Linux, Apache, … out of millions of LOC (lines of code)

​

Courtesy of Yuanyuan Zhou@UCSD

(16, 16, 71)�……�(16, 16, 10, 71)

Allow a maximal gap: inserting statements in copy-and-paste

69

Why Phrase Mining?

• Unigrams vs. phrases
• Unigrams (single words) are often ambiguous
• Example: “United”: United States? United Airline? United Parcel Service?
• Phrase: A natural, meaningful, unambiguous semantic unit
• Example: “United States” vs. “United Airline”
• Mining semantically meaningful phrases
• Transform text data from word granularity to phrase granularity
• Enhance the power and efficiency at manipulating unstructured data

70

From Frequent Pattern Mining to Phrase Mining

• General principle
• Exploit information redundancy and data-driven criteria to determine phrase boundaries and salience
• Methodology: Exploring three ideas
• Frequent pattern mining and colocation analysis
• Phrasal segmentation
• Quality phrase assessment
• Recent developments of phrase mining methods
• ToPMine: Mining quality phrase without training (A. El-Kishky, et al., 2015)
• SegPhrase: Mining quality phrase with tiny training sets (J. Liu, et al., 2015)
• AutoPhrase: Mining quality phrases with distant supervision (e.g., Wikipedia) (Shang, et al., 2018)

71

ToPMine: Phrase Mining before Topic Modeling

• ToPMine [El-Kishky et al. VLDB’15]: Phrase mining, then phrase-based topic modeling
• Phrase mining
• Frequent contiguous pattern mining: Extract candidate phrases and their counts
• Agglomerative merging of adjacent unigrams as guided by a significance score
• Document segmentation to count phrase occurrence
• Calculate rectified (i.e., true) phrase frequency
• Phrase ranking (using the criteria proposed in KERT)
• Popularity, concordance, informativeness, completeness
• Phrase-based topic modeling
• The mined bag-of-phrases are passed as input to PhraseLDA, an extension of LDA, that constrains all words in a phrase to each sharing the same latent topic

72

Collocation Mining

• Collocation: A sequence of words that occur more frequently than expected
• Often “interesting”, relay information not portrayed by their constituent terms
• Ex. “made an exception”, “strong tea”
• Many different measures used to extract collocations from a corpus [Dunning 93, Pederson 96]
• E.g., mutual information, t-test, z-test, chi-squared test, likelihood ratio

​

​

• Many of these measures can be used to guide the agglomerative phrase-segmentation algorithm

73

Phrase Candidate Generation: Frequent Pattern Mining + Statistical Analysis

Quality phrases

Based on significance score [Church et al.’91]:

α(P₁, P₂) ≈ (f(P₁●P₂) ̶ µ₀(P₁,P₂))/√ f(P₁●P₂)

Note for the first title:

• [feature selection] forms phrase but not [selection for] based on the significant scores computed
• [support vector machine] does not contribute to the counts of [support], [vector], [support vector], [vector machine]

74

ToPMine: Experiments on DBLP Abstracts

ToPMine is efficient and generates high-quality topics and phrases without any training data

75

ToPMine: Experiments on Yelp Reviews

ToPMine works well for phrase and topic mining in social media data

76

SagPhrase: Phrase Mining with Tiny Training Sets

• A small set of training data may enhance the quality of phrase mining

J. Liu et al., Mining Quality Phrases from Massive Text Corpora. In SIGMOD’15

77

SegPhrase+: The Overall Framework

• ClassPhrase: Frequent pattern mining, feature extraction, classification
• SegPhrase: Phrasal segmentation and phrase quality estimation
• SegPhrase+: One more round to enhance mined phrase quality

SegPhrase (a classifier is used)

​

Small labeled dataset

provided by experts

or

a distant supervised KB (e.g., Wikipedia / DBPedia)

78

SegPhrase: Pattern Mining and Feature Extraction

• Pattern Mining for Candidate Set
• Build a candidate phrases set by frequent pattern mining
• Mining frequent k-grams (k is typically small, e.g., 6 in the experiments)
• Popularity measured by raw frequent words and phrases mined from the corpus
• Feature Extraction: Concordance
• Partition a phrase into two parts to check whether the co-occurrence is significantly higher than pure random
• Feature Extraction: Informativeness
• Quality phrases typically start and end with a non-stopword
• “machine learning is” vs. “machine learning”
• Use average IDF over words in the phrase to measure the semantics
• Usually, the probabilities of a quality phrase in quotes, brackets, or connected by hyphen should be higher (punctuations information)
• e.g., “state-of-the-art”

79

SegPhrase: Classification Using Tiny Training Sets

• Use tiny training sets (300 labels for 1GB corpus; can also use phrases extracted from KBs)
• Label: indicating whether a phrase is a high quality one
• E.g., “support vector machine”: 1; “the experiment shows”: 0
• Classification: Construct models to distinguish quality phrases from poor ones
• Use Random Forest algorithm to bootstrap different datasets with limited labels
• Phrasal segmentation can tell which phrase is more appropriate
• Ex: “A standard [feature vector] [machine learning] setup is used to describe ......”

​

• Partition a sequence of words by maximizing the likelihood
• Consider length penalty and filter out phrases with low rectified frequency
• Process: Classification 🡪 Phrasal segmentation // SegPhrase
• Classification 🡪 Phrasal segmentation // SegPhrase+

​

​

Not counted towards the rectified frequency

80

Performance: Precision Recall Curves on DBLP

• Datasets:
• Evaluation
• Wiki Phrases (based on internal links, ~7K high quality phrases)
• Sampled 500*7 Wiki-uncovered phrases: Results evaluated by 3 reviewers
• Compared with other phrase-mining methods
• TF-IDF, C-Value, ConExtr, KEA, and ToPMine
• Also, Segphrase+ is efficient, linearly scalable

Use only 300 human labeled phrases for training

81

Experimental Results: Interesting Phrases�Generated (From Titles & Abstracts of SIGKDD)

Only in SegPhrase+

Only in Chunking

82

Mining Quality Phrases in Multiple Languages

• Both ToPMine and SegPhrase+ are extensible to mining quality phrases in multiple languages
• SegPhrase+ on Chinese (From Chinese Wikipedia)
• ToPMine on Arabic (From Quran (Fus7a Arabic)(no preprocessing)
• Experimental results of Arabic phrases:

كفروا 🡪 Those who disbelieve

بسم الله الرحمن الرحيم🡪 In the name of God the Gracious and Merciful