Groups Don't Move as One: A Bregman Clustering View of Linearized Group Influence

Hyunho Choi; Jaeseung Heo; Youngbin Choi; MoonJeong Park; Dongwoo Kim

cs.LGOct 10, 2026

Groups Don't Move as One: A Bregman Clustering View of Linearized Group Influence

Authors: Hyunho Choi, Jaeseung Heo, Youngbin Choi, MoonJeong Park, Dongwoo Kim

Organizations: Department of Computer Science & Engineering, POSTECH · Graduate School of Artificial Intelligence, POSTECH

Abstract

Influence functions provide an efficient alternative to retraining for assessing the effects of removing or reweighting training data. For groups, however, the standard first-order estimate reduces individual contributions to a sum that can conceal substantial differences among members, including opposing effects that cancel. We establish a Bregman centroid formulation of the linearized group influence objective, interpreting this aggregate as a single representative and using Bregman information (BI) to quantify the variation it omits. Extending this formulation to multiple clusters reveals distinct contributions whose sum recovers the original estimate. We further propose an estimator that jointly optimizes the weights of these cluster contributions, rather than simply summing them. Experiments uncover cluster-specific influence patterns and a positive association between target-specific BI and approximation error. The proposed estimator achieves higher $R^2$ than standard group influence in predicting target changes under the nonlinear proximal Bregman response function. Simplified clustering and correction variants reduce computational cost. The centroid view thus explains what additive group influence leaves out and provides a basis for using that information to improve estimation.

Figures & tables

Figure 1: Illustration of the Bregman clustering view of linearized group influence. (a) Standard GI summarizes member-wise response points by a single centroid, hiding within-group structure. (b) Bregman clustering reveals distinct component contributions while preserving the original aggregate estimate. (c) Joint E2 reweights these contributions under a corrected objective, yielding a refined estimate (blue star).

Figure 2: Bregman information tracks group influence error. Each point represents a random 1% removal group (100 groups per model). We plot projected Bregman information against the squared error of GI relative to the actual PBRF change. For each model, we show the query whose Spearman correlation

\rho

is closest to the median over 100 test queries.

Figure 3: The two clusters tend to exhibit different class-wise influence patterns. For an MNIST MLP, we split each of 100 random 10% removal groups into

k=2

Bregman clusters. Each cluster’s class-wise influence vector contains its contribution to GI averaged over test points within each class. (a) Case study: unit-normalized class-wise influence vectors of the two clusters. (b) Cosine similarities across all 100 groups (median

-0.03

, IQR

[-0.25,0.17]

). The dashed line marks the 90th percentile (

0.36

Figure 4: Actual PBRF vs. predicted test-loss changes. From top to bottom, the rows show Dogfish logistic regression (

30\%

removal), MNIST MLP (

10\%

), and CIFAR-10 ResNet9 (

1\%

). From left to right, the columns compare GI, single-component E2 (

k=1

), Euclidean Joint E2 (

k=2

), and Euclidean Intra E2 (

k=2

). Each panel shows one query across

100

removal groups, while annotations report median query-wise Spearman

\rho

and raw

R^{2}

over the retained queries. The gray line marks

y=x

. Across all three models, the improvements of both

k=2

variants over single-component E2 are significant at the

0.001

level for both metrics after Holm correction. Statistical details are provided in Section C.3 .

		Dogfish (logistic, 30%)		MNIST (MLP, 10%)
	Clustering	Spearman $\rho\uparrow$	$R^{2}\uparrow$	Spearman $\rho\uparrow$	$R^{2}\uparrow$
Joint	Bregman	$0.989_{[0.982,\,0.991]}$	$0.945_{[0.926,\,0.957]}$	$0.998_{[0.997,\,0.998]}$	$0.995_{[0.993,\,0.996]}$
Joint	Euclidean	$0.989_{[0.983,\,0.991]}$	$0.945_{[0.926,\,0.958]}$	$0.998_{[0.997,\,0.998]}$	$0.995_{[0.993,\,0.996]}$
Intra	Bregman	$0.984_{[0.977,\,0.989]}$	$0.945_{[0.919,\,0.957]}$	$0.998_{[0.997,\,0.998]}$	$0.993_{[0.991,\,0.995]}$
Intra	Euclidean	$0.984_{[0.976,\,0.989]}$	$0.945_{[0.919,\,0.957]}$	$0.998_{[0.997,\,0.998]}$	$0.994_{[0.992,\,0.995]}$

Table 1: Ablation of clustering geometry and edit-curvature scope at

k=2

. For each query, Spearman

\rho

and raw

R^{2}

are computed across

100

random removal groups. Entries report the median over the common retained queries, with the interquartile range in brackets.

Stage	Removal ratio	Baseline	Approx.	Reduction
Partition	$1\%$	$59.4$ s	$0.277$ s	$99.5\%$
Edit curvature	$10\%$	$0.193$ s	$0.103$ s	$46.6\%$

Table 2: Measured stage-wise cost reductions on MNIST at

k=2

. Baseline denotes Bregman clustering for partition construction and Joint E2 for edit curvature; Approx. denotes Euclidean clustering and Intra E2, respectively. Reduction is the relative decrease from the baseline stage time. Big-O analysis and timing protocols are provided in Section C.8 .

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Model	Classes	$N$	Ridge
Dogfish	Logistic head, 2,048 features + intercept	2	1,800	0.01
MNIST	ReLU MLP, $784$ – $512$ – $256$ – $10$	10	60,000	0.1001
CIFAR-10	Myrtle/DAWNBench ResNet9	10	50,000	0.3005

Appendix

Table 3: Models and training-set sizes. The ridge is shared by

G

and the PBRF proximal term; it is distinct from training regularization.

Model	Precision / init.	Solver	Budget and stopping
Logistic	FP64; GI initialization	Newton–PCG with strong-Wolfe L-BFGS fallback	PCG up to 100 steps; L-BFGS fallback up to 2,000 steps; gradient tolerance $10^{-10}$
MLP	FP64; GI initialization	Strong-Wolfe L-BFGS, learning rate 1, history 50	20 calls, each with up to 10 iterations
ResNet	Original-model initialization	Strong-Wolfe L-BFGS, learning rate 0.5, history 20	100 FP32 warm steps followed by 40 FP64 steps

Appendix

Table 4: Solver settings used to compute the actual PBRF reference points.

Model	$1\%$	$2\%$	$5\%$	$10\%$	$20\%$	$35\%$	$50\%$
Dogfish logistic	0.865	0.815	0.676	0.549	0.475	0.327	0.140
MNIST-10 MLP	0.701	0.656	0.580	0.453	0.340	0.169	0.121
CIFAR-10 ResNet9	0.525	0.413	0.290	0.218	0.190	0.146	0.145

Appendix

Table 5: Removal-ratio ablation for projected BI versus squared GI error. Each entry is the median of

100

query-wise Spearman correlations, each computed across

100

random groups. The original model and query bank are fixed within each model’s size sweep.

Removal	Metric	$k=1$	Joint $k=2$	$p_{\rm adj}$	Intra $k=2$	$p_{\rm adj}$
Dogfish
$1\%$	$R^{2}$	0.995	0.999	$1.01\times 10^{-16}$	—
	$\rho$	0.998	1.00	$1.35\times 10^{-16}$	—
$10\%$	$R^{2}$	0.946	0.985	$1.01\times 10^{-16}$	0.982	$1.01\times 10^{-16}$
	$\rho$	0.985	0.994	$1.01\times 10^{-16}$	0.993	$1.15\times 10^{-16}$
$30\%$	$R^{2}$	0.891	0.945	$1.40\times 10^{-16}$	0.945	$1.65\times 10^{-15}$

Appendix

Table 6: Median query-wise accuracy and two-sided query-paired

p

-values for Euclidean E2 (

k=2

) versus single-component E2 (

k=1

). Holm correction covers all

26

comparisons jointly across settings, variants, and both metrics ( Section C.3 ). The Spearman tests compare methods and are not tests of zero correlation. MNIST

30\%

Intra shows a significant decrease in raw

R^{2}

, not an improvement.

Method	Spearman	$R^{2}$
Dogfish ( $10\%$ )
GI	0.988	0.901
Single-component E2 ( $k=1$ )	0.985	0.946
Euclidean Joint E2 ( $k=2$ )	0.994	0.985
Euclidean Intra E2 ( $k=2$ )	0.993	0.982
Euclidean Joint E2 ( $k=10$ )	1.00	0.997

Appendix

Table 7: Additional removal ratios, with

100

random groups and

100

retained fixed queries per setting. All methods within a setting share the checkpoint, groups, queries, and actual PBRF references. The selected

k=2

and

k=10

comparisons expose removal-size and component-count sensitivity.

Model	Projected BI	Full BI	Euclidean
Dogfish logistic	0.865	0.759	0.760
MNIST-10 MLP	0.701	0.556	0.558

Appendix

Table 8: Geometry ablation on the same random

1\%

groups and fixed queries as the BI experiment. Entries are medians over

100

query-wise Spearman correlations with squared GI error, each computed across

100

groups. Euclidean dispersion uses raw gradients, not parameter responses.

Dogfish ( $30\%$ )
Method	Spearman	$R^{2}$
GI	0.984	0.862
Single-component E2 ( $k=1$ )	0.981	0.891
Bregman Joint E2 ( $k=2$ )	0.989	0.945
Bregman Intra E2 ( $k=2$ )	0.984	0.945
Euclidean Joint E2 ( $k=2$ )	0.989	0.945

Appendix

Table 9: Correction results against actual PBRF reference points. All settings use

100

random groups; metrics are medians over the common retained queries (

100

for Dogfish and MNIST, and

97

for ResNet9). All methods within a setting share the checkpoint, groups, queries, and actual PBRF references. Full E2 is an additional approximation, not the reference itself.

	Spearman $\rho$				$R^{2}$
	Joint E2		Intra E2		Joint E2		Intra E2
$k$	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean
1	0.981	0.981	0.981	0.981	0.891	0.891	0.891	0.891
2	0.989	0.989	0.984	0.984	0.945	0.945	0.945	0.945
4	0.993	0.993	0.984	0.984	0.968	0.970	0.951	0.950
6	0.995	0.996	0.982	0.982	0.978	0.978	0.946	0.947

Appendix

Table 10: Dogfish,

30\%

: component-count sweep on the same

100

groups and

100

queries. Each entry reports the median over fixed test queries. The four variants coincide at

k=1

	Spearman $\rho$				$R^{2}$
	Joint E2		Intra E2		Joint E2		Intra E2
$k$	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean
1	0.997	0.997	0.997	0.997	0.993	0.993	0.993	0.993
2	0.998	0.998	0.998	0.998	0.995	0.995	0.993	0.994
4	0.998	0.998	0.998	0.998	0.996	0.996	0.994	0.994
6	0.999	0.999	0.998	0.998	0.996	0.997	0.994	0.994

Appendix

Table 11: MNIST,

10\%

: component-count sweep on the same

100

groups and

100

queries. Each entry reports the median over fixed test queries. The four variants coincide at

k=1

	Spearman $\rho$				$R^{2}$
	Joint E2		Intra E2		Joint E2		Intra E2
$k$	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean	Bregman	Euclidean
1	0.985	0.985	0.985	0.985	0.946	0.946	0.946	0.946
2	0.994	0.994	0.993	0.993	0.985	0.985	0.982	0.982
4	0.998	0.998	0.994	0.994	0.995	0.996	0.986	0.987
6	0.999	0.999	0.993	0.994	0.997	0.997	0.984	0.985

Appendix

Table 12: Dogfish,

10\%

: component-count sweep on the same

100

groups and

100

queries. Each entry reports the median over fixed test queries. The four variants coincide at

k=1

Coefficient model	Retained contributions	Spearman	$R^{2}$
GI	Full	0.997	0.978
	Large only	0.794	0.630
	Small only	0.492	-0.008
Single-component E2 ( $k=1$ )	Full	0.997	0.993
	Large only	0.797	0.638
	Small only	0.492	-0.002

Appendix

Table 13: MNIST

10\%

, Bregman Joint E2 (

k=2

): component omission against the same full-group PBRF reference using

100

groups and

100

queries. E2 coefficients are held at the full-fit values; they are not refitted after omission.

$k$	Joint	Intra	Reduction (%)
2	0.193	0.103	46.6
4	0.384	0.111	71.2
10	0.973	0.136	86.0

Appendix

Table 14: Median edit-curvature stage time (seconds), MNIST

10\%

, fixed Euclidean components,

49

matched groups on an RTX3090. Reductions use the two medians. These are instrumented stage intervals, not end-to-end timings.

Influence Functions

Influence functions estimate how training examples or interventions change model parameters, predictions, and downstream behavior.

See all 40 papers

Interaction-Aware Influence Functions for Group Attribution
May 15, 2026Jaeseung Heo, Kyeongheung Yun, Youngbin Choi +3Instruction-Tuning Data Selection Influence Functions
GSAI, POSTECH · CSE, POSTECH
Extending Kernel Trick to Influence Functions
May 11, 2026Zhenhuan Sun, Shahrokh ValaeeEfficient Inference Influence Functions
University of Toronto
Which Influence Are We Estimating? The Role of Counterfactual Specifications in Data Attribution
Sep 25, 2026Zhe Li, Wei Zhao, Peixin Zhang +1Training Data Attribution Influence Functions
Singapore Management University

May 15, 2026J/K move · Enter open · S save

Interaction-Aware Influence Functions for Group Attribution

Jaeseung Heo, Kyeongheung Yun, Youngbin Choi, Sehyun Hwang+2

GSAI, POSTECH · CSE, POSTECH

Instruction-Tuning Data Selection Influence Functions Training Data Attribution

Open paper AskPDF arXiv

Influence functions approximate how removing a training example changes a quantity of interest, called the target function, such as a held-out loss. To estimate the influence of a group of examples, the standard practice is to sum the individual influences of its members. However, this sum does not capture how examples jointly affect the target: a pair of examples may be redundant or complementary, but the sum cannot distinguish these cases. We propose an interaction-aware influence function that characterizes how interactions between examples influence the target. By expanding the target to second order around the trained parameters, we obtain an estimator that augments the standard sum with a pairwise interaction term that captures the alignment between two examples' effects on the target. We empirically evaluate our estimator in two settings. First, on six dataset-model pairs spanning logistic regression, MLPs, and ResNet-9, our estimator tracks leave-group-out retraining substantially better than first-order influence across all settings. Second, when used as a greedy selection rule for instruction-tuning data on Llama-3.1-8B, it beats prior influence-based and representation-similarity baselines on five of seven downstream tasks, in a regime where standard influence-based selection underperforms random selection.

Abstract

Influence Functions

Explore similar work

Interaction-Aware Influence Functions for Group Attribution

Extending Kernel Trick to Influence Functions

Which Influence Are We Estimating? The Role of Counterfactual Specifications in Data Attribution