PaperlayerView exact revision on arXiv

Source-linked AI summary

Bipartite Graph Embedding via Mutual Information Maximization

Jiangxia Cao, Xixun Lin, Shu Guo, Luchen Liu, Tingwen Liu, Bin Wang

arXiv:2012.05442v1cs.SIcs.AI

TL;DR

Existing bipartite graph embedding methods often emphasize local structure, leaving global communities and long-range dependencies less well preserved. BiGI uses prototype-based global representations, subgraph-attention edge representations, and a local-global mutual-information objective. The paper reports consistent improvements over state-of-the-art baselines across datasets and tasks.

  • Problem

    Existing random-walk and reconstruction-based methods learn local structure, while global communities among homogeneous nodes and long-range dependencies among heterogeneous nodes are not well preserved.

    Source: §1 · p. 2

  • Method

    BiGI maximizes mutual information between subgraph-attention representations of sampled edges and a global representation composed of two node-type prototypes.

    Source: §1 · p. 2, §4.2.2 · p. 4

  • Results

    BiGI consistently outperforms state-of-the-art baselines across datasets and tasks, including top-K recommendation and link prediction.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    The experiments support modeling bipartite graph global properties as an effective approach across the evaluated datasets and tasks.

    Source: §1 · p. 2, §6 · p. 8

    BiNE results for ML-10M are unavailable because node-sequence generation did not finish within 72 hours.

    Source: §5.2.3 · p. 7

Abstract

from arXiv · show

Bipartite graph embedding has recently attracted much attention due to the fact that bipartite graphs are widely used in various application domains. Most previous methods, which adopt random walk-based or reconstruction-based objectives, are typically effective to learn local graph structures. However, the global properties of bipartite graph, including community structures of homogeneous nodes and long-range dependencies of heterogeneous nodes, are not well preserved. In this paper, we propose a bipartite graph embedding called BiGI to capture such global properties by introducing a novel local-global infomax objective. Specifically, BiGI first generates a global representation which is composed of two prototype representations. BiGI then encodes sampled edges as local representations via the proposed subgraph-level attention mechanism. Through maximizing the mutual information between local and global representations, BiGI enables nodes in bipartite graph to be globally relevant. Our model is evaluated on various benchmark datasets for the tasks of top-K recommendation and link prediction. Extensive experiments demonstrate that BiGI achieves consistent and significant improvements over state-of-the-art baselines. Detailed analyses verify the high effectiveness of modeling the global properties of bipartite graph.

1 INTRODUCTION

Bipartite graphs connect two node types, but existing embedding methods largely learn local structure rather than global communities and long-range dependencies. BiGI combines prototype-based global representations, edge-based local representations, and mutual-information maximization; experiments report improvements over state-of-the-art baselines.

1 INTRODUCTION

  • Bipartite graphs model relationships between two node types, with no direct links between nodes of the same type.Source: §1 · p. 1
  • Prior random-walk and reconstruction-based methods focus mainly on local structures, leaving global properties of bipartite graphs difficult to learn.Examples include communities among similar-genre movies that are unreachable in the graph and long-range user–movie dependencies.Source: §1 · p. 2
  • BiGI combines two prototype representations with subgraph-attention edge representations in a local-global infomax objective to capture bipartite graph properties.The objective maximizes mutual information between local and global representations.Source: §1 · p. 2
  • Across multiple benchmark datasets, BiGI yields consistent and significant improvements over state-of-the-art baselines for top-K recommendation and link prediction.Source: §1 · p. 2

2 RELATED WORK

Prior bipartite embedding and collaborative-filtering approaches primarily model local structure. Earlier mutual-information methods address homogeneous or other graph settings, while this work combines both node types in local and global representations for bipartite graphs.

2.1 Bipartite Graph Embedding

  • Bipartite-specific embedding methods mainly model local graph structure, while homogeneous and heterogeneous methods are not tailored to preserve bipartite structural characteristics.Source: §2.1 · p. 2
  • GC-MC exploits direct user-item links, and NGCF aggregates neighborhood features, but NGCF still overlooks global bipartite graph properties.Source: §2.1 · p. 2

2.2 Mutual Information Maximization

  • DGI applies infomax to homogeneous graphs, InfoGraph relates graph-level and substructure representations, and DMGI extends DGI to heterogeneous graphs while emphasizing homogeneous-node correlations.Source: §2.2 · p. 2
  • Unlike prior infomax approaches that measure information in homogeneous graphs, this work combines both node types in local and global representations for bipartite graphs.Source: §2.2 · p. 3

3 BACKGROUND

The background defines a bipartite graph through two disjoint node sets and their cross-set edges, then specifies its adjacency matrix and embedding goal.

3 BACKGROUND

  • A bipartite graph G=(U,V,E) has two disjoint node sets and edges only across sets; its binary adjacency matrix records interactions, and embedding maps each node to a d-dimensional vector.Source: §3 · p. 3

4 PROPOSED MODEL

The proposed model, BiGI, uses mutual-information maximization to construct node representations and local-global representations.

4 PROPOSED MODEL

  • BiGI starts with a bipartite graph encoder for initial node representations, then constructs global and local representations and a local-global infomax objective.The section also introduces model analysis.Source: §4 · p. 3

4.1 Bipartite Graph Encoder

The bipartite encoder updates nodes using two-hop neighborhoods, since directly aggregating one-hop neighbors of a different node type is ill-posed. It first forms temporary neighborhood representations, then applies homogeneous graph convolution.

4.1 Bipartite Graph Encoder

  • Because adjacent nodes in a bipartite graph have different types, directly updating a node from its one-hop neighbors is ill-posed.The encoder instead learns each node embedding from its two-hop neighbors in each layer.Source: §4.1 · p. 3
  • A mean operation with a nonlinear transformation forms temporary neighborhood representations from one-hop neighbors.For the example in the passage, the aggregation uses LeakyReLU and a weight matrix.Source: §4.1 · p. 3
  • The encoder then uses homogeneous graph convolution to update node representations from the temporary neighborhood representations.The described update concatenates representations; dropout is applied to each encoder layer.Source: §4.1 · p. 3

4.2 Local-Global Infomax

BiGI builds a global representation from two node-type prototypes and represents sampled edges together with their enclosing subgraphs. It maximizes mutual information between local and global representations to model global bipartite-graph properties.

4.2 Local-Global Infomax

  • BiGI maximizes mutual information between local and global representations to capture global properties of bipartite graphs.The objective uses a binary cross-entropy loss as an MI estimator based on Jensen–Shannon divergence between the joint distribution and product of marginals.Source: §4.2 · p. 3, §4.2.3 · p. 4

4.2.1 Global Representation.

  • The global representation combines two prototypes, each formed by averaging the information of nodes of one type.The composition function concatenates the two prototypes and applies a sigmoid activation.Source: §4.2.1 · pp. 3–4

4.2.2 Local Representation.

  • Each local representation takes a bipartite edge and its h-hop enclosing subgraph as the surrounding context.The enclosing subgraph is the union of the endpoint neighborhoods, with h set to an odd number; subgraph-level attention highlights the central edge and adaptively weights neighboring nodes.Source: §4.2.2 · p. 4

4.2.3 Infomax Objective.

  • BiGI corrupts adjacency entries to form negative samples for its noise-contrastive objective.A switch variable determines whether an adjacency entry is corrupted; β denotes the corruption rate.Source: §4.2.3 · p. 4
  • The two prototypes remain separate, giving each node access to both homogeneous and heterogeneous prototype information, even when correlated nodes are distant.The paper presents this as a way to move beyond local graph topology and capture global properties.Source: §4.2.3 · p. 5

4.3 Model Training

BiGI’s training objective includes a margin-based ranking loss over observed edges, using negative node pairs formed by replacing either endpoint with a random node of the same type. The model is optimized end to end with Adam.

4.3 Model Training

  • The margin-based ranking loss trains the encoder on observed edges against negative node pairs.Each negative pair replaces the head or tail with a random node from the same node set; Adam optimizes BiGI end to end.Source: §4.3 · p. 5

4.4 Model Analysis

The model analysis gives BiGI’s computational complexity and contrasts its design with DGI. It also identifies Table 1 as a summary of dataset statistics.

4.4.1 Time Complexity.

  • BiGI’s computational complexity is approximated as O(k(|E| + |eE|)d^2), where k is the encoder layer count and d the embedding size.The analysis also says an experimental comparison is provided to assess deployment on large-scale bipartite graphs.Source: §4.4.1 · p. 5

4.4.2 Relation with DGI.

  • Unlike DGI’s homogeneous node embeddings and node-level MI objective, BiGI models bipartite graphs with subgraph-level and graph-level representations.BiGI’s subgraph-level representations are described as preserving rich interactions of sampled edges, and its encoder is designed for bipartite structure.Source: §4.4.2 · p. 5

4.4 Model Analysis

  • Table 1 reports statistics for the datasets.The passage identifies the table as dataset statistics but supplies no individual values.Source: Table 1 · p. 5

5 EXPERIMENTS

The experiments evaluate BiGI on four benchmark datasets across top-K recommendation and link prediction, using established splits, metrics, and baselines. Implementation settings are held consistent, although BiNE’s ML-10M result could not be reproduced within 72 hours.

5.1 Datasets

  • Four datasets cover top-K recommendation on DBLP, ML-100K, and ML-10M, and link prediction on Wikipedia.Wikipedia is split into Wiki (5:5) and Wiki (4:6); interaction matrices are converted to implicit data.Source: §5.1 · p. 5, §5.1.1 · p. 5

5.2 Experimental Setting

  • Recommendation is measured with F1, NDCG, MAP, and MRR; link prediction uses AUC-ROC and AUC-PR.Recommendation ranks items not interacted with during training.Source: §5.2.1 · p. 5

5.2.2 Compared Baselines.

  • Baselines span homogeneous and heterogeneous graph embedding, bipartite embedding, matrix completion, and collaborative filtering.The listed methods include DeepWalk, VGAE, Metapath2vec, DMGI, PinSage, BiNE, GC-MC, IGMC, NeuMF, and NGCF.Source: §5.2.2 · pp. 5, 7

5.2.3 Implementation Details.

  • Experiments fix embedding size at 128, learning rate at 0.001, and training at 100 epochs; BiGI uses 1-hop subgraphs and a 2-layer encoder.The corruption rate β and harmonic factor λ are selected from specified ranges; side information is excluded.Source: §5.2.3 · p. 7
  • BiNE’s ML-10M result is omitted because its node sequences were not generated within 72 hours, making its concrete results hard to reproduce.The study uses paired t-tests to assess statistical significance for each dataset.Source: §5.2.3 · p. 7

5.3 Top-K Recommendation

BiGI outperforms baselines on top-K recommendation and link prediction, with analyses reporting stronger clustering and more robust predictions for distant node pairs. The variants and sensitivity studies also examine its encoder, local representations, and hyperparameters.

5.3 Top-K Recommendation

  • BiGI achieves the best performance across all metrics on DBLP, ML-100K, and ML-10M top-K recommendation.The authors report that homogeneous and heterogeneous graph embeddings are inferior, and that DMGI’s weaker results indicate the importance of a bipartite-suitable infomax objective.Source: §5.3 · p. 7

5.4 Link Prediction

  • BiGI achieves higher predictive results than the compared models on both link-prediction datasets.A logistic-regression classifier receives the embeddings for each node pair and is trained on observed edges.Source: §5.4 · pp. 7–8

5.7 Analysis of the Global Properties

  • BiGI achieves the best clustering results across varying cluster counts, supporting stronger modeling of user and item community structure.The study clusters ML-100K representations with K-Means and evaluates them using the Calinski-Harabasz Index.Source: Figure 5 · p. 8, §5.7 · p. 8

5.5 Discussions of Model Variants

  • The proposed encoder is competitive, subgraph-level attention is a suitable local representation, and the infomax objective also improves results with VGAE, NGCF, and PinSage encoders.The variants compare node, pair, and subgraph representations, including a mean-pooled subgraph without attention.Source: §5.5 · p. 8

5.6 Parameter Sensitivity

  • β=1e-5 and λ=0.3 give the best result, and BiGI remains better than other baselines even under the worst tested settings.The sensitivity analysis varies the corruption rate β and harmonic factor λ on DBLP.Source: §5.6 · p. 8

5.7 Analysis of the Global Properties

  • For node pairs at distances 3, 5, and 7, BiGI maintains promising prediction scores as distance increases and observable relations weaken.At distance 3, BiGI and the baselines can learn latent interactions; the comparison uses 15 randomly selected DBLP test pairs.Source: Figure 6 · p. 8, §5.7 · p. 8

6 CONCLUSION

BiGI combines bipartite graph encoding, prototype-based global representations, and attention-based local representations in a mutual-information objective. Experiments show consistent outperformance of state-of-the-art baselines across datasets and tasks.

6 CONCLUSION

  • BiGI is a bipartite graph embedding that maximizes mutual information between local and global representations to recognize global graph properties.The paper reports consistent outperformance of state-of-the-art baselines across datasets and tasks.Source: §6 · p. 8
  • Two prototype representations aggregate information from different homogeneous node types to construct the global representation.Initial node representations are learned with a bipartite graph encoder.Source: §6 · p. 8
  • A subgraph-level attention mechanism incorporates structural priors into local representations before local-global mutual-information maximization.Source: §6 · p. 8

Related papers

Loading 2012.05442v1…