Present business rule modeling techniques are not capable enough to capture their semantic details suitable for cloud services. Only having virtualized hardware and enabling service oriented architecture will not make the enterprises completely suitable for cloud. The biggest challenge is how business rules can be incorporated in multi-tenant cloud applications such that the services can be able to support different lines of business of the enterprises. To encounter these problems in this paper a graph based business rule representation model called, Generalized Business Rule Dependency Graph (GBRDG) has been proposed. The GBRDG provides high level representation of business rules, their composition, dependencies and several dynamic properties suitable for cloud based applications using graph based semantics. The proposal also supports the reuse of the low level business rules and capable to accommodate the changes in business rules using rich set of semantic constructs and interrelationship.