Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs

• URL: http://arxiv.org/abs/2112.06087v1
• Date: Sat, 11 Dec 2021 22:46:50 GMT
• Title: Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs
• Authors: Yitao Chen and Deepanshu Vasal
• Abstract summary: Belief propagation is a fundamental message-passing algorithm for numerous applications in machine learning. In this paper, we study the convergence behavior of generalized belief propagation algorithm on graphs with motifs.
• Score: 0.15229257192293197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Belief propagation is a fundamental message-passing algorithm for numerous applications in machine learning. It is known that belief propagation algorithm is exact on tree graphs. However, belief propagation is run on loopy graphs in most applications. So, understanding the behavior of belief propagation on loopy graphs has been a major topic for researchers in different areas. In this paper, we study the convergence behavior of generalized belief propagation algorithm on graphs with motifs (triangles, loops, etc.) We show under a certain initialization, generalized belief propagation converges to the global optimum of the Bethe free energy for ferromagnetic Ising models on graphs with motifs.

Related papers

• Causal Discovery over High-Dimensional Structured Hypothesis Spaces with Causal Graph Partitioning [0.742246975663779]
  Causal discovery allows us to infer mechanisms as sets of cause and effect relationships in a generalized way. We show our algorithm achieves comparable accuracy and a faster time to solution for biologically-tuned synthetic networks and networks up to $104$ variables.
  arXiv  Detail & Related papers  (2024-06-10T15:08:14Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  We propose fine-grained graph rationalization (FIG) for graph machine learning. Our idea is driven by the self-attention mechanism, which provides rich interactions between input nodes. Our experiments involve 7 real-world datasets, and the proposed FIG shows significant performance advantages compared to 13 baseline methods.
  arXiv  Detail & Related papers  (2023-12-13T02:56:26Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows.
  arXiv  Detail & Related papers  (2023-05-24T07:09:53Z)
• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  We investigate a previously overlooked phenomenon: in many cases, a densely connected, complementary graph can be found for the original graph. The denser graph may share nodes with the original graph, which offers a natural bridge for transferring selective, meaningful knowledge. We identify this setting as Graph Intersection-induced Transfer Learning (GITL), which is motivated by practical applications in e-commerce or academic co-authorship predictions.
  arXiv  Detail & Related papers  (2023-02-27T22:56:06Z)
• Beyond spectral gap (extended): The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. Current theory does not explain that collaboration enables larger learning rates than training alone. This paper aims to paint an accurate picture of sparsely-connected distributed optimization.
  arXiv  Detail & Related papers  (2023-01-05T16:53:38Z)
• Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. This paper aims to paint an accurate picture of sparsely-connected distributed optimization when workers share the same data distribution. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies.
  arXiv  Detail & Related papers  (2022-06-07T08:19:06Z)
• 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)
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning [65.15423587105472]
  We present a new generative and structured commonsense-reasoning task (and an associated dataset) of explanation graph generation for stance prediction. Specifically, given a belief and an argument, a model has to predict whether the argument supports or counters the belief and also generate a commonsense-augmented graph that serves as non-trivial, complete, and unambiguous explanation for the predicted stance. A significant 83% of our graphs contain external commonsense nodes with diverse structures and reasoning depths.
  arXiv  Detail & Related papers  (2021-04-15T17:51:36Z)
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks [39.370875358317946]
  Current graph neural networks (GNNs) lack generalizability with respect to scales (graph sizes, graph diameters, edge weights, etc.) when solving many graph analysis problems. We propose several extensions to address the issue. First, inspired by the dependency of the number of iteration of common graph theory algorithms on graph size, we learn to terminate the message passing process in GNNs adaptively according to the progress. Second, inspired by the fact that many graph theory algorithms are homogeneous with respect to graph weights, we introduce homogeneous transformation layers that are universal homogeneous function approximators, to convert ordinary G
  arXiv  Detail & Related papers  (2020-10-26T12:57:28Z)
• 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)
• Neural Enhanced Belief Propagation on Factor Graphs [85.61562052281688]
  A graphical model is a structured representation of locally dependent random variables. We first extend graph neural networks to factor graphs (FG-GNN) We then propose a new hybrid model that runs conjointly a FG-GNN with belief propagation.
  arXiv  Detail & Related papers  (2020-03-04T11:03:07Z)

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.