Artificial neural network (ANN) architectures typically involve several successive layers of neurons, where pairs of successive layers are often fully connected. Although such neural network architectures may provide certain benefits, they also have potential drawbacks in terms of being computationally expensive and prone to overfitting. In this work, we explore a structural sparsification (pruning) technique for fully connected neural networks, which is inspired by graph-theoretic concepts of cliques and clique relaxations. Cliques in real-world graphs or networks (e.g., social, communication, and other types of networks) represent fully connected groups of nodes with all possible links, whereas clique relaxations are increasingly popular graph-theoretic concepts that “relax” certain characteristics of cliques by removing links, while still maintaining a certain level of structural connectivity and cohesion. Specifically, we propose using optimal R-robust 2-club network configurations, which has shown in our previous work to possess the so-called “strong attack tolerance” property: after the removal of any \(R-1\) nodes and/or links, these structures are guaranteed to maintain not only the overall connectivity but also short (two-hop) distances between any pair of nodes, while requiring the minimum possible number of links for the respective network design. We adapt the concept of optimal R-robust 2-club network configurations to a time-expanded setting in order to develop structurally sparsified ANN architectures, where the levels of sparseness of the resulting ANN architectures are explicitly controlled by the parameter R. We conduct computational experiments using the well-known FashionMNIST dataset. Preliminary results demonstrate that the proposed sparsified neural network architectures maintain high classification accuracy, while significantly reducing the network complexity. In addition, due to their explicit relationship to well-defined graph topologies, the proposed architectures may also be beneficial in terms of mechanistic interpretability, which seeks to explain a “black-box” model’s internal computations using human-understandable concepts, thus potentially contributing to explainable AI methods.