skip to main content
10.1145/3206025.3206062acmconferencesArticle/Chapter ViewAbstractPublication PagesicmrConference Proceedingsconference-collections
research-article

Exploiting Relational Information in Social Networks using Geometric Deep Learning on Hypergraphs

Published: 05 June 2018 Publication History

Abstract

Online social networks are constituted by a diverse set of entities including users, images and posts which makes the task of predicting interdependencies between entities challenging. We need a model that transfers information from a given type of relations between entities to predict other types of relations, irrespective of the type of entity. In order to devise a generic framework, one needs to capture the relational information between entities without any entity dependent information. However, there are two challenges: (a) a social network has an intrinsic community structure. In these communities, some relations are much more complicated than pairwise relations, thus cannot be simply modeled by a graph; (b) there are different types of entities and relations in a social network, taking into account all of them makes it difficult to formulate a model. In this paper, we claim that representing social networks using hypergraphs improves the task of predicting missing information about an entity by capturing higher-order relations. We study the behavior of our method by performing experiments on CLEF dataset consisting of images from Flickr, an online photo sharing social network.

References

[1]
Sameer Agarwal, Kristin Branson, and Serge Belongie. 2006. Higher order learning with graphs. In Proceedings of the 23rd international conference on Machine learning. ACM, 17--24.
[2]
Kirell Benzi, Vassiiis Kalofolias, Xavier Bresson, and Pierre Vandergheynst. 2016. Song recommendation with non-negative matrix factorization and graph total variation. In Acoustics, Speech and Signal Processing (ICASSP), 2016 IEEE International Conference on. Ieee, 2439--2443.
[3]
Claude Berge. 1973. Graphs and Hypergraphs (North-Holland mathematical library; v. 6). Elsevier.
[4]
Davide Boscaini, Jonathan Masci, Emanuele Rodolà, and Michael Bronstein. 2016. Learning shape correspondence with anisotropic convolutional neural networks Advances in Neural Information Processing Systems. 3189--3197.
[5]
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. 2017. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine Vol. 34, 4 (2017), 18--42.
[6]
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. 2014. Spectral networks and locally connected networks on graphs International Conference on Learning Representations (ICLR2014), CBLS, April 2014.
[7]
Jiajun Bu, Shulong Tan, Chun Chen, Can Wang, Hao Wu, Lijun Zhang, and Xiaofei He. 2010. Music recommendation by unified hypergraph: combining social media information and music content. In Proceedings of the 18th ACM international conference on Multimedia. ACM, 391--400.
[8]
Emmanuel J Candes and Yaniv Plan. 2010. Matrix completion with noise. Proc. IEEE Vol. 98, 6 (2010), 925--936.
[9]
Gang Chen, Jianwen Zhang, Fei Wang, Changshui Zhang, and Yuli Gao. 2009. Efficient multi-label classification with hypergraph regularization Proceedings of Computer Vision and Pattern Recognition, 2009. CVPR. IEEE, 1658--1665.
[10]
Jinpeng Chen, Hongbo Gao, Zhenyu Wu, and Deyi Li. 2013. Tag co-occurrence relationship prediction in heterogeneous information networks Parallel and Distributed Systems (ICPADS), 2013 International Conference on. IEEE, 528--533.
[11]
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering Advances in Neural Information Processing Systems. 3844--3852.
[12]
Christopher P Diehl, Galileo Namata, and Lise Getoor. 2007. Relationship identification for social network discovery AAAI, Vol. Vol. 22. 546--552.
[13]
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015. Convolutional networks on graphs for learning molecular fingerprints Advances in neural information processing systems. 2224--2232.
[14]
Yue Gao, Meng Wang, Huanbo Luan, Jialie Shen, Shuicheng Yan, and Dacheng Tao. 2011. Tag-based social image search with visual-text joint hypergraph learning Proceedings of the 19th ACM international conference on Multimedia. ACM, 1517--1520.
[15]
Marco Gori, Gabriele Monfardini, and Franco Scarselli. 2005. A new model for learning in graph domains. In Neural Networks, 2005. IJCNN'05. Proceedings. 2005 IEEE International Joint Conference on, Vol. Vol. 2. IEEE, 729--734.
[16]
Mikael Henaff, Joan Bruna, and Yann LeCun. 2015. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163 (2015).
[17]
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation Vol. 9, 8 (1997), 1735--1780.
[18]
Liang Hu, Jian Cao, Guandong Xu, Jie Wang, Zhiping Gu, and Longbing Cao. 2013. Cross-domain collaborative filtering via bilinear multilevel analysis International Joint Conference on Artificial Intelligence. IJCAI/AAAI.
[19]
Justin Johnson, Lamberto Ballan, and Li Fei-Fei. 2015. Love thy neighbors: Image annotation by exploiting image metadata Proceedings of the IEEE international conference on computer vision. 4624--4632.
[20]
Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, and Pierre Vandergheynst. 2014. Matrix completion on graphs. arXiv preprint arXiv:1408.1717 (2014).
[21]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
[22]
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks Advances in neural information processing systems. 1097--1105.
[23]
Jure Leskovec and Julian J Mcauley. 2012. Learning to discover social circles in ego networks Advances in neural information processing systems. 539--547.
[24]
Dong Li, Zhiming Xu, Sheng Li, and Xin Sun. 2013. Link prediction in social networks based on hypergraph Proceedings of the 22nd International Conference on World Wide Web. ACM, 41--42.
[25]
Rui Li, Chi Wang, and Kevin Chen-Chuan Chang. 2014. User profiling in an ego network: co-profiling attributes and relationships Proceedings of the 23rd international conference on World wide web. ACM, 819--830.
[26]
David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. journal of the Association for Information Science and Technology Vol. 58, 7 (2007), 1019--1031.
[27]
Yu-Ru Lin, Jimeng Sun, Paul Castro, Ravi Konuru, Hari Sundaram, and Aisling Kelliher. 2009. Metafac: community discovery via relational hypergraph factorization Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 527--536.
[28]
Dajie Liu, Norbert Blenn, and Piet Van Mieghem. 2012. A social network model exhibiting tunable overlapping community structure. Procedia Computer Science Vol. 9 (2012), 1400--1409.
[29]
Yun-Fu Liu, Jing-Ming Guo, and Lingling An. 2017. Multimedia Classification Using Bipolar Relation Graphs. IEEE Transactions on Multimedia Vol. 19, 8 (2017), 1860--1869.
[30]
Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. 2015. Geodesic convolutional neural networks on riemannian manifolds Proceedings of the IEEE international conference on computer vision workshops. 37--45.
[31]
Julian McAuley and Jure Leskovec. 2012. Image labeling on a network: using social-network metadata for image classification. Computer Vision--ECCV 2012 (2012), 828--841.
[32]
Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and analysis of online social networks Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM, 29--42.
[33]
Federico Monti, Davide Boscaini, and Jonathan Masci. 2017 a. Geometric deep learning on graphs and manifolds using mixture model CNNs Proceedings of Computer Vision and Pattern Recognition, CVPR.
[34]
Federico Monti, Michael Bronstein, and Xavier Bresson. 2017 b. Geometric matrix completion with recurrent multi-graph neural networks Advances in Neural Information Processing Systems. 3700--3710.
[35]
André A Moreira, Demétrius R Paula, Raimundo N Costa Filho, and José S Andrade Jr. 2006. Competitive cluster growth in complex networks. Physical Review E Vol. 73, 6 (2006), 065101.
[36]
Zhenxing Niu, Gang Hua, Xinbo Gao, and Qi Tian. 2014. Semi-supervised relational topic model for weakly annotated image recognition in social media. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 4233--4240.
[37]
Weike Pan, Nathan N Liu, Evan W Xiang, and Qiang Yang. 2011. Transfer learning to predict missing ratings via heterogeneous user feedbacks IJCAI Proceedings-International Joint Conference on Artificial Intelligence, Vol. Vol. 22. 2318.
[38]
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. 2015. Collaborative filtering with graph information: Consistency and scalable methods Advances in neural information processing systems. 2107--2115.
[39]
Erzsébet Ravasz and Albert-László Barabási. 2003. Hierarchical organization in complex networks. Physical Review E Vol. 67, 2 (2003), 026112.
[40]
Stevan Rudinac, Iva Gornishka, and Marcel Worring. 2017. Multimodal Classification of Violent Online Political Extremism Content with Graph Convolutional Networks. In Proceedings of the on Thematic Workshops of ACM Multimedia 2017. ACM, 245--252.
[41]
Yue Shi, Martha Larson, and Alan Hanjalic. 2014. Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges. ACM Computing Surveys (CSUR) Vol. 47, 1 (2014), 3.
[42]
Martin Simonovsky and Nikos Komodakis. 2017. Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs Proceedings of Computer Vision and Pattern Recognition, 2017. CVPR.
[43]
Nathan Srebro, Jason Rennie, and Tommi S Jaakkola. 2005. Maximum-margin matrix factorization. In Advances in neural information processing systems. 1329--1336.
[44]
Liang Sun, Shuiwang Ji, and Jieping Ye. 2008. Hypergraph spectral learning for multi-label classification Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 668--676.
[45]
Xi Wang and Gita Sukthankar. 2013. Link prediction in multi-relational collaboration networks Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. ACM, 1445--1447.
[46]
Xi Wang and Gita Sukthankar. 2014. Link prediction in heterogeneous collaboration networks. In Social network analysis-community detection and evolution. Springer, 165--192.
[47]
Michael M Wolf, Alicia M Klinvex, and Daniel M Dunlavy. 2016. Advantages to modeling relational data using hypergraphs versus graphs High Performance Extreme Computing Conference (HPEC), 2016 IEEE. IEEE, 1--7.
[48]
Zhijun Yin, Manish Gupta, Tim Weninger, and Jiawei Han. 2010. Linkrec: a unified framework for link recommendation with user attributes and graph structure. In Proceedings of the 19th international conference on World wide web. ACM, 1211--1212.
[49]
Yi-Liang Zhao, Qiang Chen, Shuicheng Yan, Tat-Seng Chua, and Daqing Zhang. 2013. Detecting profilable and overlapping communities with user-generated multimedia contents in LBSNs. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM) Vol. 10, 1 (2013), 3.
[50]
Denny Zhou, Jiayuan Huang, and Bernhard Schölkopf. 2007. Learning with hypergraphs: Clustering, classification, and embedding Advances in neural information processing systems. 1601--1608.

Cited By

View all
  • (2025)Adaptive Neural Message Passing for Inductive Learning on HypergraphsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.343448347:1(19-31)Online publication date: Jan-2025
  • (2024)PositionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693671(39529-39555)Online publication date: 21-Jul-2024
  • (2024)A Sensor Placement Approach Using Multi-Objective Hypergraph Particle Swarm Optimization to Improve Effectiveness of Structural Health Monitoring SystemsSensors10.3390/s2405142324:5(1423)Online publication date: 22-Feb-2024
  • Show More Cited By

Index Terms

  1. Exploiting Relational Information in Social Networks using Geometric Deep Learning on Hypergraphs

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ICMR '18: Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval
      June 2018
      550 pages
      ISBN:9781450350464
      DOI:10.1145/3206025
      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 the author(s) 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

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 05 June 2018

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. geometric deep learning
      2. hypergraph
      3. social network

      Qualifiers

      • Research-article

      Funding Sources

      • Horizon 2020

      Conference

      ICMR '18
      Sponsor:

      Acceptance Rates

      ICMR '18 Paper Acceptance Rate 44 of 136 submissions, 32%;
      Overall Acceptance Rate 254 of 830 submissions, 31%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)27
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 19 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)Adaptive Neural Message Passing for Inductive Learning on HypergraphsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.343448347:1(19-31)Online publication date: Jan-2025
      • (2024)PositionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693671(39529-39555)Online publication date: 21-Jul-2024
      • (2024)A Sensor Placement Approach Using Multi-Objective Hypergraph Particle Swarm Optimization to Improve Effectiveness of Structural Health Monitoring SystemsSensors10.3390/s2405142324:5(1423)Online publication date: 22-Feb-2024
      • (2024)Predicting hyperlinks via weighted hypernetwork loop structureThe European Physical Journal Special Topics10.1140/epjs/s11734-024-01145-y233:4(863-877)Online publication date: 14-Mar-2024
      • (2024)Large-Scale Traffic Prediction With Hierarchical Hypergraph Message Passing NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2024.341900811:6(7103-7113)Online publication date: Dec-2024
      • (2024)Metro Flow Prediction With Hierarchical Hypergraph Attention NetworksIEEE Transactions on Artificial Intelligence10.1109/TAI.2023.33370525:6(3012-3021)Online publication date: Jun-2024
      • (2024)Optimal Reactive Power Planning Under Wind Power Uncertainties with Techno-Commercial AssessmentElectric Power Components and Systems10.1080/15325008.2024.2328232(1-24)Online publication date: 20-Mar-2024
      • (2024)Molecular graph transformer: stepping beyond ALIGNN into long-range interactionsDigital Discovery10.1039/D4DD00014E3:5(1048-1057)Online publication date: 2024
      • (2023)A Novel Hypergraph Clustered Gray Relational Analysis HGPSO Algorithm for Data Aggregation in WSNCybernetics and Information Technologies10.2478/cait-2023-003123:3(163-178)Online publication date: 28-Sep-2023
      • (2023)HAT: Hypergraph analysis toolboxPLOS Computational Biology10.1371/journal.pcbi.101119019:6(e1011190)Online publication date: 5-Jun-2023
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media