acceptodds
Under review as a conference paper at ICLR 2027

Gaussian Synergy-Preserving Node Aggregation for Restricted Graph

Abstract

Undirected weighted graphs model complex systems through pairwise associations, but conventional edge aggregation may fail to preserve the collective dependence between a group of nodes and their shared neighbors. We address this problem through a property-specific graph summarization framework based on a Laplacian-induced Gaussian model. The framework identifies restricted independent-neighbor motifs with a positive mutual-information synergy gap and derives superedge weights that preserve the corresponding dependence during node aggregation. For motifs with one shared neighbor, the solution uniquely preserves the joint dependence. For motifs with two shared neighbors, preservation is guaranteed only under an explicit solvability condition and applies to the two marginal dependences separately. Experiments on synthetic motifs, weighted real networks, and multiple random graph families verify numerical preservation, characterize the applicability of the solvability condition, and evaluate robustness, scheduling sensitivity, and downstream behavior. Comparisons with standard aggregation rules, a spectral oracle, and Heavy-Edge Matching show that performance depends on the graph family and evaluation objective. The proposed method therefore provides a theoretically grounded aggregation rule for restricted graph motifs rather than a universally optimal coarsening framework.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Graph Summary, Emergent Retention, Probabilistic Inference

Reviews

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

This paper studies the choice of edges weights when merging nodes in graph summarization. To do so, the authors associate the graph with a zero-mean Gaussian whose covariance is the graph Laplacian LL. This choice is motivated by an edge-flow model, where x=Bfx = Bf with independent flows ff on the edges. Under this model, pairwise non-adjacent nodes are independent. The authors start by defining a "Gaussian synergy gap" for a group of nodes X\mathbb{X} sharing a neighbour ZZ. They show that this gap is strictly positive whenever the nodes in X\mathbb{X} are non-adjacent. They then derive a weight π\pi for the edge between the merged node and ZZ such that I(X,Z)=I(Y,Z)I(\mathbb{X}, Z) = I(Y,Z). When the group has two shared neighbours, they show that both marginals mutual informations can be preserved if and only if a certain quantity is <1<1, in which case the solution is unique.

Critical strengths

I like the overall idea of the paper. Node aggregation is a useful and important tool for practitioneers, and finding alternative ways of doing this task is an interesting direction. The objective are precise, framing aggregation as preserving a declared query instead of sum or mean is a nice idea. The scope is stated carefully throughout. Feasability checks are explicit, and infeasible merges are rejected instead of being forced.

Critical weaknesses

While I find the overall idea interesting and worth pursuing, the paper has several issues that make it hard for me to recommend it for acceptance as is.

  1. Under the authors' random variable model, SUM is the exact aggregation while the proposed model breaks that. What I mean by this is the following. Let NN be the number of nodes and KK the number of sumary nodes, and let S∈{0,1}N×KS \in \{0,1\}^{N \times K} be the matrix that assigns each node to its merged group, i.e., Svg=1S_{vg} = 1 if node vv is in group gg, and 00 otherwise. Then, the Laplacian of the contracted graph becomes S⊤LSS^\top L S, which is exaclty cov(S⊤x)cov(S^\top x), when xx is the zero-mean gaussian with covariance LL described in the paper. In particular, in the flow interpretation S⊤BfS^\top B f cancels every flow inside a group, and only the flows crossing the boundary remains. This means that suming the edge weights give the exact distribution of the merged node signal Y=∑iXiY = \sum_i X_i, and leaves the degree of ZZ unchanged. The gap between SUM and the target is therefore the information lost by merging, I(∑iXi;Z)≤I(X;Z)I(\sum_i X_i; Z) \le I(\mathbb{X}; Z). The proposed approach thus inflate the weights of the merged node's edge to ZZ, which changes the variance of ZZ and therefore its mutual information to its other neighbours. This thus propagates to later merges where ZZ is a target or a member. The same holds in the double-edge case, where SUM (π1=∑iαi\pi_1 = \sum_i \alpha_i, π2=∑iβi\pi_2 = \sum_i \beta_i) is always feasible and leaves Var(Z1)Var(Z_1), Var(Z2)Var(Z_2) and I(Z1;Z2)I(Z_1;Z_2) unchanged. To me, this leaves open the question on why one would prefer using the mutual information-preserving π\pi instead of the sum.
  2. The title says "synergy preservation", but it would seem to me that the method preserves I(X;Z)I(\mathbb{X};Z) and not Δsyn\Delta_{syn}. Moreover, in the double-edge setting, only the two marginals I(X;Z1)I(\mathbb{X};Z_1) and I(X;Z2)I(\mathbb{X};Z_2) are preserved, not the joint I(X;Z1,Z2)I(\mathbb{X};Z_1,Z_2), nor I(Z1;Z2)I(Z_1;Z_2) when Z1Z_1 and Z2Z_2 are adjacent. After merging, the group is a single node, so the summary can no longer distinguish the synergistic part Δsyn\Delta_{syn} from the individual contributions ∑iI(Xi;Z)\sum_i I(X_i;Z). The method preserves their total I(X;Z)I(\mathbb{X};Z), but not the synergy as such. In what sense is the synergy preserved, beyond being included in this total?
  3. The feasbility condition in Thm. 3 is not properly characterized. The synthetic checks sample α\alpha and β\beta independently. Infeasibility does appear under log-normal weights (up to 20.8% of samples for n=25n = 25), but the paper does not explain when or why C1+C2≥1C_1 + C_2 \geq 1 occurs. Separately, the strict inequality C<1C < 1 in Thm 2 (Eq. 25) needs ∑jrj>0\sum_j r_j > 0 or o1>0o_1 > 0 (if both are zero, C=1C = 1), which should be stated in the theorem.
  4. The experiments does not show the usefulness of the proposed summarization. The experiments mostly shows that the method indeed preserves the mutual info, but no downstream task shows a benefit from a graph summarised this way.

Presentation. Please use parenthetical citations where appropriate, e.g., "Watts–Strogatz (Watts & Strogatz, 1998)" instead of "Watts–Strogatz Watts & Strogatz (1998)". The paper is sometimes dense and hard to read, and the notation is heavy, with some terms used without definition or intuition. For example, the abstract refers to "nonsingular proper principal marginals" and the "double-external-neighbor motif" without intuition. The notation XiX_i denotes both a node and a random variable, which makes some passages hard to follow.

Questions for authors
  1. Given that S⊤LS=Cov(S⊤x)S^\top L S = \mathrm{Cov}(S^\top x), why should a practitioner prefer the proposed π\pi, which changes Var(Z)\mathrm{Var}(Z), over SUM, which is exact for the summed signal?
  2. After a full end-to-end run, what is the error of the original-graph group-to-target MIs?
  3. Is there a downstream task where preserving I(X;Z)I(\mathbb{X};Z) through a merged node beats both caching the value and using SUM?
  4. How often is C1+C2≥1C_1 + C_2 \geq 1 on real weighted graphs beyond the two small benchmarks, and how should such groups be handled?
3 comments
  1. Why choose the derived weight when SUM is exact for the summed signal?

The identity Cov⁡(S⊤x)=S⊤LS\operatorname{Cov}(S^\top x) = S^\top L S gives SUM its physical interpretation: it reproduces the covariance of aggregated net flow. Our weight answers a query about the original observations: how much does observing the entire source vector reduce uncertainty about the target? Summing sources can discard information relevant to that target. Theorem 2 constructs the unique superedge from which the original vector-to-target MI can be recovered. A practitioner estimating total flow should use SUM. A practitioner querying the original group dependence can use the derived weight.

This choice can change the target variance and its dependence on other neighbors. We observed the effect on Karate: after the group {8,26}\{8, 26\} had been contracted, another merge used vertex 33 as its target. The earlier group and target were still identifiable, but their MI changed from 0.0170353 to 0.0169594 nats. The trial-contraction check uses precisely this change in the original query value to decide whether to proceed.

  1. Which quantity does the title claim to preserve?

The synergy gap identifies a property of the original motif. After contraction, the invariant is total group-to-target MI. In the two-target case, Theorem 3 preserves the two marginal MIs separately. Neither the individual source contributions nor the joint two-target MI is recoverable from these equalities alone. If the targets are adjacent, their mutual edge can remain fixed while their MI changes through their variances. We propose the revised title Mutual-Information-Preserving Node Aggregation for Restricted Graph Motifs and will use the same invariant in the abstract and theorem statements.

  1. Where are the feasibility boundaries in Theorems 2 and 3?

In Theorem 2, positive target-edge weights and nonnegative residual weights give C<1C < 1 whenever the group has positive total residual degree or the target has positive outside degree. When both totals vanish, C=1C = 1. We will state this boundary explicitly and correct the placement of strict inequalities in Eq. (25).

For two targets, each CC measures the fraction of that target’s variance explained by the group. If different sources are strongly associated with different targets, each marginal can demand a large share of the summary node’s variance. A finite positive solution exists precisely when C1+C2<1C_1 + C_2 < 1. Algorithm 1 skips infeasible candidates. In the heterogeneous log-normal experiment, 20.8% of sampled size-25 groups were infeasible.

  1. How frequent is infeasibility on an additional real graph?

On the EIA graph we exhaustively enumerated target pairs and their eligible source subsets before testing feasibility. All 60 eligible queries across 30 target pairs were feasible. The largest C1+C2C_1 + C_2 was 0.559721, for sources CPLW and MISO with targets TVA and PJM. Maximum absolute marginal MI error across the contractions was below 2.1×10−132.1 \times 10^{-13} nats. This gives an observed infeasibility rate of 0/60 for this graph and structural filter.

  1. How well are original queries preserved at the end?

At the end of the unprotected deterministic runs, we compared methods on exactly the same surviving source-set queries. On Karate, Proposed and SUM had mean absolute MI errors of 0.000151 and 0.003241 nats (3 surviving queries). On Les Misérables, the errors were 0.001041 and 0.000665 (56 surviving queries).

For a prescribed workload, the query-aware extension provides a controlled comparison. At a tolerance of 0.001 nats and a common budget of 31 Karate nodes, Proposed represented 3 of the 6 registered groups by one supernode, versus 2 for SUM. At a common budget of 70 Les Misérables nodes, the counts were 7 of 8 versus 3. Both methods could reject a merge from the outset. At the looser tolerance of 0.01 nats, both formed all six Karate groups in a 25-node summary. The choice of weight therefore matters most when the workload requires tight fidelity and actual source aggregation.

  1. Is there a downstream benefit over SUM or a scalar cache?

We evaluated missing-meter recovery in MW on the EIA data. Each method reads the same sum of the source areas’ hourly power residuals. The summary edge determines the correlation used to estimate target power, calibrated using first-quarter signal scales. We evaluated hourly predictions in the second quarter. The table reports the mean of the query-level RMSEs across 422 queries and the mean absolute deviation from original graph MI.

Weight ruleRMSE (MW)MI deviation (nats)
Exact Proposed1,469.6<10−15< 10^{-15}
SUM1,462.30.00703
MEAN1,427.50.03060
Spectral oracle1,484.70.02473
Prediction fit with 0.01-nat tolerance1,457.40.00873

The exact rule preserves the declared dependence. MEAN gave the lowest prediction error among the original graph baselines, and the time-of-week reference alone yielded 1,420.4 MW. In a separate extension, fitting the edge weight to training-period power errors within a per-query MI tolerance reduced mean RMSE by 12.2 MW relative to the exact rule. Under equal target weighting, SUM outperformed this extension (914.6 versus 923.1 MW).

A cache answers a fixed list of stored scalar scores exactly. Our shared-summary experiment measures a different deliverable: a contracted weighted graph that retains the designated queries. We quantify its node count and query coverage. A storage or latency advantage over caching would require a separate comparison.

  1. How will the notation and presentation be clarified?

We will distinguish vertices from their associated random signals, introduce the one- and two-target motifs with a concrete group-to-hub query, and explain nonsingular marginals in the model section. We will also correct the parenthetical citations, including the repeated Watts–Strogatz attribution.

Reviewer_sdzFOpenReview ↗

Answer to author

I thank the authors for their answers and apologize for my late reply.

Regarding the first question, I still do not fully understand how this error propagates to larger nodes. Since the MI is inflated at each step, how does the error behave after 10 or more steps?

The change of title is welcome, and I find the new one more fitting. Overall, the rebuttal clarified some of the claims, and I believe the idea is worth pursuing. However, the paper still needs to show how this task can be used for downstream tasks, and it would benefit from further maturation. I therefore keep my score of 2. I encourage the authors to pursue this work, and I will be happy to read a more mature version.

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

This paper studies graph summarization through node aggregation, with a specific objective: preserving the mutual information between a group of nodes and a designated target node after the group is merged into a single summary node. The authors focus on a restricted class of weighted, undirected graphs and establish theoretical guarantees under explicit structural and feasibility conditions.

Critical strengths

The local weight computation has low computational cost, and the double-edge solution can be obtained through bracket expansion and bisection. The resulting method is easier to inspect and reproduce than a learned aggregation model.

Critical weaknesses
  1. Theorem 1 establishes a positive synergy gap under pairwise nonadjacency and positive connections to a common target. However, under the assumed Gaussian model, pairwise nonadjacency implies that the corresponding group variables have a diagonal covariance matrix. The positivity result then follows from a relatively elementary inequality involving Gaussian mutual information. In other words, the theorem appears to establish a general consequence of independent Gaussian group variables correlated with a common target, rather than a distinctive property of graph summarization.

  2. The real-network experiments use only two small networks. The synthetic experiments broaden the graph-generation settings but do not replace evaluations on large or application-specific graphs. The paper also acknowledges that its runtime measurements characterize the local solver rather than the complete graph-summarization pipeline. Candidate discovery, structural validation, conflict resolution, and scheduling are not established as scalable.

Questions for authors

What genuinely new mathematical insight does Theorem 1 provide beyond the standard Gaussian mutual-information formula?

Does the result remain informative when the group nodes have correlated residual dependencies or share external neighbors?

1 comment
  1. What mathematical insight goes beyond the Gaussian MI formula?

Theorem 1 translates a familiar Gaussian inequality into a condition that can be checked on the graph: pairwise nonadjacency gives diagonal source covariance, and positive edges to a shared target yield a positive gap.

The inverse problem begins after this step. Theorems 2 and 3 determine which edge weights reproduce the dependence after a vector of sources has been replaced by a scalar. In particular, even when each original marginal MI is finite, their simultaneous preservation can fail because both summary edges share a single variance budget. The condition C1+C2<1C_1 + C_2 < 1 identifies the exact boundary under the stated assumptions.

  1. What changes with correlated sources or shared external neighbors?

A shared external neighbor does not induce marginal covariance between two nonadjacent sources in this model. Genuine source correlation changes the conclusion. For example, take two standardized Gaussian sources with correlation 0.9, each having correlation 0.5 with the target. Joint MI is about 0.153 nats, whereas the two individual MIs sum to 0.288 nats. We will use this example to make clear where source independence enters Theorem 1.

  1. Are the motifs present in an application with measured flows?

We built a graph from January–March 2024 EIA-930 hourly electricity interchange. Its edge weights are variances of bilateral flow residuals after removing training-period hour-of-week means. The graph contains 68 balancing areas and 152 edges. We found 465 eligible single-target queries across 22 targets, including 215 groups of two sources, 170 of three and 80 of four. Individual contractions reproduced the original model MI with maximum error below 1.2×10−161.2 \times 10^{-16} nats.

For 422 queries, April–June observations of total net interchange supplied a held-out Gaussian MI estimate. Query-averaged absolute error was 0.0986 nats for both the original graph and Proposed, and 0.1003 for SUM. With equal weight per target, the errors were 0.0832 and 0.0806, respectively. These two comparisons measure model-score preservation and agreement with measured dependence separately.

  1. What is the cost of the complete algorithm?

We timed candidate discovery, validation, weight solving and graph updates in the full mixed-contraction procedure. On weighted Barabási–Albert graphs with two attachments per added vertex and three seeds per size, median wall time was 0.011, 0.048, 0.262, 1.85 and 14.03 seconds at 64, 128, 256, 512 and 1,024 initial nodes.

At 1,024 nodes the median run statistics were 271 contractions and 61 remaining nodes. Candidate discovery consumed 94.7% of runtime; the weight solver took approximately 0.005 seconds. We will distinguish these end-to-end measurements from the original benchmark on already identified candidate groups.

Comments on the paper

2 comments

Our paper asks how to choose a superedge weight from the dependence query that a contraction should preserve. For one target, the original group-to-target mutual information (MI) determines a unique positive weight. For two targets, both weights contribute to the variance of the same summary node. Theorem 3 resolves this coupling by giving a necessary and sufficient feasibility condition and a unique solution. The additional experiments below test how these local results carry through successive contractions and how often the motifs occur in a measured flow network.

1 Which original queries survive a complete run of Algorithm 1?

Table 2 contracts each registered group separately. We now follow the same original queries through one shared summary per network. A query remains representable when its target is a singleton and its source group is exactly the union of current summary nodes. Reading it through one supernode additionally requires one of those nodes to contain the entire source group. Under the original deterministic schedule, 3 of 277 Karate queries and 56 of 2,911 Les Misérables queries retained an exact source-set representation. Of these, 3 and 5, respectively, could be read through one supernode. Among the representable queries, mean absolute MI drift from the original graph was 0.000151 and 0.001041 nats. These denominators distinguish query survival from accuracy conditional on survival.

2 When can the final summary guarantee a registered query?

Our new query-aware extension checks each trial contraction against the original query value before accepting it. Requiring exact representation and an absolute error within the same tolerance at every step also enforces that tolerance at termination. In a paired comparison, we registered disjoint groups before the first merge and allowed every weight rule to reject candidates. At 0.001 nats, Proposed formed all 6 designated Karate supernodes in a 25-node graph and all 8 Les Misérables supernodes in a 57-node graph. SUM formed 2 and 3, ending at 31 and 70 nodes. MEAN formed none. When we registered the complete overlapping lists, the deterministic search admitted no contraction.

3 Do the local equations require disjoint residual neighborhoods?

Disjointness is a sufficient candidate filter. Under the declared Laplacian covariance, the covariance between two source vertices depends on their direct edge. Sharing a third neighbor leaves this entry zero for nonadjacent sources. If contributions to a common residual neighbor are summed on contraction, the source and summary variances entering the local equations depend only on total residual weights. We will separate this algebraic requirement from the stricter filter used in the experiments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.