This paper develops a small-gain technique for the safety analysis and verification of interconnected systems with high-relative-degree safety constraints. In this technique, input-to-state safety (ISSf) is used to characterize how the safety of a subsystem is influenced by the external input, and ISSf-barrier functions (ISSf-BFs) with high relative degree are employed to capture the safety of subsystems. With a coordination transform, the relationship between ISSf-BFs and the existing high-relative-degree (or high-order) barrier functions is established in order to simplify the ISSf analysis. With the help of high-relative-degree ISSf-BFs, a small-gain theorem is proposed for safety verification. It is shown that, under the small-gain condition, i) the interconnection of ISSf subsystems is still ISSf; and ii) the overall interconnected system is input-to-state stable (ISS) with respect to the compositional safe set. The effectiveness of the proposed small-gain theorem is illustrated on the output-constrained decentralized control of two inverted pendulums connected by a spring mounted on two carts.