A non-automatic solution is to write underlines manually:
partial_key_attribute [label = <<u>P</u>A<u>R</u>T<u>I</u>A<u>L</u> <u>K</u>E<u>Y</u><br/><u>A</u>T<u>T</u>R<u>I</u>B<u>U</u>T<u>E</u>>];
Although ugly, at least this works with most kinds of use cases, although some preprocessing might be needed to make this more convenient.