Mining Statistically Significant Attribute Associations in Attributed Graphs

Graphs are widely used to represent many different kinds of real world data such as social networks, protein-protein interactions, and road networks. In many cases, each node in a graph is associated with a set of its attributes and it is critical to not only consider the link structure of a graph but also use the attribute information to achieve more meaningful results in various graph mining tasks. Most previous works dealing with attributed graphs take into account attribute relationships only between individually connected nodes. However, it should be greatly valuable to find out which sets of attributes are associated with each other and whether or not they are statistically significant over an entire graph. Mining such significant associations, we can uncover novel relationships among the sets of attributes in the graph. We propose an algorithm that can find those attribute associations efficiently and effectively, and show experimental results that confirm the high efficacy of the proposed algorithm.