The UnitTestGraphConnectivity would sometimes fail on parallel devices (even though the tested graph is remarkably small). The issue was likely a race condition in the pointer jumping worklets where the worklet would check graph edges in an array and then update the connections in the same array.
These race conditions are removed by reading input connections from one array and writing the results to a separate array. The algorithm now seems more stable although it now requires more memory.