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%.