Semi-supervised Hypergraph Node Classification on Hypergraph Line Expansion

1 INTRODUCTION

• Prior formulations often privilege vertices or break the bipartite property, while some deep models use two-stage message passing on heterogeneous structures.Other approaches can lose higher-order information when they construct weighted simple graphs.Source: §1 · pp. 1–2
• LE is presented as a homogeneous, bijective mapping that allows existing graph representation-learning methods to work on hypergraphs.The introduction contrasts this with formulations that impose constraints or produce heterogeneous topologies.Source: §1 · p. 2
• LE maps each incident vertex–hyperedge pair to a line node, connecting pairs that share a vertex or hyperedge.The induced graph is homogeneous and symmetric with respect to original vertices and hyperedges, and the bijective mapping preserves higher-order information.Source: §1 · p. 2
• LE projects hypergraph vertex features to the induced graph, applies graph-learning algorithms, then aggregates and back-projects representations for vertex classification.The transformation is differentiable and the overall learning process is end-to-end.Source: §1 · p. 2
• LE treats vertices and hyperedges equally, unlike formulations that transform hyperedges into cliques or rely solely on edge connectivity.The paper also frames standard star or clique expansion and simple graph learning algorithms as special cases of LE.Source: §1 · p. 2

• LE-based GCNs consistently outperform several strong hypergraph-learning baselines across five real-world hypergraphs.The paper evaluates GCNs [26] on LE.Source: §1 · p. 2

2.1 Hypergraph Notations

• A hypergraph has vertex set V and hyperedge set E, where each hyperedge is a subset of V; its incidence matrix records vertex–hyperedge membership.Vertex and hyperedge degrees count their respective incidences.Source: §2.1 · p. 2

2.2 Problem Setup

• The task is transductive node classification: infer labels for unlabeled vertices from labeled data and the graph’s geometric structure.The empirical risk is defined over labeled vertices, using ground-truth labels and commonly cross-entropy loss.Source: §2.2 · p. 2
• The setup assumes vertex similarity and edge similarity are equally important for label learning, reflecting hypergraph symmetry.The paper focuses on node classification and notes possible extension to hyperedge representation, such as relation mining.Source: §2.2 · p. 2

3.1 Traditional Hypergraph Expansions

• Clique expansion loses higher-order dependencies, while star expansion retains incidence information but remains heterogeneous and lacks explicit vertex–vertex links.These limits motivate a representation that preserves higher-order relations while remaining suitable for graph algorithms.Source: §3.1 · p. 3

3.2 Our Line Expansion

• LE treats vertices and hyperedges symmetrically, representing each incident vertex–hyperedge pair as a line node and linking pairs that share a vertex or hyperedge.Each original vertex or hyperedge induces a clique in the resulting graph.Source: §3.2 · p. 3

3.2.1 Line Expansion.

• LE generalizes neighborhood aggregation by treating line nodes as neighbors when they share a vertex or a hyperedge, preserving higher-order associations.The construction regards each vertex–hyperedge incidence as a whole.Source: §3.2.1 · p. 3

3.3 Entity Projection

• Entity projection distributes vertex information across line nodes, and the bijective mapping guarantees that the original hypergraph can be uniquely recovered.Vertex back-projection aggregates the distributed line-node information, weighting contributions by reciprocal hyperedge size.Source: §3.3 · pp. 3–4

3.4 Additional Properties of Line Expansion

• LE is isomorphic to the line graph of the star expansion; it is homogeneous and has the same connectivity as the original hypergraph.The paper distinguishes this construction from the line graph of a hypergraph.Source: §3.4 · p. 4
• For fully connected k-regular hypergraphs, the worst-case size grows as |V_l| = Θ(k|E|) and |E_l| = Θ(k^2|E|^2), while sparse real hypergraphs usually reduce the scale.The stated sparse cases include long-tailed degree distributions and most vertices or hyperedges having degree one.Source: §3.4 · p. 4

4.1.1 Overall Pipeline.

• The node-classification pipeline projects hypergraph vertex features onto line nodes, applies graph learning, then back-projects and fuses their representations for vertex prediction.The broader mapping is intended to transfer hypergraph learning problems to graph structures; this work considers generic hypergraphs without edge weights.Source: §4.1.1 · p. 4, §4 · p. 4

4.2 Convolution on Line Expansion

• Graph convolution aggregates information from line-node neighbors that share either a vertex or a hyperedge, with separate weights for the two similarities.The two terms respectively aggregate neighbors sharing the same hyperedge and those sharing the same vertex.Source: §4.2 · p. 5
• The paper focuses on vertex node classification; learning hyperedges, including for relation mining, is left for future work.The authors point to the symmetry of vertices and hyperedges as relevant to those future applications.Source: §4.2 · p. 5

4.3 Unifying Hypergraph Expansion

• Line-expansion convolution generalizes simple graph convolution, while LE generalizes clique and star expansions.The method treats vertex–hyperedge relations as a whole and exchanges information across vertices and hyperedges simultaneously.Source: §4.3 · p. 5

4.4 Acceleration: Neighborhood Sampling

• Neighborhood sampling uses separate thresholds for vertex- and hyperedge-neighbor sets, randomly sampling from either set when its degree exceeds the threshold.The approach targets computational problems from high-degree vertices by reducing the receptive field.Source: §4.4 · p. 5
• After neighborhood sampling, the model's running time is reported as comparable to state-of-the-art baselines.The model's runtime is proportional to the number of connected edges in the line expansion.Source: §4.4 · p. 5

5.1 Hypergraph Node Classification

• The five hypergraphs span news articles, categorical UCI data, and 3D datasets; accuracy is the main classification metric.The datasets are 20Newsgroups, Mushroom, Zoo, ModelNet40, and NTU 3D.Source: §5.1 · p. 6
• LE_GCN beats SOTA hypergraph methods by 2% consistently across all five datasets.Table 3 reports accuracy and running-time comparisons on real-world hypergraphs.Source: §5.1 · p. 6, Table 3 · p. 7
• After neighbor sampling, LE graphs are much sparser than clique expansions, with density about 1/1000 for most datasets.Before sampling, LE scale is within five times that of the flattened topology except for Zoo; running time is comparable to some state-of-the-art methods, especially on 20News, ModelNet40, and NTU2012.Source: §5.1 · pp. 6–7, Table 2 · p. 6

5.2 Simple Graph Node Classification

• On citation-network node classification, LE methods match or outperform their original methods, and LE_GCN ties original GCN on all three datasets.Non-end-to-end methods consistently outperform their original algorithms when applied to LE graphs.Source: §5.2 · p. 7, Table 5 · p. 7

5.3 Ablation Study on on 𝑤𝑒and 𝑤𝑣

• Accuracy curves first rise and then fall as vertex- and hyperedge-similarity weights vary, indicating benefit from aggregating both neighbor types.The preferred hyperedge weight differs by dataset: it peaks below 1 for 20News and Mushroom, and above 1 for ModelNet40 and NTU2012; the authors suggest smaller weights when there are fewer hyperedges.Source: §5.3 · p. 7, Figure 3 · p. 8

6 CONCLUSION AND FUTURE WORKS

• LE transforms hypergraphs into simple homogeneous graphs without losing structure information, and its GCN extension outperforms strong baselines on five real-world datasets.The paper also identifies edge learning and directed graphs as possible extensions.Source: §6 · p. 8
• Applying LE to edge learning in complex graphs is a proposed future direction.The paper also proposes extending LE to directed graphs, where relations are not reciprocal.Source: §6 · p. 8
• Evaluation on large hypergraphs such as DBLP or Yelp against recent two-stage baselines such as AllSet remains future work and is identified as a possible limitation.Source: §6 · p. 8

7.1 Proof of Theorem 1

• The proof assumes without proof that the hypergraph has a one-to-one relation with its star expansion.Source: §7.1 · p. 8
• The proof treats disconnected star expansions componentwise and establishes uniqueness for star-expansion graphs without Whitney’s K3 exception before reconstructing the star expansion from its line graph.The reconstruction uses a maximum independent set and selected cliques that cover the line-graph nodes.Source: §7.1 · p. 8

7.2 Proof of Theorem 3

• Line-expansion adjacency recovers star-expansion adjacency, while its degraded form corresponds to clique-expansion adjacency with 1-order self-loops.Source: §7.2 · p. 9
• When a graph is treated as a 2-regular hypergraph, the resulting adjacency differs from standard graph convolution only by a factor of 2 that can be absorbed into the filter.Source: §7.2 · p. 9

7.3 Proof of Observation 1

• Each row of the line-node incidence matrix has two 1s, and its product with its transpose yields line-expansion adjacency with 2-order self-loops.Source: §7.3 · pp. 9–10