Convex Combination Belief Propagation Algorithms

• URL: http://arxiv.org/abs/2105.12815v1
• Date: Wed, 26 May 2021 20:06:57 GMT
• Title: Convex Combination Belief Propagation Algorithms
• Authors: Anna Grim and Pedro Felzenszwalb
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce new message passing algorithms for inference with graphical models. The standard min-sum and sum-product belief propagation algorithms are guaranteed to converge when the graph is tree-structured, but may not converge and can be sensitive to the initialization when the graph contains cycles. This paper describes modifications to the standard belief propagation algorithms that are guaranteed to converge to a unique solution regardless of the topology of the graph.

Related papers

• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Convergence Guarantees for the DeepWalk Embedding on Block Models [9.898607871253775]
  We show how to use the DeepWalk algorithm on graphs obtained from the Block Model (SBM) Despite being simplistic, the SBM has proved to be a classic model for analyzing algorithms on large graphs.
  arXiv  Detail & Related papers  (2024-10-26T18:35:11Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  We introduce an algorithm for graph matching based on the proximal operator, referred to as differentiable proximal graph matching (DPGM) The whole algorithm can be considered as a differentiable map from the graph affinity matrix to the prediction of node correspondence. Numerical experiments show that PGM outperforms existing graph matching algorithms on diverse datasets.
  arXiv  Detail & Related papers  (2024-05-26T08:17:13Z)
• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
  arXiv  Detail & Related papers  (2024-04-18T15:31:13Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues [6.094384342913063]
  We derive almost linear-time algorithms to achieve $O(sqrtlogn)$-approximation and Cheeger-type guarantee for directed edge expansion. This provides a primal-dual flow-based framework to obtain the best known algorithms for directed graph partitioning.
  arXiv  Detail & Related papers  (2023-06-15T13:41:17Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Random Feature Approximation for Online Nonlinear Graph Topology Identification [7.992550355579789]
  We propose a kernel-based algorithm for graph topology estimation. We exploit the fact that the real-world networks often exhibit sparse topologies. The experiments conducted on real and synthetic data show that the proposed method outperforms its competitors.
  arXiv  Detail & Related papers  (2021-10-19T12:48:12Z)
• 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)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.