lines.sort(Comparator.comparing((String line) -> line.split(" -> ")[0])
            .thenComparing(line -> {
                String secondPart = line.split(" -> ")[1];
                return secondPart.split(" ")[0];
            })
            .thenComparing((l1, l2) -> {
                int result = l1.split("\\[label=")[1].compareTo(l2.split("\\[label=")[1]);
                return result != 0 ? -result : 0;
            }));

Final solution came down to this, To anyone stumbling upon this, better solution would be to parse line into Object which has fields with those keywords and then just compare them like e.g:

Comparator.comparing(X::obj1)
    .thenComparing(X::obj2)
    .thenComparing(X::relType)