summaries: The authors study the problem of  learning geodesically convex halfspaces on graphs within an active learning setting. They propose a new algorithm and rigorously analyzed it by showing lower and upper bounds of the query complexity. They also carry out an experimental evaluation to validate their theoretical results.

summaries: This paper presents novel bounds on the query complexity of learning halfspaces on graphs via convex analysis. Two general upper-bounds were derived along with a simple general lower bound based on extreme vertices. Based on these bounds, the authors developed two querying strategies based on greedy and selective sampling approaches. One interesting practical aspect of the proposed active learning algorithm is the evidence that ground-truth communities in real-world graphs are typically convex. The proposed bounds are compared to previous results based on the cut-size, which show that the halfspace assumption enables learning with large cuts, whereas previous bounds become less applicable.

summaries: This paper studies the query complexity of learning geodesically convex halfspaces on graphs.  In the present context, a geodesically convex set of a graph $G = (V,E)$ is a subset $C$ of $V$ such that each shortest path containing any two vertices of $C$ is contained in $C$, and a halfspace of $G$ is any convex set of $G$ whose complement is also convex.  The main contributions are upper and lower bounds for the query complexity of a class of halfspaces on a weighted graph in terms of various graph parameters.  One upper and almost matching lower bound is given in terms of the size of the minimum shortest cover and the graph diameter.  Another upper bound is given in terms of the minimum size of a hull set, the graph diameter and the maximum size of a set $W_{=ab}^*$ of vertices over all pairs $(a,b)$ of vertices, where $W_{=ab}^*$ is defined to be the set of all points that avoid the intersection of rays from $a$ (resp. $b$) to any point neither in the convex hull of $a/b$ nor in that of $b/a$ and are themselves not in these convex hulls.  The size of the set $W_{=ab}^*$ can also be bounded in terms of the treewidth.  It is shown, moreover, that increasingly tighter lower bounds can be obtained as more stringent separation axioms are assumed.

summaries: This work studies the query complexity of active learning geodesically convex halfspaces on graphs (that is given a graph $G=(V,E)$, the class of subsets $S \subseteq V$ such that $S$ and $V \setminus S$ are both convex). While most prior works gave hypothesis-dependent upper bounds, here the authors give two novel worst-case bounds based on natural graph parameters: the first on the smallest shortest path cover, the second on the hull size, diameter, and tree-width. While neither algorithm is computationally efficient in its original form, the former can be efficiently approximated to within a (multiplicative) logarithmic factor in the diameter, and the latter can be computed efficiently on graphs with bounded tree-width.  The authors also prove a complementary series of lower bounds. The first show both bounds are tight in a weak sense for general graphs in the sense that there exist examples matching the upper bound. They then provide a series of lower bounds based on four (successively stronger) standard convexity properties of the underlying graph $G$. Their final (and tightest) bound holds for graphs on which every two disjoint convex sets are halfspace separable. In this case the only gap between the upper and lower bounds is that between the Radon number and Tree-width of the graph. The authors also provide a number of reasonably natural classes on which their bounds are exactly tight, including trees, $K_{2,3}$ minor-free graphs, partial cubes, and weakly median graphs.   Finally, the authors provide some experimental motivation for their setting, along with a number of heuristic implementations of their algorithm. They compare performance to two non-trivial baseline algorithms, the label propagation algorithm of Zhu et al. (2003), and the $S^2$ algorithm of Dasarathy et al. (2015), and show preliminary experimental evidence that their algorithm outperforms both.

summaries: The paper studies the problem of active learning on graphs to identify two classes. The main assumption is that the vertices of the same class form a geodesically convex set, and the two classes are halfspace separable.  The authors propose a simple halfspace querying algorithm, and analyzes the upper and lower bounds on the number of queries required to deduce all labels of the graph for binary classification on connected undirected graphs. In particular this number of queries is related to the graph properties and the separation condition between two classes. Furthermore the VC dimension of the hypothesis class is related to the aforementioned properties.

abstractText: We systematically study the query complexity of learning geodesically convex halfspaces on graphs. Geodesic convexity is a natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We prove an upper bound on the query complexity which is linear in the treewidth and the minimum hull set size but only logarithmic in the diameter. We show tight lower bounds along well-established separation axioms and identify the Radon number as a central parameter of the query complexity and the VC dimension. While previous bounds typically depend on the cut size of the labelling, all parameters in our bounds can be computed from the unlabelled graph. We provide evidence that ground-truth communities in real-world graphs are often convex and empirically compare our proposed approach with other active learning algorithms.

authors:
Peyman Afshani
Ehsan Chiniforooshan
Reza Dorrigiv
Arash Farzan
Mehdi Mirzazadeh
Narges Simjour
Hamid Zarrabi-Zadeh

title: On the complexity of finding an unknown cut via vertex queries

venue: In International Computing and Combinatorics Conference,

title: Queries and concept learning

venue: Machine learning,

authors:
Martin Anthony
Joel Ratsaby

title: Large-width bounds for learning half-spaces on distance spaces

venue: Discrete Applied Mathematics,

authors:
Julio Araujo
Victor Campos
Frédéric Giroire
Nicolas Nisse
Leonardo Sampaio
Ronan Soares

title: On the hull number of some graph classes

venue: Theoretical Computer Science,

authors:
Julio Araujo
Gregory Morel
Leonardo Sampaio
Ronan Soares
Valentin Weber

title: Hull number: P5-free graphs and reduction rules

venue: Electronic Notes in Discrete Mathematics,

authors:
Danilo Artigas
Simone Dantas
Mitre C. Dourado
Jayme L. Szwarcfiter

title: Partitioning a graph into convex sets

venue: Discrete Mathematics,

title: Graphs with intrinsic s3 convexities

venue: Journal of graph theory,

authors:
Hans-Jürgen Bandelt
Victor Chepoi

title: Metric graph theory and geometry: a survey

venue: Contemporary Mathematics,

authors:
Avrim Blum
Shuchi Chawla

title: Learning from labeled and unlabeled data using graph mincuts

venue: In ICML,

authors:
Avrim Blum
Sariel Har-Peled
Benjamin Raichel

title: Sparse approximation via generating point sets

venue: Transactions on Algorithms,

title: A linear-time algorithm for finding tree-decompositions of small treewidth

venue: SIAM Journal on computing,

authors:
Hans L. Bodlaender
Jan van Leeuwen
Richard Tan
Dimitrios M. Thilikos

title: On interval routing schemes and treewidth

venue: Information and computation,

authors:
Bernhard E. Boser
Isabelle M. Guyon
Vladimir Vapnik

title: A training algorithm for optimal margin classifiers

venue: In COLT,

authors:
Marco Bressan
Nicolò Cesa-Bianchi
Silvio Lattanzi
Andrea Paudice

title: Exact recovery of clusters in finite metric spaces using oracle queries

title: Separation of two convex sets in convexity structures

venue: Journal of Geometry,

authors:
Erika M.M. Coelho
Mitre C. Dourado
Rudini M. Sampaio

title: Inapproximability results for graph convexity parameters

authors:
David Cohn
Les Atlas
Richard Ladner

title: Improving generalization with active learning

title: Complexity theoretic limitations on learning halfspaces

venue: In STOC,

authors:
Gautam Dasarathy
Robert Nowak
Xiaojin Zhu

title: An efficient graph based active learning algorithm with application to nonparametric classification

title: Coarse sample complexity bounds for active learning

venue: In NIPS,

authors:
Paulo H.M. de Araújo
Manoel Campêlo
Ricardo C. Corrêa
Martine Labbé

title: The geodesic classification problem on graphs

venue: Electronic Notes in Theoretical Computer Science,

authors:
Ilias Diakonikolas
Themis Gouleakis
Christos Tzamos

title: Distribution-independent PAC learning of halfspaces with Massart noise

venue: NeurIPS,

authors:
Mitre C. Dourado
John G. Gimbel
Jan Kratochvíl
Fábio Protti
Jayme L Szwarcfiter

title: On the computation of the hull number of a graph

authors:
Pierre Duchet
Henry Meyniel

title: Ensemble convexes dans les graphes

venue: i: Théorèmes de Helly et de Radon pour graphes et surfaces. European Journal of Combinatorics,

title: The use of multiple measurements in taxonomic problems

venue: Annals of eugenics,

authors:
Thomas Gärtner
Gemma C. Garriga

title: The cost of learning directed cuts

venue: In ECMLPKDD,

authors:
Roland Glantz
Henning Meyerhenke

title: On finding convex cuts in general, bipartite and plane graphs

authors:
Lee-Ad Gottlieb
Robert Krauthgamer

title: Proximity algorithms for nearly doubling spaces

venue: Journal on Discrete Mathematics,

authors:
Max Hopkins
Daniel M. Kane
Shachar Lovett
Gaurav Mahajan

title: Point location and active learning: Learning halfspaces almost optimally

venue: In FOCS,

authors:
Tamás Horváth
Jan Ramon

title: Efficient frequent connected subgraph mining in graphs of bounded tree-width

title: Ein Beweis des Satzes von M. Eidelheit über konvexe Mengen

venue: Proceedings of the Imperial Academy,

authors:
Mamadou Moustapha Kanté
Lhouari Nourine

title: Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs

venue: SIAM Journal on Discrete Mathematics,

authors:
Mamadou Moustapha Kanté
Thiago Marcilon
Rudini Sampaio

title: On the parameterized complexity of the geodesic hull number

authors:
Jure Leskovec
Andrej

title: Krevl. SNAP Datasets: Stanford large network dataset collection

venue: http: //snap.stanford.edu/data,

authors:
Bi-Qing Li
Tao Huang
Lei Liu
Yu-Dong Cai
Kuo-Chen Chou

title: Identification of colorectal cancer related genes with mrmr and shortest path in protein-protein interaction

venue: network. PLoS one,

authors:
Bi-Qing Li
Jin You
Lei Chen
Jian Zhang
Ning Zhang
Hai-Peng Li
Tao Huang
Xiang-Yin Kong
Yu-Dong Cai

title: Identification of lung-cancer-related genes with the shortest path approach in a protein-protein interaction

venue: network. BioMed research international,

authors:
Silviu Maniu
Pierre Senellart
Suraj Jog

title: An experimental study of the treewidth of real-world graph data

venue: In International Conference on Database

title: On the isometric path partition problem

venue: Discussiones Mathematicae Graph Theory,

authors:
Olana Missura
Thomas Gärtner

title: Predicting dynamic difficulty

authors:
Shay Moran
Amir Yehudayoff

title: On weak epsilon-nets and the Radon number

venue: In Symposium on Computational Geometry,

title: On convergence proofs on perceptrons

venue: In Symposium on the Mathematical Theory of Automata,

authors:
Fabian Pedregosa
Gaël Varoquaux
Alexandre Gramfort
Vincent Michel
Bertrand Thirion
Olivier Grisel
Mathieu Blondel
Peter Prettenhofer
Ron Weiss
Vincent Dubourg
Jake Vanderplas
Alexandre Passos
David Cournapeau

title: Scikit-learn: Machine learning in Python

venue: Journal of Machine Learning Research,

title: Geodesic convexity in graphs

authors:
Michalis Potamias
Francesco Bonchi
Carlos Castillo
Aristides Gionis

title: Fast shortest path distance estimation in large networks

venue: In Conference on Information and knowledge management,

authors:
Florence Regol
Soumyasundar Pal
Yingxue Zhang
Mark Coates

title: Active learning on attributed graphs via graph cognizant logistic regression and preemptive query generation

title: The Perceptron: a probabilistic model for information storage and organization in the brain

venue: Psychological review,

authors:
Florian Seiffarth
Tamás Horváth
Stefan Wrobel

title: Maximal closed set and half-space separations in finite closure systems

title: Maximum margin separations in finite closure systems

authors:
Eike Stadtländer
Tamás Horváth
Stefan Wrobel

title: Learning weakly convex sets in metric spaces

authors:
Lovro Šubelj
Dalibor Fiala
Tadej Ciglarič
Luka Kronegger

title: Convexity in scientific collaboration networks

venue: Journal of Informetrics,

authors:
Maximilian Thiessen
Thomas Gärtner

title: Active learning on graphs with geodesically convex classes

venue: In KDD workshop on Mining and Learning with Graphs,

authors:
Alexei Vazquez
Alessandro Flammini
Amos Maritan
Alessandro Vespignani

title: Global protein function prediction from protein-protein interaction networks

venue: Nature biotechnology,

authors:
Christopher KI Williams
Matthias Seeger

title: Using the Nyström method to speed up kernel machines

authors:
Wei Xiong
Luyu Xie
Shuigeng Zhou
Jihong Guan

title: Active learning for protein function prediction in protein–protein interaction

venue: networks. Neurocomputing,

authors:
Xianghong Zhou
Ming-Chih J Kao
Wing Hung Wong

title: Transitive functional annotation by shortest-path analysis of gene expression data

venue: Proceedings of the National Academy of Sciences,

authors:
Xiaojin Zhu
Zoubin Ghahramani
John Lafferty

title: Semi-supervised learning using gaussian fields and harmonic functions

authors:
Xiaojin Zhu
John Lafferty
Zoubin Ghahramani

title: Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. In ICML workshop on the continuum from labeled to unlabeled data in machine learning and data mining, 2003b

heading: 1 Introduction

text:
We systematically characterise active learning of geodesically convex halfspaces on graphs. While unlabelled graphs such as social networks are readily accessible, obtaining many labels is tedious and labour intensive. Active learning reduces the labelling effort by iteratively selecting informative data points to be labelled. Graph-based active learning, in particular, has been successfully applied on communication [Regol et al., 2020] and protein-protein-interaction networks [Vazquez et al., 2003, Xiong et al., 2014]. While most previous approaches assume that the number of edges with differently labelled vertices, the cut size, is small [Afshani et al., 2007, Guillory and Bilmes, 2009, Dasarathy et al., 2015], we take a different approach and instead assume geodesic convexity: For every pair of vertices with the same label it holds that every vertex on every shortest path between them also has that label. This assumption is used, for example, by biologists on gene similarity networks [Zhou et al., 2002] and cancer-related protein-protein-interaction networks [Li et al., 2012, 2013]. It also typically holds for connected subgraphs of collaboration networks [Marc and Šubelj, 2018, Šubelj et al., 2019] and our preliminary experiments confirmed that many communities in community detection datasets are convex. We derive bounds on the number of queries required to determine all labels, that is, the query complexity, using concepts from convexity theory and geodesic convexity spaces, which naturally generalise the regular Euclidean convexity. While learning convex sets and halfspaces in Euclidean spaces has been intensively investigated in the machine learning community for over half a century, geodesic convexity on graphs is understudied. For a concise presentation of our theoretical results in this paper, we concentrate on active learning of halfspaces on graphs, that is, the vertex set is partitioned into two classes which are both geodesically convex.
After introducing the concepts of graph and abstract convexity theory in Section 2, we derive general label-independent upper and lower bounds on the query complexity. We discuss that such general bounds can be loose on specific graphs and derive tighter lower bounds along the separation axioms of abstract convexity theory in Section 3. This allows us to substantially reduce the gap between our upper and lower bounds. Note that Euclidean spaces cannot be structured in a similar way: while the separation axioms partition the space of all graphs into non-empty sets, all separation axioms
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
hold in all real vector spaces including the Euclidean spaces. We discuss related topics like previous active learning bounds that depend on the cut size between the classes, active learning of halfspaces in Euclidean spaces, non-active learning of geodesically convex halfspaces, and other related learning theoretic concepts in Section 4. Notably, we provide a bound on the VC dimension of geodesically convex halfspaces given by the Radon number. After presenting an empirical validation of our assumptions and approach in Section 5, we conclude with a discussion of future work.

heading: 2 Convexity spaces

text:
In this section, we introduce the required concepts of convexity theory. For a more thorough introduction on convexity theory we refer the reader to van de Vel [1993] and Pelayo [2013].
For a set X and a family C ⊆ 2X of subsets, the pair (X, C) is a convexity space if (i) ∅, X ∈ C, (ii) C is closed under intersection, and (iii) C is closed under unions of sets totally ordered by inclusion. For finite set systems, property (iii) always holds. Any set in C is called convex. If a set C and its complement X \ C are convex, both are called halfspaces. Two disjoint sets A,B are halfspace separable if there exists a halfspace C such that A ⊆ C and B ⊆ X \C. A mapping σ : 2X → 2X is a convex hull (or closure) operator if for all A,B ⊆ X with A ⊆ B (i) σ(∅) = ∅, (ii) σ(A) ⊆ σ(B), (iii) A ⊆ σ(A), and (iv) σ(σ(A)) = σ(A). Any convexity space (X, C) induces a convex hull operator by σ(A) = ⋂ {C | A ⊆ C ∈ C}. A set A ⊆ X is convex, that is A ∈ C, if and only if is equal to its convex hull, A = σ(A).
A set H ⊆ X is a hull set if its convex hull is the whole space, σ(H) = X . For A,B ⊆ X , the set A/B = {x ∈ X | A ∩ σ(B ∪ {x}) 6= ∅} is the extension of A away from B. For a, b ∈ X , the extension {a}/{b} is also called a ray a/b. Two disjoint sets A1, A2 form a partition of A ⊆ X if A1 ∪ A2 = A. The partition A1, A2 of A is a Radon partition if σ(A1) ∩ σ(A2) 6= ∅. The Radon number is the minimum number r such that any subset of X of size r has a Radon partition.
A particular type of convexity is an interval convexity. Apart from the convex hull σ(·) it has an interval mapping I : X×X → 2X such that for all x, y ∈ X , (i) x, y ∈ I(x, y) and (ii) I(x, y) = I(y, x). I(x, y) is the interval between x and y. We denote I(A) = ⋃ a,b∈A I(a, b). A set C in an interval
convexity space is convex if and only if C = I(C). The convex hull is given by σ(A) = ⋃∞ k=1 I
k(A), where I1(·) = I(·) and Ik+1(·) = I(Ik(·)), A well-known instance of interval convexity spaces are metric spaces (X, d). There, the interval contains all the points for which the triangle inequality holds with equality: Id(x, y) = {z ∈ X | d(x, y) = d(x, z) + d(z, y)}. In Euclidean space this corresponds to all points on a line segment and leads to the classical notion of convex sets.
We study metric spaces induced by graphs. The geodesic convexity (or shortest path convexity) of a connected graph G = (V,E) is given by the interval mapping Id, where d : V 2 → R is the shortest path distance in G. Let x, y ∈ V . For unweighted graphs d(x, y) is the minimum number of edges on any x-y-path and for graphs with edge weights, w : E → R>0, it is the minimum total edge weight of any x-y-path. A set of vertices C ⊆ V is, thus, (geodesically) convex if and only if C contains every vertex on every shortest path joining vertices in C, corresponding again to the Euclidean case.
We denote by V (G) the vertex set of a graph G, the Radon number of the induced geodesic convexity space of a graph as r(G), and the size of the minimum hull set as h(G). Rays a/b in graphs can be defined using the shortest path distance d: In unweighted graphs a/b = {v ∈ V | d(a, v) < d(b, v)} and in weighted graphs a/b = {v ∈ V | d(b, v) = d(b, a) + d(a, v)}. A vertex v is extreme if {v} forms a halfspace, that is, V \ {v} is convex. We denote the set of extreme vertices of G as Ext(G). In unweighted graphs, v is extreme if and only if its neighbours form a clique. The diameter d(G) of a weighted or unweighted graph G is the maximum number of edges in any shortest path in G.

heading: 3 Active learning halfspaces on graphs

text:
Having introduced the necessary concepts from convexity theory, we now present the main theoretical results of the paper. In active node classification, a graph G = (V,E) with unknown vertex labels λ : V → {0, 1} is given and the goal is to accurately predict all labels using as few as possible vertex queries. Edges can be weighted or unweighted. The learner queries the vertices one by one: it iteratively selects vertices v ∈ V and receives their label λ(v). In this paper, we consider active learning on an undirected connected graph where the vertices with same label form geodesically
convex sets. The classes are, thus, halfspaces and we call the labelling halfspace separable. Our results in this section are upper and lower bounds on the number of queries required to deduce all labels λ of the graph. We denote the number of queries required to identify any halfspace separable labelling in the worst-case, the query complexity, by qc(G). We derive two general upper bounds (Proposition 1, Theorem 5) and one lower bound (Theorem 7) on qc(G) that hold for any halfspace separable labelling. To reduce the gap between the upper and lower bounds (Proposition 8), we derive increasingly tighter lower bounds along separation axioms (Theorem 10). In this section, we consider only undirected and connected graphs. Full proofs and a discussion of the multiclass, directed, and disconnected setting are in the supplementary material.

heading: 3.1 Upper bounds on the query complexity

text:
To derive a simple upper bound, we note that one immediate consequence of the halfspace assumption is that any shortest path P can have at most one cut edge, that is, an edge with differently labelled endpoints. To deduce all labels of P , we first query its endpoints. If they have the same label, we know that all vertices on P have this label. Otherwise, we find the cut edge by binary search with at most dlog d(G)e queries, as the length of P is at most the diameter |V (P )| − 1 ≤ d(G). Here, log is the base 2 logarithm. We can generalise this approach to the whole graph using shortest path covers [Thiessen and Gärtner, 2020], which is a set S of shortest paths whose vertices cover the graph:⋃ P∈S V (P ) = V (G). Performing binary search on each path in S gives our first upper bound. Proposition 1. For any weighted graph G with minimum shortest path cover S∗ the query complexity can be bounded as qc(G) ≤ |S∗|(2 + dlog d(G)e).
By considering a complete graph with edge weights such that the position of the cut edges on all shortest path in the minimum shortest path cover can be chosen independently of each other, we can show that this bound is tight: Proposition 2. For any `, s ∈ N, there exists a weighted graph G with diameter d(G) = ` and minimum shortest path cover S∗ of size s such that qc(G) ≥ |S∗| log d(G).
However, the graph in Proposition 2 is an artificial worst-case example. For most graphs, we can do much better as the labels of vertices on different paths in the cover can typically not be chosen independently of each other. Consider a cubic hypergrid graph G, that is, the Cartesian product of k paths with ` vertices each. More than |V (G)|/d(G) + 1 ≥ `k/k` shortest paths are needed to cover G but 2 + dlog(k`)e queries suffice to identify all labels, as fixing one cut edge determines all others. Our main idea to improve the bound and derive a better algorithm for active learning of geodesically convex halfspaces is to deduce additional labels using convex hulls and extensions after each query. Algorithm 1 realises this idea. It first queries the vertices of a hull set (line 1). If all labels in the hull set are the same, we conclude that all vertices in the graph have the same label (line 2-3). Otherwise, it performs binary search on a shortest path between two vertices with different labels to identify a cut edge {a, b} (line 4-5). Finally, Algorithm 1 queries the remaining vertices. It initialises the sets A and B with the convex hull of the rays a/b and b/a, respectively, corresponding to vertices with already known labels (line 6). In each iteration of the main loop, the algorithm queries a vertex v in the set Ŵ=ab = V (G) \ (σ(a/b) ∪ σ(b/a)), consisting of all vertices whose labels we cannot directly deduce through convex hulls and extensions, and updates the sets A and B using the new vertex (line 7-12). The number of queries spend in the first five lines are summarised in Lemma 3. Lemma 3. Let G be a weighted graph with halfspace separable labels. Using h(G) + dlog d(G)e queries, we can either find a cut edge or determine that all vertices of the graph have the same label.
Proof. The convex hull of any minimum hull set is the whole graph. If all vertices in a hull set have the same label, then all vertices in the graph have this label. If not, we can take two vertices with different labels and find a cut edge on a shortest path between them with dlog d(G)e queries.
Lemma 4 shows that the initialisation and updates of A and B in Algorithm 1 are indeed valid. Lemma 4. Let G be a weighted graph with halfspace separable labels given by a halfspace C and let A ⊆ C and B ⊆ V (G) \ C. It holds that σ(A/B) ⊆ C.
Proof sketch. A/B ⊆ C as A ∩ σ(B ∪ {x}) ⊆ C ∩ (V (G) \ C) = ∅ for all x ∈ V (G) \ C. This implies σ(A/B) = ⋂ {C ′ | A/B ⊆ C ′, C ′ convex} ⊆ C by definition.
Algorithm 1: Ray-based Active Halfspace Learning on Graphs Input: graph G, oracle access to labels λ Output: halfspaces corresponding to both classes
1 Compute a hull set H and query its vertices 2 if ∀h, h′ ∈ H : λ(h) = λ(h′) then 3 return (∅, V (G)) 4 Choose h, h′ ∈ H such that λ(h) 6= λ(h′) 5 Perform binary search queries on any shortest h-h′-path to find a cut edge {a, b} 6 A := σ(a/b), B := σ(b/a) 7 while A ∪B 6= V (G) do 8 query any vertex v ∈ V (G) \ (A ∪B) 9 if λ(v) = λ(a) then
10 A := σ((A ∪ {v})/B), B := σ(B/(A ∪ {v})) 11 else 12 A := σ(A/(B ∪ {v})), B := σ((B ∪ {v})/A)
13 return (A,B)
We can bound the remaining number of vertices queried by Algorithm 1 using the following set
W ∗=ab = {v ∈ Ŵ=ab | @w ∈ Ŵ=ab \ {v} such that v ∈ (w/a) ∩ (w/b)}
as it is enough to know the labels of the vertices in W ∗=ab to deduce all labels of Ŵ=ab. Theorem 5 shows that Algorithm 1 is correct and summarises our main upper bound. Theorem 5. Let G be a weighted graph. For the query complexity it holds that:
qc(G) ≤ h(G) + dlog d(G)e+ max {a,b}∈E(G) |W ∗=ab| .
Proof sketch. By Lemma 3, we can use h(G) + dlog d(G)e queries to find the first cut edge {a, b}. Every time Algorithm 1 queries a vertex v ∈ Ŵ=ab \W ∗=ab there is a w ∈W ∗=ab by definition such that v ∈ (w/a)∩ (w/b). It holds that w /∈ A∪B, as otherwise v ∈ (w/a)∩ (w/b) ⊆ A∪B, which contradicts line 8 of Algorithm 1, v ∈ V (G) \ (A ∪ B). Thus, in each iteration at least one new vertex from W ∗=ab will be added to A or B. This bounds the number of iterations by |W ∗=ab|.
Comparing our two upper bounds, we see that Theorem 5 is preferable to Proposition 1, as long as |W ∗=ab| is small. To see this, note that the endpoints of paths in a minimum shortest path cover S∗ form a hull set, implying h(G) ≤ 2|S∗|. If |W ∗=ab| is small, the bound of Theorem 5 is additive in the dominating terms h(G) + dlog d(G)e ≤ 2|S∗|+ dlog d(G)e, not multiplicative as in Proposition 1. To state the bound for the unweighted case in more common parameters, we relate |W ∗=ab| to the well-studied treewidth tw(G) [Bodlaender, 1996], which measures the ‘tree-likeness’ of a graph. It is known, that the largest k ∈ N, such that the complete bipartite graph K2,k is a minor of a graph G, is at most twice the treewidth [Bodlaender et al., 1997]: k ≤ 2 tw(G). This bounds the size |W ∗=ab| ≤ 2 tw(G) for any edge {a, b}, as the vertices {a, b} ∪W ∗=ab form a minor K2,|W∗=ab|. Consequently, graphs with small treewidth like molecules [Horváth and Ramon, 2010] and infrastructure-based networks [Maniu et al., 2019] have small W ∗=ab. Corollary 6 summarises this result. Corollary 6. Let G be an unweighted graph. For the query complexity it holds that qc(G) ≤ h(G) + dlog d(G)e+ 2 tw(G).

heading: 3.2 Lower bounds under separation axioms

text:
Having discussed our upper bounds on the query complexity, we now turn to a simple lower bound based on the extreme vertices Ext(G) of the graph, recall each of them is a halfspace by definition. Theorem 7. For any weighted graph G, it holds that qc(G) ≥ |Ext(G)|.
Considering a graph containing paths that all coincide only in the same two endpoints, we can show that this bound is tight and that the gap between it and our upper bound can be arbitrarily large.
Proposition 8. For any `, s, k, e ∈ N, there exists an unweighted graph G with d(G) ≥ `, minimum shortest path cover S∗ of size at least s, h(G) ≥ k, |Ext(G)| = e, and qc(G) ≤ max{2, e}.
This shows that this lower bound is best possible in general, even if d(G), h(G), and S∗ are large. One main insight of our work is that we achieve increasingly tighter lower bounds by structuring the set of all graphs along separation axioms, which characterise the ability of a convexity space to separate sets via halfspaces. This follows a related notion in topological spaces.
Definition 9 (Separation axioms [van de Vel, 1993]). A convexity space (X, C) is:
S1 if and only if each singleton x ∈ X is convex.
S2 if and only if each pair of distinct elements x, y ∈ X is halfspace separable.
S3 if and only if each convex set C and elements x ∈ X \ C are halfspace separable.
S4 if and only if any two disjoint convex sets are halfspace separable.
If S1 holds, which is the case for the geodesic graph convexity, the remaining axioms are increasingly stronger, that is, S2 ⇐ S3 ⇐ S4. We call a graph Si, for i = 1, . . . , 4, if the induced geodesic convexity space satisfies the respective separation axiom. While real vector spaces such as the Euclidean space satisfy all four separation axioms [Kakutani, 1937], there are graphs that are Si but not Si+1 for i = 1, 2, 3 [Bandelt, 1989], see supplementary material for some examples. Structuring all graphs along these separation axioms gives us increasingly stronger lower bounds.
Theorem 10. For every weighted graph G the following holds for the query complexity qc(G):
• if G is S2, then qc(G) ≥ max{log d(G), |Ext(G)|},
• if G is S3, then qc(G) ≥ max{log d(G), h(G)}, and
• if G is S4, then qc(G) ≥ max{log d(G), h(G), r(G)− 1}.
Each bound is tight in the respective family and stronger axioms lead to tighter bounds.
Proof sketch. In S2 graphs, any edge in a fixed but arbitrary shortest path with size of the diameter can be bisected with a halfspace. Thus, log d(G) queries are required to find the chosen edge. In S3 graphs, any point h ∈ H∗ can be separated from the remainder of a minimum hull set H∗, thus the whole hull set H∗ must be queried in the worst-case. In S4 graphs, any set that has no Radon partition can be labelled arbitrarily. To see that the bounds are increasingly tighter, notice that all extreme vertices are by definition contained in any hull set and hence |Ext(G)| ≤ h(G). As there are graphs with h(G) = k and r(G) = t for any k, t ∈ N with k, t ≥ 4, both parameter can be dominating.
Theorems 5 and 10 imply tight bounds (Table 1) for graph families in metric graph theory [Bandelt and Chepoi, 2008], convexity theory [Chepoi, 1994], and machine learning [Seiffarth et al., 2019].

heading: 3.3 Computational aspects

text:
Above, we derived lower and upper bounds on the query complexity of learning halfspaces on graphs G = (V,E). We now discuss computational aspects of our algorithms and bounds.
Shortest-path-cover-based bound To achieve the bound of Proposition 1, we need to compute a minimum shortest path cover of the given graph, which is an open problem [Manuel, 2021]. We show that greedily covering the graph with longest shortest paths gives a logarithmic approximation: Theorem 11. For a given weighted graph G, we can compute an (1 + ln(d(G) + 1))-approximation for the minimum shortest path cover S∗ in time O(|V |4).
Thus, using this approximation we achieve the query complexity bound qc(G) ≤ |S∗|(2 + dlog d(G)e)2 in polynomial time. To evaluate this bound, we also need to compute the diameter d(G), which can be achieved by a generalised Dijkstra algorithm, see supplementary material.
Hull-set-based bound The main computational bottleneck of Algorithm 1 is the computation of a minimum hull set. Computing the minimum hull set size h(G) is APX-hard [Coelho et al., 2015]. For many graph families however, such as distance-hereditary [Kanté and Nourine, 2016], interval, and cographs [Dourado et al., 2009] the problem is solvable in polynomial time. Moreover, the problem can be solved in polynomial time if any of the following parameters is bounded by a constant: the treewidth [Kanté et al., 2019], the vertex cover size, the neighbourhood diversity [Araujo et al., 2013b], and the number of induced paths in bounded vertex subsets [Araujo et al., 2013a]. The remaining runtime of Algorithm 1 is dominated by the computation of convex hulls and extensions. A single convex hull computations can be performed in time O(|V |3) by first computing the full distance matrix and then evaluating the triangle inequality for each triplet of vertices. Extensions can be computed through |V | convex hull evaluations. Algorithm 1 achieves, thus, the bound of Theorem 5 in polynomial time, as long as we can efficiently compute a minimum hull set. On unweighted graphs we additionally achieve the bound in Corollary 6 efficiently in this case. Alternatively, we can compute any, possibly non-optimal, hull set H in polynomial time to achieve the bound |H|+ dlog d(G)e+ max{a,b}∈E(G) |W ∗=ab|.
Lower bounds To evaluate our lower bounds in Theorem 10, we also need to compute |Ext(G)| and r(G). Computing the set of extreme vertices Ext(G) is possible in time O(|V ||E|) by evaluating the neighbourhood of each vertex. Computing the Radon number of a graph is even hard to approximate within any factor sublinear in |V | [Coelho et al., 2015]. However, Duchet and Meyniel [1983] bounded the Radon number in terms of the size of the largest clique minor, that is, the Hadwiger number, which in turn can be upper bounded by the treewidth. Proposition 12. For any weighted graph G, it holds that r(G) ≤ 2 tw(G) + 2.
Thus r(G) is computable in polynomial time for bounded treewidth graphs. To decide which lower bound applies for a given graph, we need to check if the graph is Si, for i = 1, . . . , 4. For the cases i = 1, 2, 3, it is unclear whether this is possible in polynomial time. Only for S4 an algorithm with runtime O(|V (G)|7) is known [Seiffarth et al., 2019]. Just deciding whether a graph has a proper halfspace, which is neither empty nor the full graph, is NP-hard [Artigas et al., 2011]. Both problems are efficiently decidable on planar and bipartite graphs [Glantz and Meyerhenke, 2017].

heading: 4 Discussion

text:
In this section, we discuss our assumptions as well as results related to our learning problem.
Convexity in real-world datasets In some applications convexity-based assumptions are already implicitly or explicitly used. For example, it is well-known that shortest paths in gene similarity networks largely preserve functional relationships [Zhou et al., 2002]. Similarly on protein-proteininteraction networks, shortest paths between cancer-related genes are used to identify a candidate set of novel genes, which are likely to be cancer-related, as well [Li et al., 2012, 2013]. Aside from biological networks, Marc and Šubelj [2018] and Šubelj et al. [2019] recently found that connected subgraphs of certain real-world graphs like collaboration networks are often convex. To provide further evidence for convexity in real-world graphs, we performed preliminary experiments on different networks with ground truth communities. Table 2 shows the number of convex communities in six datasets from SNAP [Leskovec and Krevl, 2014]. We found that on the DBLP scientific collaboration dataset more than 85% of the 5000 communities are convex, supporting the results of Šubelj et al. [2019]. On the Amazon product network we have similar results with roughly 80%. On the Youtube network we found that roughly 60% of the communities are convex. On the remaining
three datasets, however, less than a third of the communities are convex. Clearly, convexity on graphs is application dependent and further study with real-world networks is necessary.
Relationships to Euclidean convexity Learning halfspaces in Euclidean space is one of the oldest learning problems initiating algorithms like the perceptron [Rosenblatt, 1958, Novikoff, 1962] and support vector machines [Boser et al., 1992, Cortes and Vapnik, 1995], and is still an active research area [Daniely, 2016, Diakonikolas et al., 2019, Hopkins et al., 2020]. A simple lower bound for the number of queries required to learn the labels of a finite set X ⊆ Rm labelled accordingly to a halfspace is Ω(m log |X|) [Hopkins et al., 2020]. However, for worst-case instances such as points on the circle, already Ω(|X|) queries are required to identify all labels [Dasgupta, 2005], corresponding to our hull set lower bound. The query complexity can be improved through membership query synthesis [Angluin, 1988], which allows the learner to query additionally any point in Rm \X . Using them, Hopkins et al. [2020] showed that in expectation O(m log2(m) log |X|) + m1+o(1) queries are enough to infer all labels, essentially matching the lower bound. There is no direct equivalent of membership queries in the transductive graph setting. It is in general not possible to embed a graph into Rm or the other way around while preserving halfspaces. An example can be seen in Figure 1c and further discussion can be found in the supplementary material. Together with the fact that Euclidean convexity spaces are always S4 while graphs do not have to be, there is no immediate way to transform general bounds on the query complexity from one setting to the other.
Previous cut-based bounds Most previous bounds for active learning on graphs are linear in the number of cut edges C or cut vertices ∂C, which are the vertices incident to the cut edges. Therefore, these bounds can become vacuous when the cut is large, independent of halfspace separable labels. We will illustrate the bounds on the unweighted 2×k grid, that is, the Cartesian product of a path with k vertices and a path with 2 vertices. On the one hand, our upper bound of Theorem 5 yields a query complexity of 2 + log(k + 1). On the other hand, the bounds of Afshani et al. [2007] and Dasarathy et al. [2015] result in at least |∂C| queries even under additional balancedness assumptions on the labels. Thus, the bounds are at least |V | for the halfspace corresponding to the 1× k grid. The bound of Guillory and Bilmes [2009] is for the non-iterative active setting, where a set L ⊆ V of vertices is queried all at once. Let δ(T ) denote the set of edgs with exactly one endpoint in T ⊆ V . They bound the error by |C|/Ψ(L) using the min-cut-based prediction strategy [Blum and Chawla, 2001], where Ψ(L) = min∅6=T⊆(V \L) |δ(T )|/|T |. As long as |L| ≤ |V |/8, we will have Ψ(L) ≤ 4/8 and for the previously mentioned halfspace |C| = k. Thus, the error bound will be at least 2k = |V |. This shows that the three discussed previous bounds can be vacuous and exponentially worse than our achieved bound. All three are particularly sensible to large cut sizes. The sole cut is thus not sufficient to measure the complexity inherent in the labelling.
Margin-based bounds Bressan et al. [2021] study the query complexity of identifying convex clusters in the ε-nearest-neighbour of a semi-metric space (X, d). Even though they rely on additional assumptions, like a large margin, their upper bound is very similar to our main result. However, they only provide lower bounds on the query complexity on specific worst-case instances, while our lower bounds hold in general under the different separation axioms. They use same-cluster queries, which are binary queries on a pair of vertices to test whether they belong to the same cluster. Same-cluster queries and regular vertex queries are equivalent in terms of the query complexity up to a multiplicative factor given by the number of classes. To derive a bound they use restrictions beyond our halfspace assumption. In particular, Bressan et al. [2021] assume that the weight of any cut edge is > βε for a β ∈ (0, 1] and use an interval Iγ(x, y) with margin γ ∈ (0, 1], which consists of all vertices that lie on a path at most (1 + γ) as long as the shortest x-y-path, to define convex sets. The regular geodesic convexity corresponds to γ = 0. They also require a constant number of so-called seed queries that take a class label and a set U ⊆ X as input and return a vertex from U
with the specified label or certify that U does not contain such a vertex. Under these assumptions they derive an O ( log |X|+ (6/βγ)dens(X) ) upper bound on the query complexity, where dens(X)
is the density dimension of the space [Gottlieb and Krauthgamer, 2013]. Even though Bressan et al. [2021] consider a more restricted hypothesis space, there exist graph families where our bound in Theorem 5 is exponentially better. For example, on the 2× k grid, the halfspace corresponding to the 1× k grid enforces a margin of γ < 2/k. This results in a bound of at least log(2k) + (3k)dens(X) with dens(X) ≥ 1 while our bound (Theorem 5) predicts that 2 + log(k + 1) queries are enough. Even with a large γ our bound remains better on this example.
Alternatives to hull sets As computing minimum hull sets is APX-hard in general [Coelho et al., 2015], we discuss two alternatives to perform the first step in Algorithm 1, that is, finding two vertices with different labels. For that, Afshani et al. [2007] and Dasarathy et al. [2015] assume that the labels are balanced, that is, the relative size β of the smallest labelled class is close to 1/2. This assumption is in their case required to find two vertices with different labels query-efficiently with high probability 1 − α, for α ∈ (0, 1). We do not require this assumption as we can use any hull set to achieve the same deterministically. However, if β is known, we can state an alternative probabilistic upper bound. Instead of spending h(G) queries we can sample a set L of size ⌈ log(βα) log(1−β)
⌉ uniformly at random from V (G) to find two differently labelled vertices with probability 1 − α [Dasarathy et al., 2015]. This means that with probability 1− α the query complexity is bounded by qc(G) ≤ ⌈ log(βα) log(1−β) ⌉ + dlog d(G)e+ max{a,b}∈E(G) |W ∗=ab|. The other alternative is using the mentioned seed queries of Bressan et al. [2021]. Spending only two seed queries to find two vertices with different labels and dlog d(G)e+ max{a,b}∈E(G) |W ∗=ab| label queries using Algorithm 1 from line 5 on is enough. We note that both bounds can be achieved algorithmically in polynomial time.
Non-active learning of convex sets and halfspaces Non-active learning of halfspaces on graphs was studied by Seiffarth et al. [2019, 2020] and de Araújo et al. [2019]. Seiffarth et al. [2019] rely on the separation axiom S4 to bound the number of convex hull evaluations needed to construct a halfspace. Anthony and Ratsaby [2018] study the problem of learning large-margin halfspaces on a set equipped with an arbitrary dissimilarity measure d, which generalises shortest path distances of graphs. However, their notion of halfspace, {x | d(x, p+) ≤ d(x, p−)} based on the dissimilarity to two prototypes p+, p− is in general not convex. Stadtländer et al. [2021] investigate the problem of learning weakly convex sets in a metric space (X, d). Here, weakly convex sets with parameter θ ≥ 0 are given by the interval mapping Iθ(a, b) = {x ∈ X | d(a, x)+d(x, b) = d(a, b) ≤ θ}∪{a, b}. The regular geodesic convexity corresponds to θ ≥ maxa,b∈X d(a, b). Gärtner and Garriga [2007] and Missura and Gärtner [2011] studied monotone classes in directed acyclic graphs, which corresponds to an interval mapping containing the vertices on all directed paths instead of just shortest paths. Moran and Yehudayoff [2019] established that the VC dimension of halfspaces of any convexity space is smaller than the Radon number of the space. Building on that, we can show that VC dimension is exactly determined by the Radon number in S4 convexity spaces. This corresponds to the classical result that in Rm the VC dimension of halfspaces is m+ 1 and the Radon number is m+ 2. Proposition 13. The VC dimension of the hypothesis class of halfspaces of an S4 convexity space is exactly one less than the Radon number of the space.
For S4 graphs, r(G) determines the VC dimension and gives a lower bound on the query complexity (Theorem 10), establishing the Radon number as a central parameter for learning geodesically convex halfspaces. Proposition 12 together with the above bound of Moran and Yehudayoff [2019] gives: Proposition 14. The VC dimension of halfspaces in a weighted graph G is at most 2 tw(G) + 1.

heading: 5 Experiments

text:
Having discussed our bounds on the query complexity and the conceptual benefits of the halfspace assumption in terms of theoretical upper bounds, we want to see whether we also get empirical benefits on data, as well. We propose two practical versions of Algorithm 1: greedy and selective sampling. The greedy strategy tries to maximise the number of known vertex labels with each query. For that, it queries the vertex v that would maximise the minimum number of known labels after the update of A and B. More precisely, after the update with a vertex v we will know the labels
of the set σ((A∪ {v})/B) ∪ σ(B/(A∪ {v})) or the set σ(A/(B ∪ {v})) ∪ σ((B ∪ {v})/A). The greedy strategy thus selects the vertex v that maximises the size of the smaller one of these two sets. As performing the described greedy maximisation for each query is rather computationally expensive, we propose a simpler strategy based on selective sampling [Cohn et al., 1994] that picks a vertex uniformly at random from V (G) \ (A ∪B) in line 8 of Algorithm 1. To find the first cut edge, Algorithm 1 requires a hull set in the first step. As discussed, computing a minimum hull set is in general not tractable. Therefore, we propose to use the selection strategy (greedy or selective sampling) also to iteratively construct a hull set until two vertices with different labels are found. For that we start with A = ∅ and query a vertex v from V (G) \ A: either uniformly at random (selective sampling) or by maximising |σ(A ∪ {v})| (greedy). Afterwards we update A := σ(A ∪ {v}) and repeat until v has a different label than the previous vertices. Implicitly this process will construct a (typically non-minimum) hull set H . That way the query complexity bound in Theorem 5 still holds, as it is independent of the specific selection strategy used; only the h(G) is replaced with the size of the heuristically computed H . We compare these two strategies with the state-of-the-art graph-based active learning algorithm S2 [Dasarathy et al., 2015], the classical active label propagation of Zhu et al. [2003b], and baseline non-active random sampling.
As datasets, we use ε-nearest-neighbour graphs of two moons1 and Iris2, see Figures 1a and 1b. The parameter ε was selected such that the graph is connected and the labels are halfspace separable. Additionally, we use a 20 × 20 grid and a 210 hypercube labelled with a random halfspace. We implemented all approaches in python3 and ran the experiments on an Ubuntu 21.04 laptop with 32GB main memory. More details and in-depth experiments are in the supplementary material.

heading: 5.1 Query evaluation

text: Dasarathy et al. [2015] proposed to count the number of found cut vertices after each query as a measure to compare querying algorithms without relying on any classification method. A queryefficient graph-based active learner should detect these as fast as possible. The results for 20 iterative queries in the upper half of Figure 2 show that our approaches identify the cut vertices more efficiently than S2, active label propagation, and random sampling by deducing many labels after each query. Our greedy approach requires at most 6 queries to deduce all vertex labels on all four datasets emphasising the strength of convexity-based assumptions. The selective sampling approach is only slightly worse using 2-8 queries more. S2, active label propagation, and random sampling can find at most one cut vertex per query as they do not rely on these assumptions. As can be seen on the grid dataset, S2 performs better than active label propagation and random sampling finding a cut vertex on any new query, which is not by coincidence as it was specifically designed for this task.

heading: 5.2 Predictive performance

text:
We also evaluated the predictive performance of the chosen queries. Our two approaches predict the labels of the computed hulls and default to the majority of known labels when they do not know vertex’s label. The other three approaches perform label propagation [Zhu et al., 2003a] with the default Gaussian similarity and length-scale σ = 1 for prediction. We check the accuracy on the whole graph after each query of the 20 queries. In the lower half of Figure 2, we can confirm that
1ε = 0.14, make_moons(noise=0.1, random_state=0) in scikit-learn [Pedregosa et al., 2011] 2ε = 0.3, first class vs the other two [Fisher, 1936] 3https://github.com/maxthiessen/active_graph_halfspaces
greedy identifies the vertex labels of the whole graph on all datasets within 6 queries. The predictive behaviour of the three baselines is worse, even unstable. The main reason is that label propagation favours small cuts (weighted by the similarity), and thus fails to predict halfspaces, especially on the grid and hypercube. S2 mitigates this problems to some extent, even though it predicts the labels also with label propagation, by removing any found cut edge from the graph. Still, it has difficulties to find the correct halfspace and then stick to these prediction, as can be seen, for example, on the grid.

heading: 6 Conclusion and Future Work

text:
In this paper, we introduced active learning of halfspaces on graphs and derived tight bounds on the query complexity for this problem using concepts from convexity theory. On the one hand, we derived two general upper bounds: one based on shortest path covers and the other based on the diameter, hull sets, and the quantity max{a,b}∈E(G) |W ∗=ab|. We showed that the latter term is at most twice the treewidth of the graph in the unweighted case. On the other hand, we derived a general lower bound based on extreme vertices and increasingly tighter lower bounds for graph families induced by the separation axioms. For the strongest separation axiom S4, we achieved nearly tight lower and upper bounds with only the gap between the Radon number r(G) and max{a,b}∈E(G) |W ∗=ab| remaining. We compared our bounds to previous cut-based bounds and showed that the halfspace assumption makes learning with large cuts possible while previous bounds are vacuous in this case. We discussed that there are inherent differences between Euclidean and graph convexity spaces such that the respective query complexity bounds do not carry over to the other setting. With preliminary experiments we confirmed that communities in real-world networks such as collaboration and product networks are often convex. Based on our algorithm, we proposed two practical variants greedy and selective-sampling. We empirically compared them with active label propagation [Zhu et al., 2003b] and S2 [Dasarathy et al., 2015] on datasets with halfspace separable classes and found that our algorithms require considerably less queries to correctly identify the halfspaces. The main bottleneck of our variants is the cubic runtime to compute convex hulls. To scale our methods to large datasets we will investigate efficient approximations of convex hulls [Blum et al., 2019] and distances using the Nyström [Williams and Seeger, 2001] or other landmark-based methods [Potamias et al., 2009].
To make our results more broadly applicable, we propose to relax our notion of halfspaces and use the weak convexity of Stadtländer et al. [2021]. They define weak convexity with respect to a parameter θ ≥ 0 and show that weakly convex sets can be decomposed into weakly convex blocks that are at least a distance of θ apart. The number of these blocks may serve as a parameter to adapt our bounds to weakly convex classes. Another promising future research direction is to develop querying and prediction strategies for general interval convexity spaces by combining our ideas with those of Seiffarth et al. [2019], Stadtländer et al. [2021], and Bressan et al. [2021]. A promising first step is to consider geometric interval spaces using base-point orders [van de Vel, 1993]. Finally, we propose to also investigate regret bounds for online learning of convex sets on graphs.
Broader impact statement As this is an early theoretical and algorithmic work, we do not see any specific immediate societal impact, neither positive nor negative. In the long run the developed theoretical results might help to reduce the required number of labelled data points in graph-based learning settings and help with data annotation in general.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for helpful comments and Marco Bressan for fruitful discussions.

title: Active Learning of Convex Halfspaces on Graphs


summaries: The paper proposes a simple yet effective method of pretraining the feature encoder in TAL models. The motivation comes from the distribution-shift as well as the task-shift between the classical image-/action-classification pretraining and the TAL training. To make the encoder also adapt to the TAL task, the authors propose to unfreeze the encoder and pretrain under the TAL task. Due to GPU memory limit, the authors use spatially/temporally low fidelity data to pretrain the encoder. Experiments are conducted to verify the authors’ motivation and show the advantage of such a pretraining routine.

summaries: Updating after the rebuttal: The rebuttal well addressed some of my concerns. I would raise the rating to 6: Marginally above the acceptance threshold  ---  The paper presents a low-fidelity video encoder optimization approach to relieve the large memory constraints in the temporal action localization problem. The proposed approach is easy to implement and reasonable results have been obtained on ActivityNet and HACS datasets. However, the proposed approach is more like an engineering solution. The technical novelty of the proposed approach is limited.

summaries: ** Update 8/16/21 **   Thanks to the authors for their rebuttal in response to my questions/concerns. After reading the rebuttal and the other reviews, I am updating my score to 6, to better reflect the contributions made by the work.  **   The paper aims to tackle the hardware constraint for end-to-end optimization of both video encoding and TAL head models. Different from prior works that freeze the video encoding network when training the TAL head, the proposed method optimizes both of them jointly on low-resolution (spatially and temporally) video frames and then finetunes the TAL head on full-resolution videos. The main contribution of this paper is resolving the task discrepancy problem for the video encoder when training TAL models. Extensive experiments are conducted in the paper to compare the lofi setting with several state-of-the-arts, as well as similar models under different pretraining conditions. Results indicate the proposed method outperforms the baselines.

summaries: In this paper, the authors propose a new method to allow video encoder optimization in training temporal action localization (TAL) models, which is often ignored by existing TAL methods due to GPU memory constraints. The proposed method LoFi reduces the demanding GPU memory requirement by using a lower temporal and/or spatial resolution in the mini-batch construction. The proposed LoFi technique has shown to help enhance the performance of off-the-shelf TAL models on ActivityNet and HACS-v1.1. Also, the performance improvement is universal across different types of video encoder.

summaries: Models for temporal action localization (TAL) in long, untrimmed video are typically trained in two stages, a video encoder pretrained on a auxiliary video clip classification dataset and then frozen, followed by a TAL head. End-to-end training of the encoder and TAL head is infeasible because the encoder activations for an entire, long video will not fit in GPU RAM. This paper proposes a solution: use the ideas of mulgrid training [51] to do end-to-end training of a lower resolution video encoder and TAL head. They explore strategies for cycling through regimes of lower spatial, temporal, and spatio-temporal resolution training, and demonstrate performance gains on the ActivityNet and HACS datasets, using a number of backbone networks and TAL heads.

abstractText: Most existing temporal action localization (TAL) methods rely on a transfer learning pipeline, first optimizing a video encoder on a large action classification dataset (i.e., source domain), followed by freezing the encoder and training a TAL head on the action localization dataset (i.e., target domain). This results in a task discrepancy problem for the video encoder – trained for action classification, but used for TAL. Intuitively, joint optimization with both the video encoder and TAL head is an obvious solution to this discrepancy. However, this is not operable for TAL subject to the GPU memory constraints, due to the prohibitive computational cost in processing long untrimmed videos. In this paper, we resolve this challenge by introducing a novel low-fidelity (LoFi) video encoder optimization method. Instead of always using the full training configurations in TAL learning, we propose to reduce the mini-batch composition in terms of temporal, spatial or spatio-temporal resolution so that jointly optimizing the video encoder and TAL head becomes operable under the same memory conditions of a mid-range hardware budget. Crucially, this enables the gradients to flow backwards through the video encoder conditioned on a TAL supervision loss, favourably solving the task discrepancy problem and providing more effective feature representations. Extensive experiments show that the proposed LoFi optimization approach can significantly enhance the performance of existing TAL methods. Encouragingly, even with a lightweight ResNet18 based video encoder in a single RGB stream, our method surpasses two-stream (RGB + optical flow) ResNet50 based alternatives, often by a good margin. Our code is publicly available at https://github.com/saic-fi/lofi_action_localization .

authors:
Humam Alwassel
Silvio Giancola
Bernard Ghanem

title: TSP: Temporally-sensitive pretraining of video encoders for localization

venue: tasks. iccvw,

authors:
Humam Alwassel
Dhruv Mahajan
Lorenzo Torresani
Bernard Ghanem
Du Tran

title: Selfsupervised learning by cross-modal audio-video clustering

venue: In NeurIPS,

authors:
Yueran Bai
Yingying Wang
Yunhai Tong
Yang Yang
Qiyue Liu
Junhui Liu

title: Boundary Content Graph Neural Network for Temporal Action Proposal Generation

venue: In ECCV,

authors:
Sagie Benaim
Ariel Ephrat
Oran Lang
Inbar Mosseri
William T Freeman
Michael Rubinstein
Michal Irani
Tali Dekel

title: SpeedNet: Learning the speediness in videos

authors:
Navaneeth Bodla
Bharat Singh
Rama Chellappa
Larry S. Davis

title: Soft-NMS – improving object detection with one line of code

authors:
Shyamal Buch
Victor Escorcia
Chuanqi Shen
Bernard Ghanem
Juan Carlos Niebles

title: SST: single-stream temporal action proposals

authors:
Fabian Caba Heilbron
Juan Carlos Niebles
Bernard Ghanem

title: Fast temporal activity proposals for efficient detection of human actions in untrimmed videos

authors:
Joao Carreira
Andrew Zisserman

title: Quo vadis, action recognition? a new model and the Kinetics dataset

authors:
Yu-Wei Chao
Sudheendra Vijayanarasimhan
Bryan Seybold
David A. Ross
Jia Deng
Rahul Sukthankar

title: Rethinking the faster R-CNN architecture for temporal action localization

authors:
Nieves Crasto
Philippe Weinzaepfel
Karteek Alahari
Cordelia Schmid

title: MARS: Motionaugmented RGB stream for action recognition

authors:
Cristian Rodriguez-Opazo
Edison Marrese-Taylor
Fatemeh Saleh
Hongdong Li
Stephen Gould

title: Proposal-free temporal moment localization of a natural-language query in video using guided attention

venue: In WACV,

authors:
Victor Escorcia
Fabian Caba Heilbron
Juan Carlos Niebles
Bernard Ghanem

title: DAPs: Deep action proposals for action understanding

authors:
Christoph Feichtenhofer
Axel Pinz
Andrew Zisserman

title: Convolutional two-stream network fusion for video action recognition

authors:
Jiyang Gao
Kan Chen
Ramakant Nevatia

title: CTAP: Complementary temporal action proposal generation

authors:
Jialin Gao
Zhixiang Shi
Guanshuo Wang
Jiani Li
Yufeng Yuan
Shiming Ge
Xi Zhou

title: Accurate temporal action proposal generation with relation-aware pyramid network

authors:
Jialin Gao
Xin Sun
Mengmeng Xu
Xi Zhou
Bernard Ghanem

title: Relation-aware video reading comprehension for temporal language grounding

venue: EMNLP-IJCNLP,

authors:
Jiyang Gao
Zhenheng Yang
Kan Chen
Chen Sun
Ram Nevatia

title: TURN TAP: Temporal unit regression network for temporal action proposals

authors:
Ross Girshick
Jeff Donahue
Trevor Darrell
Jitendra Malik

title: Rich feature hierarchies for accurate object detection and semantic segmentation

venue: In CVPR, page 580–587,

authors:
Kaiming He
Ross Girshick
Piotr Dollár

title: Rethinking ImageNet pre-training

venue: In CVPR,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Fabian Caba Heilbron
Wayner Barrios
Victor Escorcia
Bernard Ghanem

title: SCC: Semantic context cascade for efficient action detection

authors:
Fabian Caba Heilbron
Victor Escorcia
Bernard Ghanem
Juan Carlos Niebles

title: ActivityNet: A large-scale video benchmark for human activity understanding

authors:
Jiabo Huang
Yang Liu
Shaogang Gong
Hailin Jin

title: Cross-sentence temporal and semantic relations in video activity localisation

venue: In ICCV,

authors:
Qingbao Huang
Jielong Wei
Yi Cai
Changmeng Zheng
Junying Chen
Ho-fung Leung
Qing Li

title: Aligned dual channel graph convolutional network for visual question answering

venue: In ACL,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In ICML,

authors:
Simon Jenni
Givi Meishvili
Paolo Favaro

title: Video representation learning by recognizing temporal transformations

authors:
Will Kay
João Carreira
Karen Simonyan
Brian Zhang
Chloe Hillier
Sudheendra Vijayanarasimhan
Fabio Viola
Tim Green
Trevor Back
Paul Natsev
Mustafa Suleyman
Andrew Zisserman

title: The Kinetics human action video

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In ICLR,

authors:
H. Lee
J. Huang
M. Singh
M. Yang

title: Unsupervised representation learning by sorting sequences

authors:
Jie Lei
Licheng Yu
Mohit Bansal
Tamara L Berg

title: TVQA: Localized, Compositional Video Question Answering

venue: In EMNLP-IJCNLP,

authors:
Hao Li
Pratik Chaudhari
Hao Yang
Michael Lam
Avinash Ravichandran
Rahul Bhotika
Stefano Soatto

title: Rethinking the hyperparameters for fine-tuning

authors:
Ji Lin
Chuang Gan
Song Han

title: TSM: Temporal shift module for efficient video understanding

authors:
Tianwei Lin
Xiao Liu
Xin Li
Errui Ding
Shilei Wen

title: BMN: boundary-matching network for temporal action proposal generation

authors:
Tianwei Lin
Xu Zhao
Haisheng Su
Chongjing Wang
Ming Yang

title: BSN: Boundary sensitive network for temporal action proposal generation

authors:
Daizong Liu
Xiaoye Qu
Xiao-Yang Liu
Jianfeng Dong
Pan Zhou
Zichuan Xu

title: Jointly cross-and self-modal graph attention network for query-based moment localization

venue: In ACM MM,

authors:
Rosanne Liu
Joel Lehman
Piero Molino
Felipe Petroski Such
Eric Frank
Alex Sergeev
Jason Yosinski

title: An intriguing failing of convolutional neural networks and the coordconv solution

venue: NeurIPS,

authors:
Wei Liu
Dragomir Anguelov
Dumitru Erhan
Christian Szegedy
Scott Reed
Cheng-Yang Fu
Alexander C. Berg

title: SSD: Single shot multibox detector

authors:
Yuan Liu
Lin Ma
Yifeng Zhang
Wei Liu
Shih-Fu Chang

title: Multi-granularity generator for temporal action proposal

authors:
Fuchen Long
Ting Yao
Zhaofan Qiu
Xinmei Tian
Jiebo Luo
Tao Mei

title: Gaussian temporal awareness networks for action localization

title: Understanding deep convolutional networks. Philosophical Transactions of the Royal Society A: Mathematical

venue: Physical and Engineering Sciences,

authors:
Antoine Miech
Jean-Baptiste Alayrac
Lucas Smaira
Ivan Laptev
Josef Sivic
Andrew Zisserman

title: End-to-end learning of visual representations from uncurated instructional videos

authors:
Ishan Misra
C. Lawrence Zitnick
Martial Hebert

title: Shuffle and learn: Unsupervised learning using temporal order verification

authors:
Jonghwan Mun
Minsu Cho
Bohyung Han

title: Local-global video-text interactions for temporal grounding

authors:
Zhaofan Qiu
Ting Yao
Tao Mei

title: Learning spatio-temporal representation with pseudo-3D residual networks

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

title: You only look once: Unified, real-time object detection

authors:
Zheng Shou
Jonathan Chan
Alireza Zareian
Kazuyuki Miyazawa
Shih-Fu Chang

title: CDC: Convolutional-de-convolutional networks for precise temporal action localization in untrimmed videos

authors:
Zheng Shou
Dongang Wang
Shih-Fu Chang

title: Temporal action localization in untrimmed videos via multi-stage CNNs

authors:
Mattia Soldan
Mengmeng Xu
Sisi Qu
Jesper Tegner
Bernard Ghanem

title: VLG-Net: Video-language graph matching network for video grounding

venue: In ICCV workshops,

authors:
Chuanqi Tan
Fuchun Sun
Tao Kong
Wenchang Zhang
Chao Yang
Chunfang Liu

title: A survey on deep transfer learning

venue: International Conf. on Artificial Neural Networks,

authors:
D. Tran
L. Bourdev
R. Fergus
L. Torresani
M. Paluri

title: Learning spatiotemporal features with 3D convolutional networks

authors:
Du Tran
Heng Wang
Lorenzo Torresani
Jamie Ray
Yann LeCun
Manohar Paluri

title: A closer look at spatiotemporal convolutions for action recognition

authors:
Jiangliu Wang
Jianbo Jiao
Yun-Hui Liu

title: Self-supervised video representation learning by pace prediction

authors:
Limin Wang
Yuanjun Xiong
Zhe Wang
Yu Qiao
Dahua Lin
Xiaoou Tang
Luc Van Gool

title: Temporal segment networks: Towards good practices for deep action recognition

authors:
Xiang Wang
Zhiwu Qing
Ziyuan Huang
Yutong Feng
Shiwei Zhang
Jianwen Jiang
Mingqian Tang
Changxin Gao
Nong Sang

title: Proposal relation network for temporal action detection

authors:
D. Wei
J. Lim
A. Zisserman
W.T. Freeman

title: Learning and using the arrow of time

authors:
Chao-Yuan Wu
Ross Girshick
Kaiming He
Christoph Feichtenhofer
Philipp Krahenbuhl

title: A multigrid method for efficiently training video models

authors:
Huijuan Xu
Abir Das
Kate Saenko

title: R-C3D: Region convolutional 3D network for temporal activity detection

authors:
Mengmeng Xu
Juan-Manuel Pérez-Rúa
Victor Escorcia
Brais Martinez
Xiatian Zhu
Bernard Ghanem
Tao Xiang

title: Boundary-sensitive pre-training for temporal localization in videos

authors:
Mengmeng Xu
Chen Zhao
David S Rojas
Ali Thabet
Bernard Ghanem

title: G-TAD: Subgraph localization for temporal action detection

authors:
Yuan Yao
Chang Liu
Dezhao Luo
Yu Zhou
Qixiang Ye

title: Video playback rate perception for self-supervised spatio-temporal representation learning

authors:
Ze-Huan Yuan
Jonathan C. Stroud
Tong Lu
Jia Deng

title: Temporal action localization by structured maximal sums

authors:
Runhao Zeng
Wenbing Huang
Mingkui Tan
Yu Rong
Peilin Zhao
Junzhou Huang
Chuang Gan

title: Graph convolutional networks for temporal action localization

authors:
Runhao Zeng
Haoming Xu
Wenbing Huang
Peihao Chen
Mingkui Tan
Chuang Gan

title: Dense regression network for video grounding

authors:
Hao Zhang
Aixin Sun
Wei Jing
Joey Tianyi Zhou

title: Span-based localizing network for natural language video localization

authors:
Songyang Zhang
Houwen Peng
Jianlong Fu
Jiebo Luo

title: Learning 2d temporal adjacent networks for moment localization with natural language

venue: In AAAI,

authors:
Chen Zhao
Ali K Thabet
Bernard Ghanem

title: Video self-stitching graph network for temporal action localization

authors:
Hang Zhao
Zhicheng Yan
Lorenzo Torresani
Antonio Torralba

title: HACS: Human action clips and segments dataset for recognition and temporal localization

venue: iccv,

authors:
Yue Zhao
Yuanjun Xiong
Limin Wang
Zhirong Wu
Xiaoou Tang
Dahua Lin

title: Temporal action detection with structured segment networks

heading: 1 Introduction

text:
Video analysis has become an increasingly important area of research, encompassing multiple relevant problems such as action recognition [8, 13], temporal action localization [68, 7, 12, 22, 59, 60, 55, 67, 15], video grounding[36, 65, 64, 66, 49, 16, 24], and video question answering [25, 31]. Among those, temporal action localization (TAL) [68, 22] is a fundamental task, as natural videos are not temporally trimmed. Given an untrimmed video, TAL aims to identify the start and end points of all action instances and recognize their category labels simultaneously. A typical TAL model is based on deep convolutional neural networks (CNNs) composed of two modules: a video encoder and a TAL head. The video encoder is often shared across different TAL methods (e.g., G-TAD [60], BC-GNN [3])
∗Work done during an internship at Samsung AI Centre.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
by taking a specific off-the-shelf action classification model (e.g., C3D [51], I3D [8], TSM [33]), with the differences residing only in the TAL head. However, instead of short (e.g., 10 seconds) trimmed video clips as in action recognition, the input videos to a TAL model are characterized by much longer temporal duration (e.g., 120 seconds). This causes unique computational challenges that remain unsolved, particularly in model optimization.
In standard optimization of a TAL model, a two-stage transfer learning pipeline is often involved:
1. First, the video encoder is optimized on a large source video classification dataset (e.g., Kinetics [28]) and, optionally, finetunned on the trimmed version of the target dataset under action classification supervision;
2. Second, the video encoder is frozen and the TAL head is optimized on the target action localization dataset (e.g., ActivityNet [22], HACS [68]) under TAL task supervision.
With this widely-used TAL training pipeline, the video encoder is only optimal for action classification but not for the target TAL task. Specifically, the video encoder is trained so that different short segments within an action sequence are mapped to similar outputs, thus encouraging insensitivity to the temporal boundaries of actions. This is not desirable for a TAL model. We identify this as a task discrepancy problem. Consequently, the final TAL model could suffer from suboptimal performance.
Indeed, jointly optimizing all components of a CNN architecture end-to-end with the target task’s supervision is a common practice, e.g., training models for object detection in static images [18, 46, 38]. Unfortunately, this turns out to be non-trivial for TAL. As mentioned above, model training is severely restricted by the large input size of untrimmed videos and subject to the memory constraint of GPUs. This is why the two-stage optimization pipeline as described above becomes the most common and feasible choice in practice for optimizing a TAL model. On the other hand, existing transfer learning methods mostly focus on tackling the data distribution shift problem across different datasets [70, 50], rather than the task shift problem we study here. Regardless, we believe that solving this limitation of the TAL training design bears a great potential for improving model performance.
In this work, we present a simple yet effective low-fidelity (LoFi) video encoder optimization method particularly designed for better TAL model training. It is designed to adapt the video encoder from action classification to TAL whilst subject to the same hardware budget. This is achieved by introducing a simple strategy characterized by a new intermediate training stage where both the video encoder and the TAL head are optimized end-to-end using a lower temporal and/or spatial resolution (i.e., low-fidelity) in the mini-batch construction. Compared to the standard training method, our proposed strategy does not increase the GPU memory standard (often a hard constraint for many practitioners). Crucially, with our LoFi training the gradients back-propagate to the video encoder from a temporal action localization loss whilst conditioned on the target TAL head, enabling the learning of a video encoder sensitive to the temporal localization objective.
We make the following contributions in this work. (1) We investigate the limitations of the standard optimization method for TAL models, and consider that the task discrepancy problem hinders the performance of existing TAL models. Despite it being a significant ingredient, video encoder optimization is largely ignored by existing TAL methods, left without systematic investigation. (2) To improve the training of TAL models, we present a novel, simple, and effective low-fidelity (LoFi) video encoder optimization method. It is designed specifically to address the task discrepancy problem with the TAL model’s video encoder. (3) Extensive experiments show that the proposed LoFi optimization method yields new state-of-the-art performance when combined with off-the-shelf TAL models (e.g., G-TAD [60]). Critically, our method achieves superior efficiency/accuracy trade-off with clear inference cost advantage and good generalizability to varying-capacity video encoders.

heading: 2 Related Work

text:
Temporal action localization (TAL) models: TAL models can be grouped by architectural design pattern into two categories, one-stage and two-stage architectures. One-stage methods, either predict temporal action boundaries or generate proposals, and classify them within the same network [3, 9, 21, 40, 34, 58, 60, 62]. The latter type, two-stage models, generate sets of action proposals (e.g., segments) [6, 12, 14, 23, 39] and then an auxiliary head is used for classification of each proposal into an action class [35, 47, 48, 63, 69]. In this work, rather than introducing a novel model design,
we focus on the training of generic TAL models, with a particular aim to improve the video encoder optimization. This is a relatively less investigated aspect in the TAL literature.
Video encoders in TAL: The video encoder is an indispensable part of a TAL model. Main design choices include the base architecture of video encoder and its optimization procedure. With regards to the architecture, the two-stream Temporal Segment Network (TSN) [54] is one of the most common video encoders in existing TAL methods [3, 34, 35, 60]. Concretely, these works use two TSN networks, one with a ResNet50 [20] backbone trained on RGB video frames, and the other with a BN-Inception backbone [26] trained on optical flow. Other alternatives used as a video encoder for TAL include two-stream I3D model [8] (see [19, 63]) and Pseudo-3D [45] (see [40]).
In terms of optimization, a typical paradigm is two-staged: first pre-training the video encoder and then, in a second stage, training the TAL head of the model with the video encoder fixed. This is constrained by the inherent hardware budget derived from having a large per-video input size. In particular, the video encoder is pre-trained using a cross-entropy loss for action recognition on a large-scale video classification dataset such as Kinetics [28, 64]. An optional step is to further pre-train it on the foreground segments of the target TAL dataset [34, 60, 11, 44]. This brings a mismatch between training and inference for the video encoder, which we call a task discrepancy problem. More specifically, although trained to distinguish the content of different action classes, the video encoder is less sensitive to action temporal boundaries and thus less effective for the TAL task. In fact, due to their inherent design, CNNs have limited localization capabilities [41], unless they are augmented with specialized localization-specific layers [37]. Additionally, the action classification task focuses only on the foreground content whilst ignoring per-class background segments, including the transition between foreground and background. In this paper we propose a novel low-fidelity video encoder pre-training method to solve this limitation with existing TAL methods.
While current TAL literature mostly relies on pre-training through supervised learning, the rapid advancement of self-supervised learning makes it a promising alternative [2, 4, 42, 43, 56]. Some works have focused on finding effective temporal-related pretext tasks, from frame ordering learnt through triplets of frames [43], to sorting the frames of a sequence [30], distinguishing whether sequences are played forward or backwards [56] or through playback speed-related pretext tasks [4, 61, 53, 27]. These methods exploit video-specific characteristics to force the network to focus on some sort of semantic content within video, inducing representations capturing long-term temporal semantic relations, but force invariance to or ignore the relative positioning of the snippets within the action instances. They are thus not suited for pre-training the video encoder of a TAL model.
Very recent works [1, 59] have exploited some of the aforementioned techniques for better pre-training of action localization models. For example, localization-tailored data augmentation and classification is adopted by [59]. However, these works introduce a large amount of extra video data and additional stream networks, both of which are expensive in terms of memory and computation. In contrast, our method aims to improve TAL modelling directly without the need for learning from extra training video data and using an expensive second network, nor relying on optical flow obtained at high computational cost.

heading: 3 Method

text:
A TAL model takes as input a long untrimmed video with a varying number of frames. For design convenience, it is typical to represent a varying-length video by decomposing it into a fixed-length sequence of L snippets. The definition of a snippet is the same as in action recognition, where first a number of consecutive frames (e.g., 64) is selected and then sub-sampled with stride r (e.g., stride 8 to obtain 8-frame snippets). To represent a snippet, one first applies a video encoder to extract frame-level feature vectors and then averages them to obtain the snippet-level feature representation [6, 12, 17, 35]. The resulting snippet feature sequence is denoted as X ∈ RC×L, where C is the feature dimension of each snippet, and L is the number of snippets.
In the training set, each video is associated with its ground truth, consisting of a set of action instance annotations Ψ. In particular, each action instance is represented as a segment, each including the start time, the end time, and the action class label. The objective is to train a TAL model that can accurately localize all the target action instances in a given untrimmed video. To that end, the model predicts a
varying number of action instances Φ, each comprised of the predicted temporal boundaries, action class, and confidence score.

heading: 3.1 Model Training Procedure

text: Our training procedure consists of three stages as depicted in Figure 1. (1) First, we pre-train the video encoder by action classification supervision on a large video dataset (e.g., Kinetics [28]). (2) Second, we conduct low-fidelity (LoFi) optimization of the video encoder with a TAL head on the target dataset (Sec. 3.2). This is under TAL supervision with the objective loss function derived from the ground-truth Ψ and model prediction Φ. To this end, we propose to reduce the mini-batch configuration in terms of the spatial and temporal resolution of the input as otherwise end-to-end optimization cannot satisfy the hardware constraints. Crucially, by training on the target task and target dataset, the task discrepancy gap can be reduced. (3) Last, we freeze the already end-to-end optimized video encoder and train the TAL head of choice from scratch on the target dataset at full spatial and temporal resolutions. Note that in this setup, we cannot perform end-to-end optimization of the final TAL model, limited by the hardware memory constraint. Next, we will detail the proposed LoFi training.

heading: 3.2 Low-Fidelity Training Configurations

text:
Formally, we define the full fidelity configuration of a mini-batch as
Ωf = L×H ×W, (1)
where L specifies the temporal resolution, and H ×W refers to the 2D spatial resolution. Under the full fidelity regime and with a certain memory size constraint, only the TAL head can be trained whilst leaving the video encoder frozen. In order to enable the video encoder to be optimized end-to-end together with the TAL head under the TAL task’s supervision, we design four low-fidelity configurations for the mini-batch.
(I) Spatial Low-Fidelity (S-LoFi) In the first configuration, we lower the spatial resolution of the input videos by a factor of rs in both spatial dimensions as:
Ωs = L× (H/rs)× (W/rs) (2)
With smaller spatial feature maps, this could effectively reduce the memory consumption of the video encoder’s feature maps which in turn creates space to enable the learning of the video encoder.
(II) Temporal Low-Fidelity (T-LoFi) In the second configuration, we instead consider temporal resolution reduction in the following form:
Ωt = (L/rt)×H ×W, (3) where rt > 1 is the scaling factor. This corresponds to a smaller number of snippets being taken as input by the TAL head, finally outputting less predictions in case the candidates per time location remains the same. This reduces the memory demands of both the video encoder and the temporal localization head.
(III) Spatio-Temporal Low-Fidelity (ST-LoFi) In the third configuration, we apply a (typically smaller) reduction in both temporal and spatial resolutions concurrently, formulated as:
Ωst = (L/rt)× (H/rs)× (W/rs) (4) In this setup, memory saving can be shared between the temporal and the spatial dimensions.
(IV) Cyclic Low-Fidelity (C-LoFi) Each of the above three LoFi configurations is used in isolation. To further explore their complementary benefits, we propose to apply all of them in a structured fashion. To that end, we take inspiration from the recently proposed multi-grid training strategy [57], originally designed for speeding-up action recognition training. Specifically, we form a sampling grid with the three LoFi configurations and cycle through them repeatedly. We integrate both the short and long cycle strategies [57]. In particular, the long cycle changes the values of rt and rs at the beginning of an epoch, and cycling through the configurations I to III after cl epochs. Instead, the short cycle also cycles through configurations I to III, but changes rt and rs after cs batches instead.
It is important to note some practical differences with the original multri-grid training. First, contrary to the original multi-grid method, we shift the reduction in input resolution between the temporal and the spatial dimensions so that the per-video memory usage remains (approximately) constant. Thus, the batch size also remains constant throughout, which simplifies training. Second, the full resolution setting (i.e., the full fidelity) is not used at any time during the video encoder training.
We compare the above four configurations in Section 4.3. By default, we use the C-LoFi configuration with the long cycle strategy (Long C-LoFi).

heading: 3.3 An Instantiation of LoFi

text:
Off-the-shelf TAL model: Without loss of generality, in this study we adopt G-TAD [60], a stateof-the-art TAL method, as our temporal localization module. However, any other standard alternative, e.g. [34], can be adopted without any additional considerations (see Table A in supplementary material). Relying on graph convolutions [29], G-TAD is composed of a stack of GCNeXt blocks to obtain context-aware features. In each GCNeXt block, there are two graph convolution streams to model two types of contextual information. One stream operates with temporal neighbors, and the other adaptively aggregates semantic neighbors in the snippet feature space. At the end of the last GCNeXt block, G-TAD extracts a set of sub-graphs based on pre-defined temporal anchors. With the sub-graph of interest alignment layer, SGAlign, it represents each sub-graph using a feature vector, which is further used as input to multiple fully-connected layers to predict the final action predictions.
To train G-TAD with our LoFi, we select one of the proposed low-fidelity variants and apply the original TAL loss function to optimize both the video encoder and the TAL head. We initialize G-TAD weights as in [60].
Implementation details: We use ResNet-based TSM [33] as the video encoder due to its good accuracy-cost trade-off and reasonable memory requirements compared to 3D-based alternatives. For the full fidelity setting (Eq. (1)), we follow the standard G-TAD protocol and represent each video with L = 100 snippets. The full spatial resolution is H ×W = 224 × 224. We keep the other hyper-parameters (e.g., the number of GCNeXt layers) the same as in the default G-TAD configuration. However, the number of anchor proposals can be reduced when L is less. Concretely, we enumerate all the possible combinations of start and end as the anchors, e.g., {(ts, te)| 0 < ts < te < L; ts, te ∈ N ; te − ts < L}. For LoFi training, we use an SGD optimizer. The batch size is 16 for all the training methods and input patterns. The weight decay is 10−4 and we set the momentum to 0, which is standard for fine-tuning [32]. The learning rate is 0.1, and it is decayed by 0.5 after every 5 epochs.
When we train G-TAD using the full fidelity setting, we keep the same training strategy as described in the original paper [60], except that we perform a learning rate search within the set {0.0002, 0.0005, 0.001, 0.002, 0.005}. We follow the rest of the common post-processing steps for TAL as specified in the original paper, including the application of soft-NMS [5] with a threshold of 0.84. We select the top-100 predictions for the final evaluation. We provide our code and script as part of the supplementary material.
Hardware and software settings: We implemented our method using PyTorch 1.8 with CUDA 10.1. For LoFi training, we use 4 NVIDIA V100 GPUs, each with 32GB memory. Under this setting, the memory constraint is 128GB, which constitutes a mid-range computational budget. In the supplementary material, we further test a low-budget setting with a single V100 GPU in Table B.

heading: 4 Experiments

heading: 4.1 Experimental setup

text:
Datasets: We use Kinetics400 [28] as the auxiliary video classification dataset for initial pretraining of the video encoder. For model performance evaluation, we use two popular temporal action localization benchmarks. (1) ActivityNet-v1.3 [22] contains 20K temporally annotated untrimmed videos with 200 action categories. In the standard evaluation protocol, these videos are divided into the training/validation/testing sets by the ratio of 2:1:1. (2) Human Action Clips and Segments (HACS-v1.1) [68] is a recent temporal action localization dataset. It contains 140K complete action segments from 50K videos including 200 action categories (the same ones as ActivityNet-v1.3).
Evaluation metrics: We adopt the mean Average Precision (mAP) rate at specified IoU thresholds as the main evaluation metrics. Following the standard evaluation setting, mAP values at a set of IoU thresholds, {0.5, 0.75, 0.95} are reported, as well as the average mAP over 10 different IoU thresholds [0.5 : 0.05 : 0.95].

heading: 4.2 Pre-training Methodology Comparisons

text:
Setting: In this set of experiments, we directly compare different methodologies for pre-training the video encoder. To compare with our proposed LoFi method, we first consider the most widely used pre-training method that optimizes the video encoder through the action classification task on an auxiliary dataset (Kinetics400 in our case). We denote this method as Action Classification Pre-training (ACP). To demonstrate the effect of video encoder pre-training, we also take into account an ImageNet pre-trained video encoder, which uses no video data. We refer to this baseline as Image Classification Pre-training (ICP). To adapt the video encoder to the target dataset, it can be further trained through an action classification task on a clip version of the target TAL dataset, using each positive segment as a training instance. We denote this variant as ACP+.
In this experiment, we train our model using the cyclic low-fidelity (C-LoFi) configuration with the long cycle strategy. Other configurations will be evaluated in Section 4.3.
Results: The results of the different video encoder pre-training methods are reported in Table 1. We make the following observations. (1) Without pre-training on a related auxiliary dataset, the model
performance could be significantly degraded (see row 1 v.s. row 2). This indicates the significance of the video encoder and its pre-training on large, relevant video data. (2) With action classification based pre-training on the target video data, the performance indeed improves to some degree (see row 1 v.s. row 3). This means that addressing the data distribution shift between the auxiliary dataset and the target dataset is essential. (3) Importantly, the biggest performance gains come from the proposed LoFi method, which instead solves the task discrepancy issue by optimizing the video encoder with the TAL task (see the last row). This indicates that although auxiliary video data is similar to the target data in distribution, the task-level differences would still pose obstacles harming the model performance. This confirms the motivation and hypothesis of this study. Once this obstacle is properly tackled with our low-fidelity pre-training, more significant performance gains can then be rewarded. Overall, this verifies the efficacy of the proposed method in pre-training the video encoder.

heading: 4.3 LoFi Configuration Comparisons

text:
Setting: We investigate different LoFi configurations. We use the setting as: rt = 4 for T-LoFi, rs = 2 for S-LoFi (note that this is applied in both spatial dimensions, thus being comparable to T-LoFi), rs = √ 2, rt = 2 for ST-LoFi, and cs = 16, cl = 1 for C-LoFi’s short and long cycle strategies, respectively. We include the standard pre-training strategy (i.e., ACP) to provide a baseline and facilitate comparisons.
Results: The results for ActivityNet-v1.3 and HACS-v1.1 are shown in Table 2. We provide the following observations. (1) Each of our proposed LoFi configurations can improve the video encoder, thus suggesting that spatial and temporal dimensions are both good selections for low-fidelity manipulation. (2) Integrating our LoFi configurations into a more advanced cyclic training strategy produces some further, although moderate, improvement. In particular, the long cycle leads to the best overall performance for both datasets.

heading: 4.4 Comparison with State-of-the-Art

text:
Setting: Following video encoder pre-training evaluation, we further conduct a system-level performance comparison with previous state-of-the-art methods. Whilst ResNet50-based (R50) methods are a common backbone choice for the video encoder, we still use a more lightweight ResNet18 (R18) for our method due to its higher efficiency in computation and memory. Furthermore, compared to the popular architecture design that uses two streams (one for RGB and one for optical flow), our method only uses RGB frames, avoiding the excessive costs incurred from computing optical flow and running a second forward pass.
Results: The results of our method are compared with existing alternatives in Table 3 for ActivityNet-v1.3 and Table 4 for HACS-v1.1. It is evident that our method can achieve the best performance among all the competitors, despite the single stream input modality and a much lighter video encoder backbone. This clearly demonstrates that tackling the pre-training of the video encoder is of particular importance for TAL, and that existing efforts towards improving the TAL head model have neglected it as a key model component. On ActivityNet-v1.3, it is encouraging to see that with a stronger pre-trained video encoder using our method and a shallower architecture, optical flow can be favourably eliminated without performance sacrifice (actually even enjoying better performance). This result is substantial, since the study of means to get rid of optical flow for more efficient action analysis is itself an important research problem [10].

heading: 4.5 Using Different Video Encoders

text:
Setting: Our LoFi method can be used in combination with different video encoders, as long as the backbone is end-to-end trainable. We compare the performance gains of our default encoder, i.e.ResNet18-based TSM, with a 3D-based alternative, i.e.an 18-layer R(2+1)D encoder [52], on ActivityNet-v1.3. Note that the default spatial resolution for R(2+1)D, as defined by the authors, is 112× 112 pixels. We thus use T-LoFi and maintain the default spatial resolution for both networks.
Results: The results are summarized in Table 5. We observe that with either TSM-R18 or R(2+1)D as video encoder, our method can similarly and consistently improve the performance of the stateof-the-art G-TAD method. This verifies that our LoFi method is generally effective and useful in training TAL models.

heading: 4.6 Scaling up to ResNet-34 and ResNet-50

text:
Setting: To evaluate the generalizability of our LoFi, we further evaluate two deeper video encoders: ResNet34/50-based TSM. We use the long cyclic low-fidelity configuration. Limited by the GPU memory size, we reduce the batch size accordingly whilst keeping all other hyper-parameters and the training protocol unchanged. This experiment is conducted on ActivityNet-v1.3 in comparison with the standard action classification pre-training (ACP) method as baseline.
Results: Table 6 shows that whilst the gains with deeper encoders are slightly reduced, LoFi can still consistently improve the results. This suggests good generalizability properties across varyingcapacity networks.

heading: 4.7 Comparison to Self-Supervised Learning

text:
Setting: We compare our method to two representative video self-supervised learning methods: Arrow of Time [56] and SpeedNet [4]. For both competitors, TSM-R18 is used as video encoder, and pre-trained on the Kinetics400 dataset. We use ActivityNet-v1.3 dataset for this experiment.
Results: From Table 7, we see that both SSL methods without action classification based supervision are clearly inferior for the TAL task (see row 2 and 3). When combined with the standard action classification pre-training (ACP), only slight performance gains can be achieved despite doubling the computational cost in video encoding (see row 4 and 5). This suggests marginal complementary benefit. Overall, this result indicates that the proposed LoFi optimization is superior over recent SSL alternatives in pre-training TAL’s video encoder.

heading: 5 Conclusion

text: In this work we have presented a simple and effective low-fidelity (LoFi) video encoder optimization method for achieving more effective TAL models. This is motivated by an observation that in existing TAL methods, the video encoder is merely pre-trained by action classification supervision on short video clips, lacking desired optimization w.r.t. the temporal localization supervision on the target dataset. Indeed, joint optimization itself is not novel. However, this is non-trivial to conduct for training a TAL model, due to large per-video size that would easily overwhelm the GPU memory, rendering it infeasible in practice. To overcome this obstacle, we propose to reduce the mini-batch construction configurations in the temporal and/or spatial dimensions of training videos so that end-to-end optimization becomes operable under the same memory condition. Extensive experiments demonstrate that our method can clearly improve the performance of existing off-the-shelf TAL models, yielding new state-of-the-art performance even with only RGB modality as input and a more lightweight backbone based single-stream video encoder on two representative TAL benchmarks.

heading: 6 Ethical considerations and broader impact

text: Any inherent bias present in the training data is likely to be captured by the learning algorithm given its data-driven nature. Deploying of the model into real-world scenarios should thus take that aspect into account. Furthermore, the method discussed in this paper focuses on a fundamental problem and as such its potential applications are hard to predict. However, to the best of our knowledge, there are currently no applications of this technology that raise ethical issues. Finally, biases based on gender, race or sexuality are unlikely, although not impossible.

heading: 7 Acknowledgements

text: This work was supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research through the Visual Computing Center (VCC) funding.

title: Low-Fidelity Video Encoder Optimization for Temporal Action Localization