In this paper, we introduce a new and novel graph-theoretic steganographic approach applicable to online social networking services (SNSs). The proposed approach translates a secret message to be embedded as an undirected graph called messagegraph, the structural information of which is concealed within a new directed graph. The new directed graph is released in a SNS platform by producing a sequence of ordered multiple-user interaction events. To secure communication, we propose to split a specific vertex to multiple copies and insert new vertices and edges to the directed graph. A receiver is able to reconstruct the directed graph from observations. Both the message-graph and the secret message can be orderly retrieved without error. It is probably the first work deeply focusing on the practical design of interaction based steganography using graph-theoretic approach.