Attributed Hypergraph Generation with Realistic Interplay Between Structure and Attributes (Extended Abstract)

1 Introduction

Many real-world interactions occur in groups, such as coauthorship among researchers and group discussions on online Q&A sites. Hypergraphs, which consist of hyperedges, naturally represent group interactions involving an arbitrary number of individuals or entities. Hypergraph modeling has shown effectiveness in applications such as clustering [Kumar et al., 2020; Hayashi et al., 2020], classification [Yu et al., 2012], and anomaly detection [Chun et al., 2024].

Real-world hypergraphs exhibit systematic structural patterns, such as high-degree nodes [Do et al., 2020], densely overlapping hyperedges [Lee et al., 2021], and high transitivity [Kim et al., 2023]. Building upon these findings, a number of hypergraph generative models have been proposed to reproduce realistic hypergraph structure. These models help explain real-world hypergraphs, and they are also employed in various data-mining applications, including community detection [Ruggeri et al., 2023; Badalyan et al., 2024] and hyperedge prediction [Contisciani et al., 2022].

* This is an abridged version of a paper that won the Best Paper Award at ICDM 2025 [Chun et al., 2025]

Despite their success, most hypergraph generative models overlook the interplay between hypergraph structure and node attributes. Node attributes can offer valuable information such as affiliation and field of study in co-authorship hypergraphs, where nodes represent authors and hyperedges represent co-authored publications. Moreover, as exemplified by homophily [McPherson et al., 2001], such node attributes can influence the formation of hyperedges.

Thus, we propose NOAH (Node Attribute based Hypergraph generator), a novel hypergraph generative model based on node attributes. To avoid considering exponentially many hyperedge candidates, NOAH forms each hyperedge through sequential attachments of nodes to its seed node(s). Attachment probabilities are computed by multiplying affinity scores derived from the values of each node attribute. In addition, NOAH incorporates a core-fringe node hierarchy to enhance realism. We also introduce NOAHFIT, which learns the parameters of NOAH to capture the structure-attribute interplay in a given hypergraph.

Through experiments on nine real-world hypergraphs using six structure-attribute measures, we show that NOAH with NOAHFIT outperforms eight existing hypergraph generative models in the overall assessment across the measures.

2 RelatedWork and Preliminaries

We review related work and introduce the notation used throughout the paper.

Related Work. (Hyper)graph generative models aim to reproduce structural patterns observed in real-world (hyper)graphs [Chakrabarti and Faloutsos, 2006; Lee et al., 2025], often to uncover mechanisms behind their formation. Several models exploit node hierarchies [Kim et al., 2023; Papachristou and Kleinberg, 2022]; our model follows this line through a simple yet effective core-fringe structure.

Recently, various deep learning based (hyper)graph generative models, including variational autoencoders [Simonovsky and Komodakis, 2018], generative adversarial networks [Bojchevski et al., 2018; De Cao and Kipf, 2018], and diffusion models [Liu et al., 2023], have also been proposed. However, these models typically require a large collection of graph instances for training.

For graphs, several generative models incorporate node attributes, which can play a crucial role in graph generation, as demonstrated by homophily [McPherson et al., 2001]. Examples include the exponential random graph model [Robins et al., 2007], the stochastic block model [Airoldi et al., 2008], and the latent space model [Wang et al., 2023]. Among them, the Multiplicative Attribute Graph (MAG) model [Kim and Leskovec, 2012] is especially relevant, as our attributeaffinity formulation is inspired by its multiplicative edge probability.

In contrast, very few hypergraph generative models incorporate node attributes. One exception is a stochastic block model variant [Badalyan et al., 2024], where attributes are conditionally independent of the hypergraph structure given latent communities and thus do not directly drive hyperedge formation. Unlike these models, NOAH forms hyperedges explicitly based on attribute relationships among nodes, extending the attribute-driven perspective of MAG from pairwise edges to group-wise interactions.

Preliminaries. An attributed hypergraph H = (V, E,X) consists of a set of nodes V = {v1, · · · , v|V|}, a set of hyperedges E = {e1, · · · , e|E|}, and a node attribute matrix X ∈ {0, 1}|V|×k . Each hyperedge e ∈ E is a non-empty subset of nodes, and x(l) i denotes the l-th attribute value of node vi. In this work, we assume binary node attributes, which simplifies both model design and implementation while remaining valid for many real-world datasets. Moreover, categorical and continuous attributes can also be converted into binary ones via one-hot encoding and thresholding, respectively, as in our experiments.

3 ProposedMethod

We introduce NOAH, a node attribute-based hypergraph generator, and NOAHFIT, its parameter fitting algorithm. The generation process is illustrated in Figure 1.

3.1 Proposed GenerationMethod: NOAH

NOAH generates a hypergraph by stochastically sampling nodes to attach to each hyperedge. The node set V is partitioned into two disjoint subsets: the core node set C ⊆ V and the fringe node set F ⊆ V, s.t. C ∪ F = V. NOAH generates each hyperedge in a two-step process. First, a subset of core nodes form a core group. Second, fringe nodes attach to the core group according to attribute affinity with the group.

Step 1. CoreGroupConstruction. NOAH initiates hyperedge construction by forming a subset of core nodes C˜ e ⊆ C, which plays a role as the structural nucleus of the hyperedge. Specifically, it first samples a seed core node vs ∈ C from the seed probability distribution pseed ∈ [0, 1]|C| . Each remaining core node vc ∈ C \ {vs} is then added based on its attribute affinity with the seed node vs, computed as:

where ΘC = {θ(1) C , . . . , θ(k) C } denotes core attribute affinity matrices, and each θ(l) C ∈ R2×2 captures the affinity between binary values of the l-th attribute.

Step 2. Fringe Attachment. Given the core group C˜ e, NOAH constructs a binary attribute vector xC˜ e ∈ {0, 1}k . Each l-th attribute x(l) C˜ e is independently sampled as:

This samples each attribute according to its average presence among core-group members. Each fringe node vf ∈ F is then attached with probability:

where ΘF = {θ(1) F , . . . , θ(k) F } is the set of fringe affinity matrices, and each θ(l) F ∈ R2×2 captures the affinity between binary values of the l-th attribute.

(a) Citeseer (NOAH ranks first overall)

(b) High School (NOAH ranks first overall)

Average Rank over Nine Datasets (NOAH ranks first overall)

Table 1: NOAH outperforms baselines in reproducing structure-attribute interplay on three representative datasets and achieves the best average rank over nine datasets. Top three results are highlighted in blue (first), green (second), and yellow (third). A.R.: average rank.

3.2 Proposed FittingMethod: NOAHFIT

NOAHFIT fits NOAH to a given attributed hypergraph by learning pseed, ΘC , and ΘF .

Core and Fringe Partition. Given a hypergraph H, NOAHFIT identifies core nodes C using UMHS [Amburg et al., 2021] and defines fringe nodes as its complement, i.e., F = V \ C. Each hyperedge e is decomposed into core and fringe subsets, Ce = e ∩ C and Fe = e ∩ F.

Derivation of the Likelihood of Each Hyperedge. For each hyperedge e, NOAHFIT decomposes its likelihood into core group construction and fringe attachment:

Here, Pcore(e) accounts for selecting a seed core and attaching the remaining cores in Ce, while Pfringe(e) accounts for attaching fringe nodes in Fe.

• Likelihood of Sampling Core Nodes: Given a hyperedge e, the likelihood Pcore(e) of its core group Ce is:

where PC(Ce \ {vs}|vs) is the likelihood of sampling the remaining core nodes Ce \ {vs} ⊂ C given the seed node vs.

• Likelihood of Sampling Fringe Nodes: Given the core group Ce, the likelihood of its fringe subset Fe is:

where PF (vf |Ce) is the probability of attaching fringe node vf to the core group Ce, obtained by marginalizing over the stochastic binary attribute vector xCe of Ce.

Update of the Parameters of NOAH. NOAHFIT learns the parameters by minimizing

Ledge is the negative log-likelihood over hyperedges. Ldeg and Lcard are the MSE losses matching expected degree and cardinality distributions with those of the input hypergraph.

4 Experiments

We present experimental results demonstrating the effectiveness of NOAH and NOAHFIT.

4.1 Experimental Settings

Datasets. We use nine real-world hypergraphs from four domains: Citeseer & Cora [Yadati et al., 2019] (Academic Paper), High School [Chodrow et al., 2021] & Workspace [G´enois and Barrat, 2018] (Contact), Amazon Music [Ni et al., 2019], Yelp Restaurant & Yelp Bar [Amburg et al., 2020] (Review), Devops & Patents (Online Q&A) 1 . Note that our experiments are done with varying numbers of attributes, scaling from 5 (Workspace) to 3,703 (Citeseer).

Baselines. We consider eight baseline generative models: HYPERCL, HYPERLAP [Lee et al., 2021], HYPERPA [Do et al., 2020], HYPERFF [Kook et al., 2020], hyper dK [Nakajima et al., 2021], THERA [Kim et al., 2023], HYCOSBM [Badalyan et al., 2024], HYREC [Choe et al., 2025]. Among the baselines, HYCOSBM explicitly utilizes node attributes. For HYPERPA, HYPERFF, THERA, and HYREC, where node identities are not preserved during the generation process, we assign node attributes randomly. For identitypreserving baselines, we assign attributes according to the corresponding original nodes.

1 https://archive.org/download/stackexchange

Evaluation. We compare models in terms of their ability to reproduce the structure-attribute interplay using six metrics. Type-s affinity ratio scores (T2, T3, T4) capture fine-grained attribute compositions within size-s hyperedges, while hyperedge entropy (HE), higher-order hyperedge entropy (HOHE), and node homophily score (NHS) capture attribute homogeneity at the hyperedge and node levels. For all metrics, lower values indicate smaller discrepancies from the ground-truth hypergraph. Detailed descriptions of the metrics are provided in the full paper [Chun et al., 2025].

4.2 Performance Comparison

In Table 1, we report results on three datasets (Citeseer, High School, Amazon Music) from different domains, along with the average rank over all nine datasets. Averaged over nine datasets, NOAH ranks first in four metrics (type-3 affinity score, type-4 affinity score, hyperedge entropy, and node homophily score), second in type-2 affinity score, and third in higher-order hyperedge entropy. NOAH achieves the best average rank on 5 out of 9 datasets. These results demonstrate the overall superiority of NOAH in capturing the structure-attribute interplay of real-world hypergraphs.

4.3 Case Study

We conduct a case study on the Amazon Music dataset, where the first attribute indicates whether a reviewer has reviewed music in the New York Blues genre. As shown in Figure 2, the ground-truth hypergraph exhibits strong homophily: hyperedge entropy is skewed toward 0, node homophily is skewed toward 1, and the type-(4, 4) affinity ratio score is high for both attribute values. HYPERCL fails to reproduce these patterns, whereas NOAH closely matches them. The learned affinity matrices in Figure 3 further show that NOAHFIT captures this homophily by assigning higher affinities to same-value attribute pairs.

4.4 Ablation Study

To assess the contribution of the core-fringe node hierarchy in NOAH, we compare its performance with a variant, NOAH-CF, which omits this hierarchical structure. In NOAH-CF, each hyperedge is generated by sampling a seed node from the entire node set and attaching additional nodes directly, without distinguishing between core and fringe roles. As reported in Table 1, NOAH consistently outperforms NOAH-CF across all datasets, showing the importance of the core-fringe hierarchy in realistic hyperedge formation.

5 Conclusions

In this work, we proposed NOAH, a stochastic generative model for attributed hypergraphs that reproduces realistic interplay between structure and node attributes. By leveraging a two-level node hierarchy, core and fringe nodes, NOAH formulates hyperedge generation as the sequential attachment of nodes (first cores, then fringes), where attachment probabilities are governed by node attributes. We also introduced NOAHFIT, a parameter estimation algorithm that fits NOAH to a given hypergraph by estimating affinity matrices and seed core probabilities. Through extensive experiments on nine real-world hypergraphs across four diverse domains, we demonstrated that NOAH with NOAHFIT more accurately reproduces the structure-attribute interplay than eight existing hypergraph generative models across six metrics.

Acknowledgments

This work was supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2022-0-00871 / RS-2022-II220871, Development of AI Autonomy and Knowledge Enhancement for AI Agent Collaboration, 50%) (No. RS-2024-00457882, AI Research Hub Project, 40%) (RS-2019-II190075, Artificial Intelligence Graduate School Program (KAIST), 10%).

Contribution Statement

Jaewan Chun and Seokbum Yoon contributed equally to this work.