Mining Attribute-structure Correlated Patterns in Large Attributed Graphs

1. INTRODUCTION

• Existing dense-subgraph definitions generally omit vertex attributes and do not explain how attribute sets induce dense subgraphs.The paper frames this as a question about the relationship between graph attributes and topology.Source: §1 · p. 1
• Structural correlation measures the probability that a vertex belongs to a dense subgraph in the graph induced by an attribute set; a pattern is such a dense subgraph.The paper treats the measure and its representative subgraphs as complementary information.Source: §1 · p. 1
• The mining task combines frequent itemset mining for attribute sets with quasi-cliques as the definition of dense subgraphs.This addresses the potentially large number of attribute sets and provides a dense-subgraph representation.Source: §1 · p. 1
• Statistical significance compares attribute-set structural correlation with a null-model expectation, while pattern size and density rank interesting patterns.The measures assess significance and pattern interestingness as distinct aspects.Source: §1 · pp. 1–2
• SCPM combines significance, size, and density constraints for pruning with efficient correlation-computation strategies, and its analyses of three real attributed graphs found relevant knowledge.The graphs are collaboration, music, and citation networks.Source: §1 · p. 2

2.1.1 Structural Correlation

• Structural correlation measures the probability that a vertex bearing an attribute set belongs to a quasi-clique in its induced graph; patterns pair that set with a homogeneous quasi-clique.Source: §2.1.1 · pp. 2–3

2.1.2 Structural Correlation Pattern Mining Problem

• Mining seeks supported attribute-set/quasi-clique pairs meeting support, correlation, density, and size thresholds; the problem is #P-hard.Source: §2.1.2 · p. 3

2.1.3 Statistical Significance of the Structural Correlation

• Null models compare structural correlation with its support-matched expectation; simulation estimates that expectation, while a degree-based analytical upper bound addresses costly high-r sampling.The upper bound can count threshold-degree vertices that are not in quasi-cliques because they connect to low-degree vertices.Source: §2.1.3 · pp. 3–4

2.2 Related Work

• Unlike attribute-complementarity methods and prior single-attribute correlation, this work combines multiple attributes, dense subgraphs, and efficient top-pattern enumeration.Source: §2.2 · pp. 4–5

3.1 Naive Algorithm

• The naive method enumerates frequent attribute sets, then quasi-cliques in each induced graph; both mining problems are #P-hard, limiting its expected scalability.It computes structural correlation by checking whether each vertex belongs to a quasi-clique.Source: §3.1 · p. 5

3.2 SCPM Algorithm

• SCPM prunes attribute sets and quasi-clique candidates, then returns the top-k most relevant structural correlation patterns.It avoids enumerating every frequent attribute set and checks a reduced set of quasi-clique candidates.Source: §3.2 · p. 5

3.2.1 Pruning Strategies for SCP Mining

• Theorem 3 prunes vertices using subset containment, while upper bounds on structural and normalized correlation prune attribute sets below minimum thresholds.Theorem 3 reduces the vertices checked; Theorems 4 and 5 reduce the attribute sets whose structural correlation is computed.Source: §3.2.1 · pp. 5–6

3.2.2 Computing the Structural Correlation

• For each induced graph, the algorithm checks lookahead quasi-cliques first and prunes candidates whose vertices are already covered, deriving structural correlation from vertex coverage.The set of vertices covered by quasi-cliques can be obtained from the identified quasi-cliques.Source: §3.2.2 · p. 6
• BFS explores smaller vertex sets first, whereas DFS extends sets as far as possible; BFS is expected to help when smaller quasi-cliques cover vertices more efficiently.The paper evaluates these search strategies.Source: §3.2.2 · p. 6

3.2.3 Enumerating Top-k Patterns

• Top-k enumeration uses DFS and prunes candidates unable to exceed the smallest current top-k pattern, raising the minimum size threshold as the result set improves.Patterns are ranked primarily by size and secondarily by density.Source: §3.2.3 · p. 7

4.1.1 DBLP

• 0.26 was the highest DBLP ϵ for {grid, applic}; {search, rank} led δlb at 635,349, while frequent sets generally had low ϵ.The analytical upper bound was not tight against simulation results but showed similar growth, supporting accurate comparisons.Source: §4.1.1 · pp. 8–9

4.1.2 LastFm

• 34 users formed the largest LastFm pattern around Van Morrison; frequent sets led raw ϵ but generally had low δlb because their coverage was close to expectation.The top δlb set was {S Stevens,Wilco}.Source: §4.1.2 · pp. 9–10

4.1.3 CiteSeer

• 164.40 was the highest CiteSeer δlb, for {node, wireless}; frequent sets had weaker correlation, while top sets mapped to recognizable topics and the largest pattern spanned several fields.Source: §4.1.3 · pp. 10–11

4.2 Performance Evaluation

• Up to 3 orders of magnitude faster, SCPM-DFS outperformed Naive; SCPM-BFS beat Naive throughout, and low top-k runtimes were significantly lower.Increasing ϵmin and δmin also yielded significant performance gains through pruning.Source: Figure 8 · p. 11, §4.2 · p. 11

4.3 Parameter Sensitivity and Setting

• More restrictive γmin and min size can lower average ϵ while raising δ; high σmin can raise ϵ yet lower δ when expected correlation also rises.The authors recommend choosing γmin and min size for the application, selecting σmin to yield significant expected correlation, and setting ϵmin, δmin, and k according to available resources and time.Source: §4.3 · p. 11

• Structural correlation measures how an attribute set relates to dense subgraphs in an attributed graph.Source: §5 · p. 11
• Normalization compares structural correlation with its expected value to measure statistical significance.Source: §5 · p. 11
• Search and pruning strategies support mining the largest and densest patterns, and the methods were applied to three real datasets.The reported patterns and algorithms provided relevant knowledge about correlations between attributes and dense subgraphs.Source: §5 · p. 12