research-article

Learning disentangled representations in signed directed graphs without social assumptions

Authors:

Jinhong JungAuthors Info & Claims

Volume 665, Issue C

https://doi.org/10.1016/j.ins.2024.120373

Published: 02 July 2024 Publication History

Abstract

Signed graphs can represent complex systems of positive and negative relationships such as trust or preference in various domains. Learning node representations is indispensable because they serve as pivotal features for downstream tasks on signed graphs. However, most existing methods often oversimplify the modeling of signed relationships by relying on social theories, while real-world relationships can be influenced by multiple latent factors. This hinders those methods from effectively capturing the diverse factors, thereby limiting the expressiveness of node representations.

In this paper, we propose DINES, a novel method for learning disentangled node representations in signed directed graphs without social assumptions. We adopt a disentangled framework that separates each embedding into distinct factors, allowing for capturing multiple latent factors, and uses signed directed graph convolutions that focus solely on sign and direction, without depending on social theories. Additionally, we propose a new decoder that effectively classifies an edge's sign by considering correlations between the factors. To further enhance disentanglement, we jointly train a self-supervised factor discriminator with our encoder and decoder. Throughout extensive experiments on real-world signed directed graphs, we show that DINES effectively learns disentangled node representations, and significantly outperforms its competitors in predicting link signs.

References

[1]

A.P. Bradley, The use of the area under the ROC curve in the evaluation of machine learning algorithms, Pattern Recognit. 30 (7) (1997) 1145–1159,.

Digital Library

[2]

D. Cartwright, F. Harary, Structural balance: a generalization of Heider's theory, Psychol. Rev. 63 (5) (1956) 277,.

[3]

Y. Chen, T. Qian, H. Liu, K. Sun, “Bridge”: enhanced signed directed network embedding, in: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, ACM, 2018, pp. 773–782,.

Digital Library

[4]

J.A. Davis, Clustering and structural balance in graphs, Hum. Relat. 20 (2) (1967) 181–187,.

[5]

T. Derr, Y. Ma, J. Tang, Signed graph convolutional networks, in: IEEE International Conference on Data Mining, ICDM, 2018, Singapore, November 17–20, 2018, IEEE Computer Society, 2018, pp. 929–934,.

[6]

G.L. Falher, Characterizing Edges in Signed and Vector-Valued Graphs (Caractérisation des arêtes dans les graphes signés et attribués), Ph.D. thesis Lille University of Science and Technology, France, 2018, https://tel.archives-ouvertes.fr/tel-01824215.

[7]

Fiorini, S.; Coniglio, S.; Ciavotta, M.; Messina, E. : SigMaNet: one Laplacian to rule them all. CoRR arXiv:2205.13459 [abs] : SigMaNet: one Laplacian to rule them all. https://doi.org/10.48550/arXiv.2205.13459.

[8]

R.V. Guha, R. Kumar, P. Raghavan, A. Tomkins, Propagation of trust and distrust, in: Proceedings of the 13th International Conference on World Wide Web, WWW 2004, New York, NY, USA, May 17-20, 2004, ACM, 2004, pp. 403–412,.

Digital Library

[9]

W.L. Hamilton, Z. Ying, J. Leskovec, Inductive representation learning on large graphs, in: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017, pp. 1024–1034. https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html.

[10]

J. Huang, H. Shen, L. Hou, X. Cheng, SDGNN: learning node representation for signed directed networks, Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021 in: The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, AAAI Press, 2021, pp. 196–203. https://ojs.aaai.org/index.php/AAAI/article/view/16093.

[11]

J. Jung, W. Jin, U. Kang, Random walk-based ranking in signed social networks: model and algorithms, Knowl. Inf. Syst. 62 (2) (2020) 571–610,.

Digital Library

[12]

J. Jung, W. Jin, L. Sael, U. Kang, Personalized ranking in signed networks using signed random walk with restart, in: IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, IEEE Computer Society, 2016, pp. 973–978,.

[13]

J. Jung, H. Park, U. Kang, BalanSiNG: fast and scalable generation of realistic signed networks, in: Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020, Copenhagen, Denmark, March 30 - April 02, 2020, OpenProceedings.org, 2020, pp. 193–204,.

[14]

Jung, J.; Yoo, J.; Kang, U. : Signed graph diffusion network. CoRR arXiv:2012.14191 [abs].

[15]

J. Jung, J. Yoo, U. Kang, Signed random walk diffusion for effective representation learning in signed graphs, PLoS ONE 17 (3) (2022) 1–19,.

[16]

J. Kim, H.J. Jeong, S. Lim, J. Kim, Effective and efficient core computation in signed networks, Inf. Sci. 634 (2023) 290–307,.

Digital Library

[17]

J. Kim, H. Park, J. Lee, U. Kang, SIDE: representation learning in signed directed networks, in: Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, ACM, 2018, pp. 509–518,.

Digital Library

[18]

T.N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, in: 5th International Conference on Learning Representations, Conference Track Proceedings, ICLR 2017, Toulon, France, April 24-26, 2017, OpenReview.net, 2017, https://openreview.net/forum?id=SJU4ayYgl.

[19]

J. Klicpera, A. Bojchevski, S. Günnemann, Predict then propagate: graph neural networks meet personalized PageRank, in: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019, https://openreview.net/forum?id=H1gL-2A9Ym.

[20]

T. Ko, Y. Choi, C.-K. Kim, A spectral graph convolution for signed directed graphs via magnetic Laplacian, Neural Netw. (2023) 562–574,.

Digital Library

[21]

T. Ko, Y. Choi, C.-K. Kim, Universal graph contrastive learning with a novel Laplacian perturbation, in: Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, vol. 216, 2023, pp. 1098–1108. https://proceedings.mlr.press/v216/ko23a.html.

[22]

S. Kumar, F. Spezzano, V.S. Subrahmanian, Accurately detecting trolls in Slashdot Zoo via decluttering, in: 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014, Beijing, China, August 17-20, 2014, IEEE Computer Society, 2014, pp. 188–195,.

[23]

S. Kumar, F. Spezzano, V.S. Subrahmanian, C. Faloutsos, Edge weight prediction in weighted signed networks, in: IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, IEEE Computer Society, 2016, pp. 221–230,.

[24]

J. Kunegis, A. Lommatzsch, C. Bauckhage, The Slashdot Zoo: mining a social network with negative edges, in: Proceedings of the 18th International Conference on World Wide Web, WWW 2009, April 20-24, 2009, Madrid, Spain, ACM, 2009, pp. 741–750,.

Digital Library

[25]

Y. Lee, N. Seo, K. Han, S. Kim, ASiNE: adversarial signed network embedding, in: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, ACM, 2020, pp. 609–618,.

Digital Library

[26]

J. Leskovec, D.P. Huttenlocher, J.M. Kleinberg, Predicting positive and negative links in online social networks, in: Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, ACM, 2010, pp. 641–650,.

Digital Library

[27]

J. Leskovec, D.P. Huttenlocher, J.M. Kleinberg, Predicting positive and negative links in online social networks, in: Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, ACM, 2010, pp. 641–650,.

Digital Library

[28]

J. Leskovec, D.P. Huttenlocher, J.M. Kleinberg, Signed networks in social media, in: Proceedings of the 28th International Conference on Human Factors in Computing Systems, CHI 2010, Atlanta, Georgia, USA, April 10-15, 2010, ACM, 2010, pp. 1361–1370,.

Digital Library

[29]

Y. Li, Y. Tian, J. Zhang, Y. Chang, Learning signed network embedding via graph attention, The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020 in: The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, February 7-12, 2020, New York, NY, USA, AAAI Press, 2020, pp. 4772–4779. https://ojs.aaai.org/index.php/AAAI/article/view/5911.

[30]

H. Liu, Z. Zhang, P. Cui, Y. Zhang, Q. Cui, J. Liu, W. Zhu, Signed graph neural network with latent groups, in: KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, ACM, 2021, pp. 1066–1075,.

Digital Library

[31]

Y. Liu, X. Wang, S. Wu, Z. Xiao, Independence promoted graph disentangled networks, The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020 in: The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, February 7-12, 2020, New York, NY, USA, AAAI Press, 2020, pp. 4916–4923. https://ojs.aaai.org/index.php/AAAI/article/view/5929.

[32]

J. Ma, P. Cui, K. Kuang, X. Wang, W. Zhu, Disentangled graph convolutional networks, in: Proceedings of the 36th International Conference on Machine Learning, in: Proceedings of Machine Learning Research, PMLR, vol. 97, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019, pp. 4212–4221. http://proceedings.mlr.press/v97/ma19a.html.

[33]

F. Meng, M. Medo, B. Buechel, Whom to trust in a signed network? Optimal solution and two heuristic rules, Inf. Sci. 606 (2022) 742–762,.

Digital Library

[34]

L. Shu, E. Du, Y. Chang, C. Chen, Z. Zheng, X. Xing, S. Shen, SGCL: contrastive representation learning for signed graphs, in: CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021, ACM, 2021, pp. 1671–1680,.

Digital Library

[35]

D. Song, D.A. Meyer, D. Tao, Efficient latent link recommendation in signed networks, in: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, ACM, 2015, pp. 1105–1114,.

Digital Library

[36]

A.A. Taha, A. Hanbury, Metrics for evaluating 3D medical image segmentation: analysis, selection, and tool, BMC Med. Imaging 15 (2015) 29,.

[37]

J. Tang, C.C. Aggarwal, H. Liu, Node classification in signed social networks, in: Proceedings of the 2016 SIAM International Conference on Data Mining, Miami, Florida, USA, May 5-7, 2016, SIAM, 2016, pp. 54–62,.

[38]

R. Tzeng, B. Ordozgoiti, A. Gionis, Discovering conflicting groups in signed networks, in: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020, https://proceedings.neurips.cc/paper/2020/hash/7cc538b1337957dae283c30ad46def38-Abstract.html.

[39]

S. Wang, J. Tang, C.C. Aggarwal, Y. Chang, H. Liu, Signed network embedding in social media, in: Proceedings of the 2017 SIAM International Conference on Data Mining, Houston, Texas, USA, April 27-29, 2017, SIAM, 2017, pp. 327–335,.

[40]

X. Wang, H. Jin, A. Zhang, X. He, T. Xu, T. Chua, Disentangled graph collaborative filtering, in: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, ACM, 2020, pp. 1001–1010,.

Digital Library

[41]

R. West, H.S. Paskov, J. Leskovec, C. Potts, Exploiting social network structure for person-to-person sentiment analysis, Trans. Assoc. Comput. Linguist. 2 (2014) 297–310,.

[42]

Y. Wu, Q. Yao, X. Fan, M. Gong, W. Ma, Q. Miao, PANet: a point-attention based multi-scale feature fusion network for point cloud registration, IEEE Trans. Instrum. Meas. 72 (2023) 1–13,.

[43]

K. Xu, W. Hu, J. Leskovec, S. Jegelka, How powerful are graph neural networks?, in: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019, https://openreview.net/forum?id=ryGs6iA5Km.

[44]

P. Xu, W. Hu, J. Wu, B. Du Link, Prediction with signed latent factors in signed social networks, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, ACM, 2019, pp. 1046–1054,.

Digital Library

[45]

P. Xu, Y. Zhan, L. Liu, B. Yu, B. Du, J. Wu, W. Hu, Dual-branch density ratio estimation for signed network embedding, in: WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, ACM, 2022, pp. 1651–1662,.

Digital Library

[46]

D. Yan, Y. Zhang, W. Xie, Y. Jin, Y. Zhang, MUSE: multi-faceted attention for signed network embedding, Neurocomputing 519 (2023) 36–43,.

Digital Library

[47]

S. Yuan, X. Wu, Y. Xiang, SNE: signed network embedding, in: Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, Proceedings, Part II, in: Lecture Notes in Computer Science, vol. 10235, PAKDD 2017, Jeju, South Korea, May 23-26, 2017, 2017, pp. 183–195,.

[48]

T. Zhao, X. Zhang, S. Wang, Exploring edge disentanglement for node classification, in: WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, ACM, 2022, pp. 1028–1036,.

Digital Library

[49]

L. Zhuang, H. Wang, J. Zhao, Y. Sun, Adaptive dual graph contrastive learning based on heterogeneous signed network for predicting adverse drug reaction, Inf. Sci. 642 (2023),.

Digital Library

Cited By

Lee SKo GSong HJung JSerra ESpezzano F(2024)MuLe: Multi-Grained Graph Learning for Multi-Behavior RecommendationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679709(1163-1173)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679709

Recommendations

A spectral graph convolution for signed directed graphs via magnetic Laplacian
Abstract
Signed directed graphs contain both sign and direction information on their edges, providing richer information about real-world phenomena compared to unsigned or undirected graphs. However, analyzing such graphs is more challenging due to their ...
Highlights
- This paper introduces a novel complex Hermitian adjacency matrix that encodes signed directed graphs using complex numbers.
- It proposes a magnetic Laplacian matrix via the Hermitian and proves its positive semi-definite property.
- ...
Learning Pair-Centric Representation for Link Sign Prediction with Subgraph
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge Management

Signed graphs are prevalent data structures containing both positive and negative links. Recently, the fundamental network analysis task on signed graphs, namely link sign prediction, has received careful attention. Existing methods learn two target node ...
Contrastive Learning for Signed Bipartite Graphs
SIGIR '23: Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval

This paper is the first to use contrastive learning to improve the robustness of graph representation learning for signed bipartite graphs, which are commonly found in social networks, recommender systems, and paper review platforms. Existing contrastive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 665, Issue C

Apr 2024

870 pages

Issue’s Table of Contents

Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 02 July 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee SKo GSong HJung JSerra ESpezzano F(2024)MuLe: Multi-Grained Graph Learning for Multi-Behavior RecommendationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679709(1163-1173)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679709

View Options

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents