research-article

A Graph Theoretic Approach for Multi-Objective Budget Constrained Capsule Wardrobe Recommendation

Authors:

Debopriyo Banerjee,

Shamik SuralAuthors Info & Claims

ACM Transactions on Information Systems (TOIS), Volume 40, Issue 1

Article No.: 1, Pages 1 - 33

https://doi.org/10.1145/3457182

Published: 08 September 2021 Publication History

Abstract

Traditionally, capsule wardrobes are manually designed by expert fashionistas through their creativity and technical prowess. The goal is to curate minimal fashion items that can be assembled into several compatible and versatile outfits. It is usually a cost and time intensive process, and hence lacks scalability. Although there are a few approaches that attempt to automate the process, they tend to ignore the price of items or shopping budget. In this article, we formulate this task as a multi-objective budget constrained capsule wardrobe recommendation (MOBCCWR) problem. It is modeled as a bipartite graph having two disjoint vertex sets corresponding to top-wear and bottom-wear items, respectively. An edge represents compatibility between the corresponding item pairs. The objective is to find a 1-neighbor subset of fashion items as a capsule wardrobe that jointly maximize compatibility and versatility scores by considering corresponding user-specified preference weight coefficients and an overall shopping budget as a means of achieving personalization. We study the complexity class of MOBCCWR, show that it is NP-Complete, and propose a greedy algorithm for finding a near-optimal solution in real time. We also analyze the time complexity and approximation bound for our algorithm. Experimental results show the effectiveness of the proposed approach on both real and synthetic datasets.

References

[1]

Yong-Yeol Ahn, Sebastian E. Ahnert, James P. Bagrow, and Albert-Laszlo Barabasi. 2011. Flavor network and the principles of food pairing. Journal of Scientific Reports 1, 196 (2011), 1–7.

[2]

Sihem Amer-Yahia, Francesco Bonchi, Carlos Castillo, Esteban Feuerstein, Isabel Mendez-Diaz, and Paula Zabala. 2014. Composite retrieval of diverse and complementary bundles. IEEE Transactions on Knowledge and Data Engineering 26, 11 (2014), 2662–2675.

[3]

Jinze Bai, Chang Zhou, Junshuai Song, Xiaoru Qu, Weiting An, Zhao Li, and Jun Gao. 2019. Personalized bundle list recommendation. In Proceedings of the 28th International Conference on World Wide Web (WWW’19). 60–71.

Digital Library

[4]

Glencora Borradaile, Brent Heeringa, and Gordon Wilfong. 2012. The knapsack problem with neighbour constraints. Journal of Discrete Algorithms 16 (2012), 224–235.

Digital Library

[5]

Chong Chen, Min Zhang, Weizhi Ma, Yiqun Liu, and Shaoping Ma. 2020. Jointly non-sampling learning for knowledge graph enhanced recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’20). 189–198.

Digital Library

[6]

Jia Chen, Qin Jin, Shiwan Zhao, Shenghua Bao, Li Zhang, Zhong Su, and Yong Yu. 2014. Does product recommendation meet its Waterloo in unexplored categories? No, price comes to help. In Proceedings of the 37th ACM International Conference on Research and Development in Information Retrieval (SIGIR’14). 667–676.

[7]

Shih-Fen S. Chen, Kent B. Monroe, and Yung-Chien Lou. 1998. The effects of framing price promotion messages on consumers’ perceptions and purchase intentions. Journal of Retailing 74, 3 (1998), 353–372.

[8]

Wen Chen, Pipei Huang, Jiaming Xu, Xin Guo, Cheng Guo, Fei Sun, Chao Li, Andreas Pfadler, Huan Zhao, and Binqiang Zhao. 2019. POG: Personalized outfit generation for fashion recommendation at Alibaba iFashion. In Proceedings of the 2019 ACM Conference on Knowledge Discovery and Data Mining (KDD’19). 2662–2670.

Digital Library

[9]

Xu Chen, Hanxiong Chen, Hongteng Xu, Yongfeng Zhang, Yixin Cao, Zheng Qin, and Hongyuan Zha. 2019. Personalized fashion recommendation with visual explanations based on multimodal attention network: Towards visually explainable recommendation. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’19). 765–774.

Digital Library

[10]

Xu Chen, Kun Xiong, Yongfeng Zhang, Long Xia, Dawei Yin, and Jimmy Xiangji Huang. 2020. Neural feature-aware recommendation with signed hypergraph convolutional network. ACM Transactions Information Systems 39, 1 (2020), Article 8, 22 pages.

[11]

Yifan Chen, Pengjie Ren, Yang Wang, and Maarten de Rijke. 2019. Bayesian personalized feature interaction selection for factorization machines. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’19). 665–674.

Digital Library

[12]

Yifan Chen, Yang Wang, Xiang Zhao, Jie Zou, and Maarten De Rijke. 2020. Block-aware item similarity models for top-n recommendation. ACM Transactions on Information Systems 38, 4 (2020), Article 42, 26 pages.

Digital Library

[13]

Chen Cheng, Haiqin Yang, Irwin King, and Michael R. Lyu. 2016. A unified point-of-interest recommendation framework in location-based social networks. ACM Transactions on Intelligent Systems and Technology 8, 1 (2016), Article 10, 21 pages.

Digital Library

[14]

Xue Dong, Xuemeng Song, Fuli Feng, Peiguang Jing, Xin-Shun Xu, and Liqiang Nie. 2019. Personalized capsule wardrobe creation with garment and user modeling. In Proceedings of the 2019 ACM International Conference on Multimedia (MM’19). 302–310.

Digital Library

[15]

Xue Dong, Jianlong Wu, Xuemeng Song, Hongjun Dai, and Liqiang Nie. 2020. Fashion compatibility modeling through a multi-modal try-on-guided scheme. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 771–780.

Digital Library

[16]

Esther Galbrun, Aristides Gionis, and Nikolaj Tatti. 2016. Top-k overlapping densest subgraphs. Journal of Data Mining and Knowledge Discovery 30, 5 (2016), 1134–1165.

Digital Library

[17]

Markus Ettl, Pavithra Harsha, Anna Papush, and Georgia Perakis. 2018. A data-driven approach to personalized bundle pricing and recommendation. Journal of Manufacturing & Service Operations Management 22, 3 (2018), 1–41.

[18]

Dehong Gao, Linbo Jin, Ben Chen, Minghui Qiu, Yi Wei, Yi Hu, and Hong-Ming Wang. 2020. FashionBERT: Text and image matching with adaptive loss for cross-modal retrieval. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’20). 2251–2260.

Digital Library

[19]

Nikita Golubtsov, Daniel Galper, and Andrey Filchenkov. 2016. Active adaptation of expert-based suggestions in ladieswear recommender system LookBooksClub via reinforcement learning. In Proceedings of the 2016 Biologically Inspired Cognitive Architectures for Young Scientists (BICA’16). 61–69.

[20]

Xianjing Han, Xuemeng Song, Yiyang Yao, Xin-Shun Xu, and Liqiang Nie. 2020. Neural compatibility modeling with probabilistic knowledge distillation. IEEE Transactions on Image Processing 29 (2020), 871–882.

Digital Library

[21]

Xianjing Han, Xuemeng Song, Jianhua Yin, Yinglong Wang, and Liqiang Nie. 2019. Prototype-guided attribute-wise interpretable scheme for clothing matching. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’19). 785–794.

Digital Library

[22]

Xintong Han, Zuxuan Wu, Yu-Gang Jiang, and Larry S. Davis. 2017. Learning fashion compatibility with bidirectional LSTMs. In Proceedings of the 2017 ACM International Conference on Multimedia (MM’17). 1078–1086.

[23]

Tong He and Yang Hu. 2018. FashionNet: Personalized outfit recommendation with deep neural network. arXiv:1810.02443.

[24]

Shintami Chusnul Hidayati, Cheng-Chun Hsu, Yu-Ting Chang, Kai-Lung Hua, Jianlong Fu, and Wen-Huang Cheng. 2018. What dress fits me best? Fashion recommendation on the clothing style for personal body shape. In Proceedings of the 2018 ACM International Conference on Multimedia (MM’18). 438–446.

[25]

Wei-Lin Hsiao and Kristen Grauman. 2018. Creating capsule wardrobes from fashion images. In Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR’18). 7161–7170.

[26]

Wei-Lin Hsiao and Kristen Grauman. 2019. ViBE: Dressing for diverse body shapes. arXiv:1912.06697.

[27]

Oscar H. Ibarra and Chul E. Kim. 1975. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22, 4 (1975), 463–468.

Digital Library

[28]

Wei Ji, Xi Li, Fei Wu, Zhijie Pan, and Yueting Zhuang. 2019. Human-centric clothing segmentation via deformable semantic locality-preserving network. IEEE Transactions on Circuits and Systems for Video Technology 30, 12 (2019), 1–12.

[29]

Wei Ji, Xi Li, Yueting Zhuang, Omar El Farouk Bourahla, Yixin Ji, Shihao Li, and Jiabao Cui. 2018. Semantic locality-aware deformable network for clothing segmentation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI’18). 764–770.

Digital Library

[30]

Yannis Kalantidis, Lyndon Kennedy, and Li-Jia Li. 2013. Getting the look: Clothing recognition and segmentation for automatic product suggestions in everyday photos. In Proceedings of the 3rd ACM International Conference on Multimedia Retrieval (ICMR’13). 105–112.

Digital Library

[31]

Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Introduction to NP-completeness of knapsack problems. In Knapsack Problems. Springer, Berlin, Germany, 483–493.

[32]

Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. 1999. The budgeted maximum coverage problem. Information Processing Letters 70, 1 (1999), 39–45.

Digital Library

[33]

M. Hadi Kiapour, Xufeng Han, Svetlana Lazebnik, Alexander C. Berg, and Tamara L. Berg. 2015. Where to buy it: Matching street clothing photos in online shops. In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV’15). 3343–3351.

[34]

Duje Kodzoman. 2019. The psychology of clothing: Meaning of colors, body image and gender expression in fashion. Textile & Leather Review 2, 2 (2019), 90–103.

[35]

Lakshman Krishnamurthi, Tridib Mazumdar, and S. P. Raj. 1992. Asymmetric response to price in consumer brand choice and purchase quantity decisions. Journal of Consumer Research 19, 3 (1992), 387–400.

[36]

Kedan Li, Chen Liu, Ranjitha Kumar, and David Forsyth. 2019. Using discriminative methods to learn fashion compatibility across datasets. arXiv:1906.07273.

[37]

Xingchen Li, Xiang Wang, Xiangnan He, Long Chen, Jun Xiao, and Tat-Seng Chua. 2020. Hierarchical fashion graph network for personalized outfit recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’20). 1–10.

Digital Library

[38]

Yuncheng Li, Liang Liang Cao, Jiang Zhu, and Jiebo Luo. 2017. Mining fashion outfit composition using an end-to-end deep learning approach on set data. IEEE Transactions on Multimedia 19, 8 (2017), 1946–1955.

Digital Library

[39]

Yujie Lin, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Jun Ma, and Maarten de Rijke. 2020. Explainable outfit recommendation with joint outfit matching and comment generation. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2020), 1502–1516.

[40]

Si Liu, Zheng Song, Guangcan Liu, Changsheng Xu, Hanqing Lu, and Shuicheng Yan. 2012. Street-to-shop: Cross-scenario clothing retrieval via parts alignment and auxiliary set. In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR’12). 3330–3337.

Digital Library

[41]

Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. 2015. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International Conference on Research and Development in Information Retrieval(SIGIR’15). 43–52.

[42]

Hai Thanh Nguyen, Thomas Almenningen, Martin Havig, Herman Schistad, Anders Kofod-Petersen, Helge Langseth, and Heri Ramampiaro. 2014. Learning to rank for personalised fashion recommender systems via implicit feedback. In Proceedings of the 2014 International Conference on Mining Intelligence and Knowledge Exploration (MIKE’14). 51–61.

[43]

Nilesh Pandey and Andreas Savakis. 2019. Poly-GAN: Multi-conditioned GAN for fashion synthesis. arXiv:1909.02165.

[44]

Ruihong Qiu, Zi Huang, Jingjing Li, and Hongzhi Yin. 2020. Exploiting cross-session information for session-based recommendation with graph neural networks. ACM Transactions on Information Systems 38, 3 (2020), Article 22, 23 pages.

Digital Library

[45]

Debapriya Roy, Sanchayan Santra, and Bhabatosh Chanda. 2020. LGVTON: A landmark guided approach to virtual try-on. arXiv:2004.00562.

[46]

Franco Scarselli, Marco Gori, Ah Chung Tsoia, Markus Hagenbuchner, and Gabriele Monfardini. 2009. The graph neural network model. IEEE Transactions on Neural Networks 20, 1 (2009), 61–80.

Digital Library

[47]

J. Ben Schafer, Joseph Konstan, and John Riedl. 1999. Recommender systems in e-commerce. In Proceedings of the 1st ACM Conference on Electronic Commerce (EC’99). 158–166.

Digital Library

[48]

Xuemeng Song, Fuli Feng, Jinhuan Liu, Zekun Li, Liqiang Nie, and Jun Ma. 2017. NeuroStylist: Neural compatibility modeling for clothing matching. In Proceedings of the 25th ACM International Conference on Multimedia (MM’17). 753–761.

Digital Library

[49]

Xuemeng Song, Liqiang Nie, Yinglong Wang, and Gary Marchionini. 2019. Compatibility Modeling: Data and Knowledge Applications for Clothing Matching. Morgan & Claypool.

[50]

Reuben Tan, Mariya I. Vasileva, Kate Saenko, and Bryan A. Plummer. 2019. Learning similarity conditions without explicit supervision. In Proceedings of the 2019 IEEE International Conference on Computer Vision (ICCV’19). 10373–10382.

[51]

Pongsate Tangseng, Zhipeng Wu, and Kota Yamaguchi. 2017. Looking at outfit to parse clothing. arXiv:1703.01386.

[52]

Vijay Vazirani. 2003. Approximation Algorithms. Springer-Verlag, Berlin, Germany.

Digital Library

[53]

Mengting Wan, Di Wang, Matt Goldman, Matt Taddy, Justin Rao, Jie Liu, Dimitrios Lymberopoulos, and Julian McAuley. 2017. Modeling consumer preferences and price sensitivities from large-scale grocery shopping transaction logs. In Proceedings of the 26th International Conference on World Wide Web (WWW’17). 1103–1112.

Digital Library

[54]

Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017. Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering 29, 12 (2017), 2724–2743.

[55]

Min Xie, Laks V. S. Lakshmanan, and Peter T. Wood. 2010. Breaking out of the box of recommendations: From items to packages. In Proceedings of the 4th ACM Conference on Recommender Systems (RecSys’10). ACM, New York, NY, 151–158.

[56]

Wei Yang, Ping Luo, and Liang Lin. 2014. Clothing co-parsing by joint image segmentation and labeling. In Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR’14). 3182–3189.

Digital Library

[57]

Xun Yang, Xiangnan He, Xiang Wang, Yunshan Ma, Fuli Feng, Meng Wang, and Tat-Seng Chua. 2019. Interpretable fashion matching with rich attributes. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’19). 775–784.

Digital Library

[58]

Xin Yang, Xuemeng Song, Xianjing Han, Haokun Wen, Jie Nie, and Liqiang Nie. 2020. Generative attribute manipulation scheme for flexible fashion search. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’20). 941–950.

Digital Library

[59]

Wenli Yu, Li Li Xiaofei Xu, Dengbao Wang, Jingyuan Wang, and Shiping Chen. 2017. ProductRec: Product bundle recommendation based on user’s sequential patterns in social networking service environment. In Proceedings of the 2017 IEEE International Conference on Web Services (ICWS’17). 301–308.

[60]

Guoshuai Zhao, Hao Fu, Ruihua Song, Tetsuya Sakai, Zhongxia Chen, Xing Xie, and Xueming Qian. 2019. Personalized reason generation for explainable song recommendation. ACM Transactions on Intelligent Systems and Technology 10, 4 (2019), Article 41, 21 pages.

Digital Library

[61]

Yu Zheng, Chen Gao, Xiangnan He, Yong Li, and Depeng Jin. 2020. Price-aware recommendation with graph convolutional networks. In Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE’20). 133–144.

[62]

Tao Zhu, Patrick Harrington, Junjun Li, and Lei Tang. 2014. Bundle recommendation in eCommerce. In Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’14). 657–666.

Digital Library

Cited By

Tanaka YOzaki T(2024)Interactive construction of personalized fashion capsule wardrobes with alternative item recommendations2024 7th International Conference on Information and Computer Technologies (ICICT)10.1109/ICICT62343.2024.00086(493-498)Online publication date: 15-Mar-2024
https://doi.org/10.1109/ICICT62343.2024.00086
Ni XXiong FPan SWu JWang LChen H(2023)Community Preserving Social Recommendation with Cyclic Transfer LearningACM Transactions on Information Systems10.1145/363111542:3(1-36)Online publication date: 29-Dec-2023
https://dl.acm.org/doi/10.1145/3631115
Chen LZhu GLiang WWang Y(2023)Multi-objective reinforcement learning approach for trip recommendationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120145226:COnline publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120145
Show More Cited By

Index Terms

A Graph Theoretic Approach for Multi-Objective Budget Constrained Capsule Wardrobe Recommendation

Recommendations

Fifth Workshop on Recommender Systems in Fashion and Retail – fashionXrecsys2023
RecSys '23: Proceedings of the 17th ACM Conference on Recommender Systems

Online Fashion retailers have significantly increased in popularity over the last decade, making it possible for customers to explore hundreds of thousands of products without the need to visit multiple stores or stand in long queues for checkout. ...
Fourth Workshop on Recommender Systems in Fashion and Retail – fashionXrecsys2022
RecSys '22: Proceedings of the 16th ACM Conference on Recommender Systems

Online Fashion retailers have significantly increased in popularity over the last decade, making it possible for customers to explore hundreds of thousands of products without the need to visit multiple stores or stand in long queues for checkout. ...
BOXREC: Recommending a Box of Preferred Outfits in Online Shopping
Survey Paper and Regular Paper

Fashionable outfits are generally created by expert fashionistas, who use their creativity and in-depth understanding of fashion to make attractive outfits. Over the past few years, automation of outfit composition has gained much attention from the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Information Systems

ACM Transactions on Information Systems Volume 40, Issue 1

January 2022

599 pages

ISSN:1046-8188

EISSN:1558-2868

DOI:10.1145/3483337

Editor:
Min Zhang
Tsinghua University, China

Issue’s Table of Contents

Copyright © 2021 Association for Computing Machinery.

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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 September 2021

Received: 01 July 2021

Accepted: 01 March 2021

Revised: 01 February 2021

Published in TOIS Volume 40, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
536
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)6

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tanaka YOzaki T(2024)Interactive construction of personalized fashion capsule wardrobes with alternative item recommendations2024 7th International Conference on Information and Computer Technologies (ICICT)10.1109/ICICT62343.2024.00086(493-498)Online publication date: 15-Mar-2024
https://doi.org/10.1109/ICICT62343.2024.00086
Ni XXiong FPan SWu JWang LChen H(2023)Community Preserving Social Recommendation with Cyclic Transfer LearningACM Transactions on Information Systems10.1145/363111542:3(1-36)Online publication date: 29-Dec-2023
https://dl.acm.org/doi/10.1145/3631115
Chen LZhu GLiang WWang Y(2023)Multi-objective reinforcement learning approach for trip recommendationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120145226:COnline publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120145
Tanaka YOzaki T(2022)An extension of optimal fashion capsule wardrobe construction by considering visual dissimilarity and number of good coordinates2022 Tenth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW57323.2022.00052(224-228)Online publication date: Nov-2022
https://doi.org/10.1109/CANDARW57323.2022.00052
Fazal RBhatti MRehman A(2022)Causality Analysis: The study of Size and Power based on riz-PC Algorithm of Graph Theoretic ApproachTechnological Forecasting and Social Change10.1016/j.techfore.2022.121691180(121691)Online publication date: Jul-2022
https://doi.org/10.1016/j.techfore.2022.121691
Zheng YWang D(2022)A survey of recommender systems with multi-objective optimizationNeurocomputing10.1016/j.neucom.2021.11.041474:C(141-153)Online publication date: 14-Feb-2022
https://dl.acm.org/doi/10.1016/j.neucom.2021.11.041

View Options

Get Access

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents