Attributed hypergraphs capture structure and attributes realistically, beyond binary links

Group interactions are everywhere in the real world. Researchers co-author papers, shoppers buy products together, students hang out in clusters between classes, and users on question-and-answer platforms gather around the same posts. Scientists represent these many-to-many relationships using hypergraphs, mathematical structures in which a single hyperedge can connect any number of entities at once. But a stubborn gap has separated the models used to simulate such systems from the data they are meant to mimic: nearly all existing hypergraph generators ignore the attributes of nodes, even though those attributes often determine which entities end up grouped together in the first place. A new study published in Knowledge and Information Systems closes that gap with a generative model called NoAH, which places node attributes at the heart of hyperedge formation and reproduces, with unprecedented fidelity, the way structure and attributes intertwine in real networks.

The work, led by Jaewan Chun, Seokbum Yoon, Minyoung Choe, Geon Lee, and Kijung Shin of the Kim Jaechul Graduate School of AI at KAIST, addresses a problem that has grown increasingly pressing as hypergraphs have become standard tools in clustering, classification, and anomaly detection. Real hypergraphs are not random assortments of nodes. They display high-degree hubs, densely overlapping hyperedges, and high transitivity, and previous generative models were built specifically to recreate those structural fingerprints. What they generally failed to capture is homophily, the pervasive tendency of similar nodes to interact. In a co-authorship hypergraph, for example, authors’ affiliations and fields of study shape who writes papers with whom; in contact networks, class or department membership shapes who meets whom. A generator blind to these attributes produces hypergraphs whose structure may look plausible but whose relationship between who the nodes are and how they connect is fundamentally wrong.

NoAH, short for Node Attribute based Hypergraph generator, tackles two obstacles simultaneously. The first is combinatorial: because a hyperedge can contain any number of nodes, the space of candidate hyperedges explodes exponentially with network size, making it intractable to assign a formation probability to every possibility. The second is structural realism: real hypergraphs tend to exhibit a hierarchy in which certain nodes consistently occupy central roles while others participate more peripherally. Chun and colleagues solve the first problem by modeling each hyperedge as a sequential attachment process, in which nodes join one at a time starting from a seed, with each attachment probability determined by attribute affinity. They solve the second with a simple but effective core-fringe partition, distinguishing nodes that act as the structural nucleus of each hyperedge from nodes that attach to that nucleus more peripherally.

Technically, the generative process unfolds in two steps. First, NoAH samples a seed core node according to a learned probability distribution and then attaches additional core nodes, with the inclusion probability of each candidate computed as the product of attribute affinity scores across all attributes. These affinities are stored in small two-by-two matrices for binary attributes, generalizing the Multiplicative Attribute Graph model that Kim and Leskovec introduced for pairwise networks more than a decade ago. Second, NoAH summarizes the core group’s attributes with a stochastic binary vector sampled from the group’s average attribute values, and then offers fringe nodes a chance to attach based on a second set of affinity matrices. Because a single set of global parameters, the seed distribution and affinity matrices, governs all hyperedges, the model remains both scalable and interpretable while still coupling hyperedges through shared mechanisms. The full generation procedure runs in time linear in the product of the number of hyperedges, nodes, and attributes, requiring only constant space per hyperedge.

The model is backed by theory as well as engineering. The authors prove that there exist configurations of attributes and parameters under which NoAH produces hypergraphs with power-law degree distributions, the heavy-tailed degree patterns that characterize most real-world systems. The proof proceeds by tuning the marginal attribute probabilities so that the probability mass of an attribute vector becomes proportional to a negative power of the node’s expected attachment probability; Stirling’s approximation then yields degree probabilities proportional to d raised to a negative exponent, for both core and fringe nodes. In other words, NoAH does not need degree distributions as inputs to reproduce them; realistic heavy tails emerge organically from attribute-driven attachment, which the authors highlight as evidence of the model’s expressive power.

To make NoAH useful in practice, the team developed NoAHFit, a parameter learning procedure that fits the model to an observed hypergraph. NoAHFit begins by identifying core nodes using the union of minimal hitting sets algorithm, which finds nodes that collectively intersect every hyperedge and therefore tend to occupy central structural positions. It then derives the likelihood of each hyperedge under the model, decomposed into a core-construction component and a fringe-attachment component, and updates the seed probabilities and affinity matrices to maximize the total likelihood. The loss function combines negative log-likelihood with mean squared error terms aligning expected degree and hyperedge-size distributions with those of the target data, so the fitted model reproduces both attribute-related and purely structural patterns. Fitted affinity matrices turn out to be directly interpretable: in the Amazon Music dataset, the learned matrices assign markedly higher affinity to pairs of reviewers sharing the same attribute value than to mismatched pairs, quantitatively capturing homophily.

The empirical evaluation is extensive. The authors compared NoAH against eight baseline generative models, including HyperCL, HyperPA, HyperFF, HyperLAP, hyper dK, THera, HyCoSBM, and HyRec, on nine real-world hypergraphs spanning four domains: academic citation and co-authorship networks such as Citeseer and Cora, face-to-face contact networks from a high school and a workplace, product review networks from Amazon Music and Yelp, and online question-and-answer communities from Stack Exchange. They assessed performance with six structure-attribute interplay metrics, including type-s affinity ratio scores that quantify whether hyperedges of a given size contain an unexpectedly high number of nodes sharing a label, hyperedge entropy and its higher-order variant that measure label homogeneity within hyperedges, and a newly proposed node homophily score that captures each node’s tendency to group with attribute-similar peers. Across all datasets and metrics, NoAH fitted by NoAHFit achieved the best overall average rank among the nine evaluated models, ranking first in four of the six metrics on average.

The study, which extends an earlier version presented at the IEEE International Conference on Data Mining in 2025, goes well beyond binary attributes. The authors generalize the affinity framework to categorical attributes by replacing the two-by-two matrices with category-by-category counterparts, and to continuous attributes by projecting values onto the unit interval with a learnable sigmoid mapping and interpolating continuously between the entries of the binary affinity matrices. On the PubMed co-citation hypergraph, whose nodes carry TF-IDF vectors of dimension 500, both the continuous version and a neural variant with a lightweight multilayer affinity function reproduced attribute coherence, measured by cosine similarity at the node and hyperedge levels, better than the strongest structure-focused baselines, with the neural variant achieving the smallest Wasserstein distances to the ground-truth distributions.

Perhaps the most conceptually striking extension concerns the case where no attributes exist at all. Many real hypergraphs come without any node metadata, yet the mechanisms they embody may still be attribute-like. The authors introduce NoAHFit-X, which treats node attributes as latent variables represented by a matrix of Bernoulli assignment probabilities, and jointly optimizes those probabilities together with the model parameters by replacing attribute lookups with their expectations under the latent representation. Two generation schemes then exploit the learned representation: NoAH-X samples attributes once globally, while NoAH-X+ resamples them afresh for every hyperedge, injecting diversity that better matches the distribution of pairwise hyperedge similarity observed in real data. In experiments on the review-domain datasets, NoAH-X+ outperformed all attribute-free baselines and often rivaled the version of NoAH given the true attributes, demonstrating that plausible attribute-driven structure can be learned even when nothing about the nodes is known in advance. A sensitivity analysis showed that the number of latent attributes can be tuned as a hyperparameter, and runtime scales nearly linearly with that dimension.

The implications reach across data mining and beyond. Realistic synthetic hypergraphs are valuable for anonymizing sensitive interaction data, stress-testing algorithms under controlled conditions, and running simulations in domains from epidemiology to recommendation systems. Because NoAH’s parameters are small matrices with direct interpretations as affinities between attribute values, analysts can read mechanisms straight out of a fitted model rather than treating a generator as a black box, a limitation that afflicts deep learning-based graph generators built on variational autoencoders, adversarial training, or diffusion. The authors note limitations that chart the road ahead: the two-level core-fringe hierarchy is fixed rather than multi-level, dependencies among hyperedges are captured only implicitly through shared parameters, and the current framework handles static, undirected, unweighted hypergraphs. Extending the model to temporal, heterogeneous, directed, and weighted group interactions is a natural next step. Still, with its combination of theoretical guarantees, near-linear scalability, best-in-class reproduction of structure-attribute interplay, and the ability to conjure meaningful attributes out of thin air, NoAH marks a substantial advance in the quest to generate group interaction data that behaves like the real thing.