Compact Conformal Subgraphs

• URL: http://arxiv.org/abs/2602.07530v1
• Date: Sat, 07 Feb 2026 12:55:54 GMT
• Title: Compact Conformal Subgraphs
• Abstract summary: "graph-based conformal compression" is a framework for constructing compact subgraphs.<n>We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs.
• Score: 19.72191566715581
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planning, or sequential recommendation. We introduce "graph-based conformal compression", a framework for constructing compact subgraphs that preserve statistical validity while reducing structural complexity. We formulate compression as selecting a smallest subgraph capturing a prescribed fraction of the probability mass, and reduce to a weighted version of densest $k$-subgraphs in hypergraphs, in the regime where the subgraph has a large fraction of edges. We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs. Crucially, we prove that our relaxation satisfies a monotonicity property, derived from a connection to parametric minimum cuts, which guarantees the nestedness required for valid conformal guarantees. Our results on the one hand bridge efficient conformal prediction with combinatorial graph compression via monotonicity, to provide rigorous guarantees on both statistical validity, and compression or size. On the other hand, they also highlight an algorithmic regime, distinct from classical densest-$k$-subgraph hardness settings, where the problem can be approximated efficiently. We finally validate our algorithmic approach via simulations for trip planning and navigation, and compare to natural baselines.

Related papers

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• Learning Affine Correspondences by Integrating Geometric Constraints [30.695253062973784]
  We present a new pipeline designed for extracting accurate affine correspondences by integrating dense matching and geometric constraints.<n>Specifically, a novel extraction framework is introduced, with the aid of dense matching and a novel keypoint scale and orientation estimator.<n>The experimental show that the accuracy and robustness of our method outperform the existing ones in image matching tasks.
  arXiv  Detail & Related papers  (2025-04-07T08:44:50Z)
• Epistemic Uncertainty in Conformal Scores: A Unified Approach [2.449909275410288]
  Conformal prediction methods create prediction bands with distribution-free guarantees but do not explicitly capture uncertainty.<n>We introduce $texttEPICSCORE$, a model-agnostic approach that enhances any conformal score by explicitly integrating uncertainty.<n>$texttEPICSCORE$ adaptively expands predictive intervals in regions with limited data while maintaining compact intervals where data is abundant.
  arXiv  Detail & Related papers  (2025-02-10T19:42:54Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  We propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction.<n>Design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps.<n>We achieve promoted efficiency and leading performances on five large-scale benchmarks.
  arXiv  Detail & Related papers  (2024-03-15T12:00:12Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology [10.922787879808576]
  Subgraph isomorphism, also known as subgraph matching, is typically regarded as an NP-complete problem.<n>We propose a method for identifying the node correspondence between a subgraph and a full graph in the inexact case without node labels.
  arXiv  Detail & Related papers  (2022-09-15T02:45:05Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
  arXiv  Detail & Related papers  (2021-07-05T11:41:16Z)
• Convex Combination Belief Propagation Algorithms [0.0]
  We introduce new message passing algorithms for inference with graphical models. Standard min-sum and sum-product belief propagation algorithms are guaranteed to converge when the graph is tree-structured.
  arXiv  Detail & Related papers  (2021-05-26T20:06:57Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• On Compression Principle and Bayesian Optimization for Neural Networks [0.0]
  We propose a compression principle that states that an optimal predictive model is the one that minimizes a total compressed message length of all data and model definition while guarantees decodability. We show that dropout can be used for a continuous dimensionality reduction that allows to find optimal network dimensions as required by the compression principle.
  arXiv  Detail & Related papers  (2020-06-23T03:23:47Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)

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.