1,720,971 research outputs found
Quantum processes for structural analysis
No full textMany real systems can be modelled as networks, being characterized by a set of items and links between them. Systems taking the form of networks, also called graphs, appear in a wide range of scenarios, varying from biological to technological domains. Illustrative examples abound and include neural networks, protein-protein interactions, metabolic reaction networks, social networks, coauthorship and citation relations, road maps, financial market stock correlations and the World Wide Web. In the last decade network theory has proven to be a very useful instrument to model the structure of systems, albeit not sufficient to cover all issues in the scope of structural analysis. For this reason it has arisen the need of drawing on ideas from fields such as physics which actually helped in gaining new insight for a relevant class of problems. In this thesis, we address matters encountering in graph structural analysis by exploiting new approaches based on quantum processes and the von Neumann entropy. In particular, we focus on the characterization aspects of graphs concerning structural properties, as well as on processes underlying network evolution. We commence by investigating spectral generative models for learning structural representations. Then we move on to quantum models, specifically quantum walks, and the von Neumann entropy characterization. Finally, we introduce a novel thermodynamic method to model time evolving networks
Un benchmark per il topic modeling sulle origini dell’antisemitismo moderno
Get PDFThe pace of digitized collective knowledge accumulation has become increasingly rapid in the last few years. That means we have tremendous amounts of information content to be organized, searched, and understood that can be arranged only by employing automatic methods. In the case of textual data analysis, topic modeling, a machine learning method, is definitely the most famous framework to uncover latent topics from text documents. Adopting topic modeling approaches for studying textual sources is a well-established practice in many scientific and humanities studies fields, including the historical research scope. In this paper, we present a benchmark corpus for topic models, a dataset containing an annotated real-world collection of texts focused on the antisemitism theme in 19th century France. The benchmark corpus has been developed to address a specific machine learning task but it can also support the enhancement of other natural language processing-based studies, in particular, those concerning the historical sphere.Negli ultimi anni il ritmo di accumulazione della conoscenza collettiva digitalizzata è divenuto sempre più rapido. Ciò significa che abbiamo enormi quantità di contenuto informativo da organizzare, ricercare e analizzare: una serie di compiti che possono essere svolti soltanto impiegando metodi automatici. Nel caso dell'analisi dei dati testuali, il topic modeling, un metodo di apprendimento automatico, è sicuramente la via più nota per cogliere gli argomenti latenti all’interno dei testi. L'adozione di approcci di topic modeling per lo studio delle fonti testuali è una pratica consolidata in molti campi di studi scientifici e umanistici, incluso quello della ricerca storica. In questo articolo presentiamo un benchmark per il topic modeling, un dataset contenente una collezione di testi annotati incentrati sul tema dell'antisemitismo nella Francia del XIX secolo. Il benchmark è stato sviluppato per affrontare un compito specifico di apprendimento automatico, ma può anche consentire il miglioramento di altri studi basati sull'elaborazione del linguaggio naturale, in particolare, quelli riguardanti l’ambito storico
GraFix: A Graph Transformer with Fixed Attention Based on the WL Kernel
No full textIn this paper we introduce GraFix, a novel graph transformer with fixed structural attention. Inspired by recent works 1) harnessing the link between (graph) kernels and the attention mechanism of transformers and 2) favouring simple fixed (non-learnable) attentive patterns over the standard attention mechanism, we propose to use graph kernels, specifically the WL kernel, to replace the learnable attention mechanism of a transformer with a fixed one capturing the structural similarity between substructures in the input graphs. The resulting graph transformer showcases an excellent performance on standard graph classification benchmarks, performing on-par with and in some instances outperforming a wide variety of alternative graph neural network and graph transformer-based approaches while at the same time benefiting from a reduced number of learnable parameters and learning runtime
Representation of Jews and Anti-Jewish Bias in 19th-Century French Public Discourse: Distant and Close Reading
Get PDFWe explore through the lens of distant reading the evolution of discourse on Jews in France during the XIX century. We analyze a large textual corpus including heterogeneous sources-literary works, periodicals, songs, essays, historical narratives-to trace how Jews are associated to different semantic domains, and how such associations shift over time. Our analysis deals with three key aspects of such changes: the overall transformation of embedding spaces, the trajectories of word associations, and the comparative projection of different religious groups over different, historically relevant semantic dimensions or streams of discourse. This allows to show changes in the association between words and semantic domains (referring e.g. to economic and moral behaviors), the evolution of stereotypes, and the dynamics of bias over a long time span characterized by major historical transformations. We suggest that the analysis of large textual corpora can be fruitfully used in a dialogue with more traditional close reading approaches-by pointing to opportunities of in-depth analyses that mobilize more qualitative approaches and a detailed inspection of the sources that distant reading inevitably tends to aggregate. We offer a short example of such a dialogue between different approaches in our discussion of the Second Empire transformations, where we mobilize the historian's tools to start disentangling the complex interactions between changes in French society, the nature of sources, and representations of Jews. While our example is limited in scope, we foresee large potential payoffs in the cooperative interaction between distant and close reading
GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection
Get PDFGraph neural networks are increasingly becoming the framework of choice for
graph-based machine learning. In this paper, we propose a new graph neural
network architecture that substitutes classical message passing with an
analysis of the local distribution of node features. To this end, we extract
the distribution of features in the egonet for each local neighbourhood and
compare them against a set of learned label distributions by taking the
histogram intersection kernel. The similarity information is then propagated to
other nodes in the network, effectively creating a message passing-like
mechanism where the message is determined by the ensemble of the features. We
perform an ablation study to evaluate the network's performance under different
choices of its hyper-parameters. Finally, we test our model on standard graph
classification and regression benchmarks, and we find that it outperforms
widely used alternative approaches, including both graph kernels and graph
neural networks
Non-parametric Spectral Model for Shape Retrieval
No full textNon-rigid 3D shape retrieval is an active and important research topic in content based object retrieval. This problem is often cast in terms of the shapes intrinsic geometry due to its invariance to a wide range of non-rigid deformations. In this paper, we devise a novel generative model for shape retrieval based on the spectral representation of the Laplacian of a mesh. Contrary to common use, our approach avoids the ubiquitous correspondence problem by transforming the eigenvectors of the Laplacian to a density in the spectral-embedding space which is estimated non-parametrically. We show that this model can efficiently be learned from a set of 3D meshes. The experimental results on the SHREC'14 benchmark show the effectiveness of the approach compared to the state-of-the-art
A Non-parametric Spectral Model for Graph Classification
No full textGraph-based representations have been used with considerable success in computer vision in the abstraction and recognition of object shape and scene structure. Despite this, the methodology available for learning structural representations from sets of training examples is relatively limited. In this paper we take a simple yet effective spectral approach to graph learning. In particular, we define a novel model of structural representation based on the spectral decomposition of graph Laplacian of a set of graphs, but which make away with the need of one-to-one node-correspondences at the base of several previous approaches, and handles directly a set of other invariants of the representation which are often neglected. An experimental evaluation shows that the approach significantly improves over the state of the art.Graph-based representations have been used with considerable success in computer vision in the abstraction and recognition of object shape and scene structure. Despite this, the methodology available for learning structural representations from sets of training examples is relatively limited. In this paper we take a simple yet effective spectral approach to graph learning. In particular, we define a novel model of structural representation based on the spectral decomposition of graph Laplacian of a set of graphs, but which make away with the need of one-to-one node-correspondences at the base of several previous approaches, and handles directly a set of other invariants of the representation which are often neglected. An experimental evaluation shows that the approach significantly improves over the state of the ar
k-Anonymity on Graphs using the Szemerédi Regularity Lemma
Get PDFGraph anonymisation aims at reducing the ability of an attacker to identify the nodes of a graph by obfuscating its structural information. In k-anonymity, this means making each node indistinguishable from at least other k-1 nodes. Simply stripping the nodes of a graph of their identifying label is insufficient, as with enough structural knowledge an attacker can still recover the nodes identities. We propose an algorithm to enforce k-anonymity based on the Szemerédi regularity lemma. Given a graph, we start by computing a regular partition of its nodes. The Szemerédi regularity lemma ensures that such a partition exists and that the edges between the sets of nodes behave quasi-randomly. With this partition to hand, we anonymize the graph by randomizing the edges within each set, obtaining a graph that is structurally similar to the original one yet the nodes within each set are structurally indistinguishable. Unlike other k-anonymisation methods, our approach does not consider a single type of attack, but instead it aims to prevent any structure-based de-anonymisation attempt. We test our framework on a wide range of real-world networks and we compare it against another simple yet widely used k-anonymisation technique demonstrating the effectiveness of our approach
On the von Neumann entropy of graphs
No full textThe von Neumann entropy of a graph is a spectral complexity measure that has recently found applications in complex networks analysis and pattern recognition. Two variants of the von Neumann entropy exist based on the graph Laplacian and normalized graph Laplacian, respectively. Due to its computational complexity, previous works have proposed to approximate the von Neumann entropy, effectively reducing it to the computation of simple node degree statistics. Unfortunately, a number of issues surrounding the von Neumann entropy remain unsolved to date, including the interpretation of this spectral measure in terms of structural patterns, understanding the relation between its two variants and evaluating the quality of the corresponding approximations. In this article, we aim to answer these questions by first analysing and comparing the quadratic approximations of the two variants and then performing an extensive set of experiments on both synthetic and real-world graphs. We find that (1) the two entropies lead to the emergence of similar structures, but with some significant differences; (2) the correlation between them ranges from weakly positive to strongly negative, depending on the topology of the underlying graph; (3) the quadratic approximations fail to capture the presence of non-trivial structural patterns that seem to influence the value of the exact entropies; and (4) the quality of the approximations, as well as which variant of the von Neumann entropy is better approximated, depends on the topology of the underlying graph
Thermodynamic Characterization of Temporal Networks
Get PDFTime-evolving networks have proven to be an efficient and effective means of concisely characterising the behaviour of complex systems over time. However, the analysis of such networks and the identification of the underlying dynamical process has proven to be a challenging problem, particularly trying to model the large-scale properties of graphs. In this paper we present a novel method to characterize the behaviour of the evolving systems based on a thermodynamic framework for graphs. This framework aims at relating the major structural changes in time evolving networks to thermodynamic phase transitions. This is achieved by relating the thermodynamics variables to macroscopic changes in network topology. First, by considering a recent quantum-mechanical characterization of the structure of a network, we derive the network entropy. Then we adopt a Schrödinger picture of the dynamics of the network, in order to obtain a measure of energy exchange through the estimation of a hidden time-varying Hamiltonian from the data. Experimental evaluations on real-world data demonstrate how the estimation of this time-varying energy operator strongly characterizes the different states of time evolving networks
- …
