Given a graph $E$, an action of a group $G$ on $E$, and a $G$-valued cocycle $phi$ on the edges of $E$, we define a C*-algebra denoted ${cal O}_{G,E}$, which is shown to be isomorphic to the tight C*-algebra associated to a certain inverse semigroup $S_{G,E}$ built naturally from the triple $(G,E,phi)$. As a tight C*-algebra, ${cal O}_{G,E}$ is also isomorphic to the full C*-algebra of a naturally occurring groupoid ${cal G}_{tight}(S_{G,E})$. We then study the relationship between properties of the action, of the groupoid and of the C*-algebra, with an emphasis on situations in which ${cal O}_{G,E}$ is a Kirchberg algebra. Our main applications are to Katsura algebras and to certain algebras constructed by Nekrashevych from self-similar groups. These two classes of C*-algebras are shown to be special cases of our ${cal O}_{G,E}$, and many of their known properties are shown to follow from our general theory.