PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Expansion for Hypergraph Learning

Tianyi Ma, Yiyue Qian, Shinan Zhang, Chuxu Zhang, Yanfang Ye

arXiv:2502.15564v1cs.SI

TL;DR

Classic hypergraph expansions can lose information or add redundancy, while fixed edge weights do not account for node-feature similarity. AdE adaptively selects representative node pairs and learns edge weights, and the paper reports strong results across seven benchmark hypergraphs compared with classic expansion methods.

  • Problem

    Classic expansions can lose information or add redundancy, and fixed edge weights ignore that nodes with similar attributes may be more strongly connected.

    Source: §1 · pp. 1–2

  • Method

    AdE uses GSi-Net to select representative node pairs for hyperedges and a distance-aware kernel to learn weighted graph edges.

    Source: §1 · p. 2

  • Results

    AdE outperforms all baseline methods on every evaluated hypergraph dataset, with experiments spanning seven benchmark hypergraphs.

    Source: §5.2 · p. 7, §6 · p. 8

  • Takeaways & Limitations

    The authors present AdE as a general expansion method whose weighted graphs can be used by GNNs for downstream learning.

    Source: §1 · p. 2

    For its expressive-power analysis, AdE uses unified node attributes and considers only node isomorphism classes.

    Source: §4.4 · p. 5

Abstract

from arXiv · show

Hypergraph, with its powerful ability to capture higher-order relationships, has gained significant attention recently. Consequently, many hypergraph representation learning methods have emerged to model the complex relationships among hypergraphs. In general, these methods leverage classic expansion methods to convert hypergraphs into weighted or bipartite graphs, and further employ message passing mechanisms to model the complex structures within hypergraphs. However, classical expansion methods are designed in straightforward manners with fixed edge weights, resulting in information loss or redundancy. In light of this, we design a novel clique expansion-based Adaptive Expansion method called AdE to adaptively expand hypergraphs into weighted graphs that preserve the higher-order structure information. Specifically, we introduce a novel Global Simulation Network to select two representative nodes for adaptively symbolizing each hyperedge and connect the rest of the nodes within the same hyperedge to the corresponding selected nodes. Afterward, we design a distance-aware kernel function, dynamically adjusting edge weights to ensure similar nodes within a hyperedge are connected with larger weights. Extensive theoretical justifications and empirical experiments over seven benchmark hypergraph datasets demonstrate that AdE has excellent rationality, generalization, and effectiveness compared to classic expansion models.

1 Introduction

Hypergraphs represent higher-order relationships through hyperedges connecting multiple nodes, and many representation-learning methods first expand them into graphs for message passing. The introduction argues that fixed-weight, straightforward expansions can lose information or introduce redundancy, motivating AdE’s adaptive weighted-graph construction.

1 Introduction

  • Hyperedges connect multiple nodes to represent higher-order relationships, and hypergraph representation learning commonly expands them into graphs before message passing.Classic options include clique, star, and line expansion.Source: §1 · p. 1
  • Classic clique expansion connects every pair in a hyperedge, which can introduce redundant information, while fixed weights ignore stronger links between nodes with similar attributes.HyperSAGE is cited as an example of uniform edge weighting.Source: §1 · pp. 1–2
  • AdE uses GSi-Net to select two representative nodes per hyperedge and a distance-aware kernel to assign larger weights to similar nodes.The resulting weighted graph can be used with graph neural networks for downstream representation learning.Source: §1 · p. 2

2 Related Work

Related work describes clique, star, and line expansions as ways to convert hypergraphs into graph structures for neural representation learning. It motivates adaptive expansion by noting that classic methods may fail to preserve higher-order information concisely.

2 Related Work

  • Clique expansion connects every node pair within a hyperedge, star expansion adds a node for each hyperedge, and line expansion represents node-hyperedge pairs.Figure 1 illustrates classic hypergraph expansion methods.Source: §2 · p. 2, Figure 1 · p. 2
  • Classic expansions may fail to preserve higher-order information concisely and can cause losses when converting hypergraphs to graphs.The paper presents adaptive expansion as a way to depict higher-order relationships among nodes better.Source: §2 · p. 2
  • GNNs combine node features with graph structure; GCN propagates layerwise, GAT weights neighbors with attention, and GIN uses Weisfeiler-Lehman-based aggregation.The paper feeds the graph produced by its adaptive expansion into GNNs for downstream tasks.Source: §2 · p. 2

3 Preliminary

The preliminaries define hypergraphs, graph neural networks, and the learning objective. The task is to expand a hypergraph into a weighted graph and use a GNN to produce node embeddings for downstream tasks.

3 Preliminary

  • A hypergraph H=(V,E,X) has nodes, hyperedges, and attribute features, with an incidence matrix recording node membership in each hyperedge.The text also introduces node and hyperedge degrees through incidence-matrix sums.Source: §3 · p. 3
  • GNNs recursively aggregate messages from neighboring nodes to produce successive node embeddings.The framework is stated to apply to any GNN, including GCN.Source: §3 · p. 3
  • The problem is to convert a hypergraph into a weighted graph and use a GNN mapping to embed each node for downstream tasks with ground-truth labels.Source: §3 · p. 3

4 Methodology

AdE expands hypergraphs through adaptive representative-node selection and distance-aware edge weighting, then uses the resulting graph for GNN learning. The section also gives theoretical results relating AdE expansions to HyperGCN and Weisfeiler–Leman tests.

4.1 GSi-Net for Adaptive Node Pair Selection

  • GSi-Net learns feature-dimension importance and uses the scaled attributes to select the most representative node pair for each hyperedge, replacing HyperGCN’s random-signal selection.The pair maximizes the difference between the nodes’ summed scaled-attribute values.Source: §4.1 · pp. 3–4
  • The remaining nodes connect to both representatives, and AdE can select representative pairs adaptively for different downstream tasks.This creates an adaptive graph rather than applying the same expansion structure to every task.Source: §4.1 · p. 4

4.2 Distance-aware Kernel for Edge Weight

  • The distance-aware kernel uses prior Euclidean distances and adaptive attributes to learn edge weights, assigning larger weights to node pairs with more similar attributes.The learned weights vary across downstream tasks, unlike fixed-weight expansion methods.Source: §4.2 · p. 4

4.3 Representation Learning

  • AdE’s weighted graph can be encoded by GNNs; the paper states that it enhances HyperGCN’s adaptive weighted edges given the same selected nodes and is equivalent to weight clique expansion on 3-uniform hypergraphs.The authors describe the expansion as general and use a two-layer GCN as an example.Source: §4.3 · p. 5

4.4 Expressive Power of AdE

  • With unified node attributes, AdE’s expansion preserves the stated 1-GWL-to-1-WL indistinguishability relation, and a 1-WL distinction of converted graphs implies the hypergraphs are non-isomorphic.The theoretical discussion focuses on node isomorphism classes.Source: §4.4 · p. 5

5 Experiments

Experiments compare AdE with expansion-based and hypergraph neural network baselines across seven benchmark hypergraphs. AdE leads the reported comparisons, while ablations and embedding visualizations examine its components and representations.

5.1 Experimental Setup

  • The experiments use five homophilic and two heterophilic datasets, evaluate accuracy, and average five runs using a 20%/20%/60% train/validation/test split.Methods are run for 500 epochs, with the best performance among searched hyperparameters reported for each method and dataset.Source: §5.1 · pp. 5–6

5.2 Performance Comparison

  • AdE-based methods outperform all baselines across seven benchmark hypergraphs, and AdE outperforms every baseline on every dataset.Table 1 compares expansion methods on GNNs; Table 2 compares HyGNNs and AdE.Source: Table 1 · p. 6, Table 2 · p. 6, §5.2 · pp. 6–7
  • Removing GSi-Net and the kernel, GSi-Net alone, or the kernel alone reduces performance across the ablation datasets.A1 removes both components, A2 removes GSi-Net, and A3 removes the kernel.Source: §5.2 · p. 7, Figure 3 · p. 7
  • AdE-GIN embeddings show more distinct class boundaries and less overlap than HyperGCN, LE-GIN, and HCHA on Cora-CA and Citeseer.Figure 4 uses colors to indicate classes.Source: §5.2 · p. 7, Figure 4 · p. 7
  • AdE’s per-round time complexity is O(N + M + E) = O(E), where N is nodes, M is hyperedges, and E is the total hyperedge size.The analysis assigns O(N), O(M), and O(E) to feature processing, representative-pair selection, and edge-weight generation, respectively.Source: §5.2 · p. 7

6 Conclusion

AdE adaptively selects representative node pairs for hyperedges and uses a distance-aware kernel to adjust edge weights. The paper reports theoretical justification and experiments on seven benchmark hypergraphs to support its effectiveness, rationality, and generality.

6 Conclusion

  • AdE combines adaptive representative-pair selection for each hyperedge with a distance-aware kernel that gives greater weights to more similar nodes.The conclusion describes AdE as a clique-expansion-based method that produces weighted graphs.Source: §6 · p. 7
  • The paper reports theoretical justifications and experiments on five homophilic and two heterophilic benchmark hypergraphs as evidence of AdE’s effectiveness, rationality, and generality.The comparison is with classic expansion methods.Source: §6 · p. 8

A Algorithm

  • The training procedure selects representative nodes, computes and normalizes distance-aware edge weights, forms an adaptive weighted graph, and feeds it to a GNN encoder.The encoder and AdE parameters are optimized by minimizing cross-entropy loss.Source: A Algorithm · p. 10

B Data Description

The section describes seven benchmark hypergraphs and baseline methods, then outlines how distance-aware edge weights reflect node-feature similarity.

B Data Description

  • The seven datasets comprise coauthorship and cocitation hypergraphs, plus Senate and House committee hypergraphs with label-dependent Gaussian node features.Cora-CA and DBLP are coauthorship datasets; Cora, Citeseer, and Pubmed are cocitation datasets.Source: B Data Description · p. 10

C Baseline Settings

  • Baselines include feature-only MLP and HyGNNs using convolution, attention, nonlinear node and hyperedge updates, multiset functions, diffusion, or sheaf models.The authors report following baseline source-code settings to reproduce results.Source: C Baseline Settings · p. 10

D.1 Proof of Proposition 1

  • The distance-aware kernel uses feature-space distances and learnable per-dimension sensitivity to assign smaller weights to dissimilar node pairs and larger weights to similar pairs.The edge weight is computed as Wi,j = exp(−Γi,j).Source: §D.1 · p. 10

D.2 Proof of Proposition 2

The proof compares AdE with HyperGCN when both select the same representative nodes: AdE’s distance-aware kernel can assign feature-sensitive weights rather than fixed ones.

D.2 Proof of Proposition 2

  • When the kernel assigns the same positive weight to every edge, the normalized weights are the same as HyperGCN’s.The proof presents this as the worst case for the kernel.Source: §D.2 · pp. 10–11
  • With identical representative nodes, AdE assigns higher weights to similar-feature node pairs than HyperGCN’s fixed weighting.HyperGCN assigns each edge in the converted hyperedge weight (2|e| −3)^−1.Source: §D.2 · pp. 10–11

D.3 Proof of Proposition 3

The proof describes AdE’s adjacency construction and shows that, for 3-uniform hypergraphs, it is equivalent to weighted clique expansion.

D.3 Proof of Proposition 3

  • The adjacency-matrix formulation identifies H as the incidence matrix and w as an edge-weight function.AdE uses W̄ from Eq. 4 as the criterion for computing edge weights in its adjacency matrix.Source: §D.3 · p. 11
  • For a 3-uniform hypergraph, AdE selects two nodes and treats the remaining node as a mediator, generating edges among all three nodes.Because each hyperedge has one mediator in this setting, the resulting graph structure matches clique expansion; the weights can use W̄.Source: §D.3 · p. 11
  • The proof concludes that AdE is equivalent to weighted clique expansion on 3-uniform hypergraphs.The argument uses the fact that AdE produces the same graph structure as clique expansion and allows the weight matrix to be replaced with W̄.Source: §D.3 · p. 11

D.4 Proof of Lemma 1

The proof argues by contradiction, using node and edge correspondences to challenge an assumption that the AdE graphs lack a matching structure.

D.4 Proof of Lemma 1

  • The proof assumes that no bijection maps the nodes of the two graphs so their incident edge sets correspond.It introduces a mapping between hypergraph nodes and a correspondence between incident edges.Source: §D.4 · p. 11
  • Equal 1-GWL labels at iteration t imply a bijection between the corresponding incident edge sets.The proof also describes mappings between nodes and their incident edge sets.Source: §D.4 · p. 11
  • The proof concludes that AdE’s node bijection contradicts the assumed absence of a matching correspondence.It frames this contradiction as completing the proof.Source: §D.4 · p. 11

D.5 Proof of Theorem 1

The proof transfers matching hypergraph labels and neighborhood correspondences to the converted graphs. It concludes that 1-WL cannot distinguish those graphs when 1-GWL cannot distinguish the hypergraphs.

D.5 Proof of Theorem 1

  • At initialization, the proof treats node labels in both graphs and node and hyperedge labels in both hypergraphs as identical.This is the base case for the iteration argument.Source: §D.5 · p. 11
  • The proof uses bijective mappings between hypergraph and graph nodes and between each converted node’s neighborhoods.The mappings relate nodes and their neighbors across the two converted graphs.Source: §D.5 · pp. 11–12
  • If 1-GWL cannot distinguish the hypergraphs, the proof concludes that 1-WL cannot distinguish their converted graphs.It establishes matching labels at iteration t + 1 for corresponding converted-graph nodes.Source: §D.5 · pp. 11–12

D.6 Proof of Theorem 2

Assuming 1-WL distinguishes the AdE-converted graphs at iteration t > 0, the proof derives a corresponding 1-GWL distinction between the hypergraphs.

D.6 Proof of Theorem 2

  • The proof uses the label-update step and Eqs. 26–28 to derive the distinguishing-label conclusion.It invokes the AdE property that hypergraphs with identical features and structures convert into the same graph.Source: §D.6 · p. 12
  • 1-GWL decides H and H′ are non-isomorphic at iteration t after 1-WL distinguishes their AdE-converted graphs at t > 0.The proof states this conclusion after deriving distinct hyperedge labels and then different node labels.Source: §D.6 · p. 12
Loading 2502.15564v1…