Proposing and testing mechanistic hypotheses stands as one of the key applications of contemporary computational chemistry. In the majority of computational mechanistic analyses, the individual elementary steps leading from reactants to products are proposed by the user, based on learned chemical knowledge, intuition, or comparison to an existing well-characterized mechanism for a closely related chemical reaction. However, the prerequisite of prior chemical knowledge is a barrier to automated (or "black box") mechanistic generation and assessment, and it may simultaneously preclude mechanistic proposals that lie outside the "standard" chemical reaction set. In this Article, we propose a simple random-walk algorithm that searches for the set of elementary chemical reactions that transform defined reactant structures into target products. Our approach operates exclusively in the space of molecular connectivity matrices, seeking the set of chemically sensible bonding changes that link connectivity matrices for input reactant and product structures. We subsequently illustrate how atomic coordinates for each elementary reaction can be generated under the action of a graph-restraining potential, prior to further analysis by quantum chemical calculations. Our approach is successfully demonstrated for carbon monoxide oxidation, the water-gas shift reaction, and n-hexane aromatization, all catalyzed by Pt nanoparticles.