acceptodds
Under review as a conference paper at ICLR 2027

How Do Stochastic Graph Flows Estimate Effective Geometry?

Abstract

Observed graphs are often noisy proxies for the geometry that a learning system should trust, yet continuous graph models often operate over a prescribed geometry without jointly adapting it and quantifying its uncertainty. We introduce *Stochastic Graph Flows* (SGFs), an energy-consistent framework that unifies adaptive graph geometry, representation dynamics, and model-induced geometry uncertainty. Positive edge conductances are eliminated exactly from an entropy-regularized joint energy, yielding a bounded robust energy whose gradient generates the same state-dependent Laplacian that drives the flow. Thus, geometry adaptation and representation dynamics are governed by a single scalar energy within a unified construction. At positive temperature, this energy further induces a unique Gibbs law over representation states, whose pushforward through the conductance map yields an effective mean geometry and edge-level uncertainty on the observed support. We establish free-energy dissipation and Gibbs invariance, derive conditional stability guarantees for the effective operator and its spectral subspace, and explicitly separate modeling, temperature, discretization, mixing, and sampling errors. Experiments on synthetic and real graphs support the adaptive-geometry mechanism and highlight stochasticity as a principled source of geometry uncertainty, alongside modest improvements in point estimation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
adaptive graph geometry, Riemannian Langevin dynamics, stochastic differential equations on manifolds, stochastic graph dynamics, uncertainty quantification, spectral graph theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_zQr7OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Stochastic Graph Flows (SGF), using variational elimination of edge conductance weights to unify adaptive graph geometry, representation dynamics, and geometric uncertainty within a common energy framework. It derives free-energy dissipation and Gibbs invariance, as well as conditional stability results for effective operators and spectral subspaces, and provides a finite-step estimation-error decomposition. Experiments on synthetic and real graphs cover reference-geometry recovery, edge-addition detection, linear-probe robustness, mechanism ablations, and comparisons with multiple baselines. The results support the adaptive-geometry mechanism, although point-estimation gains are generally modest and the effect of positive temperature varies across datasets. The scope of the theoretical guarantees and the interpretation of finite-chain diagnostics are central to assessing the contribution.

Critical strengths

(1) A unified methodological design. By variationally eliminating positive edge-conductance weights, the paper uses a common energy framework to determine adaptive geometry and representation flow, while the stochastic state distribution induces an average geometry and edge-level uncertainty. (2) A relatively broad theoretical and empirical evaluation. The paper provides conditional stability results and a finite-step error decomposition, and evaluates reference-geometry recovery, edge-addition detection, linear-probe performance, mechanism ablations, and multiple baselines on synthetic and real graphs. It also acknowledges that positive-temperature benefits are not universal.

Critical weaknesses

(1) The robustness evidence is concentrated on random edge additions, and gains from positive temperature are modest and dataset-dependent. These results do not by themselves establish robustness to other graph perturbations or across a broad range of application settings. The scope of the robustness claims should be stated accordingly. (2) The interpretation of uncertainty and finite-chain estimates needs careful qualification. The stability results rely on explicit assumptions about representability, concentration, and chain properties; local consistency diagnostics for a finite chain are not proof of equilibrium convergence. Model-induced edge-weight variance should not automatically be interpreted as a calibrated confidence measure.

Questions for authors

(1) The paper reports relative Laplacian/operator errors and AUROC for edge-addition detection. For Cora and Roman-Empire, the uncorrupted public graph is used as a reference, rather than asserted to be the true latent geometry. What conclusions about geometry recovery do these metrics support, and how should the errors be interpreted on real datasets where latent ground-truth geometry is unavailable? (2) Given the modest and dataset-dependent effect of positive temperature, can the authors clarify the separate contributions of the main components? Since the robustness evaluation primarily considers random edge additions, how should the claims be scoped with respect to edge deletion, rewiring, or more structured graph perturbations?

Reviewer_6fUfOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Stochastic Graph Flows (SGFs), an energy-consistent framework that unifies adaptive graph geometry, representation dynamics, and model-induced geometry uncertainty. Exact elimination of positive edge conductances yields a reduced energy that governs representation dynamics through a state-dependent Laplacian. At positive temperature, the associated Gibbs law induces a distribution over conductances, providing an effective mean geometry and edge-level uncertainty on the observed support. The authors establish free-energy dissipation and Gibbs invariance, provide conditional operator and spectral-subspace stability guarantees, and distinguish modeling, temperature, discretization, mixing, and sampling errors. Experiments support the adaptive-geometry mechanism, with modest, dataset-dependent gains from stochasticity in point estimation. The paper addresses a meaningful problem in learning from noisy graphs.

Critical strengths
  1. The mathematical modeling exhibits good internal consistency.
  2. The theoretical analysis is relatively complete and provides corresponding constraints.
  3. Experimental design and problem matching are effective.
Critical weaknesses

Some theoretical and experimental verifications are insufficient and need improvement.

Questions for authors
  1. The authors define $ u_{ij}=\operatorname{Var}{H\sim\pi\tau}!\left[c^\star_{ij}(H)\right] $ as model-induced edge-level geometry uncertainty. Although the paper reports the incremental contribution of the variance term to corrupted-edge detection AUROC, it remains unclear whether this variance provides information beyond the mean conductance. For example, among edges with similar mean conductance, does higher variance correspond to a higher corruption rate? Is this relationship stable across temperatures, sampling lengths, and corruption types?

  2. Does a strong Stiefel constraint overly restrict graph representation? D.8 shows that the representation width in the paper's experiments was fixed at p=3. Is this suitable for real graphs with complex semantic structures? Can the authors add experimental results with different dimensions p for analysis?

Reviewer_bBxDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes Stochastic Graph Flows (SGF), a method which jointly adapts edge weights and node representations when the observed graph may be noisy. The initially observed edge set is kept fixed. At each step, SGF updates node representations and uses them to update the graph. Observed edges are downweighted using a Gaussian kernel based on the distance between the embeddings of the endpoints. The updated edge weights define a new Laplacian, which is used to update the node representations.

Both updates are derived from the same objective. Minimizing it over edge weights gives the Gaussian reweighting rule and differentiating the objective wr.t. node embeddings gives the Laplacian update. The paper introduces a temperature parameter which controls noise in the embedding update. With τ=0\tau=0 the algorithm is deterministic, while at positive temperature, Brownian noise is added to the representation dynamics. The continuous process has a Gibbs equilibrium over representations. Using the conductance formula on samples from the distribution gives a mean weight and variance for each observed edge. The paper calls these the effective mean geometry and model-induced geometric uncertainty.

The theoretical results show the invariant Gibbs distribution for the continuous-time process, and that under some assumptions, the average learned Laplacian is close to the target. The experiments are performed on synthetic graphs, Cora and Roman-Empire. The experiment adds random edges and evaluates methods on graph recovery, corrupted edge detection and representation quality. Most of the improvement is obtained by the deterministic τ=0\tau=0 version, while in some datasets there is small additional improvement from the stochastic version.

Critical strengths
  • The problem setting is interesting. Graph learning methods often assume the observed graph is correct even though some of the edges may be unreliable. Updating the weights together with the representations seems natural.
  • The edge reweighting mechanism is simple and intuitive. Edges between nodes far apart in the representation space receive lower weights.
  • The comparison between the deterministic and stochastic variants is useful.
  • The mathematical framework is rigorous and formal.
Critical weaknesses

W1: I am not convinced that conductance variance gives meaningful uncertainty about the graph. The distribution over the node representations and conductances is created by adding Gaussian noise to the model's dynamics. Why should the variance be interpreted as uncertainty rather than simply variation caused by the injected noise? With τ=0\tau=0 the "uncertainty" disappears, even though the true graph is still unknown. Furthermore, the deterministic version is also where most of the empirical gain comes from.

W2: The algorithm is restricted to edges which are already present in the graph. It also cannot increase underestimated weights. This is a considerably more narrow setting than correcting the geometry of a naturally noisy graph.

W3: The theoretical results require assumptions that significantly limit their applicability. Theorem 4 says that if the representation already separates clean edges from corrupted ones by distance, then the conductance update turns this into a difference in weights. However, it does not show that the dynamics find such a separation. Theorem 5 assumes that there is a representation H which gives a Laplacian that is already close to the target Laplacian and that the Gibbs distribution remains close to this representation. This is described as a conditional stability result, which is correct but limits its value.

W4: The paper requires significant effort to follow. Figure 1 is only readable after reading through all the technical sections, which defeats the purpose of an overview figure. After reading through the introduction and problem setting, it remains unclear what quantities are observed and fixed, which outputs are expected, and what are the modeling choices to be made. For example, it is not explained what the role of an encoder is: is it picked by the practitioner or supplied as part of the problem. Similarly, conductance is not really introduced before section 4 even though it is mentioned many times before that.

Questions for authors

Is it possible to apply this method for a heterophilic graph? Roman-Empire seems to be a heterophilic graph for example. What prevents the method from removing connections which are supposed to exist even though the nodes do not have a similar embedding?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.