Rafael Angarita
email: rafael.angarita@isep.fr

Nikolaos Georgantas
email: nikolaos.georgantas@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Social Middleware for Civic Engagement

Keywords: Citizen-sensor-networks, Citizen empowerment, Civic IoT, Civic technology, Middleware, Cyber-Physical-Social Systems

Civic engagement refers to any collective action towards the identification and solving of public issues. Current civic technologies are traditional Web-or mobile-based platforms that make difficult, or just impossible, the participation of citizens via different communication technologies. Moreover, connected objects sensing physical-world data can nourish participatory processes by providing physical evidence to citizens; however, leveraging these data is not direct and still a time-consuming process for civic technologies developers. This paper introduces the concept of social middleware for civic engagement. Social middleware allows citizens to engage in participatory processessupported by civic technologies-via their favorite communication tools, and to interact not only with other citizens but also with relevant connected objects and software platforms. The mission of social middleware goes beyond the connection of all these heterogeneous entities. It aims at easing the implementation of distributed applications oriented toward civic engagement by featuring dedicated built-in services.

I. INTRODUCTION

Civic engagement, as defined by the American Psychological Association 1 , is any "individual and collective action designed to identify and address issues of public concern." It is all about caring and working to address issues that concern a community, from a local to a global scale. Citizens engage by collectively bringing new ideas and solutions, sharing those ideas and discussing and improving them, choosing the ones they prefer and putting them in action. Examples of civic engagement are numerous. They range from reporting wild water storage that contributes to the proliferation of mosquitoes, building maps of marginalized urban areas, deciding what to do with a budget allocated to a local community, to campaigning and voting in national general elections.

Pervasive digital technologies are considered to be a significant enabler of civic engagement. They pave the way for more direct democratic processes by facilitating the online, direct participation/engagement of people in government/community actions. Further, the design of the supporting socially-oriented digital technologies has become a major research topic following the mass adoption of social networking. The research in the area is broad, and is often multi-disciplinary, crossdisciplinary and even trans-disciplinary [START_REF] Kukka | Transdisciplinary approaches to urban computing[END_REF], [START_REF] Tsvetkova | Understanding human-machine networks: A cross-disciplinary survey[END_REF]. The research in the digital sciences spans the full software stack, from networking up to user interfaces. This includes middlewarerelated research, which is primarily concerned with either 1 http://www.apa.org/education/undergrad/civic-engagement.aspx analyzing social relations across social networks [START_REF] Gupta | Mobisoc: A middleware for mobile social computing applications[END_REF], [START_REF] Chen | Socaware: A middleware for social applications in online social networks[END_REF], [START_REF] Mehrotra | Sensocial: A middleware for integrating online social networks and mobile sensing data streams[END_REF] or enforcing privacy [START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF], [START_REF] Alves | Anonylikes: Anonymous quantitative feedback on social networks[END_REF], [START_REF] Koll | Soup: An online social network by the people, for the people[END_REF].

Despite the above trends, digital technologies supporting inclusive participation toward civic engagement remains a major challenge -even at a local scale. Understanding the motivations for public engagement has been and is still the focus of various studies, especially in the HCI domain (e.g., [START_REF] Lehner | Civic engagement meets pervasive gaming: Towards long-term mobile participation[END_REF], [START_REF] Harding | HCI, civic engagement & trust[END_REF], [START_REF] Kim | Factful: Engaging taxpayers in the public discussion of a government budget[END_REF], [START_REF] Salim | Urban computing in the wild: A survey on large scale participation and citizen engagement with ubiquitous computing, cyber physical systems, and internet of things[END_REF], [START_REF] Boehner | Data, design and civics: An exploratory study of civic tech[END_REF], [START_REF] Carton | Citizen-sensor-networks to confront government decision-makers: Two lessons from the netherlands[END_REF], [START_REF] May | The design of civic technology: factors that influence public participation and impact[END_REF], [START_REF] Palacin-Silva | The role of gamification in participatory environmental sensing: A study in the wild[END_REF]). However, studies concentrate on very specific use cases. Similarly, supporting digital technologies result in a specific function or platform, which limits their impact with respect to fostering massive scale engagement. It is our vision that middleware has a significant role to play. We argue that social middleware is the necessary building block to enable and foster interactions among the many relevant "civic actors" in a way that does not prevent participation of diverse actors due to the use of heterogeneous and distributed technologies, but rather reconciles them. Our work shares consideration with the Internet of People vision that revisits the Internet to integrate people and their devices as first class network entities [START_REF] Conti | The internet of people (iop): A new wave in pervasive mobile computing[END_REF]. We revisit the middleware paradigm so that it integrates interaction with people and technical objects.

We define social middleware as middleware focused on both (1) allowing people to interact for the sake of civic engagement, and (2) enhancing the quality of participation. To this end, social middleware must support:

• Civic social networking. Social middleware lets people interact, whatever technologies they use. Social middleware also accounts for the blending of the physical and virtual worlds in which connected objects and software platforms are vehicles that allow informing but also enact civic engagement (e.g., using public displays to gather and share information, leveraging crowdsensing to map environmental issues). Ultimately, interactions mediated by social middleware, whether between humans, between humans and machines, or between machines are all human-centered, building upon online social network services. • Incentives to enhance civic engagement. The goal of social middleware is to enhance the quality of civic engagement. Accordingly, since it coordinates civic technologies and citizens, social middleware can support additional incentives to those provided by the underlying civic technologies. Incentives can be in the form of recognition of citizens for their participation or by gamifying the participation process within the particular technologies citizens use. Further, every actor (spanning individuals, communities, governments but also platforms and connected objects) involved in social middleware ecosystems must adhere to a set of data privacy and security policies that ensure ethical participation. For instance, complying to the GDPR that is now enforced by EC is one obvious requirement. The paper makes the following contributions towards the design of social middleware:

• Section II surveys the diverse digital technologies enabling online civic engagement, and the related literature, from which we derive the essential requirements for social middleware. • Section III introduces the key concepts underlying social middleware, that is, enabling civic social networks across the many relevant civic actors that include citizens but also digital services associated with software platforms and the Internet of Things. • Section IV introduces the social middleware bot (sm-bot) concept, which features social bots that enable sociallydriven interactions among the relevant civic actors. To do so, sm-bots overcome the heterogeneity of the underlying digital platforms and implement socially-enhanced interactions as promoted by online social networks. • Further to enabling socially-driven interactions among the many relevant actors, the social middleware features functions dedicated to fostering the engagement of the target actors, while dealing with security and privacy. Section V surveys such functions where we build upon the civic technologies state of the art. Finally, Section VI concludes with our ongoing and future work towards the implementation of the social middleware solution.

II. TECHNOLOGIES ENABLING ONLINE CIVIC ENGAGEMENT

There is no doubt that digital technologies have changed, and will keep changing, the fabric of society. They have transformed the way humans interact, consume information and, as a consequence, influence the physical world. This especially holds for civic engagement for which digital technologies hold the promise of sustaining engagement at a very large scale [START_REF] Dubow | Civic engagement: How can digital technologies underpin citizen-powered democracy?[END_REF].

A. Social media, social networks, and messaging applications

Social media allow people to easily share their ideas, debate with others, organize, collaborate and stay in contact. It is no surprise that social media increasingly play a major role in civic engagement, as they support the growth of large digital networks of activists, on the technological as well as on the economic level [START_REF] Dahlgren | Media and political engagement[END_REF]. Two iconic instances where millions of people organized and mobilized using social media are the Arab Spring revolutions and the Occupy movement [START_REF] Poell | Social media and activist communication[END_REF]. In the Arab Spring revolutions, activists used Facebook and text messaging to share reports on the events in the streets, while Twitter played a vital role in the transnational communication on these revolutions. By reporting on the demonstrations using major social media platforms such as Twitter, YouTube and Facebook, activists of the Occupy movement created a sense of the collective [START_REF] Kavada | Creating the collective: social media, the occupy movement and its constitution as a collective actor[END_REF].

Along with social media, messaging applications such as email, SMS, WhatsApp, Telegram and Messenger play an important role in engaging and mobilizing citizens. For example, researchers showed that text message reminders via SMS produce a statistically significant increase in the likelihood of voting [START_REF] Dale | Don't forget to vote: text message reminders as a mobilization tool[END_REF].

Despite the plethora of social media and messaging application offers, people using a particular platform cannot easily interact with people using a different one. To overcome this limitation, we have proposed USNB to enable users to meet and interact beyond the boundary of their particular communication technologies [START_REF] Angarita | USNB: Enabling universal online social interactions[END_REF]. USNB is a middleware that enables interoperability across heterogeneous and distributed social media as well as messaging applications, to achieve "social interoperability".

Still, supporting civic engagement at scale, from informing to empowering to organizing, remains a challenge, which Civic Technologies aim at tackling.

B. Civic technologies

In contrast to general-purpose social media, civic technologies (aka Civic Tech) are conceived with the specific purpose of supporting civic engagement. They aim at enhancing the relationships between citizens and their governments by providing mechanisms to improve collaborative actions and participation in public decisions.

Various Civic Tech platforms have emerged over the last decade. They may be classified according to the key function they support [START_REF] Ghorayeb | Can Civic Tech Save Democracy? How Technology is Renewing Civic Engagement[END_REF]: [START_REF] Kukka | Transdisciplinary approaches to urban computing[END_REF] connecting & informing to communicate with the citizens, (2) contributing & acting to empower people, and (3) organizing & managing to change the way institutions work. Social media often serve the first function. A wellknown example belonging to the second category is Make.org (https://make.org) that is a petition platform enabling users to launch campaigns and collect signatures. Most platforms of the third category adopt the software as a service paradigm. One well-known example is NationBuilder (https://nationbuilder. com/) that is dedicated to the management of election campaigns.

In the above context, we have introduced the AppCivist service-oriented platform so as to enable the assembly of thirdparty Civic Tech services that are the most relevant to support a given civic action [START_REF] Holston | Engineering Software Assemblies for Participatory Democracy: The Participatory Budgeting Use Case[END_REF]. AppCivist enables the configuration of workflows oriented toward citizen participation, which consist of all or part of the following set of operations: proposal making, collaborative proposal editing, deliberation, voting, and implementation. All the operations are in particular leveraged in the AppCivist-PB customization of the platform, which focuses on enabling the online participation to participatory budgeting campaigns [START_REF] Parra | Expanding the Design Space of ICT for Participatory Budgeting[END_REF].

With the exception of AppCivist, most Civic Tech platforms concentrate on one function of civic engagement, thereby leaving their smooth inter-working up to the end-users. Further, studies show that citizens must be provided with adequate data access [START_REF] Boehner | Data, design and civics: An exploratory study of civic tech[END_REF], including leveraging appropriate data sources [START_REF] Taylor | Data-in-place: Thinking through the relations between data and community[END_REF], [START_REF] Carton | Citizen-sensor-networks to confront government decision-makers: Two lessons from the netherlands[END_REF]. This in particular calls for adequate connection with the physical world.

C. IoT & CPSS

We believe that the Internet of Things (IoT) has a significant role to play in Civic Engagement. By blending the physical and virtual worlds, the IoT enables aggregating knowledge that informs citizens' actions. Further considering the IoT ability to sense and act upon the physical world, it creates new interaction opportunities for the citizens.

Mobile phone sensing illustrates well the added-value of the IoT to civic engagement. Citizens are increasingly adopting participatory sensing technologies as they allow them to collect and share data about the environment [START_REF] Balestrini | IoT community technologies: leaving users to their own devices or orchestration of engagement?[END_REF], [START_REF] Issarny | Dos and don'ts in mobile phone sensing middleware: Learning from a large-scale experiment[END_REF], [START_REF] Lefèvre | Matching Technological & Societal Innovations: The Social Design of a Mobile Collaborative App for Urban Noise Monitoring[END_REF]. The emergence of CPSS -Cyber-Physical-Social-Systems-is another major illustration of the role that the IoT is playing in the development of social systems in general, and civic engagement in particular. CPSS stresses the human-centric vision for computing systems, which must provide contextually relevant abstractions to people out of the knowledge gathered from the virtual, physical and social worlds [START_REF] Sheth | Physical cyber social computing for human experience[END_REF], [START_REF] Zeng | A survey: Cyber-physicalsocial systems and their system-level design methodology[END_REF].

This trend is questioning the design of the overall stack of Internet-based computing. The Internet of People vision in particular stresses the need to revisit the current Internet paradigm where people and their devices become active elements of the Internet and today's Internet becomes its core [START_REF] Conti | The internet of people (iop): A new wave in pervasive mobile computing[END_REF]. We share this vision, for which we advocate that a social middleware is sorely missing. Social middleware will provide the abstractions associated with these diverse "social entities" and their interactions, together with key functions supporting engagement at scale. This further raises the question of proper interactions with such social entities.

D. Chat, Chatter & Social bots

Social bots, an evolution of the early software robots (aka bots) as part of the planetary-scale social networking, appears as a powerful technology solution to address interaction with social entities. A social bot is a type of conversational social agent that can interact with humans via any digital technology. Social bots are developed and deployed with specific goals by software engineers. For example, a Twitter social bot can twit a predefined message with a corresponding hashtag; a Whatsapp social bot can spam users with a message promoting a product; or a Facebook social bot can add random people as friends to later expose them to some content. Moreover, in the last years we have seen a rapid increment of social bots for automated customer service.

Because they impersonate humans in a way that may be un-noticed, social bots may be quite harmful [START_REF] Ferrara | The rise of social bots[END_REF]. Still, social bots may also work for the greater good. For example, Crisis Text Line (www.crisistextline.org) is a Facebook Messenger and SMS social bot offering a hotline for people experiencing mental health crises. It asks people the details of the crises, before handing the control of the conversation to a trained human counselor. Another example is that of early adopter nonprofits 2 , which have used bots to automate civic engagement, such as helping citizens register to vote, contact their elected officials, and elevate marginalized voices and issues.

For better or for worse, social bots thrive in political and civic engagement scenarios [START_REF] Shao | The spread of fake news by social bots[END_REF]. For example, Resistbot (resist.bot) is a social bot that lets anyone turn a text message into a fax to their representatives and senators. As of July 2017, more than 4 million faxes have been sent using the platform. Resistbot is present on Facebook Messenger, Twitter, Telegram and SMS. Social bots are increasing their presence in social network sites and messaging applications, since they have the potential of reaching millions of people and especially young people who otherwise would remain apathetic to civic engagement. For example, RockEnrol-bot (www.rockenrol.org.nz) is a social bot created by a digital community in New Zealand whose mission is to inform and engage young voters.

We cannot ignore social bots in the development of civic engagement applications and they may indeed support and foster civic engagement. However, they must behave in a ethical way; to ensure this as well as leverage all the capabilities for civic engagement offered by the technologies surveyed in this section, we advocate that a middleware solution is essential.

III. THE SOCIAL MIDDLEWARE VISION

Social middleware builds upon the notion of civic social network that establishes a collaborative framework for civic engagement. The term has been coined by others such as in [START_REF] Antonin | Collaborative Multi-Perspective Urban Knowledge and Civic media[END_REF] to emphasize the need to customize collaborative frameworks for the sake of civic engagement. However, to the best of our knowledge, existing work is mainly focused on developing specific Civic Tech platforms for the collaborative production of urban knowledge.

Social middleware embraces a broader vision of civic social networks, that is, fostering collaboration among the relevant entities of a CPSS to engage in a collective action so as to solve some public issue. Social middleware introduces a set of abstractions that address the engagement and coordination of civic actors. Such abstractions can be leveraged by civicoriented applications. Going one step further, our definition of civic actors spans citizens, online digital services, and things liaising with the physical world. In particular, and in accordance with the general idea of the Actor-Network Theory [START_REF] Latour | Reassembling the social: An introduction to actor-networktheory[END_REF], which states that human and non-human actors should receive equal treatment and be described in the same terms, an actor involved in a civic-oriented application may be any relevant entity capable of sending and/or receiving data. It does not matter its language, the middleware protocol or syntax it uses, the knowledge it represents or its nature. All that counts is that an actor has an available Internet-based interface allowing interaction within the digital world. For illustration, we consider a public consultation about the implementation of measures to reduce the population exposure to the urban environmental pollution. A government or agency typically initiates and manages the consultation; it defines the timeline as well as presents the measures under consideration. The goal is to gather ideas and feedback from citizens. The participation may additionally benefit from thirdparty environmental knowledge such as participatory sensing applications (e.g., see [START_REF] Issarny | Dos and don'ts in mobile phone sensing middleware: Learning from a large-scale experiment[END_REF]). Further, citizens may want to be able to exchange about the measures that the government/agency envisions, bringing in their perspective as much as asking questions to know more. In this public consultation, citizens can elaborate proposals collaboratively and/or vote for them and visualize the voting results.

As Figure 1 illustrates, the public consultation builds a civic social network that leverages services from existing technology platforms: popular social networks and simpler communication means such as email allow the citizens to get informed and interact, a web-based text editor enables collaborative proposal editing, a crowdsensing and a pollution monitoring service provide access to observations about the environmental pollution, an advanced visualization tool offers ways to map and visualize the available knowledge, and an existing online voting service enables gathering the citizens' votes.

Social middleware introduces the sm-bot concept to bridge seamlessly the civic actors that populate the above thirdparty technology platforms, while fostering civic engagement as part of civic-oriented applications. That is, sm-bots serve creating a civic social network overlay. The sm-bot is the core middleware component that implements built-in functions for socially-enhanced interoperability within digital platforms, as well as for supporting civic-engagement. The implementation of a civic-oriented application then relies on customizing smbots according to the specifics of the application, and deploy-ing the instances of the sm-bots in the relevant platforms. In practice and as depicted in Figure 2, the coordination of sm-bots as part of a civic-oriented application generates the coordination of the civic actors that are connected through the underlying platforms. Fig. 2: Social middleware enacts civic social networks through the sm-bot abstraction that bridges technology platforms enabling online civic engagement.

IV. SM-BOTS ENACTING CIVIC SOCIAL NETWORKS

Social middleware brings to applications the abstraction of civic actor so as to ease the coordination of people as well as of connected digital entities toward civic engagement. As we survey in Section II, the online involvement of people within civic actions is primarily via Online Social Network Services. In particular, most civic technologies rely on some OSNS for user interactions. However, we argue that social middleware must enable people to interact across heterogeneous OSNSs so that each individual may use the most convenient tool, and thereby prevent the well-known platform lock-in issue.

A. Interoperability across Online Social Networks

Social middleware builds upon our previous work on the Universal Social Network Bus (USNB) 3 enabling users to interact across OSNSs, where an OSNS may range from a base email platform to a full-fledged online social network supporting various social interaction services such as direct messaging or indirect wall posting [START_REF] Angarita | USNB: Enabling universal online social interactions[END_REF], [START_REF] Angarita | Leveraging the service bus paradigm for computer-mediated social communication interoperability[END_REF].

Figure 3 illustrates how USNB enables social interactions among four users of four different OSNSs, through the implementation of a multi-party, distributed mediator [START_REF] Angarita | Universal social network bus: Towards the federation of heterogeneous online social network services[END_REF]. The (multi-party) USNB mediator embeds a USNB persona p x for each of the OSNSs Ω x to connect them within the "universal social network". The personae are the main components of USNB and they interact with each other through the USNB reference social interaction service s, that is, a persona implements the conversion logic between the OSNS's social interaction service and the USNB's reference social interaction service.

The linking of USNB personae allows users to interact independently of the OSNS they each belong to, including sharing their profiles across the OSNSs. Figure 4 illustrates the case of four users: u 1,2,3,4 of the OSNSs Ω i,j,k,l , respectively. USNB creates synthetic profiles for each of the users in all the OSNSs where they do not have a profile. For example, u 1 has a profile in Ω i , while USNB creates synthetic profiles for u 1 in Ω j , Ω k and Ω l . The synthetic profiles, which are represented as dotted circles in the figure, enable (remote) users of distinct OSNSs to interact via the USNB personae. As a result, all the users in the USNB federation of heterogeneous OSNSs can interact. For example, u 1 and u 4 are connected and may interact, while the interactions in USNB are transparent for both of them: From u 1 's perspective, interactions happen only via Ω i ; from u 4 's perspective, only via Ω l ; in effect, u 1 and u 4 interact with synthetic profiles managed by the personae p i and p l .

The sm-bot inherits from the USNB persona concept regarding the embedded support for interoperability across online social network services, and thereby enables the creation of a civic social network overlay over existing OSNSs. As a result, the sm-bot implements a reference social interaction service, which derives from the one of USNB and relates to ( [START_REF] Angarita | USNB: Enabling universal online social interactions[END_REF]): profile management and social interactions.

B. Socially-enhanced Interactions with Civic Actors

In addition to leveraging online social networking, civicoriented applications depend on diverse civic technologies to support the involved actions, such as informing, organizing, managing, etc. Also, the IoT is a valuable network to gather information from and act upon the physical world. Hence, social middleware creates a civic social network overlay over OSNSs complemented with relevant civic tech platforms and IoT networks. Still, a key challenge is how to support the interactions with these diverse digital entities as part of a civic social network. We argue that these interactions should be socially-enhanced, that is, adaptive to the interaction context and particularly to the civic actors -people, software services, things-that are involved.

Socially-enhancing the interactions with digital entities closely relate to the vision of "speaking objects" [START_REF] Lippi | Coordinating distributed speaking objects[END_REF], where objects are capable of understanding different contexts in order to communicate in an appropriate and conversational way, as opposed to just transmitting and receiving raw data.

We highlight the following considerations associated with the sm-bot support for socially-enhanced interactions:

• Actor type and characteristics: The absence of nonverbal cues during social interactions in the virtual sphere can prevent participants from detecting demographic, personality, and interpersonal characteristics of others. According to [START_REF] Petty | The elaboration likelihood model of persuasion[END_REF], such an absence of nonverbal cues reduces the capacity of persuasion. Even though this study focuses on human-to-human interactions in computer-mediated communication, it informs how to foster meaningful interactions among all kind of actors when concerned with persuasion and engagement. Additionally and according to research on theories of computer-mediated communication [START_REF] Walther | Computer-mediated communication: Impersonal, interpersonal, and hyperpersonal interaction[END_REF], [START_REF]Theories of computer-mediated communication and interpersonal relations[END_REF], it may be preferable to use an impersonal communication style in some cases, while using a more personal communication style in other cases. Therefore, sm-bots must be aware of the type and characteristics of the actors they interact with. For example, sm-bots can learn the preferences and interests of human actors, as well as the information they decide to share, from their social networks' public profiles, and refine this knowledge overtime from the actual interactions. • Direct vs. group messaging: Direct messaging refers to one-to-one interactions between two actors knowing their respective identities; for example, sending emails to personal email addresses or communicating via Facebook direct messages. Group messaging refers to interactions between two or more actors who do not necessarily know the identities of the other members of the group. Group messaging can be private among the group members, such as in most mailing lists and Facebook group conversations, or public such as in Twitter's tweets. Sm-bots must account for privacy aspects such as how and which information they should diffuse. • Communication technologies usage: Different communication technologies can influence how people use them, particularly regarding the related synchronization. For example, a single interaction by email can be comprehensive, while the same interaction may involve a sequence of messages in the case of instant messaging. Following the above, the sm-bot enables adaptive sociallyenhanced interactions, which may be parameterized as follows within the application:

• Conversation modality: This covers the full spectrum of interaction modalities offered by today's technologies -from a binary-encoded message to a conversational agent-and the specific realization depends on the endpoints. Considering our consultation example, the Facebook sm-bot will engage the civic actors in Facebook using a conversational social bot that is considered more user-friendly. On the other hand, the contribution of the very same civic actor to a proposal writing will lead the Facebook sm-bot to send a binary-encoded message to the GDoc sm-bot. • Profile management: The sm-bots manage the profiles of the involved actors according to the specifics of the application but also -and as importantly-the features of the underlying platforms and the access control set by the actors. For instance, the Facebook sm-bot will have access to the Facebook profile that the end-user is willing to share; it will further autonomously enrich its knowledge based on the actions allowed by the end-user.

Similarly, the GDoc sm-bot will gather knowledge about the contributing users as allowed by them. • Interaction paradigm: Social middleware supports the traditional client-server and publish-subscribe interaction paradigms, which allows dealing with the spectrum of socially-enhanced interactions characterized above.

C. From Vision to Civic-oriented Distributed Systems

Our previous work on the development of the USNB solution provides us with the initial baseline solution to develop the sm-bot component enabling the creation of civic social networks. Still, enabling socially-enhanced interactions among the diverse actors -people, software services and thingscontributing to civic-oriented applications remains an open challenge. In the previous sections, we have outlined the resulting design principles for the sm-bot, and we are now investigating the following research questions toward the design and development of the actual sm-bot components:

• Sm-bot autonomous conversation manager: Sm-bots need to implement conversation with the civic actors of the related platforms. Such conversation should adapt to the context of the interaction as well as the profiles of the target actors. Designing this sm-bot capability is a longterm research challenge. We will investigate an initial design based on relevant state-of-the-art AI solutions, including existing frameworks for the management of conversational social bots. • Sm-bot interaction protocols: The design of sm-bot interaction protocols relates to core distributed system research and development. Hence, relying on known interaction paradigms and protocols, our research focuses on their social enhancement, starting with the resulting requirements upon the communication (e.g., temporality, openness, dependability, confidentiality, security, privacy, ethics, etc.). • Sm-bot synthesis: We are studying a Domain Specific Language associated with the core functions of the smbots, so as to ease the declarative specification of their mapping to the target platforms and further automate the synthesis of most of the sm-bots' concrete implementation.

V. FOSTERING CIVIC ENGAGEMENT

The social middleware core enacts the actor abstraction, where entities as diverse as people, things and software, may interact and coordinate toward some civic action. As presented in the previous section, a key feature of the social middleware is to create a civic social network overlay that implements socially-enhanced interoperability across the relevant digital platforms -online social networks, civic technologies, IoT. A remaining challenge for online civic engagement is to foster the participation of people. Obviously, providing people with access to digital tools that ease their online participation to some civic action is not sufficient to ensure that people will get involved. Analysis of the related state of the art then allows us to identify some supporting functions to be offered as part of the social middleware.

A. Supporting Intrinsic Motivation

Gamification is one of the famous approaches to motivate people to participate in activities. Gamification has been extensively studied over the last few years, with literature reviews of empirical studies investigating whether and how it is an effective approach [START_REF] Hamari | Does gamification work? -a literature review of empirical studies on gamification[END_REF]. However, it is quite challenging to assess the effectiveness of gamification independently of its application domain, especially in the context of civic engagement. Still, a review like the one reported in [START_REF] Morschheuser | Gamification in crowdsourcing: A review[END_REF] provides relevant insight, as it focuses on gamification in crowdsourcing, which is one of the main forms of e-participation. The empirical findings indicate that rankings seem to motivate users, while mixing several motivation affordances so as to target diverse groups is appealing even if not always successful. Due to the importance of participation in civic engagement, gamification design has been studied for this specific application context, e.g., [START_REF] Rehm | Dogood: examining gamification, civic engagement, and collective intelligence[END_REF], [START_REF] Palacin-Silva | The role of gamification in participatory environmental sensing: A study in the wild[END_REF]. The review in [START_REF] Hassan | Gamification of e-participation: A literature review[END_REF] concentrated on the literature about gamification of e-participation and found that points was the most commonly employed gamification design element. The study also highlights the potential negative impact of competitive gamification, which suggests to shift the focus from competition among users to among ideas.

Although gamification is often synonymous with rewards and implemented using points, the study in [START_REF] Nicholson | A RECIPE for Meaningful Gamification[END_REF] sheds light on the fact that there is another way to encourage behavior, that is, through building intrinsic motivation. In other words, the system should help users find their own motivation for engaging, which depends on [START_REF] Deci | Handbook of Self-Determintation Research[END_REF]: mastery (learning something), autonomy, and relatedness (learning about the others who are engaged). Similar recommendations are drawn in [START_REF] Suh | Enhancing user engagement through gamification[END_REF]. It is our view that implementing a participation process so that the participants may build intrinsic motivation is likely the most relevant approach in the context of civic engagement.

In general, engineering gamified software is a complex process, which further requires gathering experts from various disciplines -e.g., software engineering but also psychology, design- [START_REF] Morschheuser | How to design gamification? a method for engineering gamified software[END_REF]. Embedding supporting functions within the social middleware would be no exception. However, the principles of intrinsic motivation allow us to elicit the following base functions:

• Mastery: The participant must be able to acquire new knowledge in relation with the purpose of the civic action. By enabling interaction across actors, this is well supported by the social middleware core, i.e., the diverse types of actors -people, software services and things-are able to nurture each other's knowledge across time.

• Autonomy: The participants should feel that they remain in control, which primarily depends on the implementation of the upper layer application rather than the middleware functions. However, this also suggests that the participants must have the ability to set with which actors they are willing to interact as well as in which application actions they want to engage.

• Relatedness: This relates to the feeling of being part of a community -not being alone. This is well supported by the socially-enhanced interactions enabled by the social middleware core, while the civic-oriented application should foster as much as possible the virtual meeting of people as part of the civic actions they engage in. Of course, this should be implemented in a way that does not counterfeat the participant's autonomy.

B. Configuring the participation process

The actions underlying civic participation processes are well analyzed in the context of Civic Tech [START_REF] Holston | Engineering Software Assemblies for Participatory Democracy: The Participatory Budgeting Use Case[END_REF], [START_REF] Ghorayeb | Can Civic Tech Save Democracy? How Technology is Renewing Civic Engagement[END_REF]. They relate to: connecting with relevant actors, informing by giving access to relevant knowledge, contributing and acting by enabling collaboration toward joint proposal making, voting to reach decision, and ultimately implementing the outcome.

There exist various methods for involving the public in decision-making (e.g., see [START_REF] Petts | Evaluating methods for public participation: Literature review[END_REF] for a survey of methods and related assessment). However, a large part of the methods enabling the extended involvement of the participants are oriented toward physical meetings of rather small, yet representative, groups of people. Our objective with the social middleware is to enable civic actions at the larger Internet scale while building upon the practices of proven participation methods. In particular, existing guides to participation have suggested key principles for the selection of methods [START_REF] Petts | Evaluating methods for public participation: Literature review[END_REF]: (i) set clear objectives, (ii) identify and target all the relevant stakeholders, (iii) tailor the participation process according to the first two criteria, (iv) set out the process in an honest and understandable way, (v) ensure that the participation is timely and allow sufficient time, (vi) ensure that the process is credible, (vii) ensure that the process is interactive, (viii) ensure that the process generates a response, and (ix) only make commitments that can be kept.

Obviously, the above guidelines are primarily for use by the designers of civic actions and related civic-oriented applications, while the social middleware needs to provide the related functions that deal with the interactions and coordination of the contributing actors. This results in the following supporting framework for the customization of the sm-bots as part of a specific civic-oriented application:

• Definition of the actor base: Starting from the elicitation of the civic actors targeted by the application, customized sm-bots need to be implemented and deployed within the related platforms. Considering our running example, the platforms are: Facebook, email, GoogleDoc, monitoring networks, voting service and visualization service. The sm-bots must then initialize and maintain the base of users contributing to the application via these platforms. • Definition of the participation workflow: Provided the civic actor and sm-bot abstractions, the implementation of the civic-oriented application relies on customizing the sm-bots with respect to coordinating the involved civic actors. The customization then subdivides into implementing: (i) the interaction processes with the inner civic actors and (ii) the coordination processes among the distributed sm-bots. • Customize the interaction with participating actors: As part of the above, the interaction processes with the inner civic actors relate to the implementation of the specialized socially-enhanced interactions, as presented in Section IV-B.

C. Trust, security & privacy

Social middleware must ensure that the participation process that it enables guarantee security and privacy to the involved participants. Further, given the openness of the system, trust management must be implemented to ensure that all the participants behave properly. The literature is rich of technology solutions to manage trust, security and privacy. Regarding privacy enforcement, we may in particular leverage the solutions dedicated to crowdsourcing, e.g., [START_REF] Kajino | Preserving worker privacy in crowdsourcing[END_REF], [START_REF] Béziaud | Lightweight Privacy-Preserving Task Assignment in Skill-Aware Crowdsourcing[END_REF]. We will thus integrate state of the art solutions to trust, security and privacy within the social middleware.

A related concern that arises in the context of civic engagement follows from the vicious trends of fake news, privacy leakages, surveillance, and cyberwarfare [START_REF] Shao | The spread of fake news by social bots[END_REF], [START_REF] Cadwalladr | Google, democracy and the truth about internet search[END_REF], [START_REF] Allcott | Social media and fake news in the 2016 election[END_REF], [START_REF] Woolley | Automating power: Social bot interference in global politics[END_REF]. Given social middleware, where everything -no matter its nature-can interact in the virtual world, and where data flow across multiple independent and heterogeneous systems, it is imperative to acknowledge such trends and to devise mechanisms to fight them. Indeed, social middleware can be an attractive environment for deploying tools of mass surveillance and manipulation, or for taking advantage of the large amounts of available data for diverse purposes.

We highlight two aspects of social middleware for which contributing developers must take special care:

1) Sensitive information flowing across the boundaries of multiple systems. Consider, for example, a Facebook user sending a private message to a Twitter user or civic tech platform through social middleware. This message can be intercepted, compromised or transformed while flowing between actors and systems. Moreover, privacy policies may vary across systems, highlighting the need for modeling privacy aspects and understanding its consequences at the social middleware level. The civic engagement functions of the sm-bot related to privacy and security serve that purpose. Still, the specification of policies that the sm-bots enforce remains under the responsibility of developers.

2) The deployed instances of sm-bots can be hacked. In particular, the functions dedicated to the enhancement of social interaction may be an interesting target since they interact directly with humans. For example, a social bot launched by the sm-bot may start impersonating any connected actor of the cyber-physical layer and then spread deceptive information. There exist tools for bot detection [START_REF] Hassan | Toward automated fact-checking: Detecting checkworthy factual claims by claimbuster[END_REF], which allow blocking their interaction. However, sm-bots are the main component of social middleware to assist humans toward civic engagement, informing them about what is happening in the physical world, and enabling them to contribute and act. Knowing that an actor is not human -as state of the art bot detection does-is not enough; researchers must continue working on the detection of deceptive information and malicious behavior, regardless of whether or not actors are human.

On a complementary note, being the target of cyber-attacks is an inevitable risk for any digital system, especially for open distributed systems that are socially-oriented as social middleware is. Systems must be and are increasingly designed with that risk in mind. Further, we believe that social middleware will empower collective actions and citizens will be able to build new governance institutions supported by the cyberphysical convergence provided by such middleware. Additionally, social middleware allows the verification of facts across multiple sources -humans, connected objects, and software platforms-from a variety of distributed and heterogeneous systems.

VI. CONCLUSION

This paper puts forward the vision of social middleware as an essential element to support civic engagement at scale in today's digital era. Social middleware enables civic engagement ecosystems composed of diverse actors -human citizens, connected objects, and software services-existing in heterogeneous digital interaction environments -social media and connected object/service platforms. The ultimate purpose is to enhance the quality of participation by: (i) allowing citizens to use their favorite communication technologies to participate; (ii) allowing citizens to interact not only with other citizens but also with connected objects and software services so as to get access to relevant value-added knowledge; and (iii) leveraging Civic Tech as well as enhancing its capabilities to foster the engagement of people.

Our ongoing and future work focuses on the further development of sm-bots for a concrete civic engagement application to assess the early design of the social middleware building blocks. This development will inform the subsequent development of a method and tools to support the synthesis of sm-bots based on the declarative specification of the functions provided by third-party platforms hosting the (civic) actors.

As part of the above, we are investigating the various incentive mechanisms that we can implement within social middleware by taking advantage of the different functionalities offered by social media. Related to that, looking into anthropomorphism for civic engagement may be a way to go, as in [START_REF] Araujo | Living up to the chatbot hype: The influence of anthropomorphic design cues and communicative agency framing on conversational agent and company perceptions[END_REF] where authors highlight the relevance of anthropomorphism and social presence to important business-related outcomes, such as attitudes, satisfaction and the emotional connection that consumers feel with a company after interacting with social bots. How much more human-like sm-bots can improve the quality of civic engagement is the underlying research question.

It is also crucial to continuously investigate the impact of disruptive innovations on the civic technology ecosystem and hence, how these innovations can influence social middleware. For example, social middleware may leverage blockchain-based solutions for digital identities such as ID2020 (https://id2020.org) whose goal is to provide internationally-recognized digital identities, particularly for populations whose governments provide weak identity systems or whose identities are at risk for political reasons.

Concluding, social middleware, as presented here, poses the vision of a middleware solution contributing to civic engagement. The approach then raises the question of its midto-long term impact on civic participation processes in relation with the level of enacted automation. For instance, "Can proactive social bots play an active role in participatory processes within social middleware?" Obviously, critical actions of participatory processes -e.g., voting-are restricted to human participants only. However, some actions may benefit from the intervention of non-human participants based on the knowledge about the supported process, to instigate engagement. For example, in the context of proposal making, bots may submit ideas, or hints to ideas, so that human participants can decide if they are worth it and, if they are, they can develop them. Bots may also discover relevant digital resources/data about the ongoing process, which they may expose to the contributing actors.

Finally, we stress the trans-disciplinary nature of digital tools for civic engagement. It is essential that computer scientists, human and social scientists, engineers, citizens and government representatives collaborate for the development of such tools, from design to implementation to actual use.

Fig. 1 :

 1 Fig. 1: A CPSS enabling a public consultation.

Fig. 3 :Fig. 4 :

 34 Fig. 3: The USNB multi-party distributed mediation across online social network services.

ssir.org/articles/entry/leveraging the power of bots for civil society

https://gitlab.inria.fr/usnb/


Nicolas Boria

Sébastien Bougleux

Benoit Gaüzère

Luc Brun

Generalized Median Graph via Iterative Alternate Minimizations

Computing a graph prototype may constitute a core element for clustering or classification tasks. However, its computation is an NP-Hard problem, even for simple classes of graphs. In this paper, we propose an efficient approach based on block coordinate descent to compute a generalized median graph from a set of graphs. This approach relies on a clear definition of the optimization process and handles labeling on both edges and nodes. This iterative process optimizes the edit operations to perform on a graph alternatively on nodes and edges. Several experiments on different datasets show the efficiency of our approach.

Introduction

In a wide variety of scientific domains, attributed graphs provide a powerful structure to represent, process and analyze data. However, determining fundamental tools such as a distance or an average graph is non trivial. Given a space G of attributed graphs, Graph Edit Distance (GED) is a natural choice for comparing graphs [START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF][START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF]. It measures the minimal amount of distortion needed to transform a graph into another by means of edit operations. It can be defined as a minimal-path problem which relies on a cost function acting as a metric in G, and rewritten as a special quadratic assignment problem close to the graph matching problem. Computing Graph Edit Distance is NP-Hard and still cannot be solved in a reasonable time for graphs exceeding a dozen of vertices, even for simple cost functions. Therefore, several strategies have been explored to provide tight upper-bounds in polynomial time [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF]. Computing a representative of a set of graphs G ⊂ G is even more difficult. It commonly consists in finding a generalized median graph, ie. a graph Ḡ ∈ G that minimizes the sum of distances (SOD) to all the graphs in G [START_REF] Jiang | On median graphs: properties, algorithms, and applications[END_REF]:

Ḡ ∈ arg min G∈G G ∈G d(G, G ) (1)
where d : G × G → R + denotes Graph Edit Distance. Exact methods are restricted to labeled graphs with particular cost functions or datasets containing a small total number of vertices [START_REF] Ferrer | Theory and Algorithms on the Median Graph[END_REF]. To estimate median graphs in a reasonable computational time, several methods reduce the SOD by a local search around an initial candidate graph, by genetic search [START_REF] Jiang | On median graphs: properties, algorithms, and applications[END_REF], greedy search based on partitioning vertices of different graphs [START_REF] Hlaoui | Median graph computation for graph clustering[END_REF], greedy adaptive search [START_REF] Musmanno | Heuristics for the generalized median graph problem[END_REF], or linearization and discrete optimization [START_REF] Mukherjee | Generalized median graphs and applications[END_REF]. A different strategy is based on graph embedding [START_REF] Ferrer | Generalized median graph computation by means of graph embedding in vector spaces[END_REF][START_REF] Ferrer | A generic framework for median graph computation based on a recursive embedding approach[END_REF][START_REF] Ferrer | Median graph computation by means of graph embedding into vector spaces[END_REF][START_REF] Nienkötter | Improved prototype embedding based generalized median computation by means of refined reconstruction methods[END_REF][START_REF] Chaieb | Fuzzy generalized median graphs computation: Application to content-based document retrieval[END_REF], usually with distances between graphs as coordinates. A representative is more easily computed within this space. Then a median graph is reconstructed by going back to the original space of graphs. While these approaches are able to tackle the complexity of the previous ones, the link with the definition of a generalized median graph is not trivial and difficult to analyze. Other approaches use the relationship between commonlabeling and the median graph to derive bounds on the SOD [START_REF] Rebagliati | On the relation between the common labelling and the median graph[END_REF], or extend the concept of representative to correspondences between graphs [START_REF] Moreno-García | Correspondence edit distance to obtain a set of weighted means of graph correspondences[END_REF].

In this paper, we propose to estimate a generalized median graph by a block coordinate descent that iterates two minimization steps from an initial candidate (Sec. 3): one for updating the SOD w.r.t. edges and attributes on nodes and on edges, and the other w.r.t. distances. The order of the resulting graph is fixed before the descent process by the order of the initial candidate. This candidate is set to a set-median, i.e. a graph of G minimizing the SOD (G restricted to G in Eq. 1). While the first step of the descent shares similarities with the update presented in [START_REF] Jiang | On median graphs: properties, algorithms, and applications[END_REF], the update rules are not the same, and any algorithm can be used to estimate GED in the second step or for initialization. The first empirical results on two datasets (Sec. 4) show on the one hand that the proposed method systematically reduces the SOD associated with the initial candidate, i.e. a setmedian, and on the other hand that the accuracy of the approximate GED has more impact on the descent than on the computation of a set-median. The following section introduces the expressions we use to facilitate the derivation of the proposed algorithm.

Graph Transformations and Graph Edit Distance

We consider simple undirected attributed graphs. An attributed graph G of order n can be encoded by a triplet (ϕ, A, Φ) (Fig. 1). The n-tuple ϕ = (ϕ i ) i

2 3 1 ϕ = (1, 2, 2, 3) Φ =     0 0 0 3 0 0 1 2 0 1 0 3 3 2 3 0     G' 1 2 3 ϕ = (1, 2, 2) Φ =   0 0 4 0 0 1 4 1 0   1 4 3 2 5 1 2 3 4 G' G π = (1, 3, 2, 4) π = (1, 3, 2)
Figure 1: Labeled graphs (label 0 if no edge) and a transformation (π, π ) of their vertices. Induced operations on edges: φ 2,3 = φ 3,2 substituted by φ 3,2 = φ 2,3 , (1, 4), [START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF][START_REF] Daller | Approximate graph edit distance by several local searches in parallel[END_REF], [START_REF] Chaieb | Fuzzy generalized median graphs computation: Application to content-based document retrieval[END_REF][START_REF] Daller | Approximate graph edit distance by several local searches in parallel[END_REF]

removed from G, (1, 2) inserted in G from (1, 3) in G with φ 1,2 = φ 2,1 = φ 1,3 .
associates an attribute (or feature) ϕ i of a space F v to each integer i ∈ [n] = {1, . . . , n} (vertices are represented by the set [n]). A ∈ {0, 1} n×n is the vertexvertex adjacency matrix of G, i.e. a i,j = 1 if there is an edge (i, j), else a i,j = 0. Φ = (φ i,j ) i,j associates an attribute φ i,j of a space F e to each pair (i, j) ∈

[n] × [n]. When (i, j) is not an edge, φ i,j can be equal to any value, it does not affect the following expressions. Obviously, A and Φ are symmetric. Let G be the space of all attributed graphs for F v and F e fixed. In this paper, each space of attributes is restricted to a finite set of positive integer labels, or to the Euclidean space.

A graph G = (ϕ, A, Φ) of order n can be transformed into a graph G = (ϕ , A , Φ ) of order n by applying a composition of elementary transformations, a.k.a. edit operations, to G. An edit operation transforms a graph into another by either removing an element (a vertex or an edge), substituting an attribute attached to an element by another attribute, or by inserting an element and its attribute (between two existing vertices for edges). Moreover, if each element of both graphs is assumed to be involved in exactly one edit operation, the number of operations is minimized, and the transformation of G into G is fully described by the transformation of the vertices of G into the ones of G . Here, this transformation, a.k.a. error-correcting matching [START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF][START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF], is defined as a pair (π, π )

∈ [n + 1] n × [n + 1] n so that π i = k ∈ [n ] ⇔ π k = i ∈ [n] (Fig. 1). Each vertex i of G is either substituted by a vertex k of G (π i = k and π k = i), or removed (π i = n + 1). Each vertex k of G that is not substituted to a vertex of G is inserted (π k = n + 1). The transformation of the edges of G into the ones of G is induced by the transformation of the vertices. The set {(i, j) ∈ [n] × [n] | a i,j = 1 ∧ π i ∈ [n ] ∧ π j ∈ [n ] ∧ a πi,πj = 1} defines the substituted edges, the set {(i, j) ∈ [n] × [n] | a i,j = 1 ∧ ((π i ∈ [n ] ∧ π j ∈ [n ] ∧ a πi,πj = 0) ∨ π i = n + 1 ∨ π j = n + 1)} defines the removed edges, and the set {(k, l) ∈ [n ] × [n ] | a k,l = 1 ∧ ((π k ∈ [n] ∧ π l ∈ [n] ∧ a π k ,π l = 0) ∨ π k = n + 1 ∨ π l = n + 1)
} defines the inserted edges. Since π can be obtained from π, we omit π for simplicity, and we denote by Π(G, G ) all the transformations of G to G .

A transformation π ∈ Π(G, G ) is said to be minimal if its cost is minimal,

i.e. if c(π , G, G ) = min π∈Π(G,G ) c(π, G, G ), with c(π, G, G ) = c v (π, ϕ, ϕ ) + 1
2 c e (π, A, Φ, A , Φ ) the cost for transforming G into G using π, and

c v (π, ϕ, ϕ ) = n i=1 δ πi c vfs (ϕ i , ϕ πi ) + (1 -δ πi )c vr + n k=1 (1 -δ π k ) c vi (2) c e (π, A, Φ, A , Φ ) = n i=1 n j=1 δ πiπj a i,j a πi,πj c efs φ i,j , φ πiπj + c er n i=1 n j=1 δ πiπj a i,j (1 -a πi,πj ) + (1 -δ πiπj )a i,j + c ei n i=1 n j=1 δ πiπj (1 -a i,j )a πiπj + c ei n k=1 n l=1 (1 -δ π k π l )a k,l (3)
the costs for transforming attributed vertices and edges, respectively.

δ πi = 1 if π i ∈ [n ]
, else 0, and δ πiπj = δ πi δ πj . Functions c vfs : ) measure costs to substitute vertices and edges. In this paper, the costs for removing and inserting elements are restricted to positive constants, denoted c vr , c vi , c er , c ei . When any substitution of elements is no more expensive than removing and inserting these elements, Graph Edit Distance (GED) between G and G is equal to the cost of a minimal transformation [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF]:

F v × F v → [0, +∞) and c efs : F e × F e → [0, +∞
d(G, G ) = min π∈Π(G,G ) c(π, G, G
). This case is considered in the sequel.

Estimating a Generalized Median Graph

Given a set of graphs G = {G p } p ⊂ G, with G p = (ϕ p , A p , φ p ) of order n p , a generalized median graph Ḡ = ( φ, Ā, φ) ∈ G of G minimizes the sum of distances (SOD) to the graphs of G [START_REF] Jiang | On median graphs: properties, algorithms, and applications[END_REF][START_REF] Ferrer | Theory and Algorithms on the Median Graph[END_REF]:

s( Ḡ, G) = min G∈G s(G, G), with s(G, G) = Gp∈G d(G, G p ) = |G| p=1 min πp∈Π(G,Gp) c(π p , G, G p ).
We propose to use a block coordinate descent to estimate both Ḡ and the minimal transformations (π p ) p .

Proposed algorithm

First, Ḡ is initialized to a set-median of G, i.e. Ḡ = arg min Gp∈G s(G p , G). It can be computed in O(a|G| 2 ) time [START_REF] Ferrer | Theory and Algorithms on the Median Graph[END_REF], where a is the complexity of the algorithm used for computing or estimating GED. This also provides the minimal transformations (π p ) p from Ḡ to the graphs of G. The order n of Ḡ is then fixed, i.e. considered as a constant in the optimization process. Then, ( φ, Ā, Φ) and (π p ) p are alternatively updated as follows:

Ḡ = ( φ, Ā, Φ) ← arg min ϕ∈F n v A∈{0,1} n× n Φ∈F n× n e |G| p=1 c v (π p , ϕ, ϕ p ) + 1 2 c e (π p , A, Φ, A p , Φ p ) (4) ∀p ∈ {1, . . . , |G|}, πp ← arg min πp∈Π( Ḡ,Gp) c(π p , Ḡ, G p ) (5)
until convergence, that is, until a stability is reached both in Ḡ and (π p ) p . The resolution of the minimization of the sum of distances when the transformations are fixed (Eq. 4) mainly depends on the nature of F v and F e , as well as the form of the cost functions c vfs and c vef . This is detailed later in this section, in particular it can be solved in O(n 2 |G|) time under some conditions. The update of the transformations (Eq. 5) consists in solving |G| times GED problem, so in O(a|G|) time. Since the order n is fixed, and GED can usually be only estimated, the algorithm may not converge to the true generalized median graph. We assume that an algorithm for computing GED is given, and we focus on the minimization of the sum of distances w.r.t. the graph (Eq. 4). It can be decomposed into two independent minimizations as long as the attributes ϕ p and Φ p are independent for each p, that we consider in this paper:

φ ← arg min ϕ∈F n v s v (ϕ), ( Ā, Φ) ← arg min A∈{0,1} n× n Φ∈F n× n e s e (A, φ) (6)
with

s v (ϕ) = |G| p=1 c v (π p , ϕ, ϕ p )
and s e (φ, A) =

|G|

p=1 c e (π p , A, φ, A p , φ p ). The minimization of each term is detailed in the two following sections. Note that some results are already presented in [START_REF] Jiang | On median graphs: properties, algorithms, and applications[END_REF], in particular for vertices. There are obtained in a different way, allowing to take into account more easily different spaces of attributes and cost functions associated to edit operations.

Updating vertex attributes

Only the cost function c vfs depends on vertex attributes in the expression of c v (Eq. 2). So the attributes φ in Eq. 6 are updated by solving the equivalent problem arg min ϕ∈F n v n i=1 f i (ϕ i ), with the function f i :

F v → R + defined by f i (ϕ i ) = |G| p=1 δ π p i c vfs (ϕ i , ϕ p π p i
). The objective function is a sum of positive and independent terms f i , so the attributes are updated by: ∀i = 1, . . . , n, φi ← arg min

ϕi∈Fv f i (ϕ i ) (7)
The solution depends on F v and on the cost function c vfs . When attributes are labels (F v ⊂ N), the cost for substituting a label x ∈ F v by a label y ∈ F v is defined as c vfs (x, y) = c vs (1 -δ x,y ), with c vs > 0 a constant, i.e. 0 if the labels are the same, and c vs otherwise. Then f i can be rewritten as

f i (ϕ i ) = |G| p=1 δ π p i c vs (1 -δ ϕi,ϕ p π p i ) = c vs (|S i | -h 0 i (ϕ i ))
, where

S i = {π p i | π p i ∈ [n p ], p = 1, .
. . , |G|} is the set of vertices that are substituted to i by the mappings π p , and h 0 i :

F v → {0, . . . , |G|} ⊂ N, h 0 i (ϕ i ) = |G| p=1 δ π p i δ ϕi,ϕ p π p i
, counts the number of times i is substituted by a vertex having the same label (with zero cost). So the attributes (Eq. 7) are updated by: ∀i = 1, . . . , n, φi ← arg max

ϕi∈Fv h 0 i (ϕ i ) (8)
Notice that h 0 i can be pre-computed in O(|G|) time for each label of F v . The labels are thus updated for all the vertices of Ḡ in O(n|G|) time at each iteration.

When F v = R m is equipped with the scalar product x T y = m k=1 x k y k and the l 2 -norm x =

√

x T x, the cost for substituting an attribute x by an attribute y is defined by c vfs (x, y) = x -y 2 . In this case, we have:

f i (ϕ i ) = |G| p=1 δ π p i ϕ i -ϕ p π p i 2
. Any attribute φi satisfies ∇f i ( φi ) = 0, i.e.

2 p δ π p i ( φi - ϕ p π p i ) = 0, or: ∀i = 1, . . . , n, φi ← 1 |G| p=1 δ π p i |G| p=1 δ π p i ϕ p π p i = 1 |S i | p∈Si ϕ p π p i (9)
In other words, the optimal attribute for a vertex i is given by the mean attribute of the vertices substituted to i (the set S i defined in the previous paragraph). Once more, updating all the attributes is done in O(n|G|) time at each iteration.

Updating edges and their attributes

The edges of Ḡ, and their attributes, are computed at each step of the descent (Eq. 4) by minimizing s e (Eq. 6). By removing the constant terms in s e , i.e. in c e (Eq. 3), it is easy to show that the minimization of s e can be rewritten as:

arg min A∈{0,1} n× n Φ∈F n× n e s e (A, φ) = arg min A∈{0,1} n× n Φ∈F n× n e n i=1 n j=1 f i,j (a i,j , φ i,j ) (10)
with the function f i,j : {0, 1} × F e → R + defined by:

f i,j (a i,j , φ i,j ) = a i,j |G| p=1 δ π p i π p j a p π p i ,π p j c efs (φ i,j , φ p π p i ,π p j ) + c er a i,j |G| p=1 1 -δ π p i π p j a p π p i ,π p j + c ei (1 -a i,j ) |G| p=1 δ π p i π p j a p π p i ,π p j = a i,j |G| p=1 δ π p i π p j a p π p i ,π p j c efs (φ i,j , φ p π p i ,π p j ) + c er a i,j (|G| -|S i,j |) + c ei (1 -a i,j )|S i,j | (11)
where

S i,j = {(π p i , π p j ) | π p i ∈ [n p ] ∧ π p j ∈ [n p ] ∧ a p π p i ,π p j = 1, p = 1, .
. . , |G|} is the set of edges that are substituted to (i, j) by the mappings π p . The terms f i,j are positive and independent from each others, so Eq. 10 is equivalent to:

∀(i, j) ∈ [n] × [n], i = j, (ā i,j , φi,j ) ← arg min ai,j ∈{0,1} φi,j ∈Fe f i,j (a i,j , φ i,j ) (12)
Since a i,j can only take two values, if a i,j = 0 (no edge) then f i,j (0, φ i,j ) = c ei |S i,j | for any φ i,j ∈ F e , and if a i,j = 1 then f i,j (1, φ i,j ) is minimized for any

φ i,j ∈ arg min φi,j ∈Fe |G| p=1 δ π p i π p j a p π p i ,π p j c efs (φ i,j , φ p π p i ,π p j ) (13)
By consequence f i,j is minimized for φi,j = φ i,j and āi,j =

1 if f i,j (1, φij ) < c ei |S i,j | 0 else ( 14
)
Solutions are finally obtained by solving Eq. 13. It depends on F e and c efs . When F v ⊂ N and c efs (x, y) = c es (1 -δ x,y ), with c es > 0 a constant, is the classical cost for labels, then f i,j (Eq. 11) becomes

f i,j (a i,j , φ i,j ) = a i,j c es |S i,j | -h 0 i,j (φ i,j ) + c er (|G| -|S i,j |) +(1-a i,j )c ei |S i,j | where h 0 i,j (x) = |G| p=1 δ π p i π p j a p π p i ,π p j δ x,φ π p i ,π p j
counts the number of times (i, j) is substituted by an edge having the label x. Then Φ and Ā are updated for all (i, j)

∈ [n] × [n] by: φi,j ← arg max x∈Fe h 0 i,j (x) (15)
and āi,j ←

1 if h 0 i,j ( φi,j ) > |G| cer ces + |S i,j | 1 -cer+cei ces 0 else (16)
Each edge (i, j) is thus labeled with one of the most present labels among the ones substituted to (i, j). Notice that h 0 i,j : F e → {0, . . . , |G|} and |S i,j | can be computed in O(|G|) time. So Φ and Ā are computed in O(n 2 |G|) time.

Unlabeled graphs can be considered as labeled with a unique label, e.g. F e = {1}. In this case c efs = 0 and h 0 i,j = |S i,j |, so from Eq. 16 Ā can be computed in O(n 2 |G|) time by: āi,j ←

1 if |S i,j | > |G| cer cer+cei 0 else (17)
Remark. Similar results can be derived for directed graphs, other spaces of attributes and other cost functions, for both vertices and edges. Due to limited space, it is restricted here to the cases considered in the experiments.

Experimental results

In order to evaluate the validity of our method, the algorithm was implemented in C++ and tested on the datasets Letter (HIGH) [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF] and Monoterpenoides1 , a chemical dataset, on a computer using an intel(R) i7-8700 CPU with 12 parallel threads. The Monoterpenoides dataset has 286 graphs unevenly divided in 8 classes of at least 10 graphs. Both nodes and egdes are labeled, and the average order is 11.003. Edit costs were set to c vs = c es = 1 and c vi = c ei = c vr = c er = 3. Remember that, in a first phase, the proposed algorithm (Sec. 3.1) identifies a set-median by computing all pairwise distances in the dataset. These distances are computed through two heuristics: bipartite [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF], and IPFP [START_REF] Bougleux | Graph edit distance as a quadratic program[END_REF]. In a second phase, the algorithm iterates the update of a triplet ( φ, Ā, Φ) according to Eq. 6 (i.e. for vertices either Eq. 8 for Monoterpenoides or Eq. 9 for Letter, and for edges, Eq.15-16 for Monoterpenoides or Eq. 17 for Letter), and the update of the transformations πp using either bipartite or IPFP. We denote by mBipartite and mIPFP the multistart counterparts of Bipartite, and IPFP [START_REF] Daller | Approximate graph edit distance by several local searches in parallel[END_REF], where the number of randomly generated initializations was set to 40.

Algorithms

Table 1 sums up our results regarding SOD. In Letter and Monoterpenoides, respectively 50 and 10 graphs were picked randomly in each class, and each experiment was repeated 50 times. The results presented in Table 1 represent the averages over all classes and all experiments. The four columns SOD SM, t(SM), SOD GM and t(GM) list the SODs and computation times in seconds for the set-median (SM), and the generalized median (GM). Note that t(GM) refers to the computation time of the second phase only. Using state of the art GED heuristics and making the most of the computed transformations πp to efficiently perform the descent (conversely to many other approaches which use GED only to evaluate candidate medians, without using the detailed transformations), our algorithm produces median graphs with SODs much lower than the setmedians' with a very low running time. It is noteworthy that the time dedicated to identify the set-median (first phase) is systematically higher than the one dedicated to the generalized median (second phase). Indeed, |G| 2 distances must be computed in the first phase, while p|G| distances are computed in the second phase, where p denotes the number of iterations before convergence. In practice, we verified that, in most cases, p < 2 on the letter dataset, and p < 7 on Monoterpenoides. Interestingly enough, in the hybrid versions of the algorithm (using Bipartite in the first phase and IPFP in the second phase), the alternate descent still produces median graph with reasonably low SOD while starting from a set-median of lesser quality (i.e. with higher SODs).

Finally, note that the range between best and worst computed SODs is particularily low on the Letter dataset, while it is rather high on the Monoterpenoides dataset. This seems to indicate that approximate computed distances are close to the optimum in Letter, and far from it in Monoterpenoides.

Picking random trainsets in each class 10% and 30% the size of the class, set-medians and generalized medians were computed for each class, and the classification accuracy of a 1-nn algorithm [START_REF] Ferrer | Theory and Algorithms on the Median Graph[END_REF] was evaluated using as training examples: (SM) only the set-median, (GM) only the generalized medians and finally (TS) the whole trainset. Each experiment was repeated 50 times, and Table 2 presents our results, giving the average preprocessing time pt (i.e. the time spent in computation of set-medians and generalized medians), as well as classification precisions (denoted by %) and times for all three training examples considered. Note that the GED heuristic used in the second phase of the algorithms were also used in computing distances by the classifier.

Let us note that our approach competes with a 1-nn classification over the whole trainset, especially when all the distances are computed with a more precise heuristic, such as mIPFP. Whenever a precise heuristic is used to compute it, the generalized median appears as a better representative of the class than the set-median. Obviously, classification times are much faster using only the median graphs as training example.

In few cases, the classification accuracy enabled by set-medians is higher than that enabled by generalized medians. This only happens in cases where computed distances and edit-paths are looser approximations, i.e. this always happens on the Monoterpenoides dataset with the mBipartite heuristic used in the initialization phase.

Conclusion

We proposed an innovative general method to compute the generalized median graph based on an alternate gradient descent. We showed its efficiency through experiments on two datasets using different edit-cost structures. Computed graphs have much lower SODs than set-medians, and can efficiently be used as representatives in a clustering framework. Quality of computed graph median increases when using accurate rather than fast GED approximation algorithms as sub-routines, especially in the alternate descent phase, while the initialization phase may use different GED heuristics to reach different time/quality compromises. Future developments regarding this promising method include the extension to new edit-cost structures, as well as the possibility to modify the order of the median graph during the optimization process.

Table 1 :

 1 SOD computed using different GED approximations.

				Letter (HIGH)			Monoterpenoides
	1st phase	2nd phase	SOD SM t(SM) SOD GM	t(GM)	SOD SM t(SM) SOD GM	t(GM)
	Bipartite	Bipartite	142.69	0.01	87.80	6 * 10 -4	402.50	0.002	253.11	8 * 10 -4
	Bipartite	IPFP	142.87	0.013	87.61	0.003	398.01	0.002	128.45	0.179
	IPFP	IPFP	135.99	0.057	87.22	0.003	202.75	0.162	104.11	0.136
	mBipartite mBipartite	142.04	0.014	89.47	9 * 10 -4	283.94	0.027	186.15	0.01
	mBipartite	mIPFP	142.19	0.018	87.66	0.013	281.14	0.031	83.11	0.545
	mIPFP	mIPFP	135.99	0.274	87.23	0.015	106.10	1.159	75.08	0.288

Table 2 :

 2 Classification Results for Letter(HIGH) and Monoterpenoides datasets

	Letter (HIGH) Dataset

GREYC Chemistry dataset: https://brunl01.users.greyc.fr/CHEMISTRY/

Acknowledgments. This work is supported by Région Normandie through RIN AGAC project.


David B Blumenthal

Sébastien Bougleux

Johann Gamper

Luc Brun

GEDLIB: A C++ Library for Graph Edit Distance Computation

Keywords: Graph Edit Distance, Open Source Library, C++

The graph edit distance (GED) is a flexible graph dissimilarity measure widely used within the structural pattern recognition field. In this paper, we present GEDLIB, a C++ library for exactly or approximately computing GED. Many existing algorithms for GED are already implemented in GEDLIB. Moreover, GEDLIB is designed to be easily extensible: for implementing new edit cost functions and GED algorithms, it suffices to implement abstract classes contained in the library. For implementing these extensions, the user has access to a wide range of utilities, such as deep neural networks, support vector machines, mixed integer linear programming solvers, a blackbox optimizer, and solvers for the linear sum assignment problem with and without error-correction.

Introduction

Because of their expressiveness and versatility, labeled graphs are widely used to model various kinds of objects such as molecules, street networks, and images. Many pattern recognition problems defined over these domains presuppose the availability of a (dis-)similarity measure for labeled graphs. Despite the fact that its exact computation is N P-hard [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], one of the most widely used measures is the graph edit distance (GED). Given two labeled graphs G and H, it is defined as GED(G, H) := min P ∈Ψ (G,H) c(P ), where Ψ is the set of all edit paths between G and H and c(P ) denotes the cost of an edit path P . An edit path is a sequence of edit operations that transforms G into H. There are six edit operations: substituting a node or an edge in G by a node or an edge in H, deleting an edge or an isolated node from G, and inserting an edge or an isolated node into H. Each edit operation comes with an associated non-negative edit cost defined in terms of the node or edge labels involved in the operation; and the cost of an edit path is defined as the sum over the costs of its edit operations.

Over the past years, some exact and a lot of approximate algorithms for computing GED have been suggested. As the hardness of GED does not allow for a theoretical evaluation of approximate algorithms (the existence of any αapproximation algorithm for GED would imply that the graph isomorphism problem, a prime candidate for an N P-intermediate problem, is in P), these algorithms are typically evaluated empirically. In order for such a comparison to be fair, it is highly desirable that the compared algorithms be implemented within the same environment. However, to the best of our knowledge, no software is available that can be used for this purpose.

In this paper, we present the C++ template library GEDLIB which is intended to fill this gap. GEDLIB is available on GitHub: https://github.com/dbblumenthal/gedlib

In its current version, GEDLIB contains implementations of 24 different GED algorithms and 9 different edit cost functions. Further algorithms and edit costs can be implemented easily by implementing abstract classes contained in GEDLIB. For this, the user has access to standard libraries for blackbox optimization, mixed integer linear programming, the linear sum assignment problem with and without error-correction, deep neural networks, and support vector machines. GEDLIB provides a parser to load graphs given in the GXL file format. Alternatively, graphs with user-specified node ID, node, and edge label types can be constructed from within GEDLIB. Internally, GEDLIB uses the Boost Graph Library [START_REF] Lee | The Boost Graph Library: User Guide and Reference Manual[END_REF] for representing the graphs and Eigen [START_REF] Guennebaud | [END_REF] for matrix operations.

The remainder of this paper is organized as follows: In Section 2, the overall architecture of GEDLIB is sketched. In Section 3, the user interface is presented. In Section 4 and Section 5, the abstract classes for implementing GED algorithms and edit cost functions are described. Section 6 concludes the paper. Details, examples, and installation instructions can be found in the documentation.

Overall Architecture

Figure 1 shows the overall architecture of GEDLIB in a UML diagram. The entire library is contained in the namespace ged. The template parameters UserNodeID, UserNodeLabel, and UserEdgeLabel correspond to the types of the node IDs, the node labels, and the edge labels of the graphs provided by the user.

-The class template ged::GEDEnv provides the user interface. Via its public member functions, graphs can be constructed or loaded from GXL files, edit costs can be set, the algorithms implemented in GEDLIB can be run, and the results of the runs can be obtained. For users who do not want to provide extensions for GEDLIB, it suffices to get familiar with this class template. -The abstract class template ged::GEDMethod provides a generic interface for implementing algorithms that exactly or approximately compute GED. -The abstract class templates ged::LSBasedMethod , ged::MIPBasedMethod , and ged::LSAPEBasedMethod are derived from the generic interface provided by ged::GEDMethod . They yield more specialized interfaces for implementing methods using local search, mixed integer linear programming, and transformations to the linear sum assignment problem with error-correction. -The abstract class template ged::MLBasedMethod is derived from the interface ged::LSAPEBasedMethod . It can be used to implement algorithms that use deep neural networks or support vector machines for transforming GED to the linear sum assignment problem with error-correction. -The class template ged::GEDData contains the normalized input data on which all GED algorithms contained in GEDLIB operate. Via the public member functions of ged::GEDData, derived classes of ged::GEDMethod have access to the graphs that have been added to the environment and to the edit cost functions selected by the user. -The abstract class template ged::EditCosts provides a generic interface for implementing edit cost functions.

User Interface

In Figure 2, the class template ged::GEDEnv, which constitutes the user interface of GEDLIB, is displayed in detail. By calling add graph(), add node(), and add edge(), the user can add labeled graphs to the environment. Alternatively, load gxl graphs() can be used to load graphs given in the GXL file format. For this, the template parameter UserNodeID must be set to ged::GXLNodeID a. k. a. std::string, and the template parameters UserNodeLabel and UserEdgeLabel must be set to ged::GXLLabel a. k. a. std::map<std::string,std::string>.

Calls to set edit costs() add edit cost functions to the environment. The user can either select one of the predefined edit cost functions or use her own implementation of ged::EditCosts . Calls to init() initialize the environment eagerly or lazily. If eager initialization is chosen, all edit costs between graphs contained in the environment are precomputed. Otherwise, the edit cost functions are evaluated on the fly. The member function set method() selects one of the GED algorithms available in GEDLIB. Some algorithms accept options, which can be passed to set method() as a string of the form "[--<option> <arg>] [...]". Calls to init method() initialize the selected method for runs between graphs contained in the environment, and calls to run method() run the method between two specified graphs. The results of the runs (lower and upper bounds, runtimes, etc.) can be accessed via various getter member function.

= (c i,k ) ∈ R (n+1)×(m+1) ≥0
. The task is to compute a mapping π from rows to columns, such that each row except for n + 1 and each column expect for m + 1 is covered exactly once and C(π) := (i,k)∈π c i,k is minimized. LSAPE can be solved optimally in cubic time [START_REF] Bougleux | Fast linear sum assignment with error-correction and no cost constraints[END_REF]; in GEDLIB, we use the LSAPE toolbox [START_REF] Bougleux | Linear sum assignment with edition[END_REF] for solving LSAPE.

If LSAPE is used for approximating GED(G, H), n and m are set to |V G | and |V H |, the first |V G | rows of C are associated with the nodes of G, the first |V H | columns of C are associated with the nodes of H, and the last rows and columns are associated with dummy nodes used for codifying node insertions and deletions. With this setup, each LSAPE solution π corresponds to a node map between G and H, which, in turn, induces an edit path and hence an upper bound for GED(G, H) [START_REF] Blumenthal | On the exact computation of the graph edit distance[END_REF]. LSAPE based heuristics for GED try to achieve tight upper bounds by encoding structural information of the input graphs into C. Moreover, some of them construct C such that min π C(π) lower bounds GED.

Figure 4 shows the abstract class template ged::LSAPEBasedMethod , which provides the interface for implementing heuristics of this kind. The interface is defined by the virtual member functions starting with the prefix lsape . The most important one is lsape populate instance () , which populates the LSAPE instance C. The following algorithms implemented in GEDLIB are directly derived classes of ged::LSAPEBasedMethod : ged::Bipartite [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], ged::Branch [2], ged::BranchFast [2], ged::Node [START_REF] Justice | A binary linear programming formulation of the graph edit distance[END_REF], ged::BranchUniform [START_REF] Zheng | Efficient graph similarity search over large graph databases[END_REF], ged::Ring [3], ged::Subgraph [START_REF] Carletti | Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance[END_REF], ged::Walks [START_REF] Gauzère | Approximate graph edit distance guided by bipartite matching of bags of walks[END_REF]. Additionally, all derived classes of ged::LSAPEBasedMethod can be run with the node centralities suggested in [START_REF] Riesen | Improving graph edit distance approximation by centrality measures[END_REF].

Interface for Methods Based on Machine Learning. Recently, it has been suggested to use deep neural networks or support vector machines for carrying out the transformation from GED to LSAPE. Given two graphs G and H, feature vectors are constructed for all node substitutions, deletions, and insertions, and the matrix C is defined as c i,k := 1 -p (i, k). Here, p (i, k) is the confidence of a machine learning framework (either a deep neural network or a support vector machine) that the feature vector associated to the node edit operation corresponding to row i and column k is contained in an optimal node map. Figure 5 details the abstract class template ged::MLBasedMethod , which provides the interface for algorithm adopting this paradigm. For implementing the interface, it suffices to override the virtual member functions starting with the prefix ml . The most important ones are the three virtual member functions of the form ml populate * feature vector () , which construct the feature vectors associated to the node edit operations. Derived classes of ged::MLBasedMethod do not have to implement the machine learning frameworks, as ged::MLBasedMethod offers support for artificial deep neural networks (using FANN [START_REF] Nissen | Implementation of a fast artificial neural network library (FANN)[END_REF]) and support vector machines (using LIBSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]). The following algorithms implemented in GEDLIB are directly derived classes of ged::MLBasedMethod : ged::BipartiteML [START_REF] Riesen | Predicting the correctness of node assignments in bipartite graph matching[END_REF], ged::RingML [START_REF] Blumenthal | Upper bounding GED via transformations to LSAPE based on rings and machine learning[END_REF].

ged::MLBasedMethod ... // misc. variables -ml populate substitution feature vector () // substitution features -ml populate deletion feature vector () // deletion features -ml populate insertion feature vector () // insertion features ... // misc. member functions UserNodeLabel,UserEdgeLabel Interface for Methods Based on Mixed Integer Programming. Another approach for exactly or approximately computing GED is to rephrase the problem of computing GED(G, H) as a mixed integer programming (MIP) problem. GED(G, H) can then be computed exactly by calling an MIP solver. Alternatively, lower bounds for GED(G, H) can be obtained by solving the linear programming (LP) relaxations of the MIP formulations.

Figure 6 shows the abstract class template ged::MIPBasedMethod , which provides the interface for GED algorithms that use MIP formulations. The virtual member functions that define the interface start with the prefix mip . The most important one is mip populate model () , which constructs the employed MIP formulation and must be overridden by all derived classes. In GEDLIB, we use Gurobi [START_REF]LLC: Gurobi optimizer reference manual[END_REF] as our MIP and LP solver. Gurobi is commercial software but offers a free academic license. For users who cannot obtain a license for Gurobi, the installation script distributed with GEDLIB offers the option to install GEDLIB without ged::MIPBasedMethod and its derived classes. The following algorithms implemented in GEDLIB are directly derived classes of ged::MIPBasedMethod : ged::F1 [ Interface for Methods Based on Local Search. Another popular approach for upper bounding GED is to use variants of local search to systematically vary a previously computed or randomly generated node map, such that the cost of the induced edit path decreases. Figure 7 shows the abstract class template ged::LSBasedMethod , which provides the interface for algorithms using local search. The prefix ls marks the virtual member functions defining the interface. The most important one is ls run from initial solution () , which runs the local search from an initial node map. The following algorithms implemented in GEDLIB are directly derived classes of ged::LSBasedMethod : ged::IPFP [START_REF] Blumenthal | Quasimetric graph edit distance as a compact quadratic assignment problem[END_REF][START_REF] Bougleux | Graph edit distance as a quadratic assignment problem[END_REF][START_REF] Bougleux | Graph edit distance as a quadratic program[END_REF], ged::BPBeam [START_REF] Ferrer | A first step towards exact graph edit distance using bipartite graph matching[END_REF][START_REF] Riesen | Combining bipartite graph matching and beam search for graph edit distance approximation[END_REF], ged::Refine [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. Moreover, ged::LSBasedMethod provides support for running all derived classes with parallel multi-start as suggested in [START_REF] Daller | Approximate graph edit distance by several local searches in parallel[END_REF], and stochastic generators as suggested in [START_REF] Boria | Approximating GED using a stochastic generator and multistart IPFP[END_REF]. edge. The functions vectorize * label() return vector representations of the node and the edge labels, which are required by some methods. In GEDLIB, edit costs are available for the datasets aids, fingerprint, grec, letter, mutagenicity, and protein from the IAM Graph Database [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF], for the datasets acyclic, alkane, pah, and mao from GREYC's Chemistry Dataset (available at https://brunl01.users.greyc.fr/CHEMISTRY/), and for the dataset cmu-ged from the Graph Data Repository for Graph Edit Distance [START_REF] Abu-Aisheh | A graph database repository and performance evaluation metrics for graph edit distance[END_REF]. We also provide constant edit cost functions that can be used with any data.

Abstract Class for Implementing Edit Costs

Conclusions and Future Work

In this paper, we have presented GEDLIB, a C++ library for GED computations. GEDLIB currently implements 24 different GED algorithms and 9 different edit cost functions designed for datasets which are widely used in the research community. In the future, we will provide Python and MATLAB bindings for better usability. Moreover, we would like to encourage authors of algorithms and edit costs that are not implemented in GEDLIB to commit their work to GEDLIB.

Fig. 1 .

 1 Fig. 1. The overall architecture of GEDLIB shown in a UML class diagram.

-Fig. 4 .

 4 Fig. 4. The interface ged::LSAPEBasedMethod for methods based on LSAPE.

Fig. 5 .

 5 Fig. 5. The interface ged::MLBasedMethod for LSAPE based methods that use machine learning techniques for populating their LSAPE instances.

Fig. 6 .

 6 Fig. 6. The interface ged::MIPBasedMethod for methods based on MIP.

Figure 8 Fig. 7 .

 87 Figure8shows the abstract class template ged::EditCosts , which provided the interface for implementing edit cost functions. The virtual member functions * del cost fun() compute the cost of deleting a node or an edge with a given label, the functions * ins cost fun() compute the insertions costs, and the functions * rel cost fun() compute the costs for relabeling a node or an

Fig. 8 .

 8 Fig. 8. The interface ged::EditCosts for implementing edit costs.

  Figure 3 details the abstract class template ged::GEDMethod , which provides the generic interface for implementing GED. The interface is defined by the virtual member functions starting with the prefix ged . We here describe only the most important virtual member functions; the remaining ones are detailed in the documentation: ged run () runs the method between two input graphs, ged init () initializes the methods for the graphs that have been added to the environment, and ged parse option () parses the options of the method. The following existing algorithms already implemented in GEDLIB are directly derived classes of ged::GEDMethod : ged::BranchTight [2], ged::HED [17], ged::Partition [32], ged::Hybrid [32], ged::SimulatedAnnealing [30], ged::BranchCompact [32], ged::AnchorAwareGED [14].

		UserNodeLabel,UserEdgeLabel
		ged::GEDMethod
	...	// misc. variables
	-ged run ()	// runs the method between two graphs
	-ged init ()	// initializes the method for the graphs in ged data
	-ged parse option () // parses the options
	...	// misc. member functions
	Fig. 3. The generic interface ged::GEDMethod .
		UserNodeID,UserNodeLabel,UserEdgeLabel
		ged::GEDEnv
	...	// misc. variables
	+ add graph()	// adds a graph to the environment
	+ add node()	// adds a node to a previously added graph
	+ add edge()	// adds an edge to a previously added graph
	+ load gxl graphs() // loads graphs given as GXL files
	+ set edit costs() // selects the edit costs
	+ init()	// initializes the environment
	+ set method()	// selects the GED method
	+ init method()	// initializes the selected GED method
	+ run method()	// runs the selected GED method
	...	// misc. member functions

Fig. 2. The user interface ged::GEDEnv. 4 Abstract Classes for Implementing GED Algorithms Generic Interface.

Interface for Methods Based on the Linear Sum Assignment Problem with Error-Correction. A popular approach for approximating GED is to use transformations to the linear sum assignment problem with error-correction (LSAPE). An instance of LSAPE consists of a cost matrix C

  23], ged::F2 [23], ged::CompactMIP [6], ged::BLPNoEdgeLabels [21].

		UserNodeLabel,UserEdgeLabel
		ged::MIPBasedMethod
	...	// misc. variables
	-mip populate model () // constructs the MIP formulation
	...	// misc. member functions