I haven't found a better graph-based VJ tool than Gephex to use in Linux or Windows (but haven't been looking much either), and it's not trivial to get it running on a modern Ubuntu system- but I've worked through all the compiler messages (with the big exception of leaving out ffmpeg) and have an archive of the results available for download.
Go here for details and a link to the download:
The reconfiguring may screw it up a little, otherwise let it install to my choice of directories and then move the bin and lib etc. files as appropriate.
I'm hoping there is a new and well-supported tool out there that can take the place of gephex- movid is not intended for VJ work but may be retrofittable.