|
Sampling On Metric Graphs |
Soundness: 3: good
Presentation: 2: fair
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
This paper investigated the practical implementation of sampling in metric graphs. It seems that the authors generalise the Euler-Maruyama discretization of Langevin diffusion for continuous distribution. They provide a theoretical guarantee that the jump distribution generated by their proposed algorithm asymptotically converges to the target distribution. Then they provide a parallelizable version of the proposed algorithm to get fast and memory-saving implementation.
1. The problem investigated in this paper seems to be novel, having theoretical and practical value.
2. This paper has a certain mathematical depth.
1. There are some claims that they did not explain clearly. For example, in Line 133-134, they claimed that the results of the star graphs researched in this paper can extend to general graphs. They did not explain how to extend.
2. The presentation should be improved. The key section “Brownian Motion on Metric Graphs” should be more detailed, especially on the boundary conditions, which is not friendly to the readers.
The theoretical results seems to be valid for all target distribution $b_v$, which means they did not need to make any assumption on $b_v$. This is different from Unadjusted Langevin Algorithm for sampling in continuous distribution, which usually make assumptions on smoothness and isoperimetry properties of potential function. |
Fully human-written |
|
Sampling On Metric Graphs |
Soundness: 2: fair
Presentation: 2: fair
Contribution: 3: good
Rating: 8: accept, good paper
Confidence: 2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
This paper tackles sampling on metric graphs by introducing a time-step–splitting Euler–Maruyama (EM) scheme to simulate Brownian motion, and hence Langevin diffusions, on metric graphs. It proves that the number of vertex crossings is finite with high probability and that exit probabilities of the simulation converge to the SDE's vertex-edge jump probabilities as the step size tends to zero. The authors also present highly parallel, memory-aware implementations, and experiments show the method outperforms a finite-volume baseline in accuracy and speed.
1. The paper introduces a novel and interesting time-step–splitting EM scheme for Brownian/Langevin on metric graphs, with guarantees of finite splits (w.h.p.) and exit-probability convergence as step size goes to 0.
2. This method is efficient and scalable with memory-aware, highly parallel GPU implementation that showing strong speedups and accuracy gains over a finite-volume baseline with empirical validation
Results are interesting but restricted to star graphs and applicability to general metric graphs is neither analyzed nor empirically validated.
Beyond finite splits and exit-probability consistency, there are no non-asymptotic weak/strong error bounds or sampling error rates.
Minors:
- "Sampling On Metric Graphs" should be "Sampling on Metric Graphs"
- Line 405 the normalizing constant B if given by -> the normalizing constant B is given by
Q1: What's the non-asymptotic convergence rate?
Q2: What are the challenges for non-star graphs, and can you show experiments on non-star graphs? |
Lightly AI-edited |
|
Sampling On Metric Graphs |
Soundness: 3: good
Presentation: 3: good
Contribution: 1: poor
Rating: 2: reject
Confidence: 4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. |
The paper touches on a very interesting problem with solid research dealing with differential equations posed on metric graphs. Nevertheless, I feel that ICLR by its core definition is the wrong venue for this research and it is better suited for numerical analysis journal/UQ journal.
I think the paper is well written and deals with an interesting problem but I do not see it as being particularly focused on learning algorithms and doubt its suitability for ICLR.
I feel that the poor performance of the FVM needs to be discussed and these methods usually perform very well on metric graphs but have, of course, other weaknesses. The formatting of all the references is terrible please fix the bib-entries.
- Please explain how changing the orientation of an edge does not change the inward derivative?
- In (1) and (2) the subscript e is not explained. It is clearly the restriction onto the edge but please be precise.
- I am a bit suspicious about the FVM scheme as it seems to completely fail for the Fokker Planck equation, any reasons why? There are existing FVM schemes for quantum graphs to be found on Github that seem to do well for other PDEs. |
Fully human-written |
|
Sampling On Metric Graphs |
Soundness: 3: good
Presentation: 2: fair
Contribution: 2: fair
Rating: 4: marginally below the acceptance threshold
Confidence: 2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked. |
This paper focuses on the numerical simulation problem of Brownian motion and Langevin diffusions on metric graphs and proposes a timestep splitting Euler-Maruyama-based discretization method.
It handles vertex crossings by recursively splitting the simulation step, moving the particle to the vertex, and sampling a new edge. Theoretical analysis prove the algorithm terminates finitely and converges to correct vertex-edge jump probabilities as the timestep decreases.
A custom, memory-aware CUDA kernel is implemented for fast, parallelized execution on GPUs.
Numerical experiments on a 5-edge star graph with linear and quadratic potentials demonstrated the effectiveness of the proposed method.
The reported results show significant speedups and higher accuracy in recovering steady-state densities compared to FVM.
1. Though the theory of function space and Brownian motion on metric graphs is well-established, practical simulation algorithm is non-existent. This paper provides a concrete and practical method to simulate this process, which is a novel contribution to the field and will be beneficial for future work in this field.
2. Theoretical analysis is thorough and insightful. Theorem 2 & 3 addresses the concern of an infinite loop due to repeated vertex crossings within a single timestep, which is crucial for the practicality of the algorithm. Corollary 1 links the algorithm's behavior to the underlying SDE, proving that the simulated jump probabilities converge to the correct theoretical values $b_v$. These theoretical analysis provide a solid ground for the proposed method.
3. The CUDA kernel implementation achieves a massive speedup over a simple Pytorch implementation. This engineering effort significantly elevates the paper's utility for practitioners and researchers needing large-scale simulations.
1. Experimental Evaluation is limited critically. The entire numerical evaluation is conducted on a synthetic star graph with only 5 edges. Metric graphs are powerful precisely for modeling networks with complex cycles, multiple vertices, and varied edge lengths. Demonstrating performance only on a star graph provides almost no evidence that the algorithm works on metric graphs in general. Besides, this paper does not demonstrate the effectiveness of algorithm on a real-world problem or dataset, which undermines its potential impact. The performance gap versus the FVM baseline, while impressive, is less meaningful without a real-world context.
2. While Theorem 2 guarantees finite runtime, empirical analysis of the computation cost introduced by vertex crossings is missed. How does the average number of splits M scale with $\delta t$, the drift magnitude, and the graph complexity? This is an important practical consideration that is left unexplored.
1. Can you provide theoretical or experimental analysis to show that Algorithm 1 works effectively on a non-star metric graph, for instance, a graph containing a cycle or multiple interconnected vertices?
2. Can you provide experimental results on a concrete real-world dataset?
3. This paper focuses exclusively on standard boundary conditions, which can be further improved by discussing limitations of the current algorithm regarding these more general conditions or outlined a path for future extension. |
Fully AI-generated |