acceptodds
Under review as a conference paper at ICLR 2027

Make Each Step Count: Entropic Walker for Compact and Informative Graph Representation Learning

Abstract

Learning compact and predictive representations that capture critical substructures is fundamental for effective graph learning. However, existing works either risk critical information loss or suffer from the inclusion of task-irrelevant distractors. In this work, we present an information-theoretic formulation for compact graph learning and introduce a tractable, explicit proxy for quantifying structural redundancy. Concretely, our formulation decouples structural complexity from the mutual-information term that is entangled with subgraph diversity, and further aligns the graph compactness objective with the entropy of random walk sequences. This not only avoids direct mutual-information estimation, but also yields an explicit and tractable objective for learning compact predictive substructures. Building on this formulation, we propose Entropic Walker (EW), a framework for learning compact yet predictive graph representations via entropy-controlled random walks, with scalable formulations for both graph-level and node-level tasks. Experiments on 15 benchmarks across diverse applications show consistent performance gains and strong ablation results, highlight the need to rethink the way to measure structural redundancy of graph data.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Compact Graph Representation Learning, Random Walk

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_P8UDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper aims to preserve task-relevant structures while reducing structural redundancy. It propose an information-theoretic formulation that uses random walk entropy as a tractable surrogate for graph compactness, avoiding direct mutual information estimation. EW employs learnable random walks to select substructures and combines entropy regularization with task-specific objectives.

Critical strengths

Using structural entropy to guide the removal of task-irrelevant nodes is a reasonable and potentially promising idea.

Critical weaknesses
  1. The overall framework illustrated in Figure 1 is unnecessarily complicated and could be presented more clearly.

  2. The authors should clarify the differences and connections between this work and the following studies:

[1] Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism

[2] HuGE: An Entropy-driven Approach to Efficient and Scalable Graph Embeddings

[3] Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks

  1. Although the paper claims to conduct experiments on 15 datasets, the main performance comparisons are largely concentrated on the eight datasets reported in Tables 2 and 3, which substantially weakens the claimed experimental coverage. Moreover, most baselines are general-purpose graph representation learning methods, with very few directly addressing the same task and research objective as this paper.

  2. The manuscript contains formatting and organizational errors. In particular, why does the appendix begin with Section 5.1? The section numbering and overall formatting should be carefully checked and corrected.

Questions for authors

See above Cons.

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

This paper proposes a graph representation learning framework that uses random walks to modify the graph structure. It samples multiple differentiable random walks, merges their visited nodes and edges into a single sparsified subgraph, and passes it to an MPNN/Transformer backbone. Experiments across different benchmarks show consistent improvements over other models.

Critical strengths
  1. Standard GIB methods must estimate mutual information over discrete, non-Euclidean graphs, which relies on unstable variational approximations or overly simplifying assumptions. Avoiding direct MI estimation is a well-motivated goal.
  2. The method seems to achieve strong performance across 15 diverse benchmarks.
Critical weaknesses
  1. Despite the information theoretic framing, the algorithm seems a complicated way to simply use random walks to select and merge a connected subset of nodes and edges before running a standard MPNN/Transformer.
  2. Invoking Shannon's coding theorem to equate random-walk transition entropy with "structural redundancy" is unconvincing: simple subgraphs (e.g., a regular tree) can serve for the same scope. Why didn’t you compare your method with very simple and efficient baselines or other graph rewiring techniques?
Questions for authors
  1. Are you actually minimizing H(G′G) instead of H(G′)? Since the initial and transition probabilities are computed conditioned on a specific input graph G, isn't the walk entropy H(S) actually measuring the conditional entropy H(S|G)?
  2. You are adding many hyperparameters to be tuned. How did you tune them? And what is the overall complexity of your method?
Reviewer_h7PKOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Entropic Walker (EW), a graph representation learning framework that formulates subgraph sparsification through the lens of the Graph Information Bottleneck and coding theory. Instead of estimating mutual information between the input graph and a compressed subgraph, the authors regularize the Shannon entropy of parameterized random-walk transitions. Crucially, the sampled walks are not processed as sequences. Instead, their visited nodes and edges are merged via set union into a single static subgraph and fed into a standard hybrid message-passing / global-attention backbone. While the paper is clearly written and reports broad experiments across 15 benchmarks, the main contribution essentially repackages learnable 1-hop edge pruning inside an information-theoretic walk narrative, and several experimental inconsistencies weaken the empirical claims.

Critical strengths
  • Replacing unstable variational mutual-information estimators in classic GIB methods with an analytical entropy penalty over local transition logits provides a simple, computationally lightweight sparsification module that integrates easily into standard GNN backbones.
  • The empirical study spans 15 datasets across molecular graphs, superpixel vision tasks, long-range benchmarks, and large heterophilic graphs, supported by ablations on walk length, teleportation probability, and matched random pruning budgets.
Critical weaknesses
  • Although framed around random walks and GIB, Step 3 of EW discards all sequential walk structure, merging traversed edges into a static unweighted subgraph GmG_m before running a standard GIN + Virtual Node / Transformer backbone. Unlike CRaWL and NeuralWalker, which encode walklet identity/adjacency patterns and process walks with sequence models to surpass 1-WL expressivity, EW forfeits sequential expressivity and remains bounded by its downstream MPNN. Functionally, combining the local transition softmax (Eq. 16) with the average step-entropy penalty Hˉs\bar{H}_s (Eq. 10) reduces to 1-hop GAT-style edge scoring with entropy minimization and Gumbel-Softmax edge pruning like NeuralSparse ( Zheng et al., 2020) and NodeFormer (Wu et al. 2022).
  • Treating walk policy entropy H(S)H(S) as a measure of intrinsic "graph structural complexity" conflates sampler uncertainty with graph topology. Without Ltask\mathcal{L}_{task} in Eq. 18, H(S)H(S) trivially collapses to a deterministic 2-node oscillation. Meanwhile, it is unclear how Ltask\mathcal{L}_{task} backpropagates through the discrete deduplicated set union GmG_m into the step-wise walk logits.
  • Several discrepancies across the experimental tables undermine confidence in the claimed improvements: 1) Discrepancy of NeuralWalker on CIFAR10 reported in Table 1; 2) Missing EW results on heterophilic graphs from Table 3. 3) Table 6 sweeps β′=rβ\beta'=r\beta and highlights r=1r=1 as universally optimal across all datasets and tasks. However, Tables 10–12 show that the base β\beta was already tuned per dataset.

Wu, Qitian, et al. "Nodeformer: A scalable graph structure learning transformer for node classification." Advances in neural information processing systems 35 (2022): 27387-27401.

Questions for authors
  1. Could the authors provide some insights on discrepancy in NeuralWalker baseline numbers? Additionally, is EW's 0.06 ± 0.12 on ZINC a typo in the standard deviation?
  2. Which model corresponds to the "Baseline" column in Table 8? Why are AR and QS results of EW reported in Table 8 skipped in Table 3?
  3. Section 3.3 states that concatenating node features [xi,xj][x_i,x_j] when edge attributes are absent replicates node content and degrades EW, yet none of the five heterophilic graphs in Table 3 have edge attributes. What are the exact β\beta values and edge retention ratios ∣E(Gm)∣/∣E(G)∣\vert{}E(\mathcal{G}_m)\vert{}/\vert{}E(G)\vert{} on the five heterophilic benchmarks?
  4. Since Step 3 collapses all walks into a static subgraph GmG_m, how does EW compare against directly applying Gumbel-Softmax + entropy regularization to 1-hop edge logits Tij\mathcal{T}_{ij} on the same GIN + Global MPNN backbone without sequential random-walk sampling?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.