First order random graphs as introduced by Wong are a promising tool for structure-based classi$cation. Their complexity,
however, hampers their practical application. We describe an extension to $rst order random graphs which uses continuous
Gaussian distributions to model the densities of all random elements in a random graph. These First Order Gaussian Graphs
(FOGGs) are shown to have several nice properties which allow for fast and e#cient clustering and classi$cation. Speci$cally,
we show how the entropy of a FOGG may be computed directly from the Gaussian parameters of its random elements. This
allows for fast and memoryless computation of the objective function used in the clustering procedure used for learning a
graphical model of a class. We give a comparative evaluation between FOGGs and several traditional statistical classi$ers.
On our example problem, selected from the area of document analysis, our $rst order Gaussian graph classi$er signi$cantly
outperforms statistical, feature-based classi$ers. The FOGG classi$er achieves a classi$cation accuracy of approximately 98%,
while the best statistical classi$ers only manage approximately 91%.
@Article{BagdanovPR2003,
author = "Bagdanov, A. and Worring, M.",
title = "First Order Gaussian Graphs for Efficient Structure Classification",
journal = "Pattern Recognition",
volume = "36",
pages = "1311--1324",
year = "2003",
url = "https://ivi.fnwi.uva.nl/isis/publications/2003/BagdanovPR2003",
pdf = "https://ivi.fnwi.uva.nl/isis/publications/2003/BagdanovPR2003/BagdanovPR2003.pdf"
}