Local Subgroup Discovery on Attributed Network Graphs
摘要
We find locally exceptional subgroups of nodes in attributed graphs, combining both node attributes and structural information to assess subgroup exceptionality. Subgroups are locally exceptional if their behavior deviates from the behavior of a well-chosen local peer group, as opposed to the more common generic subgroup discovery approach where behavior is compared to the global behavior across the full dataset. This notion of Local Subgroup Discovery had been introduced for traditional flat-table data; to the best of our knowledge, we are the first to incorporate this notion explicitly in graph data. Our approach combines shortest-path distance with Gower’s Distance, integrating both network structure and node attributes to rank nodes in relation to a prototype node. Combining this notion of exceptionality with existing LSD techniques, we discover local subgroups in three attributed graph datasets.