Faster hypergraph classification with pattern overlap and frequency details
Overlap-Aware Sub-hypergraph Pattern Frequencies for Hypergraph-Level Classification
Machine Learning
Summary
Classifying entire hypergraphs, which are complex networks with varied node and edge counts, requires a consistent way to describe them. Previous methods only noted if certain sub-patterns appeared, missing how much those patterns overlapped or how common they were within each hypergraph. The authors present a method that includes overlap sizes and relative frequencies of these patterns, improving classification accuracy. They tested their approach on multiple datasets, showing notable improvements over prior methods.
What this means in practice
- •For social network analysts: Improve classification of user interaction patterns by capturing overlap and frequency in social hypergraphs like Twitter friend networks.
- •For gaming data engineers: Enhance player classification in gaming networks by utilizing detailed pattern frequency and overlap features.
Authors
Nafiul Hasan Anik, Nazira Jesmin Lina, Md Tanvir Alam, Md. Fahim Arefin
Abstract
Classifying whole hypergraphs requires a fixed-length description of inputs whose numbers of vertices and hyperedges vary. Frequent sub-hypergraph patterns provide such a description, but previous work records only whether each pattern is present, which loses two kinds of information: how large the overlap between two hyperedges is, and how much of a hypergraph each pattern makes up. We extend frequent sub-hypergraph mining with overlap labels, the binned intersection size of two pattern hyperedges inherited from the target hypergraph, and represent each hypergraph by the relative frequency of each mined pattern. The vocabulary is mined from training hypergraphs only and then frozen, and validation and test hypergraphs are matched against it. A support rule that depends on pattern size keeps the vocabulary small. On the six hypergraph-classification datasets of DHG-Bench, with a single configuration chosen on validation scores, the method has a higher mean Macro-F1 than the best published mean on five datasets, by 18.67 points on Twitter-Friend and 10.02 points on Steam-Player; on RHG-3 it is 0.21 points lower. Ablations show that on Steam-Player and Twitter-Friend, replacing relative frequencies with presence lowers Macro-F1 by about 18 points, and that removing overlap labels lowers it by 4 to 9 points.