Title: Ties That Bind - Characterizing Classes by Attributes and Social Ties,
Abstract: Given a set of attributed subgraphs known to be from different classes, how
can we discover their differences? There are many cases where collections of
subgraphs may be contrasted against each other. For example, they may be
assigned ground truth labels (spam/not-spam), or it may be desired to directly
compare the biological networks of different species or compound networks of
different chemicals.
In this work we introduce the problem of characterizing the differences
between attributed subgraphs that belong to different classes. We define this
characterization problem as one of partitioning the attributes into as many
groups as the number of classes, while maximizing the total attributed quality
score of all the given subgraphs.
We show that our attribute-to-class assignment problem is NP-hard and an
optimal $(1 - 1/e)$-approximation algorithm exists. We also propose two
different faster heuristics that are linear-time in the number of attributes
and subgraphs. Unlike previous work where only attributes were taken into
account for characterization, here we exploit both attributes and social ties
(i.e. graph structure).
Through extensive experiments, we compare our proposed algorithms, show
findings that agree with human intuition on datasets from Amazon co-purchases,
Congressional bill sponsorships, and DBLP co-authorships. We also show that our
approach of characterizing subgraphs is better suited for sense-making than
discriminating classification approaches.