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

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

Introduction

Most current Graph Neural Networks (GNNs) are designed for "dyadic" tasks—reasoning about individual nodes ($k=1$) or edges between two nodes ($k=2$). However, many real-world problems require understanding the joint characteristics of larger groups. For example, an e-commerce platform needs to predict which $k$ items might be bought together in a single shopping cart, or a research network needs to identify groups of $k$ authors who collaborate on a single paper.

Standard GNNs struggle in these scenarios because they typically represent a group by simply aggregating individual node embeddings. Recent research has shown this is insufficient to capture unique "joint" properties of the group. The core challenge is scalability: in a graph with $n$ nodes, there are $\binom{n}{k}$ possible groups. For even modest values of $n$ and $k$, it becomes computationally impossible to evaluate every group during training.

To address this, researchers have proposed Motif Hypergraph Markov Graph Neural Networks (MHM-GNN), a novel framework for learning unsupervised representations of groups of $k$ nodes (motifs) in a graph. By combining GNNs with compositional energy-based models and a clever sampling strategy, MHM-GNN captures complex higher-order relationships that are invisible to traditional dyadic models.

Methodology: MHM-GNN

The MHM-GNN framework treats the entire graph as a Hypergraph Markov Network where the probability of the graph's structure is determined by an energy function.

  1. Compositional Energy Model: The total energy of a graph is defined as the sum of the energies of all its $k$-node induced subgraphs (motifs).
  2. GNN-based Motif Representations: To compute a motif's energy, the model uses a GNN to extract features from the $k$ nodes, followed by a permutation-invariant "READOUT" function (such as a sum followed by a multi-layer perceptron). This ensures the representation doesn't change just because you reorder the nodes in the set.
  3. Tractable Optimization: To avoid the $\binom{n}{k}$ bottleneck, the authors use Noise-Contrastive Estimation (NCE), which learns by comparing real graph data against "noise" graphs.
  4. Unbiased MCMC Estimator: The most technical innovation is the use of a finite-sample unbiased estimator for the graph energy. Instead of summing over all possible subgraphs, they use "Random Walk Tours" on a higher-order network to sample connected subgraphs. This provides a mathematically sound upper bound on the loss function, making training efficient and scalable.
The MHM-GNN model architecture combining an energy-based model with GNN motif representations.

Key Insights and Ideas

  • Beyond the Edge: The paper argues that "joint $k$-node representations" are a distinct class of problems that require models to reason about sets as a whole, rather than just pairs.
  • Sparsity is an Asset: In real-world graphs, most random sets of $k$ nodes are disconnected. The authors focus their estimator on Connected Induced Subgraphs (CISes), which are much rarer and carry more structural information, while assuming a constant high energy for disconnected sets.
  • Higher-Order Networks: To sample these motifs effectively, they conceptualize a "higher-order network" where each node represents a $k$-node motif in the original graph.
Visualizing the original graph alongside its k-CNHON representation, highlighting a Random Walk Tour.

Experimental Results

The model was evaluated on six diverse datasets that contain inherent group (polyadic) information, including citation networks (Cora, Citeseer, Pubmed), coauthorship networks (DBLP), and product networks (Steam, Rent the Runway).

The tasks involved Hyperedge Detection (identifying if a set of $k$ nodes forms a hidden group) and DAG Leaf Counting (predicting structural properties of citation subgraphs). MHM-GNN consistently outperformed state-of-the-art unsupervised GNNs like GraphSAGE and Deep Graph Infomax (DGI) across all tasks:

  • Hyperedge Detection: MHM-GNN improved classification accuracy by up to 11% over the best-performing baselines.
  • DAG Leaf Counting: The model showed even more dramatic gains, with accuracy improvements of up to 24%.
  • Ablation Study: The authors found that while the motif-based architecture itself is powerful (even with random weights), the optimization process significantly improves the quality of the learned representations.

Limitations and Future Work

While MHM-GNN solves a major scalability hurdle, it still faces challenges. The experiments primarily focused on motif sizes of $k=3, 4, 5$. As $k$ grows very large, the complexity of the higher-order network and the variance of the estimator may increase. Additionally, the assumption that all disconnected subgraphs have a "constant high energy" is a simplification that might not hold in all domains.

Future directions suggested by the authors include extending this work to design new subgraph function estimators and formulating new types of joint $k$-node tasks, such as more complex recommendation systems or multi-agent coordination.

Summary updated

Abstract

Existing Graph Neural Network (GNN) methods that learn <em>inductive unsupervised</em> graph representations focus on learning node and edge representations by predicting observed edges in the graph. Although such approaches have shown advances in downstream node classification tasks, they are ineffective in jointly representing larger k-node sets, k{&gt;}2. We propose MHM-GNN, an inductive unsupervised graph representation approach that combines joint k-node representations with energy-based models (hypergraph Markov networks) and GNNs. To address the intractability of the loss that arises from this combination, we endow our optimization with a loss upper bound using a finite-sample unbiased Markov Chain Monte Carlo estimator. Our experiments show that the unsupervised joint k-node representations of MHM-GNN produce better unsupervised representations than existing approaches from the literature.
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