  $k$-truss model is a typical cohesive subgraph model and has been received
considerable attention. However, the $k$-truss model lacks the ability to
reveal fine-grained structure information of the graph. Motivated by this, in
this paper, we propose a new model named ($k$,$\tau$)-truss that considers the
higher-order neighborhood ($\tau$ hop) information of an edge. Based on the
($k$,$\tau$)-truss model, we study the higher-order neighborhood truss
decomposition problem which computes the ($k$,$\tau$)-trusses for all possible
$k$ values regarding a given $\tau$. To address this problem, we first propose
a bottom-up decomposition algorithm to compute the ($k$,$\tau$)-truss in the
increasing order of $k$ values. Based on the algorithm, we devise three
optimization strategies to further improve the decomposition efficiency. We
evaluate our proposed model and algorithms on real datasets, and the
experimental results demonstrate the effectiveness of the ($k$,$\tau$)-truss
model and the efficiency of our proposed algorithms.
