Hypergraph neural network

Overview

A hypergraph generalises a graph. An ordinary edge joins two nodes; a hyperedge joins any number of nodes at once. A hypergraph neural network runs message passing over those hyperedges, so one interaction can involve a whole group rather than being split into pairs 2204.08770 §1 2204.08770 §4.1.

The core idea shared by the variants is a two-way exchange. Nodes send their states into each hyperedge, the hyperedge computes one interaction embedding from its members, and the embedding is sent back to the nodes 2204.08770 §4.2. Only one variant is on wikillm so far, so the invariant below comes from that single paper and is not yet checked across several.

Variants

GroupNet: multiscale hyperedges over agents

GroupNet infers hyperedges over the agents in a traffic or sports scene. The hyperedges are built from pairwise affinities, which are cosine similarities between agent embeddings 2204.08770 §4.1 2204.08770 eq. 1. For each agent it creates one hyperedge per scale. A hyperedge at scale s holds that agent plus the most affine agents, up to the scale's size. The exact choice maximises the total affinity inside the group. It is solved by enumeration when the number of agents is small, and by a greedy step otherwise 2204.08770 §4.1 2204.08770 eq. 2.

Each hyperedge then gives a strength r and a soft category c, produced from a Gumbel-softmax. The interaction embedding is r times the category-weighted sum of one MLP per category 2204.08770 §4.2 2204.08770 eq. 3. The categories are learned without labels. The paper calls this "unsupervised relational reasoning" 2204.08770 §3.

GroupNet is used as the social encoder inside a CVAE trajectory predictor. It can also be attached to existing predictors 2204.08770 §5 2204.08770 §6.3. Its card: GroupNet: Multiscale Hypergraph Neural Networks for Trajectory Prediction with Relational Reasoning.

When to use which

With one variant on the page, the choice is between GroupNet and not using a hypergraph at all. The paper's own comparisons are the only evidence.

Scale count matters. On NBA, adding scales improves error and then levels off. One scale gives 1.27/1.95 m at 4.0 s. Scales 1, 2, 5 and 11 give 1.13/1.69 m 2204.08770 tab. 6 2204.08770 §6.4.

Implementation sketch

Core of the hypergraph step, for one scene with N agents. It follows 2204.08770 §4.1 and 2204.08770 §4.2. Variant-specific parts (the MLPs and the Gumbel temperature) are not given numerically in the paper.

# Build one hyperedge per agent per scale  [arxiv:2204.08770 §4.1]
# Input:  queries (N, d); scales = [K_1, ..., K_S]
# Output: one 0/1 incidence matrix per scale

def build_hyperedges(queries, scales):
    # Cosine affinity between agents  [arxiv:2204.08770 eq. 1]
    unit = queries / norm(queries, axis=-1)                # (N, d)
    affinity = unit @ transpose(unit)                      # (N, N)
    incidences = []
    for k in scales:
        # Greedy form of eq. 2: each agent plus its k-1 most affine agents
        incidences.append(top_k_per_row(affinity, k))      # (N, N)
    return incidences

# One message round over the hyperedges  [arxiv:2204.08770 §4.2] [eq. 3]
# Input:  agents (N, d); incidence (E, N); categories = L
# Output: updated agents (N, d)

def message_round(agents, incidence, category_fns, tau):
    # Pool members of each hyperedge  [arxiv:2204.08770 §4.2]
    member_sum = incidence @ agents                        # (E, d)
    # Strength r in (0, 1) and Gumbel-softmax category c  [§4.2]
    collective = pool_members(agents, member_sum, incidence)
    strength = sigmoid(mlp_r(collective))                  # (E,)
    category = gumbel_softmax(mlp_c(collective), tau)      # (E, L)
    # Interaction embedding r * sum_l c_l F_l(members)  [eq. 3]
    edge = zeros(E, d)
    for l in range(L):
        edge += category[:, l, None] * category_fns[l](member_sum)
    edge = strength[:, None] * edge                        # (E, d)
    # Hyperedge-to-node update  [arxiv:2204.08770 §4.2]
    edge_sum = transpose(incidence) @ edge                 # (N, d)
    return update_fn(concat(agents, edge_sum))             # (N, d)

Implementation notes for the sketch. The paper says message passing repeats "several times" per scale without a count 2204.08770 §4.2. Its Gumbel temperature and number of categories are not stated in the cited sections. The categories are sampled again at every forward pass, so predictions are random at test time unless the implementation fixes the noise. The released code shows this behaviour; see the card for the code citation.

Hyperparameters

Values stated in the paper for the NBA setup. Anything else is not stated in the cited sections.

Contradictions

• Scale-0 links. §4.1 says each node links to the nodes it is most affine to, which gives pairwise edges 2204.08770 §4.1. §6.1 says scale 0 links each node to all other agents 2204.08770 §6.1. The two readings give different graphs, and the paper does not say which one its results used.
• Scale identity. §6.1 gives NBA scales 2, 5 and 11 2204.08770 §6.1. Table 6's best row is 1, 2, 5, 11, and the paper does not say which module corresponds to scale 2 2204.08770 tab. 6.
• Relative gains. The text reports GroupNet+CVAE lowers minADE20 by 6.5% against PECNet on SDD 2204.08770 §6.3. On the same table its minFDE20 is higher than PECNet's 2204.08770 tab. 3. Read both numbers together.
• Loss weighting. §5 writes the three loss terms without normalisation 2204.08770 §5. The released code divides them by different counts, so the effective weights differ from the formula. See the card's Paper vs code section for the details and the code citations.

Papers

• GroupNet: Multiscale Hypergraph Neural Networks for Trajectory Prediction with Relational Reasoning: builds agent hyperedges at several sizes, learns each one's strength and category without labels, and uses them as the social encoder in a CVAE for trajectory prediction.