Graph Aggregation

2016-09-13 · Ulle Endriss, Umberto Grandi

Graph aggregation is the process of computing a single output graph that constitutes a good compromise between several input graphs, each provided by a different source. One needs to perform graph aggregation in a wide variety of situations, e.g., when applying a voting rule (graphs as preference orders), when consolidating conflicting views regarding the relationships between arguments in a debate (graphs as abstract argumentation frameworks), or when computing a consensus between several alternative clusterings of a given dataset (graphs as equivalence relations). In this paper, we introduce a formal framework for graph aggregation grounded in social choice theory. Our focus is on understanding which properties shared by the individual input graphs will transfer to the output graph returned by a given aggregation rule. We consider both common properties of graphs, such as transitivity and reflexivity, and arbitrary properties expressible in certain fragments of modal logic. Our results establish several connections between the types of properties preserved under aggregation and the choice-theoretic axioms satisfied by the rules used. The most important of these results is a powerful impossibility theorem that generalises Arrow's seminal result for the aggregation of preference orders to a large collection of different types of graphs.

📄 PDF Abstract BibTeX arXiv:1609.03765

Code (0)

등록된 구현이 없습니다.

Tasks

Abstract Argumentation

HyperAggregation: Aggregating over Graph Edges with Hypernetworks

2024-07-16 · Nicolas Lell, Ansgar Scherp

HyperAggregation is a hypernetwork-based aggregation function for Graph Neural Networks. It uses a hypernetwork to dynamically generate weights in the size of the current neighborhood, which are then used to aggregate th…

Graph Classification Graph Regression Node Classification

On Local Aggregation in Heterophilic Graphs

2021-06-06 · Hesham Mostafa, Marcel Nassar, Somdeb Majumdar

Many recent works have studied the performance of Graph Neural Networks (GNNs) in the context of graph homophily - a label-dependent measure of connectivity. Traditional GNNs generate node embeddings by aggregating infor…

Node Classification

Causality-aware Graph Aggregation Weight Estimator for Popularity Debiasing in Top-K Recommendation

2025-10-06 · Yue Que, Yingyi Zhang, Xiangyu Zhao, Chen Ma arxiv

Graph-based recommender systems leverage neighborhood aggregation to generate node representations, which is highly sensitive to popularity bias, resulting in an echo effect during information propagation. Existing graph…

Causal Inference

HAGNN: Hybrid Aggregation for Heterogeneous Graph Neural Networks

2023-07-04 · Guanghui Zhu, Zhennan Zhu, Hongyang Chen, Chunfeng Yuan 외

Heterogeneous graph neural networks (GNNs) have been successful in handling heterogeneous graphs. In existing heterogeneous GNNs, meta-path plays an essential role. However, recent work pointed out that simple homogeneou…

Link Prediction Node Classification Node Clustering

A Visibility Graph Averaging Aggregation Operator

2013-11-17 · Shiyu Chen, Yong Hu, Sankaran Mahadevan, Yong Deng

The problem of aggregation is considerable importance in many disciplines. In this paper, a new type of operator called visibility graph averaging (VGA) aggregation operator is proposed. This proposed operator is based o…

Time Series Time Series Analysis