  Effectively capturing graph node sequences in the form of vector embeddings
is critical to many applications. We achieve this by (i) first learning vector
embeddings of single graph nodes and (ii) then composing them to compactly
represent node sequences. Specifically, we propose SENSE-S (Semantically
Enhanced Node Sequence Embedding - for Single nodes), a skip-gram based novel
embedding mechanism, for single graph nodes that co-learns graph structure as
well as their textual descriptions. We demonstrate that SENSE-S vectors
increase the accuracy of multi-label classification tasks by up to 50% and
link-prediction tasks by up to 78% under a variety of scenarios using real
datasets. Based on SENSE-S, we next propose generic SENSE to compute composite
vectors that represent a sequence of nodes, where preserving the node order is
important. We prove that this approach is efficient in embedding node
sequences, and our experiments on real data confirm its high accuracy in node
order decoding.
