The true problem to me here seems to be then that I don't know what type of queries I'll run in the future, so I can't attach proper labels (to edges or nodes, doesn't matter which).

I see this exact problem with bookmarking tools. I have a large collection of bookmarks with many kinds of tags (topical, meta-tags like !important, !soon, !followup, !share, ...), etc. But the reality is those tags are not sufficient to search for what I need - adding a piece of content and searching for it are far removed in time (weeks, months, sometimes years), and "future me" doesn't remember the context something he put in with. The today-me can't anticipate which of the pieces of content will be useful and to what end.

So I don't know _what to search for_ or _how to search for it_ == but just as importantly, I don't know _what use to label something for_ and _what terms/structure_ to add to it.

I think the semantic web must have assumed we'll tag/label things correctly, and the reality is we don't do it because it's on average too hard.