Overriding entity deletion with associations

I am trying to implement a soft delete feature in my project by overriding the DbContext.SaveChanges() method and undoing the deletion of any entities which implement my ISoftDelete interface.

interface ISoftDelete
{
  bool IsDeleted { get; set; }
}

In the SaveChanges() method I am calling my SoftDelete() method for every entry that is in the 'deleted' state and implements ISoftDelete.:

var entries = this.ChangeTracker.Entries().Where(x => (x.State == EntityState.Deleted) && x.Entity is ISoftDelete)
                    .ToList();
                entries.ForEach(SoftDelete);

My SoftDelete() method is as follows:

private void SoftDelete(DbEntityEntry entry)
{
    if (entry.State == EntityState.Deleted && entry.Entity is ISoftDelete)
    {
        entry.Reload();
        var entity = (ISoftDelete)entry.Entity;
        entity.IsDeleted = true;
        entry.State = EntityState.Modified;
    }
}

This will work perfectly until I run into an entity which has a one to one association to something else. At which point, an exception is thrown with this error:

{"A relationship from the 'ChildParent' AssociationSet is in the 'Deleted' state. Given multiplicity constraints, a corresponding 'Parent' must also in the 'Deleted' state."}

Is there a way to get all the associations for that entity and change the deleted state for them as well?

I've already tried getting the reference to the actual associated entity but the entity's EntityState is set to Unchanged instead of Deleted.