First of, a refugee claim most likely fails if you are from Europe, even Ukraine. I`m from Hungary and I wish people would understand that it is a waste of time and money. Anyway, it is past.
As for a same sex common-law couple you will get no different treatment than heterosexual coupes. Canada does recognize gay marriage and common-law union, so that is not a problem. As the previous post indicated it is your task to prove your relationship. If you apply as common-law partners you have to show evidence that you lived together for at least a year: so tenancy agreement or lease, bills under both of your names. Furthermore you need to show evidence that you are living in a committed, marriage like relationship. Joint back account, savings, ownership of property, vehicle, wills and life insurances naming each other as beneficiary, money transfers can serve as proof. Also pictures, descreption from both of you explaining how your relationship developed. You may send affidavits from family members, friends stating that they know about your relationship, when how it started ect.
As a failed refugee claimant you won`t have an easy ride, you have to convince CIC that you did not enter into the relationship to gain status and as last resort to stay in the country. If it started at the same time as your claim failed I doubt that your sponsorship application will be approved unless there is a lot of supporting evidence.
You can always send additional proof up until 1st stage approval, so you might have to think what kind of evidence you have and send more.
Hope that I could help you a little.