Unsupervised link selection in networks

Quanquan Gu, Charu Aggarwal, Jiawei Han

Research output: Contribution to journalConference article

Abstract

Real-world networks are often noisy, and the existing linkage structure may not be reliable. For example, a link which connects nodes from different communities may affect the group assignment of nodes in a negative way. In this paper, we study a new problem called link selection, which can be seen as the network equivalent of the traditional feature selection problem in machine learning. More specifically, we investigate unsupervised link selection as follows: given a network, it selects a subset of informative links from the original network which enhance the quality of community structures. To achieve this goal, we use Ratio Cut size of a network as the quality measure. The resulting link selection approach can be formulated as a semi-definite programming problem. In order to solve it efficiently, we propose a backward elimination algorithm using sequential optimization. Experiments on benchmark network datasets illustrate the effectiveness of our method.

Original languageEnglish (US)
Pages (from-to)298-306
Number of pages9
JournalJournal of Machine Learning Research
Volume31
StatePublished - Jan 1 2013
Event16th International Conference on Artificial Intelligence and Statistics, AISTATS 2013 - Scottsdale, United States
Duration: Apr 29 2013May 1 2013

Fingerprint

Learning systems
Feature extraction
Experiments
Quality Measures
Community Structure
Sequential Algorithm
Semidefinite Programming
Vertex of a graph
Linkage
Feature Selection
Elimination
Machine Learning
Assignment
Benchmark
Subset
Optimization
Experiment

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Cite this

Unsupervised link selection in networks. / Gu, Quanquan; Aggarwal, Charu; Han, Jiawei.

In: Journal of Machine Learning Research, Vol. 31, 01.01.2013, p. 298-306.

Research output: Contribution to journalConference article

Gu, Quanquan ; Aggarwal, Charu ; Han, Jiawei. / Unsupervised link selection in networks. In: Journal of Machine Learning Research. 2013 ; Vol. 31. pp. 298-306.
@article{7d66367af1ef4826a4f570e01655420c,
title = "Unsupervised link selection in networks",
abstract = "Real-world networks are often noisy, and the existing linkage structure may not be reliable. For example, a link which connects nodes from different communities may affect the group assignment of nodes in a negative way. In this paper, we study a new problem called link selection, which can be seen as the network equivalent of the traditional feature selection problem in machine learning. More specifically, we investigate unsupervised link selection as follows: given a network, it selects a subset of informative links from the original network which enhance the quality of community structures. To achieve this goal, we use Ratio Cut size of a network as the quality measure. The resulting link selection approach can be formulated as a semi-definite programming problem. In order to solve it efficiently, we propose a backward elimination algorithm using sequential optimization. Experiments on benchmark network datasets illustrate the effectiveness of our method.",
author = "Quanquan Gu and Charu Aggarwal and Jiawei Han",
year = "2013",
month = "1",
day = "1",
language = "English (US)",
volume = "31",
pages = "298--306",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",

}

TY - JOUR

T1 - Unsupervised link selection in networks

AU - Gu, Quanquan

AU - Aggarwal, Charu

AU - Han, Jiawei

PY - 2013/1/1

Y1 - 2013/1/1

N2 - Real-world networks are often noisy, and the existing linkage structure may not be reliable. For example, a link which connects nodes from different communities may affect the group assignment of nodes in a negative way. In this paper, we study a new problem called link selection, which can be seen as the network equivalent of the traditional feature selection problem in machine learning. More specifically, we investigate unsupervised link selection as follows: given a network, it selects a subset of informative links from the original network which enhance the quality of community structures. To achieve this goal, we use Ratio Cut size of a network as the quality measure. The resulting link selection approach can be formulated as a semi-definite programming problem. In order to solve it efficiently, we propose a backward elimination algorithm using sequential optimization. Experiments on benchmark network datasets illustrate the effectiveness of our method.

AB - Real-world networks are often noisy, and the existing linkage structure may not be reliable. For example, a link which connects nodes from different communities may affect the group assignment of nodes in a negative way. In this paper, we study a new problem called link selection, which can be seen as the network equivalent of the traditional feature selection problem in machine learning. More specifically, we investigate unsupervised link selection as follows: given a network, it selects a subset of informative links from the original network which enhance the quality of community structures. To achieve this goal, we use Ratio Cut size of a network as the quality measure. The resulting link selection approach can be formulated as a semi-definite programming problem. In order to solve it efficiently, we propose a backward elimination algorithm using sequential optimization. Experiments on benchmark network datasets illustrate the effectiveness of our method.

UR - http://www.scopus.com/inward/record.url?scp=84954242273&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84954242273&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84954242273

VL - 31

SP - 298

EP - 306

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

ER -