Jean-Yves Y Blaise

Iwona Dudek

Gamze Saygi
email: gamze.saygi@map.cnrs.fr

Citizen contributions and minor heritage: feedback on modeling and visualising an information mash-up

Keywords: Spatio-historical data modelling, Citizen Science, Information visualization, Knowledge Discovery, Research Methodologies, Minor Heritage

teaching and research institutions in France or abroad, or from public or private research centers.

INTRODUCTION

The notion of minor heritage refers to material and immaterial forms of unprotected cultural heritage, often products of rural societies. They are genuine signs of craftsmanship, culture and traditions, and important components of the life of former generations. Nevertheless, quite often minor heritage slips through the large heritage programs or documentation initiatives, and therefore there is a lack of appropriate knowledge, and an unconsciousness of its value.

In that context citizen-birthed contributions appear as a major opportunity in the harvesting and enrichment of data about heritage assets (tangible or intangible, real-estate or movable). However actors potentially concernedfrom active citizens to scientists or collection holders -should not overlook the difficulties created by the nature of the hints one will face in that application field, for instance in the verbalization (e.g. "probably in 1666") or in the precision of the data (e.g. "alongside a former riverbed").

More generally, minor heritage is concerned with memories, with history, and history deals by essence with illdefined spatial, temporal and thematic data. Generally speaking, renewing the perceived value of such assets can help cultural actors (from citizens to "officials") in their effort to preserve the assets and assess their significance. Just as in T.Pratchett's Discworld gods get stronger when people believe in them, or weaker when they cease to do so, the understanding and preservation of minor heritage assets relies on the will of people to get engaged.

It is therefore important, along with foreseeing the potential benefits for scientists, to examine how trendy "crowdsourcing" or "citizen science" initiatives can contribute in a sustainable manner to the acquisition and analysis of heritage information sets, as well as to support actors already engaged in assessing the cultural value of minor heritage assets.

And indeed over time the "citizen science" concept tends to get blurred, and who exactly is meant when using the terms people, or citizens, can be a source of misunderstanding. Is a contributor to a crowdsourcing platform primarily a citizen, an enthusiast engaged in this or that field, or primarily "just a web user"?

As will be shown, the heart of the data we handle originates from citizens, who get involvedwith or without relation with academicsand actually produce and publish on the net large data sets. They, indeed, are citizens as well as web users; but they are primarily as far as our research is concerned local actors strongly engaged in Minor Heritage documentation, may it be for professional reasons or not. Accordingly, in the context of this research, we shall call them simply "Information Providers" (IP). Briefly said, the involvement of Information Providers appears as promising, yet demanding, in particular due to their heterogeneity:

 variety in terms of motivation, ranging from personal, private involvement of Heritage enthusiasts to a broad public sector set of actors (local communities engaged in cultural tourism for instance),

 variety in terms of analytical biases, ranging from systematic, inventory-like approaches (privileging here a thematic entry -"oratories", "old tools" -or there a geographic entry -"all about my village") to subjective selections based on the perception, emotions of the information provider,  variety in terms of work processes, in relation with the familiarity of the information providers with information technologies at large, and notably with web publishing platforms. Accordingly, our research aims at better circumscribing the difficulties one has to anticipate when wanting to harvest and visualize those pieces of information, and to derive from them pieces of Knowledge. To do so, we have pulled together three collections, that each push to the fore practical data acquisition, modelling and interpretation challenges. [START_REF] Kienreich | Information and knowledge visualisation: an oblique view[END_REF] and Visual Analytics [START_REF]Mastering the Information Age. Solving Problems with Visual Analytics[END_REF] methods as means to foster reasoning and sensemaking in the context of large, but citizenbirthed, ill-defined information sets: to which extent do these method apply?  Open-source geovisualisation solutions in the context of strongly heterogeneous data (movable vs. real-estate, tangible vs. intangible): what solutions can one rely on today, and how can the temporal dimension be efficiently visualized? But this paper is essentially about feedback: we focus on practical challenges we have faced in terms of data modeling and visualization, and introduce three main contributions.

Section 2 positions the research context with an emphasis on how citizen science practices meet minor heritage collections, and presents the strategy we have experimented in order to build mutually beneficial relations between Information Providers and the research program. Section 3 details the case study, pitfalls and choices made to cope with imperfections in the information [START_REF] Gershon | Visualization of an imperfect world[END_REF]. In that section we identify and exemplify factors of imperfection that we met in this very specific context of heterogeneous minor heritage documentation using e-sources. In Section 4 we present some of the visual solutions we have experimented in order to support analytical tasks in such information sets, and highlight the gain of insight they foster. Section 5 gives an overview of the evaluation strategies we have implemented up to now in order to measure the potential impact of the visualisations produced, as well as to get feedback from information providers and interpret it. Finally, we shortly sum up our main findings at this stage, and list some of the limitations and bottlenecks still ahead.

II. RESEARCH CONTEXT

At first glance this research could be seen as another contribution to this general and powerful move towards Digital Atlasesin the legacy of archaeological or architectural atlases, i.e. systematic, geo-referenced collections of pre-formatted information sets. Such initiatives encompass broad concerns that range from graphic semiology [START_REF] Koszewski | Visualization of Heritage-related Knowledge -Case Study of Graphic Representation of Polish National Inventory of Monuments in Spatial Information Systems[END_REF] to compatibility with standards (or more generally interoperability issues) [START_REF] Myers | The Arches heritage inventory and management system: a platform for the heritage field[END_REF] [START_REF]Definition of the CIDOC Conceptual Reference Model" version 6.2.3[END_REF]. In that general context of "formatting and interfacing heritage data sets" this research however builds on very specific choices, strategies, and issues that need to be made clear:

 The data we handle is not pre-formatted, and therefore falls outside of the classic "official records" approach to heritage items. We use heritage items as nodes (located in time and space) interlinking strongly heterogeneous e-sources.



The focus is put in this research on the potential added value of cross-examining though visual means such heterogeneous, and "imperfect" data sets.



We are concerned with the way the information provided by citizens, as it stands today, can feed the analysis of heritage items. This self-imposed constraint delineates the type of findings expected: getting a better understanding of the information sets themselves, of what analytical processes they are likely to support, and not necessarily getting a better understanding of the heritage items themselves. As a consequence this research claims no contribution to the creation or interfacing of heritage atlasesits scientific context is the impact of citizen-birthed information sets on scientific processes. And indeed with the emergence of information communication technologies citizens are becoming an increasingly important information source for diverse domains. Pioneering studies are done in geographical/spatial information thanks to open infrastructures like OpenStreetMap [START_REF] Jokar | OpenStreetMap in GIScience: Experiences, research, and applications[END_REF] and free webmapping services facilitate an implementation of the "citizens as sensors" mantra [START_REF] Goodchild | Citizens as sensors: web 2.0 and the volunteering of geographic information[END_REF], with contributors generating content, and enhancing geographical information by pointing out their local particularities. In a decade time, crowdsourced geographical information took various shades of application -e.g. voluntary geographical information, contributed geospatial information, user-created content [START_REF] See | Crowdsourcing, citizen science or volunteered geographic information? The current state of crowdsourced geographic information[END_REF], all in all, replacing the top-down tradition of geographical information production [START_REF] Gautreau | Sharing Platform in Digital Geographic Information: Everything It Promise?[END_REF]. But this move renews challenges such as inconsistency issues, data validation and quality assessment requirements [START_REF] Haklay | How good is volunteered geographical information? A comparative study of OpenStreetMap & Ordnance Survey datasets[END_REF][START_REF] Spyratos | Characteristics of Citizencontributed Geographic Information[END_REF].

In parallel typical citizen contributions for cultural heritage focus on basic tasks like annotating and tagging photos of archival material with keywords [START_REF] Ridge | Crowdsourcing our cultural heritage[END_REF], transcription of historical texts [START_REF] Noordegraaf | Modeling crowdsourcing for cultural heritage[END_REF], attributing longitude and latitude of objects by dynamically creating markers on the map [START_REF] Keinan | An Experiment in Crowdsourcing and Crowdfunding Archaeology[END_REF]. But what one needs to harvest in the context of our application field is not limited to the above indications: what we need to harvest are personal memories, records of individual experiences, self-knowledge about a time gone by. In other words, the information we need to uncover is more detailed yet less precise; it is often subjective, unverifiable, hence a questioning of the above contribution modalities. And even if we base on the assumption that contributors are good-willing and trustworthy, an experience reported in [START_REF] Freeman | Use your head: the inside track on the way we think[END_REF] shows we ought to be cautious. In that experience a group of people was asked to say how they were informed of the 1986 Challenger space shuttle accident, a short while after the accident itself, and then again 20 years later. Differences in the reports talk for themselves: recollections are significantly altered by time.

Yet uncovering personal, individual self-knowledge in citizen contributions is crucial if we want to preserve and share an understanding of minor heritage. Furthermore it does correspond to a trend that originates from citizens themselves who are today uploading self-knowledge and past experience via personal blogs.

In other words the issue of how to record, share and interpret such contributions is raised. As an answer, we use the case study as an opportunity to test out alternative contribution modalities, that target individuals' selfknowledge rather than solely focusing on collecting or decrypting massive information sets, and that can contribute to a better assessment of what imperfections are likely to be met.

More than ten years ago, M.F.Goodchild [START_REF] Goodchild | Citizens as sensors: web 2.0 and the volunteering of geographic information[END_REF] coined the terms "citizens as sensors", paving the way for the Volunteered Geographic Information (VGI) research community, while the Galaxy Zoo experiment and its extension the Zooniverse platform introduced a more generic concept referred to as people-powered research (and the latter has indeed been of use in Heritage Studies since then). Yet over time shades of that generic concept have clearly emerged [START_REF] Wiggins | From Conservation to Crowdsourcing: A Typology of Citizen Science[END_REF]: crowdsourcing practices where citizens get engaged in order to support research activities initiated and conducted by academics, citizen science projects launched by citizens themselves, and finally collaborative science where citizens and academics co-define the research topic. With regards to those shades, our contribution primarily falls within the citizen science paradigm: the engagement of Information Providers, and therefore the data we base on, obviously existed prior to our research.

Yet we have initiated a series of workshops with IPs in order to move towards a collaborative approach by conarrowing research questions. But in order to do so one has to be pay attention to potential misunderstandings between academics and non-academics, and in particular to clearly assess mutual benefits. Our strategy has been to try and demonstrate potential added-values on both sides.

This was done as a first step by showcasing the accomplishments of IPs in three different ways: each leaf of the platform (i.e. pages presenting one particular heritage item, reached after user selections) contains links to the information providers' platforms; one of the search modes is in fact a list of IPs, with for each of them a list of items they contribute to document; and a specific visualisation highlights the intensity of an information providers' activity on the territory under scrutiny (Fig. 1). Oblique lines connect a given information provider to a "number of e-sources provided" for each département. In this example daniel-thiery.com appears as quoted 157 times in one departement (green), but only once or twice in two others : a clear marker of this information provider's area of concern, and type of practice.

We then developed customized services for each information provider: on-the-fly production of three visualisations that show the information sets corresponding to one information provider (Fig. 2 We suggest that you use a text box to insert a graphic (ideally 300 dpi), with all fonts embedded) because, in an MSW document, this method is somewhat more stable than directly inserting a picture.

To have non-visible rules on your frame, use the MSWord pull-down menu, select Format > Borders and Shading > Select "None".

One should not however overlook the difficulty of aligning this strategy with the actors. Typically what we view as "services" can be totally irrelevant for this or that type of IP. Hence a necessity to try and better understand profiles of IPs, their expectations, and their work processes. At this stage of the research we identified eleven profiles (e.g. community builders, bloggers, collectors, local actors, etc.) and aligned these profiles with behaviours or work practices (type of content published, thematic scope, geographical area, etc.). This assessment of ways of doing proved helpful in the preparation of workgroup discussions with IPs (see section V) in order to unveil tendencies in the material they publish, or in their editorial choices (Fig. 3).

III. THE CASE STUDY

Our case study concerns the territory of the PACA (Provence Alpes Côte d'Azur) region, one of France's 13 metropolitan regions, composed of 958 communes (smallest administrative layer). These communes are distributed in 6 départements, an intermediate administrative level. Communes vary in size (area and population, in proportion 1:1300 and 1:3449, 2013 data). We pulled together three collections consisting of : (i) 1217 rural chapels, (ii) 360 traditional farming tools from the MuCEM Ethnological museum (Musée des Civilisations de l'Europe et de la Méditerranée), and over 200 traditional crafts and professions (Fig. 4). The idea is to try and cross-examine components of the collections and to assess visually spatial, temporal, and semantic relations.

A. Harvesting the data

Although the collections are different, we extract a set of common features corresponding to the spatial dimension (classic point location, but also relations between locations as in commercial exchanges), to the temporal dimension (both linear chronology and potential cyclic behaviors), and to thematic layers underlining potential spatial and temporal concurrences across the collections.

Table 1 sums up the data harvested (or available) for each collection.

Spatial

Temporal Thematic edifices Location (long, lat), altitude and orientation 1 . The notion of "spatial data" encompasses the 3D shape of the edifice one of our fields of concern, but a topic we do not mention in the context of this paper. Time anchors: a concept developed as the hints we meet may refer to the construction of the edifice itself ("built in the 17 th century"), but also to its "first mention in archives", etc.. Items are grouped by categories that act as thematic layers. Scarce indications are available on the "instructions for use", on the making of the items, on the way they were stored and preservedthese are the pieces of information the research primarily expects to harvest through citizen contributions.

A

crafts and professions

Association with one or several containers (communes) and when possible with a specific location (market, etc.) Recording of periods of practice (question: "when was this craft present") Thematic layers include hints on the practices themselves, on their naming (etymology, alternative names), on tools and materials concerned, and when relevant a qualitative description of the spatial layout (mobile stand, workshop, etc.

The data was harvested primarily from online e-content concerning the edifices and the traditional crafts collections. For the edifices collection 3054 web pages are recorded, along with an attribute stating the "nature" of the information provider: public service, citizen contribution (from nonspecialized blogs to heritage supporters' web sites), community building initiatives, etc. Fig. 5 gives a broad idea of the proportion of "citizen-birthed" information. Concerning the farming tools collection most of the data was already available in the MuCEM's records, however esources were harvested in order to complement definitions or to associate items with recurrent cyclic events (fairs typically).

For the traditional crafts and professions collection a set of e-sources was also collected that document the crafts in general terms or as they developed on the territory we are interested in. But here a traditional bibliography complements the information available, and multimedia content (still images, videos and sounds) are referenced that give a more "ethnographic" colour to the data harvested. On the overall 1139 e-sources are referenced. In both the above cases the data was harvested manuallya limitation in a sense, but a necessity in the early stages of the research in order to grab a fine-grain understanding of the nature of the data.

B. Modelling the data: pitfalls and choices

Defining and verifying the application of a robust observation protocol is one of the most prominent difficulties when harvesting crowdsourced data, whatever object of study is concerned. In this research we base on existing data sets, with observation protocols that are hardly described, when not simply non-existent. Our focus is therefore put on the data as it stands, and our attempt has been to try and list the consequences, in terms of reliability, of using such data sets.

Classifying factors of imperfection in spatio-temporal or historical data has been a recurrent research topic over the past years, sometimes within the boundaries of a scientific discipline [START_REF] Aigner | Visualization of Time-Oriented Data Springer: Human-Computer Interaction Series[END_REF] [START_REF] Skeels | Revealing uncertainty for information visualization[END_REF], sometimes in more interdisciplinary settings [START_REF] Blaise | Picturing What Others Know: Towards a Dashboard for Interdisciplinarity[END_REF]. In this section we borrow notions and terms from the scientific literature and from previous research, however some of these terms and notions remain today discussed. We therefore propose in the table below a series of definitions and references in order to avoid ambiguities, along with a series of "real-life" examples of where and how they are present in our case study. We make no claim that this list is comprehensive, yet it does pinpoint some key factors we came across, in a practical manner, and we consider it a significant part of this "feedback" our contribution is about.

determinacy

Whether the value of a variable is known at all or not.

[18]

An edifice that cannot be localized (only mentioned in archives, without hints on its position), or that cannot be dated.

credibility Judgment made by the human consumer of the information about the information source.

[19]

Association of a craft and a territory basing on the sole recollections of a witness. [19]

Measuring the orientation of an edifice bases on the presumption that the nave is actually straight, and the apse unambiguously positioned.

incompleteness

The idea that the observed evidence is likely to only be a small portion of the whole.

[21]

None of the collections we handle is complete, hence the necessity to be cautious in any interpretation. Furthermore, as mentioned by [START_REF] Skeels | Revealing uncertainty for information visualization[END_REF], the unidentified unknowns are the worst kind of missing information, and one of the sub-goals of a citizen science approach to minor heritage can be to try and diminish the amount of unidentified unknown.

interrelatedness Source independence from other information.

[21]

When two e-sources make a common statement, yet without quoting each other or the common initial source they based on.

currency Temporal gaps between occurrence, info collection & use.

[21]

Temporal gaps between the period of use of a farming tool, and the moment when it was collected.

multivocality When several hints appear as contradictory.

[18]

The literature sometimes mentions inconsistency or disagreement [START_REF] Thomson | Typology for Visualizing Uncertainty[END_REF] to name such imperfectionsa typical occurrence is opposite contradictory dates given for an event.

accuracy Difference between heuristic & algorithm.

[22]

Transferring a qualitative indication such as "during the spring" to a given numerical interval.

imprecision Inexactness of measurement.

[21]

The value recorded for an edifice's altitude depends on with what instrument / under what climatic conditions the survey was carried out: a non-systematic protocol may alter the precision of the data. lineage

Conduit through which info passed (number of steps).

[21]

A typical example is the recording of farming tools: the information available in the records today results from a process that involved at least the donor of the object and the museum expert, and potentially ancestors of the donor, and contemporary successive curators.

periodization Dating of a fact by reference to another one.

[20]

Periodization should be interpreted in a broad sense, from examples such as "in the early middle ages" or "rebuilt after the revolution" to natural facts and phenomena such as "during the crops". subjectivity Amount of private knowledge or heuristics utilized.

[22]

There is no reason to think that the way a craft was organized in one location by one craftsman as it is reported by him or his descendants is an objective testimony of what that craft is, yet we rely on such subjective hints to picture it. likelihood At best, a stopgap verbalization in inference making.

[20]

Wordings such as "could have been built shortly after the Wars of Religion"; or "livestock markets probably took place in the open land close to the river bed".

Most of these factors are present in the three collections, and a workable approach to "reduce" imperfections is not always within reach. It has to be said clearly that anyway in Historical Sciences reducing imperfections is in fact not a good idea at all: disagreement and open questions are fullblown components of the reasoning process. Our approach bases on the vision that what we need to convey about the data is not assertive interpretations but hints the way they are, yet made more readable, and sharable. We sum up below on one hand choices made in the modelling of the data, and what we view as open issues, lacks and shortcomings, concerning both the spatial and temporal dimensions.

C. The spatial dimension

The baseline geographical data recorded in the edifices collection are a position (longitude, latitude), an altitude, and an orientation. At this stage we defined a list of values (numerical scale) used to "tag" data with regards to determinacy and credibility factors (is it known at all? From what source?). The scale is used in the recording of the data, and at visualization time in the graphic semiology. Yet this does not solve the problem extensively. Edifices for which the location is not known at all are tagged as belonging to a container (a commune) -but what if even that indication is unavailable?

For the crafts collection we record two indications: association of a craft with one or several containers (communes) and qualitative description of the spatial layout. But in the case of occupational travelers, a category that encompasses herdsmen moving to mountain pasture areas and travelling salesmen, we still need to propose a data model that would allow the recording of itineraries. This is not a trivial issue: recording only the start and end location is bland from the scientific point of view, adding "stop points" along itineraries (a watering place, a fair, a rest place) could make sense but leaves vast unknowns since an itinerary is hardly composed of straight lines. What is more, temporal aspects of the displacements are also very significant: a series of (Space, Time) tuples could therefore better match the reality of what we need to learn.

Finally for the tools collection defining relevant geographical data is a methodological challenge: what is the "position" of a movable object? What would be the point in recording its current position (i.e in a Museum's reserves) from the point of view of scientific analysis? At this stage we record tuples of values: the position of the commune where an object was created and the commune where it was used. This at least paves the way for a visual analysis of exchange routes (rather basic though, see Fig. 6). However in many cases we only have an indication on the département of creation and of use, and the visualization then is ineffective. It is plausible anyway that a more significant information would be a simple time+space assessment of presence.

D. The temporal dimension

As mentioned before, temporal data recorded in the edifices collection are "time anchors". This indication is, as often in the heritage field, dramatically impacted by the multivocality and interrelatedness factors. In many cases the info we harvested is contradictory, and when not its level of independence is hard to state. However this case study also underlined a number of other potential pitfalls: determinacy (numerous edifices are simply not dated), scope (what is actually dated is not clearpresence at time T, time of construction, etc.), accuracy (wordings like "in the middle of the 16th century), periodization ("after the middle ages").

For each edifice we record as many time anchors as read from the sources, and have defined a "conventional temporal mapping" grid that helps us transferring the verbal indication ("beginning of the 17th century") into a quantified time slot ("1600 -1620") used at visualization time. This solution was at start designed as a makeshift solution, and we are now investigating how an ontology of temporal hints verbalization modalities can help in the analysis and visualization steps.

In both the crafts and farming tools collections what we record are time intervals during which the item is "active", as well as hints on for instance intermittency patterns. Crossexamining the three collections showed that ultimately one of the challenging issues we need to address is harvesting and reasoning not only on a chronology, on a linear time succession of dates, but on the overlapping of recurrent temporal patterns as implicitly present in expressions such as "every summer", "every second Sunday of July", "during the harvesting of the grapes". Consequently, we complement the data models that are specific to this and that collection by a data model used to collect and document cyclic (or at least non-linear) temporal occurrences (markets, fairs, votive festivals, pilgrimages, etc. ).

The data collected acts as a potential bridge between collections, since in a number of cases such an occurrence concerns two or three collections (e.g. a fair where a craft was presented, tools were sold, during a votive festival in relation with an edifice). In parallel, that data acts as a test bench for the formalization and visualization of cyclic temporal occurrences, including in the verbalization modalities.

IV. VISUALISING THE DATA

The general objective in visualizing the data is basically to cross-examine, correlate, and perform reasoning on the temporal, spatial, thematic dimensions, to spot significant patterns with keeping a concern for doubtful info. Over time we have experimented a rather large number of cartographic solutions, and of InfoVis solutions, with for each an ambition to try and answer to specific questions (a tribute to J. Bertin's vision) such as is there a relation of the altitude to the orientation of edifices? Are there more contributors in one commune than in another one? The inspiration behind these experimentations is at the intersection of geovisualisation, time-oriented data and InfoVis, an intersection personified by the works and legacy of C.J Minard [START_REF] Friendly | Visions and Re-visions of Charles Joseph Minard[END_REF]. In this section we present three examples that we believe show the above methodological intersection is worth exploring (even with "poor" data sets in terms of quality and consistency).

A. A map of exchanges

Fig. 6 shows a leaflet-based map [START_REF]Leaflet open-source JavaScript library for mobile-friendly interactive maps[END_REF] produced in order to explore the basic geographical data we have for the farming tools collection, i.e. commune of creation, commune of use. The visualization as such, a simplification of the flow map visualization paradigm, appears quite efficient in highlighting some tendencies, for instance the exchange routes between winter and summer areas concerned with transhumance related activities (SW<>NE). Colors (see legend), are used to represent the amount of objects created (interior circle) and used (exterior circle) in a commune.

Two communes (Arles and Névache) appear as strong "exporters" of tools. It is important however not to jump to conclusions: the data set is too inconsistent to provide a robust analysis groundthe visualization from our point basically acts as a proof-of-concept and shows what could be gained from a larger and better documented collection.

B. Densities and altitudes

The area of concern combines very different landscapes (mountains of the Southern Alps, dry hills, a coastal strip densely populated today, etc.). What can be learnt on the spatial distribution of edifices with regards to factors such as landscape, climate, accessibility, and so forth? The following visualisation (Figures 7,8,9) helps reading an interaction of parameters: area, various altitudes, density of edifices per commune / per department. Some striking observations emerge, that sometimes obviously deny false beliefs. For instance the "classic" vision of Provence's hilltop villages that dominate the land below appears scarcely in line with reality. In the alpine valleys climate and accessibility constraints, along with the summering activities, lead to impressive densities of edifices in territories deemed as nonwealthy. In Fig. 7 the commune of Abriès is underlinedalmost all edifices are higher than the commune's center, with a rather regular layering that is typical of mountain territories inhabited for a long time span. In the case of a mountain commune like Abriès the mean altitude is unsurprisingly higher than this of its center. Vertical lines topped with a little squares correspond to edifices inside each commune, indicating each edifice's altitude. For non-localized edifices both lines and squares are white, and aligned with the altitude of their commune's center.

Figure 8. Left, note the dramatic difference in terms of density between a (Beauvezer) and b (Bevons)although the latter is lower in altitude, and larger too. Right, c (Lurs), exemplifies a "hilltop village" pattern, with the center of the commune higher than its mean altitude.

Figure 9. A version of the densities and altitudes visualisation customized for each information provider (produced on the fly, upon selection of a given information provider, here dignois.fr). Only those communes for which the information provider does provide e-content are represented.

This version of the visualisaiton includes indications on the position of the edifice (aisolated vs. hamlet vs. village). It also shows information about e-sources recorded for each edifice (bcolours of circles correspond to the type of information providers, see Fig 5). The e-sources produced by the information provider are represented by a larger circle (c). The visualisation can be used for instance to spot inside a given commune edifices that the information provider is the only one to document (d), or by contrast edifices that the information provider does not document.

C. The "orientation cloud"

Christian churches in Europe are, in theory, oriented edifices at least until the Baroque Period (the apse should face the East). Architectural treaties teach us how middle ages builders managed to apply that rule using kind-of basic gnomons. But was that rule really applied to small chapels? Until when? Does the relief or the altitude impact its application? When the rule was not applied, did builders orient edifices erratically? In this visualization we correlate the orientation with three variables: container (département), date (time anchors), and altitude. Each rectangle corresponds to an edifice, positioned around a "compass": edifices with an apse facing the north are positioned on the "north" of the compass. The visualization underlines for instance a tendency of older edifices to be better in line with the rule (Fig. 10). It also shows an inclination of later builders for turning the apse towards the north, and de-correlates the orientation and altitude parameters (in other words, denies the common sense belief that because of stronger relief constraints builders are more keen to step out of the rule). The approach is implemented as a web platform combining classic components: an RDBMS (MySQL), a web Server (Apache), a large number of scripts (Perl / PhP) used to produce (on the fly and/or as files depending on the need) textual content : HTML files, JavaScript variables and arrays, csv "raw data" tables, SVG (visualisations) or geojson data sets. The interaction between those components is operated through JavaScript components developed on purpose. The cartography bases on the leaflet library [START_REF]Leaflet open-source JavaScript library for mobile-friendly interactive maps[END_REF].

V. EVALUATION

On the overall thirteen visualisations have been produced up to now, with three of them "customized" for each Information Provider (Fig. 2, Fig. 9, Fig 11). Their evaluation has been carried out in a twofold manner: an assessment of their usability and understandability for nonexperts (no familiarity with infovis practices nor with minor heritage), and an assessment of added-value for Information Providers themselves, carried out during ad-hoc workshops. During those workshops, we also collected a more general feedback on the research's fundamental approach, a feedback we will discuss in the final version of the paper if accepted, as the last workshop still needs to be carried out.

A. Usability and understandability

The objective of this first round of evaluation was to get a feedback on the graphic choices (encoding, layout, interaction, support for users), but also on the efficiency of the visualizations, i.e. on whether or not they do support information discovery. To do so six non-experts were asked to fill in one form per visualisation, with each form structured according to the following set of criteria:

 readability assessment (measuring to which extent graphic elementscolours, shapes, etc.-are easy to identify, and to differentiate from one another);  problem accuracy (feedback on parameters that users think should be taken into consideration) [START_REF] Munzner | Visualization Analysis and Design. AK Peters Visualization Series[END_REF];  knowledge communication (Evaluation of the capacities of the visualisation to help users understand pieces of knowledge or to help knowledge holders transfer their knowledge [START_REF] Lam | Empirical Studies in Information Visualization: Seven Scenarios[END_REF]);  reasoning and hypothesis generation (Evaluation of how the visualisation supports hypothesis generation and interactive cross-examination of data [START_REF] Lam | Empirical Studies in Information Visualization: Seven Scenarios[END_REF]);  adoption and reuse (feedback on the potential dissemination constraints) [START_REF] Lam | Empirical Studies in Information Visualization: Seven Scenarios[END_REF];  user guidance (measuring to which extent means to guide the users are relevant and efficient) [START_REF] Beier | Reading Letters: designing for legibility[END_REF];  legibility (Verification of the lexical characteristics of the information) [START_REF] Bastien | Scapin Ergonomic Criteria for the Evaluation of Human-Computer Interfaces Technical report[END_REF];  adaptability (capacity of a system to behave contextually and according to the the users' needs and preferences);  consistency (the way interface design choices (codes, naming, formats, procedures, etc.) are maintained in similar contexts, and are different when applied to different contexts). We presented to the testers the project as a whole, the data sets and the general relations between pieces of data (e.g. edifices located in communes, documented by web sources that are classified according to types of info providers, etc.). The evaluation was then performed by each tester on his own, under no supervision: the visualizations themselves were not explained, and testers had to analyse them basing on what they were told of the underlying data, and on the legends.

Answers we collected through that evaluation helped us rethink some basic and early choices such as colour palettes, sizes of graphic elements, distances between elements, level of detail of the legends, or the integration of graduated scales in order to help reading quantities. We nevertheless acknowledge the fact that such an evaluation, given the small number of testers, and the absence of a trial and error process, should not be considered as more than a starting point. The fact that testers had no background knowledge or involvement in heritage sciences at large leads to an inconclusive evaluation on factors like "problem accuracy".

B. Added-value for Information providers

As researchers, we have made choices in the identification and modelling of the information, and then developed a series of visualizations thanks to which we could perform reasoning tasks and formalize an analytic discourse. But, after all, is all that effort of any help to information providers? Since the information providers we have called in are unfamiliar with information visualization solutions, will these solutions be of any use for them? And if they are not, are we really into something that has to do with citizen science? Figure 11. The customised chronology visualisations for two information providers (top: dignois.fr; bottom: montnice.fr). Each rectangle corresponds to one edifice, the diagram is read from left to right, with each column corresponding to occurences inside a century (partial views of the visualisations, period prior to 900 AC not shown). Bottom left, legend: graphic encoding of parameters "position of the edifice" and "period of creation". The data sets correspond to individual actors engaged in the study of two strongly contrasting territories inside the region: dignois.fr focuses on one of the the least populated french departements, and one of the poorest; whereas montnice.fr focuses on the hinterland of the Nicecôte d'azur territory, a more densely populated area, relatively recently integrated to the French Republic, and not one of the poorest French departements. Note, nevermind those differences, strong similarities in aa significant rupture in the creation activity during the XIVth century (plague epidemics are a potential, however still unproven, explanatory factor) ot in ban intense creation activity during the XVIIth. Also note, in c , an observation that can be made on both data sets: old edifices are in majority isolated edificesa common sense assertion (no need to erase an edifice with no neighbours...) here backed up by facts. But beyond similarities between the features of the data sets the visualisations underline significant differences: note for instance the proportions of "prior to 1500" edifices in both cases.

In a paper introducing visual analytics, [START_REF] Keim | Visual Analytics: Definition, Process and Challenges[END_REF] coined the key expectations that need to be met: understand and analyse our data, understand and analyse our analyses. It was therefore important for us to get direct feedback from information providers on the visualisations. To do so we organized a series of workshops during which we privileged open discussions on each of the visualisations, including the customized ones. It turned out that they do provide "food for thinking" services on such aspects as density patterns or information quality patterns, and help spot "errors" (typically contradictory data, misinterpretations of temporal hints, etc.).

But beyond that, and somehow beyond our expectations, the visualisations brought a significant support to workgroup exchanges, for instance on temporal distribution patterns as they emerge from the works of different IPs (Fig. 11). Ultimately nine out of the twelve IPs included in this second round of evaluation expressed the will to get involved in carrying out more such experimentations with us, which is a somehow serendipitous outcome (as well as a fulfilling one).

VI. LIMITATIONS AND CONCLUSION

This research addresses some pending issues at the intersection of minor heritage preservation, citizen contributions, and spatio-temporal data analysis. The paper focuses on three challenging aspects for academics who would want to build on citizen-birthed information sets in order to better document and analyse minor heritage items:

 The heterogeneity of the Information (in terms of scope, of editorial choices, of quality, etc.), and behind it the heterogeneity of the Information Providers themselves. We present and discuss the strategy adopted in order to demonstrate potential added-values of such a research on both sides (academics as well as information providers), and in order to pinpoint profiles of information providers.  The factors of imperfection that are likely to be met when handling such information sets. We first give a global view of the data and information harvested from citizen-birthed e-sources, and then propose an exemplified list of the key factors of imperfection we came across during the research up to now.  The design and implementation of visual solutions supporting analytical tasks in the specific context of imperfect information sets. We present and discuss the learnings of some of the solutions we have developed, solutions that are today available online (territographie.map.cnrs.fr). The case study acts as a test bench helping to investigate data harvesting and visualization challenges. It shows that there is still a significant effort to make in adapting contribution modalities to heterogeneous collections and to the nature of the information we target. It also shows that investing time on the visualisation step, despite information imperfections, is sound: significant patterns emerge. But these patterns are not assertions: what they renew is our capacity to question and challenge our own level of knowledge and of understanding of those collections. Some clear limitations should quoted, though, at this stage of our research. Making a sound and grounded assessment of the initiative's added value is arduous since its impact depends on a time taking effort to call contributors in, and to analyse feedbacks. We therefore make no claim that we can present definitive conclusions, but on the overall we believe the experiment shows there is before us a shift in the way academics and collection holders can decode, re-read, augment minor heritage data sets: a shift from "one shot, one collection" protocols to "comparative, cumulative, open science" investigation modalities.

Figure 1 .

 1 Figure 1. Top, a browsing mode that showcases the information providers workslist of all edifices documented by an information provider (here daniel-thiery.com, in-depth historical analyses authored by a local expert on a personal basis). Bottom, a visualisation in which the geographical distribution of edifices that a given information provider contributes to document is shown. Vertical lines correspond to the six departements in the region (intermediate administrative level).Oblique lines connect a given information provider to a "number of e-sources provided" for each département. In this example daniel-thiery.com appears as quoted 157 times in one departement (green), but only once or twice in two others : a clear marker of this information provider's area of concern, and type of practice.

  , Fig. 9, Fig 11).

Figure 2 .

 2 Figure 2. Cartography customised to show the pieces of information produced by one specific Information Provider (here dignois.fr). Other customised serviceschronography and density / altitude analysis visualisations -are disucussed in section 4.

Figure 3 .

 3 Figure 3. Relations of IP profiles (represented as coloured squarescolours correspond to "types" of actorse.g. red for parapublic sector, blue for NGOs, etc.) to publication practices. The circle on the right represents "publication of raw data"only three profiles do consider the publication of such data sets, and two of them occasionally only (dashed line).

Figure 4 .

 4 Figure 4. An illustration of the items in the various collections.

  time anchor is basically the association of the edifice to a verbal or quantitative expression of a date. Other temporal indications recorded are temporal cycles of use (seasonal use for instance) and changes that occurred along the history of the edifice. Thematic layers range from architectural analysis (e.g. shapes, components) to records of experiences such as pilgrimages, votive festivals, or simply travel diaries. farming tools An item is, when possible, associated with a geographical containercommune or département. Two indications are available: the recording date (year of acquisition by the Museum) and when possible the period of use of the item (No indication on the cycles of use).

Figure 5 .

 5 Figure 5. Information providers' profiles: each square correspond to an esource. Green, blue and light-blue squares correspond to citizen-birthed information, red to public services, purple to commercial site.

approximation

  Attempt to come close to measuring or describing a phenomenon […].

Figure 6 .

 6 Figure 6. A visual representation of the communes of creation and usecircles represent communes, curves are used when a tuple [creation, use] info is associated to a tool, and the thickness of the curves correspond to the amount of tools. (a -St. Véran, b -Arvieux, c -Névache, d-Arles).

Figure 7 .

 7 Figure 7. Composition of the graphics: communes of a département are

Figure 10 .

 10 Figure 10. Orientation cloud (partial view showing the most dense part of the "compass", the North-East sector)the darker the rectangle, the older it is. Outlined in red: non dated edifices..

  Generally speaking the research pushes to the fore a number of open issues:

 Citizen science in the context of minor heritage: in what does that paradigm renew the way one can expect to enrich or analyse minor heritage assets?  Minor heritage in the general context of heritage sciences: what kind of general knowledge can be derived from such items and collections, from partial, often unverifiable hints?  Information visualization (InfoVis)

TABLE I .

 I THE DATA -SPATIAL, TEMPORAL AND THEMATIC DIMENSIONS.

TABLE II .

 II FACTORS OF IMPERFECTION: LEXICON, REFERENCES, AND EXAMPLES OF OCCURRENCES IN THE DATA SETS.

Orientation of the edifice's nave, i.e. of a vector running from the porch to the apse, by convention counted from the North.

ACKNOWLEDGMENT

This research is funded by the région Provence-Alpes-Côte d'Azur regional authorities, and conducted in cooperation with the Mucem (Musée des Civilisations de l'Europe et de la Méditerrannée) -authors thank E. De Laubrie and Y.Padilla.


Thomas Bonald

Alexandre Hollocou

Marc Lelarge

Weighted Spectral Embedding of Graphs

Keywords: South America, Pacific Ocean, Tourism, Colombia 94 Film, Sanskrit, Light, The Simpsons, Eye, Shark 71 Mining, Food, Geography, Engineering, Transport

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

Many types of data can be represented as graphs. Edges may correspond to actual links in the data (e.g., users connected by some social network) or to levels of similarity induced from the data (e.g., users having liked a large common set of movies). The resulting graph is typically sparse in the sense that the number of edges is much lower than the total number of node pairs, which makes the data hard to exploit.

A standard approach to the analysis of sparse graphs consists in embedding the graph in some vectorial space of low dimension, typically much smaller than the number of nodes [START_REF] Robles-Kelly | A Riemannian approach to graph embedding[END_REF][START_REF] Yan | Graph embedding and extensions: A general framework for dimensionality reduction[END_REF][START_REF] Cai | A comprehensive survey of graph embedding: problems, techniques and applications[END_REF]. Each node is represented by some vector in the embedding space so that close nodes in the graph (linked either directly or through many short paths in the graph) tend to be represented by close vectors in terms of the Euclidian distance. Standard learning techniques can then be applied to this dense vectorial representation of the graph to recommend new links, rank nodes or find clusters of nodes for instance [START_REF] Fouss | Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[END_REF][START_REF] Bronstein | Geometric deep learning: going beyond euclidean data[END_REF].

The most popular technique for graph embedding is based on the spectral decomposition of the graph Laplacian, each dimension of the embedding space corresponding to an eigenvector of the Laplacian matrix [START_REF] Chung | Spectral graph theory[END_REF][START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Belkin | Laplacian eigenmaps for dimensionality reduction and data representation[END_REF][START_REF] Luxburg | A tutorial on spectral clustering[END_REF][START_REF] Spielman | Spectral graph theory and its applications[END_REF][START_REF] Newman | Spectral methods for community detection and graph partitioning[END_REF]. This spectral embedding can be interpreted in terms of a random walk in the graph [START_REF] Lovász | Random walks on graphs[END_REF][START_REF] Qiu | Clustering and embedding using commute times[END_REF]. In the full embedding space (including all eigenvectors), the square distance between two vectors is proportional to the mean commute time of the random walk between the two corresponding nodes: close nodes in the graph tend to be close in the embedding space. Viewing this random walk as the path followed by electrons in the corresponding electrical network, with nodes linked by resistors, these square distances can also be interpreted as the effective resistances between pairs of nodes [START_REF] Snell | Random walks and electric networks[END_REF].

In this paper, we address the issue of the spectral embedding of graphs including node weights. We shall see that existing spectral embedding techniques implicitly consider either unit weights or so-called internal node weights, depending on the Laplacian used in the spectral decomposition. We here consider the node weights as some additional information representing the relative importance of the nodes, independently of the graph structure. The weight of a node may reflect either its value, its multiplicity if each node represents a category of users or items, or the reliability of the associate data, for instance. Surprisingly, this notion of weight is common for vectoral data (see, e.g., the weighted version of the k-means clustering algorithm [START_REF] Huang | Extensions to the k-means algorithm for clustering large data sets with categorical values[END_REF][START_REF] Dhillon | Kernel k-means: spectral clustering and normalized cuts[END_REF][START_REF] Kerdprasop | Weighted k-means for density-biased clustering[END_REF]) but not for graph data, where weights are typically assigned to edges but not to nodes, apart from those induced from the edges.

Our main contribution is a spectral embedding of the graph, we refer to as the weighted spectral embedding, that incorporates the node weights. It is based on the spectral decomposition of some properly normalized version of the Laplacian. We prove that, when all eigenvectors are used, this embedding is equivalent to the regular spectral embedding shifted so that the origin is the center of mass of the embedding. In practice, only the first eigenvectors are included to get an embedding in low dimension. We show that these eigenvectors can be interpreted as the levels of lowest energy of a physical system, either a mechanical system where nodes are linked by springs (the edges) and have different masses (the node weights), or an electrical network where nodes are linked by resistors (the edges) and connected to the ground by capacitors with different capacitances (the node weights). In particular, the weighted spectral embedding can not be derived from the regular spectral embedding in low dimension. Experiments confirm that these embeddings differ significantly in practice.

The weighted spectral embedding can also be interpreted in terms of a random walk in the graph, where nodes are visited in proportion to their weights. In the full embedding space (including all eigenvectors), the square distances between vectors are proportional to the mean commute times of this random walk between the corresponding nodes, as for unit weights. In fact, these mean commute times depend on the weights through their sum only, which explains why the pairwise distances of the embedding are independent of the weights, up to some multiplicative constant. This property is somewhat counter-intuitive as the mean hitting time of one node from another does depend on the weights. We shall explain this apparent paradox by some symmetry property of each equivalent physical system.

The rest of the paper is organized as follows. We first introduce the model and the notations. We then present the regular spectral embedding and its interpretation in terms of a random walk in the graph. The weighted version of this random walk is introduced in Section 4. Section 5 presents the weighted spectral embedding and extends the results known for the regular spectral embedding. The analogies with a mechanical system and an electrical network are described in Sections 6 and 7, respectively. Experiments on real data are presented in Section 8. Section 9 concludes the paper.

Model

We consider a connected, undirected graph of n nodes, without self-loops. We denote by A its adjacency matrix. In the absence of edge weights, this is a binary, symmetric matrix, with A ij = 1 if and only if there is an edge between nodes i and j. In the presence of edge weights, A ij is the weight of the edge between nodes i and j, if any, and is equal to 0 otherwise.

Let d = Ae, where e is the n-dimensional vector of ones. The components d 1 , . . . , d n of the vector d are equal to the actual node degrees in the absence of edge weights (A is a binary matrix) and to the total weights of incident edges otherwise (A is a non-negative matrix). We refer to d 1 , . . . , d n as the internal node weights.

Nodes are assigned positive weights w 1 , . . . , w n corresponding to their relative importances. These node weights are external parameters, independent of the graph. We denote by w the vector (w 1 , . . . , w n ).

Spectral embedding

We first present the regular spectral embedding, without taking the node weights w 1 , . . . , w n into account. Let D = diag(d) be the diagonal matrix of internal node weights. The Laplacian matrix is defined by

L = D -A.
This is a symmetric matrix. It is positive semi-definite on observing that:

∀v ∈ R n , v T Lv = i<j A ij (v j -v i ) 2 .
The spectral theorem yields

L = U ΛU T , (1)
where Λ = diag(λ 1 , . . . , λ n ) is the diagonal matrix of eigenvalues of L, with 0 = λ 1 < λ 2 ≤ . . . ≤ λ n , and U = (u 1 , . . . , u n ) is the matrix of corresponding eigenvectors, with U T U = I and u 1 = e/ √ n.

Spectral embedding. Let X = √ Λ + U T , where Λ + = diag(0, 1/λ 2 , . . . , 1/λ n ) denotes the pseudo-inverse of Λ. The columns x 1 , . . . , x n of the matrix X define an embedding of the nodes in R n , each dimension corresponding to an eigenvector of the Laplacian. Observe that the first component of each vector x 1 , . . . , x n is equal to 0, reflecting the fact that the first eigenvector is not informative. Since Xe = 0, the centroid of the n vectors is the origin:

1

n n i=1 x i = 0. (2)
The Gram matrix of X is the pseudo-inverse of the Laplacian:

X T X = U Λ + U T = L + .
Random walk. Consider a random walk in the graph where the transition rate from node i to node j is A ij . Specifically, the walker stays at node i an exponential time with parameter d i , then moves from node i to node j with probability P ij = A ij /d i . This defines a continuous-time Markov chain with generator matrix -L and uniform stationary distribution. The sequence of nodes visited by the random walk forms a discrete-time Markov chain with transition matrix P = D -1 A.

Hitting times. Let H ij be the mean hitting time of node j from node i. Observe that H ii = 0. The following results, proved in [START_REF] Lovász | Random walks on graphs[END_REF][START_REF] Qiu | Clustering and embedding using commute times[END_REF], will be extended to weighted spectral embedding in Section 4. We denote by e i the n-dimensional unit vector on component i.

Proposition 1

The matrix H satisfies:

LH = ee T -nI. (3)
Proposition 2

The solution H to equation (3) with zero diagonal entries satisfies:

∀i, j, H ij = n(e j -e i ) T L + e j . (4)
Since L + = X T X, we obtain:

H ij = n(x j -x i ) T x j .
We deduce the mean commute time between nodes i and j:

C ij = H ij + H ji = n||x i -x j || 2 .
In view of (2), the mean hitting time of node j from steady state is:

h j = 1 n n i=1 H ij = n||x j || 2 .
Cosine similarity. Observe that:

nx T i x j = h j -H ij = h i -H ji .
Let S ij = cos(x i , x j ). This is the cosine-similarity between nodes i and j. We have:

S ij = h j -H ij h i h j = h i -H ji h i h j ,
that is

S ij = h i + h j -C ij 2 h i h j . (5)
Thus the cosine-similarity between any vectors x i , x j can be interpreted in terms of the mean commute time between the corresponding nodes i, j relative to their mean hitting times.

Random walk with weights

In this section, we introduce a modified version of the random walk, that takes the node weights into account.

Recall that all weights are assumed positive. We denote by |w| = n i=1 w i the total node weight.

Random walk. We modify the random walk as follows: the transition rate from node i to node j is now A ij /w i . Thus the walker stays at node i an exponential time with parameter d i /w i , then moves from node i to node j with probability P ij . Observe that the previously considered random walk corresponds to unit weights. We get a continuous-time Markov chain with generator matrix -W -1 L, with W = diag(w), and stationary distribution π = w/|w|.

Hitting times. Let H ij be the mean hitting time of node j from node i. Observe that H ii = 0.

Proposition 3

The matrix H satisfies:

LH = we T -|w|I. (6)
Proof. We have H ii = 0 while for all i = j,

H ij = w i d i + n k=1 P ik H kj .
Thus the matrix (I -P )H -D -1 we T is diagonal. Equivalently, the matrix LH -we T is diagonal. Since e T L = 0, this diagonal matrix is -|w|I.

Proposition 4

The solution H to equation [START_REF] Dhillon | Kernel k-means: spectral clustering and normalized cuts[END_REF] with zero diagonal entries satisfies: ∀i, j, H ij = |w|(e j -e i ) T L + (e j -π).

Proof. The matrix M = we T -|w|I satisfies e T M = 0 so the seeked solution is of the form:

H = L + (we T -|w|I) + eh T ,
for some n-dimensional vector h. Thus,

H ij = |w|e T i L + (π -e j ) + h j .
Since H jj = 0, we get:

h j = -|w|e T j L + (π -e j ).
Let x be the center of mass of the vectors x 1 , . . . , x n :

x = Xπ = n i=1 π i x i .
Since L + = X T X, we obtain:

H ij = |w|(x j -x i ) T (x j -x). (7)
Thus the mean hitting times are the same as without node weights, up to the multiplicative constant |w| and the shift of the origin to the center of mass x of the vectors x 1 , . . . , x n .

In particular, the mean commute time between any nodes i and j depends on the weights through their sum only:

C ij = H ij + H ji = |w|||x i -x j || 2 .
The mean hitting time of node j from steady state is:

h j = n i=1 π i H ij = |w|||x j -x|| 2 .
Cosine similarity. Let S ij = cos(x i -x, x j -x). This is the cosine-similarity between nodes i and j. We obtain as above:

S ij = h i + h j -C ij 2 h i h j .
In particular, the relative mean commute times, as defined by ( 5), depend on the weights w 1 , . . . , w n through the center of mass x of the vectors x 1 , . . . , x n only.

Weighted spectral embedding

We now introduce the weighted spectral embedding. The generator matrix -W -1 L of the weighted random walk is not symmetric in general. Thus we consider the following normalized version of the Laplacian, we refer to as the weighted Laplacian:

L W = W -1 2 LW -1 2 .
This matrix is symmetric, positive semi-definite. In the particular case where W = D, this is known as the symmetric normalized Laplacian.

The spectral theorem yields

L W = Û Λ Û T , (8)
where Λ = diag( λ1 , . . . , λn ) is the diagonal matrix of eigenvalues of L W , with 0 = λ1 < λ2 ≤ . . . ≤ λn , and Û = (û 1 , . . . , ûn ) is the matrix of corresponding eigenvectors, with Û T Û = I and û1 = √ π. We have the following explicit expression for the pseudo-inverse of the weighted Laplacian: Proposition 5 The pseudo-inverse of L W is:

L + W = W 1 2 (I -eπ T )L + (I -πe T )W 1 2 . ( 9
)
Proof. Let M be the matrix defined by the right-hand side of [START_REF] Kerdprasop | Weighted k-means for density-biased clustering[END_REF]. Using the fact that Le = 0, we get:

L W M L W = W -1 2 LL + LW -1 2 , = W -1 2 L + W -1 2 = L W ,
which proves that M is the pseudo-inverse of L W .

Generalized eigenvalue problem. Let V = W -1 2 Û . We have:

LV = W V Λ, with V T W V = I.
Thus the columns v of the matrix V are solutions to the generalized eigenvalue problem:

Lv = λW v, (10)
with corresponding eigenvalues λ = λ1 , . . . , λn . The first column, associated to the eigenvalue λ1 = 0, satisfies v ∝ e, while the others satisfy w T v = 0.

Spectral embedding. Let Y = √ Λ + Û T W -1 2
. The columns y 1 , . . . , y n of the matrix Y define an embedding of the nodes, we refer to as the weighted spectral embedding. As for the regular spectral embedding, the first component of each vector y 1 , . . . , y n is equal to 0. Since Y w = 0, the center of mass of y 1 , . . . , y n lies at the origin:

n i=1 w i y i = 0.
The Gram matrix of Y is:

Y T Y = W -1 2 Û Λ+ Û T W -1 2 = W -1 2 L + W W -1 2 .
In view of Proposition 5,

y T i y j = e T i W -1 2 L + W W -1 2 e j , = (e i -π) T L + (e j -π) T , = (x i -x) T (x j -x).
Thus the considered weighted spectral embedding is equivalent to the regular spectral embedding, shifted so that the origin is the center of mass x. In particular, the distances between vectors in the embedding space can be interpreted in terms of mean hitting times of the random walk, as shown in Section 4.

A mechanical system

Consider the mechanical system consisting of n point particles of respective masses w 1 , . . . , w n sliding along a bar without friction. Particles i and j are linked by a spring satisfying Hooke's law with stiffness A ij .

Eigenmodes. Assume that the bar has a uniform circular motion with angular velocity ω around some fixed axis. We denote by v 1 , . . . , v n the locations of the particles along the bar, with the axis taken as the origin. By Newton's second law of motion, the system is in equilibrium if and only if ∀i = 1, . . . , n,

n j=1 A ij (v j -v i ) = -w i v i ω 2 , that is Lv = ω 2 W v.
If v = 0, then v is a solution to the generalized eigenvector problem [START_REF] Lovász | Random walks on graphs[END_REF] with eigenvalue λ = ω 2 . We refer to these equilibrium states as the eigenmodes of the mechanical system. The first eigenmode v ∝ e, for ω 2 = 0, corresponds to the absence of motion. The other eigenmodes give the possible angular velocities of the system, equal to the square roots of the eigenvalues λ2 , . . . , λn of L W . Any such eigenmode v satisfies w T v = 0, meaning that the center of mass of the system is at the origin.

Potential energy. The mechanical potential energy of the system in any state v is:

1 2 v T Lv.
If v is an eigenmode of the mechanical system, this is equal to:

λ 2 v T W v.
As v T W v is the moment of inertia of the system and λ = ω 2 is the square of the angular velocity, this corresponds to the angular kinetic energy. For a unit moment of inertia v T W v = 1, we obtain λ = v T Lv, so that the eigenvalues of the weighted Laplacian L W can be viewed as (twice) the levels of energy of the eigenmodes, for unit moments of inertia. The weighted spectral embedding reduced to the k first eigenvectors of L W can then be interpreted as that induced by the k eigenmodes of lowest potential energies of the mechanical system, for unit moments of inertia.

Dirichlet problem. For any i = j, assume the positions of the point particles i and j are set to 1 and 0, respectively. Let v be the vector of positions at equilibrium, in the absence of rotation. By Newton's first law of motion,

Lv = α(e i -e j ),
for some constant α equal to the force F exerted on both i and j (in opposite directions). This force does not depend on the masses of the point particles.

The solution to this Dirichlet problem is:

v = αL + (e i -e j ) + βe,
for some constant β. Using the fact that v i = 1 and v j = 0, we get:

v k = (e k -e j ) T L + (e i -e j ) (e i -e j ) T L + (e i -e j ) = (x k -x j ) T (x i -x j ) ||x i -x j || 2 and α = 1 ||x i -x j || 2 .
Observe in particular that v k ∈ [0, 1] for all nodes k. The mean hitting time of node j from node i by the random walk, given by ( 7), satisfies:

H ij = |w| F v,
where v is the center of mass of the system:

v = n k=1 π k v k .
By symmetry, we have:

H ji = |w| F (1 -v).
We deduce the mean commute time between nodes i and j:

C ij = H ij + H ji = |w| F .
This symmetry in the solutions to the Dirichlet problem explains why, unlike the mean hitting times, the mean commute times depend on the weights through their sum only. The mean commute time between two nodes of the graph is inversely proportional to the force exerted between the two corresponding point particles of the mechanical system, which is independent of the particle masses.

An electrical network

Consider the electrical network induced by the graph, with a resistor of conductance A ij between nodes i and j and a capacitor of capacitance w i between node i and the ground. The move of electrons in the network is precisely described by the random walk defined in Section 4.

Eigenmodes. Let v(t) be the vector of electric potentials at time t, starting from some arbitrary initial state v. By Ohm's law,

∀i = 1, . . . , n, w i dv i (t) dt = n j=1 A ij (v j (t) -v i (t)), that is W dv(t) dt = -Lv(t).
The solution to this differential equation is:

v(t) = e -W -1 Lt v.
If the initial state v is a solution to the generalized eigenvector problem [START_REF] Lovász | Random walks on graphs[END_REF], we obtain:

v(t) = e -λt v.
Since the eigenvectors of L W form a basis of R n , any initial state v can be written as a linear combination of solutions to the generalized eigenvector problem, we refer to as the eigenmodes of the electrical network. The first eigenmode v ∝ e, for λ = 0, corresponds to a static system, without discharge. The other eigenmodes give the possible discharge rates of the system, equal to the eigenvalues λ2 , . . . , λn of L W . Any such eigenmode v satisfies w T v = 0, meaning that the total charge accumulated in the capacitors is null.

Energy dissipation. The energy dissipated by the resistors for the vector of electric potentials v is:

1 2 v T Lv.
If v be an eigenmode of the electrical network, this is equal to

λ 2 v T W v.
Observing that 1 2 v T W v is the electrical potential energy of the system, we deduce that λ can be viewed as the energy dissipated by the resistors for a unit electric potential energy. In particular, the weighted spectral embedding reduced to the k first eigenvectors of L W can be interpreted as that induced by the k eigenmodes of lowest energy dissipation of the electrical network, for unit electric potential energies. Dirichlet problem. For any i = j, assume the electric potentials of nodes i and j are set to 1 and 0, respectively. Let v be the vector of electric potentials at equilibrium. We have:

Lv = α(e i -e j ),
for some constant α equal to the current flowing from i to j. This Dirichlet problem is the same as for the mechanical network, and thus the same results apply. In particular, we get v k ∈ [0, 1] for all nodes k, and the current between i to j is:

α = 1 ||x i -x j || 2 .
This is the intensity of the current I generated by a unit potential difference betweeen i and j. Its inverse is known as the effective resistance between i and j. The mean hitting time of node j from node i by the random walk satisfies:

H ij = q I ,
where q is the total charge accumulated in the capacitors:

q = n k=1 w k v k .
Observe that this expression for the mean hitting time can be seen as a consequence of Little's law, as I is the intensity of positive charges entering the network and q the mean number of positive charges accumulated in the network. By symmetry, the total charge accumulated in the capacitors when the respective electric potentials of i and j are set to 0 and 1 is:

n k=1 w k (1 -v k ) = |w| -q,
so that:

H ji = |w| -q I .
We deduce the mean commute time between nodes i and j:

C ij = H ij + H ji = |w| I .
Again, the symmetry in the solutions to the Dirichlet problem explains why the mean commute times depend on the weights through their sum only. The mean commute time between two nodes of the graph is proportional to the effective resistance between the two corresponding points of the electrical network, which is independent of the capacitors.

Experiments

We now illustrate the results on a real dataset. The considered graph is that formed by articles of Wikipedia for Schools 1 , a selection of articles of Wikipedia for children [START_REF] West | Wikispeedia: An online game for inferring semantic distances between concepts[END_REF]. Specifically, we have extracted the largest connected component of this graph, considered as undirected. The resulting graph has 4,589 nodes (the articles) and 106,644 edges (the hyperlinks between these articles). The graph is undirected and unweighted.

Both the dataset and the Python code used for the experiments are available online 2 .

Global clustering. We first apply k-means clustering 3 to the following embeddings of the graph, each in dimension k = 100:

• the regular spectral embedding, X, restricted to rows 2, . . . , k + 1, say X;

• the shifted spectral embedding, X -Xπ1 T , where π = w/|w| and 1 is the k-dimensional vector of ones;

• the weighted spectral embedding, Y , restricted to rows 2, . . . , k + 1, say Ŷ .

1 https://schools-wikipedia.org 2 https://github.com/tbonald/spectral_embedding 3 The algorithm is k-means++ [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF] 100 random initializations.

Here the vector of weights w is taken equal to d, the vector of internal node weights. In particular, the weighted spectral embedding is that following from the spectral decomposition of the normalized Laplacian, D -1 2 LD -1 2 . Observe that the first row of each embedding X and Y is equal to zero and thus discarded. Each embedding is normalized so that nodes are represented by k-dimensional unitary vectors. This is equivalent to consider the distance induced by the cosine similarity in the original embedding. In particular, the regular spectral embedding and the shifted spectral embedding give different clusterings.

Tables 1 and2 show the top articles of the clusters found for each embedding, when the number of clusters is set to 20, with the size of each cluster. The selected articles for each cluster correspond to the nodes of highest degrees among the 50% closest nodes from the center of mass of the cluster in the embedding space, with unit weights for the regular spectral embedding and internal node weights d for the shifted spectral embedding and the weighted spectral embedding. The first observation is that the three embeddings are very different. The choice of the Laplacian (regular or normalized) matters, because the dimension k is much smaller than the number of nodes n (recall that the shifted spectral embedding and the weighted spectral embedding are equivalent when k = n). The second observation is that the weighted spectral embedding seems to better capture the structure of the graph. Apart from the first cluster, which is significantly larger than the others and thus may contain articles on very different topics, the other clusters look meaningful. The regular spectral embedding puts together articles as different as Meteorology, British English and Number, while the shifted embedding groups together articles about Sanskrit, Light and The Simpsons, that should arguably appear in different clusters.

Selective clustering. We are now interested in the clustering of some selection of the articles. We take the 667 articles in the People category. A naive approach consists in considering the subgraph induced by these nodes. But this is not satisfactory as the similarity between articles in the People category depends strongly on their connections through articles that not in this category. Indeed, the subgraph of nodes in the People category is not even connected. Our approach consists in assigning a multiplicative factor of 10 to articles in the People category. Specifically, we set w i = 10 × d i if article i belongs to the People category, and w i = d i otherwise. We compare the three previous embeddings, for this vector of weights.

Tables 3 and4 show the top articles in the People category for the 20 clusters found for each embedding. The selected articles for each cluster correspond to the nodes of highest degrees in the People category. We also indicate the number of articles in the People category in each cluster. Observe that the last cluster obtained with the regular spectral embedding has no article in the People category. Again, the impact of weighting is significant. The weighted spectral embedding, which is adapted to the People category, seems to better capture the structure of the graph. Except for the first, which is much larger than the others, the clusters tend to group together articles of the People category that are closely related.

Table 1 :

 1 Global clustering of Wikipedia for Schools by weighted spectral embedding.

Table 3 :

 3 Selective clustering of Wikipedia for Schools by weighted spectral clustering.

	Count Top articles
	228	William Shakespeare, Pope John Paul II
	60	Jorge Luis Borges, Rabindranath Tagore
	55	Elizabeth II of the UK, Winston Churchill, Tony Blair
	49	Charles II of England, Elizabeth I of England
	48	Ronald Reagan, Bill Clinton, Franklin Roosevelt
	25	Alexander the Great, Genghis Khan, Muhammad
	24	Adolf Hitler, Joseph Stalin, Vladimir Lenin
	23	Napoleon I, Charlemagne, Louis XIV of France
	22	Jesus, Homer, Julius Caesar, Virgil
	22	Aristotle, Plato, Charles Darwin, Karl Marx
	21	George W. Bush, Condoleezza Rice, Nelson Mandela
	18	Elvis Presley, Paul McCartney, Bob Dylan
	15	Isaac Newton, Galileo Galilei, Ptolemy
	13	Albert Einstein, Gottfried Leibniz, Bertrand Russell
	10	Pete Sampras, Boris Becker, Tim Henman
	9	William Thomson, 1st Baron Kelvin, Humphry Davy
	8	Carolus Linnaeus, James Cook, Gerald Durrell
	8	Bill Gates, Richard Stallman, Ralph Nader
	5	Floyd Mayweather Jr., Lucy, Lady Duff-Gordon
	4	Vasco da Gama, Idit Harel Caperton, Reza Shah

We have proposed a novel spectral embedding of graphs that takes node weights into account. We have proved that the dimensions of this embedding correspond to different configurations of an equivalent physical system, either mechanical or electrical, with node weights corresponding to masses or capacitances, respectively.

A practically interesting consequence of our work is in the choice of the Laplacian, when there are no other information on the node weights than the graph itself. Thanks to weighted spectral embedding, we see that the two versions of the Laplacian, regular and normalized, correspond in fact to two relative importance of nodes, given respectively by unit weights and internal node weights.