Regarding the term REST, as is the case with many software terms, there are lots of definitions. Since Roy T. Fielding coined it, his definition should carry more weight than others. However, being RESTful shouldn't be regarded as a religious thing, and being a service at level two doesn't mean that your APIs are inferior to the ones at level three. Whether or not you should implement HATEOAS depends on the nature of your APIs and whether or not it is worth the effort.