Mining Attribute-Structure Correlated Patterns in Large Attributed Graphs
In this paper, the authors study the correlation between attribute sets and the occurrence of dense subgraphs in large attributed graphs, a task they call structural correlation pattern mining. A structural correlation pattern is a dense subgraph induced by a particular attribute set. Existing methods are not able to extract relevant knowledge regarding how vertex attributes interact with dense subgraphs. Structural correlation pattern mining combines aspects of frequent itemset and quasi-clique mining problems. They propose statistical significance measures that compare the structural correlation of attribute sets against their expected values using null models.