Pith. sign in

REVIEW 4 major objections 4 minor 71 references

Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that monophonic halfspaces, graph analogues of Euclidean halfspaces, can be separated, compressed, and learned in polynomial time through a 2-SAT-based cell decomposition.

desk verdict Strong learning results for monophonic halfspaces, but the central 2-SAT proof needs tightening before I'd fully trust it. read the letter →

arxiv 2506.23186 v1 pith:33RLH2II submitted 2025-06-29 cs.LG cs.DMmath.COstat.ML

Marco Bressan , Victor Chepoi , Emmanuel Esposito , Maximilian Thiessen This is my paper · ORCID
classification cs.LGcs.DMmath.COstat.ML MSC 05C7568Q3268R1052A01
keywords monophonicconvexitygraphhalfspaces2-SATdecompositionshadow-cellPAClearningsamplecompressionactiveonline
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Monophonic halfspaces are the graph analogue of Euclidean halfspaces: a set of vertices whose induced-path closure stays on both sides. This paper's central claim is that these halfspaces are algorithmically tractable everywhere, in stark contrast to geodesic halfspaces whose separation problem is NP-hard. The vehicle is a 2-SAT based decomposition theorem that represents every monophonic halfspace as a disjoint union of small 'cells' derived from a shadow closure. From that decomposition the authors derive polynomial-time algorithms for separation, empirical risk minimization, sample compression, active, online, and teaching learning, all with near-optimal sample or query complexity. If the decomposition holds, monophonic halfspaces become one of the few nontrivial graph concept classes that are efficiently PAC-learnable at the optimal rate.

What carries the argument

The central object is the shadow-cell decomposition of monophonic halfspaces. Starting from an edge ab, one computes the shadow closure (A*,B*) of the pair ({a},{b}) by iterating m(X/Y), the monophonic hull of the shadow of X with respect to Y. The remaining vertices R = V \ (A* ∪ B*) are grouped into cells: equivalence classes of variables in a 2-SAT formula Φ whose satisfying assignments are in bijection with the halfspaces separating A* and B*. The structure lemma (Proposition 17) shows that the directed graphs of implications between cells are either empty, have a single source with all other cells forced, or form a linear quasiorder; in all cases each halfspace is a conflict-free lower set of cells. This decomposition is computable in polynomial time and supports operations such as choosing the better of each twin pair for a labeled sample, which is exactly what makes ERM and the other learning algorithms efficient.

What would settle it

Implement the reduction on all graphs up to, say, 8 vertices: for each edge ab compute the shadow-closed pair (A*,B*) and enumerate all satisfying assignments of Φ; then brute-force check whether each assignment's H = A* ∪ {x : α(x)=1} is an m-halfspace and whether every m-halfspace separating a and b arises this way. Any mismatch falsifies Theorem 6 and, with it, the decomposition and the learning guarantees. As a targeted check, look for a vertex x0 in ∂R that fails Lemma 7's adjacency to ∂BA ∪ ∂AB, or a cell C with |C| > 2ω(G), both of which would break the proofs of Lemma 12.

Watch

Extended reading notes

Core claim

The paper establishes that the halfspace separation problem for monophonic convexity admits a polynomial-time algorithm (Theorem 3), reducing the search for a separating halfspace to checking satisfiability of a 2-SAT formula built from a shadow-closed osculating pair. The deeper structural result is Theorem 10: every m-halfspace that contains a and avoids b can be written, in a unified way, as the union of a fixed core A* plus selected cells from a linear sequence, where each cell is chosen from a pair of 'twin' cells; equivalently (Theorem 20) the chosen cells form a conflict-free lower set in a partial order on cells. This cell decomposition is the engine behind the paper's algorithmic results: it yields a polynomial-time empirical risk minimizer (Theorem 38), an efficient stable proper sample compression scheme of size 4ω(G) (Theorem 33), a tight VC-dimension estimate up to an additive constant (Theorem 23), and polynomial-time active, online, and teaching learners with near-optimal guarantees (Theorems 40, 43, 42). It also answers the open question of whether a graph admits a bipartition into two m-convex sets in polynomial time (Corollary 4).

Load-bearing premise

The load-bearing premise is Theorem 6's claim that the 2-SAT formula Φ exactly encodes which subsets of the residue form complementary monophonic halfspaces, which in turn depends on Lemma 7's adjacency assertion and on the implication constraints implying the equality constraints; the proof of Lemma 12(3) appears to conflate cell size with boundary size, a warning that the technical claims deserve scrutiny, and if any of these fails, the cell decomposition and every learning result built on it collapses.

Editorial extensions

If this is right

  • Monophonic halfspaces admit a polynomial-time empirical risk minimizer, so agnostic PAC learning of Hm(G) has the optimal Θ((d + log(1/δ))/ε²) sample complexity in polynomial time (Theorem 38 and Corollary 39).
  • In the realizable setting, the class is PAC-learnable with O((min{ω(G), d log(1/ε)} + log(1/δ))/ε) samples, reaching the optimal 1/ε rate when d and ω(G) are comparable (Theorem 37).
  • Active learning of m-halfspaces can be done in polynomial time with O(hull(G) + log diam(G) + log ω(G) + d) membership queries, matching lower bounds on S3 graphs up to constants (Theorem 40 and Proposition 41).
  • Online learning is possible in polynomial time with O(d log n) mistakes via Winnow, or in 2^d poly(n) time with O(d + log n) mistakes via Halving (Theorem 43).
  • The teaching dimension and recursive teaching dimension of Hm(G) are both at most 2d+2, supporting the general conjecture that RTD is linear in the VC-dimension (Theorem 42).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: Because the cell decomposition gives an explicit bijection between halfspaces and conflict-free lower sets, one can sample m-halfspaces approximately uniformly by random selection of such lower sets, a tool the paper does not develop.
  • Inference: The compression scheme's reliance on Carathéodory number 2 (rather than the 2-SAT machinery) suggests that any graph convexity with Carathéodory number at most 2 admits a stable, proper LSCS of size O(ω(G)), which would generalize Theorem 33 beyond monophonic convexity.
  • Inference: The paper leaves open whether Hm(G) has a labeled compression scheme of size O(d) (the Floyd–Warmuth conjecture); the twin-cell structure of the decomposition is a natural starting point for a construction, and a counterexample would likely come from a graph where cells have size much smaller than ω(G).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies monophonic halfspaces of a graph G, i.e., sets H such that both H and V\H are closed under induced paths. Its central structural claim is a 2-SAT characterization (Theorem 6) of all halfspaces separating a shadow-closed osculating pair (A,B), from which it derives a cell-decomposition theorem (Theorem 10). On top of this decomposition the paper gives a polynomial-time halfspace separation algorithm (Theorem 3), a polynomial-time ERM algorithm (Theorem 38), a VC-dimension characterization up to an additive constant (Theorem 23), a bound of |Hm(G)| ≤ m2^d + 2, and polynomial-time algorithms for active, online, and teaching with near-optimal rates. Independently of the decomposition, it gives a proper stable sample compression scheme of size 4ω(G) (Theorem 33), yielding an optimal-rate realizable PAC learner.

Significance. If the structural chain is correct, this is a substantial result: it resolves the k=2 monophonic convex partition question of González et al. (2020), contrasts sharply with NP-hardness for geodesic halfspaces, and provides one of the few polynomial-time ERM algorithms for a nontrivial graph hypothesis class. The compression scheme is an independent, elegant use of mutual imprints and Carathéodory number 2. However, the correctness of the learning theorems rests on Theorem 6 and Theorem 10; as detailed below, several load-bearing steps in the proof of Theorem 6 are asserted rather than proved, and Lemma 12(3) contains a technical error. These are repairable in my assessment, but they must be fixed before the results can be accepted.

major comments (4)
  1. [§3.2, Theorem 6 proof, (iii)⇒(i)] The proof asserts 'Since the pair (A,B) is shadow-closed, d(x,a)=d(x,b)' without justification. This equality is used to conclude x0 ∈ m(x,a) ∩ m(x,b) and hence x0 ∈ Sx, so it is load-bearing. A proof can be supplied: if d(x,a) < d(x,b), then a shortest a-x path together with the edge ab is an induced b-x path because any chord from b to an internal vertex would give d(b,x) ≤ d(a,x); hence a ∈ m(b,x), forcing x ∈ A/B = A, a contradiction; the other inequality is symmetric. This argument must appear in the text.
  2. [§3.2, Theorem 6 proof, (iii)⇒(i)] The same paragraph chooses x0 as the neighbor of a on a shortest a-x path and invokes Lemma 7 to infer x0 ∼ b. Lemma 7 applies only to vertices of ∂R, while x0 may lie in A if the shortest path does not leave A immediately. The text must prove that the first vertex of the path in R is at distance 1 from a; one can do so by applying Lemma 7 to that first vertex and comparing the resulting b-x path with d(x,b)=d(x,a). As written, the membership x0 ∈ Sx is not established.
  3. [Lemma 7, proof] The concatenated path P'' is asserted to be induced, but chords from b to internal vertices of P' are not excluded. Either prove that no such chord exists, or argue that any such chord yields an induced x0-b path through A (for example b-w-z-x0), which still gives x0 ∈ A/B. This case distinction is missing and should be supplied, since Lemma 7 underpins the boundary-adjacency and Sx-separator arguments used in Theorem 6.
  4. [Lemma 12(3)] The proof of Lemma 12(3) derives |C| ≤ |∂R| from the fact that C intersects ∂R, which is invalid because a cell C may contain vertices outside ∂R. As stated, the bound |C| ≤ 2ω(G) is not established; the argument proves at most |∂C| ≤ ω(G). This affects the use of Lemma 12 in Theorem 40, where the inequality p ≤ 2ω(G) is needed, so the statement or its application must be corrected.
minor comments (4)
  1. [§4.1, definition of equivalent variables] The definition of equivalent variables contains a typo: the second alternative should read 'or if ax = ¬ay in all solutions', not a repetition of 'ax = ay in all solutions'.
  2. [§5.2, Proposition 30, linear quasiorder case] The line 'By Theorem 10 we have |Hm(ab)| = 2q' appears to be a typo; for p antichains the count is a sum over ℓ of 2^{|C_ℓ|}, so a factor of p enters. The subsequent edge-counting argument should be written out carefully to show that this factor cancels and yields |Hm(G)| ≤ m2^d.
  3. [Algorithm 1, line 5] Algorithm 1 refers to Sx at line 5, but Sx is not defined until Section 3.2; a forward reference or a one-sentence definition at the algorithm would help readability.
  4. [Minor typos] There are several typos: 'halfspcaes' in the Section 8 heading, 'stategies' in Section 7, 'reminders' in Section 4.3, 'aell' in Lemma 27, and 'H^c(ab)' in the proof of Lemma 13, which should be 'Hm(ab)'.

Circularity Check

1 steps flagged · score 2.0 of 10

Minor load-bearing self-citation in the shadow-closure lemma; otherwise the derivation is self-contained.

  1. self citation load bearing [Section 3.1, Lemma 5]
    "Lemma 5 (Chepoi 2024) Let A, B⊆ V and H ∈ Hm(G). If A ⊆ H and B ⊆ H c, then m(A/B) ⊆ H and m(B/A) ⊆ H c."

    This lemma is the load-bearing justification for replacing the input pair (A,B) by its shadow closure: HalfspaceSep computes (A*,B*) = ShadowClosure(...) and only then builds the 2-SAT formula Φ, while Theorem 6 (and hence Theorem 10, ERM, VC-dimension, active/online/teaching bounds) applies only to a shadow-closed pair. The lemma is attributed to Chepoi 2024, a co-author, and is not proved in the present text; the paper says 'It is not hard to prove that the converse holds as well' and then cites it. Thus the correctness of the reduction rests on a self-citation rather than on an internal argument. This is a minor self-citation at a load-bearing point, but it is not a definitional equivalence and the subsequent 2-SAT-to-cell derivation is self-contained.

full rationale

The central derivation is a theorem chain: shadow closure (Lemma 5) → 2-SAT characterization (Theorem 6) → cell decomposition (Theorems 10, 20, 21) → algorithmic consequences (Theorems 23, 33, 38, 40, 42, 43). No step in the latter part fits a parameter to a target quantity and then calls it a prediction; the 2-SAT solutions are shown to be in bijection with halfspaces, and the cell decomposition is derived from equivalence classes of those solutions rather than assumed. The compression scheme is independent of the decomposition. The only circularity-adjacent issue is the imported Lemma 5, attributed to a co-author and used without proof to justify the reduction to shadow-closed pairs required by Theorem 6. This is a load-bearing self-citation, but it does not make the main claims equivalent to their inputs by construction, and the skeptical concerns about the proof of Theorem 6(iii)⇒(i) are correctness risks rather than circularity. Hence a score of 2 is appropriate.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper is pure theory: there are no fitted constants or parameters. The central claims rely on prior results about monophonic convexity (Carathéodory number 2, polynomial-time hulls), standard 2-SAT algorithms, and an external halfspace-separation algorithm by Chepoi (2024) whose correction is not reproduced. These are imported as axioms rather than proved in the paper.

assumptions (5)
  • domain assumption The Carathéodory number of monophonic convexity is at most 2 (Lemma 1(2), attributed to Duchet 1988 and Farber-Jamison 1986).
    Used to bound the m-hull of imprints by 2|X'| points; the 4ω(G) compression scheme and several hull arguments depend on it. The paper does not re-prove it.
  • domain assumption m-hulls, shadows, and minimum hull sets are computable in polynomial time (Lemma 1(4)-(5), attributed to Dourado et al. 2010).
    Used by ShadowClosure, by the compression compressor, and by the active learner; if this failed the claimed runtimes collapse.
  • domain assumption A corrected version of Chepoi's (2024) halfspace separation algorithm is correct and polynomial (used in Theorem 3, Section 3).
    The paper says it uses the 'slightly corrected' third solution, but the correction is not stated, so Theorem 3 rests on an external manuscript.
  • standard math Duchet's Lemmas 6.3 and 6.4 (clique replacement for almost-shattered sets) hold as cited (used in Lemmas 26-28).
    The VC-dimension upper bound d ≤ d̂ + 4 depends on these external structural lemmas.
  • standard math Standard 2-SAT algorithmic facts: satisfiability and variable-equivalence classes are computable in polynomial time (Aspvall et al. 1979; Feder 1995).
    Used throughout Sections 3-4 to construct and solve Φ and to extract cells.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs." pith.science (2026). https://pith.science/paper/33RLH2II

@misc{pith2026250623186,
  author       = {Pith},
  title        = {Pith review of: Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/33RLH2II}},
  note         = {Machine review of arXiv:2506.23186}
}
abstract

Abstract notions of convexity over the vertices of a graph, and corresponding notions of halfspaces, have recently gained attention from the machine learning community. In this work we study monophonic halfspaces, a notion of graph halfspaces defined through closure under induced paths. Our main result is a $2$-satisfiability based decomposition theorem, which allows one to represent monophonic halfspaces as a disjoint union of certain vertex subsets. Using this decomposition, we achieve efficient and (nearly) optimal algorithms for various learning problems, such as teaching, active, and online learning. Most notably, we obtain a polynomial-time algorithm for empirical risk minimization. Independently of the decomposition theorem, we obtain an efficient, stable, and proper sample compression scheme. This makes monophonic halfspaces efficiently learnable with proper learners and linear error rate $1/\varepsilon$ in the realizable PAC setting. Our results answer open questions from the literature, and show a stark contrast with geodesic halfspaces, for which most of the said learning problems are NP-hard.

Figures

Figures reproduced from arXiv: 2506.23186 by the authors.

Figure 1
Figure 1. A toy graph G partitioned into a monophonic halfspace H (in blue) and its complement Hc (in orange). The diamond-shaped vertices form the boundaries ∂H and ∂Hc and are cliques, see Lemma 1(1). G[A] = (A, E′ ) such that uv ∈ E′ if and only if uv ∈ E. A clique is a complete subgraph of G. For an edge uv, denote by ∆uv the set N[u] ∩ N[v] and the subgraph induced by this set. Let ω(G) denote the clique number of G. A s… view at source ↗
Figure 2
Figure 2. Visualization of the cell decomposition. Vertices are partitioned into cells (the oval halves). We first choose a block Cℓ . In this block an arbitrary selection of either C ′ i or C ′′ i for each i is valid. In the blocks before Cℓ each first half C ′ i must be selected and in blocks after Cℓ each second half C ′′ i must be selected. The union of any such combination of cells yields a valid m-halfspace (see Theorem… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 69 canonical work pages

  1. [1]

    Afshani, E

    P. Afshani, E. Chiniforooshan, R. Dorrigiv, A. Farzan, M. Mirzazadeh, N. Simjour, and H. Zarrabi-Zadeh. On the complexity of finding an unknown cut via vertex queries. In Computing and Combinatorics, 2007

    work page 2007

  2. [2]

    D. Angluin. Queries and concept learning. Mach. Learn, 2: 0 319--342, 1988

    work page 1988

  3. [3]

    Aspvall, M

    B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8: 0 121--123, 1979

    work page 1979

  4. [4]

    H.-J. Bandelt. Graphs with intrinsic s_3 convexities. J. Graph Th., 13: 0 215--228, 1989

    work page 1989

  5. [5]

    J. M. Barzdin. On the prediction of general recursive functions. Soviet Math. Dokl., 13: 0 1224--1228, 1972

    work page 1972

  6. [6]

    Ben - David and A

    S. Ben - David and A. Litman. Combinatorial variability of V apnik- C hervonenkis classes with applications to sample compression schemes. Discrete Appl. Math., 86: 0 3--25, 1998

    work page 1998

  7. [7]

    Bj\"orner, M

    A. Bj\"orner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, Cambridge, 1993

    work page 1993

  8. [8]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the V apnik- C hervonenkis dimension. Journal of the ACM, 36: 0 929--965, 1989

    work page 1989

Show all 71 references
  1. [9]

    B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In COLT, 1992

    1992

  2. [10]

    Bousquet, S

    O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy. Proper learning, H elly number, and an optimal SVM bound. In COLT , 2020

    2020

  3. [11]

    Bressan, N

    M. Bressan, N. Cesa-Bianchi, S. Lattanzi, and A. Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. In COLT, 2021

    2021

  4. [12]

    Bressan, E

    M. Bressan, E. Esposito, and M. Thiessen. Efficient algorithms for learning monophonic halfspaces in graphs. In COLT, 2024

    2024

  5. [13]

    Cesa-Bianchi, C

    N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella. Active learning on trees and graphs. In COLT, 2010

    2010

  6. [14]

    Cesa-Bianchi, C

    N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella. Random spanning trees and the prediction of weighted graphs. J. Mach. Learn. Res., 14: 0 1251--1284, 2013

    2013

  7. [15]

    Chalopin, V

    J. Chalopin, V. Chepoi, S. Moran, and M. K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. JCSS, 127: 0 1--28, 2022

    2022

  8. [16]

    Chalopin, V

    J. Chalopin, V. Chepoi, F. Mc Inerney , S. Ratel, and Y. Vax\` e s. Sample compression schemes for balls in graphs. SIAM J. Discr. Math. , 37: 0 2585--2616, 2023

    2023

  9. [17]

    Chalopin, V

    J. Chalopin, V. Chepoi, F. Mc Inerney, and S. Ratel. Non-clashing teaching maps for balls in graphs. In COLT, 2024

    2024

  10. [18]

    Changat, H

    M. Changat, H. M. Mulder, and G. Sierksma. Convexities related to path properties on graphs. Discrete Math., 290: 0 117--131, 2005

    2005

  11. [19]

    V. Chepoi. Some properties of domain finite convexity structures (in russian). Results on Algebra, Geometry and Appl. (Moldova State University), pages 142--148, 1986

    1986

  12. [20]

    V. Chepoi. Separation of two convex sets in convexity structures. J. Geom., 50: 0 30--51, 1994

    1994

  13. [21]

    V. Chepoi. Separation axiom S_3 for geodesic convexity in graphs. arXiv:2405.07512, 2024

    2024 arXiv

  14. [22]

    Chepoi, B

    V. Chepoi, B. Estellon, and Y. Vaxes. Covering planar graphs with a fixed number of balls. Discrete Comput. Geom., 37: 0 237--244, 2007

    2007

  15. [23]

    Chepoi, K

    V. Chepoi, K. Knauer, and M. Philibert. Labeled sample compression schemes for complexes of oriented matroids. JCSS, 144: 0 103543, 2024

    2024

  16. [24]

    Coudert, M

    D. Coudert, M. Csik \' o s, G. Ducoffe, and L. Viennot. Practical computation of graph VC -dimension. In SEA 2024 , pages 8:1--8:20, 2024

    2024

  17. [25]

    Darnst \"a dt

    M. Darnst \"a dt. The optimal PAC bound for intersection-closed concept classes. Inf. Process. Lett., 115 0 (4): 0 458--461, 2015

    2015

  18. [26]

    Dasarathy, R

    G. Dasarathy, R. Nowak, and X. Zhu. S ^2 : An efficient graph based active learning algorithm with application to nonparametric classification. In COLT, 2015

    2015

  19. [27]

    M. C. Dourado, F. Protti, and J. L. Szwarcfiter. Complexity results related to monophonic convexity. Discrete Appl. Math., 158: 0 1268--1274, 2010

    2010

  20. [28]

    P. Duchet. Convex sets in graphs, II . M inimal path convexity. J. Combin. Theory, Ser. B, 44 0 (3): 0 307--316, 1988

    1988

  21. [29]

    Duchet and H

    P. Duchet and H. Meyniel. Ensemble convexes dans les graphes I : Th \'e or \`e mes de H elly et de R adon pour graphes et surfaces. European J. Combin., 4: 0 127--132, 1983

    1983

  22. [30]

    A general lower bound on the number of examples needed for learning

    Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Inf.&Com., 82 0 (3): 0 247--261, 1989

    1989

  23. [31]

    Elaroussi, L

    M. Elaroussi, L. Nourine, and S. Vilmin. Half-space separation in monophonic convexity. In MFCS, pages 51:1--51:16, 2024

    2024

  24. [32]

    Farber and R

    M. Farber and R. E. Jamison. Convexity in graphs and hypergraphs. SIAM J. Algebr. Discr. Meth., 7: 0 433--444, 1986

    1986

  25. [33]

    Stable networks and product graphs

    Tom \'a s Feder. Stable networks and product graphs. American Mathematical Soc., 1995

    1995

  26. [34]

    Floyd and M

    S. Floyd and M. K. Warmuth. Sample compression, learnability, and the V apnik- C hervonenkis dimension. Mach. Learn., 21: 0 269--304, 1995

    1995

  27. [35]

    Gentile, M

    C. Gentile, M. Herbster, and S. Pasteris. Online similarity prediction of networked data from known and unknown graphs. In COLT, 2013

    2013

  28. [36]

    Glantz and H

    R. Glantz and H. Meyerhenke. On finding convex cuts in general, bipartite and plane graphs. Theor. Comput. Sci, 695: 0 54--73, 2017

    2017

  29. [37]

    S. A. Goldman and M. J. Kearns. On the complexity of teaching. JCSS, 50: 0 20--31, 1995

    1995

  30. [38]

    L. M. Gonz \'a lez, L. N. Grippo, M. D. Safe, and V. F. dos Santos. Covering graphs with convex sets and partitioning graphs into convex sets. Inf. Process. Lett., 158, 2020

    2020

  31. [39]

    Guillory and J

    A. Guillory and J. A. Bilmes. Label selection on graphs. In NIPS, 2009

    2009

  32. [40]

    S. Hanneke. An analysis of graph cut size for transductive learning. In ICML, 2006

    2006

  33. [41]

    Heged u s

    T. Heged u s. Generalized teaching dimensions and the query complexity of learning. In COLT, 1995

    1995

  34. [42]

    Herbster, M

    M. Herbster, M. Pontil, and L. Wainer. Online learning over graphs. In ICML, 2005

    2005

  35. [43]

    Herbster, S

    M. Herbster, S. Pasteris, and S. Ghosh. Online prediction at the limit of zero temperature. NIPS, 2015

    2015

  36. [44]

    Kleinberg

    J. Kleinberg. Detecting a network failure. Internet Math., 1: 0 37--55, 2004

    2004

  37. [45]

    Kuzmin and M

    D. Kuzmin and M. K. Warmuth. Unlabeled compression schemes for maximum classes. J. Mach. Learn. Res., 8: 0 2047--2081, 2007

    2007

  38. [46]

    Le and C

    H. Le and C. Wulff-Nilsen. VC set systems in minor-free (di) graphs and applications. In SODA, 2024

    2024

  39. [47]

    B.-Q. Li, J. You, L. Chen, J. Zhang, N. Zhang, H.-P. Li, T. Huang, X.-Y. Kong, and Y.-D. Cai. Identification of lung-cancer-related genes with the shortest path approach in a protein-protein interaction network. BioMed research international, 2013: 0 267375, 2013

    2013

  40. [48]

    Littlestone

    N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2: 0 285--318, 1988

    1988

  41. [49]

    Littlestone and M

    N. Littlestone and M. Warmuth. Relating data compression and learnability. Technical report, University of California, Santa Cruz, 1986

    1986

  42. [50]

    F. M. Malvestuto, M. Mezzini, and M. Moscarini. Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent. Discr. Math., Alg. Appl., 4: 0 1250063, 2012

    2012

  43. [51]

    Minsky and S

    M. Minsky and S. Papert. Perceptrons. MIT Press, 1987

    1987

  44. [52]

    Moran and M

    S. Moran and M. K. Warmuth. Labeled compression schemes for extremal classes. In ALT , 2016

    2016

  45. [53]

    Moran and A

    S. Moran and A. Yehudayoff. Sample compression schemes for VC classes. Journal of the ACM , 63: 0 21:1--21:10, 2016

    2016

  46. [54]

    I. M. Pelayo. Geodesic convexity in graphs. Springer Briefs in Mathematics. Springer, 2013

    2013

  47. [55]

    Pelckmans, J

    K. Pelckmans, J. Shawe-Taylor, J. A.K. Suykens, and B. De Moor. Margin based transductive graph cuts using linear programming. In AISTATS, 2007

    2007

  48. [56]

    B. I. P. Rubinstein and J. H. Rubinstein. A geometric approach to sample compression. J. Mach. Learn. Res., 13: 0 1221--1261, 2012

    2012

  49. [57]

    J. H. Rubinstein and B. I. P. Rubinstein. Unlabelled sample compression schemes for intersection-closed classes and extremal classes. In NeurIPS, 2022

    2022

  50. [58]

    Seiffarth, T

    F. Seiffarth, T. Horv \'a th, and S. Wrobel. Maximal closed set and half-space separations in finite closure systems. Theor. Comput. Sci, 973: 0 114105, 2023

    2023

  51. [59]

    Shalev-Shwartz and S

    S. Shalev-Shwartz and S. Ben-David. Understanding M achine L earning: From T heory to A lgorithms . Cambridge Univ. Press, 2014

    2014

  52. [60]

    H.U. Simon. RTD -conjecture and concept classes induced by graphs. arXiv:2502.05453, 2025

    2025 arXiv

  53. [61]

    Simon and S

    H.U. Simon and S. Zilles. Open problem: R ecursive teaching dimension versus VC dimension. In COLT, 2015

    2015

  54. [62]

    Self-directed node classification on graphs

    Georgy Sokolov, Maximilian Thiessen, Margarita Akhmejanova, Fabio Vitale, and Francesco Orabona. Self-directed node classification on graphs. In ALT, 2025

    2025

  55. [63]

    S ubelj, D

    L. S ubelj, D. Fiala, T. Ciglari c , and L. Kronegger. Convexity in scientific collaboration networks. J. Informetr., 13: 0 10--31, 2019

    2019

  56. [64]

    Talagrand

    M. Talagrand. Sharper bounds for G aussian and empirical processes. Ann. Probab., 22: 0 28--76, 1994

    1994

  57. [65]

    Thiessen and T

    M. Thiessen and T. G \"a rtner. Active learning of convex halfspaces on graphs. NeurIPS, 2021

    2021

  58. [66]

    Thiessen and T

    M. Thiessen and T. G \"a rtner. Online learning of convex sets on graphs. In ECMLPKDD, 2022

    2022

  59. [67]

    L. G. Valiant. A theory of the learnable. Comm. of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  60. [68]

    M. L. J. van de Vel. Theory of C onvex S tructures . North Holland, 1993

    1993

  61. [69]

    Vapnik and A

    V. Vapnik and A. Y. Chervonenkis. Theory of P attern R ecognition . Nauka, Moscow, 1974

    1974

  62. [70]

    Zhou, M.-C

    X. Zhou, M.-C. J. Kao, and W. H. Wong. Transitive functional annotation by shortest-path analysis of gene expression data. Proc. Natl. Acad. Sci. U.S.A., 99: 0 12783--12788, 2002

    2002

  63. [71]

    Zilles, S

    S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Models of cooperative teaching and learning. J. Mach. Learn. Res., 12: 0 349--384, 2011

    2011

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.