Mining Statistically Significant Attribute Associations in Attributed\n Graphs

Recently, graphs have been widely used to represent many different kinds of\nreal world data or observations such as social networks, protein-protein\nnetworks, road networks, and so on. In many cases, each node in a graph is\nassociated with a set of its attributes and it is critical to not only consider\nthe link structure of a graph but also use the attribute information to achieve\nmore meaningful results in various graph mining tasks. Most previous works with\nattributed graphs take into ac- count attribute relationships only between\nindividually connected nodes. However, it should be greatly valuable to find\nout which sets of attributes are associated with each other and whether they\nare statistically significant or not. Mining such significant associations, we\ncan uncover novel relationships among the sets of attributes in the graph. We\npropose an algorithm that can find those attribute associations efficiently and\neffectively, and show experimental results that confirm the high applicability\nof the proposed algorithm.\n