Network science has precise theorems that say why PageRank, Katz, or degree centrality rank individual nodes the way they do. These are axiomatic characterizations: short lists of rules a scoring function must obey, together with proofs that only one function obeys them all. Many machine learning problems, however, ask for a group rather than a single winner. A common case is choosing which $k$ training examples to show a language model in its prompt, the demonstrations for in-context learning. For groups, practice runs on hand-assembled objectives that add a relevance term to a diversity penalty, and nobody can say which behavioral guarantees these objectives provide. This proposal builds the missing group-level theory. Each point in a graph, for example a validation query in a nearest-neighbor graph of text embeddings, acts as a voter that ranks candidate nodes by graph distance. A size-$k$ group is then chosen with a committee scoring rule from multiwinner voting, a family of election methods whose axioms are already known.
The claim is that this construction gives a single axiomatic family of "committee centralities." Known group heuristics sit inside it: top-$k$ degree, maximum neighborhood coverage, and a rank-based k-median. The family makes checkable predictions about robustness. Rules built only on each voter's ranking of candidates should keep their choice when the candidate pool contains near-duplicate examples, and they should be insensitive to how the embedding space is scaled. Cardinal objectives such as facility location, determinantal point processes, and K-means should break in predictable ways under the same conditions. We will prove the correspondences and the axiom profile, then test the predictions as a demonstration selector on existing in-context learning benchmarks. The tests use stress conditions designed so that each axiom's presence or absence has a measurable effect.
Core Claim
Voting for Centrality showed three things for single winners, with each node ranking others by shortest-path distance. Plurality voting reproduces degree centrality. Borda and Copeland voting give new centralities. Any valid centrality must be invariant under graph symmetries and respect the vicinal preorder, meaning a node whose neighborhood contains another's is at least as central. That paper stops at single winners. It explicitly leaves group centrality open and proves no uniqueness theorems.
On the voting side, Axiomatic characterization of committee scoring rules proves that five axioms together pick out exactly the committee scoring rules: anonymity, neutrality, consistency across disjoint electorates, continuity, and committee dominance. Committee Scoring Rules: Axiomatic Classification and Hierarchy sorts these rules into nested classes. Weakly separable rules score each candidate alone. Representation-focused rules, such as Chamberlin–Courant, score a committee by each voter's single best member. Top-$k$-counting rules count how many committee members fall in each voter's top $k$.
Our central claim is that composing the distance-induced preference profile with these classes gives committee centralities, a family with three properties. First, its named members coincide with familiar graph objectives. Second, adding graph-specific axioms narrows the family to identifiable rules. Third, the family's ordinal nature yields robustness guarantees that cardinal subset objectives lack. The empirical claim, which is the part most likely to fail, is that these guarantees change in-context learning accuracy under realistic pool defects.
Research Program
The first strand is a set of correspondence theorems. Fix a graph $G=(V,E)$, a voter set $U\subseteq V$, and a candidate set $C\subseteq V$. Each voter $u$ has a weak order on $C$ given by distance $d(u,\cdot)$, with ties when distances are equal. A committee scoring rule picks the size-$k$ set $S\subseteq C$ that maximizes
$$F(S)=\sum_{u\in U} \phi\big(\mathrm{pos}_u(S)\big),$$
where $\mathrm{pos}_u(S)$ is the sorted list of positions that the members of $S$ occupy in $u$'s ranking, and $\phi$ is a scoring function on such lists. We will show the following. SNTV, the rule that takes the $k$ candidates with the most first-place votes, reduces to top-$k$ degree. Chamberlin–Courant with a $t$-approval score reduces to maximum coverage of $t$-neighborhoods, which is the existing notion of group degree. Chamberlin–Courant with Borda scores is an ordinal k-median. Handling ties in distance requires care, as the single-winner case already showed; we will follow the indifference convention of Voting for Centrality.
The second strand is characterization. We translate three axioms into the group setting. Automorphism invariance is neutrality restricted to graph symmetries. The vicinal preorder becomes a committee-dominance statement. Locality comes from Random Walk Decay Centrality and from the Set Locality axiom in An Axiomatization of the Eigenvector and Katz Centralities; in our setting it says that edits inside a disconnected component must not change which members are chosen from the other components.
The target theorem characterizes the committee scoring rules on distance-induced profiles that satisfy locality. Our conjecture is that locality forces $\phi$ to decompose over components, and that this singles out the representation-focused rules as the only non-trivial class that also respects committee dominance. We will also try to prove an impossibility result in the style of An Axiomatic Framework for Result Diversification, which showed that no diversification function meets all eight of its axioms. Our candidate impossibility is that no committee centrality satisfies locality, committee dominance, and stability in $k$ at once, where stability means that growing $k$ by one does not overhaul the chosen set.
The third strand is the robustness analysis that motivates the experiments. Two defects matter.
The first is candidate clones. We want a rule to be clone-robust, a property called $\epsilon$-split proofness in the Pareto setting: adding near-duplicates of a candidate should not change which region of the space the committee represents. Picking a Representative Set of Solutions in Multiobjective Optimization: Axioms, Algorithms, and Experiments found that no measure it studied was both monotone and clone-robust. It proved that coverage and uniformity violate both properties, while directed coverage is monotone but still violates split-proofness. We will prove which committee centralities achieve both on graph-induced profiles. We expect representation-focused ordinal rules to do so because, under rank-based scores, a clone adds nothing to any voter's best representative. If this fails, it is a clean negative result that extends that paper's trade-off from Pareto fronts to graphs.
The second defect is a rescaled or miscalibrated embedding. Rankings are unchanged by any monotone transformation of distances, so ordinal rules inherit scale invariance. The graph's shortest paths also follow the shape of the data manifold rather than raw cosine similarity. Computing Chamberlin–Courant exactly is NP-hard. We will use the greedy $(1-1/e)$ approximation proved for the submodular subclass in Committee Scoring Rules: Axiomatic Classification and Hierarchy, and we will check whether greedy selection keeps the axioms that the exact rule has.
In the in-context learning application, the candidates are pool examples. The voters are validation queries, placed in a shared nearest-neighbor graph over Sentence-BERT embeddings. The selector needs no language-model calls. An optional variant replaces graph-distance rankings with rankings induced by the language model's own log-probabilities on a small budget of calls, so that we can compare at matched cost against methods that use model feedback.
Baselines
The naive reference points are random demonstrations and top-$k$ PageRank on the same nearest-neighbor graph. Random selection is the "do nothing" point. On the eight-task classification suite of Finding Support Examples for In-Context Learning, random selection averages 44.2% accuracy and that paper's LENS method reaches 69.8%. Top-$k$ PageRank is the weakly separable competitor: the best single-node centrality applied $k$ times. Beating it isolates the value of scoring the group rather than its members one at a time.
The strongest selector that uses no model calls is the two-stage determinantal point process of Representative Demonstration Selection for In-Context Learning with Two-Stage Determinantal Point Process. A determinantal point process is a probabilistic model that favors sets of items that are individually good and mutually dissimilar. This method filters by semantic similarity and then selects a set that trades quality against diversity. The paper reports that it beats K-means representative selection by 4% to 10%; it gives no absolute accuracies. Alongside it we will run cosine facility location with the greedy algorithm, which is exactly Chamberlin–Courant with cardinal utilities. Facility location is the competitor our claim must beat, so it serves as the key ablation. It uses the same voters, candidates, and greedy optimizer, and removes only the two ingredients we claim matter: rank-based scoring and graph distance. We will also run a variant that keeps graph distances but uses cardinal scores, to separate those two ingredients.
The strongest methods that use model feedback are LENS and CASE. Sample Efficient Demonstration Selection for In-Context Learning treats exemplar selection as finding the top-$m$ arms in a linear bandit. It reports up to 15.19% improvement over LENS with GPT-3.5-turbo and 87% fewer model calls than EXPLORA across GSM8K, AquaRat, TabMWP, FinQA, and StrategyQA, but the file gives no absolute accuracies for CASE. We will rerun CASE from kiranpurohit/CASE on the same splits. For per-query retrieval, Mixture of Demonstrations for In-Context Learning reports 58.63% average over twelve tasks with GPT-Neo 2.7B. We will use it as a reference for our per-query variant, in which a query's voters are its graph neighbors.
All selectors will use the same pool, embeddings, $k$, backbone model, and prompt template. Where orderings matter, we will average over five orderings of the demonstrations. Each tunable method, including ours with the neighbor count and score vector, gets the same grid of 20 configurations chosen on a held-out validation split. Beating a baseline means a higher mean accuracy across tasks, beyond the across-seed standard deviation, with no increase in model calls.
Why not just…?
Why not just use facility location or a determinantal point process, which already balance relevance and diversity with guarantees? This is the real threat, because cosine facility location is Chamberlin–Courant with cardinal scores. On clean pools, these objectives may match our rules. Our prediction is narrower: the gap opens under clones and rescaling, where cardinal objectives lack the invariances. The clone-injection and embedding-distortion experiments below settle this. If the gap stays within noise under those stresses, the empirical case fails and the contribution reduces to the theory.
Why not just take the top-$k$ nodes by PageRank or degree? Committee Scoring Rules: Axiomatic Classification and Hierarchy shows that such weakly separable rules form a narrow class that ignores how members overlap in whom they represent. Mixture of Demonstrations for In-Context Learning reports that redundancy from independent top-$K$ retrieval costs more than 5% against its method. Our top-$k$ PageRank baseline measures this directly on graphs built from the same embeddings.
Why not just use LLM-feedback search such as CASE or LENS? These methods optimize the real target, but each spends many model calls. They also carry no behavioral guarantees: nothing stops them from dropping an example after it becomes more useful. Our variant with rankings induced by the language model competes at matched call budgets. The monotonicity test below checks whether their selections behave erratically where ours cannot.
Why not just cluster with K-means and take centroids? The determinantal point process paper already reports K-means losing by 4% to 10%. K-means is also not clone-robust by construction, since duplicates pull centroids toward themselves. We keep it only as a stress-test comparator.
Proposed Experiments
The accuracy comparison runs on three suites: the LENS eight-task classification suite with GPT2-Large and GPT-Neo, the CASE reasoning suite with Mistral-7B and GPT-3.5-turbo, and SST-2, AGNews, and RTE from the determinantal point process paper. We compare exact greedy Chamberlin–Courant, both the Borda and $t$-approval variants, against every baseline above.
The decisive checks are four controlled perturbations, each tied to one axiom. In clone injection, we duplicate or paraphrase 20% of the pool, concentrated in one class, and measure how much the selected set changes and how much accuracy drops. In embedding distortion, we apply a monotone but nonlinear rescaling of distances and a whitening change. In $k$-stability, we measure how much of the size-$k$ set survives into the size-$(k+1)$ set. In monotonicity probes, we move a candidate's embedding toward validation voters and record whether each selector drops it.
The theory predicts that rank-based committee rules are unaffected by the distortion and change little under cloning, while facility location, the determinantal point process, and K-means shift. The proposal counts as successful if two conditions hold. First, these invariances hold for the greedy approximations actually used. Second, they carry over into accuracy: under clone injection, committee rules keep their clean-pool accuracy while the cardinal baselines lose a margin larger than seed noise. If the invariances hold but accuracy does not respond, we will report that behavioral guarantees and in-context accuracy come apart. That would be a useful constraint on how far axioms can guide demonstration selection.
References
- Voting for Centrality
- Axiomatic characterization of committee scoring rules
- Committee Scoring Rules: Axiomatic Classification and Hierarchy
- Random Walk Decay Centrality
- An Axiomatization of the Eigenvector and Katz Centralities
- An Axiomatic Framework for Result Diversification
- Picking a Representative Set of Solutions in Multiobjective Optimization: Axioms, Algorithms, and Experiments
- Finding Support Examples for In-Context Learning
- Representative Demonstration Selection for In-Context Learning with Two-Stage Determinantal Point Process
- Sample Efficient Demonstration Selection for In-Context Learning
- Mixture of Demonstrations for In-Context Learning