I've experienced the same issue when using Graph# in a VSPackage. I was able to overcome the issue by not using Bindings for the graph, but by assigning the Graph property in CodeBehind.

This led to an exception that the WPFExtensions assembly could not be loaded when assigning the Graph property. I suspect that the reason for that is that in GraphSharp.Controls, the assembly is used in XAML, but the reference is not added when compiling as there are no references in code. I was able to fix this by adding the following line before assigning the Graph property:

var a = System.Reflection.Assembly.Load("WPFExtensions, Version=1.0.3437.34043, Culture=neutral, PublicKeyToken=null");

This line loads the WPFExtensions library before WPF tries to load it based on the reference in the XAML. Afterwards, the graph was shown.