Order by on relationship field

How can I order a result set by something on its relationship?

I am trying to get the Eloquent equivalent of this:

SELECT * FROM users INNER JOIN roles ON users.role_id = roles.id ORDER BY roles.label DESC
Here is what I am trying (based on the documentation):

$order = 'desc';
$users = User::with(['role' => function ($q) use ($order) {
            $q->orderBy('label', $order);
        }])->paginate(10);

but it doesn't order them properly. What am I doing wrong?

EDIT: Not sure if showing the model relationship is relevant but here it is:

 public function role()
    {
        return $this->belongsTo(Role::class);
    }

via Chebli Mohamed