MemeSequencer: Sparse Matching for Embedding Image Macros

ABSTRACT

The analysis of the creation, mutation, and propagation of social media content on the Internet is an essential problem in computational social science, affecting areas ranging from marketing to political mobilization. A first step towards understanding the evolution of images online is the analysis of rapidly modifying and propagating memetic imagery or "memes". However, a pitfall in proceeding with such an investigation is the current incapability to produce a robust semantic space for such imagery, capable of understanding differences in Image Macros. In this study, we provide a first step in the systematic study of image evolution on the Internet, by proposing an algorithm based on sparse representations and deep learning to decouple various types of content in such images and produce a rich semantic embedding. We demonstrate the benefits of our approach on a variety of tasks pertaining to memes and Image Macros, such as image clustering, image retrieval, topic prediction and virality prediction, surpassing the existing methods on each. In addition to its utility on quantitative tasks, our method opens up the possibility of obtaining the first large-scale understanding of the evolution and propagation of memetic imagery.

References

1. {n. d.}. reddit: the front page of the internet. http://www.reddit.com/. ({n. d.}). Accessed: 2017-09--30.
2. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. {n. d.}. TensorFlow: A System for Large-Scale Machine Learning.
3. Lada A Adamic, Thomas M Lento, Eytan Adar, and Pauline C Ng. 2016. Information evolution in social networks. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. ACM, 473--482.
4. Edoardo Amaldi and Viggo Kann. 1998. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science 209, 1--2 (1998), 237--260.
5. Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic. 2012. The role of social networks in information diffusion. In Proceedings of the 21st international conference on World Wide Web. ACM, 519--528.
6. Albert-László Barabási. 2016. Network science. Cambridge university press.
7. Jonah Berger and Katherine L Milkman. 2012. What makes online content viral? Journal of marketing research 49, 2 (2012), 192--205.
8. Jonah Berger and Eric M Schwartz. 2011. What drives immediate and ongoing word of mouth? Journal of Marketing Research 48, 5 (2011), 869--880.
9. Vincent Buskens and Jeroen Weesie. 2000. Cooperation via social networks. Analyse & Kritik 22, 1 (2000), 44--74.
10. Vincent Buskens and Kazuo Yamaguchi. 1999. A new model for information diffusion in heterogeneous social networks. Sociological methodology 29, 1 (1999), 281--325.
11. Emmanuel J Candes, Justin K Romberg, and Terence Tao. 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics 59, 8 (2006), 1207--1223.
12. Scott Shaobing Chen, David L Donoho, and Michael A Saunders. 2001. Atomic decomposition by basis pursuit. SIAM review 43, 1 (2001), 129--159.
13. Justin Cheng, Lada Adamic, P Alex Dow, Jon Michael Kleinberg, and Jure Leskovec. 2014. Can cascades be predicted?. In Proceedings of the 23rd international conference on World wide web. ACM, 925--936.
14. Justin Cheng, Lada A Adamic, Jon M Kleinberg, and Jure Leskovec. 2016. Do Cascades Recur?. In Proceedings of the 25th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 671--681.
15. Ronan Collobert and Jason Weston. 2008. A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th international conference on Machine learning. ACM, 160--167.
16. Michele Coscia. 2013. Competition and Success in the Meme Pool: A Case Study on Quickmeme. com.
17. Michele Coscia. 2014. Average is boring: How similarity kills a meme's success. Scientific reports 4 (2014), 6477.
18. David L Davies and Donald W Bouldin. 1979. A cluster separation measure. IEEE transactions on pattern analysis and machine intelligence 2 (1979), 224--227.
19. Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 248--255.
20. Arturo Deza and Devi Parikh. 2015. Understanding image virality. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 1818--1826.
21. Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. 2014. Decaf: A deep convolutional activation feature for generic visual recognition. In International conference on machine learning. 647--655.
22. David L Donoho. 2006. For most large underdetermined systems of linear equations the minimal-norm solution is also the sparsest solution. Communications on pure and applied mathematics 59, 6 (2006), 797--829.
23. Cícero Nogueira Dos Santos and Maira Gatti. 2014. Deep Convolutional Neural Networks for Sentiment Analysis of Short Texts. In COLING. 69--78.
24. Abhimanyu Dubey and Sumeet Agarwal. 2017. Modeling Image Virality with Pairwise Spatial Transformer Networks. In Proceedings of the 2017 ACM on Multi- media Conference, MM 2017, Mountain View, CA, USA, October 23--27, 2017. 663--671.
25. Phil Edwards. {n. d.}. The reason every meme uses that one font. https://www.vox.com/2015/7/26/9036993/meme-font-impact/. ({n. d.}). Accessed: 2017-09--30.
26. James P Gleeson, Kevin P O'Sullivan, Raquel A Baños, and Yamir Moreno. 2016. Effects of network structure, competition and memory time on social spreading phenomena. Physical Review X 6, 2 (2016), 021019.
27. Alex Graves and Jurgen Schmidhuber. 2005. Framewise phoneme classification with bidirectional LSTM and other neural network architectures. Neural Networks 18, 5 (2005), 602--610.
28. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 770--778.
29. Chih-Wei Hsu and Chih-Jen Lin. 2002. A comparison of methods for multiclass support vector machines. IEEE transactions on Neural Networks 13, 2 (2002), 415--425.
30. Thorsten Joachims. 2002. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 133--142.
31. Eric Jones, Travis Oliphant, Pearu Peterson, et al. 2001--. SciPy: Open source scientific tools for Python. (2001--). http://www.scipy.org/ {Online; accessed 9/30/2017}.
32. Aditya Khosla, Atish Das Sarma, and Raffay Hamid. 2014. What makes an image popular?. In Proceedings of the 23rd international conference on World wide web. ACM, 867--876.
33. Ryan Kiros, Yukun Zhu, Ruslan R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015. Skip-thought vectors. In Advances in neural information processing systems. 3294--3302.
34. Michele Knobel and Colin Lankshear. {n. d.}. Online memes, affinities, and cultural production. ({n. d.}).
35. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems. 1097--1105.
36. Himabindu Lakkaraju, Julian J McAuley, and Jure Leskovec. 2013. What's in a Name? Understanding the Interplay between Titles, Content, and Communities in Social Media. (2013).
37. Jure Leskovec, Lars Backstrom, and Jon Kleinberg. 2009. Meme-tracking and the dynamics of the news cycle. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 497--506.
38. M Douglas McIlroy. 1960. Macro instruction extensions of compiler languages. Commun. ACM 3, 4 (1960), 214--220.
39. LR Medsker and LC Jain. 2001. Recurrent neural networks. Design and Applications 5 (2001).
40. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems. 3111--3119.
41. Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016. A corpus and evaluation framework for deeper understanding of commonsense stories. arXiv preprint arXiv:1604.01696 (2016).
42. Ruth Page. 2012. The linguistics of self-branding and micro-celebrity in Twitter: The role of hashtags. Discourse & communication 6, 2 (2012), 181--201.
43. Adam Paszke, Sam Gross, and Soumith Chintala. 2017. PyTorch. (2017).
44. Slobodan Petrovic. 2006. A comparison between the silhouette index and the davies-bouldin index in labelling ids clusters. In Proceedings of the 11th Nordic Workshop of Secure IT Systems. 53--64.
45. R Rehurek and P Sojka. 2011. Gensim--python framework for vector space modelling. NLP Centre, Faculty of Informatics, Masaryk University, Brno, Czech Republic 3, 2 (2011).
46. Daniel M Romero, Brendan Meeder, and Jon Kleinberg. 2011. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings of the 20th international conference on World wide web. ACM, 695--704.
47. Kazumi Saito, Ryohei Nakano, and Masahiro Kimura. 2008. Prediction of information diffusion probabilities for independent cascade model. In Knowledge-based intelligent information and engineering systems. Springer, 67--75.
48. Limor Shifman. 2013. Memes in a digital world: Reconciling with a conceptual troublemaker. Journal of Computer-Mediated Communication 18, 3 (2013), 362--377.
49. Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014).
50. Krishna Kumar Singh and Yong Jae Lee. 2016. End-to-end localization and ranking for relative attributes. In European Conference on Computer Vision. Springer, 753--769.
51. Ray Smith. 2007. An overview of the Tesseract OCR engine. In Document Analysis and Recognition, 2007. ICDAR 2007. Ninth International Conference on, Vol. 2. IEEE, 629--633.
52. Thomas W Valente. 1995. Network models of the diffusion of innovations. (1995).
53. Lilian Weng and Filippo Menczer. 2015. Topicality and impact in social media: diverse messages, focused messengers. PloS one 10, 2 (2015), e0118410.
54. Lilian Weng, Filipspo Menczer, and Yong-Yeol Ahn. 2013. Virality prediction and community structure in social networks. Scientific reports 3 (2013), 2522.
55. Lilian Weng, Filippo Menczer, and Yong-Yeol Ahn. 2014. Predicting Successful Memes Using Network and Community Structure.. In ICWSM.
56. John Wright, Allen Y Yang, Arvind Ganesh, S Shankar Sastry, and Yi Ma. 2009. Robust face recognition via sparse representation. IEEE transactions on pattern analysis and machine intelligence 31, 2 (2009), 210--227.
57. Fanyi Xiao and Yong Jae Lee. 2015. Discovering the spatial extent of relative attributes. In Proceedings of the IEEE International Conference on Computer Vision. 1458--1466.
58. Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alexander J Smola, and Eduard H Hovy. 2016. Hierarchical Attention Networks for Document Classification.. In HLT-NAACL. 1480--1489.
59. Chenxi Zhang, Jizhou Gao, Oliver Wang, Pierre Georgel, Ruigang Yang, James Davis, Jan-Michael Frahm, and Marc Pollefeys. 2014. Personal photograph enhancement using internet photo collections. IEEE transactions on visualization and computer graphics 20, 2 (2014), 262--275.
60. Ye Zhang and Byron Wallace. 2015. A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification. arXiv preprint arXiv:1510.03820 (2015).
61. Xiaoqing Zheng, Hanyang Chen, and Tianyu Xu. 2013. Deep Learning for Chinese Word Segmentation and POS Tagging. In EMNLP. 647--657.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision representations

        • Image representations

      • Computer vision tasks

        • Visual content-based indexing and retrieval

    • Knowledge representation and reasoning

      • Semantic networks

• Information systems

  • World Wide Web

    • Web applications

      • Social networks