Qi Luo

With the growing global emphasis on data privacy protection, particularly the enforcement of the “right to be forgotten” under the GDPR, effectively deleting private information from models has become an urgent challenge. Graph-structured data presents a particularly challenging unlearning scenario due to its non-Euclidean nature and strong relational dependencies, which are prevalent in real-world applications such as social and recommendation systems. To address this issue, graph unlearning has been introduced to eliminate the influence of deleted data on models while preserving their overall performance. The effectiveness of graph unlearning is typically evaluated by three key metrics: model performance, unlearning efficiency, and robustness against membership inference attacks, which together determine the overall quality of an unlearning method. Existing graph unlearning methods fall into exact and approximate regimes. Most studies focus on edge/node-level unlearning, and existing attempts at feature-level unlearning remain limited. Exact unlearning methods that adopt the SISA partition and retraining paradigm may inadvertently reintroduce the features intended to be unlearned during the aggregation phase, thereby leading to incomplete unlearning. Approximate methods, on the other hand, often incur excessive information loss in feature-level removal, which degrades predictive accuracy. Accordingly, we propose a graph unlearning framework specifically designed for feature-level unlearning, consisting of two main stages. In the first stage, we zero out the features of the unlearned nodes at each layer to block their propagation through the GNN, thereby reducing their influence on neighboring node representations. In the second stage, we induce misclassification of the unlearned nodes to progressively degrade model representations and learned knowledge associated with them, enabling more thorough feature-level unlearning. Experiments on multiple graph datasets and models demonstrate that our method achieves favorable overall unlearning performance in most settings, offering a balanced trade-off between accuracy, unlearning efficiency, and unlearning effectiveness.

Graph unlearning aims to provably remove some training data from graph neural networks (GNNs) while eliminating their impact on model predictions. Although retraining the GNNs from scratch is a direct and legitimate solution, it entails substantial computational resources. To address this issue, graph unlearning methods have been proposed in the domain of graph data. However, applying existing graph unlearning methods directly to hypergraph data affects model utility. Specifically, the graph unlearning methods severely damage the higher-order structural information of hypergraphs and fail to remove all the information that needs to be unlearned. In this paper, we propose Hyperedge Size-Based Core-Sharing Decomposition, a novel hypergraph unlearning framework tailored to the structural characteristics of hypergraph data. Its contributions include a subgraph partitioning method specific to hypergraphs and an aggregation method based on node coverage. We conduct extensive experiments on seven real-world hypergraph datasets to demonstrate the unlearning efficiency and model utility. Compared to the baseline methods, our approach achieves up to 5% higher accuracy and reduces the average unlearning time by 28%. Furthermore, our node-coverage-based aggregation approach achieves up to 6% higher accuracy.

A hypergraph is a mathematical structure capable of representing complex relationships among multiple entities, with widespread applications. However, as the size of hypergraphs continues to grow, their analysis and processing become increasingly challenging. Therefore, how to effectively process large hypergraphs to enable efficient analysis with limited computational resources has become an important research problem. In this article, we propose a method called hypergraph adaptive sampling (HAS), a framework that achieves adaptive batch sampling of hyperedges. This framework adaptively adjusts the sampling probability of hyperedges to ensure that the sampled subhypergraph closely resembles the original hypergraph in terms of structural characteristics, effectively reducing information loss caused by sampling. Extensive experiments are conducted on six public datasets to evaluate, and the results demonstrate that HAS outperforms other algorithms in preserving hypergraph properties. Using our hypergraph sampling method, even when only 20% of the edges of the original image are sampled, the sampled subhypergraph still maintains a small structural error compared to the original hypergraph. The KL divergence of the subhypergraph degree distribution is 0.09, which is 4.1${\boldsymbol\times}$ better than the baseline. Last, the efficiency and adaptability of HAS make it applicable not only to hypergraph analysis but also for providing a general and scalable solution for efficiently processing large-scale hypergraph data.

Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual-layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large-sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.

Graphs are a commonly used model in data mining to represent complex relationships, with nodes representing entities and edges representing relationships. However, graphs have limitations in modeling high-order relationships. In contrast, hypergraphs offer a more versatile representation, allowing edges to join any number of nodes. This capability empowers hypergraphs to model multiple relationships and capture high-order information present in real-world applications. We focus on the problem of local clustering in hypergraphs, which computes a cluster near a given seed node. Although extensively explored in the context of graphs, this problem has received less attention for hypergraphs. Current methods often directly extend graph-based local clustering to hypergraphs, overlooking their inherent high-order features and resulting in low-quality local clusters. To address this, we propose an effective hypergraph local clustering model. This model introduces a novel conductance measurement that leverages the high-order properties of hypergraphs to assess cluster quality. Based on this new definition of hypergraph conductance, we propose a greedy algorithm to find local clusters in real time. Experimental evaluations and case studies on real-world datasets demonstrate the effectiveness of the proposed methods.

Hypergraphs are applicable to various domains such as social contagion, online groups, and protein structures due to their effective modeling of multivariate relationships. However, the increasing size of hypergraphs has led to high computation costs, necessitating efficient acceleration strategies. Existing approaches often require consideration of algorithm-specific issues, making them difficult to directly apply to arbitrary hypergraph processing tasks. In this paper, we propose a compression-array acceleration strategy involving hypergraph reordering to improve memory access efficiency, which can be applied to various hypergraph processing tasks without considering the algorithm itself. We introduce a new metric called closeness to optimize the ordering of vertices and hyperedges in the one-dimensional array representation. Moreover, we present an $\frac{1}{2w}$ -approximation algorithm to obtain the optimal ordering of vertices and hyperedges. We also develop an efficient update mechanism for dynamic hypergraphs. Our extensive experiments demonstrate significant improvements in hypergraph processing performance, reduced cache misses, and reduced memory footprint. Furthermore, our method can be integrated into existing hypergraph processing frameworks, such as Hygra, to enhance their performance.