Graphs are a commonly used and well-studied mathematical abstraction for the modeling of complex systems. Three-dimensional (3D) structural geology is no exception, and graphs have received significant attention in recent years to characterize the connectivity for fracture sets, faults, geological units and reservoir compartments. The basis for these analyzes is to summarize an existing structural model as a graph, and to label the nodes and edges using the geological features of interest. In this sense, structural geologists building a 3D structural model are actually creating a graph. For this, they use geological reasoning to relate the various rock units of the subsurface. &#160;</p><p>As a matter of fact, the final graph corresponding to a 3D structural model also relates the input spatial data, such as field measurements or interpretive contact lines. Based on this observation, we have proposed a graph-based framework to stochastically model 3D fault networks from incomplete observations, which randomizes the assignment of fault evidence to fault objects. The geometry of these faults is then determined using existing geomodeling techniques. In this approach, each piece of data is considered as a node of a complete graph called a possibility graph. The edges of the possibility graph are valued by a likelihood that two graph nodes belong to the same fault surface, which makes it possible to quickly remove some edges corresponding the associations deemed impossible. A hierarchical simulation algorithm is then proposed, based on the observation that each fault network corresponds to a possible partitioning of the input graph into distinct cliques. This formulation allows to give upper bounds for the (very large) number of possibilities that can be generated. We give several examples of likelihoods that integrate prior geological knowledge (e.g., the fault size distribution and orientation distribution), and check the consistency of the sampling algorithm when more informative rules are used. These preliminary results show that the simulation method consistently explores the search space, but they also highlight the need to further study the mathematical and computational properties of the sampler. Nonetheless, this approach is promising to efficiently generate and cluster a large set of possible structural scenarios and the associated ensemble of structural models obtained by a combination of data-perturbation, interpolation and or model-perturbation.