Displaying link category with get_links

I am trying to figure out a way to use get_links to pull a a random list of links from my blogroll and also display which category the link is associated with. Any idea on how I can pull this data from the db?

For example:

• Link 1
  from: Category 3
• Link 2
  from: Category 2
• Link 3
  from: Category 1