Common Random Subgraph Modeling Using Multiple Instance Learning
Tao Xu, David Chiu, Iker Gondra · 2018
In balancing information that is typical of a class and discriminatory between classes, we aim at synthesizing a common random subgraph (CRSG) model from an ensemble of attributed graph data. The common random subgraph model incorporates both structural and probabilistic information of the data that is common of a class in the ensemble, while multiple instance learning provides an effective process in handling large number of samples and is tolerant of substantial irrelevant graph elements. The proposed two-level multiple instance learning that compares the data between graphs at one level (as bags of instances), but also takes into account structural relationships between graph elements (as instances) at the other level. The method is evaluated using benchmarked structural datasets taken from the IAM graph repository. The experimental results show that the method can generate a meaningful and informative common random subgraph model of a class, but also effective in applying it to classification tasks in discriminating between classes.