  Mining discriminative features for graph data has attracted much attention in
recent years due to its important role in constructing graph classifiers,
generating graph indices, etc. Most measurement of interestingness of
discriminative subgraph features are defined on certain graphs, where the
structure of graph objects are certain, and the binary edges within each graph
represent the "presence" of linkages among the nodes. In many real-world
applications, however, the linkage structure of the graphs is inherently
uncertain. Therefore, existing measurements of interestingness based upon
certain graphs are unable to capture the structural uncertainty in these
applications effectively. In this paper, we study the problem of discriminative
subgraph feature selection from uncertain graphs. This problem is challenging
and different from conventional subgraph mining problems because both the
structure of the graph objects and the discrimination score of each subgraph
feature are uncertain. To address these challenges, we propose a novel
discriminative subgraph feature selection method, DUG, which can find
discriminative subgraph features in uncertain graphs based upon different
statistical measures including expectation, median, mode and phi-probability.
We first compute the probability distribution of the discrimination scores for
each subgraph feature based on dynamic programming. Then a branch-and-bound
algorithm is proposed to search for discriminative subgraphs efficiently.
Extensive experiments on various neuroimaging applications (i.e., Alzheimer's
Disease, ADHD and HIV) have been performed to analyze the gain in performance
by taking into account structural uncertainties in identifying discriminative
subgraph features for graph classification.
