Hierarchical classification offers an approach to incorporate the concept of mistake severity by leveraging a structured, labeled hierarchy. However, decoding in such settings frequently relies on heuristic decision rules, which may not align with task-specific evaluation metrics. In this work, we propose a framework for the optimal decoding of an output probability distribution with respect to a target metric. We derive optimal decision rules for increasingly complex prediction settings, providing universal algorithms when candidates are limited to the set of nodes. In the most general case of predicting a *subset of nodes*, we focus on rules dedicated to the hierarchical $\mathrm{hF}_{\beta}$ scores, tailored to hierarchical settings. To demonstrate the practical utility of our approach, we conduct extensive empirical evaluations, showcasing the superiority of our proposed optimal strategies, particularly in underdetermined scenarios. These results highlight the potential of our methods to enhance the performance and reliability of hierarchical classifiers in real-world applications.

This paper investigates the factuality of large language models (LLMs) as knowledge bases in the legal domain, in a realistic usage scenario: we allow for acceptable variations in the answer, and let the model abstain from answering when uncertain. First, we design a dataset of diverse factual questions about case law and legislation. We then use the dataset to evaluate several LLMs under different evaluation methods, including exact, alias, and fuzzy matching. Our results show that the performance improves significantly under the alias and fuzzy matching methods. Further, we explore the impact of abstaining and in-context examples, finding that both strategies enhance precision. Finally, we demonstrate that additional pre-training on legal documents, as seen with SaulLM, further improves factual precision from 63% to 81%.

Due to its collaborative nature, Wikidata is known to have a complex taxonomy, with recurrent issues like the ambiguity between instances and classes, the inaccuracy of some taxonomic paths, the presence of cycles, and the high level of redundancy across classes. Manual efforts to clean up this taxonomy are time-consuming and prone to errors or subjective decisions. We present WiKC, a new version of Wikidata taxonomy cleaned automatically using a combination of Large Language Models (LLMs) and graph mining techniques. Operations on the taxonomy, such as cutting links or merging classes, are performed with the help of zero-shot prompting on an open-source LLM. The quality of the refined taxonomy is evaluated from both intrinsic and extrinsic perspectives, on a task of entity typing for the latter, showing the practical interest of WiKC.

Link prediction is a fundamental task in machine learning for graphs. Recently, Graph Neural Networks (GNNs) have gained in popularity and have become the default approach for solving this type of task. Despite the considerable interest for these methods, simple topological heuristics persistently emerge as competitive alternatives to GNNs. In this study, we show that this phenomenon is not an exception and that GNNs do not consistently establish a performance standard for link prediction on graphs. For this purpose, we identify several limitations in the current GNN evaluation methodology, such as the lack of variety in benchmark dataset characteristics and the limited use of diverse baselines outside of neural methods. In particular, we highlight that integrating feature information into topological heuristics remains a little-explored path. In line with this observation, we propose a simple non-neural model that leverages local structure, node feature, and graph feature information within a weighted combination. Experiments conducted on large variety of networks indicate that the proposed approach outperforms existing state-of-the-art GNNs and increases generalisation ability. Contrasting with GNNs, our approach does not rely on any learning process and therefore achieves superior results without sacrificing efficiency, showcasing a reduction of one to three orders of magnitude in computation time.

International audience

Multivariate time series (MTS) have specific features that complicate their analysis: interactions in space and time between the MTS components, variable length, absence of trivial alignment between samples and high dimensionality. Hence, finding a representation of MTS from which we can extract meaningful information is a challenging task. In general, specific assumptions are needed to obtain a valuable representation. In this paper, we assume that a dataset of MTS samples has an underlying causal structure that we can exploit to represent samples. Our contribution is a new representation framework that consists of first finding the overall causality graph in a studied dataset and then mapping each sample onto G to obtain a causality-based representation. Since causality isG an important feature underlying MTS data, we claim and show that representating samples on G is meaningful. We name this method Sequence-to-Graph (Seq2Graph). We apply Seq2Graph on health monitoring tasks, using two MTS datasets coming from ageing mechanical systems.

Scikit-network is a Python package inspired by scikit-learn for the analysis of large graphs. Graphs are represented by their adjacency matrix in the sparse CSR format of SciPy. The package provides state-of-the-art algorithms for ranking, clustering, classifying, embedding and visualizing the nodes of a graph. High performance is achieved through a mix of fast matrix-vector products (using SciPy), compiled code (using Cython) and parallel processing. The package is distributed under the BSD license, with dependencies limited to NumPy and SciPy. It is compatible with Python 3.6 and newer. Source code, documentation and installation instructions are available online.

Clustering is a central problem in machine learning for which graph-based approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maximization problem, well-known in the graph partitioning literature. A solution of this relaxation gives to each element of the dataset a probability to belong to a given cluster, whereas a solution of the standard modularity problem is a partition. We introduce an efficient optimization algorithm to solve this relaxation, that is both memory efficient and local. Furthermore, we prove that our method includes, as a special case, the Louvain optimization scheme, a state-of-the-art technique to solve the traditional modularity problem. Experiments on both synthetic and real-world data illustrate that our approach provides meaningful information on various types of data.

We introduce the tree sampling divergence (TSD), an information-theoretic metric for assessing the quality of the hierarchical clustering of a graph. Any hierarchical clustering of a graph can be represented as a tree whose nodes correspond to clusters of the graph. The TSD is the Kullback-Leibler divergence between two probability distributions over the nodes of this tree: those induced respectively by sampling at random edges and node pairs of the graph. A fundamental property of the proposed metric is that it is interpretable in terms of graph reconstruction. Specifically, it quantifies the ability to reconstruct the graph from the tree in terms of information loss. In particular, the TSD is maximum when perfect reconstruction is feasible, i.e., when the graph has a complete hierarchical structure. Another key property of TSD is that it applies to any tree, not necessarily binary. In particular, the TSD can be used to compress a binary tree while minimizing the information loss in terms of graph reconstruction, so as to get a compact representation of the hierarchical structure of a graph. We illustrate the behavior of TSD compared to existing metrics on experiments based on both synthetic and real datasets.

The paper relates to multi-resource sharing between flows with heterogeneous requirements as arises in networks with wireless links or software routers implementing network function virtualization. Bottleneck max fairness (BMF) is a sharing objective in this context with good performance. The paper shows that BMF results when local fairness is imposed at each resource while flow rates are controlled by an end-to-end window. We analytically prove convergence to BMF under a fluid model when flows share a network limited to 2 resources while numerical results confirm BMF convergence for larger networks. Simulation results illustrate the impact of packetized transmission.

We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data.

The main weakness of coordination techniques in LTE-Advanced networks is the extra resource consumption incurred by the joint transmission from several base stations. In this paper, we propose a new scheduling policy that performs coordination primarily for users staying at the cell edge, without mobility. Other cell-edge users are likely to move and to be served in better radio conditions where cell coordination is not required. We compare the performance of this algorithm to other usual scheduling policies in the presence of elastic traffic through the analysis of flow-level traffic models.

Although adaptive streaming is becoming a preponderant technology for online streaming providers, the design of video chunks has not been well examined in the literature. This issue becomes more important in a mobile context characterized by a large heterogeneity of radio conditions between users. We develop in this paper some flow-level models to assess the impact of different video chunk durations. Our analytical and simulation results show that smaller chunk durations can improve the video smoothness and reduce buffer starvation events. However, this would require to increase HTTP signaling and to manage many headers and URLs of video chunks. To resolve this challenge, we propose to transmit multiple chunks instead of one chunk in an HTTP request. We show that our proposal can achieve better video smoothness as the case of deploying shorter chunk duration while keeping the same number of video chunks.

In this paper, we assess the performance of inter-cell coordination in the presence of mobility. This performance depends primarily on the resource allocation scheme. Indeed, a scheduling strategy which may seem efficient when users are static can lead to bad performance when users are mobile. Several scheduling policies are investigated. Their performance critically depends on their ability to predict users' mobility. The results are based on the analysis of flow-level traffic models.

This paper proposes a performance model for mobile networks carrying adaptive streaming traffic. The proposed model takes into account the flow dynamics in addition to the main parameters influencing the performance of adaptive streaming, such as the playout buffer and the video bit rates. We show how to compute several performance metrics like the average video bit rate, the deficit rate, defined as the probability of having an instantaneous throughput lower than the chosen video bit rate, and the average buffer surplus, related to the amount of data accumulated in the buffer. Considering the coexistence of multiple services and heterogeneous radio conditions that make the exact solution intractable, we propose a simple yet accurate approximation that is easy to integrate in the operator's dimensioning tools. Our numerical results investigate the performance trade-offs between the different parameters of the adaptive streaming service.

Designing efficient and fair algorithms for sharing multiple resources between heterogeneous demands is becoming increasingly important. Applications include compute clusters shared by multi-task jobs and routers equipped with middleboxes shared by flows of different types. We show that the currently preferred objective of Dominant Resource Fairness (DRF) has a significantly less favorable efficiency-fairness tradeoff than alternatives like Proportional Fairness and our proposal, Bottleneck Max Fairness. We propose practical algorithms to realize these sharing objectives and evaluate their performance under a stochastic demand model. It is shown, in particular, that the strategyproofness property that motivated the choice of DRF for an assumed fixed set of jobs or flows, is largely irrelevant when demand is dynamic.

In this paper, we discuss several Coordinated Multi-Point (CoMP) schemes proposed for LTE- Advanced systems. We investigate their benefits in a multi-antenna beamforming system where multiple cells may share their resources and jointly coordinate their transmissions to improve the performance at cell edge and the overall system capacity. We evaluate the system performance by combining flow-level analysis with numerical results from LTE-Advanced network simulator. We show that the intra-site coordination brings significant gains in beamforming systems, especially with the joint transmission scheme where the user throughput and the system capacity are improved.

In this paper, we assess the performance gains of mobility on the downlink of cellular data networks. These gains are only due to the elastic nature of traffic and thus observed even under a blind, fair scheduling scheme: data are more likely transmitted when users are close to the base stations, in good radio conditions. This phenomenon is further amplified by opportunistic scheduling schemes that exploit multi-user diversity. The results are based on the analysis of flow-level traffic models and validated by system-level simulations.

In recent years, Storage as a Service Cloud gained popularity among both companies and private users. However, security and interoperability issues still have to be adequately faced and solved. In this work, we propose a simple, secure, and privacy-preserving architecture for inter-Cloud data sharing. The proposed solution relies on open standards for both sharing and communication mechanisms, thus ensuring durability, robustness, and compatibility of the approach in the current Internet.

Carrier aggregation and multi-flow transmission are among the most important features of HSPA+. While the former allows users to be served simultaneously by several carriers in the same sector, the latter enables adjacent sectors to simultaneously schedule different data streams to the same user in their overlapping region. In this paper, we investigate the inter-operation of these two features. We evaluate the flow-level performance using a method based on network simulation coupled with Markov chain analysis. Results in single-carrier mode show an improvement in throughput at low load and an efficient load balancing across sectors at high load. In multi-carrier mode, we show that coordination is no more recommended since it does not achieve any throughput gain over the classical multi-carrier system. This is due to the actual status of the standard that limits the number of carriers that can be used for the multi-flow transmission to two. However, if this restriction is released in the standard, our results show that multi-flow transmission would bring significant gains.

Among the several features that are foreseen for increasing the capacity of cellular systems, Multi-user multiple-input multiple-output (MU-MIMO) is considered as a key enabling technology. Particularly, MU-beamforming is a powerful means of increasing the system capacity and throughput by creating several spatial signals to different users on the same time/frequency resource. In this paper, we develop an analytical model for MU-beamforming based on queuing theory combined with network simulations. The proposed framework is used for evaluating the potential gains in terms of capacity and throughput in LTE-Advanced system. Several scenarios are studied, with and without beamforming. Results show an important gain of SU-beamforming over the classical system without beamforming and a further gain of MU-beamforming, especially at high loads.

We consider an infinite-armed bandit problem with Bernoulli rewards. The mean rewards are independent, uniformly distributed over $[0,1]$. Rewards 0 and 1 are referred to as a success and a failure, respectively. We propose a novel algorithm where the decision to exploit any arm is based on two successive targets, namely, the total number of successes until the first failure and the first $m$ failures, respectively, where $m$ is a fixed parameter. This two-target algorithm achieves a long-term average regret in $\sqrt{2n}$ for a large parameter $m$ and a known time horizon $n$. This regret is optimal and strictly less than the regret achieved by the best known algorithms, which is in $2\sqrt{n}$. The results are extended to any mean-reward distribution whose support contains 1 and to unknown time horizons. Numerical experiments show the performance of the algorithm for finite time horizons.

High Speed-Single Frequency Network (HS-SFN) is one of the possible multipoint transmission techniques proposed in the 3GPP standard for High Speed Downlink Packet Access (HSDPA) in order to improve network performance, especially at the cell edge. It allows neighboring cells to transmit simultaneously the same data stream to a User Equipment (UE) in the Handover region (HO). In order to evaluate the user-level performance of this technique, we develop a method based on network simulation coupled with Markov chain analysis. It shows that when the HS-SFN technique is performed in the HO region between adjacent cells, the user data rates increase significantly. However, this is true only when involved cells are partially loaded, which is not always the case. We thus propose an optimized approach that adapts the coordination area based on the average offered traffic observed in the network. Network performance is then improved at any load.

This paper studies the radio capacity improvement provided by an HSPA+ key feature: dual-cell, combined with MIMO. The proposed method combines drive test measurements, link-level simulations, and a queuing theory-based statistical capacity model, thereby providing a reliable estimate of the network radio capacity. Simulation results show that dual cell combined with MIMO and non-linear receivers using Successive Interference Cancellation (SIC) significantly increases network radio capacity. Those results confirm that HSPA networks evolutions are promising.

We present a packet scheduler called "shortest queue first" (SQF) that aims at protecting audio and video traffic from the congestion caused by data traffic. Unlike standard solutions, the services to be handled with priority are not known in advance. It is rather the traffic characteristics of audio and video applications that are used to detect their delay sensitivity. The SQF algorithm does not require any prior configuration of the network and, as such, adapts to the fast evolution of traffic and usage. The performance of the proposed solution is demonstrated using both analysis and experiments on a testbed emulating a residential access line.

The downlink capacity of cellular networks is known to be strongly limited by inter-cell interference. In order to mitigate this interference, a number of frequency reuse schemes have recently been proposed. In this paper, we compare the potential capacity gains of these schemes accounting for the random nature of traffic.

In this paper we seek to characterize the behavior of the Internet in the absence of congestion control. More specifically, we assume all sources transmit at their maximum rate and recover from packet loss by the use of some ideal erasure coding scheme. We estimate the efficiency of resource utilization in terms of the maximum load the network can sustain, accounting for the random nature of traffic. Contrary to common belief, there is generally no congestion collapse. Efficiency remains higher than 90% for most network topologies as long as maximum source rates are less than link capacity by one or two orders of magnitude. Moreover, a simple fair drop policy enforcing fair sharing at flow level is sufficient to guarantee 100% efficiency in all cases.

When IEEE 802.11 access points (APs) share the same channel in a multi-cell WLAN, their downlink transmissions can interfere. Typically, an AP whose scheduled transmission to some user is blocked by another cell will apply the CSMA/CA back-off algorithm and continue to make reattempts to the same user. Through analytical models and simulations, we demonstrate that significant capacity gains can be attained by choosing an alternative destination for the reattempt. Results demonstrate that a simple random choice of alternative destination brings almost the same gain as a more sophisticated algorithm that seeks to maximize spatial reuse.

This paper contributes to the definition of an association policy for a multi-channel, multiple AP WLAN that depends on both physical rate and realised throughput. We show that existing proposals are inefficient when several APs share the same channel and define a new policy that is demonstrated to be close to optimal. Policies are compared through their traffic capacity defined as the network stability limit. We determine this capacity analytically using the fluid limit method for some simple network configurations deriving insight into the structure of the optimal policy. The quasi-optimality of our proposal is verified by simulation of a more complex network configuration.

Performance of WLANs has been extensively studied during the past few years. While the focus has mostly been on isolated cells, the coverage of WLANs is in practice most often realised through several cells. Cells using the same frequency channel typically interact through the exclusion region enforced by the RTS/CTS mechanism prior to the transmission of any packet.

Several peer-to-peer systems for live streaming have been recently deployed (e.g. CoolStreaming, PPLive, SopCast). These all rely on distributed, epidemic-style dissemination mechanisms. Despite their popularity, the fundamental performance trade-offs of such mechanisms are still poorly understood. In this paper we propose several results that contribute to the understanding of such trade-offs.

The potential for exploiting rate variations to increase the capacity of wireless systems by opportunistic scheduling has been extensively studied at packet level. In the present paper, we examine how slower, mobility-induced rate variations impact performance at flow level, accounting for the random number of flows sharing the transmission resource. We identify two limit regimes, termed fluid and quasistationary, where the rate variations occur on an infinitely fast and an infinitely slow time scale, respectively. Using stochastic comparison techniques, we show that these limit regimes provide simple performance bounds that only depend on easily calculated load factors. Additionally, we prove that for a broad class of fading processes, performance varies monotically with the speed of the rate variations. These results are illustrated through numerical experiments, showing that the fluid and quasistationary bounds are remarkably tight in certain usual cases

The performance of wireless data systems has been extensively studied in the context of a single base station. In the present paper we investigate the flow-level performance in networks with multiple base stations. We specifically examine the complex, dynamic interaction of the number of active flows in the various cells introduced by the strong impact of interference between neighboring base stations. For the downlink data transmissions that we consider, lower service rates caused by increased interference from neighboring base stations result in longer delays and thus a higher number of active flows. This in turn results in a longer duration of interference on surrounding base stations, causing a strong correlation between the activity states of the base stations. Such a system can be modelled as a network of multi-class processor-sharing queues, where the service rates for the various classes at each queue vary over time as governed by the activity state of the other queues. The complex interaction between the various queues renders an exact analysis intractable in general. A simplified network with only one class per queue reduces to a coupled-processors model, for which there are few results, even in the case of two queues. We thus derive bounds and approximations for key performance metrics like the number of active flows, transfer delays, and flow throughputs in the various cells. Importantly, these bounds and approximations are insensitive, yielding simple expressions, that render the detailed statistical characteristics of the system largely irrelevant.

A large variety of communication systems, including telephone and data networks, can be represented by so-called Whittle networks. The stationary distribution of these networks is insensitive, depending on the service requirements at each node through their mean only. These models are of considerable practical interest as derived engineering rules are robust to the evolution of traffic characteristics. In this paper we relax the usual assumption of static routing and address the issue of dynamic load balancing. Specifically, we identify the class of load balancing policies which preserve insensitivity and characterize optimal strategies in some specific cases. Analytical results are illustrated numerically on a number of toy network examples.

We consider a network model where bandwidth is fairly shared by a dynamic number of elastic and adaptive streaming flows. Elastic flows correspond to data transfers while adaptive streaming flows correspond to audio/video applications with variable rate codecs. In particular, the former are characterized by a fixed size (in bits) while the latter are characterized by a fixed duration. This flow-level model turns out to be intractable in general. In this paper, we give performance bounds for both elastic and streaming traffic by means of sample-path arguments. These bounds present the practical interest of being insensitive to traffic characteristics like the distributions of elastic flow size and streaming flow duration.

International audience

We represent a data network as a set of links shared by a dynamic number of competing flows. These flows are generated within sessions and correspond to the transfer of a random volume of date on a pre-defined network route. The evolution of the stochastic process describing the number of flows on all routes, and the performance of the data transfers, depend on how link bandwidth is allocated between concurrent flows. We use some key properties of Whittle networks to characterize the class of bandwidth allocations which are insensitive in the sense that the stationary distribution of this stochastic process does not depend on any traffic characteristics (session structure, data volume distribution) except the traffic intensity on each route. This insensitivity property presents the practical interest of allowing the development of robust engineering rules independently of precise traffic statistics.

We suggest that satisfactory statistical performance guarantees for streaming flows can be fulfilled when their packets receive expedited forwarding in non-preemptive priority queues. This relies on the conjecture that jitter remains negligible in the network such that performance measures can be bounded by assuming flows constitute Poisson arrival processes of maximum transfer unit (MTU) sized packets. We provide analytical and simulation evidence in support of this conjecture and show how it leads to simple engineering rules for both constant and variable rate streaming traffic.

In this paper we study the statistics of the realized throughput of elastic document transfers, accounting for the way network bandwidth is shared dynamically between the randomly varying number of concurrent flows. We first discuss the way TCP realizes statistical bandwidth sharing, illustrating essential properties by means of packet level simulations. Mathematical flow level models based on the theory of stochastic networks are then proposed to explain the observed behavior. A notable result is that first order performance (e.g., mean throughput) is insensitive with respect both to the flow size distribution and the flow arrival process, as long as "sessions" arrive according to a Poisson process. Perceived performance is shown to depend most significantly on whether demand at flow level is less than or greater than available capacity. The models provide a key to understanding the effectiveness of techniques for congestion management and service differentiation.

End-to-end congestion control mechanisms such as those in TCP are not enough to prevent congestion collapse in the Internet, and they must be supplemented by control mechanisms inside the network. The IRTF has singled out random early detection (RED) as one queue management scheme recommended for rapid deployment throughout the Internet. However, RED is not a thoroughly understood scheme-witness for example how the recommended parameter setting, or even the various benefits RED is claimed to provide, have changed over the past few years. In this paper, we describe simple analytic models for RED, and use these models to quantify the benefits (or lack thereof) brought about by RED. In particular, we examine the impact of RED on the loss and delay suffered by bursty and less bursty traffic (such as TCP and UDP traffic, respectively). We find that: (i) RED does eliminate the higher loss bias against bursty traffic observed with tail drop, but not by decreasing the loss rate of bursty traffic, rather by increasing that of non bursty traffic; (ii) the number of consecutive packet drops is higher with RED than tail drop, suggesting RED might not help as anticipated with the global synchronization of TCP flows; (iii) RED can be used to control the average queueing delay in routers and hence the end to end delay, but increases the jitter of non bursty streams. Thus, applications that generate smooth traffic, such as interactive audio applications, will suffer higher loss rates and require large playout buffers, thereby negating at least in part the lower mean delay brought about by RED.