From the Windows Guidelines:
Context menu: Do the following conditions apply:
- Is there a small set of contextual commands and options that apply to the selected object or window region?
- Are these menu items redundant?
- Are the target users familiar with context menus?
If so, consider providing context menus for the objects and window
regions that need them.
Do you have information as to why they can't find it? And does the contextmenu contain functionality which is only available via that menu?
Commands in a contextmenu should also be available in your UI via actionbuttons/ menu's/Toolbars/etc. Things that are visible to the user so they can find it and click it. A contextmenu is not visible and if the user does not expect a menu, or is not familiar with the concept, they probably won't find the functionality 'hidden' in your contextmenu.
Do you use contextmenu's in other parts of your application? That could also cause the problem. If you don't use them anywhere else the users won't expect them to exist on a graph and probably won't bother to try.
I would not create extra hints to the contextmenu. Instead I would use some sort of menubutton or toolbar which contains the contextmenu functionality. And besides that keep the contextmenu itself as well.
You can also put a dropdown menu in the top corner of the graph. When you click it it gives you the same menu as the contextmenu. Below is an example from VS2012: