Unsupervised Joint k-node Graph Representations with Compositional Energy-Based Models

Leonardo Cotta, Carlos H. C. Teixeira, Ananthram Swami, Bruno Ribeiro

Abstract

Standard Graph Neural Networks (GNNs) primarily focus on dyadic relationships, often failing to capture higher-order dependencies among groups of $k$ nodes ($k > 2$). We present MHM-GNN (Motif Hypergraph Markov Graph Neural Networks), an unsupervised framework that learns joint representations for node groups by treating the graph as a Hypergraph Markov Network. By employing energy-based modeling and a novel Random Walk Tour (RWT) estimator for scalability, MHM-GNN effectively captures group-level characteristics without requiring labeled data. Experimental results across six datasets demonstrate significant improvements in hyperedge detection and structural prediction tasks compared to state-of-the-art unsupervised baselines.

Introduction

Most current Graph Neural Networks are "dyadic," meaning they learn representations by observing nodes and the pairwise edges between them. While effective for tasks like link prediction, this approach struggles to reason about larger groups. For instance, in e-commerce, identifying a "bundle" of items bought together requires understanding the synergy of a $k$-node set rather than just individual pairs.

Existing methods for higher-order relationships typically rely on supervised learning, which is often prohibitively expensive due to the need for labeled hypergraphs. MHM-GNN addresses this gap by providing a way to learn these group representations in an entirely unsupervised manner from simple pairwise graph data.

Methodology: The MHM-GNN Framework

The MHM-GNN pipeline: from input graph to motif representation via a Hypergraph Markov Network model.

The MHM-GNN approach is built upon three primary pillars:

1. Energy-Based Modeling

The framework treats the entire graph as a Hypergraph Markov Network (HMN). The probability of a graph is defined by its "energy," which is the sum of the energies of all its $k$-node induced subgraphs, or motifs. This allows the model to capture global graph distributions through local group interactions.

2. Compositional Motif Representations

To calculate the energy of a group, MHM-GNN uses a GNN to generate a representation for the $k$-node set. This representation is "compositional," meaning it is explicitly constructed from the nodes and edges within that specific group, capturing the unique synergy of the motif.

3. Scalable Estimation via Random Walk Tours

Calculating energy for every possible group of $k$ nodes is computationally intractable as it grows combinatorially. MHM-GNN solves this using Noise-Contrastive Estimation (NCE) combined with a novel Random Walk Tour (RWT) estimator. By performing specialized random walks on a "collapsed" higher-order network, the model obtains a finite-sample unbiased estimate of the total graph energy without exhaustive enumeration.

Comparison between an original graph and its collapsed higher-order network (k-CNHON) used for scalable energy estimation.

Experimental Evaluation

The model was evaluated on six diverse datasets, including citation networks (Cora, Citeseer, Pubmed), coauthorship networks (DBLP), and product networks (Steam, Rent the Runway). Two primary downstream tasks were used to test the learned representations:

  • Hyperedge Detection: Identifying hidden groups of nodes.
  • DAG Leaf Counting: Predicting the internal structure of directed relationships within a group.

Key Results

MHM-GNN consistently outperformed state-of-the-art unsupervised GNNs like GraphSAGE and Deep Graph Infomax:

  • Accuracy Gains: Hyperedge detection accuracy increased by up to 11% over baselines, while the structural DAG leaf counting task saw gains of up to 24%.
  • Robustness: The inductive approach of MHM-GNN proved superior at capturing group-level logic even when compared against transductive methods that had access to test data during training.

Discussion and Conclusion

A central insight of this work is that simple node pooling (e.g., averaging node embeddings) is insufficient for higher-order tasks; joint representations are necessary to capture group synergy. MHM-GNN successfully bridges the gap between GNNs and classical statistical physics models like Exponential Random Graph Models (ERGMs).

While the model currently requires a pre-defined group size $k$ and introduces some computational overhead compared to dyadic GNNs, it represents a significant step toward natively handling polyadic data and complex group-level reasoning in an unsupervised setting. Future work will explore handling variable-sized motifs and extending the framework to native hypergraph inputs.

Summary updated

BibTeX
@inproceedings{cotta2020unsupervised,
  author = {Leonardo Cotta and Carlos H. C. Teixeira and Ananthram Swami and Bruno Ribeiro},
  title = {{Unsupervised Joint k-node Graph Representations with Compositional Energy-Based Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=0Zl-yf0KuJl},
}
Figure