MISAGA: An Algorithm for Mining Interesting Subgraphs in Attributed Graphs.

Area of Science:

• Graph analytics
• Data mining
• Network science

Background:

• Attributed graphs represent entities with associated attribute values.
• Mining clusters or communities (interesting subgraphs) is crucial for graph analytics.
• Existing algorithms struggle with subgraph discovery based on attribute associations.

Purpose of the Study:

• To propose a novel algorithm, MISAGA, for discovering interesting subgraphs in attributed graphs.
• To address the limitations of topology-based subgraph mining algorithms.
• To enable the identification of meaningful structures based on attribute value associations.

Main Methods:

• MISAGA employs a probabilistic measure to assess the strength of association between attribute value pairs.
• It computes the degree of association between vertex pairs using an information-theoretic measure.
• Subgraph identification is formulated as a constrained optimization problem, solved via optimal vertex-subgraph affiliation.

Main Results:

• MISAGA successfully identifies interesting subgraphs by considering both edge structure and vertex association degrees.
• The algorithm was validated on several large-scale real-world attributed graphs.
• The approach demonstrated potential utility across various data mining applications.

Conclusions:

• MISAGA provides an effective method for mining interesting subgraphs in attributed graphs.
• The algorithm's ability to leverage attribute information enhances subgraph discovery.
• MISAGA shows promise for applications requiring the identification of complex patterns in attributed network data.