PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Deep Embedding for Hyper-Networks

Ke Tu, Peng Cui, Xiao Wang, Fei Wang, Wenwu Zhu

arXiv:1711.10146v2cs.SI

TL;DR

Pairwise embedding methods do not adequately handle heterogeneous hyper-networks with indecomposable hyperedges, where subsets need not retain the original relationship. DHNE uses a nonlinear tuplewise similarity function with a deep autoencoder to preserve local and global structure, and experiments across four hyper-network types show significant, consistent outperformance of state-of-the-art methods.

  • Problem

    Existing network embedding methods focus on pairwise relationships and do not preserve indecomposable high-order relationships in heterogeneous hyper-networks.

  • Method

    DHNE uses a deep model with nonlinear tuplewise similarity and a deep autoencoder to preserve indecomposable relationships plus local and global structural information.

  • Results

    Experiments on four real-world information networks show that DHNE significantly and consistently outperforms state-of-the-art algorithms.

  • Takeaways & Limitations

    Preserving indecomposable hyperedges together with local and global structure yields embeddings with stronger reconstruction and link-prediction performance than decomposable or pairwise baselines.

  • Takeaways & Limitations

    The model mainly focuses on hyperedges with uniform length N = 3, though it can be extended to N > 3.

Abstract

from arXiv · show

Network embedding has recently attracted lots of attentions in data mining. Existing network embedding methods mainly focus on networks with pairwise relationships. In real world, however, the relationships among data points could go beyond pairwise, i.e., three or more objects are involved in each relationship represented by a hyperedge, thus forming hyper-networks. These hyper-networks pose great challenges to existing network embedding methods when the hyperedges are indecomposable, that is to say, any subset of nodes in a hyperedge cannot form another hyperedge. These indecomposable hyperedges are especially common in heterogeneous networks. In this paper, we propose a novel Deep Hyper-Network Embedding (DHNE) model to embed hyper-networks with indecomposable hyperedges. More specifically, we theoretically prove that any linear similarity metric in embedding space commonly used in existing methods cannot maintain the indecomposibility property in hyper-networks, and thus propose a new deep model to realize a non-linear tuplewise similarity function while preserving both local and global proximities in the formed embedding space. We conduct extensive experiments on four different types of hyper-networks, including a GPS network, an online social network, a drug network and a semantic network. The empirical results demonstrate that our method can significantly and consistently outperform the state-of-the-art algorithms.

Introduction

Existing network embedding methods are built for pairwise relationships, whereas heterogeneous hyper-networks contain indecomposable high-order relationships and require both local and global structure preservation. DHNE addresses these issues with a nonlinear tuplewise similarity model and a deep autoencoder, jointly optimized for embedding.

  • Pairwise network embedding methods do not directly represent relationships involving three or more objects in hyper-networks.
  • Indecomposable hyperedges cannot be safely decomposed because strong relationships among all nodes do not imply strong relationships among their subsets.For example, user–movie–tag relationships do not generally imply user–tag relationships.
  • Hyper-network embedding must preserve global neighborhood structure in addition to observed local relationships because real-world networks are sparse.
  • DHNE models each hyperedge as a whole with a nonlinear tuplewise similarity function and uses a deep autoencoder to reconstruct neighborhood structures.
  • The tuplewise similarity function and deep autoencoder are jointly optimized to preserve indecomposable relationships alongside local and global structural information.

Related work

Prior network embedding methods largely assume pairwise relationships, while hypergraph methods mainly address homogeneous structures and cannot preserve indecomposable heterogeneous hyperedges. DHNE extends embedding to this setting with explicit nonlinear tuplewise modeling and structural preservation.

  • Earlier embedding methods use matrix factorization, random walks, proximity objectives, or community structure, but assume pairwise relationships.
  • Hypergraph methods generalize spectral clustering for homogeneous hypergraphs but preserve hyperedges implicitly through latent similarity.
  • Because they do not explicitly preserve indecomposable hyperedges, existing homogeneous hypergraph methods are unsuitable for heterogeneous hyper-networks.

Notations and Definitions

The paper defines hyper-networks as typed hypergraphs whose hyperedges may contain more than two nodes, then formalizes first-order tuplewise and second-order neighborhood-based proximity. These definitions distinguish indecomposable relationships from global structural similarity.

  • A hyper-network is a typed hypergraph G = (V, E) whose hyperedges may contain two or more nodes; it is heterogeneous when multiple node types exist.
  • First-order proximity assigns N-tuplewise similarity when N nodes form a hyperedge, without implying proximity for any subset.
  • Second-order proximity measures similarity between nodes through similarity of their neighborhood structures.For a node vi in hyperedge Ei, the neighborhood is represented by Ei/vi.
  • In the example, A1 and A2 have second-order similarity because their neighborhood sets share (L1, U2).

Deep Hyper-Network Embedding

DHNE combines a nonlinear tuplewise similarity model with type-specific autoencoders to preserve hyperedge relationships and neighborhood structure in heterogeneous hyper-networks.

  • Indecomposable similarity: DHNE uses a multilayer perceptron because linear tuplewise similarity cannot satisfy the indecomposability property.The model concatenates node embeddings, maps them nonlinearly into a latent space, and produces tuplewise similarity.
  • Indecomposable similarity: The tuplewise objective makes similarity large for observed hyperedges and small otherwise, preserving first-order proximity.R_ijk equals 1 for an existing three-node hyperedge and 0 otherwise.
  • Structure preservation: An adjacency-matrix autoencoder preserves second-order proximity by learning similar representations for nodes with similar neighborhood structures.The hypergraph adjacency matrix is constructed from the incidence matrix, and only non-zero entries are reconstructed to accelerate training.
  • Structure preservation: Each heterogeneous node type receives its own autoencoder, allowing the model to learn type-specific latent spaces.The type-specific autoencoders are combined with the tuplewise similarity objective.
  • Optimization: DHNE is optimized with stochastic gradient descent, backpropagation, and sampled negative hyperedges to avoid trivial similarity solutions.Negative hyperedges are sampled because networks typically contain mostly positive relationships.
  • Scalability and extension: The training complexity is linear in the number of vertices, and a new vertex can be embedded from its adjacency vector using its type-specific autoencoder.Out-of-sample embedding has complexity O(d_vd).

Experiment

The experiments evaluate DHNE across four real-world hyper-network datasets spanning GPS, social, medicine, and semantic domains.

  • Datasets: DHNE is evaluated on four dataset types: GPS, social, medicine, and semantic hyper-networks.The datasets include GPS, MovieLens, drug2, and wordnet.
  • Datasets: GPS hyperedges represent user, location, and activity relations.
  • Datasets: MovieLens hyperedges represent user, movie, and tag relations from personal tagging activity.
  • Datasets: drug2 hyperedges represent user, drug, and reaction relationships associated with adverse events.
  • Datasets: wordnet hyperedges represent head entity, relation type, and tail entity triplets from WordNet 3.0.

Parameter Settings

DHNE is compared with six established embedding methods under a common representation size, with pairwise baselines adapted through clique expansion or pairwise similarity aggregation.

  • Compared Methods: DHNE is compared with DeepWalk, LINE, node2vec, SHE, Tensor decomposition, and HEBE.
  • Compared Methods: DeepWalk, LINE, and node2vec use clique expansion to transform hyper-networks into conventional pairwise networks.
  • Compared Methods: DeepWalk, LINE, node2vec, and SHE measure pairwise relationships and use mean or minimum pairwise similarity for candidate hyperedges.
  • Hyperparameters: All methods use representation size 64, while DeepWalk and node2vec use window size 10, walk length 40, and 10 walks per vertex.

Network Reconstruction

Network reconstruction evaluates whether learned embeddings preserve the original hyper-network structure, using AUC to predict links.

  • Evaluation: AUC is used to evaluate network reconstruction by predicting links from learned embeddings.
  • Results: DHNE achieves significant AUC improvements over baselines on all four datasets.
  • Results: DHNE improves more over baselines on sparse drug and wordnet datasets than on GPS and MovieLens.
  • Results: DHNE outperforms DeepWalk, LINE, and SHE, which assume high-order relationships are decomposable.

Link Prediction

Link prediction tests DHNE on held-out hyper-network links and under varying sparsity, with additional figure-based evaluations covering GPS, MovieLens, and wordnet.

  • Evaluation: Two link-prediction tasks evaluate overall performance and performance across different network sparsity levels.
  • Overall Link Prediction: For the overall task, 20% of existing edges are hidden for training, and AUC measures prediction performance.
  • Figures: Figure 3 presents a GPS ROC curve and link-prediction performance across networks with different sparsity.
  • Overall Link Prediction: DHNE achieves significant improvements over baselines on all datasets, indicating strong predictive power for unseen links.
  • Overall Link Prediction: Transforming indecomposable high-order relationships into multiple pairwise relationships damages the predictive power of learned embeddings.
  • Sparsity Robustness: DHNE significantly improves over the best baselines across all tested sparsity levels on the drug dataset.The retained-edge ratio ranges from 10% to 90%.

Classification

On MovieLens and wordnet classification tasks, DHNE consistently outperforms the baselines, including when labeled data is sparse. Its relative advantage becomes more apparent as labeled data increases.

  • Classification: DHNE performs consistently better than baselines on both Micro-F1 and Macro-F1 classification curves.The evaluation covers multi-label classification on MovieLens and multi-class classification on wordnet.
  • Classification: DHNE still outperforms the baselines when labeled data is quite sparse.This indicates robustness under limited supervision.
  • Classification: As labeled data becomes richer, DHNE’s relative improvement over the baselines becomes more obvious.

Parameter Sensitivity

The experiments examine how the proximity-loss trade-off and embedding dimension affect link-prediction performance and training time. Both first- and second-order proximities contribute, while training time scales linearly with node count.

  • Parameter Sensitivity: Embedding dimension initially improves link-prediction performance in the drug dataset.The supplied passage reports that performance raises firstly as dimension changes.
  • Parameter Sensitivity: Both first-order and second-order proximities are necessary for hyper-network embedding.Values of α between 0.1 and 2 outperform α = 0, while also outperforming α = 5.
  • Parameter Sensitivity: Training time per batch scales linearly with the number of nodes.This agrees with the model’s complexity analysis and indicates scalability.

Conclusion

DHNE addresses hyper-networks with indecomposable hyperedges by learning low-dimensional representations through a deep model. It realizes nonlinear tuplewise similarity while preserving local and global proximities.

  • Conclusion: DHNE learns low-dimensional representations for hyper-networks with indecomposable hyperedges.The model is designed for this hyper-network embedding setting.
  • Conclusion: The model realizes a nonlinear tuplewise similarity function while preserving both local and global proximities.This follows the theoretical limitation of linear similarity metrics for indecomposable hyper-networks.
Loading 1711.10146v2…