Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix

• URL: http://arxiv.org/abs/2507.06508v1
• Date: Wed, 09 Jul 2025 03:13:15 GMT
• Title: Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix
• Authors: Jintao Guo, Ying Zhou, Chao Li, Guixun Luo,
• Abstract summary: We propose the Noisy Adjacency Matrix (NAM), which combines differential privacy with the adjacency matrix of the graph.<n>Based on NAM, we designed five algorithms to count three types of subgraphs: triangles, quadrangles, and 2-stars.<n>We implement edge-LDP for noisy data via a confidence interval-inspired method, providing DP guarantees on randomized data.
• Score: 12.264804926096593
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When analyzing connection patterns within graphs, subgraph counting serves as an effective and fundamental approach. Edge-local differential privacy (edge-LDP) and shuffle model have been employed to achieve subgraph counting under a privacy-preserving situation. Existing algorithms are plagued by high time complexity, excessive download costs, low accuracy, or dependence on trusted third parties. To address the aforementioned challenges, we propose the Noisy Adjacency Matrix (NAM), which combines differential privacy with the adjacency matrix of the graph. NAM offers strong versatility and scalability, making it applicable to a wider range of DP variants, DP mechanisms, and graph types. Based on NAM, we designed five algorithms (TriOR, TriTR, TriMTR, QuaTR, and 2STAR) to count three types of subgraphs: triangles, quadrangles, and 2-stars. Theoretical and experimental results demonstrate that in triangle counting, TriOR maximizes accuracy with reduced time complexity among one-round algorithms, TriTR achieves optimal accuracy, TriMTR achieves the highest accuracy under low download costs, and QuaTR stands as the first quadrangle counting algorithm under pure edge-LDP. We implement edge-LDP for noisy data via a confidence interval-inspired method, providing DP guarantees on randomized data. Our 2STAR algorithm achieves the highest accuracy in 2-star counting and can be derived as a byproduct of two-round triangle or quadrangle counting algorithms, enabling efficient joint estimation of triangle, quadrangle, and 2-star counts within two query rounds.

Related papers

• SEED: A Simple and Effective 3D DETR in Point Clouds [72.74016394325675]
  We argue that the main challenges are challenging due to the high sparsity and uneven distribution of point clouds. We propose a simple and effective 3D DETR method (SEED) for detecting 3D objects from point clouds.
  arXiv  Detail & Related papers  (2024-07-15T14:21:07Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  This paper studies density-based clustering of point sets.<n>It unifies the different variants of density peaks clustering into a single framework, PECANN.<n>We implement five clustering algorithms with PECANN and evaluate them on synthetic and real-world datasets with up to 1.28 million points and up to 1024 dimensions on a 30-core machine with two-way hyper-threading.
  arXiv  Detail & Related papers  (2023-12-06T22:43:50Z)
• KECOR: Kernel Coding Rate Maximization for Active 3D Object Detection [48.66703222700795]
  We resort to a novel kernel strategy to identify the most informative point clouds to acquire labels. To accommodate both one-stage (i.e., SECOND) and two-stage detectors, we incorporate the classification entropy tangent and well trade-off between detection performance and the total number of bounding boxes selected for annotation. Our results show that approximately 44% box-level annotation costs and 26% computational time are reduced compared to the state-of-the-art method.
  arXiv  Detail & Related papers  (2023-07-16T04:27:03Z)
• RoCNet: 3D Robust Registration of Point-Clouds using Deep Learning [5.494111035517598]
  This paper introduces a new method for 3D point cloud registration based on deep learning. We conduct experiments on the ModelNet40 dataset, and our proposed architecture shows very promising results.
  arXiv  Detail & Related papers  (2023-03-14T15:07:51Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K. We express this algorithm within the setting of discrete Morse theory, which considerably reduces the number of input simplices to consider. We also introduce a stratification approach to the problem, that we call "sandwiching"
  arXiv  Detail & Related papers  (2022-06-27T10:54:24Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D Edge Alignment [85.32080531133799]
  This paper reviews the classical problem of free-form curve registration and applies it to an efficient RGBD visual odometry system called Canny-VO. Two replacements for the distance transformation commonly used in edge registration are proposed: Approximate Nearest Neighbour Fields and Oriented Nearest Neighbour Fields. 3D2D edge alignment benefits from these alternative formulations in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2020-12-15T11:42:17Z)
• NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
  A novel framework is proposed for cellular offloading with the aid of multiple unmanned aerial vehicles (UAVs) Non-orthogonal multiple access (NOMA) technique is employed at each UAV to further improve the spectrum efficiency of the wireless network. A mutual deep Q-network (MDQN) algorithm is proposed to jointly determine the optimal 3D trajectory and power allocation of UAVs.
  arXiv  Detail & Related papers  (2020-10-18T17:38:48Z)
• TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
  First fast and robust certifiable algorithm for the registration of 3D points in the presence of large amounts of outliers. Second fast and robust certifiable translation, named TEASER++, uses graduated non-componentity to solve a large subproblem.
  arXiv  Detail & Related papers  (2020-01-21T18:56:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.