Source-linked AI summary
On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
Vince Lyzinski, Keith Levin, Donniell E. Fishkind, Carey E. Priebe
TL;DR
Vertex nomination ranks unobserved vertices using a few known examples, with the goal of placing members of a target community near the top. The paper proves consistency for maximum-likelihood nomination, including a more scalable restricted-focus variant, with model parameters known or estimated from seeds.
Problem
Vertex nomination must rank remaining vertices from seed examples, while prior stochastic block model work provides a Bayes-optimal scheme as a benchmark.
Source: §1 · p. 2, §1.1 · p. 3Method
The paper develops maximum-likelihood vertex nomination and a restricted-focus variant, and studies consistency with known and seed-estimated model parameters.
Source: §1 · p. 2Results
Both maximum-likelihood schemes are proved consistent, including when model parameters are estimated using seeds, which may be an asymptotically vanishing portion of the graph.
Source: §1 · p. 2Takeaways & Limitations
The proofs establish the stronger outcome AP(L)=1 almost always almost surely for the two nomination schemes.
Source: §1.1 · p. 3
Abstract
from arXiv · showhide
Given a graph in which a few vertices are deemed interesting a priori, the vertex nomination task is to order the remaining vertices into a nomination list such that there is a concentration of interesting vertices at the top of the list. Previous work has yielded several approaches to this problem, with theoretical results in the setting where the graph is drawn from a stochastic block model (SBM), including a vertex nomination analogue of the Bayes optimal classifier. In this paper, we prove that maximum likelihood (ML)-based vertex nomination is consistent, in the sense that the performance of the ML-based scheme asymptotically matches that of the Bayes optimal scheme. We prove theorems of this form both when model parameters are known and unknown. Additionally, we introduce and prove consistency of a related, more scalable restricted-focus ML vertex nomination scheme. Finally, we incorporate vertex and edge features into ML-based vertex nomination and briefly explore the empirical effectiveness of this approach.
1 Introduction and Background
Vertex nomination uses observed seed vertices to rank the remaining vertices so that members of a target community concentrate near the top. The paper establishes consistency results for maximum-likelihood schemes and introduces a restricted-focus variant.
1 Introduction and Background
- The paper proves consistency for maximum-likelihood nomination and introduces a restricted-focus maximum-likelihood scheme that is efficiently exactly solvable.Consistency is also established when model parameters are unknown and estimated using seed vertices, even when seeds are an asymptotically vanishing portion of the graph.Source: §1 · p. 2
1.1 Background
- The stochastic block model provides a tractable model of latent community structure, although it may not capture the eccentricities of many real graphs.Prior work also relates maximum likelihood and maximum modularity in a special known-parameter SBM case; the paper states that this yields a consistent modularity-based nomination scheme there.Source: §1.1 · pp. 2, 4
- Vertex nomination orders nonseed vertices so that members of the community of interest concentrate at the top, using seed vertices as examples.The paper measures nomination efficacy with average precision (AP), which rewards placing interesting vertices higher in the list.Source: §1 · p. 1, §1.1 · p. 3
- The canonical nomination scheme is Bayes-optimal under mild stochastic block model assumptions, providing the benchmark for consistency.The background describes L_C as satisfying E AP(L_C) ≥ E AP(L) for any nomination scheme L.Source: §1.1 · p. 3
2 Graph Matching and Maximum Likelihood Estimation
The maximum-likelihood nomination approach estimates seeded block memberships by solving a likelihood optimization that can be recast as seeded graph matching. It then ranks nonseed vertices using likelihood changes associated with switching their estimated memberships.
2 Graph Matching and Maximum Likelihood Estimation
- The maximum-likelihood estimator searches feasible block assignments that preserve the observed seed memberships and block sizes.The feasible assignments define the candidate block membership functions used in the likelihood optimization.Source: §2 · pp. 4–5
- The likelihood optimization can be reformulated as seeded graph matching by representing block assignments with permutation matrices and using a weighted graph.The reformulation preserves the optimizer, allowing graph-matching algorithms to approximately find the maximum-likelihood assignment.Source: §2 · pp. 5–6
2.1 The LML Vertex Nomination Scheme
- LML approximately solves seeded graph matching, then uses likelihood changes from switching estimated memberships to rank vertices in the target block and outside it.The resulting scores are interpreted as confidence measures for whether a vertex belongs to the block of interest.Source: §2.1 · pp. 6–7
- When model parameters are unknown, seed memberships can estimate the edge-probability matrix and, if needed, the block sizes for plug-in use.The estimated matrix replaces the known-parameter matrix in the optimization.Source: §2.1 · p. 7
R Vertex Nomination Scheme
The restricted-focus scheme makes likelihood-based nomination more tractable by dropping edges between nonseed vertices from its matching objective. This yields a linear assignment problem, while the full LML scheme can use the omitted adjacency information and achieve higher precision in the reported comparison.
R Vertex Nomination Scheme
- General graph matching is computationally difficult, and efficient approximate algorithms often lack performance guarantees.The paper motivates a restricted-focus approach rather than relying on a fast approximation to the full matching problem.Source: R Vertex Nomination Scheme · p. 7
- Restricted-focus matching ignores edges between unseeded vertices, retaining the seed-to-nonseed part of the objective as a linear assignment problem.The corresponding assignment can be solved exactly in O(u^3) time with the Hungarian algorithm.Source: R Vertex Nomination Scheme · p. 8
- The restricted-focus scheme is reported feasible for graphs up to thousands of nodes, while full LML can achieve superior precision by using nonseed adjacency.The authors describe the feasibility scale as based on their experience.Source: R Vertex Nomination Scheme · p. 9
3 Consistency of LML and LML
The paper proves consistency for both LML schemes, first with known stochastic block model parameters and then with parameters estimated from seeds. For the restricted-focus result, the stated conditions include separation between within- and between-block probabilities and sufficient growth of nonseed and seed counts.
3 Consistency of LML and LML
- The paper states that both schemes remain consistent when model parameters are unknown and estimated from seed vertices.The preceding theorems assume model parameters are known a priori.Source: §3 · p. 9
- For the LML nomination scheme, as n tends to infinity, its expected average precision tends to 1; moreover, LML is a consistent nomination scheme.Source: §3 · p. 10
- The restricted-focus scheme is consistent under conditions including distinct within- versus between-block probabilities and uk = ω(√n), mk = ω(log uk).The theorem states that its expected average precision tends to 1.Source: §3 · p. 10
R When the Model Parameters are Unknown
The paper proves that ML and restricted-focus ML nomination remain consistent under mild assumptions when model parameters and block sizes are estimated from seeds. The guarantees allow the seeds to form a vanishing fraction of the graph.
R When the Model Parameters are Unknown
- The stated conditions require fixed K and, for each covered block, nk=Θ(n) and mk=ω(n^(2/3)log(n)), with each diagonal block probability differing from every off-diagonal probability.One condition applies to every k∈[K]; another applies only to k≠1.Source: R When the Model Parameters are Unknown · pp. 10–11
- Both nomination schemes remain consistent when model parameters and block sizes are estimated from seed vertices, under their respective stated assumptions.For each scheme, the corresponding theorem gives expected average precision tending to 1.Source: R When the Model Parameters are Unknown · pp. 10–11
- Consistency is possible even when the seeds form a vanishing fraction of the graph.The paper also reports accurate practical nomination with just a handful of seeds.Source: R When the Model Parameters are Unknown · pp. 10–11
5 Model Generalizations
The paper extends its nomination schemes to weighted-edge models and vertex-annotated graphs. It describes how feature information enters seeded graph matching and identifies unresolved choices in feature weighting and categorical-data handling.
5 Model Generalizations
- The schemes extend to bounded canonical exponential-family SBMs, with consistency analogues when transformed edge data are matched to block parameters.The stated extension uses T(A_ij) for the edge data and θ_b(i),b(j) for the block-parameter matrix.Source: §5 · pp. 11–12
- Conditionally independent vertex features can enter seeded graph matching through a linear term weighted against network topology by λ.The feature densities are estimated by block and incorporated into the matching problem.Source: §5 · p. 12
- Choosing λ remains unresolved: a value near the number of nonseed vertices worked reliably, but the best choice likely depends on graph structure and feature predictiveness.The authors leave a more thorough investigation of λ selection for future work.Source: §5 · p. 13
- Handling categorical feature data and exploring related approaches are left for future work.Source: §5 · p. 14
6 Experiments
Experiments compare vertex-nomination methods on one synthetic SBM and four real-world graphs, using known and estimated model parameters. Performance varies by graph structure and scale; in Florida Bay, combining features with graph matching improves nomination over features alone.
6.1 Simulations
- In the 500-vertex SBM, ML remains ahead of spectral nomination with known or unknown parameters, while spectral improves over chance and restricted-focus ML is slightly worse.For small graphs, canonical nomination is strongest when tractable; ML nearly matches it, and restricted-focus ML trails ML by less than 0.1 AP.Source: §6.1 · p. 16
6.2 Word Co-occurrences
- On the linguistic graph, known-parameter ML is near-perfect with at least 20 seeds; unknown-parameter ML is also nearly perfect at that seed count, while unprojected spectral nomination stays near chance.The graph’s adjective–noun block structure is disassortative, and sphere projection is important for successful spectral retrieval.Source: §6.2 · p. 17
6.3 Zachary’s Karate Club
- On Zachary’s karate network, spectral nomination performs nearly perfectly across seed counts, while ML is competitive when parameters are known and approaches comparable AP with at least 20 seeds when unknown.The graph’s two factions are naturally separated, making it well-suited to spectral methods.Source: §6.3 · pp. 18–19
6.4 Political Blogs
- On political blogs, spectral nomination is nearly perfect above 10 seeds when sphere-projected; ML becomes competitive at 50 known-parameter seeds or 500 unknown-parameter seeds.In the unknown-parameter case, restricted-focus ML has higher AP than ML, although their ARI shows no such gap.Source: §6.4 · p. 20
6.5 Ecological Network
- In Florida Bay, feature-plus-graph matching improves average precision by about 0.1 over features alone for 8, 16, and 32 seeds.Graph-only ML and spectral methods improve little over chance except when most labels are observed.Source: §6.5 · p. 21
7 Discussion and Future Work
The paper establishes consistency for maximum-likelihood and restricted-focus vertex nomination, and extends ML nomination to graphs with features. Experiments show that method choice depends on graph size and structure, with scalability limiting full ML on very large graphs.
7 Discussion and Future Work
- The paper establishes consistency for ML and restricted-focus ML, whose exactly solvable optimization uses less graph information, and introduces ML nomination for vertex features and possibly weighted edges.The methods rely on quickly approximating seeded graph matching.Source: §7 · p. 22
- The best method depends on graph size and structure: full ML is intractable for graphs with tens of thousands of vertices, but detects signal missed by spectral methods on smaller and medium graphs.Restricted-focus ML is also competitive with spectral methods, though less consistently than full ML.Source: §7 · p. 22
- Full ML can outperform spectral nomination when graph structure violates typical spectral assumptions, as in the linguistic data set.The authors identify determining which methods suit which graphs as a direction for further study.Source: §7 · p. 22
A Proof Details
The proof details establish consistency by controlling incorrect permutations, first for known model parameters and then for seed-based estimates. The restricted-focus result follows a similar argument, while its proof details are abbreviated.
A Proof Details
- For known parameters, the proof derives a summable bound on the probability of a bad permutation, so consistency follows by the Borel-Cantelli lemma.The argument considers permutations that move vertices across blocks.Source: A Proof Details · p. 23
- Cross-block permutation cycles contribute at least αβ to the expected loss, and Hoeffding’s inequality bounds deviations of the sum of independent bounded variables.The proof states that cycle contributions are nonnegative and the variables lie in [−c, c].Source: A Proof Details · pp. 23–24
- The restricted-focus consistency proof follows the known-parameter ML argument with a key difference, but the proof sketch omits its details.The excerpt does not specify the difference.Source: A Proof Details · p. 25
- With unknown parameters, consistency is proved when each block has Θ(n) vertices and the smallest seed count grows faster than √(n_k log(n_k)).The proof estimates model parameters using seed vertices.Source: A Proof Details · p. 26
- The unknown-parameter restricted-focus result combines the proof approaches for the known-parameter restricted-focus and unknown-parameter ML theorems.Theorem 10’s proof is given as a sketch.Source: A Proof Details · p. 27