How to store datasets of lexical connections?
I would think you could use a graph database, perhaps Neo4J or Titan or something of that nature.  Or, if you want a simple file format, you could use one of the many formats that exist for representing graphs.  You can find a list and overview of some of them here.

Another option would be to store them in RDF using a triplestore like Jena.