  This contribution proposes a new approach towards developing a class of
probabilistic methods for classifying attributed graphs. The key concept is
random attributed graph, which is defined as an attributed graph whose nodes
and edges are annotated by random variables. Every node/edge has two random
processes associated with it- occurence probability and the probability
distribution over the attribute values. These are estimated within the maximum
likelihood framework. The likelihood of a random attributed graph to generate
an outcome graph is used as a feature for classification. The proposed approach
is fast and robust to noise.
