Moving beyond $L_p$ geometric structure, we propose novel efficient Orlicz-Sobolev approaches (i.e., Orlicz-EPT, and Orlicz-Sobolev transport) for measures on a graph, possibly having different total mass.