Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis
We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary iterations of the Embedded Trees algorithm using any sequence of subgraphs converge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures provide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Efficient Higher-order Subgraph Attribution via Message Passing
Explaining graph neural networks (GNNs) has become more and more important recently. Higher-order interpretation schemes, such as GNN-LRP (layer-wise relevance propagation for GNN), emerged as powerful tools for unraveli…
Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
We propose an expressive and efficient approach that combines the strengths of two prominent extensions of Graph Neural Networks (GNNs): Subgraph GNNs and Structural Encodings (SEs). Our approach leverages walk-based cen…
Local Graph Clustering Beyond Cheeger's Inequality
Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. All previously known…
ClusteringGraph ClusteringMoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts
While graph neural networks (GNNs) have achieved great success in learning from graph-structured data, their reliance on local, pairwise message passing restricts their ability to capture complex, high-order subgraph pat…
Representation LearningNode ClassificationA dense subgraph based algorithm for compact salient image region detection
We present an algorithm for graph based saliency computation that utilizes the underlying dense subgraphs in finding visually salient regions in an image. To compute the salient regions, the model first obtains a salienc…
Few-Shot Semantic Segmentation