Towards feature selection in network
Published 24 October 2011
Quanquan Gu, Jiawei Han
Citations88
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents a supervised feature selection method based on Laplacian Regularized Least Squares (LapRLS) for networked data which uses linear regression to utilize the content information, and adopt graph regularization to consider the link information.
Abstract
Traditional feature selection methods assume that the data are independent and identically distributed (i.i.d.). However, in real world, there are tremendous amount of data which are distributing in a network. Existing features selection methods are not suited for networked data because the i.i.d. assumption no longer holds. This motivates us to study feature selection in a network. In this paper, we present a supervised feature selection method based on Laplacian Regularized Least Squares (LapRLS) for networked data. In detail, we use linear regression to utilize the content information, and adopt graph regularization to consider the link information. The proposed feature selection method aims at selecting a subset of features such that the empirical error of LapRLS is minimized. The resultant optimization problem is a mixed integer programming, which is difficult to solve. It is relaxed into a $L_{2,1}$-norm constrained LapRLS problem and solved by accelerated proximal gradient descent algorithm. Experiments on benchmark networked data sets show that the proposed feature selection method outperforms traditional feature selection method and the state of the art learning in network approaches.
Keywords
Computer ScienceSocial Sciences
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
Proceedings of the National Academy of SciencesModularity and community structure in networks
12,281 Citations2006M. E. J. Newman
It is shown that the modularity of a network can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which is called modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times.
Advances in industrial controlPattern Classification
7,884 Citations2000Evan L. Russell, Leo H. Chiang +1 more
Journal of Machine Learning ResearchAn introduction to variable and feature selection
7,831 Citations2003GuyonIsabelle, ElisseeffAndré
Neural ComputationLaplacian Eigenmaps for Dimensionality Reduction and Data Representation
7,709 Citations2003Mikhail Belkin, Partha Niyogi
This work proposes a geometrically motivated algorithm for representing the high-dimensional data that provides a computationally efficient approach to nonlinear dimensionality reduction that has locality-preserving properties and a natural connection to clustering.
A Comparative Study on Feature Selection in Text Categorization
4,766 Citations1997Yiming Yang, Jan Pedersen
DF thresholding, the simplest method with the lowest cost in computation, can be reliably used instead of IG or CHI when the computation of these measures are too expensive, and strong correlations between the DF, IG and CHI values of a term are found.
Locality Preserving Projections
3,955 Citations2003Xiaofei He, Partha Niyogi
These are linear projective maps that arise by solving a variational problem that optimally preserves the neighborhood structure of the data set by finding the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the manifold.
MPG.PuRe (Max Planck Society)Learning with Local and Global Consistency
3,750 Citations2003Dengyong Zhou, Olivier Bousquet +3 more
A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points.
Medical Entomology and ZoologyIntroductory Lectures on Convex Optimization: A Basic Course
3,707 Citations2014Ю Е Нестеров
Semi-supervised learning using Gaussian fields and harmonic functions
3,377 Citations2003Xiaojin Zhu, Zoubin Ghahramani +1 more
AI MagazineCollective Classification in Network Data
3,287 Citations2008Prithviraj Sen, Galileo Namata +4 more
This article introduces four of the most widely used inference algorithms for classifying networked data and empirically compare them on both synthetic and real-world data.
Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples
3,266 Citations2006Mikhail Belkin, Partha Niyogi +1 more
A semi-supervised framework that incorporates labeled and unlabeled data in a general-purpose learner is proposed and properties of reproducing kernel Hilbert spaces are used to prove new Representer theorems that provide theoretical basis for the algorithms.
IEEE Transactions on Pattern Analysis and Machine IntelligenceGraph Embedding and Extensions: A General Framework for Dimensionality Reduction
2,863 Citations2006Shuicheng Yan, Dong Xu +4 more
Machine LearningUnsupervised Learning by Probabilistic Latent Semantic Analysis
2,443 Citations2001Thomas Hofmann
This paper proposes to make use of a temperature controlled version of the Expectation Maximization algorithm for model fitting, which has shown excellent performance in practice, and results in a more principled approach with a solid foundation in statistical inference.
Journal of Machine Learning ResearchManifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples
2,130 Citations2006BelkinMikhail, NiyogiPartha +1 more
Lecture notes in computer scienceKernels and Regularization on Graphs
839 Citations2003Alexander J. Smola, Risi Kondor
It is shown that the class of positive, monotonically decreasing functions on the unit interval leads to kernels and corresponding regularization operators and can be found as a special case of the reasoning.
arXiv (Cornell University)Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization
553 Citations2012Jun Liu, Shuiwang Ji +1 more
This paper proposes to accelerate the computation of the l2, 1-norm regularized regression model by reformulating it as two equivalent smooth convex optimization problems which are then solved via the Nesterov's method---an optimal first-order black-box method for smooth conveX optimization.
An accelerated gradient method for trace norm minimization
540 Citations2009Shuiwang Ji, Jieping Ye
This paper exploits the special structure of the trace norm, based on which it is proposed an extended gradient algorithm that converges as O(1/k) and proposes an accelerated gradient algorithm, which achieves the optimal convergence rate of O( 1/k2) for smooth problems.
The Missing Link - A Probabilistic Model of Document Content and Hypertext Connectivity
439 Citations2000David Cohn, Thomas Hofmann
A joint probabilistic model for modeling the contents and inter-connectivity of document collections such as sets of web pages or research paper archives is described, based on a Probabilistic factor decomposition.
Learning from labeled and unlabeled data on a directed graph
403 Citations2005Dengyong Zhou, Jiayuan Huang +1 more
A general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered, which generalizes the spectral clustering approach for undirected graphs.
PubMedGraph embedding and extensions: a general framework for dimensionality reduction.
381 Citations2007Shuicheng Yan, Dong Xu +4 more
A new supervised dimensionality reduction algorithm called marginal Fisher analysis is proposed in which the intrinsic graph characterizes the intraclass compactness and connects each data point with its neighboring points of the same class, while the penalty graph connects the marginal points and characterizing the interclass separability.
Combining content and link for classification using matrix factorization
263 Citations2007Shenghuo Zhu, Kai Yu +2 more
This paper aims to design an algorithm that exploits both the content and linkage information, by carrying out a joint factorization on both the linkage adjacency matrix and the document-term matrix, and derives a new representation for web pages in a low-dimensional factor space, without explicitly separating them as content, hub or authority factors.
Generalized Fisher score for feature selection
221 Citations2011Quanquan Gu, Zhenhui Li +1 more
Experiments indicate that the proposed generalized Fisher score to jointly select features outperforms Fisher score as well as many other state-of-the-art feature selection methods.
Active Learning for Networked Data
149 Citations2010Mustafa Bilgic, Lilyana Mihalkova +1 more
A novel active learning algorithm is introduced for classification of network data that effectively exploits the links between instances and the interaction between the local and collective aspects of a classifier to improve the accuracy of learning from fewer labeled examples.
Relation regularized matrix factorization
103 Citations2009Wu-Jun Li, Dit‐Yan Yeung
A novel MF method called relation regularized matrix factorization (RRMF) is proposed, which seamlessly integrates both the relation information and the content information into a principled framework and a linear-time learning algorithm with convergence guarantee to learn the parameters of RRMF is proposed.
DIAL (Catholic University of Leuven)Introductory lectures on convex optimization : a basic course
46 Citations2004Nesterov, Yurii
Probabilistic Relational PCA
17 Citations2009Wu-Jun Li, Dit‐Yan Yeung +1 more
By explicitly modeling covariance between instances as derived from the relational information, a novel probabilistic dimensionality reduction method is proposed, called Probabilistic relational PCA (PRPCA), for relational data analysis.
Combining link and content for collective active learning
9 Citations2010Lixin Shi, Yuhang Zhao +1 more
This paper defines an objective function based on three criteria and presents an efficient algorithm to optimize the objective function with a bounded approximation rate and results on a real-world data sets demonstrate the effectiveness of the proposed approach.
ScienceAMERICAN MATHEMATICAL SOCIETY
8 Citations1899B. K. Parady, Joel F. Smith +2 more
A discussion of the Calculus Sequence as gateway or gatekeeper and the essential elements to providing a relevant program in today’s world are examined.