- 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 . This choice is motivated by an edge-flow model, where with independent flows 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 sharing a neighbour . They show that this gap is strictly positive whenever the nodes in are non-adjacent. They then derive a weight for the edge between the merged node and such that . 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 , 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.
- 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 be the number of nodes and the number of sumary nodes, and let be the matrix that assigns each node to its merged group, i.e., if node is in group , and otherwise. Then, the Laplacian of the contracted graph becomes , which is exaclty , when is the zero-mean gaussian with covariance described in the paper. In particular, in the flow interpretation 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 , and leaves the degree of unchanged. The gap between SUM and the target is therefore the information lost by merging, . The proposed approach thus inflate the weights of the merged node's edge to , which changes the variance of and therefore its mutual information to its other neighbours. This thus propagates to later merges where is a target or a member. The same holds in the double-edge case, where SUM (, ) is always feasible and leaves , and unchanged. To me, this leaves open the question on why one would prefer using the mutual information-preserving instead of the sum.
- The title says "synergy preservation", but it would seem to me that the method preserves and not . Moreover, in the double-edge setting, only the two marginals and are preserved, not the joint , nor when and are adjacent. After merging, the group is a single node, so the summary can no longer distinguish the synergistic part from the individual contributions . The method preserves their total , but not the synergy as such. In what sense is the synergy preserved, beyond being included in this total?
- The feasbility condition in Thm. 3 is not properly characterized. The synthetic checks sample and independently. Infeasibility does appear under log-normal weights (up to 20.8% of samples for ), but the paper does not explain when or why occurs. Separately, the strict inequality in Thm 2 (Eq. 25) needs or (if both are zero, ), which should be stated in the theorem.
- 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 denotes both a node and a random variable, which makes some passages hard to follow.
Questions for authors
- Given that , why should a practitioner prefer the proposed , which changes , over SUM, which is exact for the summed signal?
- After a full end-to-end run, what is the error of the original-graph group-to-target MIs?
- Is there a downstream task where preserving through a merged node beats both caching the value and using SUM?
- How often is on real weighted graphs beyond the two small benchmarks, and how should such groups be handled?
3 comments
- 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 rule | RMSE (MW) | MI deviation (nats) |
|---|---|---|
| Exact Proposed | 1,469.6 | |
| SUM | 1,462.3 | 0.00703 |
| MEAN | 1,427.5 | 0.03060 |
| Spectral oracle | 1,484.7 | 0.02473 |
| Prediction fit with 0.01-nat tolerance | 1,457.4 | 0.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.
- 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.
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.
The identity Cov(S⊤x)=S⊤LS 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} 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.
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.
In Theorem 2, positive target-edge weights and nonnegative residual weights give C<1 whenever the group has positive total residual degree or the target has positive outside degree. When both totals vanish, C=1. We will state this boundary explicitly and correct the placement of strict inequalities in Eq. (25).
For two targets, each C 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<1. Algorithm 1 skips infeasible candidates. In the heterogeneous log-normal experiment, 20.8% of sampled size-25 groups were infeasible.
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+C2 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−13 nats. This gives an observed infeasibility rate of 0/60 for this graph and structural filter.
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.