K Crosby

L L Shaw
email: lshaw2@iit.edu

C Estournes

G Chevallier

A W Fliflet

M A Imam

Enhancement in Ti-6Al-4V sintering via nanostructured powder and spark plasma sintering

Keywords: Titanium alloys, Ball milling, Nanomaterials, Sintering

Studies are performed to enhance low temperature sintering of Ti-6Al-4V. High energy ball milling is found to be effective in lowering the sintering temperature through the mechanisms of particle size reduction and nanograin formation. The former reduces the diffusion distance for densification, whereas the latter introduces an additional densification mechanism allowing mass transport from the interior of the particle to the neck zone. Together, these two effects can reduce the onset temperature for densification by about 300uC. Spark plasma sintering can further improve low temperature sintering when compared with radiant heat sintering and microwave sintering. The enhanced densification is discussed on the basis of the applied pressure (50 MPa) and the intrinsic joule effect that leads to increase in the local temperature at the contact point between particles.

Introduction

Currently, there is a significant need to improve fixation and performance of orthopaedic implants because of the growing elderly population. Device lifespan and bioactivity have been improved steadily since the inception of orthopaedic implants through the use of specific materials systems (e.g. bioinert metallic alloys, low modulus alloys and bioactive ceramic coatings) [START_REF] Niinomi | Recent metallic materials for biomedical applications[END_REF][START_REF] Niinomi | Mechanical biocompatibilities of titanium alloys for biomedical applications[END_REF][START_REF] Hu | One-step modification of nano-hydroxyapatite coating on titanium surface by hydrothermal method[END_REF] and fabrication techniques (e.g. porous surface structures). [START_REF] Dewidar | Properties of solid core and porous surface Ti-6Al-4V implants manufactured by powder metallurgy[END_REF] However, there is still a desire to further enhance the lifespan and performance of implants such that the device meets or exceeds the performance of the natural biological structure. One of the approaches to achieve this goal is to develop functionally graded implants composed of a Ti-6Al-4V (Ti-6-4) core and a hydroxyapatite (HA) rich surface. The former will provide mechanical strength, while the latter will offer a bioactive surface with no sharp interface between the core and surface. Such functionally graded implants can be fabricated via powder processing and cosintering of Ti-6-4 and HA. However, cosintering of Ti-6-4 and HA at temperatures above 1000uC results in a substantial strength reduction of Ti-6-4 due to the embrittlement of oxygen diffusion into the metal. [START_REF] Wei | Hydroxyapatite-coated metals: interfacial reactions during sintering[END_REF] Thus, there is a critical need to study methods for sintering Ti-6-4 at temperatures ,1000uC.

Sintering behaviour of Ti-6-4 has been studied by many investigators in order to obtain either porous or dense bodies. [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF][START_REF] Jo | Mechanical properties of fully porous and porous-surfaced Ti-6Al-4V implants fabricated by electro-discharge-sintering[END_REF][START_REF] Kim | Densification behavior of titanium alloy powder during hot pressing[END_REF][START_REF] Tasdemirci | The effect of strain rate on the compressive deformation behavior of a sintered Ti6Al4V powder compact[END_REF][START_REF] Lee | Fabrication of fully porous and porous-surfaced Ti-6Al-4V implants by electro-discharge-sintering of spherical Ti-6Al-4V powders in an one-step process[END_REF][START_REF] Dewidar | Properties of solid core and porous surface Ti-6Al-4V implants manufactured by powder metallurgy[END_REF][START_REF] Nicula | Spark plasma sintering synthesis of porous nanocrystalline titanium alloys for biomedical applications[END_REF][START_REF] Bautista | Influence of sintering on the corrosion behavior of a Ti-6Al-4V alloy[END_REF][START_REF] Guden | Compression testing of a sintered Ti6Al4V powder compact for biomedical applications[END_REF] Porous bodies or porous surface with a dense core is aimed at enhancing tissue ingrowth for Ti-6-4 orthopaedic implants, [START_REF] Jo | Mechanical properties of fully porous and porous-surfaced Ti-6Al-4V implants fabricated by electro-discharge-sintering[END_REF][START_REF] Lee | Fabrication of fully porous and porous-surfaced Ti-6Al-4V implants by electro-discharge-sintering of spherical Ti-6Al-4V powders in an one-step process[END_REF][START_REF] Dewidar | Properties of solid core and porous surface Ti-6Al-4V implants manufactured by powder metallurgy[END_REF][START_REF] Nicula | Spark plasma sintering synthesis of porous nanocrystalline titanium alloys for biomedical applications[END_REF] whereas dense bodies can offer superior specific strength for load carrying applications. [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF][START_REF] Kim | Densification behavior of titanium alloy powder during hot pressing[END_REF] In general, 1200uC or higher is required to obtain dense Ti-6-4 bodies. Specifically, Tasdemirci et al. [START_REF] Tasdemirci | The effect of strain rate on the compressive deformation behavior of a sintered Ti6Al4V powder compact[END_REF] reveal that sintering at 1200uC for 2 h only results in Ti-6-4 bodies that still contain 38 vol.-% porosity. The same sintering result is reported by Guden et al. [START_REF] Guden | Compression testing of a sintered Ti6Al4V powder compact for biomedical applications[END_REF] Shibo and his co-workers [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF] show that depending on the binder used in the powder injection moulding process, powder injection moulded Ti-6-4 bodies can reach a relative density of either 97 or 94% of the theoretical density after sintering at 1230uC for 3 h. They further demonstrate that uniaxial pressing of the same Ti-6-4 powder followed by sintering at 1230uC for 3 h can only lead to a relative density of 95%, similar to the powder injection moulded bodies. Bautista et al. [START_REF] Bautista | Influence of sintering on the corrosion behavior of a Ti-6Al-4V alloy[END_REF] have sintered Ti-6-4 bodies at different conditions and have shown that Ti-6-4 bodies still contain about 0?5% porosity after sintering at 1260uC for 4 h. When the sintering temperature is reduced to 1230 and 1200uC, the porosity level is increased to 1 and 1?3% respectively. [START_REF] Bautista | Influence of sintering on the corrosion behavior of a Ti-6Al-4V alloy[END_REF] All of these studies reveal one common phenomenon, that is pressureless sintering of Ti-6-4 requires sintering temperatures at 1200uC or higher in order to reduce porosity in the sintered bodies.

In order to obtain fully dense Ti-6-4 bodies, pressure is often applied during sintering. For example, Shibo et al. [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF] demonstrate that Ti-6-4 bodies with 99?3% density can be obtained by pressureless sintering at 1230uC for 3 h, followed by hot isostatic pressing at 1230uC again. Kim and Yang 8 also reveal that by applying a pressure of 60 MPa during hot pressing (HP), Ti-6-4 bodies with density higher than 99% can be obtained after HP at 950uC for 2 h. However, HP at 850uC for 2 h is not sufficient to obtain Ti-6-4 bodies with density higher than 99%. [START_REF] Kim | Densification behavior of titanium alloy powder during hot pressing[END_REF] Clearly, there are challenges in attaining dense Ti-6-4 bodies at sintering temperature below 1000uC. In this study, we focus on the investigation of processing of nanostructured Ti-6-4 powder along with different sintering methods in order to achieve sintering of fully dense Ti-6-4 bodies at 1000uC or lower. This study will pave the way to achieve co-sintering of Ti-6-4 and HA at temperatures compatible with the stability domain of HA and prevention of Ti-6-4 embrittlement (i.e. ,1000uC) in the near future. The detail of attaining nanostructured Ti-6-4 and sintering at temperatures below 1000uC is described below.

Materials and methods

The commercial Ti-6-4 powder was purchased from Advanced Specialty Metals (Nashua, NH, USA). The as received powder is composed of highly uniform spherical particles in the range of 45-250 mm in diameter. High energy ball milling under inert argon atmosphere was performed using a SPEX mill with a ball/powder weight ratio of 10 : 1. To prevent excessive cold welding during ball milling, stearic acid was added to the powder as a process control agent (PCA). The concentration of stearic acid ranging from 1 to 5 wt-% was investigated in order to identify the proper concentration of PCA for achieving the smallest crystallite size of Ti-6-4 along with the minimum particle size. To avoid substantial heating during ball milling that can also lead to excessive cold welding, long duration ball milling was conducted using short 1 h milling increments followed by 15 min of cooling at room temperature. On the basis of these investigations, Ti-6-4 powder with the smallest crystallite size was selected for sintering studies.

Sintering investigation was performed using three different methods, that is traditional radiant heat sintering (RHS), spark plasma sintering (SPS) and microwave sintering (MWS). Radiant heat sintering was conducted using an alumina tube with steel end caps which allow for atmospheric control. Green body pellets were prepared with a stainless steel die by using 300 MPa uniaxial pressure. To prevent oxidation during sintering, pellets were wrapped in tantalum foil and sealed in quartz tubing under a vacuum of less than 10 mT before their insertion into the alumina tube, which was evacuated and purged with argon before the onset of heating. Spark plasma sintering was performed at the Plateforme Nationale CNRS de Frittage-Flash (PNF 2 , Toulouse) using a Dr Sinter 2080 (SPS Syntex Inc., Japan). The desired amount of Ti-6-4 powder was loaded into a graphite die of 8 mm in diameter. For easy removal of the sintered pellet, a sheet of graphitic paper was placed between the punch and the powder as well as between the die and the powder to prevent sticking due to any possible reaction between the powder and graphite die/punch. A uniaxial pressure of 50 MPa was applied throughout the process. Sintering was conducted under vacuum, and the heating rate was 100uC min [START_REF] Belyakov | Grain refinement in copper under large strain deformation[END_REF] . Changes in temperature, average intensity and voltage of the pulsed current and sintering displacement were recorded in situ by a computer during the entire sintering process. The thermocouple for monitoring the temperature was placed in a little hole 3 mm in depth at the surface of the graphite die. Thus, the measured value corresponds to the temperature of the inner surface of the die near the sample. However, because of the high thermal conductivity of graphite and Ti-6-4, the sample temperature would be close to the thermocouple reading. The sintering displacement curves were used to identify the onset and completion temperatures of densification during continuous heating. The green pellets 0?5 inch in diameter for MWS were formed using 670 MPa uniaxial pressure, followed by 690 MPa isostatic pressing at room temperature. The green pellets were then placed inside an insulated chamber. No susceptor material was used due to the particle-pore dipole interaction that suffices to generate heat within the sample. The microwaves were generated in a 2?45 GHz Cober Electronics Model S6F Industrial Microwave Generator and transported to the heating chamber via S band waveguide.

Scanning electron microscopy (SEM) was used to examine the average powder particle size as a function of milling duration. Samples for particle size measurements were prepared by dry dropping of the powder particles onto copper tape that was mounted on an SEM sample stub. Quantification via SEM involved direct measurement of the powder particles using a calibration based on the scale bar specific to the magnification displayed on each image. Approximately 15 particles were measured from each of five images of the same SPEX milling powder condition. As such, the average particle size calculation took into account the distribution of particle sizes over .50 particles. Scanning electron microscopy analysis was also conducted to examine the microstructure and porosity of sintered samples. On the basis of the porosity at the polished cross-section, the densities of sintered samples were determined. For microstructural characterisation of the as received and ball milled powders, powders were mounted in conductive copper mounting compound, ground to 1200 grit SiC roughness and then polished to a mirror finish using 0?05 mm colloidal silica. After a uniform surface was attained, the sample was swabbed with Kroll's etchant until the microstructure had reasonable contrast under the optical microscope.

X-ray diffraction (XRD) (Bruker D2 Phaser, Madison, WI, USA) studies were conducted for each SPEX milled sample to determine phase purity and monitor any compounds that may be forming during the milling process using Cu K a radiation, 30 V, 10 mA, 0?02u/step and 0?26 s/step scan rate. In addition to monitoring phase formation, XRD was also used to estimate the crystallite size via peak broadening through the use of the Scherrer formula [START_REF] Klug | X-ray diffraction procedures for polycrystalline and amorphous materials[END_REF] b g ~kl=Dcos h

where b g is the full width half maximum peak breadth, k is the shape factor (y1?0), l is the X-ray wavelength (Cu K a1 51?541 nm), D is the crystallite size and h is the Bragg angle. In this study, the reflections used for the crystallite size estimation were at low 2h angles (to be provided in the section on 'Results and discussion'). Since the reflections used for the crystallite size estimation were at low 2h angles and the instrumental broadening of our instrument was small, the broadening was therefore mainly attributed to ultrafine crystallites. [START_REF] Shaw | Thermal stability of nanostructured Al 93 Fe 3 Ti 2 Cr 2 alloys prepared via mechanical alloying[END_REF] To verify the crystallite size estimation via the XRD line broadening, transmission electron microscopy (TEM) analysis of ball milled samples was performed. The TEM samples were prepared by ultrasonicating the ball milled powder in ethanol for 15 min to suspend the fine particles. A pipette was used to dispense a few suspension drops to an ultrathin carbon film (Ted Pella TEM product). The drops were allowed to dry in air. The operating condition of the TEM (FEI Tecnai Spirit Twin TEM) was 120 kV in either bright or dark field imaging modes.

Results and discussion

Particle size reduction and nanostructure formation through high energy ball milling Figure 1 shows the evolution of the shape and microstructure of Ti-6-4 particles induced by ball milling. One hour ball milling has changed the initial spherical particles with an average diameter of 120 mm (Fig. 1a) to large flakes with a thickness of y25 and 150 mm in diameter (Fig. 1b). Further ball milling up to 4 h leads to equiaxed particles with an average diameter of y25 mm (Fig. 1c). However, prolonged milling beyond the 4 h duration yields little change in the particle morphology and the average particle diameter, indicating that a balance between cold welding and fracture has been reached at y4 h milling for the material with 4 wt-% stearic acid. Such morphology evolution is consistent with the behaviour of ductile phases subjected to high energy ball milling observed previously. [START_REF] Aikin | The Kinetics of composite particle formation during mechanical alloying[END_REF][START_REF] Zawrah | Microstructure and hardness of nanostructured Al-Fe-Cr-Ti alloys through mechanical alloying[END_REF][START_REF] Shaw | Effects of process control agents on mechanical alloying of nanostructured aluminum alloys[END_REF] That is the formation of plate-like morphology at the early stage of milling due to severe plastic deformation via 'mini forging', which is followed by repeated particle fracture once the ductility of particles is exhausted. Finally, the extensive particle fracture is balanced by cold welding, leading to the final particle sizes that are insensitive to the prolonged milling time.

In addition to the particle morphology evolution, the microstructure of particles has been altered as well. The as received powder particles show a dendritic microstructure with a dendrite arm thickness of y4 mm, indicative of slow cooling from a melt (Fig. 1d). When ball milling is performed, the dendritic microstructure is replaced by an elongated lamellar microstructure with a thickness of y1 mm (Fig. 1e). Such microstructure evolution is due to continual plastic deformation and cold welding during the ball milling process. Although nanograin formation cannot be detected using SEM, the XRD and TEM analyses below indicate that the microstructure change at the nanometre level also takes place during ball milling.

Figure 2 shows the XRD spectra of Ti-6-4 as a function of the milling time. It can be seen that the crystallite size decreases continuously with increased milling duration, as indicated by the continuous peak broadening when the milling time increases. The coherent XRD domain size (termed as the crystallite size hereafter) of Ti-6-4 has been estimated using the Scherrer formula. [START_REF] Klug | X-ray diffraction procedures for polycrystalline and amorphous materials[END_REF] The two major reflections, (101) and (002), of Ti-6-4 are utilised for such estimation. The values obtained are listed in Table 1. As shown, the peak broadening analysis of both reflections reveals that the crystallite sizes of Ti-6-4 powder decrease continually as the milling time increases. With 4 h milling, the crystallite sizes have been reduced to 35 or 15 nm, depending on which reflection is considered. In contrast, the crystallite size for the as received particles is beyond the valid range of the Scherrer formula (i.e. .100 nm). The estimation of crystallite sizes was corroborated using the TEM analysis. As shown in Fig. 3, the Ti-6-4 powder after 4 h of ball milling with the presence of 4 wt-% stearic acid exhibits many grains with sizes in the order of 10-20 nm. These observations are consistent with the expectation that sufficient high energy ball milling will result in the formation of nanograins within ductile particles. [START_REF] Zawrah | Microstructure and hardness of nanostructured Al-Fe-Cr-Ti alloys through mechanical alloying[END_REF][START_REF] Shaw | Effects of process control agents on mechanical alloying of nanostructured aluminum alloys[END_REF][START_REF] Fecht | Nanocrystalline metals prepared by high-energy ball milling[END_REF][START_REF] Belyakov | Grain refinement in copper under large strain deformation[END_REF][START_REF] Koch | The synthesis and structure of nanocrystalline materials produced by mechanical attrition: a review[END_REF][START_REF] Suryanarayana | Mechanical alloying and milling[END_REF] The formation of nanograins in ductile phases has been shown to proceed by substantial/ increases in dislocation density, followed by the disintegration of the crystal into subgrains separated by low angle grain boundaries, and a gradual increase in subgrain boundary misorientation, which eventually leads to the full evolution of nanograins. [START_REF] Fecht | Nanocrystalline metals prepared by high-energy ball milling[END_REF][START_REF] Belyakov | Grain refinement in copper under large strain deformation[END_REF] The effect of the PCA concentration on the particle size and crystallite size as a function of milling time is shown in Fig. 4. The data for the 1 wt-%PCA addition are not included in this figure because of severe cold welding of the powder to the walls of the milling vial. Figure 4 shows clearly that the average particle size decreases with increasing the PCA concentration. This is consistent with the expectation because the function of PCA is to prevent cold welding. [START_REF] Shaw | Effects of process control agents on mechanical alloying of nanostructured aluminum alloys[END_REF] Therefore, the more PCA, the more effective in preventing cold welding and thus the smaller particle size. It is interesting to note that the average crystallite size also decreases with increasing the PCA concentration until a critical concentration (y4 wt-% for 4 h milling) is reached. We propose that this phenomenon arises because of two competing processes. First, the initial increase in the PCA concentration results in smaller particle sizes, as shown in Fig. 4a. The decreased particle size leads to more effective plastic deformation of the particle and thus results in higher dislocation densities in the particle. The latter in turn translates to faster grain size reduction because the formation of nanograins requires the accumulation of plastic strain to a critical value. [START_REF] Umemoto | Formation of nanocrystalline structure in carbon steels by ball drop and particle impact techniques[END_REF] Second, after the PCA concentration reaches a critical value (y4 wt-% for 4 h milling), further increase in PCA does not lead to reduction in the grain size; instead, it may result in a slight increase in the grain size as shown in Fig. 4b. This is due to the lubricating effect of PCA and has been observed in ball milling of Al alloys previously. [START_REF] Shaw | Effects of process control agents on mechanical alloying of nanostructured aluminum alloys[END_REF] a as received; b ball milled for 1 h; c ball milled for 2 h; d ball milled for 3 h; e ball milled for 4 h (all are with 4 wt-% stearic acid) 2 X-ray diffraction spectra of Ti-6-4 samples Based on the reduced particle and crystallite sizes, we expect that sintering kinetics will be improved. Furthermore, we have chosen the Ti-6-4 powder ball milled for 4 h with the addition of 4 wt-% stearic acid for detailed sintering studies because this powder exhibits the lowest crystallite size along with the second smallest particle size. The sintering behaviour of this powder is described below.

Sintering enhancement via nanostructured powder

Figure 5 presents the microstructure of Ti-6-4 samples sintered under various conditions. The as received powder only results in a porous body after sintering at 1250uC for 2 h via RHS (Fig. 5a). The fraction of the solid area determined using the ImageJ image analysis software (National Institutes of Health, USA) is found to be y90%. However, 4 h ball milling before sintering has reduced porosity drastically and increased the sintered density to 97% of the theoretical (Fig. 5b). With SPS, the sintered density can reach .99% even with the use of the as received powder and continuous heating up to 860uC only (Fig. 5c). In contrast, MWS exhibits similar sintered densities as RHS, showing a density of 98% at the central region (Fig. 5d) and a density of 81% at the edge (not shown here) after sintering at 1250uC for 30 min. The densities of all other samples sintered under different conditions are summarised in Table 2. It is interesting to note that the sintered density for the 1 h ball milled powder sintered using RHS is only 75% of the theoretical, even lower than the density sintered from the as received powder. This is due to the formation of elongated plate-like particles after 1 h ball milling (Fig. 1b). These elongated plate-like particles do not pack well during uniaxial pressing, which is performed at a pressure below the yield strength of Ti-6-4. Therefore, the large pore volume and folding/unfolding of the plate-like particles prevent the achievement of high green density and thus lead to the low sintered density.

Note that the low density of the sintered bodies derived from the as received powder is in good accordance with other studies. Specifically, using Ti-6-4 particles with a mean diameter of 170 mm and sintering at 1200uC for 2 h, Tasdemirci et al. [START_REF] Tasdemirci | The effect of strain rate on the compressive deformation behavior of a sintered Ti6Al4V powder compact[END_REF] have obtained a sintered body of only 62% dense. In contrast, densification behaviour improves noticeably when the powder particle size decreases. For example, using Ti-6-4 powder with particle sizes ranging from 25 to 45 mm and pressing followed by sintering at 1230uC for 3 h, Shibo et al. [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF] have achieved sintered bodies of 94?6% dense. Although a precise comparison cannot be made between the present study and previous ones because of different sources of powders and different packing densities before sintering, the trend of the present study showing improved densification with decreasing particle sizes is consistent with previous investigations. [START_REF] Guo | Powder injection molding of Ti-6Al-4V alloy[END_REF][START_REF] Tasdemirci | The effect of strain rate on the compressive deformation behavior of a sintered Ti6Al4V powder compact[END_REF][START_REF] Guden | Compression testing of a sintered Ti6Al4V powder compact for biomedical applications[END_REF] For the present study, the drastically improved densification behaviour of 4 h ball milled Ti-6-4 samples versus the as received powder can be attributed to two factors. First, the particle size has been reduced from y120 to 25 mm. This particle size reduction will translate into a shorter diffusion distance from the interparticle boundary area to the neck zone of the particles, and thus enhance the densification rate, as predicted by Herring's scaling law. [START_REF] Herring | Effect of change of scale on sintering phenomena[END_REF] Second, the crystallites of the ball milled particles have been reduced to y35 nm or less, indicating the formation of nanograins within micrometre sized particles. As pointed out before, many metals exhibit the same behaviour as Ti-6-4 in this study, that is they become nanostructured particles after sufficient high energy ball milling. [START_REF] Zawrah | Microstructure and hardness of nanostructured Al-Fe-Cr-Ti alloys through mechanical alloying[END_REF][START_REF] Shaw | Effects of process control agents on mechanical alloying of nanostructured aluminum alloys[END_REF][START_REF] Fecht | Nanocrystalline metals prepared by high-energy ball milling[END_REF][START_REF] Belyakov | Grain refinement in copper under large strain deformation[END_REF][START_REF] Koch | The synthesis and structure of nanocrystalline materials produced by mechanical attrition: a review[END_REF][START_REF] Suryanarayana | Mechanical alloying and milling[END_REF] The presence of the nanograins will greatly increase the grain boundary area within each particle, and thus the diffusion flux of the atoms from the interior of the particle to the neck zone of the particles. The presence of this nanostructure effect can be confirmed by analysing the onset temperature for densification of the as received and 4 h ball milled samples during SPS. As shown in Fig. 6, the onset temperature for densification has been reduced from 893 K (620uC) for the as received powder to 613 K (340uC) for the 4 h ball milled sample. It is well known that at the initial stage of sintering, the shrinkage is related to neck growth through equation ( 2) 26

DL L 0 ~x D 2 ( 2
)
where the shrinkage DL/L 0 is the length change divided by the initial length, x is the neck diameter and D is the particle diameter. The neck size ratio x/D is in turn correlated to the particle diameter, sintering time t, sintering temperature T and the primary mechanism of mass transport for densification. [START_REF] German | Powder metallurgy science[END_REF] Assuming that the primary mechanism for densification is the mass transport from the interparticle boundary area to the neck zone through interparticle boundary diffusion, one will have the following relationship [START_REF] German | Powder metallurgy science[END_REF] x D

6 ~B0 exp { Q gb RT t D 4 (3)
where Q gb is the activation energy for interparticle boundary diffusion, which is close to that for grain boundary diffusion; B 0 is a constant related to the interparticle boundary width, surface energy and atomic volume; and t and T have been defined above. Since Ti-6-4 at the annealed condition is composed of y90% of the a phase and 10% of the b phase, [START_REF] Brooks | Heat treatment, structure and properties of nonferrous alloys[END_REF] one can use the activation energy for grain boundary self diffusion in a-Ti (Q gb 5187 kJ mol 21 ) [START_REF] Herzig | Titanium tracer diffusion in grain boundaries of a-Ti, a 2 -Ti 3 Al, and c-TiAl and in a 2 /c interphase boundaries[END_REF] to estimate the neck size ratio as a function of the sintering time, sintering temperature and particle diameter. Substituting the onset temperatures of 893 K for the as received powder (D5120 mm) and 613 K for the 4 h ball milled sample (D525 mm) with the same sintering time (e.g. 1 s at 893 K for the as received powder and at 613 K for the 4 h ball milled powder) into equation ( 3), one can find that the ratio of (x/D) for the as received powder to (x/D) for the 4 h ball milled powder is 185. In other words, if the shrinkage of the 4 h ball milled powder at the initial stage of sintering depends only on the mass transport from the interparticle boundary area to the neck zone, the neck size ratio of the 4 h ball milled sample would be about two orders of magnitude smaller than that of the as received powder sample. Since the neck size ratio of the 4 h ball milled sample at 613 K is similar to that of the as received powder sample at 893 K (as evidenced by the similar shrinkage at 893 and 613 K for the as received and 4 h ball milled powders respectively, shown in Fig. 6), one can conclude that neck growth for the 4 h ball milled sample does not rely only on the mass transport from the interparticle boundary area to the neck zone. The mass transport from the particle interior to the neck zone, due to substantial nanograin boundaries inside each particle, must also contribute to the neck growth and densification of the 4 h ball milled sample. Therefore, high energy ball milling has resulted in two beneficial effects on sintering of Ti-6-4. These are reduced particle sizes and the formation of nanostructure within each particle.

It should be pointed out that high energy ball milling can also activate the surface of particles and increase their reactivity. [START_REF] Volante | Reactivity induced by grinding in silicon nitride[END_REF][START_REF] Lin | Review of the phase transformation and synthesis of inorganic solids obtained by mechanical treatment (mechanochemical reactions)[END_REF][START_REF] Yu | Butyagin: 'Mechanochemical reactions of solids with gases[END_REF][START_REF] Ren | Synthesis of nanostructured silicon carbide through integrated mechanical and thermal activation process[END_REF][START_REF] Shaw | Mechanically enhanced reactivity of Si for the formation of Si 3 N 4 composites[END_REF] Thus, one may argue that high energy ball milling also leads to enhanced surface diffusion due to the activated surface. However, it is well known that mass transport through surface diffusion does not result in densification of a powder compact. [START_REF] Greshovich | Sintering of covalent solids[END_REF] Thus, the contribution of enhanced surface diffusion to densification, if any, should be negligible. Therefore, the enhanced densification observed for the 4 h ball milled sample should be attributed to particle size reduction and nanograin formation, as discussed above.

Densification enhancement through SPS

The present study also reveals that the densification behaviour of Ti-6-4 can be improved immensely via SPS. As shown in Table 2, the as received powder only leads to in a porous body after sintering at 1250uC for 2 h via RHS. In sharp contrast, a dense body can be formed via SPS during continuous heating up to 860uC with a heating rate of 100uC min [START_REF] Belyakov | Grain refinement in copper under large strain deformation[END_REF] . For the 4 h ball milled powder, the enhancement is equally impressive. A sintered body of 97% dense can be obtained via RHS at 1250uC for 2 h. However, a sintered body of .99% dense is obtained by continuous heating up to 740uC only for SPS. This represents a reduction of more than 500uC in the sintering temperature when RHS is replaced by SPS. Furthermore, it is noted that by adding a short holding time at a preselected temperature the densification temperature of SPS can be further reduced. For example, continuous heating up to 600uC with a holding time of 5 min via SPS has resulted in a sintered body of 96% dense, indicating that with a finite holding time the completion temperature for densification via SPS can be reduced by as much as 650uC from 1250uC for RHS.

The enhanced densification properties exhibited by SPS could be ascribed to two mechanisms. First, the uniaxial pressure of 50 MPa can force particle rearrangement and the breakdown of agglomerates as well as inducing plastic deformation at high temperatures. The latter can be supported by the fact that Ti-6-4 can plastically deform under 50 MPa with a strain rate of 10 23 s 21 at 775uC. [START_REF] Comley | Multi-rate superplastic forming of fine grain Ti-6Al-4V titanium alloy[END_REF] In addition, it should be noted that the enhancement in densification is not due to the uniaxial pressure of 50 MPa only. The intrinsic joule effect derived from the pulsed current during SPS also plays an important role. A previous study 8 on the effect of uniaxial pressure using experiments and finite element modelling has revealed that applying 60 MPa with a holding time 10 min at 750uC only results in a Ti-6-4 body with ,80% dense. In the present study, a fully dense body is obtained by continuous heating up to 740uC with a heating rate of 100uC min 21 for SPS. Clearly, SPS has led to a far better result than the case of applying 60 MPa at 750uC for 10 min. Thus, the intrinsic joule effect derived from the pulsed current during SPS must also play a role in enhancing densification. Since Ti-6-4 is a conducting material, a fraction of the pulsed current can flow through the powder compact resulting in heating by intrinsic joule effect. This effect is particularly important at the contact point between particles where the current density is concentrated, resulting in an increase in the local temperature and the enhanced diffusion. [START_REF] Song | Neck formation and self-adjusting mechanism of neck growth of conducting powders in spark plasma sintering[END_REF][START_REF] Chaim | s: 'Sintering and densification of nanocrystalline ceramic oxide powders: a review[END_REF][START_REF] Orru | Consolidation/synthesis of materials by electric current activated/ assisted sintering[END_REF] In addition, the applied current can enhance sintering via non-thermal effects, such as enhanced defect mobility, point defect generation and electromigration. [START_REF] Munir | Electric current activation of sintering: a review of the pulsed electric current sintering process[END_REF] It is worth pointing out that the improved densification behaviour of SPS over HP has also been reported for commercially pure Ti powder. [START_REF] Eriksson | Fast densification and deformation of titanium powder[END_REF] It has been shown that SPS can result in dense Ti bodies at 730uC, while the same Ti powder would require 950uC to become dense bodies by using HP. [START_REF] Eriksson | Fast densification and deformation of titanium powder[END_REF] Another study [START_REF] Zadra | Microstructure and mechanical properties of cp-titanium produced by spark plasma sintering[END_REF] shows that commercial Ti powder (,45 mm in size) can reach 99% density at 800uC using SPS, again demonstrating that SPS can lead to low temperature densification of Ti powder, while this is not achievable through HP and RHS.

Microwave sintering behaviour

Unlike SPS, MWS, which relies on microwave energy to stimulate solid state diffusion for densification, exhibits similar sintering properties for Ti-6-4 as RHS. In MWS, the porosity of the green body allows penetration of the microwave fields into the metallic compact. These fields induce eddy currents on particle surfaces, resulting into heat generation. [START_REF] Carr | Far-infrared properties of inhomogeneous materials[END_REF] Thus, fully dense metallic bodies like Ti-6-4 are relatively difficult to attain via MWS. Nevertheless, slightly improved densification behaviour over RHS has been observed, as evidenced by 98% density at the centre of the as received powder sample sintered at 1250uC for 0?5 h (Table 2). However, microwave sintered samples show a gradient in density from the centre of the pellet to the edge. This phenomenon stems from the microwave interaction with the sample and cooler chamber surfaces causing heat emanating from the centre of the sample to flow outward. The gradient in heating within the pellet causes the sintered body to show a large amount of porosity near the edges, with nearly full density at the core where the thermally driven diffusion process is more prominent. This is different from RHS that involves heating from the outside of the pellet. In spite of different heating mechanisms, RHS and MWS exhibit similar sintering effectiveness for Ti-6-4, as revealed in this study.

Conclusions

In summary, the present study has revealed that high energy ball milling of Ti-6-4 can greatly enhance sintering properties of Ti-6-4 powder via two mechanisms. One is the reduction of particle sizes and the other is the formation of nanostructure within each particle. The former reduces the diffusion distance for densification, whereas the latter introduces an additional densification mechanism allowing mass transport from the interior of the particle to the neck zone. Together, these two effects can reduce the onset temperature for densification by y300uC. SPS exhibits substantial advantages over RHS and MWS, achieving nearly full theoretical density in less than 5 min of sintering at 600uC. This is well below the critical temperature of 1000uC that must be avoided for co-sintering of Ti-Al-V and HA composites. Thus, SPS is a viable option for the functionally graded orthopaedic implants. The reduction in the densification temperature achieved via SPS over RHS by as much as 650uC is attributed to particle sliding and plastic deformation at high temperatures due to the presence of the applied pressure (50 MPa) and the intrinsic joule effect that results in an increase in the local temperature at the contact point between particles.

4 a

 4 average particle size (via SEM image analysis) and b average crystallite size [via XRD analysis of (002) reflection] of Ti-6Al-4V powder ball milled for 4 h as function of PCA concentration a as received powder sintered at 1250uC for 2 h via RHS; b 4 h ball milled powder sintered at 1250uC for 2 h via RHS; c as received powder sintered via SPS with completion of shrinkage at 860uC during continuous heating; d core region of 4 h ball milled powder sintered at 1250uC for 30 min via MWS 5 Polished surfaces of sintered pellets

Table 1 X

 1 -ray diffraction analysis of crystallite sizes as function of milling duration

	Milling	(101) crystallite	(002) crystallite
	duration/h	size/nm	size/nm
	0 (as received)	.100	.100
	1	51	77
	2	53	76
	3	44	21
	4	35	15

3 Dark field TEM image of Ti-6-4 powder ball milled for 4 h with presence of 4 wt-% stearic acid

Table 2

 2 Density values of Ti-6-4 bodies sintered via various methods and conditions* Punch displacement curves during SPS with heating rate of 100uC min 21 ; arrows point to onset temperature for shrinkage during continuous heating for powder compacts indicated

	Sample condition

*All samples are made from the 4 h ball milled Ti-6-4 with 4 wt-% stearic acid unless indicated otherwise. 6

Acknowledgement

This work was supported by the US National Science Foundation through contract no. CBET-0930365.


Alberto García-Durán

Antoine Bordes
email: bordesan@utc.fr

Nicolas Usunier
email: nusunier@utc.fr

E↵ective Blending of Two and Three-way Interactions for Modeling Multi-relational Data

Keywords:

Much work has been recently proposed to model relational data, especially in the multi-relational case, where di↵erent kinds of relationships are used to connect the various data entities. Previous attempts either consist of powerful systems with high capacity to model complex connectivity patterns, which unfortunately usually end up overfitting on rare relationships, or in approaches that trade capacity for simplicity in order to fairly model all relationships, frequent or not. In this paper, we propose a happy medium obtained by complementing a high-capacity model with a simpler one, both pre-trained separately and jointly finetuned. We show that our approach outperforms existing models on different types of relationships, and achieves state-of-the-art results on two benchmarks of the literature.

Introduction

Predicting new links in multi-relational data plays a key role in many areas and hence triggers a growing body of work. Multi-relational data are defined as directed graphs whose nodes correspond to entities and edges are in the form of triples (head, label, tail) (denoted (h, `, t)), each of which indicates that there exists a relationship of name label between the entities head and tail. Figure 1 displays an example of such data with six entities (Jane, Patti, John, Mom, Miami and Austin) and two relationships (born in and child of). Link prediction in this context consists in attempting to create new connections between entities and to determine their type; this is crucial in social networks, knowledge management or recommender systems to name a few.

Performing predictions in multi-relational data is complex because of their heterogeneous nature. Any such data can equivalently be seen as a set of directed graphs that share the same nodes but that usually present drastically di↵erent properties in terms of sparsity or connectivity. As illustration, we can look at some statistics of a subset of the knowledge base Freebase, named FB15k in the following, which we use for our experiments. This data set contains ⇠15k entities connected by ⇠1.5k relationships to form a graph of ⇠500k triples. Even if FB15k is just a small sample, it is likely that its characteristics are shared with most real-world multi-relational data, but at a di↵erent scale. The relationships of FB15k have a mean number of triples of ⇠400 and a median of 21: a vast number of relationships appear in very few triples, while others provide a large majority of the connections. Besides, roughly 25% of the relationships are of type 1-to-1, that is a head is connected to at most one tail (think of a spouse of link for instance), but on the opposite 25% of the relationships are of type Many-to-Many, that is, multiple head can be linked to a tail and vice-versa (for instance, a like product link). Creating new connections for Many-to-Many relationships can be possible by relying on several existing links of the same kind, whereas in the 1-to-1 case, the only way to be able to generalize is to count on the other relationships, especially if the relationship of interest happens to be rare.

In contrast to (pseudo-) symbolic approaches for link prediction based on Markov-logic networks [START_REF] Kok | Statistical predicate invention[END_REF] or random walks [START_REF] Lao | Random walk inference and learning in a large scale knowledge base[END_REF], most recent e↵ort towards solving this problem concern latent factor models (e.g. [START_REF] Paccanaro | Learning distributed representations of concepts using linear relational embedding[END_REF][START_REF] Kemp | Learning systems of concepts with an infinite relational model[END_REF][START_REF] Sutskever | Modelling relational data using bayesian clustered tensor factorization[END_REF][START_REF] Miller | Nonparametric latent feature models for link prediction[END_REF][START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF][START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF][START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF]) because they tend to scale better and to be more robust w.r.t. the heterogeneity of multi-relational data. These models represent entities with latent factors (usually low-dimensional vectors or embeddings) and relationships as operators destined to combine those factors. Operators and latent factors are trained to fit the data using reconstruction [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF], clustering [START_REF] Sutskever | Modelling relational data using bayesian clustered tensor factorization[END_REF] or ranking costs [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF]. The multi-relational quality of the data is modeled through the sharing of the latent factors across relationships which grants a transfer of information from one relationship to another; operators are normally specific to each relationships, except in [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF] where some parameters are shared among relationships.

Learning these latent factor models can be seen as a kind of multitask training, with one task per relationship: one model is fitted for each task and some parameters are shared across tasks. All existing latent factor approaches define the same formulation for each task. This is natural since hand-crafting a particular model for each relationship seems daunting since there can be several thousands of them. However, as all relationships have very di↵erent properties, this also induces important drawbacks.

The standard modeling assumption is to consider 3-way interactions between head, label and tail, i.e. to consider that they are all interdependent: the validity of a triple (h, `, t) depends jointly on h, `and t. This generally results in models where entities are represented by vectors and relationships by matrices. An exception is Parafac [START_REF] Harshman | Parafac: parallel factor analysis[END_REF][START_REF] Franz | Triplerank: Ranking semantic web data by tensor decomposition[END_REF] that models multi-relational data as a binary tensor and factorizes it as a sum of rank one tensors. Other tensor factorization methods derived from Tucker decompositions [START_REF] Tucker | Some mathematical notes on three-mode factor analysis[END_REF] or Dedicom [?] like RESCAL [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF][START_REF] Nickel | Factorizing yago: scalable machine learning for linked data[END_REF] end up with vectorial latent factors for entities and low rank matrices for relationships. This formulation is also shared by many non-parametric Bayesian approaches such as extensions of the Stochastic Block Models [START_REF] Kemp | Learning systems of concepts with an infinite relational model[END_REF][START_REF] Miller | Nonparametric latent feature models for link prediction[END_REF][START_REF] Zhu | Max-margin nonparametric latent feature models for link prediction[END_REF], or joint entities and relationships clustering approaches [START_REF] Sutskever | Modelling relational data using bayesian clustered tensor factorization[END_REF], which end up modeling the data with similar architectures but with drastically di↵erent training and inference procedures. Linear Relational Embeddings [START_REF] Paccanaro | Learning distributed representations of concepts using linear relational embedding[END_REF] were proposed as a 3-way model trained using a regression loss: the vector representing t is learned so that it can be reconstructed using the embedding of h and the matrix encoding `, if (h, `, t) is valid. This work was later followed by the Structured Embeddings model (SE) [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF] where the regression loss was replaced by a ranking loss for learning embeddings of entities.

Three-way models are appropriate for multi-relational data since they can potentially represent any kind of interaction. However, this comes at a price since they have to allocate the same large capacity to model each relationship. While this is beneficial for frequent ones, this can be problematic for rare relationships and cause major overfitting. Hence, one must control the capacity either by regularizing, which is not straightforward since di↵erent penalties might need to be used for each relationship, or by reducing the expressivity of the model. The second option is implemented in two recent embedding models, SME [START_REF] Bordes | A semantic matching energy function for learning with multi-relational data[END_REF] and TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], that choose to represent multi-relational data as combination of 2-way interactions. The idea is to assume that the validity of a triple (h, `, t) is governed by binary interaction terms (h, t), (t, `) and (h, `), which allows to represent a relationship as a vector as with the other entities. Such a model, TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], outperforms most 3-way approaches on various data sets, which indicates that less expressivity can be beneficial overall for a whole database, especially for relationships where the number of training triples is reduced. However, by design, methods based on 2-way interactions are limited and can not hope to represent all kinds of relations between entities.

In this paper, we introduce Tatec (for Two And Three-way Embeddings Combination), a latent factor model which successfully combines well-controlled 2way interactions with high-capacity 3-way ones. We demonstrate in the following that our proposal is a generalization of many previous methods. Unlike recent work like the Latent Factor Model (LFM) of [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF] or the Neural Tensor Model (NTN) of [START_REF] Socher | Reasoning With Neural Tensor Networks For Knowledge Base Completion[END_REF] that proposed similar joint formulations mixing several interaction terms, we deliberately choose not to share parameters between the 2-and 3-way interaction components of our model. Previous work use the same embeddings for entities in all terms of their models, which seems to be a sound and natural idea to obtain the possible latent representations. However, we discov-ered that 2-and 3-way models do not respond to the same data patterns, and that they do not necessarily encode the same kind of information in the embeddings: sharing them among interaction terms can hence be detrimental because it can make some features to be missed by the embeddings or to be destroyed. On the contrary, we explain in the following that using di↵erent embeddings for both terms allows to detect distinct kinds of patterns in the data. To ensure that Tatec satisfactorily collects both kinds of patterns, we pre-train separately a 2-way and a 3-way model, which are then combined and jointly fine-tuned in a second stage. We show in various experiments that this combination process is powerful since it allows to jointly enjoy both nice properties of 2 and of 3-way interactions. As a result, Tatec is more robust than previous work w.r.t. the number of training samples and the type of relationships. It consistently outperforms most models in all conditions and achieves state-of-the-art results on two benchmarks from the literature, FB15k [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF] and SVO [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF].

This paper is organized as follows. Section 2 introduces our formulation and our training procedure, divided in a pre-training phase followed by a fine-tuning step both conducted via stochastic gradient descent. We justify our particular modeling choices in Section 3. Finally, we display and discuss our experimental results on FB15k, SVO and a synthetic dataset in Section 4.

Model

We now describe our model, and the training algorithm associated to it. The motivation underlying our parameterization is given in the next section.

Scoring Function

The data S is a set of relations between entities in a fixed set of entities in E = {e 1 , ..., e E }. Relations are represented as triples (h, `, t) where the head h and the tail t are indexes of entities (i.e. h, t 2 [[E]] = {1, ..., E}), and the label `is the index of a relationship in L = {l 1 , ..., l L }, which defines the type of the relation between the entities e h and e t . Our goal is to learn a discriminant scoring function on the set of all possible triples E ⇥ L ⇥ E so that the triples which represent likely relations receive higher scores than triples that represent unlikely relations. Our proposed model, Tatec, learns embeddings of entities in low dimensional vector spaces, and parameters of operators on R d ⇥ R d , most of them being associated to single relationships. More precisely, the score given by Tatec to a triple (h, `, t), denoted by s(h, `, t), is defined as:

s(h, `, t) = s 1 (h, `, t) + s 2 (h, `, t) (1)
where s 1 and s 2 have the following form:

(B) Bigrams or the 2-way interactions terms:

s 1 (h, `, t) = ⌦ r 1 e h 1 ↵ + ⌦ r 2 e t 1 ↵ + ⌦ e h 1 D e t 1 ↵
, where e h 1 , e t 1 are embeddings in R d1 of the head and tail entities of (h, `, t) respectively, r 1 and r 2 are vectors in R d1 that depend on the relationship l `, and D is a diagonal matrix that does not depend on the input triple. As a general notation throughout this section, ⌦ . . ↵ is the canonical dot product, and

⌦ x A y ↵ = ⌦
x Ay ↵ where x and y are two vectors in the same space and A is a square matrix of appropriate dimensions. (T) Trigram or the 3-way interactions term:

s 2 (h, `, t) = ⌦ e h 2 R ` e t 2 ↵ , where R `is a matrix of dimensions (d 2 , d 2 )
, and e h 2 and e t 2 are embeddings in R d2 of the head and tail entities respectively. The embeddings of the entities for this term are not the same as for the 2-way term; they can have di↵erent dimensions for instance.

The embedding dimensions d 1 and d 2 are hyperparameters of our model. All other vectors and matrices are learned without any additional parameter sharing.

The 2-way interactions term of the model is similar to that of [START_REF] Bordes | A semantic matching energy function for learning with multi-relational data[END_REF], but slightly more general because it does not contain any constraint between the relationdependent vectors r 1 and r 2. It can also be seen as a relaxation of the translation model of [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], which is the special case where r 1 = r 2, D is the identity matrix, and the 2-norm of the entities embeddings are constrained to equal 1.

The 3-way term corresponds exactly to the model used by the collective factorization method RESCAL [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF], and we chose it for its high expressivity on complex relationships. Indeed, as we said earlier in the introduction, 3-way models can basically represent any kind of interaction among entities. The usage of combinations of 2-way and 3-way terms has already been used in [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF][START_REF] Socher | Reasoning With Neural Tensor Networks For Knowledge Base Completion[END_REF], but, besides a di↵erent parameterization, Tatec contrasts with them by the choice of not sharing the embeddings between the two models. In LFM [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF], constraints were imposed on the relation-dependent matrix of the 3-way terms (low rank in a limited basis of rank-one matrices), the relation vectors r 1 and r 2 were constrained to be a constant linear function of the matrix (D = 0 in their work). These global constraints severely limited the expressivity of the 3-way model, and act as powerful regularization in that respect. However, their global constraints also reduces the expressivity of the 2-way model, which, as we explain in Section 3, should be left with maximum degrees of freedom. The fact that we do not share any parameter between relations is similar to NTN [START_REF] Socher | Reasoning With Neural Tensor Networks For Knowledge Base Completion[END_REF]. Our overall scoring function is similar to this model with a single layer, with the fundamental di↵erence that we use di↵erent embedding spaces and do not use any non-linear transfer function, which results in a facilitated training (the gradients have a larger magnitude, for instance).

Training

Training is carried out using gradient descent, with a ranking criterion as training objective. The optimization approach is similar to the one used for TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], but the models are very di↵erent. Our loss function takes training triples, and tries to give them higher scores than to corrupted versions, where the corruption consists in either replacing the head or the tail of each triple by a random entity. Since we are learning with positive examples only, this kind of criterion implements the prior knowledge that unobserved triples are likely to be invalid. Such corruption approaches are widely used when learning embeddings of knowledge bases [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF][START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF] or words in the context of language models [START_REF] Collobert | Natural language processing (almost) from scratch[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF].

Given a training triple (h, `, t), the set of possible corrupted triples, denoted by C(h, `, t), is defined as:

C(h, `, t) = {(h 0 , `, t 0 ) 2 [[E]] ⇥ {`} ⇥ [[E]]|h 0 = h or t 0 = t} .
The loss function we optimize is then:

X (h,`,t)2S X (h 0 ,`,t 0 )2C(h,`,t) max(0, 1 s(h, `, t) + s(h 0 , `, t 0 )) ( 2
)
Stochastic gradient is performed in a minibatch setting. The dataset S is shu✏ed at each epoch, minibatches of m << |S| training triples are selected, and, for each one of them, a corresponding mini-batch of corrupted triples is sampled at random to create ranking pairs. We only create a single corrupted triple per training sample. The learning rate of the stochastic gradient is kept constant, and optimization is stopped using early stopping on a validation set. Several regularization schemes were tried during training: either by forcing the entity embeddings to have, at most, a 2-norm of r (for radius), or by adding 2norm regularization inside the sum of (2) of the form k x k 2 2 for each parameter x (relation vectors and diagonal matrix in the 2-way term or relation matrix in the 3-way term) that appears in max(0, 1 s(h, `, t) + s(h 0 , `, t 0 )). The first kind of regularization is carried out after each minibatch by projecting the entities into the 2-norm ball of radius r.

A random initialization of the scoring function (1) can lead to a poor local minimum, but can also prevent the di↵erent embeddings used in the 2-and 3way terms to capture di↵erent patterns as we expect (see next section). Hence, following many previous work on deep architecture, we decided to first pre-train separately the bigrams and trigram terms on the training set. When their pretraining is over (i.e. stopped using early stopping on a validation set), we initialize the parameter of the full score (1) using these learned weights and fine-tuned it by running stochastic gradient descent on the training set with the full model.

Interpretation and Motivation of the Model

This section discusses the motivations underlying the parameterization of Tatec, and in particular our choice of 2-way model to complement the 3-way term.

2-Way Interactions as one Fiber Biases

It is common in regression, classification or collaborative filtering to add biases (also called o↵sets or intercepts) to the model. For instance, a critical step of the best-performing techniques of the Netflix prize was to add user and item biases, i.e. to approximate a user-rating R ui according to (see e.g. [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]):

R ui ⇡ ⌦ P u Q i ↵ + ↵ u + i + µ (3)
where P 2 R U ⇥k , with each row P u containing the k-dimensional embedding of the user (U is the number of users), Q 2 R I⇥k containing the embeddings of the I items, ↵ u 2 R a bias only depending on a user and i 2 R a bias only depending on an item (µ is a constant that we do not consider further on). The 2-way + 3-way interactions model we propose can be seen as the 3mode tensor version of this "biased" version of matrix factorization: the trigram term (T) is the collective matrix factorization parametrization of the RESCAL algorithm [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF] and plays a role analogous to the term

⌦ P u Q i ↵
of the matrix factorization model for collaborative filtering [START_REF] Bordes | A semantic matching energy function for learning with multi-relational data[END_REF]. The bigram term (B) then plays the role of biases for each fiber of the tensor,1 i.e.

s 1 (h, `, t) ⇡ B 1 l,h + B 2 l,t + B 3 h,t (4)
and thus is the analogous for tensors to the term ↵ u + i in the matrix factorization model [START_REF] Bordes | A semantic matching energy function for learning with multi-relational data[END_REF]. The exact form of s 1 (h, `, t) given in (B) corresponds to a specific form of collective factorization of the fiber-wise bias matrices

B 1 = h B 1 l,h i l2[[L]],h2[[E]]
, B 2 and B 3 of Equation 4. We do not exactly learn one bias by fiber because many such fibers have very little data, while, as we argue in the following, the specific form of collective factorization we propose in (B) should allow to share relevant information between di↵erent biases.

The Need for Multiple Embeddings

A key feature of Tatec is to use di↵erent embedding spaces for the 2-way and 3-way terms, while existing approaches that have both types of interactions use the same embedding space [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF][START_REF] Socher | Reasoning With Neural Tensor Networks For Knowledge Base Completion[END_REF]. We motivate this choice in this section.

It is important to notice that biases in the matrix factorization model (3), or the bigram term in the overall scoring function [START_REF] Bader | Temporal analysis of social networks using three-way dedicom[END_REF] do not a↵ect the model expressiveness, and in particular do not a↵ect the main modeling assumptions that embeddings should have low rank. The user/item-biases in (3) only boil down to adding two rank-1 matrices ↵1 T and 1 T to the factorization model. Since the rank of the matrix is a hyperparameter, one may simply add 2 to this hyperparameter and get a slightly larger expressiveness than before, with reasonably little impact since the increase in rank would remain small w.r.t. its original value (which is usually 50 or 100 for large collaborative filtering data sets). The critical feature of these biases in collaborative filtering is how they interfere with capacity control terms other than the rank, namely the 2-norm regularization: in [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF] for instance, all terms of (3) are trained using a squared error as a measure of approximation and regularized by

⇣ k P u k 2 2 + k Q i k 2 2 + ↵ 2 u + 2 i ⌘
, where > 0 is the regularization factor. This kind of regularization is a weighted trace norm regularization [START_REF] Salakhutdinov | Collaborative filtering in a non-uniform world: Learning with the weighted trace norm[END_REF] on PQ T . Leaving aside the "weighted" part, the idea is that at convergence, the quantity ⇣ P

u k P u k 2 2 + P i k Q i k 2 2
⌘ is equal to 2 times the sum of the singular values of the matrix PQ T . However, k ↵ k 2 2 , which is the regularization applied to user biases, is not 2 times the singular value of the rank-one matrix ↵1 T , which is equal to p Ik ↵ k 2 , and can be much larger than k ↵ k 2 2 . Thus, if the pattern user+item biases exists in the data, but very weakly because it is hidden by stronger factors, it will be less regularized than others and the model should be able to capture it. Biases, which are allowed to fit the data more than other factors, o↵er the opportunity of relaxing the control of capacity on some parts of the model but this translates into gains if the patterns that they capture are indeed useful patterns for generalization. Otherwise, this ends up relaxing the capacity to lead to more overfitting.

Our ↵ is directly in an appropriate quadratic form. Thus, the only way to gain from the addition of bigram terms is to ensure that they can capture useful patterns, but also that capacity control on these terms is less strict than on the trigram terms. In tensor factorization models, and especially 3-way interaction models with parameterizations such as (T), capacity control through the regularization of individual parameters is still not well understood, and as it turns out in experiments is more detrimental than e↵ective. The only e↵ective parameter is the admissible rank of the embeddings, which leads to the conclusion that the bigram term can be really useful in addition to the trigram term if higher-dimensional embeddings are used. Hence, in absence of clear and concrete way of e↵ectively controlling the capacity of the trigram term, we believe that di↵erent embedding spaces should be used.

2-Way Interactions as Entity Types+Similarity

Having a part of the model that is less expressive, but less regularized than the other part is only useful if the patterns it can learn are meaningful for the prediction task at hand. In this section, we give the motivation for our 2-way interactions term for the task of modeling multi-relational data.

Most relationships in multi-relational data, and in knowledge bases like FB15k in particular, are strongly typed, in the sense that only well-defined and specific subsets of entities can be either heads or tails of selected relationships. For instance, a relationship like capital of expects a (big) city as head and a country as tail for any valid relation. Large knowledge bases have huge amounts of entities, but those belong to many di↵erent types. Identifying the expected types of head and tail entities of relationships, with an appropriate granularity of types (e.g. person or artist or writer), is likely to filter out 95% of the entity set during prediction. The exact form of the first two terms 2-way interaction model (B), which corresponds to a low-rank factorization of the per bias matrices (head, label) and (tail, label) in which head and tail entities have the same embeddings, is based on the assumption that the types of entities can be predicted based on few (learned) features, and these features are the same for predicting head-types as for predicting tail-types. As such, it is natural to share the entities embeddings in the first two terms of (B).

⌦ r 1 e h 1 ↵ + ⌦ r 2 e t 1 ↵ of the
The last term, ⌦ e h 1 D e t 1 ↵
, is intended to account for a global similarity between entities. For instance, predicting the capital of France can easily be performed correctly by saying that we search for the city with strongest overall connections with France in the knowledge base. A country and a city may be strongly linked through their geographical positions, independent of their respective types. The diagonal matrix D allows to re-weight features of the embedding space to account for the fact that the features used to describe types may not be the same as those that can describe the similarity between objects of di↵erent types. The use of a diagonal matrix is strictly equivalent to using a general symmetric matrix in place of D. 2 The reason for using a symmetric matrix comes from the intuition that the direction of many relationships is arbitrary (i.e. the choice between having triples "Paris is capital of France" rather than "France has capital Paris"), and the model should be invariant under arbitrary inversions of the directions of the relationships (in the case of an inversion of direction, the relations vectors r 1 and r 2 are swapped, but all other parameters are una↵ected). For tasks in which such invariance is not desirable, the diagonal matrix could be replaced by an arbitrary matrix.

Experiments

This section presents a series of experiments that we conducted to compare Tatec to previous models from the literature on two benchmarks, FB15k, a subset of Freebase [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], and SVO, a database of nouns connected by verbs and introduced in [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF], as well an artificial data set that we created (Family). The statistics of these data sets are given in Table 1. 2 We can see the equivalence by taking the eigenvalue decomposition of a symmetric D: apply the change of basis to the embeddings to keep only the diagonal part ofD in the term

⌦ e h 1 D e t 1 ↵
, and apply the reverse transformation to the vectors r 1 and r 2. Note that since rotations preserve euclidian distances, the equivalence still holds under 2-norm regularization of the embeddings.

Table 2. Baselines. Rules used by our symbolic baselines, an upper and a lower one, to predict a tail given a head and a label on the Family data set. Similar symmetric rules have been used to predict a head given a tail and a label for these relations.

Relationship Baseline

Rules for predicting a tail given a head cousin of Lower Any entity of the same layer as the head of the families where the head has a cousin.

Upper

Any entity whose parent is a sibling(-in-law) of the parents of the head.

sibling of

Lower Any entitiy of the same layer as the head of the families where the head has a sibling. Upper Any entity whose parent is the same as the parents of head.

married to

Lower Any entity of the same layer as the head whose marriage would not be forbidden with.

Upper Entity who has children in common with the head.

parent of Lower

Any entity of the lower layer of head of the families where head has a child.

Upper

Any entity being children of the spouse of head.

uncle of Lower

Any entity of the lower layer of head of the families where head has a niece/nephew.

Upper

Any entity being child of a sibling/sibling a law of head or the spouse of head.

For evaluation, we use a ranking procedure as in [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF][START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF]. For each test triplet, the head is removed and replaced by each of the entities of the dictionary in turn. Scores of those corrupted triplets are computed by the models and sorted by descending order and the rank of the correct entity is stored. This whole procedure is repeated when removing the tail instead or the head. We report the mean of those predicted ranks and the hits@10, i.e. the proportion of correct entities ranked in the top 10.

Synthetic Data

"Family" Data Set This database contains triples expressing family relationships among the members of 5 families along 6 generations, each family being organized in a layered tree structure where each layer refers to a generation. These 5 families are first created independent of each other by recursively sampling the number of children of each node of a layer using the normal distribution N (3, 1.5) to create a new generation. Then, families are connected by marriage links between two members. We use pre-defined rules to avoid non-typical situations, like marriages between cousins and brothers, as well as marriages between two members of di↵erent generations. To control the number of connections between families, only i 1 marriages are allowed in the generation i.

After all families are created, we build a multi-relational data set by collecting the pairs of entities connected using the following relationships: cousin of, married to, parent of, sibling of and uncle of. We end up with a data set with 721 entities, 5 relationships and ⇠9k triples which is later split into training, validation and test sets. There is a large variation in the numbers of triples: there are only 30 examples with married to but 5, 060 with cousin of. Family is a realistic and challenging study case, but for which we know the underlying semantics.

Baselines We created two symbolic baselines since we know the underlying rules used to generate the data. These baselines can be used to assess what kind of pattern is caught by our model. Our first baseline, Lower, uses simplistic rules in order to find a set of potential candidates among all entities given a label and either a head or a tail as input. Our second baseline, Upper, returns candidate answers using a much more refined knowledge about the underlying semantics of the relationships, such as, if John and Mary have children together then they are likely to be married. We made sure than, for any triple from the data set, the correct missing element given a label and either a head or a tail as input, is always contained in the sets returned by Lower and Upper (the second being included in the first one). Then, for each test triple, we computed the mean rank of the answers given by the baselines, by sorting the elements of the returned candidate sets by the number of occurrences of each entity in the training set. It is worth noting that the entities of the Upper set always form triples expressing true knowledge. The rules used to defined both baselines are given in Table 2.

Implementation To pre-train our Bigrams and Trigram models we selected the learning rate for the stochastic gradient descent among {0.1, 0.01, 0.001, 0.0001}, and the embedding dimension among {5, 10, 20}. The margin was fixed to 1, and the radius determining the maximim 2-norm of the entity embeddings was validated among {1, 10, 100}. For fine-tuning Tatec, the learning rate was selected among the same values as above, independent of the values chosen for pretraining. For all three models, training was limited to a maximum of 500 epochs, and we used the mean rank on the validation set (computed every 50 epochs) as stopping criterion.

Results Table 3 presents our results. Tatec outperforms the best performance of Bigrams and Trigram counterparts for each relationship, indicating that the biases brought to the 3-way model by the bigram terms are indeed beneficial to detect complementary patterns in the data. As a result, Tatec gets a really close performance to that of the upper baseline, indicating that it can perform relatively sophisticated inference, as long as the amount of data is su cient. Indeed, all embedding-based models fail completely on the married to relationship: with very few training samples, those models cannot learn any meaningful information that would grant non-trivial predictions for this complex relationship.

Encoding Freebase

Freebase Data Set (FB15k) Freebase is a huge and growing database of general facts; there are currently around 1.2 billion triples and more than 80 million entities. We used FB15k, a data set based on Freebase introduced in [4], This small data set is based on a subset of entities that are also present in the Wikilinks database 3 and that also have at least 100 mentions in Freebase (for both entities and relationships). This results in 592, 213 triples with 14, 951 entities and 1, 345 relationship which were randomized and split.

Baselines We compare Tatec with various models from previous work: RESCAL [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF], LFM [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF] , SE [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF] , SME [START_REF] Bordes | A semantic matching energy function for learning with multi-relational data[END_REF] and TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF]. Results were extracted from [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF] since we follow the same experimental protocol here. We also include comparisons with NTN [START_REF] Socher | Reasoning With Neural Tensor Networks For Knowledge Base Completion[END_REF]. For this method, we ran experiments with the code provided by the authors. The embedding dimension was selected between {25, 50} and the number of slices of the tensor layer was fixed to 2 for computational considerations. We chose the regularization hyperparameter among {0, 0.1, 0.01, 0.001} and tanh as nonlinear element-wise function. The negative triplets were generated as before in a proportion of 10 negative to 1 positive triple. The model ran for 700 iterations and was validated every 50 iterations. Besides Bigrams, Trigram and Tatec, we also propose the performance of 3 other versions of Tatec:

-Tatec-no-pretrain: Tatec without pre-training s 1 (h, `, t) and s 2 (h, `, t).

-Tatec-shared: Tatec but sharing the embeddings between s 1 (h, `, t) and s 2 (h, `, t) and without pre-training. -Tatec-linear-comb: this version simply combines the bigram and trigram terms using a linear combination, without jointly fine-tuning their parameters. The score is hence defined as follows: The combination weights ì depend on the relationship and are learned by optimizing the ranking loss defined in (2) using L-BFGS, with an additional quadratic penalization term,

s(h, `, t) = 1⌦ r 1 e h 1 ↵ + 2⌦ r 2 e t 1 ↵ + 3⌦ e h 1 D
P k || k || 2 2 k +✏ , subject to P k k = .
Training is carried out in an iterative way, by alternating optimization of parameters via L-BFGS, and update of parameters using

⇤ i = || i ||2 P i || i ||2
, until some stopping criterion is reached. The parameters are initialized to 1 and the value is validated among {0.1, 1, 10, 100, 250, 500, 1000}. The intuition behind this particular penalization for the s is that it is equivalent to a LASSO penalization [START_REF] Grandvalet | Least absolute shrinkage is equivalent to quadratic penalization[END_REF] and our initial idea was to enforce sparsity among parameters. However we found experimentally that the best performance was obtained with a of 250, which does not yield a sparse solution.

Implementation Tatec, and its 3 alternative versions have been trained and validated in the same setting that was used for the Family experiments, except that we chose the embedding dimensions among {25, 50}.

Results Table 4 displays the mean rank and hits@10 for all the aforementioned methods. These results have been computed in a filtered setting as defined in [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF]: to reduce the error introduced by true triples that might be ranked above the target triple in test, all the entities forming existing triples in the train, validation and test sets but the target one are removed from the candidate set of entities to be ranked. This grants a clearer view on ranking performance.

First of all, we can notice that our plain 2-and 3 way models (Bigrams and

Trigram respectively) are performing comparably as other similarly expressive models: Bigrams is better than SME(linear) but worse than TransE, and Trigram performs roughly like SME(bilinear). RESCAL is interesting since it achieves a very poor mean rank but almost the best hits@10 value: we believe that this is due to overfitting. To make it scale on large data sets, RESCAL has to be ran without regularization, this causes a major overfitting on rare relationships and hence a poor mean rank. But, it seems that one can reach a very decent hits@10 nonetheless. Interestingly, Tatec is able to significantly outperform both its con- Tatec outperforms all previous models by a wide margin, especially in hits@10. We also broke down the results by type of relation, classifying each relationship according to the cardinality of their head and tail arguments. A relationship is considered as 1-to-1, 1-to-M, M-to-1 or M-M regarding the variety of arguments head given a tail and vice versa. If the average number of di↵erent heads for the whole set of unique pairs (label, tail) given a relationship is below 1.5 we have considered it as 1, and the same in the other way around. The number of relations classified as 1-to-1, 1-to-M, M-to-1 and M-M is 353, 305, 380 and 307, respectively. The results are displayed in the Table 5. Most results point out that Tatec consistently outperforms all models we compared it with, except for the relations 1-to-M and M-to-M when predicting the tail.

Predicting Verbs

In this last experimental section, we present results of ranking label given head and tail. We do so by working on a verb prediction task, where one has to assign the correct verb given two noun phrases acting subject and direct object.

Subject-Verb-Object Data Set (SVO) This data set was generated by extracting sentences from Wikipedia articles whose syntactic structure is (subject, verb, direct object) and where the verb appears in the WordNet lexicon [START_REF] Miller | WordNet: a Lexical Database for English[END_REF] and where the subject and direct object are noun phrases from WordNet as well. Due to the high number of relations in this data set, this is an interesting benchmark for label prediction.

Baselines We compare Tatec with 3 di↵erent approaches: LFM, Counts and SME(linear). Counts is based on the direct estimation of probabilities of triples (head, label, tail) by using the number of occurrences of pairs (head, label) and (label, tail) in the training set. The results for these models have been extracted from [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF], and we followed the same experimental setting.

Implementation Due to the di↵erent nature of the application, the negative triples have been generated here by replacing the verb of a given positive triple by a random verb. The rest of the experimental setting is identical to the one used for Family and FB15k, but running only 100 epochs and validating every 10 epochs in the pre-training phase, since we found that the models were converging much faster. For Tatec, we even validated every epoch.

Results

Table 6 shows the results for this database. The measure hits@z% indicates the proportion of predictions for which the correct verb is ranked in the top z% of the verb list. The performance of Tatec is also excellent in this case since it outperforms all previous methods on all metrics, including LFM, another model combining 2-and 3-way interactions.

Conclusion

This paper introduced Tatec, a new method for performing link prediction in multi-relational data, which is made of the combination a 2-and 3-way interactions terms. Both terms do not share their embeddings and this, along with a two-phase training (pre-training and fine-tuning), allows for the model to encode complementary information into its parameters. As a result, Tatec outperforms by a wide margin many methods from the literature, some based on 2-way, on 3-way interactions or on both.

Fig. 1 .

 1 Fig. 1. Example of multi-relational data with 6 entities and 2 relationships.

  bigram terms are closely related to the trigram term: the terms ⌦ r 1 e h

	↵
	1 can be added to the trigram term by adding constant features in the entities' embeddings, and and ⌦ r 2 e t 1 ↵ ⌦ e h 1 D e t 1

Table 1 .

 1 Statistics of the data sets used in this paper and extracted from an artificial database, Family, and from two knowledge bases: FB15k and SVO.

	Data set	Family FB15k [4] SVO [9]
	Entities	721	14,951	30,605
	Relationships	5	1,345	4,547
	Training examples	5,748 483,142 1,000,000
	Validation examples 1,935	50,000	50,000
	Test examples	1,955	59,071 250,000

Table 3 .

 3 Synthetic data set. We compare our Bigrams, Trigram and Tatec models in terms of mean rank, with both baselines on the Family dataset.

	Relation cousin of married to parents of sibling of uncle of
	Lower	76	4	25	35	34
	Upper	4	3	7	4	3
	Bigrams	10	102	9	8	13
	Trigram	7	1 6 2	7	5	8
	Tatec	6	6 9	5	4	6

Table 4 .

 4 Link prediction results. We compare Bigrams, Trigram and several version of Tatec with various methods from the literature on the FB15k dataset. Results are displayed in the filtered setting, see the text for more details.

	Interaction Model	Mean Rank Hits@10
	2-way	SME(linear) [3] TransE [4]	154 125	40.8 47.1
		SE [2]	162	39.8
	3-way	SME(bilinear) [3]	158	41.3
		RESCAL [17]	683	44.1
	2 + 3-way	NTN [21] LFM [9]	332 164	27.0 33.1
	2-way	Bigram	133	44.7
	3-way	Trigram	156	42.7
		Tatec-no-pretrain	133	44.7
	2 + 3-way	Tatec-shared-embs Tatec-linear-comb	137 115	45.0 51.7
		Tatec	111	52.6

Table 5 .

 5 Detailed results by category of relationship. We compare our Bigrams, Trigram and Tatec models in terms of Hits@10 (in %) on FB15k in the filtered setting against other models of the literature. (M. stands for Many).

	e t 1	↵	+	4⌦	e h 2 R ` e t 2	↵

Table 6 .

 6 Verb prediction results. We compare our Bigrams, Trigram and Tatec models with baselines from the literature on the SVO dataset. Bigrams and Trigram, which indicates that they can encode complementary information. This is confirmed by the comparison with the baseline 2+3-way models, LFM and NTN. 4 By sharing their embeddings between their 2-and 3way terms, they constrain their model too much. We can see a similar behavior if we look at the results of Tatec-shared-embs, which are much worse than those of Tatec. The pre-training is very useful: without pre-training, Tatec only achieves the same performance as the 2-way term alone. Tatec-linear-comb performs only slightly worse than Tatec, which indicates that, with proper regularization, a simpler combination of 2-and 3-way terms can be e cient. Overall,

		Median/Mean Rank Hits@5% Hits@20%
	Counts [9]	48/517	72	83
	LFM [9]	50/195	78	95
	SME [3]	56/199	77	95
	Bigrams	52/210	78	98
	Trigram	44/188	79	95
	Tatec	42/180	80	99
	stituents

Fibers are the higher order analogue of matrix rows and columns for tensors and are defnied by fixing every index but one.

Results of NTN are worse than expected. As we said earlier, we tried a large number of hyperparameter values but NTN might require to cover an even wider range.

Acknowledgments

This work was carried out in the framework of the Labex MS2T (ANR-11-IDEX-0004-02), and was funded by the French National Agency for Research (EVEREST-12-JS02-005-01).