The need to re-publish the service depends on the nature of the change being made to the participating feature class validation attribute rules.
For Data Reviewer-based rules, changes that include the use of a new data source (such as the data source of the Features to Compare parameter in the Feature on Feature check) will require re-publishing if that data source is not already included in the service.
The same condition would apply when creating a new rule that includes a data source that is not already included in the service (such as including the destination data source when using the Relationship check) .