how to encode labels for relationship extraction
I would reommend parsing the sentences using something like spaCy, which will be able to build such relationships for you.

It will then be a matter of extracting the realtionships and deciding how you want to label them. Let's work through a small example. Imagine your big block of text contains many sentence. We first parse the big block, then could (optionally) extract just the sentence that we care about:

import spacy

nlp = spacy.load('en_core_web_sm')      # this defines our 'parser' for English
doc = nlp(big_block_of_text)            # you may want to clean the text beforehand


Assume we only want sentences that contain the word 'went':

sents = [sent for sent in doc.sents if 'went' in sent.string]


Here is an example of grammatically walking down the parse tree. I say semantically because we are using the grammar parts-of-speech to conditionally navigate (using e.g. nouns):

for sent in sents:                          # loop over each sentence
    for word in sent:                       # analyse each word
        if word.pos_ == 'NOUN':             # if it is a noun
            for child in word.children:     # find children (go down the tree)
                if child.pos_ == 'NOUN':    # select only nouns from the children
                    print(word, child)


I believe this snippet would extract the pairs in your given example, so the output would hopefully indeed be:

"He movie"
"they school"


There are many other parts-of-speech that you will be able to use to be more specific or match other use cases - check out the relevant spaCy docs.



How to actually encode the relationships between your target words will depend on their final purpose, i.e. what you eventually want to do with the encodings. You now have the noun pairs. If you want to retain the knowledge of where they actually came from (from which sentences), you could indeed build a hierarchy, that keeps a code for the origin sentence and then a code for each pair of words.