The Web bears the potential to become the world's most comprehensive knowledge base. Organizing information from the Web into entity-relationship graph structures could
be a first step towards unleashing this potential. In a second step, the inherent semantics of such structures would have to be exploited by expressive search techniques that go beyond
today's keyword search paradigm. In this realm, we have developed NAGA (Not Another Google Answer), a semantic search engine which provides expressive means for querying,
searching and ranking at entity-relationship level. For knowledge discovery tasks, like finding broad or interesting relations between k (>=2) given entities NAGA comes with two
efficient algorithms: STAR (Steiner Tree Approximation in Relationship Graphs), and MING (Mining Informative Graphs). NAGA is a fully implemented prototype system and is part
of the YAGO-NAGA project.