Tancrède Almeras

Arthur Gronvold

Arie Van Der Lee

Bruno Clair

Cédric Montero

Almeras Tancrède

Gronvold Arthur

Van Der Lee

Clair Bruno

Montero Cédric

Contribution of cellulose to the moisture-dependent elastic behaviour of wood Composites Science and Technology

Keywords: wood, cellulose, X-ray diffraction, micromechanics, crystal strain

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Wood has a hierarchical structure, with several levels of organisation. Wood tissue at the submillimetric scale is made of different kinds of cells, namely fibres (or tracheids) and rays, and sometimes vessels and axial parenchyma. Among these cells, fibres are from far the most abundant and stiff. Fibres are long hollow cells, with cell walls glued to adjacent cell walls, that form a honeycomb structure. The cell wall is made of several concentric layers, and forms a multilayer structure. Each wall layer is a fibre composite layout where the matrix phase is a mixture of lignin and hemicellulose, and the fibres (called microfibrils) are made of cellulose. The cellulose microfibrils are arranged helically in the cell, with a characteristic angle for each layer, termed microfibrils angle. Cellulose is present in a partly crystalline form, where amorphous cellulose is organised in serie and in parallel with cellulose crystallites. Crystalline cellulose is from far the stiffest constituent of wood. Its extraordinary large stiffness (approx. 135 GPa [START_REF] Eichhorn | Modelling the crystalline deformation of native and regenerated cellulose[END_REF][START_REF] Young | Deformation mechanisms in polymer fibres and nanocomposites[END_REF][START_REF] Sakurada | Experimental determination of the elastic modulus of crystalline regions in oriented polymers[END_REF] ) provides the good properties of wood in the axial direction. The mechanical behaviour of wood depends on the organisation of the material at all levels. The link between structure and properties is therefore the key to predict the variability of the wood material and understand its origin. Structure and properties can be linked through multiscale modelling. The principle of this modelling is using hierarchical models, where each model predicts the behaviour at one scale, based on the structure and behaviour at lower scales. Such schemes have been developed for wood to model different kinds of behaviour, such as drying shrinkage, elastic and viscoelastic behaviours [4; 5]. Another key element of the models is the assumption used for the kinematics of elements, i.e. how they deform relatively to each other. Most of the time, these assumptions are based on an idealization of wood structure [START_REF] De Borst | Structure-function relationships in hardwood-insight from micromechanical modelling[END_REF] and are particularly difficult to assess. In material science, different methods are used to evaluate the stress transfer between the fibre and the matrix phase in fibre-reinforced composites. These methods are based on the measurement of strain at the molecular scale, using Raman spectroscopy, infrared spectroscopy or X-ray diffraction. They have been used to assess the performance and characterize the kinematics of composite materials [3; 6]. X-ray diffraction methods have been used for wood to evaluate how the cellulose crystal strains in response to different loading, such as elastic [START_REF] Suzuki | Mechanical deformation of crystal lattice of cellulose in Hinoki wood[END_REF][START_REF] Nakai | The relationship between macroscopic strain and crystal lattice strain in wood under uniaxial stress in the fiber direction[END_REF][START_REF] Nakai | Mechanical behavior of the crystalline region of wood and the piezoelectric response of wood in tension tests[END_REF][START_REF] Nakai | Mechanical behavior of the crystal lattice of natural cellulose in wood under repeated uniaxial tension stress in the fiber direction[END_REF][START_REF] Peura | The effect of axial strain on crystalline cellulose in Norway spruce[END_REF][START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF], viscoelastic [13; 14] or mechanosorptive [START_REF] Moriizumi | Viscoelasticity and structure of wood. IV: Behavior of crystal lattice strain depended on moisture content an time[END_REF] strains, hygro-thermal treatments [START_REF] Toba | Mechanical interaction between cellulose microfibrils and matrix substances in wood cell walls induced by repeated wet-and-dry treatment[END_REF][START_REF] Toba | Crystallization of cellulose microfibrils in wood cell wall by repeated dry-and-wet treatment, using X-ray diffraction technique[END_REF][START_REF] Toba | On the mechanical interaction between cellulose microfibrils and matrix substances in wood cell walls: effects of chemical pretreatment and subsequent repeated dry-and-wet treatment[END_REF] , chemical treatments [START_REF] Toba | On the mechanical interaction between cellulose microfibrils and matrix substances in wood cell walls: effects of chemical pretreatment and subsequent repeated dry-and-wet treatment[END_REF], drying [17; 18], stress release [17; 18] or stress induced by biological transformations [START_REF] Clair | Maturation stress generation in poplar tension wood studied by synchrotron radiation microdiffraction[END_REF]. Montero et al. [START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF] probed the behaviour of crystalline cellulose during elastic deformations of poplar wood. The results showed that the deformation of crystalline cellulose is lower than the macroscopic wood strain, and that this difference could not be explained by the projection effect of microfibril angle alone, but originated in one or more elements associated in series with crystalline cellulose. Hypotheses for the localization of these contributions are related to the "non-ideal" nature of wood structures, where elements at different scales may not be completely straight and have a finite length, leading to bending or shearlag effects for which strain happen without straining the cellulose crystal. Understanding the origin and behaviour of these localized strain is essential for understanding how the wood structure ensures a good transmission of mechanical stress from the macroscopic scale to its stiffest constituent at a molecular scale. Here we aim at analysing the moisture-dependant behaviour of wood. The ratio between crystal and macroscopic strain is measured during elastic loading using an improved methodology based on Montero [START_REF] Peura | The effect of axial strain on crystalline cellulose in Norway spruce[END_REF], and this ratio is compared between wood in wet and dry states, to probe the contribution of cellulose to wood strain and its change with moisture content.

Material and methods

Wood material and macroscopic measurements

Experiments were performed on wood specimens taken in the same area of a board of European spruce (Picea abies). Wood was first air-dried, then earlywood specimens of 50 x 3.2 x 1.8 mm (LxTxR) were cut far enough of the pith to neglect the annual ring curvature, and consider the R and T directions as uniform over the specimen. Specimens were polished with a precision motorized sander to make sure that their dimensions were uniform and that surfaces were parallel. The basic density of the specimens was 364 kg/m 3 (± 16 S.D.). The mean microfibril angle (MFA) of each specimen was measured by X-ray diffraction following the methodology described by Cave [START_REF] Cave | Theory of X-ray measurement of microfibril angle in wood[END_REF]. A total of 18 specimens with similar MFA (11.8° ±0.6 S.D.) were selected for this experiment. Nine of them were stabilized at ambient air-dry conditions (approx. 40% RH), and will hereafter be referred to as "dry specimens". Their average moisture content was 6.0% (± 0.4 S.D.). The other 9 specimens were watersaturated by immersion in water in a chamber submitted to vacuum cycles during 7 days, and will hereafter be referred to as "wet specimens". The modulus of elasticity (MOE) of the specimens was measured using a dedicated 4 point bending apparatus placed into a conventional testing machine. The specific modulus (E/d) was computed as the ratio of MOE to basic density.

Bending set-up and measurement of macroscopic strain

The specimens were used to perform in situ four-point bending tests while measuring axial lattice distance of crystalline cellulose. The set-up used is similar to that used by Montero et al. [START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF]. The bending device is illustrated in Fig. 1. Wood macroscopic strain were measured with 5 mm-long strain gages (Kyowa KFG-5-120-C1-11-L1M3R) glued with cyanoacrylate, in the middle of the top and bottom LxR surfaces of the specimen. The gages were connected to a data-logger (Vishay Model P3) recording the strain level. Four small pieces of steel were pasted on the upper and lower surfaces at the position of the loading points (Fig. 1) to minimize the effect of indentation of cylinders on wood during the test. A screw on the top of the bending device enabled the control of the displacement of the upper spans in the T direction, while the lower spans were fixed. The displacement was increased with the screw, until the desired strain level (average of the two strain gages = 0.15% and 0.24% for wet and dry specimens respectively) was reached. Temperature and relative humidity (RH) in the testing chamber were continuously measured during the tests, and ranged between 35-45% RH and 24-26°C.

X-ray diffraction set-up for measuring cellulose strain

The change in lattice distance of crystalline cellulose was calculated from the shift of the 004 cellulose crystal plane during bending. The bending device was placed in an X-ray goniometer (Agilent Technologies Gemini S), using a CuK source (wavelength =0.154 nm, energy E=8.05 keV) monitored at 40 kV and 40 mA. The spot size was 800 µm in diameter. In order to optimise the intensity of the (004) cellulose diffraction signal, the specimen was rotated at an angle =17° to the X-rays (corresponding 3

to the Bragg angle of the cellulose 004 plane with this wavelength), and the detector of an angle 2=34° (Fig. 2). Also, to maximize the resolution of the recorded pattern, the CCD detector (2048x2048; 31µm/pixel; bin1) was placed at a distance D=135 mm of the specimen (Fig. 2), acquisition focusing on the 004 cellulose peak. Gold powder (with particles of 5 µm diameter) was placed on the back LxT surface of the specimen, to calibrate the distance between the specimen surface and the CCD detector, by detection of the angle of the (111) reflection of gold on each image. Dry specimens were exposed to X-rays during 60 seconds. Wet specimens, yielding lower signal intensity due to water absorption, were exposed during 90 seconds. To avoid any drying during the test of wet specimens, the bending device was enveloped in a cellophane film with water-saturated absorbent paper, ensuring a water-saturated atmosphere surrounding the specimen. The specimens were scanned at 30 positions along the Z-axis (Fig. 2) from top to bottom, by moving up the device between two scans. The Z-position of the bending device was measured using a displacement sensor (Mitutoyo Absolute Digimatic Indicator; 1 µm accuracy). Steps of 100 µm were used for the 10 first scans, then 200 µm for the 10 following scans, and then 100 µm for the 10 last scans. This procedure was chosen to maximize the precision near the upper and lower surfaces of the specimen, where the strain is the largest. Given the size of the steps and that of the spot, successive probed wood areas partly overlap. At each step, the scan produced a pattern of X-ray diffraction including reflection peaks of cellulose (004) cellulose and gold (111) gold as illustrated on Fig. 2.

Signal integration and processing

Each pattern was integrated in the azimuthal direction (from  = -20° to  = +20° and from 2 =  to 24°), yielding a one-dimensional signal expressing intensity variations as a function of the diffraction angle . The diffraction angle is related to the lattice distance via Bragg's law: d=n/(2sin) (Eq. 1) (with d=lattice distance, =wavelength of the X-ray,  = diffraction angle; and n=1). Figure 3 shows a typical raw pattern of intensity versus lattice distance. On this curve, two peaks are clearly distinct: one due to the diffraction of X-rays on the (004) cellulose crystal planes, and the other due to the diffraction of X-rays on (111) gold crystal planes. In order to remove the baseline of the background signal (due to the scattering of air, water and amorphous material), the curve was fitted by a 2 nd order polynomial in domains far enough from the peaks (Fig. 3-a). The corrected curve is computed as the difference between the raw curve and the fitted baseline (Fig. 3-b). Peaks of (004) cellulose and (111) gold on the corrected curve are then fitted to a 4 nd order polynomial in a central area of the peak including inflexion points of the peaks (Fig. 3-b). This polynomial order yielded very stable fits, accounting for the possible asymmetry and kurtosis of the real peaks. The lattice distance at maximum intensity of the two peaks (d (004)cellulose and d (111)gold ) was determined analytically from the fitted polynomial coefficients. As the beam has a diameter of 800 µm, the d (004)cellulose represents the average of the (004) lattice distance of all the cellulose crystallites contained in the volume of wood crossed by the X-rays (~1.1 mm 3 ). Taking into account wood density, assuming that wood roughly contains a mass fraction of 30% crystalline cellulose, and that cellulose crystallites are roughly 3 nm in width and 30 nm in length, the order of magnitude of the number of crystallites contained in the wood volume cross by X-rays is larger than 10 14 . This large number of crystallites enable to consider changes in lattice distance as representative of an average behaviour of crystalline cellulose.

Evaluation of cellulose crystal strain

Complete sets of 30 exposures were recorded at the initial state for each specimen, producing the initial lattice distance (d (004)cellulose_initial ) at each position in the beam height. The same series of measurements was performed after bending, producing the final lattice distance (d (004)cellulose_final ) at each position. The total time of a set of scan is approximately 45 minutes for dry specimens and 60 minutes for wet specimens. The final (bent) state is reached after having imposed a displacement inducing the desired macroscopic strain and then blocked with the screw to avoid any possible creep. As the specimen moves along Z during this operation, the position of each scan is not exactly the same between initial and final states, and therefore an interpolation procedure was necessary to match data along specimen height (see Appendix). Slight out-of-plane movements of the specimen may also happen during the bending. These movements directly affect the position of the peak on the CCD camera, and thus induce a possible bias on the estimation of lattice distance. The evaluation of crystal strain is very sensitive to this possible artefact and the gold signal was used to correct for it (see Appendix). The average axial strain of the cellulose crystal was then calculated at each of the positions as: 004)cellulose_initial (Eq. 2) where  (111)gold represents bias evaluated from the displacement of gold peak between initial and final state (see Appendix).

 cellulose = [(d (004)cellulose_final  d (004)cellulose_initial )   (111)gold ] / d (
During the numerical data processing, points with a too low diffracted signal (extreme points where the X-ray beam is tangent to the specimen and thus contains a minor amount of wood, 2 or 3 points on each side for the dry and wet specimens, respectively) were ignored and are not presented in the results.

Projection of the cellulose axial strain along in the wood fibre axis

The raw ratio of cellulose crystal strain to macroscopic strain ( raw = cellulose / macro ) was evaluated as the slope of their relationship, after removing outliers at the top and bottom of the profile. The longitudinal direction of cellulose differs from the longitudinal direction of the specimen by the MFA. Considering this, in order to compare strain in the same direction, the cellulose axial strain was projected along the longitudinal direction of the specimen. The same correction as the one used by [START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF], has been used:

 proj =  cellulose / (cos²(µ) LT sin²(µ)) (Eq.
3) Where µ is the MFA of the specimen, and LT , the Poisson's ratio of the cell wall, is evaluated with a micromechanical model (similar to that used in Alméras et al. [START_REF] Alméras | Modelling anisotropic maturation strains in wood in relation to fibre boundary conditions,microstructure and maturation kinetics[END_REF]) under the assumption of shear restraint and thin cell wall (yielding  LT ~0.7 for µ=12°). This projection yields a slightly larger strain than the original crystal strain, and would represent the cell wall strain in the limit case where its shearing is entirely restrained by adjacent cell walls, and cellulose microfibrils are entirely crystalline, perfectly straight, of infinite length and perfectly cohesive with the cell wall matrix material. The projected strain ratio ( proj ) was computed as  proj / micro .

Results

Elastic modulus

The MOE of the dry specimens ranged between 13 and 17 GPa, with a mean of 15.4 GPa (± 1.1 S.D.) (Table 1). Their specific modulus ranged between 36 and 46 GPa.m 3 /kg, with a mean of 42.1 GPa.m 3 /kg (± 3.2 S.D.) (Table 1). The MOE for the wet specimens ranged from 9 to 11 GPa with a mean of 10.0 GPa (± 0.5 S.D.). Their specific modulus ranged between 21 and 26 GPa.m 3 /kg with a mean of 28.7 GPa.m 3 /kg (± 1.8 S.D.) (Table 2). The two sets of specimens are well matched presenting a similar range of MFA and density levels.

Sample

Relationship between macroscopic strain and cellulose crystal strain: dry specimens

Figure 4 shows a typical profile of strain along the height of the specimens. Macroscopic strains, measured with strain gages on both sides, were linearly interpolated between the upper and lower side of the specimen, according to Benoulli hypothesis. At each point, the projected crystal strain is slightly larger than the crystal strain, and slightly lower than macroscopic strain. Overall, the relation between the strain and the position in the specimen are approximately linear, except for 1 to 3 points located near the border. Relationships between projected crystal strain and macroscopic strain are shown in Fig 5 . This relation is most of the time approximately linear (mean R²=0.995), except for the points located near the border. The ratio of crystal strain to macroscopic strain are shown in Table 1, for both raw and projected crystal strains. The raw ratio ( raw ) range between 0.78 and 0.93, with a mean of 0.85 (±0.06 S.D.). The projected ( proj ) ratio ranges between 0.84 and 1.00 (mean 0.91 ±0.06 S.D.).

Relationship between macroscopic strain and cellulose crystals strain: wet specimens

Results for wet specimens are shown in Figure 6 and Table 2. The degree of linearity is lower than for dry specimens, but the quality of the regressions are satisfying anyway when border points are avoided (R² ranging between 0.975 and 0.998). The strain ratios were lower than in the dry case: raw ratios range between 0.55 and 0.81 (mean 0.64 ±0.09 S.D.), and projected ratios between 0.60 and 0.87 (mean 0.69 ±0.10 S.D.).

Discussion

Linearity between macroscopic and crystal strain in the stress-strain linear domain

The slight deviation from linearity in the stress-strain linear domain can be ascribed to material heterogeneity and also to the cumulated errors due to the data processing. Montero et al. ( 2012) had similar results on poplar at dry state and during an elastic bending test. The degree of linearity of the relationship between macroscopic and crystal strain has been improved in the present study due to an improved procedure of data processing. The main improvements are: a higher order polynomial fit to determine the position of the peak, enabling to take into account more points and having a much more stable fit; an improved method of spatial interpolation to take into account the change in impacted area between initial and final states; a more stable correction of out-of-plane movements obtained by fitting the profile of position of the gold peaks as a rigid body movement (see Material and Methods and Appendix for details).

The calculated ratio  for the dry specimens are smaller than 1, even after considering the projection effect of MFA. This result is consistent with several studies comparing cellulose crystal strain to macroscopic strain for small macroscopic strain values. Using a similar procedure on dry poplar wood, Montero et al. ( 2012) reported a ratio of 0.85 after taking into account the projection effect of the MFA, in a bending experiment in the linear domain. Other studies involving tensile tests [7-10; 14] report ratios ranging from 0.3 to 0.93, for different wood species, MFA, moisture content and strain level. Our results strongly confirm the hypothesis that a source of strain  add is additive to the projected cellulose crystal strain  proj in the wood media. This additive strain increases linearly with macroscopic strain:  add = (1-) macro . Results show that the ratio  proj. varies considerably with the moisture content ( proj. dry =0.91 vs.  proj. wet =0.67). This implies that, at a given level of macroscopic strain, the contribution of crystalline cellulose to the total strain is lower when wood is wet than dry. Conversely, the contribution of the additive strain increases with moisture content. It represents 9% and 33% of the total strain for dry and wet specimens, respectively. [START_REF] Moriizumi | Viscoelasticity and structure of wood. IV: Behavior of crystal lattice strain depended on moisture content an time[END_REF] did similar measurements of the crystal strains as a function of wood moisture content (see Table 3). A decrease in strain ratio with increasing moisture content was observed, consistently with present study. This decrease was however lower than observed in the present study.

Modelling the sources of moisture-dependent compliance

The compliance of wood (inverse of the modulus of elasticity) can be modelled as the sum of a contribution of two elements. The first contribution originates from the strain that occurs simultaneously with cellulose strain and the second for the source of additional strain C add . This first contribution is equivalent to the strain of an "ideal" cell wall (i.e. a cell wall where cellulose microfibrils are entirely crystalline, perfectly straight, of infinite length and perfectly cohesive with the cell wall matrix material), and will therefore be termed C ideal . Then we can write:

C tot = C ideal + C add As these two contributions can be modeled in series, the stress is the same in each of them, so that the compliances can be computed as:

C ideal =  proj. / E C add = (1 proj. )/ E Table 4 indicates the compliances for dry and wet specimens, as well as the change between wet and dry states. Results indicate that, although wood compliance increased by 46%, the compliance associated to crystalline material only increased by 12%. The additional compartment was much more sensitive to water, since its compliance increased 4-fold between the dry and wet state. Most of the increase in compliance with moisture content (77%) was actually located in this additional compartment. This analysis enables the calculation of the specific MOE of the "ideal" compartment, given by the inverse of its compliance, i.e. 46.2 and 41.4 GPa for the dry and wet states respectively. A cell wall model similar to that developed by Alméras et al. [START_REF] Alméras | Modelling anisotropic maturation strains in wood in relation to fibre boundary conditions,microstructure and maturation kinetics[END_REF] was used to assess the effect of moisture on cell wall stiffness. This model is based on the assumption that cellulose microfibrils are perfectly parallel to each other, mostly crystalline and of infinite length. It does not take into account additional sources of deformations located within the wall or at higher levels of organisation, and is therefore suitable to model the "ideal" cell wall. Assuming that cellulose represents 50% of wood dry mass and accounts for the MFA of 12°, the modulus of elasticity of dry and wet cell walls can be modelled by fitting the variations of modulus of elasticity of the matrix material with moisture content. Using 17 GPa and 3 GPa for the MOE of the matrix, specific MOE of the cell wall of 46.4 and 41.5 GPa were obtained for dry and wet states respectively, which yields a decrease in MOE of 12% between dry and wet states. These values fit well with the data, and are realistic compared to the measured values for these parameters [22; 23], showing that the measured values of specific MOE and its decrease with moisture content found for the behaviour of the "ideal" cell wall compartment are consistent with their mechanical modelling.

Hypotheses about the source of additive strain in the linear domain

Several hypotheses can be formulated to explain the origin of this additive strain in wood media. Montero et al. [START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF] listed the different reasonable origins, involving the contribution of constituent physically associated in series, or the contribution of bending and shear strain at different lengthscales. The present study proves that this additive source of compliance is also strongly moisturedependent.

Results of the present study strongly support the hypothesis of an involvement of non-negligible shear strains. The shear strain would increase the macroscopic strain without increasing the cellulose strain, and is thus a possible candidate for the source of additive strain. These may be in-plane shear at the level of the cell wall (incomplete shear restraint between walls of adjacent cells) or localized shear effects due to the discontinuity of crystalline material at different scales (shear lag effect near the end of microfibrils within the wall, normal-longitudinal shear between cell wall layers, shear-lag effect near the end of fibres). Other hypotheses formulated by Montero et al. [START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF] involve bending effects at different scales (at the microfibril scale assuming that microfibrils are not completely straight at initial states and may straighten during cell wall extension, at the fibre scale due to the slight curvature of the cell wall in the longitudinal plane, or at the tissue scale due to fibre bending around rays).

Hypotheses involving global shear, localized shear or microfibril bending are all consistent with the increase of this additive strain with moisture content, since in all cases the strain of non-crystalline material (middle lamella or cell wall matrix) is involved in the proposed deformation mechanism. These components are made of pectins, lignins and hemicelluloses, which are all known to have moisture-dependant compliance. The change in stiffness of these constituents between the wet and dry states was reported to be 2 fold for lignin, and almost 100 fold for hemicellulose [22; 23]. The 4fold increase in compliance of the additive compartment between wet and dry state therefore seems compatible with these values. A hypothesis formulated by several previous authors is that this additive strain represents the contribution of amorphous domains of cellulose located in the microfibrils [START_REF] Nakai | The relationship between macroscopic strain and crystal lattice strain in wood under uniaxial stress in the fiber direction[END_REF][START_REF] Nakai | Mechanical behavior of the crystalline region of wood and the piezoelectric response of wood in tension tests[END_REF][START_REF] Nakai | Mechanical behavior of the crystal lattice of natural cellulose in wood under repeated uniaxial tension stress in the fiber direction[END_REF][START_REF] Peura | The effect of axial strain on crystalline cellulose in Norway spruce[END_REF][START_REF] Montero | Relationship between wood elastic strain under bending and cellulose crystal strain[END_REF] . The presence of such domains associated in series with crystalline cellulose is supported by several studies [2; 24; 25] , although a recent work [START_REF] Salmén | Wood morphology and properties from molecular perspectives[END_REF] showed that the "equal strain" model (parallel association between crystalline and amorphous cellulose), was more realistic than the "equal stress" model (series association). Contrary to crystalline cellulose, amorphous cellulose is hydrophilic and could then exhibit a moisture-dependent behaviour. This source of strain could also have a non-negligible contribution to additional strains.

Consequences for mechanical models of wood behaviour

Mechanical models usually consider only a simplified representation of wood structure. Regarding the behaviour in the grain direction, many of such models as based on the assumption that wood behaviour can be modelled at the cell and cell wall scales [START_REF] Cave | The anisotropic elasticity of the plant cell wall[END_REF][START_REF] Cave | Modelling moisture-related mechanical properties of wood Part I: Properties of the wood constituents[END_REF][START_REF] Harrington | Modelling the elastic properties of softwood-Part I: The cell-wall lamellae[END_REF][START_REF] Yamamoto | Origin of the biomechanical properties of wood related to the fine structure of the multi-layered cell wall[END_REF][START_REF] Xu | Models of microfibril elastic modulus parallel to the cell axis[END_REF][START_REF] Qing | Moisture-related mechanical properties of softwood: 3D micromechanical modeling[END_REF]. The main parameters of wood behaviour are then accounted for through the cell wall relative thickness and the orientation of microfibrils. These models are based on many implicit assumptions about wood structure, considering straight elements (microfibrils and/or wood fibres) of infinite length. More complex models are based on a multiscale representation ranging from the polymer scale to the macroscopic scale and account for finite length of crystalline microfibrils, but not for other factors possibly influencing the ratio of crystal strain to macroscopic strain [START_REF] De Borst | Structure-function relationships in hardwood-insight from micromechanical modelling[END_REF]. The present study shows that these assumptions may neglect important determinants of wood compliance related to the 'non-ideal' structure of wood, in particular when moisture-dependant behaviour is considered [28; 30; 33; 34]. These simplifications may also have important consequences for the modelling of other behaviours, and in particular visco-elastic behaviour [START_REF] Eitelberger | Multiscale prediction of viscoelastic properties of softwood under constant climatic conditions[END_REF], because its main determinants are non-crystalline domains, similar to those identified as a source of additive strain in the present study. We suggest that the strain ratio  could be used for the validation for mechanical models, by comparing the modelled ratio to its real values.

Conclusion

We measured strain in the cellulose crystal, compared it to the macroscopic strain through the strain ratio, and showed that crystal strains are lower than macroscopic strains. This difference could not be explained only by the difference between cell wall and cellulose orientations, but involves other sources of compliance associated in series with crystalline cellulose. This source of compliance amounts approximately to 9% of the wood total compliance for dry wood, and dramatically increases with moisture content, raising to a value of 31%. Our analysis shows that the compliance of the noncrystalline sources of strain increased 4-fold between air-dry and water-saturated conditions. Different possible localisations of this source of strain were proposed, and it is suggested that current models of wood elastic behaviour could use the strain ratio as a validation parameter.

Appendix: re-positioning of the scans between initial and deformed states

Between initial and final measurements, the zone of specimen impacted by X-rays can move in two directions: z in the height of the beam, due to deflection, and r in the perpendicular direction, due slight to out-of-plane movement of the specimen (see Fig. 2). The r movement affects the precision of lattice distance measurements, and the z movement is problematic for the calculation of cellulose crystal strain.

Correction of specimen movement in the Z direction

In our set-up, the deflection of the beam at the level of the X-ray scans cannot be precisely determined and monitored. Therefore, the scans made at initial and final states are not exactly impacting the same wood area. The position of the first scanned area relative to the specimen border differs by z between the initial and final states. Because of the natural variability of wood, the mean cellulose lattice distance at initial state is not uniform in the wood specimen. Therefore, to take into account this variability during the computation of strain between initial and loaded states, it is important to consider the change in impacted area. For this, an interpolation procedure was used, consisting in two steps: (1) determination of the position of a given scan in initial state relative to the position of scans made in final state; (2) determination of the lattice distance at this position in the final state by linear interpolation between lattice distances measured on neighbouring positions in the final state. For the first step, the profile of maximal intensity of the diffraction patterns is used. Indeed, because of the variability of wood material, the density of wood is not uniform in the wood specimen, and thus the signal intensity has a profile that depends on this non-uniformity, but not on the state of strain. The profiles of signal intensity in initial and final states are matched by fitting a linear transformation (translation + dilatation of the profile). The fitted parameters are used to determine the relative positions of initial and final scans.

Correction of specimen movement in the R direction

The accuracy of the (004) cellulose lattice measurement using X-ray diffraction strongly depends on the precision of the position of the specimen in the device, and, more precisely, the distance D between the centre of mass of the impacted area and the camera (see Fig. 2). This distance is used to determine accurately the  angle, from which the lattice distance d 004 is computed. Even a slight outof-plane movement (r) of the specimen has an important consequence on this estimation, especially when small crystal strains (lower than 0.1%) are to be detected. Increasing the distance D between the specimen and the detector is a first solution to minimize the relative effect of this out-of-plane movement. This distance D was set to the maximal value possible in our X-ray diffraction apparatus. To achieve higher accuracy, the calibration with gold powder was used. Gold powder does not strain during the bending of the specimen, so that the change in position of its peak on the diffraction pattern enables the computation of the out-of-plane displacement r, and use it for correcting raw data. To improve the stability of this correction, we assumed that the movement of each gold particle between initial and final state was a linear function of its position relative to the specimen border (i.e. the layer of gold displaces as a rigid body, being characterized by a translation and a rotation). This enables to calculate, at each scan position, the bias  (111)gold in the estimation of d (004)cellulose at final state.

Figure 1 .

 1 Figure 1. Design of the bending device and specimen geometry (dimensions in mm).

Figure 2 .

 2 Figure 2. Schematics of the X-ray beam path through the wood specimen to the detector. The loading mode (4point bending) is not represented on the figure.

Figure 3 .

 3 Figure 3. (a) typical raw curve of intensity versus lattice distance (dots), baseline (2 nd order polynomial fitted far from the peaks; red solid line) and boundaries used for baseline determination (vertical dotted line); (b) Typical corrected curve of intensity versus lattice distance (dots) after removing the baseline signal and 4 th order polynomial fit of gold and cellulose peaks (red solid lines) determining the lattice at maximal intensity (arrows) of gold and cellulose.

Figure 4 .

 4 Figure 4. Typical profile of crystal strain (specimen 1). Each dot is a measurement point located along the height of the specimen. Black line represents macroscopic strain, linearly interpolated between the upper and the lower sides of the specimen.

Figure 5 .

 5 Figure 5. Relationship between macroscopic strain and projected crystal strain for dry specimens. Black line: linear regression of the points. Only closed symbols are used for the regression (open symbols are ignored)

Figure 6 .

 6 Figure 6. Relationship between macroscopic strain and projected crystal strain for wet specimens. Black line: linear regression of the points. Only data points represented by closed symbols are used for the regression (open symbols are ignored).

Table 1 .

 1 Dry specimen characteristics and bending test results. MFA: microfibril angle (°), dB: basic density (kg/m 3 ), w: moisture content (%), E: elastic modulus (GPa), E/d specific modulus (GPa.m 3 /kg), Max. : maximal strain during the test (µstrain),  raw : raw strain ratio,  proj. : projected strain ratio, R²: coefficient of determination of the relationship between strains, SD standard deviation.

		MFA	dB	w	E	E/d	Max.   raw	 proj.	R²
	1	11.6	378	6.7%	14.5	38.4	0.22%	0.78	0.84	0.996
	2	11.4	378	5.2%	16.3	43.1	0.20%	0.93	1.00	0.997
	3	11.3	359	5.9%	13.1	36.5	0.26%	0.86	0.93	0.997
	4	11.2	370	6.3%	17	45.9	0.20%	0.90	0.96	0.981
	5	12.4	356	6.0%	15.7	44.1	0.22%	0.79	0.85	0.999
	6	12.6	342	5.8%	15.7	45.9	0.25%	0.92	1.00	0.997
	7	11	362	5.9%	15.3	42.3	0.28%	0.83	0.88	0.996
	8	12.7	355	6.2%	14.9	42.0	0.27%	0.80	0.87	0.997
	9	11.6	396	6.0%	16.1	40.7	0.26%	0.80	0.86	0.998
	Mean	11.8	366	6.0%	15.4	42.1	0.24%	0.85	0.91	0.995
	SD	0.6	16	0.4%	1.1	3.2	0.03%	0.06	0.06	0.005
	Sample	MFA	dB	w	E	E/d	Max.   raw	 proj.	R²

Table 2 .

 2 Wet specimen characteristics and bending test results. MFA: microfibril angle (°), dB: basic density (kg/m 3 ), w: moisture content is saturated (above fibre saturation point), E: elastic modulus (GPa), E/d specific modulus (GPa.m 3 /kg), Max. : maximal strain during the test (µstrain),  raw : raw strain ratio,  proj. : projected strain ratio, R²: coefficient of determination of the relationship between strains, SD standard deviation.

Table 3 .

 3 Strain ratio obtained in different literature sources. MFA: microfibril angle of the specimens. Moisture content of the specimens.  raw : raw strain ratio.  proj : projected strain ratio computed using MFA and  raw

	Author	Test	MFA	Moisture content	 raw	 proj
	Suzuki et al. (1968) [7]	Traction	13.5°10-13%	0.66	0.73
	Moriizumi et al. (1978) [13]	Traction	9°7%	0.93	0.97
				13%	0.92	0.96
				27%	0.90	0.94
	Nakai et al. (2005) [9]	Traction	9-21°12%	0.35-0.78 0.37-1.00
	Nakai et al. (2005) [8]	Traction	15-17°12%	0.25-1.00 0.28-1.17
		Compression	12-14°12%	0.45-0.90 0.49-1.00
	Nakai et al. (2006) [10]	Traction	9-21°~11% (20°C 60%RH)	0.54-0.85 0.56-1.09
	Peura et al. (2007) [11]	Bending	10°~10% (24°C, 40%RH)	0.10	0.11
	Montero et al. (2012) [12]	Bending	18°~10% (22°C, 50%RH)	0.74	0.88
	Present study	Bending	12°6%	0.85	0.91
				Saturated	0.64	0.69

Table 4 .

 4 Sources of compliance in wet and dry state. C tot : total compliance [GPa-1 ]. C ideal : compliance of the compartment associated in parallel with crystalline cellulose [GPa-1 ]. C add : compliance of the additional compartment [GPa-1 ].


Géraud Le Falher

Nicolò Cesa-Bianchi

Claudio Gentile

Fabio Vitale

On the Troll-Trust Model for Edge Sign Prediction in Social Networks

In the problem of edge sign prediction, we are given a directed graph (representing a social network), and our task is to predict the binary labels of the edges (i.e., the positive or negative nature of the social relationships). Many successful heuristics for this problem are based on the troll-trust features, estimating at each node the fraction of outgoing and incoming positive/negative edges. We show that these heuristics can be understood, and rigorously analyzed, as approximators to the Bayes optimal classifier for a simple probabilistic model of the edge labels. We then show that the maximum likelihood estimator for this model approximately corresponds to the predictions of a Label Propagation algorithm run on a transformed version of the original social graph. Extensive experiments on a number of real-world datasets show that this algorithm is competitive against state-ofthe-art classifiers in terms of both accuracy and scalability. Finally, we show that trolltrust features can also be used to derive online learning algorithms which have theoretical guarantees even when edges are adversarially labeled.

Introduction

Connections in social networks are mostly driven by the homophily assumption: linked individuals tend to be similar, sharing personality traits, attitudes, or interests. However, homophily alone is clearly not sufficient to explain the variety of social links. In fact, sociologists have long studied networks, hereafter called signed social networks, where also negative relationships -like dissimilarity, disapproval or distrust-are explicitly displayed. The presence of negative relationships is also a feature of many technology-mediated social networks. Known examples are Ebay, where users trust Preliminary work under review: do not distribute.

or distrust agents in the network based on their personal interactions, Slashdot, where each user can tag another user as friend or foe, and Epinion, where users can rate positively or negatively not only products, but also other users. Even in social networks where connections solely represent friendships, negative links can still emerge from the analysis of online debates among users.

When the social network is signed, specific challenges arise in both network analysis and learning. On the one hand, novel methods are required to tackle standard tasks (e.g., user clustering, link prediction, targeted advertising/recommendation, analysis of the spreading of diseases in epidemiological models). On the other hand, new problems such as edge sign prediction, which we consider here, naturally emerge. Edge sign prediction is the problem of classifying the positive or negative nature of the links based on the network topology. Prior knowledge of the network topology is often a realistic assumption, for in several situations the discovery of the link sign can be more costly than acquiring the topological information of the network. For instance, when two users of an online social network communicate on a public web page, we immediately detect a link. Yet, the classification of the link sign as positive or negative may require complex techniques.

From the modeling and algorithmic viewpoints, because of the huge amount of available networked data, a major concern in developing learning methods for edge sign prediction is algorithmic scalability. Many successful, yet simple heuristics for edge sign prediction are based on the troll-trust features, i.e., on the fraction of outgoing negative links (trollness) and incoming positive links (trustworthiness) at each node. We study such heuristics by defining a probabilistic generative model for the signs on the directed links of a given network, and show that these heuristics can be understood and analyzed as approximators to the Bayes optimal classifier for our generative model. We also gather empirical evidence supporting our probabilistic model by observing that a logistic model trained on trollness and trustworthiness features alone is able to learn weights that, on all datasets considered in our experiments, consistently satisfy the properties predicted by our model.

We then introduce suitable graph transformations defining reductions from edge sign prediction to node sign prediction problems. This opens up the possibility of using the arsenal of known algorithmic techniques developed for node classification. In particular, we show that a Label Propagation algorithm, combined with our reduction, approximates the maximum likelihood estimator of our probabilistic generative model. Experiments on real-world data show the competitiveness of our approach in terms of both prediction performance (especially in the regime when training data are scarce) and scalability.

Finally, we point out that the notions of trollness and trustworthiness naturally define a measure of complexity, or learning bias, for the signed network that can also be used to design online (i.e., sequential) learning algorithms for the edge sign prediction problem. The learning bias encourages settings where the nodes in the network have polarized features (e.g., trollness/trustworthiness are either very high or very low). Our online analysis holds under adversarial conditions, namely, without any stochastic assumption on the assignment of signs to the network links.

Related work

Interest in signed networks can be traced back to the psychological theory of structural balance [4,[START_REF] Heider | The psychology of interpersonal relations[END_REF] with its weak version [START_REF] Davis | Clustering and structural balance in graphs[END_REF]. The advent of online signed social networks has enabled a more thorough and quantitative understanding of that phenomenon. Among the several approaches related to our work, some extend the spectral properties of a graph to the signed case in order to find good embeddings for classification [START_REF] Kunegis | The Slashdot Zoo: Mining a Social Network with Negative Edges[END_REF][START_REF] Zheng | Spectral Embedding of Signed Networks[END_REF]. However, the use of the adjacency matrix usually requires a quadratic running time in the number of nodes, which makes those methods hardly scalable to large graphs. Another approach is based on mining ego networks with SVM. Although this method seems to deliver good results [START_REF] Papaoikonomou | Predicting Edge Signs in Social Networks Using Frequent Subgraph Discovery[END_REF], the running time makes it often impractical for large real-world datasets. An alternative approach, based on local features only and proposed in [START_REF] Leskovec | Predicting positive and negative links in online social networks[END_REF], relies on the so-called status theory for directed graphs [START_REF] Guha | Propagation of trust and distrust[END_REF]. Some works in active learning, using a more sophisticated bias based on the correlation clustering (CC) index [START_REF] Cesa-Bianchi | A linear time active learning algorithm for link classification[END_REF][START_REF] Cesa-Bianchi | A correlation clustering approach to link classification in signed networks[END_REF], provide strong theoretical guarantees. However, the bias used there is rather strong, since it assumes the existence of a 2-clustering of the nodes with a small CC index.

Whereas our focus will be on binary prediction, re-searchers have also considered a weighted version of the problem, where edges measure the amount of trust or distrust between two users (e.g., [START_REF] Guha | Propagation of trust and distrust[END_REF][START_REF] Tang | Exploiting homophily effect for trust prediction[END_REF][START_REF] Qian | Foundations of Trust and Distrust in Networks: Extended Structural Balance Theory[END_REF]). Other works have also considered versions of the problem where side information related to the network is available to the learning system. For instance, [START_REF] Papaoikonomou | Trust Inference in Online Social Networks[END_REF] uses the product purchased on Epinion in conjunction with a neural network, [START_REF] Cheng | Antisocial behavior in online discussion communities[END_REF] identifies trolls by analysing the textual content of their post, and [START_REF] Ye | Predicting Positive and Negative Links in Signed Social Networks by Transfer Learning[END_REF] uses SVM to perform transfer learning from one network to another. While many of these approaches have interesting performances, they often require extra information which is not always available (or reliable) and, in addition, may face severe scaling issues. The recent survey [START_REF] Tang | A Survey of Signed Network Mining in Social Media[END_REF] contains pointers to many papers on edge sign prediction for signed networks, especially in the Data Mining area. Additional references, more closely related to our work, will be mentioned at the end of Section 4.1.

Notation and Preliminaries

In what follows, we let G = (V, E) be a directed graph, whose edges (i, j) ∈ E carry a binary label y i,j ∈ {-1, +1}. The edge labeling will sometimes be collectively denoted by the

|V | × |V | matrix Y = [Y i,j ],
where Y i,j = y i,j if (i, j) ∈ E, and Y i,j = 0, otherwise. The corresponding edge-labeled graph will be denoted by G(Y ) = (V, E(Y )). We use E in (i) and E out (i) to denote, respectively, the set of edges incoming to and outgoing from node i ∈ V , with d in (i) = E in (i) and d out (i) = E out (i) being the in-degree and the out-degree of i. Moreover, d + in (i) is the number of edges (k, i) ∈ E in (i) such that y k,i = +1. We define d - in (i), d + out (i), and d - out (i) similarly, so that, for instance, d - out (i)/d out (i) is the fraction of outgoing edges from node i whose label in G(Y ) is -1. We call tr(i) = d - out (i)/d out (i) the trollness of node i, and un(i) = d - in (i)/d in (i) the untrustworthiness of node i. Finally, we also use the notation N in (i) and N out (i) to represent, respectively, the in-neighborhood and the out-neighborhood of node i ∈ V .

Given the directed graph G = (V, E), we define two edge-to-node reductions transforming the original graph G into other graphs. As we see later, these reductions are useful in turning the edge sign prediction problem into a node sign prediction problem (often called node classification problem), for which many algorithms are indeed available -see, e.g., [3,[START_REF] Zhu | Semisupervised learning using Gaussian fields and harmonic functions[END_REF][START_REF] Herbster | Prediction on a graph with the Perceptron[END_REF][START_REF] Herbster | Online prediction on large diameter graphs[END_REF][START_REF] Cesa-Bianchi | Random spanning trees and the prediction of weighted graphs[END_REF]. Although any node classification method could in principle be used, the reductions we describe next are essentially aimed at preparing the ground for quadratic energyminimization approaches computed through a Label Propagation algorithm (e.g., [START_REF] Zhu | Semisupervised learning using Gaussian fields and harmonic functions[END_REF]2]).

The first reduction, called G → G , builds an undirected graph G = (V , E ) as follows. Each node i ∈ V has two copies in V , call them i in and i out . Each directed edge (i, j) in E is associated with one node, call it e i,j , in V , along with the two undirected edges (i out , e i,j ) and (e i,j , j in ). Hence

|V | = 2|V | + |E| and |E | = 2|E|. Moreover, if G = G(Y )
is edge labeled, then this labeling transfers to the subset of nodes e i,j ∈ V , so that G is a graph G (Y ) = (V (Y ), E ) with partiallylabeled nodes. The second reduction, called G → G , builds an undirected and weighted graph G = (V , E ). Specifically, we have V ≡ V and E ⊃ E , where the set E also includes edges (i out , j in ) for all i and j such that (i, j) ∈ E. The edges in E have weight 2, whereas the edges in E \ E have weight -1. Finally, as in the G → G reduction, if G = G(Y ) is edge labeled, then this labeling transfers to the subset of nodes e i,j ∈ V . Graph G , which will not be used in this paper, is an intermediate structure between G and G and provides a conceptual link to the standard cutsize measure in node sign classification. Figure 1 illustrates the two reductions.

These reductions are meaningful only if they are able to approximately preserve label regularity when moving from edges to nodes. That is, if the edge sign prediction problem is easy for a given G(Y ) = (V, E(Y )), then the corresponding node sign prediction problems on G (Y ) = (V (Y ), E ) and G (Y ) = (V (Y ), E) are also easy, and vice versa. While we could make this argument more quantitative, here we simply observe that if each node in G tends to be either troll or trustworthy, then few labels from the incoming and outgoing edges of each such node are sufficient to predict the labels on the remaining edges in G, and this translates to a small cutsize1 of G (Y ) over the nodes corresponding to the edges in G (the colored squares in Figure 1 (b)). Again, we would like to point out that these reductions serve two purposes: i. They allow us to use the many algorithms designed for the better studied problem of node sign prediction, and ii. the reduction G → G specifically makes the Label Propagation solution approximate the maximum likelihood estimator associated with our generative model (see Section 4.1). Besides, efficient Label Propagation implementations exist that can leverage the sparsity of G .

We consider two learning settings associated with the problem of edge sign prediction: a batch setting and an online setting. In the batch setting, we assume that a training set of edges E 0 has been drawn uniformly at random without replacement from E, we observe the labels in E 0 , and we are interested in predicting the sign of the remaining edges E \ E 0 by making as few prediction mistakes as possible. The specific batch setting we study here assumes that labels are produced by a generative model which we describe in the next section, and our label regularity measure is a quadratic function (denoted by Ψ2 G (Y ) -see Section 6 for a definition), related to this model. Ψ 2 G (Y ) is small just when all nodes in G tend to be either troll or trustworthy.

On the other hand, the online setting we consider is the standard mistake bound model of online learning [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF] where all edge labels are assumed to be generated by an adversary and sequentially presented to the learner according to an arbitrary permutation. For an online learning algorithm A, we are interested in measuring the total number of mistakes M A (Y ) the algorithm makes over G(Y ) when the worst possible presentation order of the edge labels in Y is selected by the adversary. Also in the online setting our label regularity measure, denoted here by Ψ G (Y ), is small when nodes in G tend to be either troll or trustworthy. Formally, for fixed G and Y , let

Ψ in (j, Y ) = min d - in (j), d + in (j) and Ψ out (i, Y ) = min d - out (i), d + out (i) . Let also Ψ in (Y ) = j∈V Ψ in (j, Y ) and Ψ out (Y ) = i∈V Ψ out (i, Y ). Then we define Ψ G (Y ) = min Ψ in (Y ), Ψ out (Y ) .
The two measures Ψ 2 G (Y ) and Ψ G (Y ) are conceptually related, as also empirically confirmed by our experiments (see Table 2 in Section 6).

Generative Model for Edge Labels

We now define the stochastic generative model for edge labels we use in the batch learning setting. Given the graph G = (V, E), let the label y i,j ∈ {-1, +1} of directed edge (i, j) ∈ E be generated as follows. Each node i ∈ V is endowed with two latent parameters p i , q i ∈ [0, 1], which we assume to be generated, for each node i, by an independent draw from a fixed but unknown joint prior distribution µ(p, q) over [0, 1] 2 . Each label y i,j ∈ {-1, +1} is then generated by an independent draw from the mixture of p i and q j ,

P y i,j = 1 = pi+qj 2
. The basic intuition is that the nature y i,j of a relationship i → j is stochastically determined by a mixture between how much node i tends to like other people (p i ) and how much node j tends to be liked by other people (q j ). In a certain sense, 1-tr(i) is the empirical counterpart to p i , and 1 -un(j) is the empirical counterpart to q j . 2 Notice that the Bayes optimal prediction for y i,j is y * (i, j) = sgn η(i, j) -1 2 , where η(i, j) = P y i,j = 1 . Moreover, the probability of drawing at random a +1-labeled edge from E out (i) and the probability of drawing at random a +1-labeled edge from E in (j) are respectively equal to

1 2 3 4 + + - - + - (a) 1 out 2 out 3 out 4 out 1 in 2 in 3 in 4 in 1 -1 -1 1 -1 1 (b) 1 out 2 out 3 out 4 out 1 in 2 in 3 in 4 in 1 -1 -1 1 -1 1 2 2 2 2 2 2 2 2 2 2 2 2 -1 -1 -1 -1 -1 -1 (c)
1 2 pi + 1 dout(i) j∈N out (i) qj and 1 2 qj + 1 din(j) i∈N in (j)
pi .

(1)

Algorithms in the Batch Setting

Given G(Y ) = (V, E(Y )), we have at our disposal a training set E 0 of labeled edges from E(Y ), our goal being that of building a predictive model for the labels of the remaining edges.

Our first algorithm is an approximation to the Bayes optimal predictor y * (i, j). Let us denote by tr(i) and un(i) the trollness and the untrustworthiness of node i when both are computed on the subgraph induced by the training edges. We now design and analyze an edge classifier of the form

sgn 1 -tr(i) + 1 -un(j) -1 2 -τ , (2)
where τ ≥ 0 is the only parameter to be trained. Despite its simplicity, this classifier works reasonably well in practice, as demonstrated by our experiments (see Section 6). Moreover, unlike previous edge sign prediction methods for directed graphs, our classifier comes with a rigorous theoretical motivation, since it approximates the Bayes optimal classifier y * (i, j) with respect to the generative model defined in Section 3. It is important to point out that when we use 1 -tr(i) and 1 -un(j) to estimate p i and q j , an additive bias shows up due to (1). This motivates the need of a threshold parameter τ to cancel this bias. Yet, the presence of a prior distribution µ(p, q) ensures that this bias is the same for all edges (i, j) ∈ E.

Our algorithm works under the assumption that for given parameters Q (a positive integer) and α ∈ (0, 1) there exists a set 3 E L ⊆ E of size 2Q α where each vertex 3 This set is needed to find an estimate τ of τ in (2), i ∈ V appearing as an endpoint of some edge in E L occurs at most once as origin -i.e., (i, j)-and at most once as destination -i.e., (j, i). Moreover, we assume E 0 has been drawn from E at random without replacement, with m = |E 0 | = α |E|. The algorithm performs the following steps:

1. For each j ∈ V , let un(j) = d - in (j)/ d in (j), i.e., the fraction of negative edges found in E in (j) ∩ E 0 . 2. For each i ∈ V , let tr(i) = d - out (i)/ d out (i), i.e.
, the fraction of negative edges found in E out (i) ∩ E 0 .

Let τ be the fraction of positive edges in E

L ∩ E 0 .
4. Any remaining edge (i, j) ∈ E \ E 0 is predicted as

y(i, j) = sgn 1 -tr(i) + 1 -un(j) -1 2 -τ .
The next result 4 shows that if the graph is not too sparse, then the above algorithm can approximate the Bayes optimal predictor on nodes whose in-degree and out-degree is not too small.

Theorem 1. Let G(Y ) = (V, E(Y )
) be a directed graph with labels on the edges generated according to the model in Section 3. If the algorithm is run with parameter Q = Ω(ln |V |), and α ∈ (0, 1) such that the above assumptions are satisfied, then y(i, j) = y * (i, j) holds with high probability simultaneously for all test edges

(i, j) ∈ E such that d out (i), d in (j) = Ω(ln |V |), and
η(i, j) = P(y i,j = 1) is bounded away from 1 2 .
From this algorithm we derive the blc algorithm we use in our experiments of Section 6.

Approximation to Maximum Likelihood via Label Propagation

For simplicity, assume the joint prior distribution µ(p, q) is uniform over [0, 1] 2 with independent see Step 3 of the algorithm. It can be any set of directed paths/cycles in G that are pairwise vertex-disjoint. 4 Due to space limitations, all proofs are in the supplementary material. marginals, and suppose that we draw at random without replacement the training set E 0 = (i 1 , j 1 ), y i1,j1 ), ((i 2 , j 2 ), y i2,j2 ), . . . , ((i m , j m ), y im,jm , with m = |E 0 |. Then a reasonable approach to approximate y * (i, j) would be to resort to a maximum likelihood estimator of the parameters

{p i , q i } |V | i=1
based on E 0 . Working out the math (details in the supplementary material), one can easily see that the gradient of the log-likelihood function w.r.t.

{p i , q i } |V | i=1 satisfies ∂ log P E0 {pi, qi} |V | i=1 ∂p (3) = m k=1 I {i k = , y ,j k = +1} p + qj k - m k=1 I {i k = , y ,j k = -1} 2 -p -qj k , ∂ log P E0 {pi, qi} |V | i=1 ∂q (4) = m k=1 I {j k = , y i k , = +1} pi k + q - m k=1 I {j k = , y i k , = -1} 2 -pi k -q ,
where I {•} is the indicator function of the event at argument. Unfortunately, equating ( 3) and ( 4) to zero, and solving for parameters

{p i , q i } |V |
i=1 gives rise to a hard set of nonlinear equations. Moreover, it may well be the case that some such parameters never occur in these equations. This will happen precisely whenever E out (i) or E in (j) are not represented in E 0 for some i, j ∈ V . A more viable and computation-friendly alternative is to approximate the nonlinear equations resulting from (3) and (4) by the following set of linear equations, one for each ∈ V :

m k=1 I {i k = , y ,j k = +1} (2 -p -q j k ) = m k=1 I {i k = , y ,j k = -1} (p + q j k ) m k=1 I {j k = , y i k , = +1} (2 -p i k -q ) = m k=1 I {j k = , y i k , = -1} (p i k + q ) .
The solution to these equations are precisely the points where the gradient w.r.

t. (p, q) = {p i , q i } |V | i=1 of the quadratic function f E0 (p, q) = (i,j)∈E0 1 + y i,j 2 - p i + q j 2 2
vanishes. We follow a label propagation approach by adding to f E0 the corresponding test set function f E\E0 , and treat the sum of the two as the function to be minimized during training w.r.t. both (p, q) and all y i,j ∈ [-1, +1] for (i, j) ∈ E \ E 0 , i.e., min

(p,q),yi,j ∈[-1,+1], (i,j)∈E\E0 f E0 (p, q) + f E\E0 (p, q) .
(5) Binary ±1 predictions on the test set E \ E 0 are then obtained by thresholding the obtained values y i,j at 0.

The above problem can be approximately solved by standard label propagation [START_REF] Zhu | Semisupervised learning using Gaussian fields and harmonic functions[END_REF] on graph G obtained through the G → G reduction of Section 2. However, because of the presence of negative edge weights in G , we first have to symmetrize variables p i , q i , y i,j so as they all lie in the interval [-1, +1]. After this step, one can see that, once we get back to the original variables, label propagation computes the harmonic solution minimizing the function

f p, q, yi,j (i,j)∈E\E 0 = fE 0 (p, q) + f E\E 0 (p, q) + 1 2 i∈V dout(i) pi - 1 2 2 +din(i) qi - 1 2 2 .
The function f is thus a regularized version of the target function f E0 + f E\E0 in [START_REF] Cesa-Bianchi | A correlation clustering approach to link classification in signed networks[END_REF], where the regularization term tries to enforce the extra constraint that whenever a node i has a high out-degree then the corresponding p i should be close to 1/2. Thus, on any edge (i, j) departing from i, the Bayes optimal predictor y * (i, j) = sgn(p i + q j -1) will mainly depend on q j being larger or smaller than 1 2 (assuming j has small in-degree). Similarly, if i has a high in-degree, then the corresponding q i should be close to 1/2 implying that on any edge (j, i) arriving at i the Bayes optimal predictor y * (j, i) will mainly depend on p j (assuming j has small out-degree). Put differently, a node having a huge out-neighborhood makes each outgoing edge "count less" than a node having only a small number of outgoing edges, and similarly for in-neighborhoods. The label propagation algorithm operating on G does so (see again Figure 1 (c)) by iteratively updating as follows:

p i ← -j∈Nout(i) q j + j∈Nout(i) (1 + y i,j ) 3 d out (i) ∀i ∈ V q j ← -i∈Nin(j) p i + i∈Nin(j) (1 + y i,j ) 3 d in (j) ∀j ∈ V y i,j ← p i + q j 2 ∀(i, j) ∈ E \ E 0 .
The algorithm is guaranteed to converge [START_REF] Zhu | Semisupervised learning using Gaussian fields and harmonic functions[END_REF] to the minimizer of f . Notice that the presence of negative weights on the edges of G does not prevent label propagation from converging. This is the algorithm we will be championing in our experiments of Section 6.

Further related work. The vast majority of existing edge sign prediction algorithms for directed graphs are based on the computation of local features of the graph. These features are evaluated on the subgraph induced by the training edges, and the resulting values are used to train a supervised classification algorithm (e.g., logistic regression). The most basic set of local features used to classify a given edge (i, j) are defined by d + in (j), d - in (j), d + out (i), d - out (i) computed over the training set E 0 , and by the embeddedness coefficient E out (i) ∩ E in (j) . In turn, these can be used to define more complicated features, such as

d + in (j)+|E + |Uin(j) din(j)+Uin(j)
and

d + out (i)+p + Uout(i)
dout(i)+Uout(i) introduced in [START_REF] Song | Link sign prediction and ranking in signed directed social networks[END_REF], together with their negative counterparts, where |E + | is the overall fraction of positive edges, and U in (j), U out (i) are, respectively, the number of test edges outgoing from i and the number of test edges incoming to j. Other types of features are derived from social status theory (e.g., [START_REF] Leskovec | Predicting positive and negative links in online social networks[END_REF]), and involve the so-called triads; namely, the triangles formed by (i, j) together with (i, w) and (w, j) for any w ∈ N out (i) ∩ N in (j). A third group of features is based on node ranking scores. These scores are computed using a variery of methods, including Prestige [START_REF] Zolfaghar | Mining trust and distrust relationships in social web applications[END_REF], exponential ranking [START_REF] Traag | Exponential Ranking: taking into account negative links[END_REF], PageTrust [START_REF] De Kerchove | The pagetrust algorithm: How to rank web pages when negative links are allowed?[END_REF], Bias and Deserve [START_REF] Mishra | Finding the bias and prestige of nodes in networks based on trust scores[END_REF], TrollTrust [START_REF] Wu | The troll-trust model for ranking in signed networks[END_REF], and generalizations of PageRank and HITS to signed networks [START_REF] Shahriari | Ranking nodes in signed social networks[END_REF]. Examples of features using such scores are reputation and optimism [START_REF] Shahriari | Ranking nodes in signed social networks[END_REF], defined for a node i by j∈N in (i) yj,iσ(j) j∈N in (i) σ(j) and j∈N out (i) Yi,j σ(j) j∈N out (i) σ(j) , where σ(j) is the ranking score assigned to node j. Some of these algorithms will be used as representative competitors in our experimental study of Section 6.

Algorithms in the Online Setting

For the online scenario, we have the following result.

Theorem 2. There exists a randomized online prediction algorithm A whose expected number of mistakes satisfies

EM A (Y ) = Ψ G (Y ) + O |V |Ψ G (Y ) + |V | on any edge-labeled graph G(Y ) = (V, E(Y )).
The algorithm used in Theorem 2 is a combination of randomized Weighted Majority instances. Details are reported in the supplementary material. We complement the above result by providing a mistake lower bound. Like Theorem 2, the following result holds for all graphs, and for all label irregularity levels Ψ G (Y ).

Experimental Analysis

In this section, we evaluate our edge sign classification methods on representative real-world datasets of varying density and label regularity, showing that our methods compete well against existing approaches in terms of both predictive and computational performance. We are especially interested in small training set regimes, and have restricted our comparison to the batch learning scenario since all competing methods we are aware of have been developed in that setting only.

Datasets. We considered five real-world classification datasets. The first three are directed signed social networks widely used as benchmarks for this task (e.g., [START_REF] Leskovec | Predicting positive and negative links in online social networks[END_REF][START_REF] Shahriari | Ranking nodes in signed social networks[END_REF][START_REF] Wu | The troll-trust model for ranking in signed networks[END_REF]): In Wikipedia, there is an edge from user i to user j if j applies for an admin position and i votes for or against that promotion. In Slashdot, a news sharing and commenting website, member i can tag other members j as friends or foes. Finally, in Epinion, an online shopping website, user j reviews products and, based on these reviews, another user i can display whether he considers j to be reliable or not. In addition to these three datasets, we considered two other signed social networks where the signs are inferred automatically. In Wik. Edits [START_REF] Maniu | Casting a Web of Trust over Wikipedia: An Interactionbased Approach[END_REF], an edge from Wikipedia user i to user j indicates whether they edited the same article in a constructive manner or not. 5 Finally, in the Citations [START_REF] Kumar | Structure and Dynamics of Signed Citation Networks[END_REF] network, an author i cites another author j by either endorsing or criticizing j's work. The edge sign is derived by classifying the citation sentiment with a simple, yet powerful, keyword-based technique using a list of positive and negative words. See [START_REF] Kumar | Structure and Dynamics of Signed Citation Networks[END_REF] for more details. 6Table 1 summarizes statistics for these datasets. We note that most edge labels are positive. Hence, test set accuracy is not an appropriate measure of prediction performance. We instead evaluated our performance using the so-called Matthews Correlation Coefficient (MCC) (e.g., [1]), defined as

MCC = tp × tn -f p × f n (tp + f p)(tp + f n)(tn + f p)(tn + f n) .
MCC combines all the four quantities found in a binary confusion matrix (true positive, true negative, f alse positive and f alse negative) into a single metric which ranges from -1 (when all predictions are incorrect) to +1 (when all predictions are correct).

Although the semantics of the edge signs is not the same across these networks, we can see from where

Ψ 2 G (Y ) = min (p,q)
f E0 (p, q) + f E\E0 (p, q) , f E0 and f E\E0 being the quadratic criterions of Section 4.1, viewed as functions of both (p, q), and y i,j , and Ψ G (Y ) is the label regularity measure adopted in the online setting, as defined in Section 2. It is reasonable to expect that higher label irregularity corresponds to lower prediction performance. This trend is in fact confirmed by our experimental findings: whereas Epinion tends to be easy, Citations tends to be hard, and this holds for all algorithms we tested, even if they do not explicitly comply with our inductive bias principles. Moreover, Ψ 2 G (Y )/|E| tends to be proportional to Ψ G (Y )/|E| across datasets, hence confirming the anticipated connection between the two regularity measures.

Algorithms and parameter tuning. We compared the following algorithms: 1. The label propagation algorithm of Section 4.1 (referred to as L. Prop.). The actual binarizing threshold was set by cross-validation on the training set. 2. The algorithm analyzed at the beginning of Section 4, which we call blc(tr, un) (Bayes Learning Classifier based on trollness and untrustworthiness). After computing tr(i) and un(i) on training set E 0 for all i ∈ V (or setting those values to 1 2 in case there is no outgoing or incoming edges for some node), we use Eq. ( 2) and estimate τ on E 0 . 3. A logistic regression model where each edge (i, j) is associated with the features [1 -tr(i), 1 -un(j)] computed again on E 0 (we call this method LogReg). Best binary thresholding is again computed on E 0 . Experimenting with this logistic model serves to support the claim we made in the introduction that our generative model in Section 3 is a good fit for the data. 4. The solution obtained by directly solving the unregularized problem (5) through a fast constrained minimization algorithm (referred to as Unreg.). Again, the actual binarizing threshold was set by cross-validation on the training set. We have also tried to minimize (5) by removing the [-1, +1] constraints, but got similar MCC results as the ones we report for Unreg.

5.

The matrix completion method from [START_REF] Chiang | Prediction and Clustering in Signed Networks: A Local to Global Perspective[END_REF] based on LowRank matrix factorization. Since the authors showed their method to be robust to the choice of the rank parameter k, we picked k = 7 in our experiments. 6. A logistic regression model built on 16 Triads features derived from status theory [START_REF] Leskovec | Predicting positive and negative links in online social networks[END_REF]. 7. The PageRank-inspired algorithm from [START_REF] Wu | The troll-trust model for ranking in signed networks[END_REF], where a recursive notion of trollness is computed by solving a suitable set of nonlinear equations through an iterative method, and then used to assign ranking scores to nodes, from which (un)trustworthiness features are finally extracted for each edge. We call this method RankNodes. As for hyperparameter tuning (β and λ 1 in [START_REF] Wu | The troll-trust model for ranking in signed networks[END_REF]), we closely followed the authors' suggestion of doing cross validation. 8. The last competitor is the logistic regression model whose features have been build according to [START_REF] Song | Link sign prediction and ranking in signed directed social networks[END_REF]. We call this method Bayesian.

The above methods can be roughly divided into local and global methods. A local method hinges on building local predictive features, based on neighborhoods: blc(tr, un), LogReg, 16 Triads, and Bayesian essentially fall into this category. The remaining methods are global in that their features are designed to depend on global properties of the graph topology.

Results. Our main results are summarized in Table 2, where we report MCC test set performance after training on sets of varying size (from 3% to 25%). Results have been averaged over 12 repetitions. Because scalability is a major concern when training on sizeable datasets, we also give an idea of relative training times (in milliseconds) by reporting the time it took to train a single run of each algorithm on a training set of size 8 15% of |E|, and then predict on the test set. Though our experiments are not conclusive, some trends can be readily spotted: 1. Global methods tend to outperform local methods in terms of prediction performance, but are also significantly (or even much) slower (running times can differ by as much as three orders of magnitude). This is not 8 Comparison of training time performances is fair since all algorithms have been carefully implemented using the same stack of Python libraries, and run on the same machine (16 Xeon cores and 192Gb Ram). surprising, and is in line with previous experimental findings (e.g., [START_REF] Shahriari | Ranking nodes in signed social networks[END_REF][START_REF] Wu | The troll-trust model for ranking in signed networks[END_REF]). Bayesian looks like an exception to this rule, but its running time is indeed in the same ballpark as global methods.

2. L. Prop. always ranks first or at least second in this comparison when MCC is considered. On top of it, L. Prop. is fastest among the global methods (one or even two orders of magnitude faster), thereby showing the benefit of our approach to edge sign prediction.

3. The regularized solution computed by L. Prop. is always better than the unregularized one computed by Unreg. in terms of both MCC and running time.

4.

As claimed in the introduction, our Bayes approximator blc(tr, un) closely mirrors in performance the more involved LogReg model. In fact, supporting our generative model of Section 3, the logistic regression weights for features 1 -tr(i) and 1 -un(j) are almost equal (see Table 2 in the supplementary material), thereby suggesting that predictor (2), derived from the theoretical results at the beginning of Section 4, is also the best logistic model based on trollness and untrustworthiness.

Conclusions and Ongoing Research

We have studied the edge sign prediction problem in directed graphs in both batch and online learning settings. In both cases, the underlying modeling assump-tion hinges on the trollness and (un)trustworthiness predictive features. We have introduced a simple generative model for the edge labels that serves both as a theoretical justification for many successful heuristic methods to edge sign prediction and as a way to craft this problem as a node sign prediction problem to be efficiently tackled by standard Label Propagation algorithms. We then observed that the notion of trollness and trustworthiness naturally lend themselves to define a notion of edge sign regularity that can also be analyzed in an (adversarial) online setting. In this setting, we have provided upper and (almost matching) lower bounds on the expected number of prediction mistakes.

We then complemented the above with experiments on five real-world datasets in the small training set regime. Two interesting conclusions from our experiments are: i. Our generative model is robust, for it produces Bayes optimal predictors which tend to be empirically best also within the larger set of models that includes all logistic regressors based on trollness and trustworthiness alone; ii. our methods are in practice either strictly better than their competitors in terms of prediction quality or, when they are not, they are faster.

We are currently engaged in gathering more experimental evidence, as well as in extending our approach so as to incorporate further predictive features (e.g., side information, when available).

A Proofs from Section 4

The following ancillary results will be useful.

Lemma 1 (Hoeffding's inequality for sampling without replacement). Let X = {x 1 , . . . , x N } be a finite subset of [0, 1] and let

µ = 1 N N i=1 x i .
If X 1 , . . . , X n is a random sample drawn at random from X without replacement, then, for every ε > 0,

P 1 n n t=1 X t -µ ≥ ε ≤ 2e -2nε 2 .
Lemma 2. Let N 1 , . . . , N n be subsets of a finite set E. Let E 0 ⊆ E be sampled uniformly at random without replacement from E, with |E 0 | = m. Then, for δ ∈ (0, 1), Q > 0, and θ ≥ 2 × max Q, 4 ln n δ , we have

P ∃i : |N i | ≥ θ, |N i ∩ E 0 | < Q ≤ δ provided |E| ≥ m ≥ 2|E| θ × max Q, 4 ln n δ .
Proof of Lemma 2. Set for brevity

p i = |N i |/|E|.
Then, due to the sampling without replacement, each random variable |N i ∩ E 0 | is the sum of m dependent Bernoulli random variables X i,1 , . . . , X i,m such that P(X i,t = 1) = p i , for t = 1, . . . , m. Let i be such that

|N i | ≥ θ. Then the condition m ≥ 2|E|Q θ implies Q ≤ mθ 2|E| ≤ m p i 2 = E |N i ∩ E 0 | 2 .
Since the variables X i,j are negatively associated, we may apply a (multiplicative) Chernoff bound [3, Section 3.1]. This gives

P |N i ∩ E 0 | < Q ≤ e -m p i 8 ≤ e -m θ 8|E| so that P ∃i : |N i | ≥ θ, |N i ∩ E 0 | < Q ≤ n e -m θ
8|E| , which is in turn upper bounded by δ whenever m ≥ 8|E| θ ln n δ .

Let now

E θ = {(i, j) ∈ E : d in (j) ≥ θ, d out (i) ≥ θ} \ E 0
, where E 0 ⊆ E is the set of edges sampled by the learning algorithm of Section 4.1. Then Theorem 1 in the main paper is an immediate consequence of the following lemma. Lemma 3. Let G(Y ) = (V, E(Y )) be a directed graph with labels on the edges generated according to the model in Section 3. For all 0 < α, δ < 1 and 0 < ε < 1 16 , if the learning algorithm of Section 4.1 is run with parameters

Q = 1 2ε 2 ln 4|V | δ
and α, then with probability at least 1 -11δ the predictions y(i, j) satisfy y(i, j) = y * (i, j) for all (i, j) ∈ E θ such that η(i, j) -1 2 > 8ε.

Proof of Lemma 3. We apply Lemma 2 with θ = 2Q α ≥ 2 × max Q, 4 ln 2|V |+1 δ to the 2|V | + 1 subsets of E consisting of E L and E in (i), E out (i), for i ∈ V . We have that, with probability at least 1 -δ, at least Q edges of E L are sampled, at least Q edges of E in (i) are sampled for each i such that N in (i) ≥ θ, and at least Q edges of E out (j) are sampled for each j such that N out (j) ≥ θ. For all (i, j) ∈ E θ let

p j = 1 d in (j) i∈Nin(j) p i and q i = 1 d out (i) j∈Nout(i) q j
and set for brevity δ in (j) = 1 -un(j) and δ out (i) = 1 -tr(i). We now prove that δ in (j) and δ out (i) are concentrated around their expectations for all (i, j) ∈ E θ . Consider δ out (i) (the same argument works for δ in (j)). Let J 1 , . . . , J Q be the first Q draws in E 0 ∩ N out (i) and define

µ p (i) = 1 Q Q t=1 p i + q Jt 2 .
Applying Lemma 1 to the set pi+qj 2

: j ∈ N out (i) , and using our choice of Q, we get that µ p (i) -µ p (i) ≤ ε holds with probability at least 1 -δ/(2|V |), where

µ p (i) = 1 d out (i) j∈Nout(i) p i + q j 2 = p i + q i 2 .
Now consider the random variables Z t = I {y i,Jt = 1}, for t = 1, . . . , Q. Conditioned on J 1 , . . . , J Q , these are independent Bernoulli random variables with

E[Z t | J t ] = pi+q J t 2
. Hence, applying a standard Hoeffding bound for independent variables and using our choice of Q, we get that

1 Q Q t=1 Z t -µ p (i) ≤ ε
with probability at least 1 -δ/(2|V |) for every realization of J 1 , . . . , J Q . Since δ out (i) = (Z 1 + • • • + Z Q )/Q, we get that δ out (i) -µ p (i) ≤ 2ε with probability at least 1 -2δ/(2|V |). Applying the same argument to δ in (j), and the union bound9 on the set δ in (j), δ out (i) : (i, j) ∈ E θ , we get that

δ out (i) + δ in (j) - p i + q j 2 - p j + q i 2 ≤ 4ε (6)
simultaneously holds for all (i, j) ∈ E θ with probability at least 1 -4δ. Now notice that p j is a sample mean of Q i.i.d. [0, 1]-valued random variables drawn from the prior marginal 1 0 µ •, q dq with expectation µ p . Similarly, q i is a sample mean of Q i.i.d. [0, 1]-valued random variables independently drawn from the prior marginal 1 0 µ p, • dp with expectation µ q . By applying Hoeffding bound for independent variables, together with the union bound to the set of pairs of random variables whose sample means are p j and q i for each (i, j) ∈ E θ (there are at most 2|V | of them) we obtain that p j -µ p ≤ ε and q i -µ q ≤ ε hold simultaneously for all (i, j) ∈ E θ with probability at least 1 -2δ. Combining with [START_REF] Cesa-Bianchi | A linear time active learning algorithm for link classification[END_REF] we obtain that

δ out (i) + δ in (j) - p i + q j 2 - µ p + µ q 2 ≤ 5ε (7)
simultaneously holds for each (i, j) ∈ E θ with probability at least 1 -6δ. Next, let E L be the set of the first Q edges drawn in E L ∩ E 0 . Then

E τ = 1 Q (i,j)∈E L P y i,j = 1 = 1 Q (i,j)∈E L p i + q j 2 ,
where the expectation is w.r.t. the independent draws of the labels y i,j for (i, j) ∈ E L . Hence, by applying again Hoeffding bound (this time without the union bound) to the Q = 1 2ε 2 ln 2 δ independent Bernoulli random variables I {y i,j = 1}, (i, j) ∈ E L , the event τ -E τ ≤ ε holds with probability at least 1 -δ. Now, introduce the function

F (p, q) = E τ = 1 Q (i,j)∈E L p i + q j 2 .
For any realization q 0 of q, the function

F 1 (p) = F (p, q 0 ) is a sample mean of Q = 1 2ε 2 ln 4|V | δ i.i.d. [0, 1]- valued random variables {p i : (i, j) ∈ E L } (recall that if i ∈ V
is the origin of an edge (i, j) ∈ E L , then it is not the origin of any other edge (i, j ) ∈ E L ). Using again the standard Hoeffding bound, we obtain that F (p, q) -E p F (p, q) ≤ ε holds with probability at least 1-δ for each q ∈ [0, 1] |V | . With a similar argument, we obtain that E p F (p, q) -E p,q F (p, q) ≤ ε also holds with probability at least 1 -δ. Since E p,q F (p, q) = µ p + µ q 2

we obtain that

τ - µ p + µ q 2 ≤ 3ε (8)
with probability at least 1 -3δ. Combining ( 7) with ( 8) we obtain

δ out (i) + δ in (j) - p(i) + q(j) 2 ≤ 8ε
simultaneously holds for each (i, j) ∈ E θ with probability at least 1 -10δ. Putting together concludes the proof.

Derivation of the maximum likelihood equations.

Recall that the training set E 0 = i t , j t ), y it,jt : t = 1, . . . , m is drawn uniformly at random from E without replacement. We can write

P E 0 {p i , q i } |V | i=1 = 1 |E| m m! m k=1 p i k + q j k 2 I{yi k ,j k =+1} × m k=1 1 - p i k + q j k 2 I{yi k ,j k =-1} = 1 |E| m m! |V | =1 m k=1 p + q j k 2 I{i k = , y ,j k =+1} × m k=1 1 - p + q j k 2 I{i k = , y ,j k =-1} so that log P E 0 {p i , q i } |V | i=1 is proportional to |V | =1 m k=1 I {i k = , y ,j k = +1} log p + q j k 2 + |V | =1 m k=1 I {i k = , y ,j k = +1} log 1 - p + q j k 2 and ∂ log P E 0 {p i , q i } |V | i=1 ∂p = m k=1 I {i k = , y ,j k = +1} p + q j k - m k=1 I {i k = , y ,j k = -1} 2 -p -q j k .
By a similar argument,

P E 0 {p i , q i } |V | i=1 = 1 |E| m m! |V | =1 m k=1 p i k + q 2 I{j k = , y i k , =+1} × m k=1 1 - p i k + q 2 I{j k = , y i k , =-1}
so that

∂ log P E 0 {p i , q i } |V | i=1 ∂q = m k=1 I {j k = , y i k , = +1} p i k + q - m k=1 I {j k = , y i k , = -1} 2 -p i k -q .
B Proofs from Section 5

Proof of Theorem 2. Let each node i ∈ V host two instances of the randomized Weighted Majority (RWM) algorithm [4] with an online tuning of their learning rate [2,1]: one instance for predicting the sign of outgoing edges (i, j), and one instance for predicting the sign of incoming edges (j, i). Both instances simply compete against the two constant experts, predicting always +1 or always -1. Denote by M (i, j) the indicator function (zero-one loss) of a mistake on edge (i, j).

Then the expected number of mistakes of each RWM instance satisfy [2,1]:

j∈Nout(i) E M (i, j) = Ψ out (i, Y )+O Ψ out (i, Y ) + 1 and i∈Nin(j) E M (i, j) = Ψ in (j, Y ) + O Ψ in (j, Y ) + 1 .
We then define two meta-experts: an ingoing expert, which predicts y i,j using the prediction of the ingoing RWM instance for node j, and the outgoing expert, which predicts y i,j using the prediction of the outgoing RWM instance for node i. The number of mistakes of these two experts satisfy

i∈V j∈Nout(i) E M (i, j) = Ψ out (Y ) + O |V |Ψ out (Y ) + |V | j∈V i∈Nin(j) E M (i, j) = Ψ in (Y ) + O |V |Ψ in (Y ) + |V | ,
where we used j∈V Ψ in (j, Y ) ≤ |V |Ψ in (Y ), and similarly for Ψ out (Y ). Finally, let the overall prediction of our algorithm be a RWM instance run on top of the ingoing and the outgoing experts. Then the expected number of mistakes of this predictor satisfies

(i,j)∈E E M (i, j) = Ψ G (Y ) + O |V |Ψ G (Y ) + |V | + Ψ G (Y ) + |V | + |V |Ψ G (Y ) = Ψ G (Y ) + O |V |Ψ G (Y ) + |V | , as claimed.
Proof sketch of Theorem 3. Let Y K be the set of all labelings Y such that the total number of negative and positive edges are K and |E| -K, respectively (without loss of generality we will focus on negative edges). Consider the randomized strategy that draws a labeling Y ∈ {-1, +1} |E| uniformly at random from Y K . For each node i ∈ V , we have Ψ in (i, Y ) ≤ d - in (i), which implies Ψ in (Y ) ≤ K. A very similar argument applies to the outgoing edges, leading to Ψ out (Y ) ≤ K. The constraint Ψ G (Y ) ≤ K is therefore always satisfied.

The adversary will force on average 1/2 mistakes in each one of the first K rounds of the online protocol by repeating K times the following: (i) A label value ∈ {-1, +1} is selected uniformly at random. (ii) An edge (i, j) is sampled uniformly at random from the set of all edges that were not previously revealed and whose labels are equal to .

The learner is required to predict y i,j and, in doing so, 1/2 mistakes will be clearly made on average because of the randomized labeling procedure. Observe that this holds even when A knows the value of K and Ψ G (Y ). Hence, we can conclude that the expected number of mistakes that A can be forced to make is always at least K/2, as claimed.

We now show that, as K |E| → 0, the lower bound gets arbitrarily close to K for any G(Y ) and any constant K. Let E be the following event: There is at least one unrevealed negative label. The randomized iterative strategy used to achieve this result is identical to the one described above, except for the stopping criterion. Instead of repeating step (i) and (ii) only for the first K rounds, these steps are repeated until E is true. Let m r,c be defined as follows: For c = 1 it is equal to the expected number of mistakes forced in round r when K = 1. For c > 1 it is equal to the difference between the expected number of mistakes forced in round r when K = c and K = c -1. One can see that m r,c is null when r < c. When K = 1, the probability that E is true in round r is clearly equal to 1 2 r-1 . Hence, the expected number of mistakes made by A when K = 1 in any round r is equal to 1 2 1 2 r-1 = 1 2 r . We can therefore conclude that m r,1 = 1 2 r for all r. A simple calculation shows that if r = c then m r,c = 1 2 r . Furthermore, when r > 1 and c > 1, we have the following recurrence:

m r,c = m r-1,c + m r-1,c-1 2 .
In order to calculate m r,c for all r and c, we will rest on the ancillary quantity s j (i), recursively defined as specified next.

Given any integer variable i, we have s 0 (i) = 1 and, for any positive integer j, s j (i) = i k=1 s j-1 (k) .

It is not difficult to verify that m r,c = s c-1 (r -c + 1) 2 r .

Since s j (i) = i j j! , where i j is the rising factorial i(i + 1)(i + 2) . . . (i + j -1), we have m r,c = r -c + 1 c-1 (c -1)!2 r .

When K |E| → 0, given any integer K > 1, the difference between the expected number of mistakes forced when K = K and K = K -1 is equal to

∞ r=K m r,K = 1 (K -1)! ∞ r=K r -K + 1 K -1 2 r = 1 (K -1)!2 K -1 ∞ r =1 r K -1 2 r ,
where we set r = r -K + 1. Setting i = i -1 and recalling that

i j = j! i + j -1 i -1 ,
we have

1 j! ∞ i=1 i j 2 i = ∞ i=1 i+j-1 i-1 2 i = ∞ i =0 i +j i 2 i +1 .
Now, using the identity

i + j + 1 i = i + j i + i + j i -1 ,
we can easily prove by induction on j that

∞ i =0 i +j i 2 i +1 = 2 j .
Hence, we have

C Further Experimental Results

This section contains more evidence related to the experiments in Section 6 of the main paper. In particular, we experimentally demonstrate the alignment between blc(tr, un) and LogReg.

After training on the two features 1-tr(i) and 1-un(j), LogReg has learned three weights w 0 , w 1 and w 2 , which allow to predict y i,j according to sgn w 1 (1 -tr(i) + w 2 1 -un(j) + w 0 .

This can be rewritten as sgn 1 -tr(i) + w 2 1 -un(j) -1 2 -τ , with w 2 = w2 w1 and τ = -1 2 + w0 w1 .

As shown in Table 3, and in accordance with the predictor built out of Equation ( 2) from the main paper, w 2 is almost 1 on all datasets, while τ tends to be always close the fraction of positive edges in the dataset.

Figure 1 :

 1 Figure 1: (a) A directed edge-labeled graph G. (b) Its corresponding graph G resulting from the G → G reduction. The square nodes in G correspond to the edges in G, and carry the same labels as their corresponding edges. On the other hand, the 2|V | circle nodes in G are unlabeled. Observe that some nodes in G are isolated (and thus unimportant); these are exactly the nodes in G corresponding to the nodes having in G no outgoing or no incoming edges -see, e.g., nodes 3 and 4 in G. (c) The weighted graph resulting from the G → G reduction.

Theorem 3 . 2 .

 32 Given any edge-labeled graphG(Y ) = (V, E(Y )) and any integer K ≤ |E| 2 , a randomized labeling Y ∈ {-1, +1} |E| exists such that Ψ G (Y ) ≤ K,and the expected number of mistakes that any online algorithm A can be forced to make satisfies EM A (Y ) ≥ K Moreover, as K |E| → 0 then EM A (Y ) = K.

7

 7

7

 7

0 EM

 0 shown earlier, m r,1 = 1 2 r for all r. Hence we can conclude that when K |E| → K = K for any edge-labeled graph G(Y ) and any constant K, as claimed.

Table 1

 1

	that our generative model essentially fits all of them.
	Specifically, the last two columns of the table report the
	rate of label (ir)regularity, as measured by Ψ 2 G (Y )/|E|
	(second-last column) and Ψ G (Y )/|E| (last column),

Table 1 :

 1 Dataset properties. The 5th column gives the fraction of positive labels. The last two columns provide two different measures of label regularity -see main text.

	Dataset	|V |	|E|	|E| |V |	|E + | |E|	Ψ 2 G (Y ) |E|	Ψ G (Y ) |E|
	Citations	4,831	39,452	8.1 72.33%	.076	.191
	Wikipedia	7,114 103,108 14.5 78.79%	.063	.142
	Slashdot	82,140 549,202	6.7 77.40%	.059	.143
	Wik. Edits 138,587 740,106	5.3 87.89%	.034	.086
	Epinion	131,580 840,799	6.4 85.29%	.031	.074

Table 2 :

 2 MCC with increasing training set size, with one standard deviation over 12 random sampling of E 0 . The last four columns refer to the methods we took from the literature. For the sake of readability, we multiplied all MCC values by 100. The best number in each row is highlighted in bold brown and the second one in italic red. If the difference is statistically significant (p-value of a paired Student's t-test less than 0.005), the best score is underlined. The "time" rows contain the time taken to train on a 15% training set.Wikipedia3% 34.08 ± 1.03 31.65 ± 0.99 32 .08 ± 0.94 28.50 ± 0.92 19.73 ± 0.99 3.98 ± 0.84 27.43 ± 0.99 20.11 ± 1.14 9% 45.80 ± 0.43 44.92 ± 0.48 45 .72 ± 0.42 43.02 ± 0.52 30.24 ± 0.54 23.50 ± 1.66 41.36 ± 0.66 38.05 ± 0.93 15% 50 .49 ± 0.33 49.89 ± 0.40 50.87 ± 0.36 49.08 ± 0.33 35.77 ± 0.58 33.64 ± 0.83 48.50 ± 0.47 47.07 ± 0.38 20% 52 .74 ± 0.31 52.24 ± 0.49 53.13 ± 0.27 51.79 ± 0.35 37.90 ± 0.27 38.41 ± 0.53 51.49 ± 0.43 50.54 ± 0.39 25% 54 .00 ± 0.63 53.42 ± 0.59 54.26 ± 0.37 53.31 ± 0.37 40.16 ± 0.57 41.34 ± 1.07 53.30 ± 0.37 52.92 ± 0.3% 36 .58 ± 0.43 31.71 ± 0.59 32.29 ± 0.47 29.14 ± 0.56 34.39 ± 0.56 20.57 ± 0.93 42.98 ± 0.56 24.96 ± 0.43 9% 45 .71 ± 0.28 41.06 ± 0.38 42.19 ± 0.18 39.60 ± 0.25 39.39 ± 0.34 37.92 ± 1.57 47.40 ± 0.42 36.83 ± 0.36 15% 49.62 ± 0.22 45.42 ± 0.36 46.42 ± 0.16 45.56 ± 0.19 41.21 ± 0.19 45.88 ± 1.01 48 .75 ± 0.71 43.47 ± 0.16 20% 51 .88 ± 0.24 47.78 ± 0.25 48.66 ± 0.10 48.10 ± 0.30 42.74 ± 0.44 48.79 ± 0.57 52.10 ± 0.33 46.89 ± 0.27 25% 53 .12 ± 0.20 49.39 ± 0.24 50.22 ± 0.12 50.11 ± 0.20 44.24 ± 0.44 50.62 ± 0.53 53.29 ± 0.22 49.42 ± 0.Epinion 3% 51 .43 ± 0.29 41.42 ± 0.84 43.41 ± 0.34 36.56 ± 0.49 37.01 ± 0.57 31.71 ± 6.20 52.33 ± 0.42 31.25 ± 0.80 9% 58 .48 ± 0.26 53.20 ± 0.62 54.80 ± 0.12 51.58 ± 0.36 43.81 ± 0.50 50.43 ± 2.07 60.06 ± 0.46 48.06 ± 0.41 15% 61 .47 ± 0.21 57.63 ± 0.45 59.25 ± 0.17 58.80 ± 0.32 48.24 ± 0.58 54.64 ± 1.62 62.69 ± 0.21 56.94 ± 0.65 20% 63 .17 ± 0.13 60.15 ± 0.40 61.45 ± 0.17 61.86 ± 0.13 52.21 ± 0.37 57.27 ± 1.42 64.10 ± 0.12 61.18 ± 0.45 25% 64.05 ± 0.20 61.88 ± 0.38 62.89 ± 0.12 63.42 ± 0.14 54.68 ± 0.62 58.42 ± 1.59 65.40 ± 0.85 64 .59 ± 0.3% 33.88 ± 0.54 26 .02 ± 0.80 26.02 ± 0.42 15.13 ± 0.40 19.93 ± 0.56 0.86 ± 0.11 23.50 ± 0.54 20.10 ± 0.60 9% 38.62 ± 0.52 35.10 ± 0.17 35 .29 ± 0.11 28.23 ± 0.33 26.61 ± 0.37 9.99 ± 0.93 33.22 ± 0.29 33.86 ± 0.24 15% 39 .08 ± 0.55 37.77 ± 0.22 38.27 ± 0.19 33.61 ± 0.11 30.05 ± 0.29 17.95 ± 0.92 36.88 ± 0.32 40.00 ± 0.26 20% 39.04 ± 0.69 38.88 ± 0.36 39 .55 ± 0.11 35.04 ± 0.17 32.17 ± 0.31 21.44 ± 0.67 38.60 ± 0.31 43.32 ± 0.22 25% 38.90 ± 0.45 39.41 ± 0.16 40 .44 ± 0.14 36.18 ± 0.20 33.94 ± 0.74 23.41 ± 0.41 39.75 ± 0.32 45.76 ± 0.29

		|E 0 | |E|	L. Prop.	blc(tr, un)	LogReg	Unreg.	LowRank	16 Triads	RankNodes	Bayesian
	Citations	3% 19.07 ± 1.38 14.97 ± 0.72 15 .05 ± 0.73 10.88 ± 0.83 8.89 ± 1.44 7.54 ± 1.42 12.48 ± 1.18 11.06 ± 1.64 9% 29.64 ± 0.74 25 .96 ± 0.61 25.90 ± 0.67 23.51 ± 0.72 17.05 ± 0.70 16.13 ± 0.64 23.84 ± 0.91 23.44 ± 0.81 15% 35.66 ± 0.68 32 .87 ± 0.58 32.79 ± 0.60 31.39 ± 0.75 22.58 ± 0.53 21.55 ± 0.91 30.60 ± 0.87 31.71 ± 0.99 20% 38.67 ± 0.48 36 .94 ± 0.51 36.86 ± 0.48 35.47 ± 0.41 25.80 ± 0.94 24.27 ± 0.56 35.01 ± 0.83 36.13 ± 0.75 25% 41.05 ± 0.73 39.83 ± 0.58 39.76 ± 0.59 38.48 ± 0.55 29.67 ± 0.78 26.85 ± 0.87 38.06 ± 0.86 40 .34 ± 0.94 time 19.6 0.6 2.6 2835 3279 6.2 155 4813
											48
		time	41.9	1.6	6.0	10629	8523	14.8	249	12507
	Slashdot	time	677	8.3	32.8	78537	69988	131	2441	68085	22
											30
		time	1329	10.1	54.0	143881	127654	209	3174	104305
	Wik. Edits	time	927	9.6	46.8	219109	129460	177	3890	92719

Table 3 :

 3 Normalized logistic regression coefficients averaged over 12 runs (with one standard deviation)

	|E 0 | |E|	w 2	τ
	Citations

Recall that the cutsize of an undirected node-labeled graph G (Y ) is the number of edges in G connecting nodes having mismatching labels.

One might view our model as reminiscent of standard models for link generation in social network analysis, like the classical p1 model from[START_REF] Holland | An Exponential Family of Probability Distributions for Directed Graphs[END_REF]. Yet, the similarity falls short, for all these models aim at representing the likelihood of the network topology, rather than the probability of edge signs, once the topology is given.

This is the KONECT version of the "Wikisigned" dataset, from which we removed self-loops.

We again removed self-loops and merged multi-edges which are all of the same sign.

The sample spaces for the ingoing and outgoing edges of the vertices occurring as endpoints in E θ overlap. Hence, in order to prove a uniform concentration result, we need to apply the union bound over the random variables defined over these sample spaces, which motivates the presence of the factor ln(2|V |) in the definition of Q.