Generalizing Design of Support Measures for Counting Frequent Patterns in Graphs

Area of Science:

• Computer Science
• Graph Theory
• Data Mining

Background:

• Frequent subgraph mining (FSM) is crucial in data analysis.
• Developing effective support measures for FSM patterns is a key challenge.
• Current methods often use hypergraph frameworks, unifying overlap-graph (MIS) and minimum image/instance (MNI) measures.

Purpose of the Study:

• To explore the space between existing FSM support measure types.
• To provide general sufficient conditions for designing novel FSM support measures within a hypergraph framework.
• To guide the development of new, efficient, and user-defined support measures.

Main Methods:

• Developed general sufficient conditions for constructing support measures in a hypergraph framework.
• Applied these conditions to generalize existing measures like Minimum Image/Instance (MNI) and Minimum Instance (MI).
• Introduced a novel Maximum Independent Subedge Set (MISS) measure.

Main Results:

• The proposed conditions successfully generalize MNI and MI measures, enabling user-defined linear-time measures.
• The new Maximum Independent Subedge Set (MISS) measure effectively bridges the gap between MIS and MI measures in terms of computational complexity and support count.
• Demonstrated applicability to measures beyond the overlap graph framework.

Conclusions:

• The established sufficient conditions offer a robust framework for creating new FSM support measures.
• The generalized and novel measures enhance the flexibility and efficiency of frequent subgraph mining.
• The MISS measure provides a valuable new option for balancing computational cost and pattern frequency in FSM.