A Generic Framework for Interesting Subspace Cluster Detection in
  Multi-attributed Networks
  Detection of interesting (e.g., coherent or anomalous) clusters has been
studied extensively on plain or univariate networks, with various applications.
Recently, algorithms have been extended to networks with multiple attributes
for each node in the real-world. In a multi-attributed network, often, a
cluster of nodes is only interesting for a subset (subspace) of attributes, and
this type of clusters is called subspace clusters. However, in the current
literature, few methods are capable of detecting subspace clusters, which
involves concurrent feature selection and network cluster detection. These
relevant methods are mostly heuristic-driven and customized for specific
application scenarios.
  In this work, we present a generic and theoretical framework for detection of
interesting subspace clusters in large multi-attributed networks. Specifically,
we propose a subspace graph-structured matching pursuit algorithm, namely,
SG-Pursuit, to address a broad class of such problems for different score
functions (e.g., coherence or anomalous functions) and topology constraints
(e.g., connected subgraphs and dense subgraphs). We prove that our algorithm 1)
runs in nearly-linear time on the network size and the total number of
attributes and 2) enjoys rigorous guarantees (geometrical convergence rate and
tight error bound) analogous to those of the state-of-the-art algorithms for
sparse feature selection problems and subgraph detection problems. As a case
study, we specialize SG-Pursuit to optimize a number of well-known score
functions for two typical tasks, including detection of coherent dense and
anomalous connected subspace clusters in real-world networks. Empirical
evidence demonstrates that our proposed generic algorithm SG-Pursuit performs
superior over state-of-the-art methods that are designed specifically for these
two tasks.
