More Web Proxy on the site http://driver.im/

research-article

Multi-modal constraint propagation for heterogeneous image clustering

Authors:

Horace H.S. Ip,

Zhiwu LuAuthors Info & Claims

MM '11: Proceedings of the 19th ACM international conference on Multimedia

Pages 143 - 152

https://doi.org/10.1145/2072298.2072318

Published: 28 November 2011 Publication History

Abstract

This paper presents a multi-modal constraint propagation approach to exploiting pairwise constraints for constrained clustering tasks on multi-modal datasets. Pairwise constraint propagation methods have previously been designed primarily for single modality data and cannot be directly applied to multi-modal data or a dataset with multiple representations. In this paper, we provide an effective solution to the multi-modal constraint propagation problem by decomposing it into a set of independent multi-graph based two-class label propagation subproblems which are then merged into a unified problem and solved by quadratic optimization. We also show that such a formulation yields a closed-form solution. Our approach allows the initial pairwise constraints to be propagated throughout the entire multi-modal dataset. The propagated constraints are further used to refine the similarities between the objects for subsequent clustering tasks. The proposed method has been tested in constrained clustering tasks on two real-life multi-modal image datasets and shown to achieve significant improvements with respect to the single modality methods.

References

[1]

S. Basu, M. Bilenko, and R. Mooney. A probabilistic framework for semi-supervised clustering. In SIGKDD, 2004.

Digital Library

[2]

F. Chung. Spectral graph theory. American Mathematical Society, 1997.

[3]

H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication. In FOCS, 2004.

Digital Library

[4]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of symbolic computation, 9(3):251--280, 1990.

Digital Library

[5]

A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. In ICCV, 2007.

[6]

Z. Fu, Z. Lu, H. Ip, Y. Peng, and H. Lu. Symmetric graph regularized constraint propagation. In AAAI, 2011.

[7]

B. Gao, T. Liu, T. Qin, X. Zheng, Q. Cheng, and W. Ma. Web image clustering by consistent utilization of visual features and surrounding texts. In ACM Multimedia, 2005.

Digital Library

[8]

S. Kamvar, D. Klein, and C. Manning. Spectral learning. In IJCAI, 2003.

Digital Library

[9]

B. Kulis, S. Basu, I. Dhillon, and R. Mooney. Semi-supervised graph clustering: a kernel approach. In ICML, 2005.

Digital Library

[10]

Z. Li, J. Liu, and X. Tang. Pairwise constraint propagation by semidefinite programming for semi-supervised classification. In ICML, 2008.

Digital Library

[11]

Z. Lu and M. Carreira-Perpinán. Constrained spectral clustering through affinity propagation. In CVPR, 2008.

[12]

Z. Lu and H. Ip. Image categorization by learning with context and consistency. In CVPR, 2009.

[13]

Z. Lu and H. Ip. Constrained spectral clustering via exhaustive and efficient constraint propagation. In ECCV, 2010.

Digital Library

[14]

B. Manjunath and W. Ma. Texture features for browsing and retrieval of image data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8):837--842, 1996.

Digital Library

[15]

S. Rüping and T. Scheffer. Learning with multiple views. In Proc. ICML Workshop on Learning with Multiple Views, 2005.

[16]

L. Shapiro and G. Stockman. Computer Vision. Prentice Hall, 2003.

Digital Library

[17]

J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000.

Digital Library

[18]

A. Strehl and J. Ghosh. Cluster ensembles--a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research, 3:583--617, 2003.

Digital Library

[19]

U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395--416, 2007.

Digital Library

[20]

K. Wagstaff and C. Cardie. Clustering with instance-level constraints. In ICML, 2000.

Digital Library

[21]

X. Wang and I. Davidson. Active spectral clustering. In ICDM, 2010.

Digital Library

[22]

X. Wang and I. Davidson. Flexible constrained spectral clustering. In SIGKDD, 2010.

Digital Library

[23]

X. Wang, W. Ma, G. Xue, and X. Li. Multi-model similarity propagation and its application for web image retrieval. In ACM Multimedia, 2004.

Digital Library

[24]

E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. In NIPS, 2003.

Digital Library

[25]

L. Xu, W. Li, and D. Schuurmans. Fast normalized cut with linear constraints. In CVPR, 2009.

[26]

D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In NIPS, 2004.

Digital Library

[27]

D. Zhou and C. Burges. Spectral clustering and transductive learning with multiple views. In ICML, 2007.

Digital Library

Cited By

Jia YLiu HHou JKwong SZhang Q(2022)Semisupervised Affinity Matrix Learning via Dual-Channel Information RecoveryIEEE Transactions on Cybernetics10.1109/TCYB.2020.304149352:8(7919-7930)Online publication date: Aug-2022
https://doi.org/10.1109/TCYB.2020.3041493
Zhao KCai ZSui QWei EZhu K(2022)Clustering Image Search Results by Entity DisambiguationMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44845-8_24(369-384)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44845-8_24
Jia YLiu HHou JKwong S(2020)Pairwise Constraint Propagation With Dual Adversarial Manifold RegularizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2020.297019531:12(5575-5587)Online publication date: Dec-2020
https://doi.org/10.1109/TNNLS.2020.2970195
Show More Cited By

Index Terms

Multi-modal constraint propagation for heterogeneous image clustering
1. Information systems
  1. Information retrieval
    1. Document representation

Recommendations

On Multi-modal Fusion Learning in constraint propagation
Abstract
Constraint propagation methods demonstrate splendid performance in constrained clustering tasks. Although some multi-modal constraint propagation methods have been proposed in recent years, a feasible and robust approach to multi-modal ...
Modalities consensus for multi-modal constraint propagation
MM '12: Proceedings of the 20th ACM international conference on Multimedia

This paper presents a novel modalities consensus framework for multi-modal pairwise constraint propagation (MCP). We first combine multiple single-modal constraint propagation (SCP) problems together, and then explicitly introduce a new modalities ...
Local similarity learning for pairwise constraint propagation

Pairwise constraint propagation studies the problem of propagating the scarce pairwise constraints across the entire dataset. Effective propagation algorithms have previously been designed based on the graph-based semi-supervised learning framework. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MM '11: Proceedings of the 19th ACM international conference on Multimedia

November 2011

944 pages

ISBN:9781450306164

DOI:10.1145/2072298

General Chairs:
K. Selçuk Candan
Arizona State University, USA
,
Sethuraman Panchanathan
Arizona State University, USA
,
Balakrishnan Prabhakaran
University of Texas at Dallas, USA
,
Program Chairs:
Hari Sundaram
Arizona State University, USA
,
Wu-Chi Feng
Portland State University, USA
,
Nicu Sebe
University of Trento, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 November 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MM '11

Sponsor:

SIGMM

MM '11: ACM Multimedia Conference

November 28 - December 1, 2011

Arizona, Scottsdale, USA

Acceptance Rates

Overall Acceptance Rate 2,145 of 8,556 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
516
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jia YLiu HHou JKwong SZhang Q(2022)Semisupervised Affinity Matrix Learning via Dual-Channel Information RecoveryIEEE Transactions on Cybernetics10.1109/TCYB.2020.304149352:8(7919-7930)Online publication date: Aug-2022
https://doi.org/10.1109/TCYB.2020.3041493
Zhao KCai ZSui QWei EZhu K(2022)Clustering Image Search Results by Entity DisambiguationMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44845-8_24(369-384)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44845-8_24
Jia YLiu HHou JKwong S(2020)Pairwise Constraint Propagation With Dual Adversarial Manifold RegularizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2020.297019531:12(5575-5587)Online publication date: Dec-2020
https://doi.org/10.1109/TNNLS.2020.2970195
Jing PSu YLi ZNie L(2020)Learning Robust Affinity Graph Representation for Multi-view ClusteringInformation Sciences10.1016/j.ins.2020.06.068Online publication date: Jul-2020
https://doi.org/10.1016/j.ins.2020.06.068
Chen CQian HChen WZheng ZZhu H(2019)Auto-weighted multi-view constrained spectral clusteringNeurocomputing10.1016/j.neucom.2019.06.098366:C(1-11)Online publication date: 13-Nov-2019
https://dl.acm.org/doi/10.1016/j.neucom.2019.06.098
Zhang JLi CSun ZLuo ZZhou CLi S(2019)Towards a unified multi-source-based optimization framework for multi-label learningApplied Soft Computing10.1016/j.asoc.2018.12.01676(425-435)Online publication date: Mar-2019
https://doi.org/10.1016/j.asoc.2018.12.016
Meng LTan AWunsch II DMeng LTan AWunsch II D(2019)Clustering and Its Extensions in the Social Media DomainAdaptive Resonance Theory in Social Media Data Clustering10.1007/978-3-030-02985-2_2(15-44)Online publication date: 1-May-2019
https://doi.org/10.1007/978-3-030-02985-2_2
Wu WJia YKwong SHou J(2018)Pairwise Constraint Propagation-Induced Symmetric Nonnegative Matrix FactorizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2018.283076129:12(6348-6361)Online publication date: Dec-2018
https://doi.org/10.1109/TNNLS.2018.2830761
Liu AShi YJing PLiu JSu Y(2018)Low-rank regularized multi-view inverse-covariance estimation for visual sentiment distribution predictionJournal of Visual Communication and Image Representation10.1016/j.jvcir.2018.11.00657(243-252)Online publication date: Nov-2018
https://doi.org/10.1016/j.jvcir.2018.11.006
Hu JSun ZSun YShi J(2018)Accumulative image categorizationMultimedia Tools and Applications10.1007/s11042-018-6152-977:24(32179-32211)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11042-018-6152-9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten