Hypergraph Basics: Incidence Matrices and Clique Expansion

Standard graphs connect pairs of nodes: each edge has exactly two endpoints. Many real-world relationships involve more than two entities simultaneously — a research paper has multiple co-authors, a chemical reaction involves multiple reactants and products, a collaboration project connects a team of people. These multi-way relationships are naturally modeled as hypergraphs, where a single hyperedge can connect any number of nodes.

TGraphX provides hypergraph utilities in tgraphx.mining.hypergraph. The module is experimental and evolving; this article explains the mathematical foundations, the key operations (incidence matrix construction and clique expansion), and how to work with hypergraphs in TGraphX.

What Is a Hypergraph

A hypergraph H = (V, E) consists of a vertex set V and a set of hyperedges E, where each hyperedge e ∈ E is a subset of V of arbitrary size. Ordinary graphs are the special case where every hyperedge has exactly two members.

Example: Consider five authors {A, B, C, D, E} and three papers:
- Paper 1 authored by {A, B, C}
- Paper 2 authored by {C, D}
- Paper 3 authored by {B, D, E}

The hyperedges are {{A,B,C}, {C,D}, {B,D,E}}. No standard graph can represent these three-way co-authorship relationships without loss of information.

The Incidence Matrix

The incidence matrix H of a hypergraph with |V| = N nodes and |E| = M hyperedges is an N × M binary matrix where:

H[v, e] = 1   if node v belongs to hyperedge e
        H[v, e] = 0   otherwise
        

For the co-authorship example:

        Paper1  Paper2  Paper3
        A         1       0       0
        B         1       0       1
        C         1       1       0
        D         0       1       1
        E         0       0       1
        

From H, several useful matrices are derived:

• Node degree matrix D_v = diag(H · 1): diagonal matrix where D_v[i,i] is the number of hyperedges node i belongs to.
• Hyperedge degree matrix D_e = diag(H^T · 1): diagonal matrix where D_e[j,j] is the cardinality (number of nodes) in hyperedge j.
• Hypergraph Laplacian: Δ = D_v^{-1/2} H W D_e^{-1} H^T D_v^{-1/2} where W is a diagonal hyperedge weight matrix.

Prerequisites

This article assumes:

• Familiarity with standard graph adjacency and Laplacian matrices
• Basic linear algebra (matrix multiplication, eigenvalues)
• PyTorch basics for tensor operations

Install TGraphX:

pip install tgraphx
        

The hypergraph module is marked Experimental in TGraphX. API stability is not guaranteed between minor versions. Review the TGraphX GitHub for the current API before writing production code.

Building an Incidence Matrix with TGraphX

import torch
        from tgraphx.mining.hypergraph import HypergraphBuilder, compute_incidence_matrix
        
        # Define hyperedges as lists of node indices
        hyperedges = [
            [0, 1, 2],    # hyperedge 0: nodes 0, 1, 2
            [2, 3],       # hyperedge 1: nodes 2, 3
            [1, 3, 4],    # hyperedge 2: nodes 1, 3, 4
        ]
        num_nodes = 5
        
        # Build incidence matrix [N, M]
        H = compute_incidence_matrix(hyperedges, num_nodes)
        print(H.shape)   # [5, 3]
        print(H)
        # tensor([[1., 0., 0.],
        #         [1., 0., 1.],
        #         [1., 1., 0.],
        #         [0., 1., 1.],
        #         [0., 0., 1.]])
        

You can also use the builder interface for incremental construction:

builder = HypergraphBuilder(num_nodes=5)
        builder.add_hyperedge([0, 1, 2])
        builder.add_hyperedge([2, 3])
        builder.add_hyperedge([1, 3, 4])
        
        H = builder.incidence_matrix()   # [5, 3]
        node_degrees = builder.node_degrees()    # [5] — number of hyperedges per node
        edge_degrees = builder.edge_degrees()   # [3] — cardinality of each hyperedge
        

Clique Expansion

Clique expansion converts a hypergraph into a standard pairwise graph by replacing each hyperedge with a complete graph (clique) on its member nodes. This allows standard GNN architectures to be applied to hypergraph data.

For a hyperedge {A, B, C}, clique expansion adds edges (A,B), (A,C), and (B,C).

from tgraphx.mining.hypergraph import clique_expansion
        
        hyperedges = [
            [0, 1, 2],
            [2, 3],
            [1, 3, 4],
        ]
        
        # Returns edge_index [2, E'] for the expanded graph
        expanded_edge_index = clique_expansion(hyperedges, num_nodes=5)
        print(expanded_edge_index.shape)  # [2, E'] — E' depends on hyperedge sizes
        
        # The expanded graph can now be used with any TGraphX GNN layer
        from tgraphx.layers.sage import TensorGraphSAGELayer
        
        layer = TensorGraphSAGELayer(in_channels=16, out_channels=32)
        x = torch.randn(5, 16)
        out = layer(x, expanded_edge_index)
        print(out.shape)  # [5, 32]
        

Clique expansion is computationally cheap and enables immediate use of existing GNN infrastructure. However, it loses hyperedge identity — the model cannot distinguish whether three nodes are connected by a single 3-way hyperedge or by three separate pairwise edges.

Hyperedge Convolution via the Incidence Matrix

A more principled alternative to clique expansion is to perform message passing through the incidence matrix directly. The two-step hyperedge convolution proceeds as:

1. Node to hyperedge aggregation: Each hyperedge aggregates its member nodes' features.
2. Hyperedge to node aggregation: Each node aggregates information from all hyperedges it belongs to.

import torch
        import torch.nn.functional as F
        
        def hyperedge_conv(x, H, W_e=None, W_v=None):
            """
            Two-step hyperedge convolution.
            x: [N, D] node features
            H: [N, M] incidence matrix (float)
            W_e: optional [M, M] hyperedge weight diagonal (defaults to identity)
            """
            # Step 1: Node -> Hyperedge (aggregate nodes in each hyperedge)
            # D_e_inv: diagonal of 1 / edge_degree
            edge_degrees = H.sum(dim=0).clamp(min=1)          # [M]
            D_e_inv = torch.diag(1.0 / edge_degrees)           # [M, M]
        
            # [M, D]: hyperedge embeddings = D_e^{-1} H^T x
            e = D_e_inv @ H.t() @ x
        
            # Optional: apply per-hyperedge weighting
            if W_e is not None:
                e = W_e @ e
        
            # Step 2: Hyperedge -> Node (aggregate hyperedges each node belongs to)
            node_degrees = H.sum(dim=1).clamp(min=1)           # [N]
            D_v_inv = torch.diag(1.0 / node_degrees)           # [N, N]
        
            # [N, D]: node output = D_v^{-1} H e
            out = D_v_inv @ H @ e
            return out
        
        H = compute_incidence_matrix(hyperedges, num_nodes=5).float()
        x = torch.randn(5, 16)
        out = hyperedge_conv(x, H)
        print(out.shape)  # [5, 16]
        

This implementation is pedagogically clear but not GPU-optimized for large hypergraphs. The TGraphX hypergraph module provides optimized sparse variants.

Clique Expansion vs Incidence Matrix Convolution: Comparison

For most practical tasks, clique expansion is a reasonable first step that uses all existing GNN infrastructure. Use incidence matrix convolution or star expansion when you need to distinguish different hyperedge cardinalities or when multiple hyperedges connecting the same node subset should be treated differently.

Limitations and Honest Notes

The TGraphX hypergraph module is experimental. The API may change between minor releases. Do not depend on specific argument names or return formats in production code without pinning the TGraphX version.

Clique expansion is lossy. A triangle in the expanded graph might come from a 3-way hyperedge or from three independent pairwise edges — the GNN cannot distinguish these without additional markup.

Incidence matrix convolution scales as O(N × M). For hypergraphs with large numbers of hyperedges, storing the dense incidence matrix in GPU memory may be prohibitive. Use sparse tensor representations for large inputs.

No benchmark comparisons are provided here. Hypergraph GNN performance is dataset-dependent and sensitive to hypergraph construction choices. Treat all published numbers as dataset-specific rather than general claims.

Higher-order expressiveness requires care. Hypergraph methods are not automatically more expressive than standard GNNs just because they model multi-way interactions. Expressiveness depends on the specific message-passing scheme and aggregation operators used.

Frequently Asked Questions

When should I use a hypergraph instead of a standard graph?
When the natural structure of your data is multi-way: co-authorship, group membership, multi-participant interactions, reactions with multiple agents. Forcing a hypergraph into pairwise edges by clique expansion loses structural information that may be predictive.

Can I combine hypergraph convolution with standard GNN layers?
Yes. After the hyperedge convolution produces node embeddings, you can pass them to any TGraphX GNN layer (e.g., TensorGraphSAGELayer, TensorGATLayer) for further processing.

How do I construct a hypergraph from a knowledge graph?
One common construction is to create a hyperedge for each relation type connecting all entities that participate in that relation. Alternatively, clique-expand the knowledge graph and use standard GNNs. See knowledge graph embedding with TGraphX for knowledge graph GNN approaches.

Where is the full source code?
GitHub, package: PyPI.

A Full Hypergraph Node Classification Example

Combining the incidence matrix convolution with downstream classification gives a complete pipeline:

import torch
        import torch.nn as nn
        import torch.nn.functional as F
        from tgraphx.mining.hypergraph import compute_incidence_matrix, clique_expansion
        from tgraphx.layers.sage import TensorGraphSAGELayer
        
        # Define hyperedges (e.g., from a co-authorship network)
        hyperedges = [
            [0, 1, 2, 3],
            [2, 3, 4],
            [3, 4, 5, 6],
            [6, 7, 8],
            [7, 8, 9],
        ]
        num_nodes = 10
        num_classes = 3
        
        # Build both representations
        H = compute_incidence_matrix(hyperedges, num_nodes).float()  # [10, 5]
        expanded_ei = clique_expansion(hyperedges, num_nodes)        # [2, E']
        
        # Node features
        x = torch.randn(num_nodes, 32)
        labels = torch.randint(0, num_classes, (num_nodes,))
        
        # Two-step hyperedge convolution as pre-processing
        def hyperedge_conv(x, H):
            edge_deg = H.sum(0).clamp(min=1)
            node_deg = H.sum(1).clamp(min=1)
            e = (H.t() @ x) / edge_deg.unsqueeze(1)
            out = (H @ e) / node_deg.unsqueeze(1)
            return out
        
        x_hyp = F.relu(hyperedge_conv(x, H))  # [10, 32]
        
        # Then apply standard GNN on the clique-expanded graph
        class HypergraphGNN(nn.Module):
            def __init__(self, in_dim, hidden_dim, num_classes):
                super().__init__()
                self.gnn1 = TensorGraphSAGELayer(in_dim, hidden_dim)
                self.gnn2 = TensorGraphSAGELayer(hidden_dim, num_classes)
        
            def forward(self, x, edge_index):
                x = F.relu(self.gnn1(x, edge_index))
                return self.gnn2(x, edge_index)
        
        model = HypergraphGNN(32, 64, num_classes)
        optimizer = torch.optim.Adam(model.parameters(), lr=1e-2)
        
        for epoch in range(50):
            model.train()
            optimizer.zero_grad()
            out = model(x_hyp, expanded_ei)
            loss = F.cross_entropy(out, labels)
            loss.backward()
            optimizer.step()
        
        model.eval()
        with torch.no_grad():
            pred = model(x_hyp, expanded_ei).argmax(1)
        acc = (pred == labels).float().mean()
        print(f"Accuracy: {acc.item():.4f}")
        

This two-stage pipeline — hyperedge convolution followed by GNN on the clique-expanded graph — is a pragmatic approach that leverages the hyperedge structure in the pre-processing step while using well-tested GNN infrastructure for the main computation.

Hypergraphs in Practice: Co-Authorship and Protein Complexes

Two real-world application domains illustrate the value of hypergraphs:

Co-authorship networks. In a standard graph model, a paper with 5 authors requires 5×4/2 = 10 pairwise edges. With many multi-author papers, the graph becomes dense and loses information about which authors collaborated on the same specific paper. A hypergraph uses one hyperedge per paper, capturing the precise collaboration set.

Protein complexes. Proteins interact in complexes involving three or more members simultaneously. Standard protein-protein interaction (PPI) graphs model binary interactions and miss the multi-way structure of large protein complexes. Hyperedges representing complexes preserve this information.

Both domains benefit from the incidence matrix convolution approach: nodes (authors or proteins) aggregate information from all hyperedges (papers or complexes) they participate in, then propagate that information back through the hyperedge membership.

Connection to Labeled Propagation

Hypergraph structure can also be exploited without deep learning. TGraphX's tgraphx.mining.label_prop module implements label propagation, which spreads known labels through the graph via the Laplacian. On a clique-expanded hypergraph, label propagation naturally spreads labels within tight-knit communities:

from tgraphx.mining.label_prop import LabelPropagation
        
        # Use the clique-expanded graph for label propagation
        lp = LabelPropagation(num_nodes=num_nodes, num_iterations=20, alpha=0.9)
        
        # Partial labels (some nodes labeled, others unlabeled = -1)
        partial_labels = torch.tensor([-1, 0, 1, -1, 2, -1, 1, -1, 0, -1])
        propagated = lp(partial_labels, expanded_ei)
        print(propagated.argmax(1))  # predicted class for each node
        

Label propagation on clique-expanded hypergraphs is a strong baseline for semi-supervised node classification. It requires no gradient-based training and can handle very sparse label settings effectively.