Unsupervised feature selection for attributed graphs. (15th April 2021) - Zhou, Ruizhi; Niu, Lingfeng; Yang, Hong
Abstract: Many real-world applications generate attributed graphs that contain both link structures and content information associated with nodes. Content information in real networks always contains high dimensional feature space. In recent years, unsupervised feature selection has been widely used in handling high dimensional data without label information. Most existing unsupervised feature selection methods assume that instances in datasets are independent and identically distributed. However, instances in attributed graphs are intrinsically correlated. Considering the wide applications of feature selection in attributed graphs, we propose a new unsupervised feature selection method based on regularized sparse learning. We use pseudo class labels to learn the interdependency from both link and content information, and embed the obtained information into a sparse learning based feature selection framework. In particular, a new regularization term is designed to learn link information, which capture group behavior among the connected instances utilizing latent social dimensions. To solve the proposed feature selection model, we consider both convex and nonconvex cases and design the corresponding algorithms based on the Alternating Direction Method of Multipliers (ADMM) combined with ConCave Convex Procedure (CCCP). Numerical studies are implemented on real-world datasets to validate the advantage of our new method. Highlights: A novel method of unsupervised feature selection for attributed graphs is given. Correlation learned from both link & content are embedded into sparse learning. A regularization which exploits the group behavior of linked data is proposed. Algorithms for convex/nonconvex regularization cases of our model are designed. Extensive numerical experiments validate the advantage of our new method.