Advanced search
1 file | 1.07 MB Add to list

CSNE : Conditional Signed Network Embedding

Alexandru Cristian Mara (UGent) , Yoosof Mashayekhi (UGent) , Jefrey Lijffijt (UGent) and Tijl De Bie (UGent)
(2020) arXiv.
Author
Organization
Abstract
Signed networks are mathematical structures that encode positive and negative relations between entities such as friend/foe or trust/distrust. Recently, several papers studied the construction of useful low-dimensional representations (embeddings) of these networks for the prediction of missing relations or signs. Existing embedding methods for sign prediction generally enforce different notions of status or balance theories in their optimization function. These theories, however, are often inaccurate or incomplete, which negatively impacts method performance. In this context, we introduce conditional signed network embedding (CSNE). Our probabilistic approach models structural information about the signs in the network separately from fine-grained detail. Structural information is represented in the form of a prior, while the embedding itself is used for capturing fine-grained information. These components are then integrated in a rigorous manner. CSNE's accuracy depends on the existence of sufficiently powerful structural priors for modelling signed networks, currently unavailable in the literature. Thus, as a second main contribution, which we find to be highly valuable in its own right, we also introduce a novel approach to construct priors based on the Maximum Entropy (MaxEnt) principle. These priors can model the polarity of nodes (degree to which their links are positive) as well as signed triangle counts (a measure of the degree structural balance holds to in a network). Experiments on a variety of real-world networks confirm that CSNE outperforms the state-of-the-art on the task of sign prediction. Moreover, the MaxEnt priors on their own, while less accurate than full CSNE, achieve accuracies competitive with the state-of-the-art at very limited computational cost, thus providing an excellent runtime-accuracy trade-off in resource-constrained situations.
Keywords
Signed Network Embedding, Sign Prediction, MaxEnt Models

Downloads

  • manuscript.pdf
    • full text (Author's original)
    • |
    • open access
    • |
    • PDF
    • |
    • 1.07 MB

Citation

Please use this url to cite or link to this publication:

MLA
Mara, Alexandru Cristian, et al. “CSNE : Conditional Signed Network Embedding.” ArXiv, 2020.
APA
Mara, A. C., Mashayekhi, Y., Lijffijt, J., & De Bie, T. (2020). CSNE : Conditional Signed Network Embedding. arXiv.
Chicago author-date
Mara, Alexandru Cristian, Yoosof Mashayekhi, Jefrey Lijffijt, and Tijl De Bie. 2020. “CSNE : Conditional Signed Network Embedding.” ArXiv.
Chicago author-date (all authors)
Mara, Alexandru Cristian, Yoosof Mashayekhi, Jefrey Lijffijt, and Tijl De Bie. 2020. “CSNE : Conditional Signed Network Embedding.” ArXiv.
Vancouver
1.
Mara AC, Mashayekhi Y, Lijffijt J, De Bie T. CSNE : Conditional Signed Network Embedding. arXiv. 2020.
IEEE
[1]
A. C. Mara, Y. Mashayekhi, J. Lijffijt, and T. De Bie, “CSNE : Conditional Signed Network Embedding,” arXiv. 2020.
@misc{8662685,
  abstract     = {Signed networks are mathematical structures that encode positive and negative relations between entities such as friend/foe or trust/distrust. Recently, several papers studied the construction of useful low-dimensional representations (embeddings) of these networks for the prediction of missing relations or signs. Existing embedding methods for sign prediction generally enforce different notions of status or balance theories in their optimization function. These theories, however, are often inaccurate or incomplete, which negatively impacts method performance. 

In this context, we introduce conditional signed network embedding (CSNE). Our probabilistic approach models structural information about the signs in the network separately from fine-grained detail. Structural information is represented in the form of a prior, while the embedding itself is used for capturing fine-grained information. These components are then integrated in a rigorous manner. CSNE's accuracy depends on the existence of sufficiently powerful structural priors for modelling signed networks, currently unavailable in the literature. Thus, as a second main contribution, which we find to be highly valuable in its own right, we also introduce a novel approach to construct priors based on the Maximum Entropy (MaxEnt) principle. These priors can model the polarity of nodes (degree to which their links are positive) as well as signed triangle counts (a measure of the degree structural balance holds to in a network).

Experiments on a variety of real-world networks confirm that CSNE outperforms the state-of-the-art on the task of sign prediction. Moreover, the MaxEnt priors on their own, while less accurate than full CSNE, achieve accuracies competitive with the state-of-the-art at very limited computational cost, thus providing an excellent runtime-accuracy trade-off in resource-constrained situations.},
  author       = {Mara, Alexandru Cristian and Mashayekhi, Yoosof and Lijffijt, Jefrey and De Bie, Tijl},
  keywords     = {Signed Network Embedding,Sign Prediction,MaxEnt Models},
  language     = {eng},
  pages        = {10},
  series       = {arXiv},
  title        = {CSNE : Conditional Signed Network Embedding},
  url          = {https://arxiv.org/abs/2005.10701},
  year         = {2020},
}