Acyclic Graph Pattern Counting under Local Differential Privacy

• URL: http://arxiv.org/abs/2603.19671v1
• Date: Fri, 20 Mar 2026 06:12:12 GMT
• Title: Acyclic Graph Pattern Counting under Local Differential Privacy
• Abstract summary: We present the first general solution for counting arbitrary acyclic patterns under local differential privacy (LDP)<n>We tackle two fundamental challenges: generalizing pattern construction from distributed data and eliminating node duplication during the construction.<n> Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to $46$-$2600times$ improvement in utility and $300$-$650times$ reduction in communication cost compared to the baseline methods.
• Score: 6.729442409066558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph pattern counting serves as a cornerstone of network analysis with extensive real-world applications. Its integration with local differential privacy (LDP) has gained growing attention for protecting sensitive graph information in decentralized settings. However, existing LDP frameworks are largely ad hoc, offering solutions only for specific patterns such as triangles and stars. A general mechanism for counting arbitrary graph patterns, even for the subclass of acyclic patterns, has remained an open problem. To fill this gap, we present the first general solution for counting arbitrary acyclic patterns under LDP. We identify and tackle two fundamental challenges: generalizing pattern construction from distributed data and eliminating node duplication during the construction. To address the first challenge, we propose an LDP-tailored recursive subpattern counting framework that incrementally builds patterns across multiple communication rounds. For the second challenge, we apply a random marking technique that restricts each node to a unique position in the pattern during computation. Our mechanism achieves strong utility guarantees: for any acyclic graph pattern with $k$ edges, we achieve an additive error of $\tilde{O}(\sqrt{N}d(G)^k)$, where $N$ is the number of nodes and $d(G)$ is the maximum degree of the input graph $G$. Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to $46$-$2600\times$ improvement in utility and $300$-$650\times$ reduction in communication cost compared to the baseline methods.

Related papers

• Graph-Based Fraud Detection with Dual-Path Graph Filtering [52.459703746017624]
  Fraud detection on graph data requires distinguishing between different types of nodes.<n>This paper proposes a Graph-Based Fraud Detection Model with Dual-Path Graph Filtering.<n>Experiments on four real-world financial fraud detection datasets demonstrate the effectiveness of our proposed method.
  arXiv  Detail & Related papers  (2026-04-14T20:46:36Z)
• Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
  Hirschberg's algorithm reduces the space complexity for the longest common subsequence problem from $O(N2)$ to $O(N)$ via a midpoint bisection on a grid dynamic program (DP)<n>We show that the underlying idea generalizes to a broad class of dynamic programs with local dependencies on directed acyclic graphs (DP DAGs)<n>We show that an $()$ space term is unavoidable in forward single-pass models and discuss conjectured $sqrtT$-type barriers in streaming settings.
  arXiv  Detail & Related papers  (2025-12-10T22:26:22Z)
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds [8.781923502647055]
  We develop new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings.<n>We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an ErdHos-R'enyi graph $mathbfG=mathbfG(k,p)$ in the regime $p in mathcalO((log (k)/k)1/2)
  arXiv  Detail & Related papers  (2025-09-08T17:13:28Z)
• Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation [46.17999216122895]
  We propose a novel DGC method termed underlinetextbfComplementary underlinetextbfMulti-underlinetextbfView.<n> CMV-ND preprocesses graph structural information into multiple views in a complete but non-redundant manner.<n> Experimental results on six widely used graph datasets demonstrate that CMV-ND significantly improves the performance of various methods.
  arXiv  Detail & Related papers  (2025-07-09T13:42:43Z)
• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  We introduce Generative Graph Pattern Machine (G$2$PM), a generative Transformer pre-training framework for graphs.<n>G$2$PM represents graph instances (nodes, edges, or entire graphs) as sequences of substructures.<n>It employs generative pre-training over the sequences to learn generalizable and transferable representations.
  arXiv  Detail & Related papers  (2025-05-22T02:16:34Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
  We show that the adjacency of a large random Kronecker graph can be decomposed. We propose a denoise-and-solve'' approach to infer the key graph parameters.
  arXiv  Detail & Related papers  (2023-06-14T13:09:38Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Graph Generation with $K^2$-trees [13.281380233427287]
  We introduce a novel graph generation method leveraging $K2$-tree representation. We also present a sequential $K2$-treerepresentation that incorporates pruning, flattening, and tokenization processes. We extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.
  arXiv  Detail & Related papers  (2023-05-30T15:36:37Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)

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.