Oh! You keep talking about avoiding duplicates in a hash, but your problem is actually with avoiding duplicates in an array.

A common idiom to weed out duplicates is: (from perlfaq4)

my %seen;
my @array = grep !$seen{$_}++, LIST;
[download]

To insert at the same time, that would be

my %seen;
my @array = grep !$seen{$_}++, @array, $new_value;
[download]

Plug it in and get:

my %edges;
while (<STREAM>) {
   my($node1, $node2) = split;
   my %seen;
   @{$edges{$node1}} = grep !$seen{$_}++, @{$edges{$node1}}, $node2;
}
[download]

A faster (but more memory hungry) version would be:

my %edges;
my %seen;
while (<STREAM>) {
   my($node1, $node2) = split;
   next if !$seen{$node1}{$node2}++;
   push @{$edges{$node1}}, $node2;
}
[download]

Ahh Yes! Thanks for someone still making sense out of my
pitifully worded question!
The point is that I want to avoid duplicates in values, not keys.
When googled this bit, I found out I could use Tie::Hash::Multivalue
for ensuring I can add multiple values
to a key in the hash, and I can pass an argument
'Unique' to ensure that only unique values get added.
So that was my original question - how do I pass the argument
"unique" to Tie::Hash::Multivalue?

Thanks all for responding!

use warnings;
use strict;

use Data::Dumper;


my %edges;  # created empty

while (<DATA>) {

    my ($node1, $node2) = split;

    # nothing to do if node1 already has a node2 in its array.
    next if exists $edges{$node1}{present}{$node2};

    # node2 not already there: push it, mark it present.
    push @{ $edges{$node1}{array} }, $node2;
    $edges{$node1}{present}{$node2} = 1;

    }

# transform hash to final structure.
for my $node (keys %edges) {  # for each node1 of hash...
    # presence flags no longer needed: eliminate them.
    delete $edges{$node}{present};
    # associate each node1 directly with its node2 array ref.
    $edges{$node} = delete $edges{$node}{array};
    }

# see what we got.
print Dumper \%edges;

__DATA__
1 2
1 3
1 4
1 2
1 5
2 1
1 2
2 2
1 6
2 3
1 2
2 2
[download]

>perl uniq_hash_value_1.pl
$VAR1 = {
          '1' => [
                   '2',
                   '3',
                   '4',
                   '5',
                   '6'
                 ],
          '2' => [
                   '1',
                   '2',
                   '3'
                 ]
        };
[download]