Abstract: Novel bond-level molecular descriptors based on linear maps similar to those defined in algebra theory are proposed. The kth edge-adjacency matrix (Ek) denotes the matrix of bond linear indices (non-stochastic) with respect to the canonical basis set. The kth stochastic edge-adjacency matrix, ESk, is here proposed as a new molecular representation easily calculated from Ek. Then, the kth stochastic bond linear indices are calculated using ESk as operators of linear transformations. In both cases, the bond-type formalism was developed. The kth non-stochastic and stochastic bond-type linear indices values are the sum of the kth nonstochastic and stochastic bond linear indices values for bonds of the same bond type, respectively. In the same way, the kth non-stochastic and stochastic total (whole-molecule) linear indices are calculated by summing up the kth non-stochastic and stochastic bond linear indices, correspondingly, of all bonds in the molecule. The new bond-based molecular descriptors were tested for suitability for the quantitative structure-property relationship (QSPR) by analyzing regressions of novel indices for selected physicochemical properties of octane isomers. All the found regression models are very significant from the statistical point of view and showed very good stability to data variation in leave-one-out crossvalidation experiments. General performance of the new descriptors in this QSPR studies has been evaluated with respect to the well-known sets of 2D/3D molecular descriptors. From the analysis, we can conclude that the non-stochastic and stochastic bond-based (total and bond-type) linear indices have an overall good modeling capability proving their usefulness in QSPR studies. The approach described in this work appears to be a very promising structural invariant, useful not alone for QSPR/QSAR studies, but also for similarity/diversity analysis and drug discovery protocols.